1 // Copyright 2009-2021 Intel Corporation
2 // SPDX-License-Identifier: Apache-2.0
3 
4 #include "primitive.h"
5 
6 namespace embree
7 {
8   namespace isa
9   {
10     struct TriangleTriangleIntersector
11     {
TTriangleTriangleIntersector12       __forceinline static float T(float pa0, float pa1, float da0, float da1) {
13         return pa0 + (pa1-pa0)*da0/(da0-da1);
14       }
15 
point_line_sideTriangleTriangleIntersector16       __forceinline static bool point_line_side(const Vec2f& p, const Vec2f& a0, const Vec2f& a1) {
17         return det(p-a0,a0-a1) >= 0.0f;
18       }
19 
point_inside_triangleTriangleTriangleIntersector20       __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,a,b);
23         const bool pbc = point_line_side(p,b,c);
24         const bool pca = point_line_side(p,c,a);
25         return pab == pbc && pab == pca;
26       }
27 
intersect_line_lineTriangleTriangleIntersector28       __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(b0,a0,a1) != point_line_side(b1,a0,a1);
31         const bool different_sides1 = point_line_side(a0,b0,b1) != point_line_side(a1,b0,b1);
32         return different_sides0 && different_sides1;
33       }
34 
intersect_triangle_triangleTriangleTriangleIntersector35       __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,b1,b2);
41         if (a01_b12) return true;
42         const bool a01_b20 = intersect_line_line(a0,a1,b2,b0);
43         if (a01_b20) return true;
44         const bool a12_b01 = intersect_line_line(a1,a2,b0,b1);
45         if (a12_b01) return true;
46         const bool a12_b12 = intersect_line_line(a1,a2,b1,b2);
47         if (a12_b12) return true;
48         const bool a12_b20 = intersect_line_line(a1,a2,b2,b0);
49         if (a12_b20) return true;
50         const bool a20_b01 = intersect_line_line(a2,a0,b0,b1);
51         if (a20_b01) return true;
52         const bool a20_b12 = intersect_line_line(a2,a0,b1,b2);
53         if (a20_b12) return true;
54         const bool a20_b20 = intersect_line_line(a2,a0,b2,b0);
55         if (a20_b20) return true;
56 
57         bool a_in_b = point_inside_triangle(a0,b0,b1,b2) && point_inside_triangle(a1,b0,b1,b2) && point_inside_triangle(a2,b0,b1,b2);
58         if (a_in_b) return true;
59 
60         bool b_in_a = point_inside_triangle(b0,a0,a1,a2) && point_inside_triangle(b1,a0,a1,a2) && point_inside_triangle(b2,a0,a1,a2);
61         if (b_in_a) return true;
62 
63         return false;
64       }
65 
intersect_triangle_triangleTriangleTriangleIntersector66       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(a1-a0,a2-a0);
73         const float  Ca = dot(Na,a0);
74         const Vec3fa Nb = cross(b1-b0,b2-b0);
75         const float  Cb = dot(Nb,b0);
76 
77         /* project triangle A onto plane B */
78         const float da0 = dot(Nb,a0)-Cb;
79         const float da1 = dot(Nb,a1)-Cb;
80         const float da2 = dot(Nb,a2)-Cb;
81         if (max(da0,da1,da2) < -eps) return false;
82         if (min(da0,da1,da2) > +eps) return false;
83         //CSTAT(bvh_collide_prim_intersections4++);
84 
85         /* project triangle B onto plane A */
86         const float db0 = dot(Na,b0)-Ca;
87         const float db1 = dot(Na,b1)-Ca;
88         const float db2 = dot(Na,b2)-Ca;
89         if (max(db0,db1,db2) < -eps) return false;
90         if (min(db0,db1,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(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,A1,A2,B0,B1,B2);
106         }
107 
108         const Vec3fa D = cross(Na,Nb);
109         const float pa0 = dot(D,a0);
110         const float pa1 = dot(D,a1);
111         const float pa2 = dot(D,a2);
112         const float pb0 = dot(D,b0);
113         const float pb1 = dot(D,b1);
114         const float pb2 = dot(D,b2);
115 
116         BBox1f ba = empty;
117         if (min(da0,da1) <= 0.0f && max(da0,da1) >= 0.0f && abs(da0-da1) > 0.0f) ba.extend(T(pa0,pa1,da0,da1));
118         if (min(da1,da2) <= 0.0f && max(da1,da2) >= 0.0f && abs(da1-da2) > 0.0f) ba.extend(T(pa1,pa2,da1,da2));
119         if (min(da2,da0) <= 0.0f && max(da2,da0) >= 0.0f && abs(da2-da0) > 0.0f) ba.extend(T(pa2,pa0,da2,da0));
120 
121         BBox1f bb = empty;
122         if (min(db0,db1) <= 0.0f && max(db0,db1) >= 0.0f && abs(db0-db1) > 0.0f) bb.extend(T(pb0,pb1,db0,db1));
123         if (min(db1,db2) <= 0.0f && max(db1,db2) >= 0.0f && abs(db1-db2) > 0.0f) bb.extend(T(pb1,pb2,db1,db2));
124         if (min(db2,db0) <= 0.0f && max(db2,db0) >= 0.0f && abs(db2-db0) > 0.0f) bb.extend(T(pb2,pb0,db2,db0));
125 
126         return conjoint(ba,bb);
127       }
128     };
129   }
130 }
131 
132 
133