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 13 namespace embree 14 { 15 namespace isa 16 { 17 template<int N, typename Mesh, typename Primitive> BVHNBuilderTwoLevel(BVH * bvh,Scene * scene,Geometry::GTypeMask gtype,bool useMortonBuilder,const size_t singleThreadThreshold)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> ~BVHNBuilderTwoLevel()22 BVHNBuilderTwoLevel<N,Mesh,Primitive>::~BVHNBuilderTwoLevel () { 23 } 24 25 // =========================================================================== 26 // =========================================================================== 27 // =========================================================================== 28 29 template<int N, typename Mesh, typename Primitive> build()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> deleteGeometry(size_t geomID)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> clear()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> open_sequential(const size_t extSize)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> setupSmallBuildRefBuilder(size_t objectID,Mesh const * const)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> setupLargeBuildRefBuilder(size_t objectID,Mesh const * const mesh)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) BVH4BuilderTwoLevelTriangle4MeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)307 Builder* BVH4BuilderTwoLevelTriangle4MeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) { 308 return new BVHNBuilderTwoLevel<4,TriangleMesh,Triangle4>((BVH4*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder); 309 } BVH4BuilderTwoLevelTriangle4vMeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)310 Builder* BVH4BuilderTwoLevelTriangle4vMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) { 311 return new BVHNBuilderTwoLevel<4,TriangleMesh,Triangle4v>((BVH4*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder); 312 } BVH4BuilderTwoLevelTriangle4iMeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)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) BVH4BuilderTwoLevelQuadMeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)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) BVH4BuilderTwoLevelVirtualSAH(void * bvh,Scene * scene,bool useMortonBuilder)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) BVH4BuilderTwoLevelInstanceSAH(void * bvh,Scene * scene,Geometry::GTypeMask gtype,bool useMortonBuilder)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) BVH8BuilderTwoLevelTriangle4MeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)338 Builder* BVH8BuilderTwoLevelTriangle4MeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) { 339 return new BVHNBuilderTwoLevel<8,TriangleMesh,Triangle4>((BVH8*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder); 340 } BVH8BuilderTwoLevelTriangle4vMeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)341 Builder* BVH8BuilderTwoLevelTriangle4vMeshSAH (void* bvh, Scene* scene, bool useMortonBuilder) { 342 return new BVHNBuilderTwoLevel<8,TriangleMesh,Triangle4v>((BVH8*)bvh,scene,TriangleMesh::geom_type,useMortonBuilder); 343 } BVH8BuilderTwoLevelTriangle4iMeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)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) BVH8BuilderTwoLevelQuadMeshSAH(void * bvh,Scene * scene,bool useMortonBuilder)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) BVH8BuilderTwoLevelVirtualSAH(void * bvh,Scene * scene,bool useMortonBuilder)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) BVH8BuilderTwoLevelInstanceSAH(void * bvh,Scene * scene,Geometry::GTypeMask gtype,bool useMortonBuilder)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