Main Page | Data Structures | File List | Data Fields | Globals | Search for 

codemp/game/tri_coll_test.c File Reference

#include <math.h>
#include "../game/q_shared.h"
#include "../game/g_local.h"

Go to the source code of this file.

Defines

#define USE_EPSILON_TEST   1
#define EPSILON   0.000001
#define CROSS(dest, v1, v2)
#define DOT(v1, v2)   (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
#define SUB(dest, v1, v2)
#define SORT(a, b)
#define ISECT(VV0, VV1, VV2, D0, D1, D2, isect0, isect1)
#define COMPUTE_INTERVALS(VV0, VV1, VV2, D0, D1, D2, D0D1, D0D2, isect0, isect1)
#define EDGE_EDGE_TEST(V0, U0, U1)
#define EDGE_AGAINST_TRI_EDGES(V0, V1, U0, U1, U2)
#define POINT_IN_TRI(V0, U0, U1, U2)

Functions

qboolean coplanar_tri_tri (vec3_t N, vec3_t V0, vec3_t V1, vec3_t V2, vec3_t U0, vec3_t U1, vec3_t U2)
qboolean tri_tri_intersect (vec3_t V0, vec3_t V1, vec3_t V2, vec3_t U0, vec3_t U1, vec3_t U2)

Define Documentation

#define COMPUTE_INTERVALS (  VV0,
VV1,
VV2,
D0,
D1,
D2,
D0D1,
D0D2,
isect0,
isect1   ) 
 

Value:

if(D0D1>0.0f)                                         \
  {                                                     \
                        \
      \
    ISECT(VV2,VV0,VV1,D2,D0,D1,isect0,isect1);          \
  }                                                     \
  else if(D0D2>0.0f)                                    \
  {                                                     \
                        \
    ISECT(VV1,VV0,VV2,D1,D0,D2,isect0,isect1);          \
  }                                                     \
  else if(D1*D2>0.0f || D0!=0.0f)                       \
  {                                                     \
        \
    ISECT(VV0,VV1,VV2,D0,D1,D2,isect0,isect1);          \
  }                                                     \
  else if(D1!=0.0f)                                     \
  {                                                     \
    ISECT(VV1,VV0,VV2,D1,D0,D2,isect0,isect1);          \
  }                                                     \
  else if(D2!=0.0f)                                     \
  {                                                     \
    ISECT(VV2,VV0,VV1,D2,D0,D1,isect0,isect1);          \
  }                                                     \
  else                                                  \
  {                                                     \
                             \
    return coplanar_tri_tri(N1,V0,V1,V2,U0,U1,U2);      \
  }

Definition at line 55 of file tri_coll_test.c.

Referenced by tri_tri_intersect().

#define CROSS (  dest,
v1,
v2   ) 
 

Value:

dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
              dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
              dest[2]=v1[0]*v2[1]-v1[1]*v2[0];

Definition at line 28 of file tri_coll_test.c.

Referenced by tri_tri_intersect().

#define DOT (  v1,
v2   )     (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
 

Definition at line 33 of file tri_coll_test.c.

Referenced by tri_tri_intersect().

#define EDGE_AGAINST_TRI_EDGES (  V0,
V1,
U0,
U1,
U2   ) 
 

Value:

{                                              \
  float Ax,Ay,Bx,By,Cx,Cy,e,d,f;               \
  Ax=V1[i0]-V0[i0];                            \
  Ay=V1[i1]-V0[i1];                            \
             \
  EDGE_EDGE_TEST(V0,U0,U1);                    \
             \
  EDGE_EDGE_TEST(V0,U1,U2);                    \
             \
  EDGE_EDGE_TEST(V0,U2,U0);                    \
}

Definition at line 111 of file tri_coll_test.c.

Referenced by coplanar_tri_tri().

#define EDGE_EDGE_TEST (  V0,
U0,
U1   ) 
 

Value:

Bx=U0[i0]-U1[i0];                                   \
  By=U0[i1]-U1[i1];                                   \
  Cx=V0[i0]-U0[i0];                                   \
  Cy=V0[i1]-U0[i1];                                   \
  f=Ay*Bx-Ax*By;                                      \
  d=By*Cx-Bx*Cy;                                      \
  if((f>0 && d>=0 && d<=f) || (f<0 && d<=0 && d>=f))  \
  {                                                   \
    e=Ax*Cy-Ay*Cx;                                    \
    if(f>0)                                           \
    {                                                 \
      if(e>=0 && e<=f) return 1;                      \
    }                                                 \
    else                                              \
    {                                                 \
      if(e<=0 && e>=f) return 1;                      \
    }                                                 \
  }

