OpenMEEG
Loading...
Searching...
No Matches
Triangle_triangle_intersection.h
Go to the documentation of this file.
1#pragma once
2/*****************************************************************************/
3/* */
4/* Fast and Robust Triangle-Triangle Overlap Test */
5/* July, 2002 */
6/* */
7/* Philippe Guigue */
8/* INRIA - Sophia Antipolis */
9/* France */
10/* philippe.guigue@inria.fr */
11/* */
12/* This file contains C implementation of algorithms for */
13/* performing two and three-dimensional triangle-triangle intersection test */
14/* The algorithms and underlying theory are described in */
15/* "Faster Triangle-Triangle Intersection Tests" */
16/* */
17/* */
18/* This paper listed above, and other information are available */
19/* from the Web page */
20/* http://www.inria.fr/rrrt/rr-4488.html */
21/* */
22/*****************************************************************************/
23/*****************************************************************************/
24/* */
25/* Using this code: */
26/* */
27/* First, read the paper (from the Web page above). */
28/* */
29/* */
30/* Several geometric predicates are defined. Their parameters are all */
31/* points. Each point is an array of two or three double precision */
32/* floating point numbers. The geometric predicates, described in */
33/* the papers, are */
34/* */
35/* */
36/* int tri_tri_overlap_test_3d(p1,q1,r1,p2,q2,r2) */
37/* int tri_tri_overlap_test_2d(p1,q1,r1,p2,q2,r2) */
38/* */
39/* int tri_tri_intersection_test_3d(p1,q1,r1,p2,q2,r2,coplanar, */
40/* source,target) */
41/* a version that computes the segment of intersection when */
42/* the triangles overlap */
43/* */
44/* each function returns 1 if the triangles (including their */
45/* boundary) intersect, otherwise 0 */
46/* */
47/*****************************************************************************/
48
49#include <cmath>
50
51namespace OpenMEEG {
52
53 /* function prototype */
54
55 OPENMEEG_EXPORT bool tri_tri_overlap_test_3d(double p1[3], double q1[3], double r1[3],
56 double p2[3], double q2[3], double r2[3]);
57
58
59 bool coplanar_tri_tri3d(double p1[3], double q1[3], double r1[3],
60 double p2[3], double q2[3], double r2[3],
61 double N1[3], double N2[3]);
62
63
64 bool tri_tri_overlap_test_2d(double p1[2], double q1[2], double r1[2],
65 double p2[2], double q2[2], double r2[2]);
66
67
68 bool tri_tri_intersection_test_3d(double p1[3], double q1[3], double r1[3],
69 double p2[3], double q2[3], double r2[3],
70 int * coplanar, double source[3],double target[3]);
71
72 double triangle_area(double p[3], double q[3], double r[3]);
73
74 /* coplanar returns whether the triangles are coplanar */
75 /* source and target are the endpoints of the segment of intersection if it exists) */
76
77
78 /* some 3D macros */
79 #ifndef CROSS
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];
84 #endif
85
86 #ifndef DOT
87 #define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])
88 #endif
89
90 #ifndef SUB
91 #define SUB(dest,v1,v2) dest[0]=v1[0]-v2[0]; \
92 dest[1]=v1[1]-v2[1]; \
93 dest[2]=v1[2]-v2[2];
94 #endif
95
96
97 #define SCALAR(dest,alpha,v) dest[0] = alpha * v[0]; \
98 dest[1] = alpha * v[1]; \
99 dest[2] = alpha * v[2];
100
101
102
103 #define CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2) {\
104 SUB(v1,p2,q1)\
105 SUB(v2,p1,q1)\
106 CROSS(N1,v1,v2)\
107 SUB(v1,q2,q1)\
108 if (DOT(v1,N1) > 0.0f) return 0;\
109 SUB(v1,p2,p1)\
110 SUB(v2,r1,p1)\
111 CROSS(N1,v1,v2)\
112 SUB(v1,r2,p1) \
113 if (DOT(v1,N1) > 0.0f) return 0;\
114 else return 1; }
115
116
117
118 // Permutation in a canonical form of T2's vertices
119 #define TRI_TRI_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) { \
120 if (dp2 > 0.0f) { \
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)\
128 } else { \
129 if (dq2 < 0.0f) { \
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)\
132 } \
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)\
136 } \
137 else { \
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);\
141 }}}
142
143
144
145 /******************************************************************/
146 /* */
147 /* Three-dimensional Triangle-Triangle Overlap Test */
148 /* */
149 /******************************************************************/
150
151
152 bool tri_tri_overlap_test_3d(double p1[3], double q1[3], double r1[3],
153 double p2[3], double q2[3], double r2[3])
154 {
155 double dp1, dq1, dr1, dp2, dq2, dr2;
156 double v1[3], v2[3];
157 double N1[3], N2[3];
158 const double eps=1e-16;
159
160 // Compute distance signs of p1, q1 and r1 to the plane of triangle(p2,q2,r2)
161
162 SUB(v1,p2,r2)
163 SUB(v2,q2,r2)
164 CROSS(N2,v1,v2)
165
166 SUB(v1,p1,r2)
167 dp1 = DOT(v1,N2);
168 SUB(v1,q1,r2)
169 dq1 = DOT(v1,N2);
170 SUB(v1,r1,r2)
171 dr1 = DOT(v1,N2);
172
173 if (((dp1 * dq1) > 0.0f) && ((dp1 * dr1) > 0.0f)) return 0;
174
175 // Compute distance signs of p2, q2 and r2 to the plane of triangle(p1,q1,r1)
176
177 SUB(v1,q1,p1)
178 SUB(v2,r1,p1)
179 CROSS(N1,v1,v2)
180
181 SUB(v1,p2,r1)
182 dp2 = DOT(v1,N1);
183 SUB(v1,q2,r1)
184 dq2 = DOT(v1,N1);
185 SUB(v1,r2,r1)
186 dr2 = DOT(v1,N1);
187
188 if (((dp2 * dq2) > 0.0f) && ((dp2 * dr2) > 0.0f)) return 0;
189
190 // Permutation in a canonical form of T1's vertices
191 if (dp1 > eps) {
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)
199 } else {
200 if (dq1 < -eps) {
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)
203 }
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)
207 }
208 else {
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)
211 else return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);
212 }
213 }
214 }
215
216 bool coplanar_tri_tri3d(double p1[3], double q1[3], double r1[3],
217 double p2[3], double q2[3], double r2[3],
218 double normal_1[3], double[3]) {
219
220 double P1[2],Q1[2],R1[2];
221 double P2[2],Q2[2],R2[2];
222
223 double n_x, n_y, n_z;
224
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]);
228
229
230 // Projection of the triangles in 3D onto 2D such that the area of
231 // the projection is maximized.
232
233 if (( n_x > n_z ) && ( n_x >= n_y )) {
234 // Project onto plane YZ
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];
238
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];
242
243 } else if (( n_y > n_z ) && ( n_y >= n_x )) {
244 // Project onto plane XZ
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];
248
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];
252
253 } else {
254 // Project onto plane XY
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];
258
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];
262 }
263
264 return tri_tri_overlap_test_2d(P1,Q1,R1,P2,Q2,R2);
265
266 }
267
268 /******************************************************************/
269 /* */
270 /* Three-dimensional Triangle-Triangle Intersection */
271 /* */
272 /******************************************************************/
273
274
275 // This macro is called when the triangles surely intersect
276 // It constructs the segment of intersection of the two triangles
277 // if they are not coplanar.
278
279 #define CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) { \
280 SUB(v1,q1,p1) \
281 SUB(v2,r2,p1) \
282 CROSS(N,v1,v2) \
283 SUB(v,p2,p1) \
284 if (DOT(v,N) > 0.0f) {\
285 SUB(v1,r1,p1) \
286 CROSS(N,v1,v2) \
287 if (DOT(v,N) <= 0.0f) { \
288 SUB(v2,q2,p1) \
289 CROSS(N,v1,v2) \
290 if (DOT(v,N) > 0.0f) { \
291 SUB(v1,p1,p2) \
292 SUB(v2,p1,r1) \
293 alpha = DOT(v1,N2) / DOT(v2,N2); \
294 SCALAR(v1,alpha,v2) \
295 SUB(source,p1,v1) \
296 SUB(v1,p2,p1) \
297 SUB(v2,p2,r2) \
298 alpha = DOT(v1,N1) / DOT(v2,N1); \
299 SCALAR(v1,alpha,v2) \
300 SUB(target,p2,v1) \
301 return 1; \
302 } else { \
303 SUB(v1,p2,p1) \
304 SUB(v2,p2,q2) \
305 alpha = DOT(v1,N1) / DOT(v2,N1); \
306 SCALAR(v1,alpha,v2) \
307 SUB(source,p2,v1) \
308 SUB(v1,p2,p1) \
309 SUB(v2,p2,r2) \
310 alpha = DOT(v1,N1) / DOT(v2,N1); \
311 SCALAR(v1,alpha,v2) \
312 SUB(target,p2,v1) \
313 return 1; \
314 } \
315 } else { \
316 return 0; \
317 } \
318 } else { \
319 SUB(v2,q2,p1) \
320 CROSS(N,v1,v2) \
321 if (DOT(v,N) < 0.0f) { \
322 return 0; \
323 } else { \
324 SUB(v1,r1,p1) \
325 CROSS(N,v1,v2) \
326 if (DOT(v,N) >= 0.0f) { \
327 SUB(v1,p1,p2) \
328 SUB(v2,p1,r1) \
329 alpha = DOT(v1,N2) / DOT(v2,N2); \
330 SCALAR(v1,alpha,v2) \
331 SUB(source,p1,v1) \
332 SUB(v1,p1,p2) \
333 SUB(v2,p1,q1) \
334 alpha = DOT(v1,N2) / DOT(v2,N2); \
335 SCALAR(v1,alpha,v2) \
336 SUB(target,p1,v1) \
337 return 1; \
338 } else { \
339 SUB(v1,p2,p1) \
340 SUB(v2,p2,q2) \
341 alpha = DOT(v1,N1) / DOT(v2,N1); \
342 SCALAR(v1,alpha,v2) \
343 SUB(source,p2,v1) \
344 SUB(v1,p1,p2) \
345 SUB(v2,p1,q1) \
346 alpha = DOT(v1,N2) / DOT(v2,N2); \
347 SCALAR(v1,alpha,v2) \
348 SUB(target,p1,v1) \
349 return 1; \
350 }}}}
351
352
353
354 #define TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) { \
355 if (dp2 > 0.0f) { \
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)\
363 } else { \
364 if (dq2 < 0.0f) { \
365 if (dr2 >= 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2)\
366 else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2)\
367 } \
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)\
371 } \
372 else { \
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)\
375 else { \
376 *coplanar = 1; \
377 return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);\
378 } \
379 }} }
380
381
382 // The following version computes the segment of intersection of the
383 // two triangles if it exists.
384 // coplanar returns whether the triangles are coplanar
385 // source and target are the endpoints of the line segment of intersection
386
387 bool tri_tri_intersection_test_3d(double p1[3], double q1[3], double r1[3],
388 double p2[3], double q2[3], double r2[3],
389 int * coplanar,
390 double source[3], double target[3])
391
392 {
393 double dp1, dq1, dr1, dp2, dq2, dr2;
394 double v1[3], v2[3], v[3];
395 double N1[3], N2[3], N[3];
396 double alpha;
397
398 // Compute distance signs of p1, q1 and r1 to the plane of triangle(p2,q2,r2)
399
400 SUB(v1,p2,r2)
401 SUB(v2,q2,r2)
402 CROSS(N2,v1,v2)
403
404 SUB(v1,p1,r2)
405 dp1 = DOT(v1,N2);
406 SUB(v1,q1,r2)
407 dq1 = DOT(v1,N2);
408 SUB(v1,r1,r2)
409 dr1 = DOT(v1,N2);
410
411 if (((dp1 * dq1) > 0.0f) && ((dp1 * dr1) > 0.0f)) return 0;
412
413 // Compute distance signs of p2, q2 and r2 to the plane of triangle(p1,q1,r1)
414
415 SUB(v1,q1,p1)
416 SUB(v2,r1,p1)
417 CROSS(N1,v1,v2)
418
419 SUB(v1,p2,r1)
420 dp2 = DOT(v1,N1);
421 SUB(v1,q2,r1)
422 dq2 = DOT(v1,N1);
423 SUB(v1,r2,r1)
424 dr2 = DOT(v1,N1);
425
426 if (((dp2 * dq2) > 0.0f) && ((dp2 * dr2) > 0.0f)) return 0;
427
428 // Permutation in a canonical form of T1's vertices
429 if (dp1 > 0.0f) {
430 if (dq1 > 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
431 else if (dr1 > 0.0f) TRI_TRI_INTER_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
432 else TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
433 } else if (dp1 < 0.0f) {
434 if (dq1 < 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
435 else if (dr1 < 0.0f) TRI_TRI_INTER_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
436 else TRI_TRI_INTER_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
437 } else {
438 if (dq1 < 0.0f) {
439 if (dr1 >= 0.0f) TRI_TRI_INTER_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
440 else TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
441 }
442 else if (dq1 > 0.0f) {
443 if (dr1 > 0.0f) TRI_TRI_INTER_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
444 else TRI_TRI_INTER_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
445 }
446 else {
447
448 if (dr1 > 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
449 else if (dr1 < 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
450 else {
451 // triangles are co-planar
452 *coplanar = 1;
453 return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);
454 }
455 }
456 }
457 }
458
459 /******************************************************************/
460 /* */
461 /* Two dimensional Triangle-Triangle Overlap Test */
462 /* */
463 /******************************************************************/
464
465
466 /* some 2D macros */
467
468 #define ORIENT_2D(a, b, c) ((a[0]-c[0])*(b[1]-c[1])-(a[1]-c[1])*(b[0]-c[0]))
469
470
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; \
479 else return 0;\
480 else return 0;}\
481 else \
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; \
485 else return 0;\
486 else return 0;\
487 else return 0;\
488 else\
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;\
492 else return 0;\
493 else \
494 if (ORIENT_2D(Q1,R1,Q2) >= 0.0f) {\
495 if (ORIENT_2D(R2,R1,Q2) >= 0.0f) return 1; \
496 else return 0; }\
497 else return 0; \
498 else return 0; \
499 }
500
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;} \
508 else return 0; } \
509 } else {\
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; \
513 else {\
514 if (ORIENT_2D(Q1,R1,R2) >= 0.0f) return 1; else return 0;}}\
515 else return 0; }\
516 else return 0; }}
517
518
519
520 bool ccw_tri_tri_intersection_2d(double p1[2], double q1[2], double r1[2],
521 double p2[2], double q2[2], double r2[2]) {
522 if ( ORIENT_2D(p2,q2,p1) >= 0.0f ) {
523 if ( ORIENT_2D(q2,r2,p1) >= 0.0f ) {
524 if ( ORIENT_2D(r2,p2,p1) >= 0.0f ) return 1;
525 else INTERSECTION_TEST_EDGE(p1,q1,r1,p2,q2,r2)
526 } else {
527 if ( ORIENT_2D(r2,p2,p1) >= 0.0f ) INTERSECTION_TEST_EDGE(p1,q1,r1,r2,p2,q2)
528 else INTERSECTION_TEST_VERTEX(p1,q1,r1,p2,q2,r2)}}
529 else {
530 if ( ORIENT_2D(q2,r2,p1) >= 0.0f ) {
531 if ( ORIENT_2D(r2,p2,p1) >= 0.0f ) INTERSECTION_TEST_EDGE(p1,q1,r1,q2,r2,p2)
532 else INTERSECTION_TEST_VERTEX(p1,q1,r1,q2,r2,p2)}
533 else INTERSECTION_TEST_VERTEX(p1,q1,r1,r2,p2,q2)}
534 }
535
536 bool tri_tri_overlap_test_2d(double p1[2], double q1[2], double r1[2],
537 double p2[2], double q2[2], double r2[2]) {
538 if ( ORIENT_2D(p1,q1,r1) < 0.0f )
539 if ( ORIENT_2D(p2,q2,r2) < 0.0f )
540 return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,r2,q2);
541 else
542 return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,q2,r2);
543 else
544 if ( ORIENT_2D(p2,q2,r2) < 0.0f )
545 return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,r2,q2);
546 else
547 return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,q2,r2);
548
549 }
550
551 double triangle_area(double p[3], double q[3], double r[3]) {
552 double v1[3], v2[3], N[3];
553 SUB(v1,p,r)
554 SUB(v2,q,r)
555 CROSS(N,v1,v2)
556 return sqrt(DOT(N,N)) / 2;
557 }
558}
#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 DOT(v1, v2)
#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])