Nebula
Loading...
Searching...
No Matches
bvh.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
16//------------------------------------------------------------------------------
17#include "math/bbox.h"
18#include "math/line.h"
19
20namespace Util
21{
22
23class Bvh
24{
25public:
26 ~Bvh();
27
29 void Build(Math::bbox* bboxes, uint32_t numBoxes);
30
33
34//private:
35 class Node
36 {
37 public:
38 float CalculateCost() const
39 {
40 return this->count * this->bbox.area();
41 }
42
43 bool IsLeaf() const
44 {
45 return count > 0;
46 }
47
48 //private:
49 friend Bvh;
53 uint32_t index = -1;
55 uint32_t count;
56 };
57
58 void UpdateNodeBounds(Bvh::Node* node, Math::bbox* bboxes);
59 void Subdivide(Bvh::Node* node, Math::bbox* bboxes);
60 float FindBestSplitPlane(Bvh::Node* node, Math::bbox* bboxes, int& axis, float& splitPos);
61
62 void Clear();
63
64 Bvh::Node* nodes = nullptr;
66 uint32_t* externalIndices = nullptr;
67 uint32_t rootNodeIndex = 0;
68 uint32_t numNodes = 0;
69 uint32_t nodesUsed = 0;
70};
71
72//------------------------------------------------------------------------------
75inline Bvh::~Bvh()
76{
77 this->Clear();
78}
79
80//------------------------------------------------------------------------------
83inline void
84Bvh::Build(Math::bbox* bboxes, uint32_t numBoxes)
85{
86 this->Clear();
87
88 this->numNodes = numBoxes * 2 - 1;
89 this->nodes = new Bvh::Node[numBoxes * 2 - 1];
90 this->nodesUsed = 1;
91 this->externalIndices = new uint32_t[numBoxes];
92 for (uint32_t i = 0; i < numBoxes; i++)
93 this->externalIndices[i] = i;
94
95 Bvh::Node& root = this->nodes[this->rootNodeIndex];
96 root.index = 0;
97 root.count = numBoxes;
98 this->UpdateNodeBounds(&root, bboxes);
99 // subdivide recursively
100 this->Subdivide(&root, bboxes);
101}
102
103//------------------------------------------------------------------------------
108{
110
112
113 Bvh::Node* node = this->nodes;
114 Bvh::Node* stack[64];
115 uint stackPtr = 0;
116 while (true)
117 {
118 if (node->IsLeaf())
119 {
120 // We've got an intersection!
121 for (uint32_t i = 0; i < node->count; i++)
122 {
123 ret.Append(this->externalIndices[node->index + i]);
124 }
125
126 if (stackPtr == 0)
127 break;
128 else
129 node = stack[--stackPtr];
130
131 continue;
132 }
133 Bvh::Node* child1 = &this->nodes[node->index];
134 Bvh::Node* child2 = &this->nodes[node->index + 1];
135 float dist1;
136 float dist2;
137
138 child1->bbox.intersects(line, dist1);
139 child2->bbox.intersects(line, dist2);
140
141 if (dist1 > dist2)
142 {
143 std::swap(dist1, dist2);
144 std::swap(child1, child2);
145 }
146 if (dist1 >= 1e30f)
147 {
148 if (stackPtr == 0)
149 {
150 break;
151 }
152 else
153 {
154 node = stack[--stackPtr];
155 }
156 }
157 else
158 {
159 node = child1;
160 if (dist2 < 1e30f)
161 {
162 stack[stackPtr++] = child2;
163 }
164 }
165 }
166
167 return ret;
168}
169
170//------------------------------------------------------------------------------
173inline void
175{
176 node->bbox.begin_extend();
177 uint32_t const end = node->index + node->count;
178 for (uint32_t i = node->index; i < end; i++)
179 {
180 uint32_t index = this->externalIndices[i];
181 Math::bbox const& leafBBox = bboxes[index];
182 node->bbox.extend(leafBBox);
183 }
184 node->bbox.end_extend();
185}
186
187//------------------------------------------------------------------------------
190inline void
192{
193 if (node->count <= 2)
194 return;
195
196 // calculate splitting plane
197 int axis;
198 float splitPos;
199 float const splitCost = FindBestSplitPlane(node, bboxes, axis, splitPos);
200 float const nosplitCost = node->CalculateCost();
201 if (splitCost >= nosplitCost)
202 return;
203
204 // split group into two halves
205 // just swap elements to be to the left or right of a split in the aabb array
206 int i = node->index;
207 int j = i + node->count - 1;
208 while (i <= j)
209 {
210 uint32_t const idx = this->externalIndices[i];
211 float center = (bboxes[idx].pmin[axis] + bboxes[idx].pmax[axis]) * 0.5f;
212 if (center < splitPos)
213 i++;
214 else
215 std::swap(this->externalIndices[i], this->externalIndices[j--]);
216 }
217
218 int leftCount = i - node->index;
219 if (leftCount == 0 || leftCount == node->count)
220 return;
221 // create child nodes
222 int leftChildIdx = this->nodesUsed++;
223 int rightChildIdx = this->nodesUsed++;
224 this->nodes[leftChildIdx].index = node->index;
225 this->nodes[leftChildIdx].count = leftCount;
226 this->nodes[rightChildIdx].index = i;
227 this->nodes[rightChildIdx].count = node->count - leftCount;
228 node->index = leftChildIdx;
229 node->count = 0;
230 UpdateNodeBounds(this->nodes + leftChildIdx, bboxes);
231 UpdateNodeBounds(this->nodes + rightChildIdx, bboxes);
232 Subdivide(this->nodes + leftChildIdx, bboxes);
233 Subdivide(this->nodes + rightChildIdx, bboxes);
234}
235
236//------------------------------------------------------------------------------
239inline float
240Bvh::FindBestSplitPlane(Bvh::Node* node, Math::bbox* bboxes, int& axis, float& splitPos)
241{
242 constexpr uint32_t intervals = 8;
243 float bestCost = 1e30f;
244 for (uint32_t a = 0; a < 3; a++)
245 {
246 float boundsMin = 1e30f;
247 float boundsMax = -1e30f;
248 for (uint32_t i = 0; i < node->count; i++)
249 {
250 Math::bbox const& bbox = bboxes[this->externalIndices[node->index + i]];
251 float center = (bbox.pmax[a] + bbox.pmin[a]) * 0.5f;
252 boundsMin = Math::min(boundsMin, center);
253 boundsMax = Math::max(boundsMax, center);
254 }
255
256 if (boundsMin == boundsMax)
257 continue;
258
259 struct Bin
260 {
261 Math::bbox bounds;
262 uint32_t count = 0;
263 };
264
265 // populate the bins
266 Bin bin[intervals];
267
268 float scale = (float)intervals / (boundsMax - boundsMin);
269 for (uint32_t i = 0; i < node->count; i++)
270 {
271 Math::bbox const& bbox = bboxes[this->externalIndices[node->index + i]];
272 float center = (bbox.pmax[a] + bbox.pmin[a]) * 0.5f;
273 uint32_t binIdx = Math::min(intervals - 1, (uint32_t)((center - boundsMin) * scale));
274 bin[binIdx].count++;
275 bin[binIdx].bounds.extend(bbox);
276 }
277 // gather data for the 7 planes between the 8 bins
278 float leftArea[intervals - 1];
279 float rightArea[intervals - 1];
280 uint32_t leftCount[intervals - 1];
281 uint32_t rightCount[intervals - 1];
282 Math::bbox leftBox;
283 leftBox.begin_extend();
284 Math::bbox rightBox;
285 rightBox.begin_extend();
286 uint32_t leftSum = 0;
287 uint32_t rightSum = 0;
288 for (uint32_t i = 0; i < intervals - 1; i++)
289 {
290 leftSum += bin[i].count;
291 leftCount[i] = leftSum;
292 leftBox.extend(bin[i].bounds);
293 leftArea[i] = leftBox.area();
294 rightSum += bin[intervals - 1 - i].count;
295 rightCount[intervals - 2 - i] = rightSum;
296 rightBox.extend(bin[intervals - 1 - i].bounds);
297 rightArea[intervals - 2 - i] = rightBox.area();
298 }
299 // calculate SAH cost for the 7 planes
300 scale = (boundsMax - boundsMin) / intervals;
301 for (int i = 0; i < intervals - 1; i++)
302 {
303 float planeCost = leftCount[i] * leftArea[i] + rightCount[i] * rightArea[i];
304 if (planeCost < bestCost)
305 {
306 axis = a;
307 splitPos = boundsMin + scale * (i + 1);
308 bestCost = planeCost;
309 }
310 }
311 }
312 return bestCost;
313}
314
315//------------------------------------------------------------------------------
318inline void
320{
321 if (this->nodes != nullptr)
322 delete[] this->nodes;
323 if (this->externalIndices != nullptr)
324 delete[] this->externalIndices;
325
326 this->nodes = nullptr;
327 this->externalIndices = nullptr;
328 this->nodesUsed = 0;
329 this->rootNodeIndex = 0;
330 this->numNodes = 0;
331}
332
333} // namespace Util
Nebula's bounding box class.
Definition bbox.h:24
void end_extend()
this resets the bounding box size to zero if no extend() method was called after begin_extend()
Definition bbox.h:196
point pmax
Definition bbox.h:93
void begin_extend()
begin extending the box
Definition bbox.h:183
void extend(const vec3 &p)
extend the box
Definition bbox.h:210
point pmin
Definition bbox.h:92
float area() const
calculate half-area of the surface of the box. If you need the full area, just multiply by 2.
Definition bbox.h:563
bool intersects(const bbox &box) const
check for intersection with axis aligned bounding box
Definition bbox.h:289
A line in 3d space.
Definition line.h:22
vector m
Definition line.h:56
Nebula's dynamic array class.
Definition array.h:60
void Append(const TYPE &first, const ELEM_TYPE &... elements)
Append multiple elements to the end of the array.
Definition array.h:1334
Definition bvh.h:36
float CalculateCost() const
Definition bvh.h:38
uint32_t index
left node, or index to first child if count is zero
Definition bvh.h:53
Math::bbox bbox
the bounding box of the node
Definition bvh.h:51
uint32_t count
number of children
Definition bvh.h:55
bool IsLeaf() const
Definition bvh.h:43
friend Bvh
Definition bvh.h:49
Definition bvh.h:24
void UpdateNodeBounds(Bvh::Node *node, Math::bbox *bboxes)
Definition bvh.h:174
uint32_t rootNodeIndex
Definition bvh.h:67
void Build(Math::bbox *bboxes, uint32_t numBoxes)
Builds the bvh tree.
Definition bvh.h:84
~Bvh()
Definition bvh.h:75
Util::Array< uint32_t > Intersect(Math::line line)
returns all intersected bboxes indices based on the order they were when passed to the Build method.
Definition bvh.h:107
uint32_t numNodes
Definition bvh.h:68
void Clear()
Definition bvh.h:319
uint32_t nodesUsed
Definition bvh.h:69
uint32_t * externalIndices
these map to where the original bbox was when passed to the build method.
Definition bvh.h:66
float FindBestSplitPlane(Bvh::Node *node, Math::bbox *bboxes, int &axis, float &splitPos)
Definition bvh.h:240
void Subdivide(Bvh::Node *node, Math::bbox *bboxes)
Definition bvh.h:191
Bvh::Node * nodes
Definition bvh.h:64
__forceinline plane normalize(const plane &p)
Definition plane.h:255
__forceinline TYPE min(TYPE a, TYPE b)
Definition scalar.h:390
__forceinline TYPE max(TYPE a, TYPE b)
Definition scalar.h:359
A pinned array is an array which manages its own virtual memory.
Definition String.cs:6
unsigned int uint
Definition types.h:31