1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6#include "triangle.h"
7#include "intersector_epilog.h"
8
9/*! This intersector implements a modified version of the Moeller
10 * Trumbore intersector from the paper "Fast, Minimum Storage
11 * Ray-Triangle Intersection". In contrast to the paper we
12 * precalculate some factors and factor the calculations differently
13 * to allow precalculating the cross product e1 x e2. The resulting
14 * algorithm is similar to the fastest one of the paper "Optimizing
15 * Ray-Triangle Intersection via Automated Search". */
16
17namespace embree
18{
19 namespace isa
20 {
21 template<int M, typename UVMapper>
22 struct MoellerTrumboreHitM
23 {
24 __forceinline MoellerTrumboreHitM(const UVMapper& mapUV) : mapUV(mapUV) {}
25
26 __forceinline MoellerTrumboreHitM(const vbool<M>& valid, const vfloat<M>& U, const vfloat<M>& V, const vfloat<M>& T, const vfloat<M>& absDen, const Vec3vf<M>& Ng, const UVMapper& mapUV)
27 : U(U), V(V), T(T), absDen(absDen), mapUV(mapUV), valid(valid), vNg(Ng) {}
28
29 __forceinline void finalize()
30 {
31 const vfloat<M> rcpAbsDen = rcp(absDen);
32 vt = T * rcpAbsDen;
33 vu = U * rcpAbsDen;
34 vv = V * rcpAbsDen;
35 mapUV(vu,vv,vNg);
36 }
37
38 __forceinline Vec2vf<M> uv() const { return Vec2vf<M>(vu,vv); }
39 __forceinline vfloat<M> t () const { return vt; }
40 __forceinline Vec3vf<M> Ng() const { return vNg; }
41
42 __forceinline Vec2f uv (const size_t i) const { return Vec2f(vu[i],vv[i]); }
43 __forceinline float t (const size_t i) const { return vt[i]; }
44 __forceinline Vec3fa Ng(const size_t i) const { return Vec3fa(vNg.x[i],vNg.y[i],vNg.z[i]); }
45
46 public:
47 vfloat<M> U;
48 vfloat<M> V;
49 vfloat<M> T;
50 vfloat<M> absDen;
51 UVMapper mapUV;
52
53 public:
54 vbool<M> valid;
55 vfloat<M> vu;
56 vfloat<M> vv;
57 vfloat<M> vt;
58 Vec3vf<M> vNg;
59 };
60
61 template<int M, bool early_out = true>
62 struct MoellerTrumboreIntersector1
63 {
64 __forceinline MoellerTrumboreIntersector1() {}
65
66 __forceinline MoellerTrumboreIntersector1(const Ray& ray, const void* ptr) {}
67
68 template<typename UVMapper>
69 __forceinline bool intersect(const vbool<M>& valid0,
70 Ray& ray,
71 const Vec3vf<M>& tri_v0,
72 const Vec3vf<M>& tri_e1,
73 const Vec3vf<M>& tri_e2,
74 const Vec3vf<M>& tri_Ng,
75 const UVMapper& mapUV,
76 MoellerTrumboreHitM<M,UVMapper>& hit) const
77 {
78 /* calculate denominator */
79 vbool<M> valid = valid0;
80 const Vec3vf<M> O = Vec3vf<M>((Vec3fa)ray.org);
81 const Vec3vf<M> D = Vec3vf<M>((Vec3fa)ray.dir);
82 const Vec3vf<M> C = Vec3vf<M>(tri_v0) - O;
83 const Vec3vf<M> R = cross(C,D);
84 const vfloat<M> den = dot(Vec3vf<M>(tri_Ng),D);
85
86 const vfloat<M> absDen = abs(den);
87 const vfloat<M> sgnDen = signmsk(den);
88
89 /* perform edge tests */
90 const vfloat<M> U = dot(R,Vec3vf<M>(tri_e2)) ^ sgnDen;
91 const vfloat<M> V = dot(R,Vec3vf<M>(tri_e1)) ^ sgnDen;
92
93 /* perform backface culling */
94#if defined(EMBREE_BACKFACE_CULLING)
95 valid &= (den < vfloat<M>(zero)) & (U >= 0.0f) & (V >= 0.0f) & (U+V<=absDen);
96#else
97 valid &= (den != vfloat<M>(zero)) & (U >= 0.0f) & (V >= 0.0f) & (U+V<=absDen);
98#endif
99 if (likely(early_out && none(valid))) return false;
100
101 /* perform depth test */
102 const vfloat<M> T = dot(Vec3vf<M>(tri_Ng),C) ^ sgnDen;
103 valid &= (absDen*vfloat<M>(ray.tnear()) < T) & (T <= absDen*vfloat<M>(ray.tfar));
104 if (likely(early_out && none(valid))) return false;
105
106 /* update hit information */
107 new (&hit) MoellerTrumboreHitM<M,UVMapper>(valid,U,V,T,absDen,tri_Ng,mapUV);
108
109 return true;
110 }
111
112 template<typename UVMapper>
113 __forceinline bool intersectEdge(const vbool<M>& valid,
114 Ray& ray,
115 const Vec3vf<M>& tri_v0,
116 const Vec3vf<M>& tri_e1,
117 const Vec3vf<M>& tri_e2,
118 const UVMapper& mapUV,
119 MoellerTrumboreHitM<M,UVMapper>& hit) const
120 {
121 const Vec3<vfloat<M>> tri_Ng = cross(tri_e2,tri_e1);
122 return intersect(valid,ray,tri_v0,tri_e1,tri_e2,tri_Ng,mapUV,hit);
123 }
124
125 template<typename UVMapper>
126 __forceinline bool intersectEdge(Ray& ray,
127 const Vec3vf<M>& tri_v0,
128 const Vec3vf<M>& tri_e1,
129 const Vec3vf<M>& tri_e2,
130 const UVMapper& mapUV,
131 MoellerTrumboreHitM<M,UVMapper>& hit) const
132 {
133 vbool<M> valid = true;
134 const Vec3<vfloat<M>> tri_Ng = cross(tri_e2,tri_e1);
135 return intersect(valid,ray,tri_v0,tri_e1,tri_e2,tri_Ng,mapUV,hit);
136 }
137
138 template<typename UVMapper>
139 __forceinline bool intersect(Ray& ray,
140 const Vec3vf<M>& v0,
141 const Vec3vf<M>& v1,
142 const Vec3vf<M>& v2,
143 const UVMapper& mapUV,
144 MoellerTrumboreHitM<M,UVMapper>& hit) const
145 {
146 const Vec3vf<M> e1 = v0-v1;
147 const Vec3vf<M> e2 = v2-v0;
148 return intersectEdge(ray,v0,e1,e2,mapUV,hit);
149 }
150
151 template<typename UVMapper>
152 __forceinline bool intersect(const vbool<M>& valid,
153 Ray& ray,
154 const Vec3vf<M>& v0,
155 const Vec3vf<M>& v1,
156 const Vec3vf<M>& v2,
157 const UVMapper& mapUV,
158 MoellerTrumboreHitM<M,UVMapper>& hit) const
159 {
160 const Vec3vf<M> e1 = v0-v1;
161 const Vec3vf<M> e2 = v2-v0;
162 return intersectEdge(valid,ray,v0,e1,e2,mapUV,hit);
163 }
164
165 template<typename UVMapper, typename Epilog>
166 __forceinline bool intersectEdge(Ray& ray,
167 const Vec3vf<M>& v0,
168 const Vec3vf<M>& e1,
169 const Vec3vf<M>& e2,
170 const UVMapper& mapUV,
171 const Epilog& epilog) const
172 {
173 MoellerTrumboreHitM<M,UVMapper> hit(mapUV);
174 if (likely(intersectEdge(ray,v0,e1,e2,mapUV,hit))) return epilog(hit.valid,hit);
175 return false;
176 }
177
178 template<typename UVMapper, typename Epilog>
179 __forceinline bool intersect(Ray& ray,
180 const Vec3vf<M>& v0,
181 const Vec3vf<M>& v1,
182 const Vec3vf<M>& v2,
183 const UVMapper& mapUV,
184 const Epilog& epilog) const
185 {
186 MoellerTrumboreHitM<M,UVMapper> hit(mapUV);
187 if (likely(intersect(ray,v0,v1,v2,mapUV,hit))) return epilog(hit.valid,hit);
188 return false;
189 }
190
191 template<typename Epilog>
192 __forceinline bool intersect(Ray& ray,
193 const Vec3vf<M>& v0,
194 const Vec3vf<M>& v1,
195 const Vec3vf<M>& v2,
196 const Epilog& epilog) const
197 {
198 auto mapUV = UVIdentity<M>();
199 MoellerTrumboreHitM<M,UVIdentity<M>> hit(mapUV);
200 if (likely(intersect(ray,v0,v1,v2,mapUV,hit))) return epilog(hit.valid,hit);
201 return false;
202 }
203
204 template<typename UVMapper, typename Epilog>
205 __forceinline bool intersect(const vbool<M>& valid,
206 Ray& ray,
207 const Vec3vf<M>& v0,
208 const Vec3vf<M>& v1,
209 const Vec3vf<M>& v2,
210 const UVMapper& mapUV,
211 const Epilog& epilog) const
212 {
213 MoellerTrumboreHitM<M,UVMapper> hit(mapUV);
214 if (likely(intersect(valid,ray,v0,v1,v2,mapUV,hit))) return epilog(hit.valid,hit);
215 return false;
216 }
217 };
218
219 template<int K, typename UVMapper>
220 struct MoellerTrumboreHitK
221 {
222 __forceinline MoellerTrumboreHitK(const UVMapper& mapUV) : mapUV(mapUV) {}
223 __forceinline MoellerTrumboreHitK(const vfloat<K>& U, const vfloat<K>& V, const vfloat<K>& T, const vfloat<K>& absDen, const Vec3vf<K>& Ng, const UVMapper& mapUV)
224 : U(U), V(V), T(T), absDen(absDen), Ng(Ng), mapUV(mapUV) {}
225
226 __forceinline std::tuple<vfloat<K>,vfloat<K>,vfloat<K>,Vec3vf<K>> operator() () const
227 {
228 const vfloat<K> rcpAbsDen = rcp(absDen);
229 const vfloat<K> t = T * rcpAbsDen;
230 vfloat<K> u = U * rcpAbsDen;
231 vfloat<K> v = V * rcpAbsDen;
232 Vec3vf<K> vNg = Ng;
233 mapUV(u,v,vNg);
234 return std::make_tuple(u,v,t,vNg);
235 }
236
237 vfloat<K> U;
238 vfloat<K> V;
239 const vfloat<K> T;
240 const vfloat<K> absDen;
241 const Vec3vf<K> Ng;
242 const UVMapper& mapUV;
243 };
244
245 template<int M, int K>
246 struct MoellerTrumboreIntersectorK
247 {
248 __forceinline MoellerTrumboreIntersectorK() {}
249 __forceinline MoellerTrumboreIntersectorK(const vbool<K>& valid, const RayK<K>& ray) {}
250
251 /*! Intersects K rays with one of M triangles. */
252 template<typename UVMapper>
253 __forceinline vbool<K> intersectK(const vbool<K>& valid0,
254 //RayK<K>& ray,
255 const Vec3vf<K>& ray_org,
256 const Vec3vf<K>& ray_dir,
257 const vfloat<K>& ray_tnear,
258 const vfloat<K>& ray_tfar,
259 const Vec3vf<K>& tri_v0,
260 const Vec3vf<K>& tri_e1,
261 const Vec3vf<K>& tri_e2,
262 const Vec3vf<K>& tri_Ng,
263 const UVMapper& mapUV,
264 MoellerTrumboreHitK<K,UVMapper> &hit) const
265 {
266 /* calculate denominator */
267 vbool<K> valid = valid0;
268 const Vec3vf<K> C = tri_v0 - ray_org;
269 const Vec3vf<K> R = cross(C,ray_dir);
270 const vfloat<K> den = dot(tri_Ng,ray_dir);
271 const vfloat<K> absDen = abs(den);
272 const vfloat<K> sgnDen = signmsk(den);
273
274 /* test against edge p2 p0 */
275 const vfloat<K> U = dot(tri_e2,R) ^ sgnDen;
276 valid &= U >= 0.0f;
277 if (likely(none(valid))) return false;
278
279 /* test against edge p0 p1 */
280 const vfloat<K> V = dot(tri_e1,R) ^ sgnDen;
281 valid &= V >= 0.0f;
282 if (likely(none(valid))) return false;
283
284 /* test against edge p1 p2 */
285 const vfloat<K> W = absDen-U-V;
286 valid &= W >= 0.0f;
287 if (likely(none(valid))) return false;
288
289 /* perform depth test */
290 const vfloat<K> T = dot(tri_Ng,C) ^ sgnDen;
291 valid &= (absDen*ray_tnear < T) & (T <= absDen*ray_tfar);
292 if (unlikely(none(valid))) return false;
293
294 /* perform backface culling */
295#if defined(EMBREE_BACKFACE_CULLING)
296 valid &= den < vfloat<K>(zero);
297 if (unlikely(none(valid))) return false;
298#else
299 valid &= den != vfloat<K>(zero);
300 if (unlikely(none(valid))) return false;
301#endif
302
303 /* calculate hit information */
304 new (&hit) MoellerTrumboreHitK<K,UVMapper>(U,V,T,absDen,tri_Ng,mapUV);
305 return valid;
306 }
307
308 /*! Intersects K rays with one of M triangles. */
309 template<typename UVMapper>
310 __forceinline vbool<K> intersectK(const vbool<K>& valid0,
311 RayK<K>& ray,
312 const Vec3vf<K>& tri_v0,
313 const Vec3vf<K>& tri_v1,
314 const Vec3vf<K>& tri_v2,
315 const UVMapper& mapUV,
316 MoellerTrumboreHitK<K,UVMapper> &hit) const
317 {
318 const Vec3vf<K> e1 = tri_v0-tri_v1;
319 const Vec3vf<K> e2 = tri_v2-tri_v0;
320 const Vec3vf<K> Ng = cross(e2,e1);
321 return intersectK(valid0,ray.org,ray.dir,ray.tnear(),ray.tfar,tri_v0,e1,e2,Ng,mapUV,hit);
322 }
323
324
325 /*! Intersects K rays with one of M triangles. */
326 template<typename UVMapper, typename Epilog>
327 __forceinline vbool<K> intersectK(const vbool<K>& valid0,
328 RayK<K>& ray,
329 const Vec3vf<K>& tri_v0,
330 const Vec3vf<K>& tri_v1,
331 const Vec3vf<K>& tri_v2,
332 const UVMapper& mapUV,
333 const Epilog& epilog) const
334 {
335 MoellerTrumboreHitK<K,UVIdentity<K>> hit(mapUV);
336 const Vec3vf<K> e1 = tri_v0-tri_v1;
337 const Vec3vf<K> e2 = tri_v2-tri_v0;
338 const Vec3vf<K> Ng = cross(e2,e1);
339 const vbool<K> valid = intersectK(valid0,ray.org,ray.dir,ray.tnear(),ray.tfar,tri_v0,e1,e2,Ng,mapUV,hit);
340 return epilog(valid,hit);
341 }
342
343
344
345 template<typename Epilog>
346 __forceinline vbool<K> intersectK(const vbool<K>& valid0,
347 RayK<K>& ray,
348 const Vec3vf<K>& tri_v0,
349 const Vec3vf<K>& tri_v1,
350 const Vec3vf<K>& tri_v2,
351 const Epilog& epilog) const
352 {
353 UVIdentity<K> mapUV;
354 MoellerTrumboreHitK<K,UVIdentity<K>> hit(mapUV);
355 const Vec3vf<K> e1 = tri_v0-tri_v1;
356 const Vec3vf<K> e2 = tri_v2-tri_v0;
357 const Vec3vf<K> Ng = cross(e2,e1);
358 const vbool<K> valid = intersectK(valid0,ray.org,ray.dir,ray.tnear(),ray.tfar,tri_v0,e1,e2,Ng,mapUV,hit);
359 return epilog(valid,hit);
360 }
361
362 /*! Intersects K rays with one of M triangles. */
363 template<typename UVMapper, typename Epilog>
364 __forceinline vbool<K> intersectEdgeK(const vbool<K>& valid0,
365 RayK<K>& ray,
366 const Vec3vf<K>& tri_v0,
367 const Vec3vf<K>& tri_e1,
368 const Vec3vf<K>& tri_e2,
369 const UVMapper& mapUV,
370 const Epilog& epilog) const
371 {
372 MoellerTrumboreHitK<K,UVIdentity<K>> hit(mapUV);
373 const Vec3vf<K> tri_Ng = cross(tri_e2,tri_e1);
374 const vbool<K> valid = intersectK(valid0,ray.org,ray.dir,ray.tnear(),ray.tfar,tri_v0,tri_e1,tri_e2,tri_Ng,mapUV,hit);
375 return epilog(valid,hit);
376 }
377
378 /*! Intersect k'th ray from ray packet of size K with M triangles. */
379 template<typename UVMapper>
380 __forceinline bool intersectEdge(RayK<K>& ray,
381 size_t k,
382 const Vec3vf<M>& tri_v0,
383 const Vec3vf<M>& tri_e1,
384 const Vec3vf<M>& tri_e2,
385 const UVMapper& mapUV,
386 MoellerTrumboreHitM<M,UVMapper>& hit) const
387 {
388 /* calculate denominator */
389 typedef Vec3vf<M> Vec3vfM;
390 const Vec3vf<M> tri_Ng = cross(tri_e2,tri_e1);
391
392 const Vec3vfM O = broadcast<vfloat<M>>(ray.org,k);
393 const Vec3vfM D = broadcast<vfloat<M>>(ray.dir,k);
394 const Vec3vfM C = Vec3vfM(tri_v0) - O;
395 const Vec3vfM R = cross(C,D);
396 const vfloat<M> den = dot(Vec3vfM(tri_Ng),D);
397 const vfloat<M> absDen = abs(den);
398 const vfloat<M> sgnDen = signmsk(den);
399
400 /* perform edge tests */
401 const vfloat<M> U = dot(Vec3vf<M>(tri_e2),R) ^ sgnDen;
402 const vfloat<M> V = dot(Vec3vf<M>(tri_e1),R) ^ sgnDen;
403
404 /* perform backface culling */
405#if defined(EMBREE_BACKFACE_CULLING)
406 vbool<M> valid = (den < vfloat<M>(zero)) & (U >= 0.0f) & (V >= 0.0f) & (U+V<=absDen);
407#else
408 vbool<M> valid = (den != vfloat<M>(zero)) & (U >= 0.0f) & (V >= 0.0f) & (U+V<=absDen);
409#endif
410 if (likely(none(valid))) return false;
411
412 /* perform depth test */
413 const vfloat<M> T = dot(Vec3vf<M>(tri_Ng),C) ^ sgnDen;
414 valid &= (absDen*vfloat<M>(ray.tnear()[k]) < T) & (T <= absDen*vfloat<M>(ray.tfar[k]));
415 if (likely(none(valid))) return false;
416
417 /* calculate hit information */
418 new (&hit) MoellerTrumboreHitM<M,UVMapper>(valid,U,V,T,absDen,tri_Ng,mapUV);
419 return true;
420 }
421
422 template<typename UVMapper>
423 __forceinline bool intersectEdge(RayK<K>& ray,
424 size_t k,
425 const BBox<vfloat<M>>& time_range,
426 const Vec3vf<M>& tri_v0,
427 const Vec3vf<M>& tri_e1,
428 const Vec3vf<M>& tri_e2,
429 const UVMapper& mapUV,
430 MoellerTrumboreHitM<M,UVMapper>& hit) const
431 {
432 if (likely(intersect(ray,k,tri_v0,tri_e1,tri_e2,mapUV,hit)))
433 {
434 hit.valid &= time_range.lower <= vfloat<M>(ray.time[k]);
435 hit.valid &= vfloat<M>(ray.time[k]) < time_range.upper;
436 return any(hit.valid);
437 }
438 return false;
439 }
440
441 template<typename UVMapper>
442 __forceinline bool intersect(RayK<K>& ray,
443 size_t k,
444 const Vec3vf<M>& v0,
445 const Vec3vf<M>& v1,
446 const Vec3vf<M>& v2,
447 const UVMapper& mapUV,
448 MoellerTrumboreHitM<M,UVMapper>& hit) const
449 {
450 const Vec3vf<M> e1 = v0-v1;
451 const Vec3vf<M> e2 = v2-v0;
452 return intersectEdge(ray,k,v0,e1,e2,mapUV,hit);
453 }
454
455 template<typename UVMapper, typename Epilog>
456 __forceinline bool intersectEdge(RayK<K>& ray,
457 size_t k,
458 const Vec3vf<M>& tri_v0,
459 const Vec3vf<M>& tri_e1,
460 const Vec3vf<M>& tri_e2,
461 const UVMapper& mapUV,
462 const Epilog& epilog) const
463 {
464 MoellerTrumboreHitM<M,UVMapper> hit(mapUV);
465 if (likely(intersectEdge(ray,k,tri_v0,tri_e1,tri_e2,mapUV,hit))) return epilog(hit.valid,hit);
466 return false;
467 }
468
469 template<typename UVMapper, typename Epilog>
470 __forceinline bool intersectEdge(RayK<K>& ray,
471 size_t k,
472 const BBox<vfloat<M>>& time_range,
473 const Vec3vf<M>& tri_v0,
474 const Vec3vf<M>& tri_e1,
475 const Vec3vf<M>& tri_e2,
476 const UVMapper& mapUV,
477 const Epilog& epilog) const
478 {
479 MoellerTrumboreHitM<M,UVMapper> hit(mapUV);
480 if (likely(intersectEdge(ray,k,time_range,tri_v0,tri_e1,tri_e2,mapUV,hit))) return epilog(hit.valid,hit);
481 return false;
482 }
483
484 template<typename UVMapper, typename Epilog>
485 __forceinline bool intersect(RayK<K>& ray,
486 size_t k,
487 const Vec3vf<M>& v0,
488 const Vec3vf<M>& v1,
489 const Vec3vf<M>& v2,
490 const UVMapper& mapUV,
491 const Epilog& epilog) const
492 {
493 const Vec3vf<M> e1 = v0-v1;
494 const Vec3vf<M> e2 = v2-v0;
495 return intersectEdge(ray,k,v0,e1,e2,mapUV,epilog);
496 }
497
498 template<typename Epilog>
499 __forceinline bool intersect(RayK<K>& ray,
500 size_t k,
501 const Vec3vf<M>& v0,
502 const Vec3vf<M>& v1,
503 const Vec3vf<M>& v2,
504 const Epilog& epilog) const
505 {
506 return intersect(ray,k,v0,v1,v2,UVIdentity<M>(),epilog);
507 }
508
509 template<typename UVMapper, typename Epilog>
510 __forceinline bool intersect(RayK<K>& ray,
511 size_t k,
512 const BBox<vfloat<M>>& time_range,
513 const Vec3vf<M>& v0,
514 const Vec3vf<M>& v1,
515 const Vec3vf<M>& v2,
516 const UVMapper& mapUV,
517 const Epilog& epilog) const
518 {
519 const Vec3vf<M> e1 = v0-v1;
520 const Vec3vf<M> e2 = v2-v0;
521 return intersectEdge(ray,k,time_range,v0,e1,e2,mapUV,epilog);
522 }
523 };
524 }
525}
526

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