Definition at line 91 of file tri_coll_test.c.

#define EPSILON   0.000001
 

Definition at line 24 of file tri_coll_test.c.

Referenced by tri_tri_intersect().

#define ISECT (  VV0,
VV1,
VV2,
D0,
D1,
D2,
isect0,
isect1   ) 
 

Value:

isect0=VV0+(VV1-VV0)*D0/(D0-D1);    \
              isect1=VV0+(VV2-VV0)*D0/(D0-D2);

Definition at line 50 of file tri_coll_test.c.

#define POINT_IN_TRI (  V0,
U0,
U1,
U2   ) 
 

Value:

{                                           \
  float a,b,c,d0,d1,d2;                     \
             \
    \
  a=U1[i1]-U0[i1];                          \
  b=-(U1[i0]-U0[i0]);                       \
  c=-a*U0[i0]-b*U0[i1];                     \
  d0=a*V0[i0]+b*V0[i1]+c;                   \
                                            \
  a=U2[i1]-U1[i1];                          \
  b=-(U2[i0]-U1[i0]);                       \
  c=-a*U1[i0]-b*U1[i1];                     \
  d1=a*V0[i0]+b*V0[i1]+c;                   \
                                            \
  a=U0[i1]-U2[i1];                          \
  b=-(U0[i0]-U2[i0]);                       \
  c=-a*U2[i0]-b*U2[i1];                     \
  d2=a*V0[i0]+b*V0[i1]+c;                   \
  if(d0*d1>0.0)                             \
  {                                         \
    if(d0*d2>0.0) return 1;                 \
  }                                         \
}

Definition at line 124 of file tri_coll_test.c.

Referenced by coplanar_tri_tri().

#define SORT (  a,
b   ) 
 

Value:

if(a>b)    \
             {          \
               float c; \
               c=a;     \
               a=b;     \
               b=c;     \
             }

Definition at line 41 of file tri_coll_test.c.

Referenced by tri_tri_intersect().

#define SUB (  dest,
v1,
v2   ) 
 

Value:

dest[0]=v1[0]-v2[0]; \
            dest[1]=v1[1]-v2[1]; \
            dest[2]=v1[2]-v2[2];

Definition at line 35 of file tri_coll_test.c.

Referenced by tri_tri_intersect().

#define USE_EPSILON_TEST   1
 

Definition at line 23 of file tri_coll_test.c.

Function Documentation

qboolean coplanar_tri_tri (  vec3_t  N,
vec3_t  V0,
vec3_t  V1,
vec3_t  V2,
vec3_t  U0,
vec3_t  U1,
vec3_t  U2
) 
 

Definition at line 149 of file tri_coll_test.c.

References EDGE_AGAINST_TRI_EDGES, fabs(), POINT_IN_TRI, qboolean, qfalse, and vec3_t. 

00151 {
00152    vec3_t A;
00153    short i0,i1;
00154    /* first project onto an axis-aligned plane, that maximizes the area */
00155    /* of the triangles, compute indices: i0,i1. */
00156    A[0]=fabs(N[0]);
00157    A[1]=fabs(N[1]);
00158    A[2]=fabs(N[2]);
00159    if(A[0]>A[1])
00160    {
00161       if(A[0]>A[2])  
00162       {
00163           i0=1;      /* A[0] is greatest */
00164           i1=2;
00165       }
00166       else
00167       {
00168           i0=0;      /* A[2] is greatest */
00169           i1=1;
00170       }
00171    }
00172    else   /* A[0]<=A[1] */
00173    {
00174       if(A[2]>A[1])
00175       {
00176           i0=0;      /* A[2] is greatest */
00177           i1=1;                                           
00178       }
00179       else
00180       {
00181           i0=0;      /* A[1] is greatest */
00182           i1=2;
00183       }
00184     }               
00185                 
00186     /* test all edges of triangle 1 against the edges of triangle 2 */
00187     EDGE_AGAINST_TRI_EDGES(V0,V1,U0,U1,U2);
00188     EDGE_AGAINST_TRI_EDGES(V1,V2,U0,U1,U2);
00189     EDGE_AGAINST_TRI_EDGES(V2,V0,U0,U1,U2);
00190                 
00191     /* finally, test if tri1 is totally contained in tri2 or vice versa */
00192     POINT_IN_TRI(V0,U0,U1,U2);
00193     POINT_IN_TRI(U0,V0,V1,V2);
00194 
00195     return qfalse;
00196 }

