1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "primitive.h"
5
6namespace embree
7{
8 namespace isa
9 {
10 struct TriangleTriangleIntersector
11 {
12 __forceinline static float T(float pa0, float pa1, float da0, float da1) {
13 return pa0 + (pa1-pa0)*da0/(da0-da1);
14 }
15
16 __forceinline static bool point_line_side(const Vec2f& p, const Vec2f& a0, const Vec2f& a1) {
17 return det(a: p-a0,b: a0-a1) >= 0.0f;
18 }
19
20 __forceinline static bool point_inside_triangle(const Vec2f& p, const Vec2f& a, const Vec2f& b, const Vec2f& c)
21 {
22 const bool pab = point_line_side(p,a0: a,a1: b);
23 const bool pbc = point_line_side(p,a0: b,a1: c);
24 const bool pca = point_line_side(p,a0: c,a1: a);
25 return pab == pbc && pab == pca;
26 }
27
28 __forceinline static bool intersect_line_line(const Vec2f& a0, const Vec2f& a1, const Vec2f& b0, const Vec2f& b1)
29 {
30 const bool different_sides0 = point_line_side(p: b0,a0,a1) != point_line_side(p: b1,a0,a1);
31 const bool different_sides1 = point_line_side(p: a0,a0: b0,a1: b1) != point_line_side(p: a1,a0: b0,a1: b1);
32 return different_sides0 && different_sides1;
33 }
34
35 __forceinline static bool intersect_triangle_triangle (const Vec2f& a0, const Vec2f& a1, const Vec2f& a2,
36 const Vec2f& b0, const Vec2f& b1, const Vec2f& b2)
37 {
38 const bool a01_b01 = intersect_line_line(a0,a1,b0,b1);
39 if (a01_b01) return true;
40 const bool a01_b12 = intersect_line_line(a0,a1,b0: b1,b1: b2);
41 if (a01_b12) return true;
42 const bool a01_b20 = intersect_line_line(a0,a1,b0: b2,b1: b0);
43 if (a01_b20) return true;
44 const bool a12_b01 = intersect_line_line(a0: a1,a1: a2,b0,b1);
45 if (a12_b01) return true;
46 const bool a12_b12 = intersect_line_line(a0: a1,a1: a2,b0: b1,b1: b2);
47 if (a12_b12) return true;
48 const bool a12_b20 = intersect_line_line(a0: a1,a1: a2,b0: b2,b1: b0);
49 if (a12_b20) return true;
50 const bool a20_b01 = intersect_line_line(a0: a2,a1: a0,b0,b1);
51 if (a20_b01) return true;
52 const bool a20_b12 = intersect_line_line(a0: a2,a1: a0,b0: b1,b1: b2);
53 if (a20_b12) return true;
54 const bool a20_b20 = intersect_line_line(a0: a2,a1: a0,b0: b2,b1: b0);
55 if (a20_b20) return true;
56
57 bool a_in_b = point_inside_triangle(p: a0,a: b0,b: b1,c: b2) && point_inside_triangle(p: a1,a: b0,b: b1,c: b2) && point_inside_triangle(p: a2,a: b0,b: b1,c: b2);
58 if (a_in_b) return true;
59
60 bool b_in_a = point_inside_triangle(p: b0,a: a0,b: a1,c: a2) && point_inside_triangle(p: b1,a: a0,b: a1,c: a2) && point_inside_triangle(p: b2,a: a0,b: a1,c: a2);
61 if (b_in_a) return true;
62
63 return false;
64 }
65
66 static bool intersect_triangle_triangle (const Vec3fa& a0, const Vec3fa& a1, const Vec3fa& a2,
67 const Vec3fa& b0, const Vec3fa& b1, const Vec3fa& b2)
68 {
69 const float eps = 1E-5f;
70
71 /* calculate triangle planes */
72 const Vec3fa Na = cross(a: a1-a0,b: a2-a0);
73 const float Ca = dot(a: Na,b: a0);
74 const Vec3fa Nb = cross(a: b1-b0,b: b2-b0);
75 const float Cb = dot(a: Nb,b: b0);
76
77 /* project triangle A onto plane B */
78 const float da0 = dot(a: Nb,b: a0)-Cb;
79 const float da1 = dot(a: Nb,b: a1)-Cb;
80 const float da2 = dot(a: Nb,b: a2)-Cb;
81 if (max(a: da0,b: da1,c: da2) < -eps) return false;
82 if (min(a: da0,b: da1,c: da2) > +eps) return false;
83 //CSTAT(bvh_collide_prim_intersections4++);
84
85 /* project triangle B onto plane A */
86 const float db0 = dot(a: Na,b: b0)-Ca;
87 const float db1 = dot(a: Na,b: b1)-Ca;
88 const float db2 = dot(a: Na,b: b2)-Ca;
89 if (max(a: db0,b: db1,c: db2) < -eps) return false;
90 if (min(a: db0,b: db1,c: db2) > +eps) return false;
91 //CSTAT(bvh_collide_prim_intersections5++);
92
93 if (unlikely((std::fabs(da0) < eps && std::fabs(da1) < eps && std::fabs(da2) < eps) ||
94 (std::fabs(db0) < eps && std::fabs(db1) < eps && std::fabs(db2) < eps)))
95 {
96 const size_t dz = maxDim(a: Na);
97 const size_t dx = (dz+1)%3;
98 const size_t dy = (dx+1)%3;
99 const Vec2f A0(a0[dx],a0[dy]);
100 const Vec2f A1(a1[dx],a1[dy]);
101 const Vec2f A2(a2[dx],a2[dy]);
102 const Vec2f B0(b0[dx],b0[dy]);
103 const Vec2f B1(b1[dx],b1[dy]);
104 const Vec2f B2(b2[dx],b2[dy]);
105 return intersect_triangle_triangle(a0: A0,a1: A1,a2: A2,b0: B0,b1: B1,b2: B2);
106 }
107
108 const Vec3fa D = cross(a: Na,b: Nb);
109 const float pa0 = dot(a: D,b: a0);
110 const float pa1 = dot(a: D,b: a1);
111 const float pa2 = dot(a: D,b: a2);
112 const float pb0 = dot(a: D,b: b0);
113 const float pb1 = dot(a: D,b: b1);
114 const float pb2 = dot(a: D,b: b2);
115
116 BBox1f ba = empty;
117 if (min(a: da0,b: da1) <= 0.0f && max(a: da0,b: da1) >= 0.0f && abs(x: da0-da1) > 0.0f) ba.extend(other: T(pa0,pa1,da0,da1));
118 if (min(a: da1,b: da2) <= 0.0f && max(a: da1,b: da2) >= 0.0f && abs(x: da1-da2) > 0.0f) ba.extend(other: T(pa0: pa1,pa1: pa2,da0: da1,da1: da2));
119 if (min(a: da2,b: da0) <= 0.0f && max(a: da2,b: da0) >= 0.0f && abs(x: da2-da0) > 0.0f) ba.extend(other: T(pa0: pa2,pa1: pa0,da0: da2,da1: da0));
120
121 BBox1f bb = empty;
122 if (min(a: db0,b: db1) <= 0.0f && max(a: db0,b: db1) >= 0.0f && abs(x: db0-db1) > 0.0f) bb.extend(other: T(pa0: pb0,pa1: pb1,da0: db0,da1: db1));
123 if (min(a: db1,b: db2) <= 0.0f && max(a: db1,b: db2) >= 0.0f && abs(x: db1-db2) > 0.0f) bb.extend(other: T(pa0: pb1,pa1: pb2,da0: db1,da1: db2));
124 if (min(a: db2,b: db0) <= 0.0f && max(a: db2,b: db0) >= 0.0f && abs(x: db2-db0) > 0.0f) bb.extend(other: T(pa0: pb2,pa1: pb0,da0: db2,da1: db0));
125
126 return conjoint(a: ba,b: bb);
127 }
128 };
129 }
130}
131
132
133

source code of qtquick3d/src/3rdparty/embree/kernels/geometry/triangle_triangle_intersector.h