BRL-CAD
tri_tri.c File Reference
#include "common.h"
#include <math.h>
#include "vmath.h"
#include "bn/plane_struct.h"
#include "bn/plane_calc.h"
#include "bn/tol.h"
#include "bn/tri_tri.h"
Include dependency graph for tri_tri.c:

Go to the source code of this file.

Macros

#define USE_EPSILON_TEST   1
 
#define EPSILON   0.000001
 
#define SORT(a, b)
 
#define SORT2(a, b, smallest)
 
#define EDGE_EDGE_TEST(V0, U0, U1)
 
#define EDGE_EDGE_TEST_AREA(V0, U0, U1)
 
#define EDGE_AGAINST_TRI_EDGES(V0, V1, U0, U1, U2)
 
#define EDGE_AGAINST_TRI_EDGES_AREA(V0, V1, U0, U1, U2)
 
#define POINT_IN_TRI(V0, U0, U1, U2)
 
#define NEWCOMPUTE_INTERVALS(VV0, VV1, VV2, D0, D1, D2, D0D1, D0D2, A, B, C, X0, X1)
 

Functions

int bn_tri_tri_isect_coplanar (point_t V0, point_t V1, point_t V2, point_t U0, point_t U1, point_t U2, int area_flag)
 Tomas Möller's triangle/triangle intersection routines from the article. More...
 
int coplanar_tri_tri (point_t N, point_t V0, point_t V1, point_t V2, point_t U0, point_t U1, point_t U2)
 
int bn_tri_tri_isect (point_t V0, point_t V1, point_t V2, point_t U0, point_t U1, point_t U2)
 
void calc_isect2 (point_t VTX0, point_t VTX1, point_t VTX2, fastf_t VV0, fastf_t VV1, fastf_t VV2, fastf_t D0, fastf_t D1, fastf_t D2, fastf_t *isect0, fastf_t *isect1, point_t isectpoint0, point_t isectpoint1)
 
int compute_intervals_isectline (point_t VERT0, point_t VERT1, point_t VERT2, fastf_t VV0, fastf_t VV1, fastf_t VV2, fastf_t D0, fastf_t D1, fastf_t D2, fastf_t D0D1, fastf_t D0D2, fastf_t *isect0, fastf_t *isect1, point_t isectpoint0, point_t isectpoint1)
 
int bn_tri_tri_isect_with_line (point_t V0, point_t V1, point_t V2, point_t U0, point_t U1, point_t U2, int *coplanar, point_t *isectpt1, point_t *isectpt2)
 

Macro Definition Documentation

#define USE_EPSILON_TEST   1

Definition at line 70 of file tri_tri.c.

#define EPSILON   0.000001
#define SORT (   a,
 
)
Value:
if (a>b) { \
fastf_t c_tmp; \
c_tmp=a; \
a=b; \
b=c_tmp; \
}
double fastf_t
Definition: defines.h:300

Definition at line 74 of file tri_tri.c.

Referenced by attr_cmd(), and bn_tri_tri_isect().

#define SORT2 (   a,
  b,
  smallest 
)
Value:
if (a>b) { \
fastf_t c_tmp; \
c_tmp=a; \
a=b; \
b=c_tmp; \
smallest=1; \
} \
else smallest=0;
else
Definition: nmg_mod.c:3872
double fastf_t
Definition: defines.h:300

Definition at line 82 of file tri_tri.c.

Referenced by bn_tri_tri_isect_with_line().

#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; \
} \
}
if(share_geom)
Definition: nmg_mod.c:3829
else
Definition: nmg_mod.c:3872

Definition at line 96 of file tri_tri.c.

#define EDGE_EDGE_TEST_AREA (   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 && !NEAR_EQUAL(d, f, EPSILON)) || (f<0 && d<0 && d>f && !NEAR_EQUAL(d, f, EPSILON))) { \
e=Ax*Cy-Ay*Cx; \
if (f>EPSILON) { \
if (e>EPSILON && e<f && !NEAR_EQUAL(e, f, EPSILON)) return 1; \
} else { \
if (e<EPSILON && e>f && !NEAR_EQUAL(e, f, EPSILON)) return 1; \
} \
}
#define EPSILON
Definition: tri_tri.c:71
if(share_geom)
Definition: nmg_mod.c:3829
else
Definition: nmg_mod.c:3872

Definition at line 112 of file tri_tri.c.

#define EDGE_AGAINST_TRI_EDGES (   V0,
  V1,
  U0,
  U1,
  U2 
)
Value:
{ \
fastf_t 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); \
}
#define EDGE_EDGE_TEST(V0, U0, U1)
Definition: tri_tri.c:96
double fastf_t
Definition: defines.h:300

