1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "bvh_intersector1.h"
5#include "node_intersector1.h"
6#include "bvh_traverser1.h"
7
8#include "../geometry/intersector_iterators.h"
9#include "../geometry/triangle_intersector.h"
10#include "../geometry/trianglev_intersector.h"
11#include "../geometry/trianglev_mb_intersector.h"
12#include "../geometry/trianglei_intersector.h"
13#include "../geometry/quadv_intersector.h"
14#include "../geometry/quadi_intersector.h"
15#include "../geometry/curveNv_intersector.h"
16#include "../geometry/curveNi_intersector.h"
17#include "../geometry/curveNi_mb_intersector.h"
18#include "../geometry/linei_intersector.h"
19#include "../geometry/subdivpatch1_intersector.h"
20#include "../geometry/object_intersector.h"
21#include "../geometry/instance_intersector.h"
22#include "../geometry/subgrid_intersector.h"
23#include "../geometry/subgrid_mb_intersector.h"
24#include "../geometry/curve_intersector_virtual.h"
25
26namespace embree
27{
28 namespace isa
29 {
30 template<int N, int types, bool robust, typename PrimitiveIntersector1>
31 void BVHNIntersector1<N, types, robust, PrimitiveIntersector1>::intersect(const Accel::Intersectors* __restrict__ This,
32 RayHit& __restrict__ ray,
33 IntersectContext* __restrict__ context)
34 {
35 const BVH* __restrict__ bvh = (const BVH*)This->ptr;
36
37 /* we may traverse an empty BVH in case all geometry was invalid */
38 if (bvh->root == BVH::emptyNode)
39 return;
40
41 /* perform per ray precalculations required by the primitive intersector */
42 Precalculations pre(ray, bvh);
43
44 /* stack state */
45 StackItemT<NodeRef> stack[stackSize]; // stack of nodes
46 StackItemT<NodeRef>* stackPtr = stack+1; // current stack pointer
47 StackItemT<NodeRef>* stackEnd = stack+stackSize;
48 stack[0].ptr = bvh->root;
49 stack[0].dist = neg_inf;
50
51 if (bvh->root == BVH::emptyNode)
52 return;
53
54 /* filter out invalid rays */
55#if defined(EMBREE_IGNORE_INVALID_RAYS)
56 if (!ray.valid()) return;
57#endif
58 /* verify correct input */
59 assert(ray.valid());
60 assert(ray.tnear() >= 0.0f);
61 assert(!(types & BVH_MB) || (ray.time() >= 0.0f && ray.time() <= 1.0f));
62
63 /* load the ray into SIMD registers */
64 TravRay<N,robust> tray(ray.org, ray.dir, max(a: ray.tnear(), b: 0.0f), max(a: ray.tfar, b: 0.0f));
65
66 /* initialize the node traverser */
67 BVHNNodeTraverser1Hit<N, types> nodeTraverser;
68
69 /* pop loop */
70 while (true) pop:
71 {
72 /* pop next node */
73 if (unlikely(stackPtr == stack)) break;
74 stackPtr--;
75 NodeRef cur = NodeRef(stackPtr->ptr);
76
77 /* if popped node is too far, pop next one */
78 if (unlikely(*(float*)&stackPtr->dist > ray.tfar))
79 continue;
80
81 /* downtraversal loop */
82 while (true)
83 {
84 /* intersect node */
85 size_t mask; vfloat<N> tNear;
86 STAT3(normal.trav_nodes,1,1,1);
87 bool nodeIntersected = BVHNNodeIntersector1<N, types, robust>::intersect(cur, tray, ray.time(), tNear, mask);
88 if (unlikely(!nodeIntersected)) { STAT3(normal.trav_nodes,-1,-1,-1); break; }
89
90 /* if no child is hit, pop next node */
91 if (unlikely(mask == 0))
92 goto pop;
93
94 /* select next child and push other children */
95 nodeTraverser.traverseClosestHit(cur, mask, tNear, stackPtr, stackEnd);
96 }
97
98 /* this is a leaf node */
99 assert(cur != BVH::emptyNode);
100 STAT3(normal.trav_leaves,1,1,1);
101 size_t num; Primitive* prim = (Primitive*)cur.leaf(num);
102 size_t lazy_node = 0;
103 PrimitiveIntersector1::intersect(This, pre, ray, context, prim, num, tray, lazy_node);
104 tray.tfar = ray.tfar;
105
106 /* push lazy node onto stack */
107 if (unlikely(lazy_node)) {
108 stackPtr->ptr = lazy_node;
109 stackPtr->dist = neg_inf;
110 stackPtr++;
111 }
112 }
113 }
114
115 template<int N, int types, bool robust, typename PrimitiveIntersector1>
116 void BVHNIntersector1<N, types, robust, PrimitiveIntersector1>::occluded(const Accel::Intersectors* __restrict__ This,
117 Ray& __restrict__ ray,
118 IntersectContext* __restrict__ context)
119 {
120 const BVH* __restrict__ bvh = (const BVH*)This->ptr;
121
122 /* we may traverse an empty BVH in case all geometry was invalid */
123 if (bvh->root == BVH::emptyNode)
124 return;
125
126 /* early out for already occluded rays */
127 if (unlikely(ray.tfar < 0.0f))
128 return;
129
130 /* perform per ray precalculations required by the primitive intersector */
131 Precalculations pre(ray, bvh);
132
133 /* stack state */
134 NodeRef stack[stackSize]; // stack of nodes that still need to get traversed
135 NodeRef* stackPtr = stack+1; // current stack pointer
136 NodeRef* stackEnd = stack+stackSize;
137 stack[0] = bvh->root;
138
139 /* filter out invalid rays */
140#if defined(EMBREE_IGNORE_INVALID_RAYS)
141 if (!ray.valid()) return;
142#endif
143
144 /* verify correct input */
145 assert(ray.valid());
146 assert(ray.tnear() >= 0.0f);
147 assert(!(types & BVH_MB) || (ray.time() >= 0.0f && ray.time() <= 1.0f));
148
149 /* load the ray into SIMD registers */
150 TravRay<N,robust> tray(ray.org, ray.dir, max(a: ray.tnear(), b: 0.0f), max(a: ray.tfar, b: 0.0f));
151
152 /* initialize the node traverser */
153 BVHNNodeTraverser1Hit<N, types> nodeTraverser;
154
155 /* pop loop */
156 while (true) pop:
157 {
158 /* pop next node */
159 if (unlikely(stackPtr == stack)) break;
160 stackPtr--;
161 NodeRef cur = (NodeRef)*stackPtr;
162
163 /* downtraversal loop */
164 while (true)
165 {
166 /* intersect node */
167 size_t mask; vfloat<N> tNear;
168 STAT3(shadow.trav_nodes,1,1,1);
169 bool nodeIntersected = BVHNNodeIntersector1<N, types, robust>::intersect(cur, tray, ray.time(), tNear, mask);
170 if (unlikely(!nodeIntersected)) { STAT3(shadow.trav_nodes,-1,-1,-1); break; }
171
172 /* if no child is hit, pop next node */
173 if (unlikely(mask == 0))
174 goto pop;
175
176 /* select next child and push other children */
177 nodeTraverser.traverseAnyHit(cur, mask, tNear, stackPtr, stackEnd);
178 }
179
180 /* this is a leaf node */
181 assert(cur != BVH::emptyNode);
182 STAT3(shadow.trav_leaves,1,1,1);
183 size_t num; Primitive* prim = (Primitive*)cur.leaf(num);
184 size_t lazy_node = 0;
185 if (PrimitiveIntersector1::occluded(This, pre, ray, context, prim, num, tray, lazy_node)) {
186 ray.tfar = neg_inf;
187 break;
188 }
189
190 /* push lazy node onto stack */
191 if (unlikely(lazy_node)) {
192 *stackPtr = (NodeRef)lazy_node;
193 stackPtr++;
194 }
195 }
196 }
197
198 template<int N, int types, bool robust, typename PrimitiveIntersector1>
199 struct PointQueryDispatch
200 {
201 typedef typename PrimitiveIntersector1::Precalculations Precalculations;
202 typedef typename PrimitiveIntersector1::Primitive Primitive;
203 typedef BVHN<N> BVH;
204 typedef typename BVH::NodeRef NodeRef;
205 typedef typename BVH::AABBNode AABBNode;
206 typedef typename BVH::AABBNodeMB4D AABBNodeMB4D;
207
208 static const size_t stackSize = 1+(N-1)*BVH::maxDepth+3; // +3 due to 16-wide store
209
210 static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context)
211 {
212 const BVH* __restrict__ bvh = (const BVH*)This->ptr;
213
214 /* we may traverse an empty BVH in case all geometry was invalid */
215 if (bvh->root == BVH::emptyNode)
216 return false;
217
218 /* stack state */
219 StackItemT<NodeRef> stack[stackSize]; // stack of nodes
220 StackItemT<NodeRef>* stackPtr = stack+1; // current stack pointer
221 StackItemT<NodeRef>* stackEnd = stack+stackSize;
222 stack[0].ptr = bvh->root;
223 stack[0].dist = neg_inf;
224
225 /* verify correct input */
226 assert(!(types & BVH_MB) || (query->time >= 0.0f && query->time <= 1.0f));
227
228 /* load the point query into SIMD registers */
229 TravPointQuery<N> tquery(query->p, context->query_radius);
230
231 /* initialize the node traverser */
232 BVHNNodeTraverser1Hit<N,types> nodeTraverser;
233
234 bool changed = false;
235 float cull_radius = context->query_type == POINT_QUERY_TYPE_SPHERE
236 ? query->radius * query->radius
237 : dot(a: context->query_radius, b: context->query_radius);
238
239 /* pop loop */
240 while (true) pop:
241 {
242 /* pop next node */
243 if (unlikely(stackPtr == stack)) break;
244 stackPtr--;
245 NodeRef cur = NodeRef(stackPtr->ptr);
246
247 /* if popped node is too far, pop next one */
248 if (unlikely(*(float*)&stackPtr->dist > cull_radius))
249 continue;
250
251 /* downtraversal loop */
252 while (true)
253 {
254 /* intersect node */
255 size_t mask; vfloat<N> tNear;
256 STAT3(point_query.trav_nodes,1,1,1);
257 bool nodeIntersected;
258 if (likely(context->query_type == POINT_QUERY_TYPE_SPHERE)) {
259 nodeIntersected = BVHNNodePointQuerySphere1<N, types>::pointQuery(cur, tquery, query->time, tNear, mask);
260 } else {
261 nodeIntersected = BVHNNodePointQueryAABB1 <N, types>::pointQuery(cur, tquery, query->time, tNear, mask);
262 }
263 if (unlikely(!nodeIntersected)) { STAT3(point_query.trav_nodes,-1,-1,-1); break; }
264
265 /* if no child is hit, pop next node */
266 if (unlikely(mask == 0))
267 goto pop;
268
269 /* select next child and push other children */
270 nodeTraverser.traverseClosestHit(cur, mask, tNear, stackPtr, stackEnd);
271 }
272
273 /* this is a leaf node */
274 assert(cur != BVH::emptyNode);
275 STAT3(point_query.trav_leaves,1,1,1);
276 size_t num; Primitive* prim = (Primitive*)cur.leaf(num);
277 size_t lazy_node = 0;
278 if (PrimitiveIntersector1::pointQuery(This, query, context, prim, num, tquery, lazy_node))
279 {
280 changed = true;
281 tquery.rad = context->query_radius;
282 cull_radius = context->query_type == POINT_QUERY_TYPE_SPHERE
283 ? query->radius * query->radius
284 : dot(a: context->query_radius, b: context->query_radius);
285 }
286
287 /* push lazy node onto stack */
288 if (unlikely(lazy_node)) {
289 stackPtr->ptr = lazy_node;
290 stackPtr->dist = neg_inf;
291 stackPtr++;
292 }
293 }
294 return changed;
295 }
296 };
297
298 /* disable point queries for not yet supported geometry types */
299 template<int N, int types, bool robust>
300 struct PointQueryDispatch<N, types, robust, VirtualCurveIntersector1> {
301 static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context) { return false; }
302 };
303
304 template<int N, int types, bool robust>
305 struct PointQueryDispatch<N, types, robust, SubdivPatch1Intersector1> {
306 static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context) { return false; }
307 };
308
309 template<int N, int types, bool robust>
310 struct PointQueryDispatch<N, types, robust, SubdivPatch1MBIntersector1> {
311 static __forceinline bool pointQuery(const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context) { return false; }
312 };
313
314 template<int N, int types, bool robust, typename PrimitiveIntersector1>
315 bool BVHNIntersector1<N, types, robust, PrimitiveIntersector1>::pointQuery(
316 const Accel::Intersectors* This, PointQuery* query, PointQueryContext* context)
317 {
318 return PointQueryDispatch<N, types, robust, PrimitiveIntersector1>::pointQuery(This, query, context);
319 }
320 }
321}
322

source code of qtquick3d/src/3rdparty/embree/kernels/bvh/bvh_intersector1.cpp