1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6#include <type_traits>
7
8#include "bvh_builder_twolevel_internal.h"
9#include "bvh.h"
10#include "../common/primref.h"
11#include "../builders/priminfo.h"
12#include "../builders/primrefgen.h"
13
14/* new open/merge builder */
15#define ENABLE_DIRECT_SAH_MERGE_BUILDER 1
16#define ENABLE_OPEN_SEQUENTIAL 0
17#define SPLIT_MEMORY_RESERVE_FACTOR 1000
18#define SPLIT_MEMORY_RESERVE_SCALE 2
19#define SPLIT_MIN_EXT_SPACE 1000
20
21namespace embree
22{
23 namespace isa
24 {
25 template<int N, typename Mesh, typename Primitive>
26 class BVHNBuilderTwoLevel : public Builder
27 {
28 typedef BVHN<N> BVH;
29 typedef typename BVH::AABBNode AABBNode;
30 typedef typename BVH::NodeRef NodeRef;
31
32 __forceinline static bool isSmallGeometry(Mesh* mesh) {
33 return mesh->size() <= 4;
34 }
35
36 public:
37
38 typedef void (*createMeshAccelTy)(Scene* scene, unsigned int geomID, AccelData*& accel, Builder*& builder);
39
40 struct BuildRef : public PrimRef
41 {
42 public:
43 __forceinline BuildRef () {}
44
45 __forceinline BuildRef (const BBox3fa& bounds, NodeRef node)
46 : PrimRef(bounds,(size_t)node), node(node)
47 {
48 if (node.isLeaf())
49 bounds_area = 0.0f;
50 else
51 bounds_area = area(this->bounds());
52 }
53
54 /* used by the open/merge bvh builder */
55 __forceinline BuildRef (const BBox3fa& bounds, NodeRef node, const unsigned int geomID, const unsigned int numPrimitives)
56 : PrimRef(bounds,geomID,numPrimitives), node(node)
57 {
58 /* important for relative buildref ordering */
59 if (node.isLeaf())
60 bounds_area = 0.0f;
61 else
62 bounds_area = area(this->bounds());
63 }
64
65 __forceinline size_t size() const {
66 return primID();
67 }
68
69 friend bool operator< (const BuildRef& a, const BuildRef& b) {
70 return a.bounds_area < b.bounds_area;
71 }
72
73 friend __forceinline embree_ostream operator<<(embree_ostream cout, const BuildRef& ref) {
74 return cout << "{ lower = " << ref.lower << ", upper = " << ref.upper << ", center2 = " << ref.center2() << ", geomID = " << ref.geomID() << ", numPrimitives = " << ref.numPrimitives() << ", bounds_area = " << ref.bounds_area << " }";
75 }
76
77 __forceinline unsigned int numPrimitives() const { return primID(); }
78
79 public:
80 NodeRef node;
81 float bounds_area;
82 };
83
84
85 __forceinline size_t openBuildRef(BuildRef &bref, BuildRef *const refs) {
86 if (bref.node.isLeaf())
87 {
88 refs[0] = bref;
89 return 1;
90 }
91 NodeRef ref = bref.node;
92 unsigned int geomID = bref.geomID();
93 unsigned int numPrims = max(a: (unsigned int)bref.numPrimitives() / N,b: (unsigned int)1);
94 AABBNode* node = ref.getAABBNode();
95 size_t n = 0;
96 for (size_t i=0; i<N; i++) {
97 if (node->child(i) == BVH::emptyNode) continue;
98 refs[i] = BuildRef(node->bounds(i),node->child(i),geomID,numPrims);
99 n++;
100 }
101 assert(n > 1);
102 return n;
103 }
104
105 /*! Constructor. */
106 BVHNBuilderTwoLevel (BVH* bvh, Scene* scene, Geometry::GTypeMask gtype = Mesh::geom_type, bool useMortonBuilder = false, const size_t singleThreadThreshold = DEFAULT_SINGLE_THREAD_THRESHOLD);
107
108 /*! Destructor */
109 ~BVHNBuilderTwoLevel ();
110
111 /*! builder entry point */
112 void build();
113 void deleteGeometry(size_t geomID);
114 void clear();
115
116 void open_sequential(const size_t extSize);
117
118 private:
119
120 class RefBuilderBase {
121 public:
122 virtual ~RefBuilderBase () {}
123 virtual void attachBuildRefs (BVHNBuilderTwoLevel* builder) = 0;
124 virtual bool meshQualityChanged (RTCBuildQuality currQuality) = 0;
125 };
126
127 class RefBuilderSmall : public RefBuilderBase {
128 public:
129
130 RefBuilderSmall (size_t objectID)
131 : objectID_ (objectID) {}
132
133 void attachBuildRefs (BVHNBuilderTwoLevel* topBuilder) {
134
135 Mesh* mesh = topBuilder->scene->template getSafe<Mesh>(objectID_);
136 size_t meshSize = mesh->size();
137 assert(isSmallGeometry(mesh));
138
139 mvector<PrimRef> prefs(topBuilder->scene->device, meshSize);
140 auto pinfo = createPrimRefArray(mesh,objectID_,meshSize,prefs,topBuilder->bvh->scene->progressInterface);
141
142 size_t begin=0;
143 while (begin < pinfo.size())
144 {
145 Primitive* accel = (Primitive*) topBuilder->bvh->alloc.getCachedAllocator().malloc1(sizeof(Primitive),BVH::byteAlignment);
146 typename BVH::NodeRef node = BVH::encodeLeaf((char*)accel,1);
147 accel->fill(prefs.data(),begin,pinfo.size(),topBuilder->bvh->scene);
148
149 /* create build primitive */
150#if ENABLE_DIRECT_SAH_MERGE_BUILDER
151 topBuilder->refs[topBuilder->nextRef++] = BVHNBuilderTwoLevel::BuildRef(pinfo.geomBounds,node,(unsigned int)objectID_,1);
152#else
153 topBuilder->refs[topBuilder->nextRef++] = BVHNBuilderTwoLevel::BuildRef(pinfo.geomBounds,node);
154#endif
155 }
156 assert(begin == pinfo.size());
157 }
158
159 bool meshQualityChanged (RTCBuildQuality /*currQuality*/) {
160 return false;
161 }
162
163 size_t objectID_;
164 };
165
166 class RefBuilderLarge : public RefBuilderBase {
167 public:
168
169 RefBuilderLarge (size_t objectID, const Ref<Builder>& builder, RTCBuildQuality quality)
170 : objectID_ (objectID), builder_ (builder), quality_ (quality) {}
171
172 void attachBuildRefs (BVHNBuilderTwoLevel* topBuilder)
173 {
174 BVH* object = topBuilder->getBVH(objectID_); assert(object);
175
176 /* build object if it got modified */
177 if (topBuilder->isGeometryModified(objectID_))
178 builder_->build();
179
180 /* create build primitive */
181 if (!object->getBounds().empty())
182 {
183#if ENABLE_DIRECT_SAH_MERGE_BUILDER
184 Mesh* mesh = topBuilder->getMesh(objectID_);
185 topBuilder->refs[topBuilder->nextRef++] = BVHNBuilderTwoLevel::BuildRef(object->getBounds(),object->root,(unsigned int)objectID_,(unsigned int)mesh->size());
186#else
187 topBuilder->refs[topBuilder->nextRef++] = BVHNBuilderTwoLevel::BuildRef(object->getBounds(),object->root);
188#endif
189 }
190 }
191
192 bool meshQualityChanged (RTCBuildQuality currQuality) {
193 return currQuality != quality_;
194 }
195
196 private:
197 size_t objectID_;
198 Ref<Builder> builder_;
199 RTCBuildQuality quality_;
200 };
201
202 void setupLargeBuildRefBuilder (size_t objectID, Mesh const * const mesh);
203 void setupSmallBuildRefBuilder (size_t objectID, Mesh const * const mesh);
204
205 BVH* getBVH (size_t objectID) {
206 return this->bvh->objects[objectID];
207 }
208 Mesh* getMesh (size_t objectID) {
209 return this->scene->template getSafe<Mesh>(objectID);
210 }
211 bool isGeometryModified (size_t objectID) {
212 return this->scene->isGeometryModified(objectID);
213 }
214
215 void resizeRefsList ()
216 {
217 size_t num = parallel_reduce (size_t(0), scene->size(), size_t(0),
218 [this](const range<size_t>& r)->size_t {
219 size_t c = 0;
220 for (auto i=r.begin(); i<r.end(); ++i) {
221 Mesh* mesh = scene->getSafe<Mesh>(i);
222 if (mesh == nullptr || mesh->numTimeSteps != 1)
223 continue;
224 size_t meshSize = mesh->size();
225 c += isSmallGeometry(mesh) ? Primitive::blocks(meshSize) : 1;
226 }
227 return c;
228 },
229 std::plus<size_t>()
230 );
231
232 if (refs.size() < num) {
233 refs.resize(num);
234 }
235 }
236
237 void createMeshAccel (size_t geomID, Builder*& builder)
238 {
239 bvh->objects[geomID] = new BVH(Primitive::type,scene);
240 BVH* accel = bvh->objects[geomID];
241 auto mesh = scene->getSafe<Mesh>(geomID);
242 if (nullptr == mesh) {
243 throw_RTCError(RTC_ERROR_INVALID_ARGUMENT,"geomID does not return correct type");
244 return;
245 }
246
247 __internal_two_level_builder__::MeshBuilder<N,Mesh,Primitive>()(accel, mesh, geomID, this->gtype, this->useMortonBuilder_, builder);
248 }
249
250 using BuilderList = std::vector<std::unique_ptr<RefBuilderBase>>;
251
252 BuilderList builders;
253 BVH* bvh;
254 Scene* scene;
255 mvector<BuildRef> refs;
256 mvector<PrimRef> prims;
257 std::atomic<int> nextRef;
258 const size_t singleThreadThreshold;
259 Geometry::GTypeMask gtype;
260 bool useMortonBuilder_ = false;
261 };
262 }
263}
264

source code of qtquick3d/src/3rdparty/embree/kernels/bvh/bvh_builder_twolevel.h