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 
217  bool coplanar_tri_tri3d(double p1[3], double q1[3], double r1[3],
218  double p2[3], double q2[3], double r2[3],
219  double normal_1[3], double[3]){
220 
221  double P1[2],Q1[2],R1[2];
222  double P2[2],Q2[2],R2[2];
223 
224  double n_x, n_y, n_z;
225 
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]);
229 
230 
231  // Projection of the triangles in 3D onto 2D such that the area of
232  // the projection is maximized.
233 
234  if (( n_x > n_z ) && ( n_x >= n_y )) {
235  // Project onto plane YZ
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];
239 
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];
243 
244  } else if (( n_y > n_z ) && ( n_y >= n_x )) {
245  // Project onto plane XZ
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];
249 
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];
253 
254  } else {
255  // Project onto plane XY
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];
259 
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];
263  }
264 
265  return tri_tri_overlap_test_2d(P1,Q1,R1,P2,Q2,R2);
266 
267  };
268 
269 
270 
271  /******************************************************************/
272  /* */
273  /* Three-dimensional Triangle-Triangle Intersection */
274  /* */
275  /******************************************************************/
276 
277 
278  // This macro is called when the triangles surely intersect
279  // It constructs the segment of intersection of the two triangles
280  // if they are not coplanar.
281 
282  #define CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) { \
283  SUB(v1,q1,p1) \
284  SUB(v2,r2,p1) \
285  CROSS(N,v1,v2) \
286  SUB(v,p2,p1) \
287  if (DOT(v,N) > 0.0f) {\
288  SUB(v1,r1,p1) \
289  CROSS(N,v1,v2) \
290  if (DOT(v,N) <= 0.0f) { \
291  SUB(v2,q2,p1) \
292  CROSS(N,v1,v2) \
293  if (DOT(v,N) > 0.0f) { \
294  SUB(v1,p1,p2) \
295  SUB(v2,p1,r1) \
296  alpha = DOT(v1,N2) / DOT(v2,N2); \
297  SCALAR(v1,alpha,v2) \
298  SUB(source,p1,v1) \
299  SUB(v1,p2,p1) \
300  SUB(v2,p2,r2) \
301  alpha = DOT(v1,N1) / DOT(v2,N1); \
302  SCALAR(v1,alpha,v2) \
303  SUB(target,p2,v1) \
304  return 1; \
305  } else { \
306  SUB(v1,p2,p1) \
307  SUB(v2,p2,q2) \
308  alpha = DOT(v1,N1) / DOT(v2,N1); \
309  SCALAR(v1,alpha,v2) \
310  SUB(source,p2,v1) \
311  SUB(v1,p2,p1) \
312  SUB(v2,p2,r2) \
313  alpha = DOT(v1,N1) / DOT(v2,N1); \
314  SCALAR(v1,alpha,v2) \
315  SUB(target,p2,v1) \
316  return 1; \
317  } \
318  } else { \
319  return 0; \
320  } \
321  } else { \
322  SUB(v2,q2,p1) \
323  CROSS(N,v1,v2) \
324  if (DOT(v,N) < 0.0f) { \
325  return 0; \
326  } else { \
327  SUB(v1,r1,p1) \
328  CROSS(N,v1,v2) \
329  if (DOT(v,N) >= 0.0f) { \
330  SUB(v1,p1,p2) \
331  SUB(v2,p1,r1) \
332  alpha = DOT(v1,N2) / DOT(v2,N2); \
333  SCALAR(v1,alpha,v2) \
334  SUB(source,p1,v1) \
335  SUB(v1,p1,p2) \
336  SUB(v2,p1,q1) \
337  alpha = DOT(v1,N2) / DOT(v2,N2); \
338  SCALAR(v1,alpha,v2) \
339  SUB(target,p1,v1) \
340  return 1; \
341  } else { \
342  SUB(v1,p2,p1) \
343  SUB(v2,p2,q2) \
344  alpha = DOT(v1,N1) / DOT(v2,N1); \
345  SCALAR(v1,alpha,v2) \
346  SUB(source,p2,v1) \
347  SUB(v1,p1,p2) \
348  SUB(v2,p1,q1) \
349  alpha = DOT(v1,N2) / DOT(v2,N2); \
350  SCALAR(v1,alpha,v2) \
351  SUB(target,p1,v1) \
352  return 1; \
353  }}}}
354 
355 
356 
357  #define TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) { \
358  if (dp2 > 0.0f) { \
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)\
366  } else { \
367  if (dq2 < 0.0f) { \
368  if (dr2 >= 0.0f) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2)\
369  else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2)\
370  } \
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)\
374  } \
375  else { \
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)\
378  else { \
379  *coplanar = 1; \
380  return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);\
381  } \
382  }} }
383 
384 
385  // The following version computes the segment of intersection of the
386  // two triangles if it exists.
387  // coplanar returns whether the triangles are coplanar
388  // source and target are the endpoints of the line segment of intersection
389 
390  bool tri_tri_intersection_test_3d(double p1[3], double q1[3], double r1[3],
391  double p2[3], double q2[3], double r2[3],
392  int * coplanar,
393  double source[3], double target[3])
394 
395  {
396  double dp1, dq1, dr1, dp2, dq2, dr2;
397  double v1[3], v2[3], v[3];
398  double N1[3], N2[3], N[3];
399  double alpha;
400 
401  // Compute distance signs of p1, q1 and r1 to the plane of triangle(p2,q2,r2)
402 
403  SUB(v1,p2,r2)
404  SUB(v2,q2,r2)
405  CROSS(N2,v1,v2)
406 
407  SUB(v1,p1,r2)
408  dp1 = DOT(v1,N2);
409  SUB(v1,q1,r2)
410  dq1 = DOT(v1,N2);
411  SUB(v1,r1,r2)
412  dr1 = DOT(v1,N2);
413 
414  if (((dp1 * dq1) > 0.0f) && ((dp1 * dr1) > 0.0f)) return 0;
415 
416  // Compute distance signs of p2, q2 and r2 to the plane of triangle(p1,q1,r1)
417 
418  SUB(v1,q1,p1)
419  SUB(v2,r1,p1)
420  CROSS(N1,v1,v2)
421 
422  SUB(v1,p2,r1)
423  dp2 = DOT(v1,N1);
424  SUB(v1,q2,r1)
425  dq2 = DOT(v1,N1);
426  SUB(v1,r2,r1)
427  dr2 = DOT(v1,N1);
428 
429  if (((dp2 * dq2) > 0.0f) && ((dp2 * dr2) > 0.0f)) return 0;
430 
431  // Permutation in a canonical form of T1's vertices
432  if (dp1 > 0.0f) {
433  if (dq1 > 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
434  else if (dr1 > 0.0f) TRI_TRI_INTER_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
435  else TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
436  } else if (dp1 < 0.0f) {
437  if (dq1 < 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
438  else if (dr1 < 0.0f) TRI_TRI_INTER_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
439  else TRI_TRI_INTER_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
440  } else {
441  if (dq1 < 0.0f) {
442  if (dr1 >= 0.0f) TRI_TRI_INTER_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
443  else TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
444  }
445  else if (dq1 > 0.0f) {
446  if (dr1 > 0.0f) TRI_TRI_INTER_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
447  else TRI_TRI_INTER_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
448  }
449  else {
450 
451  if (dr1 > 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
452  else if (dr1 < 0.0f) TRI_TRI_INTER_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
453  else {
454  // triangles are co-planar
455  *coplanar = 1;
456  return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);
457  }
458  }
459  }
460  };
461 
462 
463 
464 
465 
466  /******************************************************************/
467  /* */
468  /* Two dimensional Triangle-Triangle Overlap Test */
469  /* */
470  /******************************************************************/
471 
472 
473  /* some 2D macros */
474 
475  #define ORIENT_2D(a, b, c) ((a[0]-c[0])*(b[1]-c[1])-(a[1]-c[1])*(b[0]-c[0]))
476 
477 
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; \
486  else return 0;\
487  else return 0;}\
488  else \
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; \
492  else return 0;\
493  else return 0;\
494  else return 0;\
495  else\
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;\
499  else return 0;\
500  else \
501  if (ORIENT_2D(Q1,R1,Q2) >= 0.0f) {\
502  if (ORIENT_2D(R2,R1,Q2) >= 0.0f) return 1; \
503  else return 0; }\
504  else return 0; \
505  else return 0; \
506  };
507 
508 
509 
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;} \
517  else return 0; } \
518  } else {\
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; \
522  else {\
523  if (ORIENT_2D(Q1,R1,R2) >= 0.0f) return 1; else return 0;}}\
524  else return 0; }\
525  else return 0; }}
526 
527 
528 
529  bool ccw_tri_tri_intersection_2d(double p1[2], double q1[2], double r1[2],
530  double p2[2], double q2[2], double r2[2]) {
531  if ( ORIENT_2D(p2,q2,p1) >= 0.0f ) {
532  if ( ORIENT_2D(q2,r2,p1) >= 0.0f ) {
533  if ( ORIENT_2D(r2,p2,p1) >= 0.0f ) return 1;
534  else INTERSECTION_TEST_EDGE(p1,q1,r1,p2,q2,r2)
535  } else {
536  if ( ORIENT_2D(r2,p2,p1) >= 0.0f ) INTERSECTION_TEST_EDGE(p1,q1,r1,r2,p2,q2)
537  else INTERSECTION_TEST_VERTEX(p1,q1,r1,p2,q2,r2)}}
538  else {
539  if ( ORIENT_2D(q2,r2,p1) >= 0.0f ) {
540  if ( ORIENT_2D(r2,p2,p1) >= 0.0f ) INTERSECTION_TEST_EDGE(p1,q1,r1,q2,r2,p2)
541  else INTERSECTION_TEST_VERTEX(p1,q1,r1,q2,r2,p2)}
542  else INTERSECTION_TEST_VERTEX(p1,q1,r1,r2,p2,q2)}
543  };
544 
545 
546  bool tri_tri_overlap_test_2d(double p1[2], double q1[2], double r1[2],
547  double p2[2], double q2[2], double r2[2]) {
548  if ( ORIENT_2D(p1,q1,r1) < 0.0f )
549  if ( ORIENT_2D(p2,q2,r2) < 0.0f )
550  return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,r2,q2);
551  else
552  return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,q2,r2);
553  else
554  if ( ORIENT_2D(p2,q2,r2) < 0.0f )
555  return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,r2,q2);
556  else
557  return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,q2,r2);
558 
559  };
560 
561 
562  double triangle_area(double p[3], double q[3], double r[3]) {
563  double v1[3], v2[3], N[3];
564  SUB(v1,p,r)
565  SUB(v2,q,r)
566  CROSS(N,v1,v2)
567  return sqrt(DOT(N,N)) / 2;
568  }
569 }
OpenMEEG::coplanar_tri_tri3d
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])
Definition: Triangle_triangle_intersection.h:217
ORIENT_2D
#define ORIENT_2D(a, b, c)
Definition: Triangle_triangle_intersection.h:475
TRI_TRI_3D
#define TRI_TRI_3D(p1, q1, r1, p2, q2, r2, dp2, dq2, dr2)
Definition: Triangle_triangle_intersection.h:119
INTERSECTION_TEST_EDGE
#define INTERSECTION_TEST_EDGE(P1, Q1, R1, P2, Q2, R2)
Definition: Triangle_triangle_intersection.h:510
OpenMEEG::tri_tri_overlap_test_2d
bool tri_tri_overlap_test_2d(double p1[2], double q1[2], double r1[2], double p2[2], double q2[2], double r2[2])
Definition: Triangle_triangle_intersection.h:546
OpenMEEG::tri_tri_overlap_test_3d
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])
Definition: Triangle_triangle_intersection.h:152
OpenMEEG
Definition: analytics.h:45
CROSS
#define CROSS(dest, v1, v2)
Definition: Triangle_triangle_intersection.h:80
INTERSECTION_TEST_VERTEX
#define INTERSECTION_TEST_VERTEX(P1, Q1, R1, P2, Q2, R2)
Definition: Triangle_triangle_intersection.h:478
SUB
#define SUB(dest, v1, v2)
Definition: Triangle_triangle_intersection.h:91
OpenMEEG::ccw_tri_tri_intersection_2d
bool ccw_tri_tri_intersection_2d(double p1[2], double q1[2], double r1[2], double p2[2], double q2[2], double r2[2])
Definition: Triangle_triangle_intersection.h:529
TRI_TRI_INTER_3D
#define TRI_TRI_INTER_3D(p1, q1, r1, p2, q2, r2, dp2, dq2, dr2)
Definition: Triangle_triangle_intersection.h:357
OpenMEEG::tri_tri_intersection_test_3d
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])
Definition: Triangle_triangle_intersection.h:390
OpenMEEG::triangle_area
double triangle_area(double p[3], double q[3], double r[3])
Definition: Triangle_triangle_intersection.h:562
DOT
#define DOT(v1, v2)
Definition: Triangle_triangle_intersection.h:87