# Trees in Games: Bounding Volume Hierarchy (Implementation)

Again, thanks to CMU 15662 Computer Graphics course, I have got a nice visualization tool that can clearly show the bounding boxes in the Bounding Volume Hierarchy (BVH). Then under Zoe’s help, I have successfully implemented a simple BVH and visualized it.

My BVH will firstly build the root bounding box, and find the longest axis, then recursively equally divide space along the longest axis, recalculate the child bounding boxes and put them into the tree. Here is the relevant code for it.

```BVH(const std::vector<Primitive *> &_primitives, size_t max_leaf_size) {
this->primitives = _primitives;

// Construct a BVH from the given vector of primitives and maximum leaf
// size configuration. The starter code build a BVH aggregate with a
// single leaf node (which is also the root) that encloses all the
// primitives.

BBox bb;
for (size_t i = 0; i < primitives.size(); ++i) {
bb.expand(primitives[i]->get_bbox());
}

root = new BVHNode(bb, 0, primitives.size());

// start

// choose longest axis
int longestAxisIndex = 0;
int longestAxisDistance = -INF_D;
for (int i = 0; i < 3; ++i)
{
if (bb.extent[i] > longestAxisDistance)
{
longestAxisDistance = bb.extent[i];
longestAxisIndex = i;
}
}

// sort according to longestAxisIndex
multimap<float, int> centroidMap;
for (size_t i = 0; i < primitives.size(); ++i)
{
float centroidPointOnLongestAxis = primitives[i]->get_bbox().centroid()[longestAxisIndex];
centroidMap.insert(pair<float, int>(centroidPointOnLongestAxis, i));
}

std::vector<Primitive *> temp_primitives = primitives;
int count = 0;
for (multimap<float, int>::iterator it = centroidMap.begin(); it != centroidMap.end(); ++it)
{
primitives[count] = temp_primitives[it->second];
count++;
}

PartitionEqually(primitives, bb, root, longestAxisIndex, max_leaf_size);

}

void PartitionEqually(std::vector<Primitive *> &primitives, BBox bb, BVHNode* node, int longestAxisIndex, size_t max_leaf_size) {

if (node->range <= max_leaf_size)
{
return;
}

// part equally
float middlePoint = bb.min[longestAxisIndex] + bb.extent[longestAxisIndex] / 2.0f;

// left child
BBox bbLeft;
int leftCount = 0;

// right child
BBox bbRight;
int rightCount = 0;

for (size_t i = 0; i < node->range; ++i)
{
if (primitives[(node->start) + i]->get_bbox().centroid()[longestAxisIndex] >= middlePoint)
{
bbRight.expand(primitives[(node->start) + i]->get_bbox());
rightCount++;
}
else
{
bbLeft.expand(primitives[(node->start) + i]->get_bbox());
leftCount++;
}
}

BVHNode* leftNode = new BVHNode(bbLeft, node->start, leftCount);
BVHNode* rightNode = new BVHNode(bbRight, node->start + leftCount, rightCount);

node->l = leftNode;
node->r = rightNode;

if (leftCount == 0 || rightCount == 0)
{
return;
}

PartitionEqually(primitives, bbLeft, leftNode, longestAxisIndex, max_leaf_size);
PartitionEqually(primitives, bbRight, rightNode, longestAxisIndex, max_leaf_size);

}
```

And it works!

This slideshow requires JavaScript.

Advertisements
Posted on Categories Longyi