qboolean tri_tri_intersect (  vec3_t  V0,
vec3_t  V1,
vec3_t  V2,
vec3_t  U0,
vec3_t  U1,
vec3_t  U2
) 
 

Definition at line 198 of file tri_coll_test.c.

References COMPUTE_INTERVALS, CROSS, DOT, EPSILON, fabs(), qboolean, qfalse, qtrue, SORT, SUB, and vec3_t.

Referenced by WP_SabersIntersect(). 

00200 {
00201   vec3_t E1,E2;
00202   vec3_t N1,N2;
00203   float d1,d2;
00204   float du0,du1,du2,dv0,dv1,dv2;
00205   vec3_t D;
00206   float isect1[2], isect2[2];
00207   float du0du1,du0du2,dv0dv1,dv0dv2;
00208   short index;
00209   float vp0,vp1,vp2;
00210   float up0,up1,up2;
00211   float b,c,max;
00212 
00213   /* compute plane equation of triangle(V0,V1,V2) */
00214   SUB(E1,V1,V0);
00215   SUB(E2,V2,V0);
00216   CROSS(N1,E1,E2);
00217   d1=-DOT(N1,V0);
00218   /* plane equation 1: N1.X+d1=0 */
00219 
00220   /* put U0,U1,U2 into plane equation 1 to compute signed distances to the plane*/
00221   du0=DOT(N1,U0)+d1;
00222   du1=DOT(N1,U1)+d1;
00223   du2=DOT(N1,U2)+d1;
00224 
00225   /* coplanarity robustness check */
00226 #if USE_EPSILON_TEST
00227   if(fabs(du0)<EPSILON) du0=0.0;
00228   if(fabs(du1)<EPSILON) du1=0.0;
00229   if(fabs(du2)<EPSILON) du2=0.0;
00230 #endif
00231   du0du1=du0*du1;
00232   du0du2=du0*du2;
00233 
00234   if(du0du1>0.0f && du0du2>0.0f) /* same sign on all of them + not equal 0 ? */
00235     return 0;                    /* no intersection occurs */
00236 
00237   /* compute plane of triangle (U0,U1,U2) */
00238   SUB(E1,U1,U0);
00239   SUB(E2,U2,U0);
00240   CROSS(N2,E1,E2);
00241   d2=-DOT(N2,U0);
00242   /* plane equation 2: N2.X+d2=0 */
00243 
00244   /* put V0,V1,V2 into plane equation 2 */
00245   dv0=DOT(N2,V0)+d2;
00246   dv1=DOT(N2,V1)+d2;
00247   dv2=DOT(N2,V2)+d2;
00248 
00249 #if USE_EPSILON_TEST
00250   if(fabs(dv0)<EPSILON) dv0=0.0;
00251   if(fabs(dv1)<EPSILON) dv1=0.0;
00252   if(fabs(dv2)<EPSILON) dv2=0.0;
00253 #endif
00254 
00255   dv0dv1=dv0*dv1;
00256   dv0dv2=dv0*dv2;
00257         
00258   if(dv0dv1>0.0f && dv0dv2>0.0f) /* same sign on all of them + not equal 0 ? */
00259     return 0;                    /* no intersection occurs */
00260 
00261   /* compute direction of intersection line */
00262   CROSS(D,N1,N2);
00263 
00264   /* compute and index to the largest component of D */
00265   max=fabs(D[0]);
00266   index=0;
00267   b=fabs(D[1]);
00268   c=fabs(D[2]);
00269   if(b>max) max=b,index=1;
00270   if(c>max) max=c,index=2;
00271 
00272         /* this is the simplified projection onto L*/
00273         vp0=V0[index];
00274         vp1=V1[index];
00275         vp2=V2[index];
00276 
00277         up0=U0[index];
00278         up1=U1[index];
00279         up2=U2[index];
00280 
00281   /* compute interval for triangle 1 */
00282   COMPUTE_INTERVALS(vp0,vp1,vp2,dv0,dv1,dv2,dv0dv1,dv0dv2,isect1[0],isect1[1]);
00283 
00284   /* compute interval for triangle 2 */
00285   COMPUTE_INTERVALS(up0,up1,up2,du0,du1,du2,du0du1,du0du2,isect2[0],isect2[1]);
00286 
00287   SORT(isect1[0],isect1[1]);
00288   SORT(isect2[0],isect2[1]);
00289 
00290   if(isect1[1]<isect2[0] || isect2[1]<isect1[0]) return qtrue;
00291   return qfalse;
00292 }