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])
155 double dp1, dq1, dr1, dp2, dq2, dr2;
158 const double eps=1e-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;
192 if (dq1 > eps)
TRI_TRI_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
193 else if (dr1 > eps)
TRI_TRI_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
194 else TRI_TRI_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
195 }
else if (dp1 < -eps) {
196 if (dq1 < -eps)
TRI_TRI_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
197 else if (dr1 < -eps)
TRI_TRI_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
198 else TRI_TRI_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
201 if (dr1 >= eps)
TRI_TRI_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
202 else TRI_TRI_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
204 else if (dq1 > eps) {
205 if (dr1 > eps)
TRI_TRI_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
206 else TRI_TRI_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
209 if (dr1 > eps)
TRI_TRI_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
210 else if (dr1 < -eps)
TRI_TRI_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
217 double p2[3],
double q2[3],
double r2[3],
218 double normal_1[3],
double[3]) {
220 double P1[2],Q1[2],R1[2];
221 double P2[2],Q2[2],R2[2];
223 double n_x, n_y, n_z;
225 n_x = ((normal_1[0]<0)?-normal_1[0]:normal_1[0]);
226 n_y = ((normal_1[1]<0)?-normal_1[1]:normal_1[1]);
227 n_z = ((normal_1[2]<0)?-normal_1[2]:normal_1[2]);
233 if (( n_x > n_z ) && ( n_x >= n_y )) {
235 P1[0] = q1[2]; P1[1] = q1[1];
236 Q1[0] = p1[2]; Q1[1] = p1[1];
237 R1[0] = r1[2]; R1[1] = r1[1];
239 P2[0] = q2[2]; P2[1] = q2[1];
240 Q2[0] = p2[2]; Q2[1] = p2[1];
241 R2[0] = r2[2]; R2[1] = r2[1];
243 }
else if (( n_y > n_z ) && ( n_y >= n_x )) {
245 P1[0] = q1[0]; P1[1] = q1[2];
246 Q1[0] = p1[0]; Q1[1] = p1[2];
247 R1[0] = r1[0]; R1[1] = r1[2];
249 P2[0] = q2[0]; P2[1] = q2[2];
250 Q2[0] = p2[0]; Q2[1] = p2[2];
251 R2[0] = r2[0]; R2[1] = r2[2];
255 P1[0] = p1[0]; P1[1] = p1[1];
256 Q1[0] = q1[0]; Q1[1] = q1[1];
257 R1[0] = r1[0]; R1[1] = r1[1];
259 P2[0] = p2[0]; P2[1] = p2[1];
260 Q2[0] = q2[0]; Q2[1] = q2[1];
261 R2[0] = r2[0]; R2[1] = r2[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],
390 double source[3],
double target[3])
393 double dp1, dq1, dr1, dp2, dq2, dr2;
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]) {
524 if (
ORIENT_2D(r2,p2,p1) >= 0.0f )
return 1;
537 double p2[2],
double q2[2],
double r2[2]) {
552 double v1[3], v2[3], N[3];
556 return sqrt(
DOT(N,N)) / 2;
#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])