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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s