tritri.cpp File Reference

#include <cmath>
#include <cstring>
#include <cstdlib>
#include "math_util.h"

Namespaces
namespace	ug
	the ug namespace

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

Functions
int	coplanar_tri_tri (number N[3], number V0[3], number V1[3], number V2[3], number U0[3], number U1[3], number U2[3])
int	tri_tri_intersect (number V0[3], number V1[3], number V2[3], number U0[3], number U1[3], number U2[3], number *ip1Out, number *ip2Out, const number snapThreshold)
UG_API bool	ug::TriangleTriangleIntersection (const MathVector< 3 > &p0, const MathVector< 3 > &p1, const MathVector< 3 > &p2, const MathVector< 3 > &q0, const MathVector< 3 > &q1, const MathVector< 3 > &q2, MathVector< 3 > *ip1Out=NULL, MathVector< 3 > *ip2Out=NULL, number snapThreshold=SMALL)
	checks whether two triangles intersect and returns the intervals, if they do.

Macro Definition Documentation

COMPUTE_INTERVAL_POINTS

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

Value:

  if(D0D1>0.0f)                                         \
  {                                                     \
    /* here we know that D0D2<=0.0 */                   \
    /* that is D0, D1 are on the same side, D2 on the other or on the plane */ \
    ISECT3(VV2,VV0,VV1,D2,D0,D1,isect0,isect1);          \
  }                                                     \
  else if(D0D2>0.0f)                                    \
  {                                                     \
    /* here we know that d0d1<=0.0 */                   \
    ISECT3(VV1,VV0,VV2,D1,D0,D2,isect0,isect1);          \
  }                                                     \
  else if(D1*D2>0.0f || D0!=0.0f)                       \
  {                                                     \
    /* here we know that d0d1<=0.0 or that D0!=0.0 */   \
    ISECT3(VV0,VV1,VV2,D0,D1,D2,isect0,isect1);          \
  }                                                     \
  else if(D1!=0.0f)                                     \
  {                                                     \
    ISECT3(VV1,VV0,VV2,D1,D0,D2,isect0,isect1);          \
  }                                                     \
  else if(D2!=0.0f)                                     \
  {                                                     \
    ISECT3(VV2,VV0,VV1,D2,D0,D1,isect0,isect1);          \
  }                                                     \
  else                                                  \
  {                                                     \
    /* triangles are coplanar */                        \
  /* we ignore this case since it we already returned.*/ \
  }

COMPUTE_INTERVALS

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

Value:

  if(D0D1>0.0f)                                         \
  {                                                     \
    /* here we know that D0D2<=0.0 */                   \
    /* that is D0, D1 are on the same side, D2 on the other or on the plane */ \
    ISECT(VV2,VV0,VV1,D2,D0,D1,isect0,isect1);          \
  }                                                     \
  else if(D0D2>0.0f)                                    \
  {                                                     \
    /* here we know that d0d1<=0.0 */                   \
    ISECT(VV1,VV0,VV2,D1,D0,D2,isect0,isect1);          \
  }                                                     \
  else if(D1*D2>0.0f || D0!=0.0f)                       \
  {                                                     \
    /* here we know that d0d1<=0.0 or that D0!=0.0 */   \
    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                                                  \
  {                                                     \
    /* triangles are coplanar */                        \
    return coplanar_tri_tri(N1,V0,V1,V2,U0,U1,U2);      \
  }

CROSS

#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];

DOT

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

EDGE_AGAINST_TRI_EDGES

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

Value:

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

EDGE_EDGE_TEST

#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 2;                      \
    }                                                 \
    else                                              \
    {                                                 \
      if(e<=0 && e>=f) return 2;                      \
    }                                                 \
  }

EPSILON

#define EPSILON   1.e-12

ISECT

#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);

ISECT3

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

Value:

              isect0[0]=VV0[0]+(VV1[0]-VV0[0])*D0/(D0-D1);    \
              isect0[1]=VV0[1]+(VV1[1]-VV0[1])*D0/(D0-D1);    \
              isect0[2]=VV0[2]+(VV1[2]-VV0[2])*D0/(D0-D1);    \
              isect1[0]=VV0[0]+(VV2[0]-VV0[0])*D0/(D0-D2);    \
              isect1[1]=VV0[1]+(VV2[1]-VV0[1])*D0/(D0-D2);    \
              isect1[2]=VV0[2]+(VV2[2]-VV0[2])*D0/(D0-D2);

POINT_IN_TRI

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

Value:

{                                           \
  number a,b,c,d0,d1,d2;                     \
  /* is T1 completly inside T2? */          \
  /* check if V0 is inside tri(U0,U1,U2) */ \
  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 2;                 \
  }                                         \
}

SORT

#define SORT	(		a,
			b
	)

Value:

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

SUB

#define SUB	(		dest,
			v1,
			v2
	)

Value:

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

USE_EPSILON_TEST

#define USE_EPSILON_TEST   TRUE

Function Documentation

coplanar_tri_tri()

int coplanar_tri_tri	(	number	N[3],
		number	V0[3],
		number	V1[3],
		number	V2[3],
		number	U0[3],
		number	U1[3],
		number	U2[3]
	)

References EDGE_AGAINST_TRI_EDGES, and POINT_IN_TRI.

tri_tri_intersect()

int tri_tri_intersect	(	number	V0[3],
		number	V1[3],
		number	V2[3],
		number	U0[3],
		number	U1[3],
		number	U2[3],
		number *	ip1Out,
		number *	ip2Out,
		const number	snapThreshold
	)

References COMPUTE_INTERVAL_POINTS, COMPUTE_INTERVALS, CROSS, DOT, and SUB.

Referenced by ug::TriangleTriangleIntersection().