1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "bvh.h"
5#include "bvh_builder.h"
6
7#include "../builders/primrefgen.h"
8#include "../builders/primrefgen_presplit.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
24namespace embree
25{
26 namespace isa
27 {
28 template<int N, typename Primitive>
29 struct CreateLeafSpatial
30 {
31 typedef BVHN<N> BVH;
32 typedef typename BVH::NodeRef NodeRef;
33
34 __forceinline CreateLeafSpatial (BVH* bvh) : bvh(bvh) {}
35
36 __forceinline NodeRef operator() (const PrimRef* prims, const range<size_t>& set, const FastAllocator::CachedAllocator& alloc) const
37 {
38 size_t n = set.size();
39 size_t items = Primitive::blocks(n);
40 size_t start = set.begin();
41 Primitive* accel = (Primitive*) alloc.malloc1(items*sizeof(Primitive),BVH::byteAlignment);
42 typename BVH::NodeRef node = BVH::encodeLeaf((char*)accel,items);
43 for (size_t i=0; i<items; i++) {
44 accel[i].fill(prims,start,set.end(),bvh->scene);
45 }
46 return node;
47 }
48
49 BVH* bvh;
50 };
51
52 template<int N, typename Mesh, typename Primitive, typename Splitter>
53 struct BVHNBuilderFastSpatialSAH : public Builder
54 {
55 typedef BVHN<N> BVH;
56 typedef typename BVH::NodeRef NodeRef;
57 BVH* bvh;
58 Scene* scene;
59 Mesh* mesh;
60 mvector<PrimRef> prims0;
61 GeneralBVHBuilder::Settings settings;
62 const float splitFactor;
63 unsigned int geomID_ = std::numeric_limits<unsigned int>::max();
64 unsigned int numPreviousPrimitives = 0;
65
66 BVHNBuilderFastSpatialSAH (BVH* bvh, Scene* scene, const size_t sahBlockSize, const float intCost, const size_t minLeafSize, const size_t maxLeafSize, const size_t mode)
67 : bvh(bvh), scene(scene), mesh(nullptr), prims0(scene->device,0), settings(sahBlockSize, minLeafSize, min(maxLeafSize,Primitive::max_size()*BVH::maxLeafBlocks), travCost, intCost, DEFAULT_SINGLE_THREAD_THRESHOLD),
68 splitFactor(scene->device->max_spatial_split_replications) {}
69
70 BVHNBuilderFastSpatialSAH (BVH* bvh, Mesh* mesh, const unsigned int geomID, const size_t sahBlockSize, const float intCost, const size_t minLeafSize, const size_t maxLeafSize, const size_t mode)
71 : bvh(bvh), scene(nullptr), mesh(mesh), prims0(bvh->device,0), settings(sahBlockSize, minLeafSize, min(maxLeafSize,Primitive::max_size()*BVH::maxLeafBlocks), travCost, intCost, DEFAULT_SINGLE_THREAD_THRESHOLD),
72 splitFactor(scene->device->max_spatial_split_replications), geomID_(geomID) {}
73
74 // FIXME: shrink bvh->alloc in destructor here and in other builders too
75
76 void build()
77 {
78 /* we reset the allocator when the mesh size changed */
79 if (mesh && mesh->numPrimitives != numPreviousPrimitives) {
80 bvh->alloc.clear();
81 }
82
83 /* skip build for empty scene */
84 const size_t numOriginalPrimitives = mesh ? mesh->size() : scene->getNumPrimitives(Mesh::geom_type,false);
85 numPreviousPrimitives = numOriginalPrimitives;
86 if (numOriginalPrimitives == 0) {
87 prims0.clear();
88 bvh->clear();
89 return;
90 }
91
92 const unsigned int maxGeomID = mesh ? geomID_ : scene->getMaxGeomID<Mesh,false>();
93 const bool usePreSplits = scene->device->useSpatialPreSplits || (maxGeomID >= ((unsigned int)1 << (32-RESERVED_NUM_SPATIAL_SPLITS_GEOMID_BITS)));
94 double t0 = bvh->preBuild(mesh ? "" : TOSTRING(isa) "::BVH" + toString(N) + (usePreSplits ? "BuilderFastSpatialPresplitSAH" : "BuilderFastSpatialSAH"));
95
96 /* create primref array */
97 const size_t numSplitPrimitives = max(numOriginalPrimitives,size_t(splitFactor*numOriginalPrimitives));
98 prims0.resize(numSplitPrimitives);
99
100 /* enable os_malloc for two level build */
101 if (mesh)
102 bvh->alloc.setOSallocation(true);
103
104 NodeRef root(0);
105 PrimInfo pinfo;
106
107
108 if (likely(usePreSplits))
109 {
110 /* spatial presplit SAH BVH builder */
111 pinfo = mesh ?
112 createPrimRefArray_presplit<Mesh,Splitter>(mesh,maxGeomID,numOriginalPrimitives,prims0,bvh->scene->progressInterface) :
113 createPrimRefArray_presplit<Mesh,Splitter>(scene,Mesh::geom_type,false,numOriginalPrimitives,prims0,bvh->scene->progressInterface);
114
115 const size_t node_bytes = pinfo.size()*sizeof(typename BVH::AABBNode)/(4*N);
116 const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.size())*sizeof(Primitive));
117 bvh->alloc.init_estimate(node_bytes+leaf_bytes);
118 settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
119
120 settings.branchingFactor = N;
121 settings.maxDepth = BVH::maxBuildDepthLeaf;
122
123 /* call BVH builder */
124 root = BVHNBuilderVirtual<N>::build(&bvh->alloc,CreateLeafSpatial<N,Primitive>(bvh),bvh->scene->progressInterface,prims0.data(),pinfo,settings);
125 }
126 else
127 {
128 /* standard spatial split SAH BVH builder */
129 pinfo = mesh ?
130 createPrimRefArray(mesh,geomID_,numSplitPrimitives,prims0,bvh->scene->progressInterface) :
131 createPrimRefArray(scene,Mesh::geom_type,false,numSplitPrimitives,prims0,bvh->scene->progressInterface);
132
133 Splitter splitter(scene);
134
135 const size_t node_bytes = pinfo.size()*sizeof(typename BVH::AABBNode)/(4*N);
136 const size_t leaf_bytes = size_t(1.2*Primitive::blocks(pinfo.size())*sizeof(Primitive));
137 bvh->alloc.init_estimate(node_bytes+leaf_bytes);
138 settings.singleThreadThreshold = bvh->alloc.fixSingleThreadThreshold(N,DEFAULT_SINGLE_THREAD_THRESHOLD,pinfo.size(),node_bytes+leaf_bytes);
139
140 settings.branchingFactor = N;
141 settings.maxDepth = BVH::maxBuildDepthLeaf;
142
143 /* call BVH builder */
144 root = BVHBuilderBinnedFastSpatialSAH::build<NodeRef>(
145 typename BVH::CreateAlloc(bvh),
146 typename BVH::AABBNode::Create2(),
147 typename BVH::AABBNode::Set2(),
148 CreateLeafSpatial<N,Primitive>(bvh),
149 splitter,
150 bvh->scene->progressInterface,
151 prims0.data(),
152 numSplitPrimitives,
153 pinfo,settings);
154
155 /* ==================== */
156 }
157
158 bvh->set(root,LBBox3fa(pinfo.geomBounds),pinfo.size());
159 bvh->layoutLargeNodes(size_t(pinfo.size()*0.005f));
160
161 /* clear temporary data for static geometry */
162 if (scene && scene->isStaticAccel()) {
163 prims0.clear();
164 }
165 bvh->cleanup();
166 bvh->postBuild(t0);
167 }
168
169 void clear() {
170 prims0.clear();
171 }
172 };
173
174 /************************************************************************************/
175 /************************************************************************************/
176 /************************************************************************************/
177 /************************************************************************************/
178
179
180#if defined(EMBREE_GEOMETRY_TRIANGLE)
181
182 Builder* BVH4Triangle4SceneBuilderFastSpatialSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderFastSpatialSAH<4,TriangleMesh,Triangle4,TriangleSplitterFactory>((BVH4*)bvh,scene,4,1.0f,4,inf,mode); }
183 Builder* BVH4Triangle4vSceneBuilderFastSpatialSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderFastSpatialSAH<4,TriangleMesh,Triangle4v,TriangleSplitterFactory>((BVH4*)bvh,scene,4,1.0f,4,inf,mode); }
184 Builder* BVH4Triangle4iSceneBuilderFastSpatialSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderFastSpatialSAH<4,TriangleMesh,Triangle4i,TriangleSplitterFactory>((BVH4*)bvh,scene,4,1.0f,4,inf,mode); }
185
186#if defined(__AVX__)
187 Builder* BVH8Triangle4SceneBuilderFastSpatialSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderFastSpatialSAH<8,TriangleMesh,Triangle4,TriangleSplitterFactory>((BVH8*)bvh,scene,4,1.0f,4,inf,mode); }
188 Builder* BVH8Triangle4vSceneBuilderFastSpatialSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderFastSpatialSAH<8,TriangleMesh,Triangle4v,TriangleSplitterFactory>((BVH8*)bvh,scene,4,1.0f,4,inf,mode); }
189#endif
190#endif
191
192#if defined(EMBREE_GEOMETRY_QUAD)
193 Builder* BVH4Quad4vSceneBuilderFastSpatialSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderFastSpatialSAH<4,QuadMesh,Quad4v,QuadSplitterFactory>((BVH4*)bvh,scene,4,1.0f,4,inf,mode); }
194
195#if defined(__AVX__)
196 Builder* BVH8Quad4vSceneBuilderFastSpatialSAH (void* bvh, Scene* scene, size_t mode) { return new BVHNBuilderFastSpatialSAH<8,QuadMesh,Quad4v,QuadSplitterFactory>((BVH8*)bvh,scene,4,1.0f,4,inf,mode); }
197#endif
198
199#endif
200 }
201}
202