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 | |
26 | namespace 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(ray.tnear(), 0.0f), max(ray.tfar, 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(ray.tnear(), 0.0f), max(ray.tfar, 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(context->query_radius, 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(context->query_radius, 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 | |