triangle_triangle_intersection.h
1 /*
2 * Triangle-Triangle Overlap Test Routines
3 * July, 2002
4 * Updated December 2003
5 * Modified by Andreas Schuh in September 2016
6 *
7 * This file contains C implementation of algorithms for
8 * performing two and three-dimensional triangle-triangle intersection test
9 * The algorithms and underlying theory are described in
10 *
11 * "Fast and Robust Triangle-Triangle Overlap Test
12 * Using Orientation Predicates" P. Guigue - O. Devillers
13 *
14 * Journal of Graphics Tools, 8(1), 2003
15 *
16 * Several geometric predicates are defined. Their parameters are all
17 * points. Each point is an array of two or three real precision
18 * floating point numbers. The geometric predicates implemented in
19 * this file are:
20 *
21 * int tri_tri_overlap_test_3d(p1,q1,r1,p2,q2,r2)
22 * int tri_tri_overlap_test_2d(p1,q1,r1,p2,q2,r2)
23 *
24 * int tri_tri_intersection_test_3d(p1,q1,r1,p2,q2,r2,
25 * coplanar,source,target)
26 *
27 * is a version that computes the segment of intersection when
28 * the triangles overlap (and are not coplanar)
29 *
30 * each function returns 1 if the triangles (including their
31 * boundary) intersect, otherwise 0
32 *
33 *
34 * Other information are available from the Web page
35 * http:<i>//www.acm.org/jgt/papers/GuigueDevillers03/
36 *
37 */
38 
39 // Andreas: Copied this source file on 6/6/2016 from
40 // https://raw.githubusercontent.com/benardp/contours/755cf3c5086d58d07928934384dd185604ea2c2c/freestyle/view_map/triangle_triangle_intersection.c
41 // and modified to use eps and zero constants for chosen real data type.
42 // Clamp dot products / signed distance to triangle plane to zero when
43 // absolute value is less than abs to better detect coplanarity.
44 typedef double real;
45 
46 static const real zero = real(0);
47 static const real eps = static_cast<real>(1e-12);
48 
49 
50 #define ZERO_TEST(x) (abs(x) <= eps)
51 
52 
53 /* function prototype */
54 inline int tri_tri_overlap_test_3d(real p1[3], real q1[3], real r1[3],
55  real p2[3], real q2[3], real r2[3]);
56 
57 inline int coplanar_tri_tri3d(real p1[3], real q1[3], real r1[3],
58  real p2[3], real q2[3], real r2[3],
59  real N1[3], real N2[3]);
60 
61 inline int tri_tri_overlap_test_2d(real p1[2], real q1[2], real r1[2],
62  real p2[2], real q2[2], real r2[2]);
63 
64 inline int tri_tri_intersection_test_3d(real p1[3], real q1[3], real r1[3],
65  real p2[3], real q2[3], real r2[3],
66  int * coplanar,
67  real source[3], real target[3]);
68 
69 /* coplanar returns whether the triangles are coplanar
70 * source and target are the endpoints of the segment of
71 * intersection if it exists)
72 */
73 
74 #define CROSS(dest,v1,v2) dest[0] = v1[1]*v2[2] - v1[2]*v2[1]; \
75  dest[1] = v1[2]*v2[0] - v1[0]*v2[2]; \
76  dest[2] = v1[0]*v2[1] - v1[1]*v2[0];
77 
78 #define DOT(v1,v2) (v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2])
79 
80 
81 
82 #define SUB(dest,v1,v2) dest[0] = v1[0] - v2[0]; \
83  dest[1] = v1[1] - v2[1]; \
84  dest[2] = v1[2] - v2[2];
85 
86 
87 #define SCALAR(dest,alpha,v) dest[0] = alpha * v[0]; \
88  dest[1] = alpha * v[1]; \
89  dest[2] = alpha * v[2];
90 
91 
92 
93 // Andreas: Changed conditions from DOT(v1,N1) > zero to DOT(v1,N1) >= -eps
94 #define CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2) \
95  { \
96  SUB(v1,p2,q1) \
97  SUB(v2,p1,q1) \
98  CROSS(N1,v1,v2) \
99  SUB(v1,q2,q1) \
100  if (DOT(v1,N1) >= -eps) return 0; \
101  SUB(v1,p2,p1) \
102  SUB(v2,r1,p1) \
103  CROSS(N1,v1,v2) \
104  SUB(v1,r2,p1) \
105  if (DOT(v1,N1) >= -eps) return 0; \
106  return 1; \
107  }
108 
109 
110 /* Permutation in a canonical form of T2's vertices */
111 #define TRI_TRI_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) \
112  { \
113  if (dp2 > zero) { \
114  if (dq2 > zero) CHECK_MIN_MAX(p1,r1,q1,r2,p2,q2) \
115  else if (dr2 > zero) CHECK_MIN_MAX(p1,r1,q1,q2,r2,p2) \
116  else CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2) \
117  } else if (dp2 < zero) { \
118  if (dq2 < zero) CHECK_MIN_MAX(p1,q1,r1,r2,p2,q2) \
119  else if (dr2 < zero) CHECK_MIN_MAX(p1,q1,r1,q2,r2,p2) \
120  else CHECK_MIN_MAX(p1,r1,q1,p2,q2,r2) \
121  } else { \
122  if (dq2 < zero) { \
123  if (dr2 >= zero) CHECK_MIN_MAX(p1,r1,q1,q2,r2,p2) \
124  else CHECK_MIN_MAX(p1,q1,r1,p2,q2,r2) \
125  } else if (dq2 > zero) { \
126  if (dr2 > zero) CHECK_MIN_MAX(p1,r1,q1,p2,q2,r2) \
127  else CHECK_MIN_MAX(p1,q1,r1,q2,r2,p2) \
128  } else { \
129  if (dr2 > zero) CHECK_MIN_MAX(p1,q1,r1,r2,p2,q2) \
130  else if (dr2 < zero) CHECK_MIN_MAX(p1,r1,q1,r2,p2,q2) \
131  else return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2); \
132  } \
133  } \
134  }
135 
136 
137 /*
138 *
139 * Three-dimensional Triangle-Triangle Overlap Test
140 *
141 */
142 
143 
144 int tri_tri_overlap_test_3d(real p1[3], real q1[3], real r1[3],
145  real p2[3], real q2[3], real r2[3])
146 {
147  real dp1, dq1, dr1, dp2, dq2, dr2;
148  real v1[3], v2[3];
149  real N1[3], N2[3];
150 
151  // Compute distance signs of p1, q1 and r1 to the plane of triangle(p2,q2,r2)
152  SUB(v1,p2,r2)
153  SUB(v2,q2,r2)
154  CROSS(N2,v1,v2)
155 
156  SUB(v1,p1,r2)
157  dp1 = DOT(v1,N2);
158  SUB(v1,q1,r2)
159  dq1 = DOT(v1,N2);
160  SUB(v1,r1,r2)
161  dr1 = DOT(v1,N2);
162 
163  if (((dp1 * dq1) > zero) && ((dp1 * dr1) > zero)) return 0;
164 
165  // Compute distance signs of p2, q2 and r2 to the plane of triangle(p1,q1,r1)
166  SUB(v1,q1,p1)
167  SUB(v2,r1,p1)
168  CROSS(N1,v1,v2)
169 
170  SUB(v1,p2,r1)
171  dp2 = DOT(v1,N1);
172  SUB(v1,q2,r1)
173  dq2 = DOT(v1,N1);
174  SUB(v1,r2,r1)
175  dr2 = DOT(v1,N1);
176 
177  if (((dp2 * dq2) > zero) && ((dp2 * dr2) > zero)) return 0;
178 
179  // Permutation in a canonical form of T1's vertices
180  if (ZERO_TEST(dp1)) dp1 = zero;
181  if (ZERO_TEST(dq1)) dq1 = zero;
182  if (ZERO_TEST(dr1)) dr1 = zero;
183 
184  if (ZERO_TEST(dp2)) dp2 = zero;
185  if (ZERO_TEST(dq2)) dq2 = zero;
186  if (ZERO_TEST(dr2)) dr2 = zero;
187 
188  if (dp1 > zero) {
189  if (dq1 > zero) TRI_TRI_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
190  else if (dr1 > zero) TRI_TRI_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
191  else TRI_TRI_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
192  } else if (dp1 < zero) {
193  if (dq1 < zero) TRI_TRI_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
194  else if (dr1 < zero) TRI_TRI_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
195  else TRI_TRI_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
196  } else {
197  if (dq1 < zero) {
198  if (dr1 >= zero) TRI_TRI_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
199  else TRI_TRI_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
200  } else if (dq1 > zero) {
201  if (dr1 > zero) TRI_TRI_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
202  else TRI_TRI_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
203  } else {
204  if (dr1 > zero) TRI_TRI_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
205  else if (dr1 < zero) TRI_TRI_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
206  else return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);
207  }
208  }
209 };
210 
211 
212 int coplanar_tri_tri3d(real p1[3], real q1[3], real r1[3],
213  real p2[3], real q2[3], real r2[3],
214  real normal_1[3], real normal_2[3])
215 {
216  real P1[2],Q1[2],R1[2];
217  real P2[2],Q2[2],R2[2];
218 
219  real n_x, n_y, n_z;
220 
221  n_x = ((normal_1[0] < zero) ? -normal_1[0] : normal_1[0]);
222  n_y = ((normal_1[1] < zero) ? -normal_1[1] : normal_1[1]);
223  n_z = ((normal_1[2] < zero) ? -normal_1[2] : normal_1[2]);
224 
225  /* Projection of the triangles in 3D onto 2D such that the area of
226  the projection is maximized. */
227 
228  // Project onto plane YZ
229  if (( n_x > n_z ) && ( n_x >= n_y )) {
230 
231  P1[0] = q1[2]; P1[1] = q1[1];
232  Q1[0] = p1[2]; Q1[1] = p1[1];
233  R1[0] = r1[2]; R1[1] = r1[1];
234 
235  P2[0] = q2[2]; P2[1] = q2[1];
236  Q2[0] = p2[2]; Q2[1] = p2[1];
237  R2[0] = r2[2]; R2[1] = r2[1];
238 
239  // Project onto plane XZ
240  } else if (( n_y > n_z ) && ( n_y >= n_x )) {
241 
242  P1[0] = q1[0]; P1[1] = q1[2];
243  Q1[0] = p1[0]; Q1[1] = p1[2];
244  R1[0] = r1[0]; R1[1] = r1[2];
245 
246  P2[0] = q2[0]; P2[1] = q2[2];
247  Q2[0] = p2[0]; Q2[1] = p2[2];
248  R2[0] = r2[0]; R2[1] = r2[2];
249 
250  // Project onto plane XY
251  } else {
252 
253  P1[0] = p1[0]; P1[1] = p1[1];
254  Q1[0] = q1[0]; Q1[1] = q1[1];
255  R1[0] = r1[0]; R1[1] = r1[1];
256 
257  P2[0] = p2[0]; P2[1] = p2[1];
258  Q2[0] = q2[0]; Q2[1] = q2[1];
259  R2[0] = r2[0]; R2[1] = r2[1];
260 
261  }
262 
263  return tri_tri_overlap_test_2d(P1,Q1,R1,P2,Q2,R2);
264 };
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 
280 #define CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) \
281  { \
282  SUB(v1,q1,p1) \
283  SUB(v2,r2,p1) \
284  CROSS(N,v1,v2) \
285  SUB(v,p2,p1) \
286  if (DOT(v,N) > zero) {\
287  SUB(v1,r1,p1) \
288  CROSS(N,v1,v2) \
289  if (DOT(v,N) <= zero) { \
290  SUB(v2,q2,p1) \
291  CROSS(N,v1,v2) \
292  if (DOT(v,N) > zero) { \
293  SUB(v1,p1,p2) \
294  SUB(v2,p1,r1) \
295  alpha = DOT(v1,N2) / DOT(v2,N2); \
296  SCALAR(v1,alpha,v2) \
297  SUB(source,p1,v1) \
298  SUB(v1,p2,p1) \
299  SUB(v2,p2,r2) \
300  alpha = DOT(v1,N1) / DOT(v2,N1); \
301  SCALAR(v1,alpha,v2) \
302  SUB(target,p2,v1) \
303  return 1; \
304  } else { \
305  SUB(v1,p2,p1) \
306  SUB(v2,p2,q2) \
307  alpha = DOT(v1,N1) / DOT(v2,N1); \
308  SCALAR(v1,alpha,v2) \
309  SUB(source,p2,v1) \
310  SUB(v1,p2,p1) \
311  SUB(v2,p2,r2) \
312  alpha = DOT(v1,N1) / DOT(v2,N1); \
313  SCALAR(v1,alpha,v2) \
314  SUB(target,p2,v1) \
315  return 1; \
316  } \
317  } else { \
318  return 0; \
319  } \
320  } else { \
321  SUB(v2,q2,p1) \
322  CROSS(N,v1,v2) \
323  if (DOT(v,N) < zero) { \
324  return 0; \
325  } else { \
326  SUB(v1,r1,p1) \
327  CROSS(N,v1,v2) \
328  if (DOT(v,N) >= zero) { \
329  SUB(v1,p1,p2) \
330  SUB(v2,p1,r1) \
331  alpha = DOT(v1,N2) / DOT(v2,N2); \
332  SCALAR(v1,alpha,v2) \
333  SUB(source,p1,v1) \
334  SUB(v1,p1,p2) \
335  SUB(v2,p1,q1) \
336  alpha = DOT(v1,N2) / DOT(v2,N2); \
337  SCALAR(v1,alpha,v2) \
338  SUB(target,p1,v1) \
339  return 1; \
340  } else { \
341  SUB(v1,p2,p1) \
342  SUB(v2,p2,q2) \
343  alpha = DOT(v1,N1) / DOT(v2,N1); \
344  SCALAR(v1,alpha,v2) \
345  SUB(source,p2,v1) \
346  SUB(v1,p1,p2) \
347  SUB(v2,p1,q1) \
348  alpha = DOT(v1,N2) / DOT(v2,N2); \
349  SCALAR(v1,alpha,v2) \
350  SUB(target,p1,v1) \
351  return 1; \
352  } \
353  } \
354  } \
355  }
356 
357 
358 #define TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2) \
359  { \
360  if (dp2 > zero) { \
361  if (dq2 > zero) CONSTRUCT_INTERSECTION(p1,r1,q1,r2,p2,q2) \
362  else if (dr2 > zero) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2) \
363  else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) \
364  } else if (dp2 < zero) { \
365  if (dq2 < zero) CONSTRUCT_INTERSECTION(p1,q1,r1,r2,p2,q2) \
366  else if (dr2 < zero) CONSTRUCT_INTERSECTION(p1,q1,r1,q2,r2,p2) \
367  else CONSTRUCT_INTERSECTION(p1,r1,q1,p2,q2,r2) \
368  } else { \
369  if (dq2 < zero) { \
370  if (dr2 >= zero) CONSTRUCT_INTERSECTION(p1,r1,q1,q2,r2,p2) \
371  else CONSTRUCT_INTERSECTION(p1,q1,r1,p2,q2,r2) \
372  } else if (dq2 > zero) { \
373  if (dr2 > zero) CONSTRUCT_INTERSECTION(p1,r1,q1,p2,q2,r2) \
374  else CONSTRUCT_INTERSECTION(p1,q1,r1,q2,r2,p2) \
375  } else { \
376  if (dr2 > zero) CONSTRUCT_INTERSECTION(p1,q1,r1,r2,p2,q2) \
377  else if (dr2 < zero) 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 
386 
387 /*
388  The following version computes the segment of intersection of the
389  two triangles if it exists.
390  coplanar returns whether the triangles are coplanar
391  source and target are the endpoints of the line segment of intersection
392 */
393 
394 int tri_tri_intersection_test_3d(real p1[3], real q1[3], real r1[3],
395  real p2[3], real q2[3], real r2[3],
396  int * coplanar,
397  real source[3], real target[3])
398 {
399  real dp1, dq1, dr1, dp2, dq2, dr2;
400  real v1[3], v2[3], v[3];
401  real N1[3], N2[3], N[3];
402  real alpha;
403 
404  // Compute distance signs of p1, q1 and r1
405  // to the plane of triangle(p2,q2,r2)
406  SUB(v1,p2,r2)
407  SUB(v2,q2,r2)
408  CROSS(N2,v1,v2)
409 
410  SUB(v1,p1,r2)
411  dp1 = DOT(v1,N2);
412  SUB(v1,q1,r2)
413  dq1 = DOT(v1,N2);
414  SUB(v1,r1,r2)
415  dr1 = DOT(v1,N2);
416 
417  if (((dp1 * dq1) > zero) && ((dp1 * dr1) > zero)) return 0;
418 
419  // Compute distance signs of p2, q2 and r2
420  // to the plane of triangle(p1,q1,r1)
421  SUB(v1,q1,p1)
422  SUB(v2,r1,p1)
423  CROSS(N1,v1,v2)
424 
425  SUB(v1,p2,r1)
426  dp2 = DOT(v1,N1);
427  SUB(v1,q2,r1)
428  dq2 = DOT(v1,N1);
429  SUB(v1,r2,r1)
430  dr2 = DOT(v1,N1);
431 
432  if (((dp2 * dq2) > zero) && ((dp2 * dr2) > zero)) return 0;
433 
434  // Permutation in a canonical form of T1's vertices
435  if (ZERO_TEST(dp1)) dp1 = zero;
436  if (ZERO_TEST(dq1)) dq1 = zero;
437  if (ZERO_TEST(dr1)) dr1 = zero;
438 
439  if (ZERO_TEST(dp2)) dp2 = zero;
440  if (ZERO_TEST(dq2)) dq2 = zero;
441  if (ZERO_TEST(dr2)) dr2 = zero;
442 
443  if (dp1 > zero) {
444  if (dq1 > zero) TRI_TRI_INTER_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
445  else if (dr1 > zero) TRI_TRI_INTER_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
446  else TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
447  } else if (dp1 < zero) {
448  if (dq1 < zero) TRI_TRI_INTER_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
449  else if (dr1 < zero) TRI_TRI_INTER_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
450  else TRI_TRI_INTER_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
451  } else {
452  if (dq1 < zero) {
453  if (dr1 >= zero) TRI_TRI_INTER_3D(q1,r1,p1,p2,r2,q2,dp2,dr2,dq2)
454  else TRI_TRI_INTER_3D(p1,q1,r1,p2,q2,r2,dp2,dq2,dr2)
455  }
456  else if (dq1 > zero) {
457  if (dr1 > zero) TRI_TRI_INTER_3D(p1,q1,r1,p2,r2,q2,dp2,dr2,dq2)
458  else TRI_TRI_INTER_3D(q1,r1,p1,p2,q2,r2,dp2,dq2,dr2)
459  }
460  else {
461  if (dr1 > zero) TRI_TRI_INTER_3D(r1,p1,q1,p2,q2,r2,dp2,dq2,dr2)
462  else if (dr1 < zero) TRI_TRI_INTER_3D(r1,p1,q1,p2,r2,q2,dp2,dr2,dq2)
463  else {
464  *coplanar = 1;
465  return coplanar_tri_tri3d(p1,q1,r1,p2,q2,r2,N1,N2);
466  }
467  }
468  }
469 };
470 
471 
472 
473 /*
474 *
475 * Two dimensional Triangle-Triangle Overlap Test
476 *
477 */
478 
479 // -----------------------------------------------------------------------------
480 #define ORIENT_2D(a, b, c) ((a[0]-c[0])*(b[1]-c[1])-(a[1]-c[1])*(b[0]-c[0]))
481 
482 // -----------------------------------------------------------------------------
483 #define INTERSECTION_TEST_VERTEX(P1, Q1, R1, P2, Q2, R2) \
484  { \
485  if (ORIENT_2D(R2,P2,Q1) >= zero) { \
486  if (ORIENT_2D(R2,Q2,Q1) <= zero) { \
487  if (ORIENT_2D(P1,P2,Q1) > zero) { \
488  if (ORIENT_2D(P1,Q2,Q1) <= zero) return 1; \
489  } else { \
490  if (ORIENT_2D(P1,P2,R1) >= zero) { \
491  if (ORIENT_2D(Q1,R1,P2) >= zero) return 1; \
492  } \
493  } \
494  } else { \
495  if (ORIENT_2D(P1,Q2,Q1) <= zero) { \
496  if (ORIENT_2D(R2,Q2,R1) <= zero) { \
497  if (ORIENT_2D(Q1,R1,Q2) >= zero) return 1; \
498  } \
499  } \
500  } \
501  } else { \
502  if (ORIENT_2D(R2,P2,R1) >= zero) { \
503  if (ORIENT_2D(Q1,R1,R2) >= zero) { \
504  if (ORIENT_2D(P1,P2,R1) >= zero) return 1;\
505  } else { \
506  if (ORIENT_2D(Q1,R1,Q2) >= zero) { \
507  if (ORIENT_2D(R2,R1,Q2) >= zero) return 1; \
508  } \
509  } \
510  } \
511  } \
512  return 0; \
513  }
514 
515 // -----------------------------------------------------------------------------
516 #define INTERSECTION_TEST_EDGE(P1, Q1, R1, P2, Q2, R2) \
517  { \
518  if (ORIENT_2D(R2,P2,Q1) >= zero) { \
519  if (ORIENT_2D(P1,P2,Q1) >= zero) { \
520  if (ORIENT_2D(P1,Q1,R2) >= zero) return 1; \
521  } else { \
522  if (ORIENT_2D(Q1,R1,P2) >= zero) { \
523  if (ORIENT_2D(R1,P1,P2) >= zero) return 1; \
524  } \
525  } \
526  } else { \
527  if (ORIENT_2D(R2,P2,R1) >= zero) { \
528  if (ORIENT_2D(P1,P2,R1) >= zero) { \
529  if (ORIENT_2D(P1,R1,R2) >= zero) return 1; \
530  if (ORIENT_2D(Q1,R1,R2) >= zero) return 1; \
531  } \
532  } \
533  } \
534  return 0; \
535  }
536 
537 // -----------------------------------------------------------------------------
538 int ccw_tri_tri_intersection_2d(real p1[2], real q1[2], real r1[2],
539  real p2[2], real q2[2], real r2[2])
540 {
541  if (ORIENT_2D(p2,q2,p1) >= zero) {
542  if (ORIENT_2D(q2,r2,p1) >= zero) {
543  if (ORIENT_2D(r2,p2,p1) >= zero) return 1;
544  INTERSECTION_TEST_EDGE(p1,q1,r1,p2,q2,r2)
545  } else {
546  if (ORIENT_2D(r2,p2,p1) >= zero) INTERSECTION_TEST_EDGE(p1,q1,r1,r2,p2,q2)
547  else INTERSECTION_TEST_VERTEX(p1,q1,r1,p2,q2,r2)
548  }
549  } else {
550  if (ORIENT_2D(q2,r2,p1) >= zero) {
551  if (ORIENT_2D(r2,p2,p1) >= zero) INTERSECTION_TEST_EDGE(p1,q1,r1,q2,r2,p2)
552  else INTERSECTION_TEST_VERTEX(p1,q1,r1,q2,r2,p2)
553  } else {
554  INTERSECTION_TEST_VERTEX(p1,q1,r1,r2,p2,q2)
555  }
556  }
557 };
558 
559 // -----------------------------------------------------------------------------
560 int tri_tri_overlap_test_2d(real p1[2], real q1[2], real r1[2],
561  real p2[2], real q2[2], real r2[2])
562 {
563  if (ORIENT_2D(p1,q1,r1) < zero) {
564  if (ORIENT_2D(p2,q2,r2) < zero) {
565  return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,r2,q2);
566  } else {
567  return ccw_tri_tri_intersection_2d(p1,r1,q1,p2,q2,r2);
568  }
569  } else {
570  if (ORIENT_2D(p2,q2,r2) < zero) {
571  return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,r2,q2);
572  } else {
573  return ccw_tri_tri_intersection_2d(p1,q1,r1,p2,q2,r2);
574  }
575  }
576 };
© 2013-2018 Imperial College London, Andreas Schuh.