opttritri.h

Go to the documentation of this file.
00001 #ifndef OPTTRITRI_H
00002 #define OPTTRITRI_H
00003 
00004 /* Triangle/triangle intersection test routine,
00005  * by Tomas Moller, 1997.
00006  * See article "A Fast Triangle-Triangle Intersection Test",
00007  * Journal of Graphics Tools, 2(2), 1997
00008  *
00009  * Updated June 1999: removed the divisions -- a little faster now!
00010  * Updated October 1999: added {} to CROSS and SUB macros 
00011  *
00012  * int NoDivTriTriIsect(double V0[3],double V1[3],double V2[3],
00013  *                      double U0[3],double U1[3],double U2[3])
00014  *
00015  * parameters: vertices of triangle 1: V0,V1,V2
00016  *             vertices of triangle 2: U0,U1,U2
00017  * result    : returns 1 if the triangles intersect, otherwise 0
00018  *
00019  */
00020 
00021 #include <math.h>
00022 
00023 #include "meshmorph.h"
00024 
00025 #define FABS(x) (fabs(x))        /* implement as is fastest on your machine */
00026 
00027 /* if USE_EPSILON_TEST is true then we do a check:
00028    if |dv|<EPSILON then dv=0.0;
00029    else no check is done (which is less robust)
00030    */
00031 #define USE_EPSILON_TEST TRUE
00032 
00033 /* sort so that a<=b */
00034 #define SORT(a,b)       \
00035       if(a>b)    \
00036 {          \
00037   double c; \
00038   c=a;     \
00039   a=b;     \
00040   b=c;     \
00041 }
00042 
00043 
00044 /* this edge to edge test is based on Franlin Antonio's gem:
00045    "Faster Line Segment Intersection", in Graphics Gems III,
00046    pp. 199-202 */
00047 #define EDGE_EDGE_TEST(V0,U0,U1)                      \
00048       Bx=U0->p[i0]-U1->p[i0];                                   \
00049 By=U0->p[i1]-U1->p[i1];                                   \
00050 Cx=V0->p[i0]-U0->p[i0];                                   \
00051 Cy=V0->p[i1]-U0->p[i1];                                   \
00052 f=Ay*Bx-Ax*By;                                      \
00053 d=By*Cx-Bx*Cy;                                      \
00054 if((f>0 && d>=0 && d<=f) || (f<0 && d<=0 && d>=f))  \
00055 {                                                   \
00056   e=Ax*Cy-Ay*Cx;                                    \
00057   if(f>0)                                           \
00058   {                                                 \
00059     if(e>=0 && e<=f) return 1;                      \
00060   }                                                 \
00061   else                                              \
00062   {                                                 \
00063     if(e<=0 && e>=f) return 1;                      \
00064   }                                                 \
00065 }
00066 
00067 #define EDGE_AGAINST_TRI_EDGES(V0,V1,U0,U1,U2) \
00068 {                                              \
00069   double Ax,Ay,Bx,By,Cx,Cy,e,d,f;               \
00070   Ax=V1->p[i0]-V0->p[i0];                            \
00071   Ay=V1->p[i1]-V0->p[i1];                            \
00072   /* test edge U0,U1 against V0,V1 */          \
00073   EDGE_EDGE_TEST(V0,U0,U1);                    \
00074   /* test edge U1,U2 against V0,V1 */          \
00075   EDGE_EDGE_TEST(V0,U1,U2);                    \
00076   /* test edge U2,U1 against V0,V1 */          \
00077   EDGE_EDGE_TEST(V0,U2,U0);                    \
00078 }
00079 
00080 #define POINT_IN_TRI(V0,U0,U1,U2)           \
00081 {                                           \
00082   double a,b,c,d0,d1,d2;                     \
00083   /* is T1 completly inside T2? */          \
00084   /* check if V0 is inside tri(U0,U1,U2) */ \
00085   a=U1->p[i1]-U0->p[i1];                          \
00086   b=-(U1->p[i0]-U0->p[i0]);                       \
00087   c=-a*U0->p[i0]-b*U0->p[i1];                     \
00088   d0=a*V0->p[i0]+b*V0->p[i1]+c;                   \
00089   \
00090   a=U2->p[i1]-U1->p[i1];                          \
00091   b=-(U2->p[i0]-U1->p[i0]);                       \
00092   c=-a*U1->p[i0]-b*U1->p[i1];                     \
00093   d1=a*V0->p[i0]+b*V0->p[i1]+c;                   \
00094   \
00095   a=U0->p[i1]-U2->p[i1];                          \
00096   b=-(U0->p[i0]-U2->p[i0]);                       \
00097   c=-a*U2->p[i0]-b*U2->p[i1];                     \
00098   d2=a*V0->p[i0]+b*V0->p[i1]+c;                   \
00099   if(d0*d1>0.0)                             \
00100   {                                         \
00101     if(d0*d2>0.0) return 1;                 \
00102   }                                         \
00103 }
00104 
00105 int coplanar_tri_tri(vector3 & N,vector3 const * V0,vector3 const * V1,vector3 const * V2,
00106                      vector3 const * U0,vector3 const * U1,vector3 const * U2);
00107 
00108 
00109 
00110 #define NEWCOMPUTE_INTERVALS(VV0,VV1,VV2,D0,D1,D2,D0D1,D0D2,A,B,C,X0,X1) \
00111 { \
00112   if(D0D1>0.0f) \
00113   { \
00114     /* here we know that D0D2<=0.0 */ \
00115     /* that is D0, D1 are on the same side, D2 on the other or on the plane */ \
00116     A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
00117   } \
00118   else if(D0D2>0.0f)\
00119   { \
00120     /* here we know that d0d1<=0.0 */ \
00121     A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
00122   } \
00123   else if(D1*D2>0.0f || D0!=0.0f) \
00124   { \
00125     /* here we know that d0d1<=0.0 or that D0!=0.0 */ \
00126     A=VV0; B=(VV1-VV0)*D0; C=(VV2-VV0)*D0; X0=D0-D1; X1=D0-D2; \
00127   } \
00128   else if(D1!=0.0f) \
00129   { \
00130     A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
00131   } \
00132   else if(D2!=0.0f) \
00133   { \
00134     A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
00135   } \
00136   else \
00137   { \
00138     /* triangles are coplanar */ \
00139     return coplanar_tri_tri(N1,V0,V1,V2,U0,U1,U2); \
00140   } \
00141 }
00142 
00143 
00144 
00145 int NoDivTriTriIsect(vector3 const * V0,vector3 const * V1,vector3 const * V2,
00146                      vector3 const * U0,vector3 const * U1,vector3 const * U2);
00147 
00148 int intersect_triangle3(vector3 const * orig, vector3 const * end, vector3 const * normal,
00149                         vector3 const * vert0, vector3 const * vert1, vector3 const * vert2,
00150                         result & r);
00151 #endif

Generated on Fri Feb 13 13:58:10 2009 for meshmorph by  doxygen 1.5.1