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