92 for (uint32_t i = 0; i < numBoxes; i++)
97 root.
count = numBoxes;
121 for (uint32_t i = 0; i < node->
count; i++)
129 node = stack[--stackPtr];
143 std::swap(dist1, dist2);
144 std::swap(child1, child2);
154 node = stack[--stackPtr];
162 stack[stackPtr++] = child2;
177 uint32_t
const end = node->
index + node->
count;
178 for (uint32_t i = node->
index; i < end; i++)
193 if (node->
count <= 2)
201 if (splitCost >= nosplitCost)
207 int j = i + node->
count - 1;
211 float center = (bboxes[idx].
pmin[axis] + bboxes[idx].
pmax[axis]) * 0.5f;
212 if (center < splitPos)
218 int leftCount = i - node->
index;
219 if (leftCount == 0 || leftCount == node->
count)
228 node->
index = leftChildIdx;
242 constexpr uint32_t intervals = 8;
243 float bestCost = 1e30f;
244 for (uint32_t a = 0; a < 3; a++)
246 float boundsMin = 1e30f;
247 float boundsMax = -1e30f;
248 for (uint32_t i = 0; i < node->
count; i++)
252 boundsMin =
Math::min(boundsMin, center);
253 boundsMax =
Math::max(boundsMax, center);
256 if (boundsMin == boundsMax)
268 float scale = (float)intervals / (boundsMax - boundsMin);
269 for (uint32_t i = 0; i < node->
count; i++)
273 uint32_t binIdx =
Math::min(intervals - 1, (uint32_t)((center - boundsMin) * scale));
275 bin[binIdx].bounds.extend(
bbox);
278 float leftArea[intervals - 1];
279 float rightArea[intervals - 1];
280 uint32_t leftCount[intervals - 1];
281 uint32_t rightCount[intervals - 1];
286 uint32_t leftSum = 0;
287 uint32_t rightSum = 0;
288 for (uint32_t i = 0; i < intervals - 1; i++)
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();
300 scale = (boundsMax - boundsMin) / intervals;
301 for (
int i = 0; i < intervals - 1; i++)
303 float planeCost = leftCount[i] * leftArea[i] + rightCount[i] * rightArea[i];
304 if (planeCost < bestCost)
307 splitPos = boundsMin + scale * (i + 1);
308 bestCost = planeCost;
321 if (this->
nodes !=
nullptr)
322 delete[] this->
nodes;
326 this->
nodes =
nullptr;
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
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
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