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)
218 double p2[3],
double q2[3],
double r2[3],
219 double normal_1[3],
double[3]){
221 double P1[2],Q1[2],R1[2];
222 double P2[2],Q2[2],R2[2];
224 double n_x, n_y, n_z;
226 n_x = ((normal_1[0]<0)?-normal_1[0]:normal_1[0]);
227 n_y = ((normal_1[1]<0)?-normal_1[1]:normal_1[1]);
228 n_z = ((normal_1[2]<0)?-normal_1[2]:normal_1[2]);
234 if (( n_x > n_z ) && ( n_x >= n_y )) {
236 P1[0] = q1[2]; P1[1] = q1[1];
237 Q1[0] = p1[2]; Q1[1] = p1[1];
238 R1[0] = r1[2]; R1[1] = r1[1];
240 P2[0] = q2[2]; P2[1] = q2[1];
241 Q2[0] = p2[2]; Q2[1] = p2[1];
242 R2[0] = r2[2]; R2[1] = r2[1];
244 }
else if (( n_y > n_z ) && ( n_y >= n_x )) {
246 P1[0] = q1[0]; P1[1] = q1[2];
247 Q1[0] = p1[0]; Q1[1] = p1[2];
248 R1[0] = r1[0]; R1[1] = r1[2];
250 P2[0] = q2[0]; P2[1] = q2[2];
251 Q2[0] = p2[0]; Q2[1] = p2[2];
252 R2[0] = r2[0]; R2[1] = r2[2];
256 P1[0] = p1[0]; P1[1] = p1[1];
257 Q1[0] = q1[0]; Q1[1] = q1[1];
258 R1[0] = r1[0]; R1[1] = r1[1];
260 P2[0] = p2[0]; P2[1] = p2[1];
261 Q2[0] = q2[0]; Q2[1] = q2[1];
262 R2[0] = r2[0]; R2[1] = r2[1];
282 #define CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) { \
287 if (DOT(v,N) > 0.0f) {\
290 if (DOT(v,N) <= 0.0f) { \
293 if (DOT(v,N) > 0.0f) { \
296 alpha = DOT(v1,N2) / DOT(v2,N2); \
297 SCALAR(v1,alpha,v2) \
301 alpha = DOT(v1,N1) / DOT(v2,N1); \
302 SCALAR(v1,alpha,v2) \
308 alpha = DOT(v1,N1) / DOT(v2,N1); \
309 SCALAR(v1,alpha,v2) \
313 alpha = DOT(v1,N1) / DOT(v2,N1); \
314 SCALAR(v1,alpha,v2) \
324 if (DOT(v,N) < 0.0f) { \
329 if (DOT(v,N) >= 0.0f) { \
332 alpha = DOT(v1,N2) / DOT(v2,N2); \
333 SCALAR(v1,alpha,v2) \
337 alpha = DOT(v1,N2) / DOT(v2,N2); \
338 SCALAR(v1,alpha,v2) \
344 alpha = DOT(v1,N1) / DOT(v2,N1); \
345 SCALAR(v1,alpha,v2) \
349 alpha = DOT(v1,N2) / DOT(v2,N2); \
350 SCALAR(v1,alpha,v2) \
357 #define TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) { \
359 if (dq2 > 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,r2,p2,q2) \
360 else if (dr2 > 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2)\
361 else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) }\
362 else if (dp2 < 0.0f) { \
363 if (dq2 < 0.0f) CONSTRUCT_INTERSECTION(p1,q1,r1,r2,p2,q2)\
364 else if (dr2 < 0.0f) CONSTRUCT_INTERSECTION(p1,q1,r1,q2,r2,p2)\
365 else CONSTRUCT_INTERSECTION(p1,r1,q1,p2,q2,r2)\
368 if (dr2 >= 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2)\
369 else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2)\
371 else if (dq2 > 0.0f) { \
372 if (dr2 > 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,p2,q2,r2)\
373 else CONSTRUCT_INTERSECTION(p1,q1,r1,q2,r2,p2)\
376 if (dr2 > 0.0f) CONSTRUCT_INTERSECTION(p1,q1,r1,r2,p2,q2)\
377 else if (dr2 < 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,r2,p2,q2)\
380 return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);\
391 double p2[3],
double q2[3],
double r2[3],
393 double source[3],
double target[3])
396 double dp1, dq1, dr1, dp2, dq2, dr2;
397 double v1[3], v2[3], v[3];
398 double N1[3], N2[3], N[3];
414 if (((dp1 * dq1) > 0.0f) && ((dp1 * dr1) > 0.0f))
return 0;
429 if (((dp2 * dq2) > 0.0f) && ((dp2 * dr2) > 0.0f))
return 0;
436 }
else if (dp1 < 0.0f) {
445 else if (dq1 > 0.0f) {
475 #define ORIENT_2D(a, b, c) ((a[0]-c[0])*(b[1]-c[1])-(a[1]-c[1])*(b[0]-c[0]))
478 #define INTERSECTION_TEST_VERTEX(P1, Q1, R1, P2, Q2, R2) {\
479 if (ORIENT_2D(R2,P2,Q1) >= 0.0f)\
480 if (ORIENT_2D(R2,Q2,Q1) <= 0.0f)\
481 if (ORIENT_2D(P1,P2,Q1) > 0.0f) {\
482 if (ORIENT_2D(P1,Q2,Q1) <= 0.0f) return 1; \
483 else return 0;} else {\
484 if (ORIENT_2D(P1,P2,R1) >= 0.0f)\
485 if (ORIENT_2D(Q1,R1,P2) >= 0.0f) return 1; \
489 if (ORIENT_2D(P1,Q2,Q1) <= 0.0f)\
490 if (ORIENT_2D(R2,Q2,R1) <= 0.0f)\
491 if (ORIENT_2D(Q1,R1,Q2) >= 0.0f) return 1; \
496 if (ORIENT_2D(R2,P2,R1) >= 0.0f) \
497 if (ORIENT_2D(Q1,R1,R2) >= 0.0f)\
498 if (ORIENT_2D(P1,P2,R1) >= 0.0f) return 1;\
501 if (ORIENT_2D(Q1,R1,Q2) >= 0.0f) {\
502 if (ORIENT_2D(R2,R1,Q2) >= 0.0f) return 1; \
510 #define INTERSECTION_TEST_EDGE(P1, Q1, R1, P2, Q2, R2) { \
511 if (ORIENT_2D(R2,P2,Q1) >= 0.0f) {\
512 if (ORIENT_2D(P1,P2,Q1) >= 0.0f) { \
513 if (ORIENT_2D(P1,Q1,R2) >= 0.0f) return 1; \
514 else return 0;} else { \
515 if (ORIENT_2D(Q1,R1,P2) >= 0.0f){ \
516 if (ORIENT_2D(R1,P1,P2) >= 0.0f) return 1; else return 0;} \
519 if (ORIENT_2D(R2,P2,R1) >= 0.0f) {\
520 if (ORIENT_2D(P1,P2,R1) >= 0.0f) {\
521 if (ORIENT_2D(P1,R1,R2) >= 0.0f) return 1; \
523 if (ORIENT_2D(Q1,R1,R2) >= 0.0f) return 1; else return 0;}}\
530 double p2[2],
double q2[2],
double r2[2]) {
533 if (
ORIENT_2D(r2,p2,p1) >= 0.0f )
return 1;
547 double p2[2],
double q2[2],
double r2[2]) {
563 double v1[3], v2[3], N[3];
567 return sqrt(
DOT(N,N)) / 2;
#define TRI_TRI_INTER_3D(p1, q1, r1, p2, q2, r2, dp2, dq2, dr2)
#define INTERSECTION_TEST_EDGE(P1, Q1, R1, P2, Q2, R2)
#define ORIENT_2D(a, b, c)
double triangle_area(double p[3], double q[3], double r[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])
#define TRI_TRI_3D(p1, q1, r1, p2, q2, r2, dp2, dq2, dr2)
#define SUB(dest, v1, v2)
#define CROSS(dest, v1, v2)
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])
#define INTERSECTION_TEST_VERTEX(P1, Q1, R1, P2, Q2, R2)
OPENMEEG_EXPORT 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_overlap_test_2d(double p1[2], double q1[2], double r1[2], double p2[2], double q2[2], double r2[2])
bool ccw_tri_tri_intersection_2d(double p1[2], double q1[2], double r1[2], double p2[2], double q2[2], double r2[2])