OpenMEEG
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 
51 namespace 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])