1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "bvh_builder_twolevel.h"
5#include "bvh_statistics.h"
6#include "../builders/bvh_builder_sah.h"
7#include "../common/scene_line_segments.h"
8#include "../common/scene_triangle_mesh.h"
9#include "../common/scene_quad_mesh.h"
10
11#define PROFILE 0
12
13namespace embree
14{
15 namespace isa
16 {
17 template<int N, typename Mesh, typename Primitive>
18 BVHNBuilderTwoLevel<N,Mesh,Primitive>::BVHNBuilderTwoLevel (BVH* bvh, Scene* scene, Geometry::GTypeMask gtype, bool useMortonBuilder, const size_t singleThreadThreshold)
19 : bvh(bvh), scene(scene), refs(scene->device,0), prims(scene->device,0), singleThreadThreshold(singleThreadThreshold), gtype(gtype), useMortonBuilder_(useMortonBuilder) {}
20
21 template<int N, typename Mesh, typename Primitive>
22 BVHNBuilderTwoLevel<N,Mesh,Primitive>::~BVHNBuilderTwoLevel () {
23 }
24
25 // ===========================================================================
26 // ===========================================================================
27 // ===========================================================================
28
29 template<int N, typename Mesh, typename Primitive>
30 void BVHNBuilderTwoLevel<N,Mesh,Primitive>::build()
31 {
32 /* delete some objects */
33 size_t num = scene->size();
34 if (num < bvh->objects.size()) {
35 parallel_for(num, bvh->objects.size(), [&] (const range<size_t>& r) {
36 for (size_t i=r.begin(); i<r.end(); i++) {
37 builders[i].reset();
38 delete bvh->objects[i]; bvh->objects[i] = nullptr;
39 }
40 });
41 }
42
43#if PROFILE
44 while(1)
45#endif
46 {
47 /* reset memory allocator */
48 bvh->alloc.reset();
49
50 /* skip build for empty scene */
51 const size_t numPrimitives = scene->getNumPrimitives(gtype,false);
52
53 if (numPrimitives == 0) {
54 prims.resize(0);
55 bvh->set(BVH::emptyNode,empty,0);
56 return;
57 }
58
59 /* calculate the size of the entire BVH */
60 const size_t numLeafBlocks = Primitive::blocks(numPrimitives);
61 const size_t node_bytes = 2*numLeafBlocks*sizeof(typename BVH::AABBNode)/N;
62 const size_t leaf_bytes = size_t(1.2*numLeafBlocks*sizeof(Primitive));
63 bvh->alloc.init_estimate(node_bytes+leaf_bytes);
64
65 double t0 = bvh->preBuild(TOSTRING(isa) "::BVH" + toString(N) + "BuilderTwoLevel");
66
67 /* resize object array if scene got larger */
68 if (bvh->objects.size() < num) bvh->objects.resize(num);
69 if (builders.size() < num) builders.resize(num);
70 resizeRefsList ();
71 nextRef.store(0);
72
73 /* create acceleration structures */
74 parallel_for(size_t(0), num, [&] (const range<size_t>& r)
75 {
76 for (size_t objectID=r.begin(); objectID<r.end(); objectID++)
77 {
78 Mesh* mesh = scene->getSafe<Mesh>(objectID);
79
80 /* ignore meshes we do not support */
81 if (mesh == nullptr || mesh->numTimeSteps != 1)
82 continue;
83
84 if (isSmallGeometry(mesh)) {
85 setupSmallBuildRefBuilder (objectID, mesh);
86 } else {
87 setupLargeBuildRefBuilder (objectID, mesh);
88 }
89 }
90 });
91
92 /* parallel build of acceleration structures */
93 parallel_for(size_t(0), num, [&] (const range<size_t>& r)
94 {
95 for (size_t objectID=r.begin(); objectID<r.end(); objectID++)
96 {
97 /* ignore if no triangle mesh or not enabled */
98 Mesh* mesh = scene->getSafe<Mesh>(objectID);
99 if (mesh == nullptr || !mesh->isEnabled() || mesh->numTimeSteps != 1)
100 continue;
101
102 builders[objectID]->attachBuildRefs (this);
103 }
104 });
105
106
107#if PROFILE
108 double d0 = getSeconds();
109#endif
110 /* fast path for single geometry scenes */
111 if (nextRef == 1) {
112 bvh->set(refs[0].node,LBBox3fa(refs[0].bounds()),numPrimitives);
113 }
114
115 else
116 {
117 /* open all large nodes */
118 refs.resize(nextRef);
119
120 /* this probably needs some more tuning */
121 const size_t extSize = max(max((size_t)SPLIT_MIN_EXT_SPACE,refs.size()*SPLIT_MEMORY_RESERVE_SCALE),size_t((float)numPrimitives / SPLIT_MEMORY_RESERVE_FACTOR));
122
123#if !ENABLE_DIRECT_SAH_MERGE_BUILDER
124
125#if ENABLE_OPEN_SEQUENTIAL
126 open_sequential(extSize);
127#endif
128 /* compute PrimRefs */
129 prims.resize(refs.size());
130#endif
131
132 {
133#if ENABLE_DIRECT_SAH_MERGE_BUILDER
134
135 const PrimInfo pinfo = parallel_reduce(size_t(0), refs.size(), PrimInfo(empty), [&] (const range<size_t>& r) -> PrimInfo {
136
137 PrimInfo pinfo(empty);
138 for (size_t i=r.begin(); i<r.end(); i++) {
139 pinfo.add_center2(refs[i]);
140 }
141 return pinfo;
142 }, [] (const PrimInfo& a, const PrimInfo& b) { return PrimInfo::merge(a,b); });
143
144#else
145 const PrimInfo pinfo = parallel_reduce(size_t(0), refs.size(), PrimInfo(empty), [&] (const range<size_t>& r) -> PrimInfo {
146
147 PrimInfo pinfo(empty);
148 for (size_t i=r.begin(); i<r.end(); i++) {
149 pinfo.add_center2(refs[i]);
150 prims[i] = PrimRef(refs[i].bounds(),(size_t)refs[i].node);
151 }
152 return pinfo;
153 }, [] (const PrimInfo& a, const PrimInfo& b) { return PrimInfo::merge(a,b); });
154#endif
155
156 /* skip if all objects where empty */
157 if (pinfo.size() == 0)
158 bvh->set(BVH::emptyNode,empty,0);
159
160 /* otherwise build toplevel hierarchy */
161 else
162 {
163 /* settings for BVH build */
164 GeneralBVHBuilder::Settings settings;
165 settings.branchingFactor = N;
166 settings.maxDepth = BVH::maxBuildDepthLeaf;
167 settings.logBlockSize = bsr(N);
168 settings.minLeafSize = 1;
169 settings.maxLeafSize = 1;
170 settings.travCost = 1.0f;
171 settings.intCost = 1.0f;
172 settings.singleThreadThreshold = singleThreadThreshold;
173
174#if ENABLE_DIRECT_SAH_MERGE_BUILDER
175
176 refs.resize(extSize);
177
178 NodeRef root = BVHBuilderBinnedOpenMergeSAH::build<NodeRef,BuildRef>(
179 typename BVH::CreateAlloc(bvh),
180 typename BVH::AABBNode::Create2(),
181 typename BVH::AABBNode::Set2(),
182
183 [&] (const BuildRef* refs, const range<size_t>& range, const FastAllocator::CachedAllocator& alloc) -> NodeRef {
184 assert(range.size() == 1);
185 return (NodeRef) refs[range.begin()].node;
186 },
187 [&] (BuildRef &bref, BuildRef *refs) -> size_t {
188 return openBuildRef(bref,refs);
189 },
190 [&] (size_t dn) { bvh->scene->progressMonitor(0); },
191 refs.data(),extSize,pinfo,settings);
192#else
193 NodeRef root = BVHBuilderBinnedSAH::build<NodeRef>(
194 typename BVH::CreateAlloc(bvh),
195 typename BVH::AABBNode::Create2(),
196 typename BVH::AABBNode::Set2(),
197
198 [&] (const PrimRef* prims, const range<size_t>& range, const FastAllocator::CachedAllocator& alloc) -> NodeRef {
199 assert(range.size() == 1);
200 return (NodeRef) prims[range.begin()].ID();
201 },
202 [&] (size_t dn) { bvh->scene->progressMonitor(0); },
203 prims.data(),pinfo,settings);
204#endif
205
206
207 bvh->set(root,LBBox3fa(pinfo.geomBounds),numPrimitives);
208 }
209 }
210 }
211
212 bvh->alloc.cleanup();
213 bvh->postBuild(t0);
214#if PROFILE
215 double d1 = getSeconds();
216 std::cout << "TOP_LEVEL OPENING/REBUILD TIME " << 1000.0*(d1-d0) << " ms" << std::endl;
217#endif
218 }
219
220 }
221
222 template<int N, typename Mesh, typename Primitive>
223 void BVHNBuilderTwoLevel<N,Mesh,Primitive>::deleteGeometry(size_t geomID)
224 {
225 if (geomID >= bvh->objects.size()) return;
226 if (builders[geomID]) builders[geomID].reset();
227 delete bvh->objects [geomID]; bvh->objects [geomID] = nullptr;
228 }
229
230 template<int N, typename Mesh, typename Primitive>
231 void BVHNBuilderTwoLevel<N,Mesh,Primitive>::clear()
232 {
233 for (size_t i=0; i<bvh->objects.size(); i++)
234 if (bvh->objects[i]) bvh->objects[i]->clear();
235
236 for (size_t i=0; i<builders.size(); i++)
237 if (builders[i]) builders[i].reset();
238
239 refs.clear();
240 }
241
242 template<int N, typename Mesh, typename Primitive>
243 void BVHNBuilderTwoLevel<N,Mesh,Primitive>::open_sequential(const size_t extSize)
244 {
245 if (refs.size() == 0)
246 return;
247
248 refs.reserve(extSize);
249
250#if 1
251 for (size_t i=0;i<refs.size();i++)
252 {
253 NodeRef ref = refs[i].node;
254 if (ref.isAABBNode())
255 BVH::prefetch(ref);
256 }
257#endif
258
259 std::make_heap(refs.begin(),refs.end());
260 while (refs.size()+N-1 <= extSize)
261 {
262 std::pop_heap (refs.begin(),refs.end());
263 NodeRef ref = refs.back().node;
264 if (ref.isLeaf()) break;
265 refs.pop_back();
266
267 AABBNode* node = ref.getAABBNode();
268 for (size_t i=0; i<N; i++) {
269 if (node->child(i) == BVH::emptyNode) continue;
270 refs.push_back(BuildRef(node->bounds(i),node->child(i)));
271
272#if 1
273 NodeRef ref_pre = node->child(i);
274 if (ref_pre.isAABBNode())
275 ref_pre.prefetch();
276#endif
277 std::push_heap (refs.begin(),refs.end());
278 }
279 }
280 }
281
282 template<int N, typename Mesh, typename Primitive>
283 void BVHNBuilderTwoLevel<N,Mesh,Primitive>::setupSmallBuildRefBuilder (size_t objectID, Mesh const * const /*mesh*/)
284 {
285 if (builders[objectID] == nullptr || // new mesh
286 dynamic_cast<RefBuilderSmall*>(builders[objectID].get()) == nullptr) // size change resulted in large->small change
287 {
288 builders[objectID].reset (new RefBuilderSmall(objectID));
289 }
290 }
291
292 template<int N, typename Mesh, typename Primitive>
293 void BVHNBuilderTwoLevel<N,Mesh,Primitive>::setupLargeBuildRefBuilder (size_t objectID, Mesh const * const mesh)
294 {
295 if (bvh->objects[objectID] == nullptr || // new mesh
296 builders[objectID]->meshQualityChanged (mesh->quality) || // changed build quality
297 dynamic_cast<RefBuilderLarge*>(builders[objectID].get()) == nullptr) // size change resulted in small->large change
298 {
299 Builder* builder = nullptr;
300 delete bvh->objects[objectID];
301 createMeshAccel(objectID, builder);
302 builders[objectID].reset (new RefBuilderLarge(objectID, builder, mesh->quality));
303 }
304 }
305
306#if defined(EMBREE_GEOMETRY_TRIANGLE)
307 Builder* BVH4BuilderTwoLevelTriangle4MeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
308 return new BVHNBuilderTwoLevel<4,TriangleMesh,Triangle4>((BVH4*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder);
309 }
310 Builder* BVH4BuilderTwoLevelTriangle4vMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
311 return new BVHNBuilderTwoLevel<4,TriangleMesh,Triangle4v>((BVH4*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder);
312 }
313 Builder* BVH4BuilderTwoLevelTriangle4iMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
314 return new BVHNBuilderTwoLevel<4,TriangleMesh,Triangle4i>((BVH4*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder);
315 }
316#endif
317
318#if defined(EMBREE_GEOMETRY_QUAD)
319 Builder* BVH4BuilderTwoLevelQuadMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
320 return new BVHNBuilderTwoLevel<4,QuadMesh,Quad4v>((BVH4*)bvh,scene,QuadMesh::geom_type,useMortonBuilder);
321 }
322#endif
323
324#if defined(EMBREE_GEOMETRY_USER)
325 Builder* BVH4BuilderTwoLevelVirtualSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
326 return new BVHNBuilderTwoLevel<4,UserGeometry,Object>((BVH4*)bvh,scene,UserGeometry::geom_type,useMortonBuilder);
327 }
328#endif
329
330#if defined(EMBREE_GEOMETRY_INSTANCE)
331 Builder* BVH4BuilderTwoLevelInstanceSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype, bool useMortonBuilder) {
332 return new BVHNBuilderTwoLevel<4,Instance,InstancePrimitive>((BVH4*)bvh,scene,gtype,useMortonBuilder);
333 }
334#endif
335
336#if defined(__AVX__)
337#if defined(EMBREE_GEOMETRY_TRIANGLE)
338 Builder* BVH8BuilderTwoLevelTriangle4MeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
339 return new BVHNBuilderTwoLevel<8,TriangleMesh,Triangle4>((BVH8*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder);
340 }
341 Builder* BVH8BuilderTwoLevelTriangle4vMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
342 return new BVHNBuilderTwoLevel<8,TriangleMesh,Triangle4v>((BVH8*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder);
343 }
344 Builder* BVH8BuilderTwoLevelTriangle4iMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
345 return new BVHNBuilderTwoLevel<8,TriangleMesh,Triangle4i>((BVH8*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder);
346 }
347#endif
348
349#if defined(EMBREE_GEOMETRY_QUAD)
350 Builder* BVH8BuilderTwoLevelQuadMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
351 return new BVHNBuilderTwoLevel<8,QuadMesh,Quad4v>((BVH8*)bvh,scene,QuadMesh::geom_type,useMortonBuilder);
352 }
353#endif
354
355#if defined(EMBREE_GEOMETRY_USER)
356 Builder* BVH8BuilderTwoLevelVirtualSAH (void* bvh, Scene* scene, bool useMortonBuilder) {
357 return new BVHNBuilderTwoLevel<8,UserGeometry,Object>((BVH8*)bvh,scene,UserGeometry::geom_type,useMortonBuilder);
358 }
359#endif
360
361#if defined(EMBREE_GEOMETRY_INSTANCE)
362 Builder* BVH8BuilderTwoLevelInstanceSAH (void* bvh, Scene* scene, Geometry::GTypeMask gtype, bool useMortonBuilder) {
363 return new BVHNBuilderTwoLevel<8,Instance,InstancePrimitive>((BVH8*)bvh,scene,gtype,useMortonBuilder);
364 }
365#endif
366
367#endif
368 }
369}
370