Definition at line 129 of file tri_tri.c.

Referenced by bn_tri_tri_isect_coplanar(), and coplanar_tri_tri().

#define EDGE_AGAINST_TRI_EDGES_AREA (   V0,
  V1,
  U0,
  U1,
  U2 
)
Value:
{ \
fastf_t 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_AREA(V0, U0, U1); \
/* test edge U1, U2 against V0, V1 */ \
EDGE_EDGE_TEST_AREA(V0, U1, U2); \
/* test edge U2, U1 against V0, V1 */ \
EDGE_EDGE_TEST_AREA(V0, U2, U0); \
}
#define EDGE_EDGE_TEST_AREA(V0, U0, U1)
Definition: tri_tri.c:112
double fastf_t
Definition: defines.h:300

Definition at line 143 of file tri_tri.c.

Referenced by bn_tri_tri_isect_coplanar().

#define POINT_IN_TRI (   V0,
  U0,
  U1,
  U2 
)
Value:
{ \
fastf_t a, b, c, d0, d1, d2; \
/* is T1 completely 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 1; \
} \
}
if(share_geom)
Definition: nmg_mod.c:3829
double fastf_t
Definition: defines.h:300

Definition at line 157 of file tri_tri.c.

Referenced by bn_tri_tri_isect_coplanar(), and coplanar_tri_tri().

#define NEWCOMPUTE_INTERVALS (   VV0,
  VV1,
  VV2,
  D0,
  D1,
  D2,
  D0D1,
  D0D2,
  A,
  B,
  C,
  X0,
  X1 
)
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 */ \
A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
} else if (D0D2>0.0f) { \
/* here we know that d0d1<=0.0 */ \
A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
} else if (D1*D2>0.0f || !NEAR_ZERO(D0, SMALL_FASTF)) { \
/* here we know that d0d1<=0.0 or that D0!=0.0 */ \
A=VV0; B=(VV1-VV0)*D0; C=(VV2-VV0)*D0; X0=D0-D1; X1=D0-D2; \
} else if (!NEAR_ZERO(D1, SMALL_FASTF)) { \
A=VV1; B=(VV0-VV1)*D1; C=(VV2-VV1)*D1; X0=D1-D0; X1=D1-D2; \
} else if (!NEAR_ZERO(D2, SMALL_FASTF)) { \
A=VV2; B=(VV0-VV2)*D2; C=(VV1-VV2)*D2; X0=D2-D0; X1=D2-D1; \
} else { \
/* triangles are coplanar */ \
return coplanar_tri_tri(N1, V0, V1, V2, U0, U1, U2); \
} \
}
fastf_t C[2 *MAX_CNT+1][2 *MAX_CNT+1]
Definition: dsp_brep.cpp:38
#define SMALL_FASTF
Definition: defines.h:342
if(share_geom)
Definition: nmg_mod.c:3829
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
#define A
Definition: msr.c:51
int coplanar_tri_tri(point_t N, point_t V0, point_t V1, point_t V2, point_t U0, point_t U1, point_t U2)
Definition: tri_tri.c:253

Definition at line 296 of file tri_tri.c.

Referenced by bn_tri_tri_isect().

Function Documentation

int coplanar_tri_tri ( point_t  N,
point_t  V0,
point_t  V1,
point_t  V2,
point_t  U0,
point_t  U1,
point_t  U2 
)

Definition at line 253 of file tri_tri.c.

References A, EDGE_AGAINST_TRI_EDGES, and POINT_IN_TRI.

Referenced by bn_tri_tri_isect_with_line().

void calc_isect2 ( point_t  VTX0,
point_t  VTX1,
point_t  VTX2,
fastf_t  VV0,
fastf_t  VV1,
fastf_t  VV2,
fastf_t  D0,
fastf_t  D1,
fastf_t  D2,
fastf_t isect0,
fastf_t isect1,
point_t  isectpoint0,
point_t  isectpoint1 
)

Definition at line 434 of file tri_tri.c.

Referenced by compute_intervals_isectline().

int compute_intervals_isectline ( point_t  VERT0,
point_t  VERT1,
point_t  VERT2,
fastf_t  VV0,
fastf_t  VV1,
fastf_t  VV2,
fastf_t  D0,
fastf_t  D1,
fastf_t  D2,
fastf_t  D0D1,
fastf_t  D0D2,
fastf_t isect0,
fastf_t isect1,
point_t  isectpoint0,
point_t  isectpoint1 
)

Definition at line 452 of file tri_tri.c.

References calc_isect2(), NEAR_ZERO, and SMALL_FASTF.

Referenced by bn_tri_tri_isect_with_line().

Here is the call graph for this function: