56 double p2[3],
double q2[3],
double r2[3]);
60 double p2[3],
double q2[3],
double r2[3],
61 double N1[3],
double N2[3]);
65 double p2[2],
double q2[2],
double r2[2]);
69 double p2[3],
double q2[3],
double r2[3],
70 int * coplanar,
double source[3],
double target[3]);
80 #define CROSS(dest,v1,v2) \
81 dest[0]=v1[1]*v2[2]-v1[2]*v2[1]; \
82 dest[1]=v1[2]*v2[0]-v1[0]*v2[2]; \
83 dest[2]=v1[0]*v2[1]-v1[1]*v2[0];
87 #define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
91 #define SUB(dest,v1,v2) dest[0]=v1[0]-v2[0]; \
92 dest[1]=v1[1]-v2[1]; \
97 #define SCALAR(dest,alpha,v) dest[0] = alpha * v[0]; \
98 dest[1] = alpha * v[1]; \
99 dest[2] = alpha * v[2];
103 #define CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2) {\
108 if (DOT(v1,N1) > 0.0f) return 0;\
113 if (DOT(v1,N1) > 0.0f) return 0;\
119 #define TRI_TRI_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) { \
121 if (dq2 > 0.0f) CHECK_MIN_MAX(p1,r1,q1,r2,p2,q2) \
122 else if (dr2 > 0.0f) CHECK_MIN_MAX(p1,r1,q1,q2,r2,p2)\
123 else CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2) }\
124 else if (dp2 < 0.0f) { \
125 if (dq2 < 0.0f) CHECK_MIN_MAX(p1,q1,r1,r2,p2,q2)\
126 else if (dr2 < 0.0f) CHECK_MIN_MAX(p1,q1,r1,q2,r2,p2)\
127 else CHECK_MIN_MAX(p1,r1,q1,p2,q2,r2)\
130 if (dr2 >= 0.0f) CHECK_MIN_MAX(p1,r1,q1,q2,r2,p2)\
131 else CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2)\
133 else if (dq2 > 0.0f) { \
134 if (dr2 > 0.0f) CHECK_MIN_MAX(p1,r1,q1,p2,q2,r2)\
135 else CHECK_MIN_MAX(p1,q1,r1,q2,r2,p2)\
138 if (dr2 > 0.0f) CHECK_MIN_MAX(p1,q1,r1,r2,p2,q2)\
139 else if (dr2 < 0.0f) CHECK_MIN_MAX(p1,r1,q1,r2,p2,q2)\
140 else return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);\
153 double p2[3],
double q2[3],
double r2[3])
158 const double eps=1
e-16;
173 if (((
dp1 *
dq1) > 0.0f) && ((
dp1 *
dr1) > 0.0f))
return 0;
188 if (((
dp2 *
dq2) > 0.0f) && ((
dp2 *
dr2) > 0.0f))
return 0;
217 double p2[3],
double q2[3],
double r2[3],
236 Q1[0] = p1[2];
Q1[1] = p1[1];
240 Q2[0] = p2[2];
Q2[1] = p2[1];
246 Q1[0] = p1[0];
Q1[1] = p1[2];
250 Q2[0] = p2[0];
Q2[1] = p2[2];
255 P1[0] = p1[0];
P1[1] = p1[1];
259 P2[0] = p2[0];
P2[1] = p2[1];
279 #define CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) { \
284 if (DOT(v,N) > 0.0f) {\
287 if (DOT(v,N) <= 0.0f) { \
290 if (DOT(v,N) > 0.0f) { \
293 alpha = DOT(v1,N2) / DOT(v2,N2); \
294 SCALAR(v1,alpha,v2) \
298 alpha = DOT(v1,N1) / DOT(v2,N1); \
299 SCALAR(v1,alpha,v2) \
305 alpha = DOT(v1,N1) / DOT(v2,N1); \
306 SCALAR(v1,alpha,v2) \
310 alpha = DOT(v1,N1) / DOT(v2,N1); \
311 SCALAR(v1,alpha,v2) \
321 if (DOT(v,N) < 0.0f) { \
326 if (DOT(v,N) >= 0.0f) { \
329 alpha = DOT(v1,N2) / DOT(v2,N2); \
330 SCALAR(v1,alpha,v2) \
334 alpha = DOT(v1,N2) / DOT(v2,N2); \
335 SCALAR(v1,alpha,v2) \
341 alpha = DOT(v1,N1) / DOT(v2,N1); \
342 SCALAR(v1,alpha,v2) \
346 alpha = DOT(v1,N2) / DOT(v2,N2); \
347 SCALAR(v1,alpha,v2) \
354 #define TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) { \
356 if (dq2 > 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,r2,p2,q2) \
357 else if (dr2 > 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2)\
358 else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) }\
359 else if (dp2 < 0.0f) { \
360 if (dq2 < 0.0f) CONSTRUCT_INTERSECTION(p1,q1,r1,r2,p2,q2)\
361 else if (dr2 < 0.0f) CONSTRUCT_INTERSECTION(p1,q1,r1,q2,r2,p2)\
362 else CONSTRUCT_INTERSECTION(p1,r1,q1,p2,q2,r2)\
365 if (dr2 >= 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2)\
366 else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2)\
368 else if (dq2 > 0.0f) { \
369 if (dr2 > 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,p2,q2,r2)\
370 else CONSTRUCT_INTERSECTION(p1,q1,r1,q2,r2,p2)\
373 if (dr2 > 0.0f) CONSTRUCT_INTERSECTION(p1,q1,r1,r2,p2,q2)\
374 else if (dr2 < 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,r2,p2,q2)\
377 return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);\
388 double p2[3],
double q2[3],
double r2[3],
394 double v1[3],
v2[3],
v[3];
395 double N1[3],
N2[3], N[3];
411 if (((
dp1 *
dq1) > 0.0f) && ((
dp1 *
dr1) > 0.0f))
return 0;
426 if (((
dp2 *
dq2) > 0.0f) && ((
dp2 *
dr2) > 0.0f))
return 0;
433 }
else if (
dp1 < 0.0f) {
442 else if (
dq1 > 0.0f) {
468 #define ORIENT_2D(a, b, c) ((a[0]-c[0])*(b[1]-c[1])-(a[1]-c[1])*(b[0]-c[0]))
471 #define INTERSECTION_TEST_VERTEX(P1, Q1, R1, P2, Q2, R2) {\
472 if (ORIENT_2D(R2,P2,Q1) >= 0.0f)\
473 if (ORIENT_2D(R2,Q2,Q1) <= 0.0f)\
474 if (ORIENT_2D(P1,P2,Q1) > 0.0f) {\
475 if (ORIENT_2D(P1,Q2,Q1) <= 0.0f) return 1; \
476 else return 0;} else {\
477 if (ORIENT_2D(P1,P2,R1) >= 0.0f)\
478 if (ORIENT_2D(Q1,R1,P2) >= 0.0f) return 1; \
482 if (ORIENT_2D(P1,Q2,Q1) <= 0.0f)\
483 if (ORIENT_2D(R2,Q2,R1) <= 0.0f)\
484 if (ORIENT_2D(Q1,R1,Q2) >= 0.0f) return 1; \
489 if (ORIENT_2D(R2,P2,R1) >= 0.0f) \
490 if (ORIENT_2D(Q1,R1,R2) >= 0.0f)\
491 if (ORIENT_2D(P1,P2,R1) >= 0.0f) return 1;\
494 if (ORIENT_2D(Q1,R1,Q2) >= 0.0f) {\
495 if (ORIENT_2D(R2,R1,Q2) >= 0.0f) return 1; \
501 #define INTERSECTION_TEST_EDGE(P1, Q1, R1, P2, Q2, R2) { \
502 if (ORIENT_2D(R2,P2,Q1) >= 0.0f) {\
503 if (ORIENT_2D(P1,P2,Q1) >= 0.0f) { \
504 if (ORIENT_2D(P1,Q1,R2) >= 0.0f) return 1; \
505 else return 0;} else { \
506 if (ORIENT_2D(Q1,R1,P2) >= 0.0f){ \
507 if (ORIENT_2D(R1,P1,P2) >= 0.0f) return 1; else return 0;} \
510 if (ORIENT_2D(R2,P2,R1) >= 0.0f) {\
511 if (ORIENT_2D(P1,P2,R1) >= 0.0f) {\
512 if (ORIENT_2D(P1,R1,R2) >= 0.0f) return 1; \
514 if (ORIENT_2D(Q1,R1,R2) >= 0.0f) return 1; else return 0;}}\
521 double p2[2],
double q2[2],
double r2[2]) {
537 double p2[2],
double q2[2],
double r2[2]) {
552 double v1[3],
v2[3], N[3];
#define INTERSECTION_TEST_VERTEX(P1, Q1, R1, P2, Q2, R2)
#define SUB(dest, v1, v2)
#define CROSS(dest, v1, v2)
#define TRI_TRI_3D(p1, q1, r1, p2, q2, r2, dp2, dq2, dr2)
#define INTERSECTION_TEST_EDGE(P1, Q1, R1, P2, Q2, R2)
#define TRI_TRI_INTER_3D(p1, q1, r1, p2, q2, r2, dp2, dq2, dr2)
#define ORIENT_2D(a, b, c)
bool ccw_tri_tri_intersection_2d(double p1[2], double q1[2], double r1[2], double p2[2], double q2[2], double r2[2])
double triangle_area(double p[3], double q[3], double r[3])
bool tri_tri_overlap_test_3d(double p1[3], double q1[3], double r1[3], double p2[3], double q2[3], double r2[3])
bool tri_tri_intersection_test_3d(double p1[3], double q1[3], double r1[3], double p2[3], double q2[3], double r2[3], int *coplanar, double source[3], double target[3])
bool coplanar_tri_tri3d(double p1[3], double q1[3], double r1[3], double p2[3], double q2[3], double r2[3], double N1[3], double N2[3])
bool tri_tri_overlap_test_2d(double p1[2], double q1[2], double r1[2], double p2[2], double q2[2], double r2[2])