1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "bvh.h"
5#include "bvh_builder.h"
6#include "../builders/bvh_builder_msmblur.h"
7
8#include "../builders/primrefgen.h"
9#include "../builders/splitter.h"
10
11#include "../geometry/linei.h"
12#include "../geometry/triangle.h"
13#include "../geometry/trianglev.h"
14#include "../geometry/trianglev_mb.h"
15#include "../geometry/trianglei.h"
16#include "../geometry/quadv.h"
17#include "../geometry/quadi.h"
18#include "../geometry/object.h"
19#include "../geometry/instance.h"
20#include "../geometry/subgrid.h"
21
22#include "../common/state.h"
23
24// FIXME: remove after removing BVHNBuilderMBlurRootTimeSplitsSAH
25#include "../../common/algorithms/parallel_for_for.h"
26#include "../../common/algorithms/parallel_for_for_prefix_sum.h"
27
28
29namespace embree
30{
31 namespace isa
32 {
33
34#if 0
35 template<int N, typename Primitive>
36 struct CreateMBlurLeaf
37 {
38 typedef BVHN<N> BVH;
39 typedef typename BVH::NodeRef NodeRef;
40 typedef typename BVH::NodeRecordMB NodeRecordMB;
41
42 __forceinline CreateMBlurLeaf (BVH* bvh, PrimRef* prims, size_t time) : bvh(bvh), prims(prims), time(time) {}
43
44 __forceinline NodeRecordMB operator() (const PrimRef* prims, const range<size_t>& set, const FastAllocator::CachedAllocator& alloc) const
45 {
46 size_t items = Primitive::blocks(set.size());
47 size_t start = set.begin();
48 for (size_t i=start; i<end; i++) assert((*current.prims.prims)[start].geomID() == (*current.prims.prims)[i].geomID()); // assert that all geomIDs are identical
49 Primitive* accel = (Primitive*) alloc.malloc1(items*sizeof(Primitive),BVH::byteAlignment);
50 NodeRef node = bvh->encodeLeaf((char*)accel,items);
51
52 LBBox3fa allBounds = empty;
53 for (size_t i=0; i<items; i++)
54 allBounds.extend(accel[i].fillMB(prims, start, set.end(), bvh->scene, time));
55
56 return NodeRecordMB(node,allBounds);
57 }
58
59 BVH* bvh;
60 PrimRef* prims;
61 size_t time;
62 };
63#endif
64
65 template<int N, typename Mesh, typename Primitive>
66 struct CreateMSMBlurLeaf
67 {
68 typedef BVHN<N> BVH;
69 typedef typename BVH::NodeRef NodeRef;
70 typedef typename BVH::NodeRecordMB4D NodeRecordMB4D;
71
72 __forceinline CreateMSMBlurLeaf (BVH* bvh) : bvh(bvh) {}
73
74 __forceinline const NodeRecordMB4D operator() (const BVHBuilderMSMBlur::BuildRecord& current, const FastAllocator::CachedAllocator& alloc) const
75 {
76 size_t items = Primitive::blocks(current.prims.size());
77 size_t start = current.prims.begin();
78 size_t end = current.prims.end();
79 for (size_t i=start; i<end; i++) assert((*current.prims.prims)[start].geomID() == (*current.prims.prims)[i].geomID()); // assert that all geomIDs are identical
80 Primitive* accel = (Primitive*) alloc.malloc1(bytes: items*sizeof(Primitive),align: BVH::byteNodeAlignment);
81 NodeRef node = bvh->encodeLeaf((char*)accel,items);
82 LBBox3fa allBounds = empty;
83 for (size_t i=0; i<items; i++)
84 allBounds.extend(other: accel[i].fillMB(current.prims.prims->data(), start, current.prims.end(), bvh->scene, current.prims.time_range));
85 return NodeRecordMB4D(node,allBounds,current.prims.time_range);
86 }
87
88 BVH* bvh;
89 };
90
91 /* Motion blur BVH with 4D nodes and internal time splits */
92 template<int N, typename Mesh, typename Primitive>
93 struct BVHNBuilderMBlurSAH : public Builder
94 {
95 typedef BVHN<N> BVH;
96 typedef typename BVHN<N>::NodeRef NodeRef;
97 typedef typename BVHN<N>::NodeRecordMB NodeRecordMB;
98 typedef typename BVHN<N>::AABBNodeMB AABBNodeMB;
99
100 BVH* bvh;
101 Scene* scene;
102 const size_t sahBlockSize;
103 const float intCost;
104 const size_t minLeafSize;
105 const size_t maxLeafSize;
106 const Geometry::GTypeMask gtype_;
107
108 BVHNBuilderMBlurSAH (BVH* bvh, Scene* scene, const size_t sahBlockSize, const float intCost, const size_t minLeafSize, const size_t maxLeafSize, const Geometry::GTypeMask gtype)
109 : bvh(bvh), scene(scene), sahBlockSize(sahBlockSize), intCost(intCost), minLeafSize(minLeafSize), maxLeafSize(min(maxLeafSize,Primitive::max_size()*BVH::maxLeafBlocks)), gtype_(gtype) {}
110
111 void build()
112 {
113 /* skip build for empty scene */
114 const size_t numPrimitives = scene->getNumPrimitives(mask: gtype_,mblur: true);
115 if (numPrimitives == 0) { bvh->clear(); return; }
116
117 double t0 = bvh->preBuild(TOSTRING(isa) "::BVH" + toString(value: N) + "BuilderMBlurSAH");
118
119#if PROFILE
120 profile(2,PROFILE_RUNS,numPrimitives,[&] (ProfileTimer& timer) {
121#endif
122
123 //const size_t numTimeSteps = scene->getNumTimeSteps<typename Mesh::type_t,true>();
124 //const size_t numTimeSegments = numTimeSteps-1; assert(numTimeSteps > 1);
125
126 /*if (numTimeSegments == 1)
127 buildSingleSegment(numPrimitives);
128 else*/
129 buildMultiSegment(numPrimitives);
130
131#if PROFILE
132 });
133#endif
134
135 /* clear temporary data for static geometry */
136 bvh->cleanup();
137 bvh->postBuild(t0);
138 }
139
140#if 0 // No longer compatible when time_ranges are present for geometries. Would have to create temporal nodes sometimes, and put only a single geometry into leaf.
141 void buildSingleSegment(size_t numPrimitives)
142 {
143 /* create primref array */
144 mvector<PrimRef> prims(scene->device,numPrimitives);
145 const PrimInfo pinfo = createPrimRefArrayMBlur(scene,gtype_,numPrimitives,prims,bvh->scene->progressInterface,0);
146 /* early out if no valid primitives */
147 if (pinfo.size() == 0) { bvh->clear(); return; }
148 /* estimate acceleration structure size */
149 const size_t node_bytes = pinfo.size()*sizeof(AABBNodeMB)/(4*N);
150 const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.size())*sizeof(Primitive));
151 bvh->alloc.init_estimate(node_bytes+leaf_bytes);
152
153 /* settings for BVH build */
154 GeneralBVHBuilder::Settings settings;
155 settings.branchingFactor = N;
156 settings.maxDepth = BVH::maxBuildDepthLeaf;
157 settings.logBlockSize = bsr(sahBlockSize);
158 settings.minLeafSize = min(minLeafSize,maxLeafSize);
159 settings.maxLeafSize = maxLeafSize;
160 settings.travCost = travCost;
161 settings.intCost = intCost;
162 settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
163
164 /* build hierarchy */
165 auto root = BVHBuilderBinnedSAH::build<NodeRecordMB>
166 (typename BVH::CreateAlloc(bvh),typename BVH::AABBNodeMB::Create(),typename BVH::AABBNodeMB::Set(),
167 CreateMBlurLeaf<N,Primitive>(bvh,prims.data(),0),bvh->scene->progressInterface,
168 prims.data(),pinfo,settings);
169
170 bvh->set(root.ref,root.lbounds,pinfo.size());
171 }
172#endif
173
174 void buildMultiSegment(size_t numPrimitives)
175 {
176 /* create primref array */
177 mvector<PrimRefMB> prims(scene->device,numPrimitives);
178 PrimInfoMB pinfo = createPrimRefArrayMSMBlur(scene,gtype_,numPrimitives,prims,bvh->scene->progressInterface);
179
180 /* early out if no valid primitives */
181 if (pinfo.size() == 0) { bvh->clear(); return; }
182
183 /* estimate acceleration structure size */
184 const size_t node_bytes = pinfo.num_time_segments*sizeof(AABBNodeMB)/(4*N);
185 const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.num_time_segments)*sizeof(Primitive));
186 bvh->alloc.init_estimate(node_bytes+leaf_bytes);
187
188 /* settings for BVH build */
189 BVHBuilderMSMBlur::Settings settings;
190 settings.branchingFactor = N;
191 settings.maxDepth = BVH::maxDepth;
192 settings.logBlockSize = bsr(v: sahBlockSize);
193 settings.minLeafSize = min(a: minLeafSize,b: maxLeafSize);
194 settings.maxLeafSize = maxLeafSize;
195 settings.travCost = travCost;
196 settings.intCost = intCost;
197 settings.singleLeafTimeSegment = Primitive::singleTimeSegment;
198 settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
199
200 /* build hierarchy */
201 auto root =
202 BVHBuilderMSMBlur::build<NodeRef>(prims,pinfo,scene->device,
203 RecalculatePrimRef<Mesh>(scene),
204 typename BVH::CreateAlloc(bvh),
205 typename BVH::AABBNodeMB4D::Create(),
206 typename BVH::AABBNodeMB4D::Set(),
207 CreateMSMBlurLeaf<N,Mesh,Primitive>(bvh),
208 bvh->scene->progressInterface,
209 settings);
210
211 bvh->set(root.ref,root.lbounds,pinfo.num_time_segments);
212 }
213
214 void clear() {
215 }
216 };
217
218 /************************************************************************************/
219 /************************************************************************************/
220 /************************************************************************************/
221 /************************************************************************************/
222
223 struct GridRecalculatePrimRef
224 {
225 Scene* scene;
226 const SubGridBuildData * const sgrids;
227
228 __forceinline GridRecalculatePrimRef (Scene* scene, const SubGridBuildData * const sgrids)
229 : scene(scene), sgrids(sgrids) {}
230
231 __forceinline PrimRefMB operator() (const PrimRefMB& prim, const BBox1f time_range) const
232 {
233 const unsigned int geomID = prim.geomID();
234 const GridMesh* mesh = scene->get<GridMesh>(i: geomID);
235 const unsigned int buildID = prim.primID();
236 const SubGridBuildData &subgrid = sgrids[buildID];
237 const unsigned int primID = subgrid.primID;
238 const size_t x = subgrid.x();
239 const size_t y = subgrid.y();
240 const LBBox3fa lbounds = mesh->linearBounds(g: mesh->grid(i: primID),sx: x,sy: y,dt: time_range);
241 const unsigned num_time_segments = mesh->numTimeSegments();
242 const range<int> tbounds = mesh->timeSegmentRange(range: time_range);
243 return PrimRefMB (lbounds, tbounds.size(), mesh->time_range, num_time_segments, geomID, buildID);
244 }
245
246 __forceinline LBBox3fa linearBounds(const PrimRefMB& prim, const BBox1f time_range) const {
247 const unsigned int geomID = prim.geomID();
248 const GridMesh* mesh = scene->get<GridMesh>(i: geomID);
249 const unsigned int buildID = prim.primID();
250 const SubGridBuildData &subgrid = sgrids[buildID];
251 const unsigned int primID = subgrid.primID;
252 const size_t x = subgrid.x();
253 const size_t y = subgrid.y();
254 return mesh->linearBounds(g: mesh->grid(i: primID),sx: x,sy: y,dt: time_range);
255 }
256
257 };
258
259 template<int N>
260 struct CreateMSMBlurLeafGrid
261 {
262 typedef BVHN<N> BVH;
263 typedef typename BVH::NodeRef NodeRef;
264 typedef typename BVH::NodeRecordMB4D NodeRecordMB4D;
265
266 __forceinline CreateMSMBlurLeafGrid (Scene* scene, BVH* bvh, const SubGridBuildData * const sgrids) : scene(scene), bvh(bvh), sgrids(sgrids) {}
267
268 __forceinline const NodeRecordMB4D operator() (const BVHBuilderMSMBlur::BuildRecord& current, const FastAllocator::CachedAllocator& alloc) const
269 {
270 const size_t items = current.prims.size();
271 const size_t start = current.prims.begin();
272
273 const PrimRefMB* prims = current.prims.prims->data();
274 /* collect all subsets with unique geomIDs */
275 assert(items <= N);
276 unsigned int geomIDs[N];
277 unsigned int num_geomIDs = 1;
278 geomIDs[0] = prims[start].geomID();
279
280 for (size_t i=1;i<items;i++)
281 {
282 bool found = false;
283 const unsigned int new_geomID = prims[start+i].geomID();
284 for (size_t j=0;j<num_geomIDs;j++)
285 if (new_geomID == geomIDs[j])
286 { found = true; break; }
287 if (!found)
288 geomIDs[num_geomIDs++] = new_geomID;
289 }
290
291 /* allocate all leaf memory in one single block */
292 SubGridMBQBVHN<N>* accel = (SubGridMBQBVHN<N>*) alloc.malloc1(bytes: num_geomIDs*sizeof(SubGridMBQBVHN<N>),align: BVH::byteAlignment);
293 typename BVH::NodeRef node = bvh->encodeLeaf((char*)accel,num_geomIDs);
294
295 LBBox3fa allBounds = empty;
296
297 for (size_t g=0;g<num_geomIDs;g++)
298 {
299 const GridMesh* __restrict__ const mesh = scene->get<GridMesh>(geomIDs[g]);
300 unsigned int x[N];
301 unsigned int y[N];
302 unsigned int primID[N];
303 BBox3fa bounds0[N];
304 BBox3fa bounds1[N];
305 unsigned int pos = 0;
306 for (size_t i=0;i<items;i++)
307 {
308 if (unlikely(prims[start+i].geomID() != geomIDs[g])) continue;
309
310 const SubGridBuildData &sgrid_bd = sgrids[prims[start+i].primID()];
311 x[pos] = sgrid_bd.sx;
312 y[pos] = sgrid_bd.sy;
313 primID[pos] = sgrid_bd.primID;
314 const size_t x = sgrid_bd.x();
315 const size_t y = sgrid_bd.y();
316 LBBox3fa newBounds = mesh->linearBounds(g: mesh->grid(i: sgrid_bd.primID),sx: x,sy: y,dt: current.prims.time_range);
317 allBounds.extend(other: newBounds);
318 bounds0[pos] = newBounds.bounds0;
319 bounds1[pos] = newBounds.bounds1;
320 pos++;
321 }
322 assert(pos <= N);
323 new (&accel[g]) SubGridMBQBVHN<N>(x,y,primID,bounds0,bounds1,geomIDs[g],current.prims.time_range.lower,1.0f/current.prims.time_range.size(),pos);
324 }
325 return NodeRecordMB4D(node,allBounds,current.prims.time_range);
326 }
327
328 Scene *scene;
329 BVH* bvh;
330 const SubGridBuildData * const sgrids;
331 };
332
333#if 0
334 template<int N>
335 struct CreateLeafGridMB
336 {
337 typedef BVHN<N> BVH;
338 typedef typename BVH::NodeRef NodeRef;
339 typedef typename BVH::NodeRecordMB NodeRecordMB;
340
341 __forceinline CreateLeafGridMB (Scene* scene, BVH* bvh, const SubGridBuildData * const sgrids)
342 : scene(scene), bvh(bvh), sgrids(sgrids) {}
343
344 __forceinline NodeRecordMB operator() (const PrimRef* prims, const range<size_t>& set, const FastAllocator::CachedAllocator& alloc) const
345 {
346 const size_t items = set.size();
347 const size_t start = set.begin();
348
349 /* collect all subsets with unique geomIDs */
350 assert(items <= N);
351 unsigned int geomIDs[N];
352 unsigned int num_geomIDs = 1;
353 geomIDs[0] = prims[start].geomID();
354
355 for (size_t i=1;i<items;i++)
356 {
357 bool found = false;
358 const unsigned int new_geomID = prims[start+i].geomID();
359 for (size_t j=0;j<num_geomIDs;j++)
360 if (new_geomID == geomIDs[j])
361 { found = true; break; }
362 if (!found)
363 geomIDs[num_geomIDs++] = new_geomID;
364 }
365
366 /* allocate all leaf memory in one single block */
367 SubGridMBQBVHN<N>* accel = (SubGridMBQBVHN<N>*) alloc.malloc1(num_geomIDs*sizeof(SubGridMBQBVHN<N>),BVH::byteAlignment);
368 typename BVH::NodeRef node = bvh->encodeLeaf((char*)accel,num_geomIDs);
369
370 LBBox3fa allBounds = empty;
371
372 for (size_t g=0;g<num_geomIDs;g++)
373 {
374 const GridMesh* __restrict__ const mesh = scene->get<GridMesh>(geomIDs[g]);
375
376 unsigned int x[N];
377 unsigned int y[N];
378 unsigned int primID[N];
379 BBox3fa bounds0[N];
380 BBox3fa bounds1[N];
381 unsigned int pos = 0;
382 for (size_t i=0;i<items;i++)
383 {
384 if (unlikely(prims[start+i].geomID() != geomIDs[g])) continue;
385
386 const SubGridBuildData &sgrid_bd = sgrids[prims[start+i].primID()];
387 x[pos] = sgrid_bd.sx;
388 y[pos] = sgrid_bd.sy;
389 primID[pos] = sgrid_bd.primID;
390 const size_t x = sgrid_bd.x();
391 const size_t y = sgrid_bd.y();
392 bool MAYBE_UNUSED valid0 = mesh->buildBounds(mesh->grid(sgrid_bd.primID),x,y,0,bounds0[pos]);
393 bool MAYBE_UNUSED valid1 = mesh->buildBounds(mesh->grid(sgrid_bd.primID),x,y,1,bounds1[pos]);
394 assert(valid0);
395 assert(valid1);
396 allBounds.extend(LBBox3fa(bounds0[pos],bounds1[pos]));
397 pos++;
398 }
399 new (&accel[g]) SubGridMBQBVHN<N>(x,y,primID,bounds0,bounds1,geomIDs[g],0.0f,1.0f,pos);
400 }
401 return NodeRecordMB(node,allBounds);
402 }
403
404 Scene *scene;
405 BVH* bvh;
406 const SubGridBuildData * const sgrids;
407 };
408#endif
409
410
411 /* Motion blur BVH with 4D nodes and internal time splits */
412 template<int N>
413 struct BVHNBuilderMBlurSAHGrid : public Builder
414 {
415 typedef BVHN<N> BVH;
416 typedef typename BVHN<N>::NodeRef NodeRef;
417 typedef typename BVHN<N>::NodeRecordMB NodeRecordMB;
418 typedef typename BVHN<N>::AABBNodeMB AABBNodeMB;
419
420 BVH* bvh;
421 Scene* scene;
422 const size_t sahBlockSize;
423 const float intCost;
424 const size_t minLeafSize;
425 const size_t maxLeafSize;
426 mvector<SubGridBuildData> sgrids;
427
428
429 BVHNBuilderMBlurSAHGrid (BVH* bvh, Scene* scene, const size_t sahBlockSize, const float intCost, const size_t minLeafSize, const size_t maxLeafSize)
430 : bvh(bvh), scene(scene), sahBlockSize(sahBlockSize), intCost(intCost), minLeafSize(minLeafSize), maxLeafSize(min(maxLeafSize,BVH::maxLeafBlocks)), sgrids(scene->device,0) {}
431
432
433 PrimInfo createPrimRefArrayMBlurGrid(Scene* scene, mvector<PrimRef>& prims, BuildProgressMonitor& progressMonitor, size_t itime)
434 {
435 /* first run to get #primitives */
436 ParallelForForPrefixSumState<PrimInfo> pstate;
437 Scene::Iterator<GridMesh,true> iter(scene);
438
439 pstate.init(array2&: iter,minStepSize: size_t(1024));
440
441 /* iterate over all meshes in the scene */
442 PrimInfo pinfo = parallel_for_for_prefix_sum0( pstate, iter, PrimInfo(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID) -> PrimInfo {
443
444 PrimInfo pinfo(empty);
445 for (size_t j=r.begin(); j<r.end(); j++)
446 {
447 if (!mesh->valid(gridID: j,itime_range: range<size_t>(0,1))) continue;
448 BBox3fa bounds = empty;
449 const PrimRef prim(bounds,unsigned(geomID),unsigned(j));
450 pinfo.add_center2(prim,i: mesh->getNumSubGrids(gridID: j));
451 }
452 return pinfo;
453 }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
454
455 size_t numPrimitives = pinfo.size();
456 if (numPrimitives == 0) return pinfo;
457
458 /* resize arrays */
459 sgrids.resize(new_size: numPrimitives);
460 prims.resize(new_size: numPrimitives);
461
462 /* second run to fill primrefs and SubGridBuildData arrays */
463 pinfo = parallel_for_for_prefix_sum1( pstate, iter, PrimInfo(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfo& base) -> PrimInfo {
464
465 k = base.size();
466 size_t p_index = k;
467 PrimInfo pinfo(empty);
468 for (size_t j=r.begin(); j<r.end(); j++)
469 {
470 const GridMesh::Grid &g = mesh->grid(i: j);
471 if (!mesh->valid(gridID: j,itime_range: range<size_t>(0,1))) continue;
472
473 for (unsigned int y=0; y<g.resY-1u; y+=2)
474 for (unsigned int x=0; x<g.resX-1u; x+=2)
475 {
476 BBox3fa bounds = empty;
477 if (!mesh->buildBounds(g,sx: x,sy: y,itime,bbox&: bounds)) continue; // get bounds of subgrid
478 const PrimRef prim(bounds,unsigned(geomID),unsigned(p_index));
479 pinfo.add_center2(prim);
480 sgrids[p_index] = SubGridBuildData(x | g.get3x3FlagsX(x), y | g.get3x3FlagsY(y), unsigned(j));
481 prims[p_index++] = prim;
482 }
483 }
484 return pinfo;
485 }, [](const PrimInfo& a, const PrimInfo& b) -> PrimInfo { return PrimInfo::merge(a,b); });
486
487 assert(pinfo.size() == numPrimitives);
488 return pinfo;
489 }
490
491 PrimInfoMB createPrimRefArrayMSMBlurGrid(Scene* scene, mvector<PrimRefMB>& prims, BuildProgressMonitor& progressMonitor, BBox1f t0t1 = BBox1f(0.0f,1.0f))
492 {
493 /* first run to get #primitives */
494 ParallelForForPrefixSumState<PrimInfoMB> pstate;
495 Scene::Iterator<GridMesh,true> iter(scene);
496
497 pstate.init(array2&: iter,minStepSize: size_t(1024));
498 /* iterate over all meshes in the scene */
499 PrimInfoMB pinfoMB = parallel_for_for_prefix_sum0( pstate, iter, PrimInfoMB(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t /*geomID*/) -> PrimInfoMB {
500
501 PrimInfoMB pinfoMB(empty);
502 for (size_t j=r.begin(); j<r.end(); j++)
503 {
504 if (!mesh->valid(gridID: j, itime_range: mesh->timeSegmentRange(range: t0t1))) continue;
505 LBBox3fa bounds(empty);
506 PrimInfoMB gridMB(0,mesh->getNumSubGrids(gridID: j));
507 pinfoMB.merge(other: gridMB);
508 }
509 return pinfoMB;
510 }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
511
512 size_t numPrimitives = pinfoMB.size();
513 if (numPrimitives == 0) return pinfoMB;
514
515 /* resize arrays */
516 sgrids.resize(new_size: numPrimitives);
517 prims.resize(new_size: numPrimitives);
518 /* second run to fill primrefs and SubGridBuildData arrays */
519 pinfoMB = parallel_for_for_prefix_sum1( pstate, iter, PrimInfoMB(empty), [&](GridMesh* mesh, const range<size_t>& r, size_t k, size_t geomID, const PrimInfoMB& base) -> PrimInfoMB {
520
521 k = base.size();
522 size_t p_index = k;
523 PrimInfoMB pinfoMB(empty);
524 for (size_t j=r.begin(); j<r.end(); j++)
525 {
526 if (!mesh->valid(gridID: j, itime_range: mesh->timeSegmentRange(range: t0t1))) continue;
527 const GridMesh::Grid &g = mesh->grid(i: j);
528
529 for (unsigned int y=0; y<g.resY-1u; y+=2)
530 for (unsigned int x=0; x<g.resX-1u; x+=2)
531 {
532 const PrimRefMB prim(mesh->linearBounds(g,sx: x,sy: y,dt: t0t1),mesh->numTimeSegments(),mesh->time_range,mesh->numTimeSegments(),unsigned(geomID),unsigned(p_index));
533 pinfoMB.add_primref(prim);
534 sgrids[p_index] = SubGridBuildData(x | g.get3x3FlagsX(x), y | g.get3x3FlagsY(y), unsigned(j));
535 prims[p_index++] = prim;
536 }
537 }
538 return pinfoMB;
539 }, [](const PrimInfoMB& a, const PrimInfoMB& b) -> PrimInfoMB { return PrimInfoMB::merge2(a,b); });
540
541 assert(pinfoMB.size() == numPrimitives);
542 pinfoMB.time_range = t0t1;
543 return pinfoMB;
544 }
545
546 void build()
547 {
548 /* skip build for empty scene */
549 const size_t numPrimitives = scene->getNumPrimitives(mask: GridMesh::geom_type,mblur: true);
550 if (numPrimitives == 0) { bvh->clear(); return; }
551
552 double t0 = bvh->preBuild(TOSTRING(isa) "::BVH" + toString(value: N) + "BuilderMBlurSAHGrid");
553
554 //const size_t numTimeSteps = scene->getNumTimeSteps<GridMesh,true>();
555 //const size_t numTimeSegments = numTimeSteps-1; assert(numTimeSteps > 1);
556 //if (numTimeSegments == 1)
557 // buildSingleSegment(numPrimitives);
558 //else
559 buildMultiSegment(numPrimitives);
560
561 /* clear temporary data for static geometry */
562 bvh->cleanup();
563 bvh->postBuild(t0);
564 }
565
566#if 0
567 void buildSingleSegment(size_t numPrimitives)
568 {
569 /* create primref array */
570 mvector<PrimRef> prims(scene->device,numPrimitives);
571 const PrimInfo pinfo = createPrimRefArrayMBlurGrid(scene,prims,bvh->scene->progressInterface,0);
572 /* early out if no valid primitives */
573 if (pinfo.size() == 0) { bvh->clear(); return; }
574
575 /* estimate acceleration structure size */
576 const size_t node_bytes = pinfo.size()*sizeof(AABBNodeMB)/(4*N);
577 //TODO: check leaf_bytes
578 const size_t leaf_bytes = size_t(1.2*(float)numPrimitives/N * sizeof(SubGridQBVHN<N>));
579 bvh->alloc.init_estimate(node_bytes+leaf_bytes);
580
581 /* settings for BVH build */
582 GeneralBVHBuilder::Settings settings;
583 settings.branchingFactor = N;
584 settings.maxDepth = BVH::maxBuildDepthLeaf;
585 settings.logBlockSize = bsr(sahBlockSize);
586 settings.minLeafSize = min(minLeafSize,maxLeafSize);
587 settings.maxLeafSize = maxLeafSize;
588 settings.travCost = travCost;
589 settings.intCost = intCost;
590 settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
591
592 /* build hierarchy */
593 auto root = BVHBuilderBinnedSAH::build<NodeRecordMB>
594 (typename BVH::CreateAlloc(bvh),
595 typename BVH::AABBNodeMB::Create(),
596 typename BVH::AABBNodeMB::Set(),
597 CreateLeafGridMB<N>(scene,bvh,sgrids.data()),
598 bvh->scene->progressInterface,
599 prims.data(),pinfo,settings);
600
601 bvh->set(root.ref,root.lbounds,pinfo.size());
602 }
603#endif
604
605 void buildMultiSegment(size_t numPrimitives)
606 {
607 /* create primref array */
608 mvector<PrimRefMB> prims(scene->device,numPrimitives);
609 PrimInfoMB pinfo = createPrimRefArrayMSMBlurGrid(scene,prims,progressMonitor&: bvh->scene->progressInterface);
610
611 /* early out if no valid primitives */
612 if (pinfo.size() == 0) { bvh->clear(); return; }
613
614
615
616 GridRecalculatePrimRef recalculatePrimRef(scene,sgrids.data());
617
618 /* estimate acceleration structure size */
619 const size_t node_bytes = pinfo.num_time_segments*sizeof(AABBNodeMB)/(4*N);
620 //FIXME: check leaf_bytes
621 //const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.num_time_segments)*sizeof(SubGridQBVHN<N>));
622 const size_t leaf_bytes = size_t(1.2*(float)numPrimitives/N * sizeof(SubGridQBVHN<N>));
623
624 bvh->alloc.init_estimate(node_bytes+leaf_bytes);
625
626 /* settings for BVH build */
627 BVHBuilderMSMBlur::Settings settings;
628 settings.branchingFactor = N;
629 settings.maxDepth = BVH::maxDepth;
630 settings.logBlockSize = bsr(v: sahBlockSize);
631 settings.minLeafSize = min(a: minLeafSize,b: maxLeafSize);
632 settings.maxLeafSize = maxLeafSize;
633 settings.travCost = travCost;
634 settings.intCost = intCost;
635 settings.singleLeafTimeSegment = false;
636 settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
637
638 /* build hierarchy */
639 auto root =
640 BVHBuilderMSMBlur::build<NodeRef>(prims,pinfo,scene->device,
641 recalculatePrimRef,
642 typename BVH::CreateAlloc(bvh),
643 typename BVH::AABBNodeMB4D::Create(),
644 typename BVH::AABBNodeMB4D::Set(),
645 CreateMSMBlurLeafGrid<N>(scene,bvh,sgrids.data()),
646 bvh->scene->progressInterface,
647 settings);
648 bvh->set(root.ref,root.lbounds,pinfo.num_time_segments);
649 }
650
651 void clear() {
652 }
653 };
654
655 /************************************************************************************/
656 /************************************************************************************/
657 /************************************************************************************/
658 /************************************************************************************/
659
660#if defined(EMBREE_GEOMETRY_TRIANGLE)
661 Builder* BVH4Triangle4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<4,TriangleMesh,Triangle4i>((BVH4*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
662 Builder* BVH4Triangle4vMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<4,TriangleMesh,Triangle4vMB>((BVH4*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
663#if defined(__AVX__)
664 Builder* BVH8Triangle4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<8,TriangleMesh,Triangle4i>((BVH8*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
665 Builder* BVH8Triangle4vMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<8,TriangleMesh,Triangle4vMB>((BVH8*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_TRIANGLE_MESH); }
666#endif
667#endif
668
669#if defined(EMBREE_GEOMETRY_QUAD)
670 Builder* BVH4Quad4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<4,QuadMesh,Quad4i>((BVH4*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_QUAD_MESH); }
671#if defined(__AVX__)
672 Builder* BVH8Quad4iMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAH<8,QuadMesh,Quad4i>((BVH8*)bvh,scene,4,1.0f,4,inf,Geometry::MTY_QUAD_MESH); }
673#endif
674#endif
675
676#if defined(EMBREE_GEOMETRY_USER)
677 Builder* BVH4VirtualMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) {
678 int minLeafSize = scene->device->object_accel_mb_min_leaf_size;
679 int maxLeafSize = scene->device->object_accel_mb_max_leaf_size;
680 return new BVHNBuilderMBlurSAH<4,UserGeometry,Object>((BVH4*)bvh,scene,4,1.0f,minLeafSize,maxLeafSize,Geometry::MTY_USER_GEOMETRY);
681 }
682#if defined(__AVX__)
683 Builder* BVH8VirtualMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) {
684 int minLeafSize = scene->device->object_accel_mb_min_leaf_size;
685 int maxLeafSize = scene->device->object_accel_mb_max_leaf_size;
686 return new BVHNBuilderMBlurSAH<8,UserGeometry,Object>((BVH8*)bvh,scene,8,1.0f,minLeafSize,maxLeafSize,Geometry::MTY_USER_GEOMETRY);
687 }
688#endif
689#endif
690
691#if defined(EMBREE_GEOMETRY_INSTANCE)
692 Builder* BVH4InstanceMBSceneBuilderSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype) { return new BVHNBuilderMBlurSAH<4,Instance,InstancePrimitive>((BVH4*)bvh,scene,4,1.0f,1,1,gtype); }
693#if defined(__AVX__)
694 Builder* BVH8InstanceMBSceneBuilderSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype) { return new BVHNBuilderMBlurSAH<8,Instance,InstancePrimitive>((BVH8*)bvh,scene,8,1.0f,1,1,gtype); }
695#endif
696#endif
697
698#if defined(EMBREE_GEOMETRY_GRID)
699 Builder* BVH4GridMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAHGrid<4>((BVH4*)bvh,scene,4,1.0f,4,4); }
700#if defined(__AVX__)
701 Builder* BVH8GridMBSceneBuilderSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderMBlurSAHGrid<8>((BVH8*)bvh,scene,8,1.0f,8,8); }
702#endif
703#endif
704 }
705}
706

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