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

Trees in Games: Bounding Volume Hierarchy

A Bounding Volume Hierarchy (BVH) is a tree structure implements the Binary Space Partitioning Trees that I talked in my last post. It often applies to a set of geometric objects, and all of them are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed with larger bounding volumes recursively, eventually resulting in a tree structure with a single bounding volume at the top of the tree. This structure is efficient when work on collision detection or ray tracing.

image.png

Thanks to CMU 15662 Computer Graphics Course, I have got a very clear example of ray-scene intersection using a BVH. Here we go:

WeChat Screenshot_20180418095249.png

struct BVHNode {
    bool leaf;  // am I a leaf node?
    BBox bbox;  // min/max coords of enclosed primitives
    BVHNode* child1; // “left” child (could be NULL)
    BVHNode* child2; // “right” child (could be NULL)
    Primitive* primList; // for leaves, stores primitives
};

struct HitInfo {
    Primitive* prim;  // which primitive did the ray hit?
    float t;   // at what t value? (Ray ray = o + td)
};

void find_closest_hit(Ray* ray, BVHNode* node, HitInfo* closest) {
    HitInfo hit = intersect(ray, node->bbox);  // test ray against node’s bounding box
    if (hit.prim == NULL || hit.t > closest.t)) {
        return; // don’t update the hit record
    }
    if (node->leaf) {
        for (each primitive p in node->primList) {
            hit = intersect(ray, p);
            if (hit.prim != NULL && hit.t < closest.t) {                 
                closest.prim = p;
                closest.t = t;
            }
        }
    } else {
        find_closest_hit(ray, node->child1, closest);
        find_closest_hit(ray, node->child2, closest);
    }
}

 

Trees in Games: Binary Space Partitioning Trees

Talking about data structures in game industry, we cannot ignore trees. For example, the Binary Space Partitioning (BSP) Tree is a very common data structure for processing three-dimensional virtual scenes, especially for rendering and collision detection. I have just learnt it from Data Structures and Algorithms for Game Developers by Allen Sherrod, and now it is a good time to write some notes as a review.

In a BSP tree, the child nodes are often called the front and back nodes instead of left and right, and I think this will help you understand ray tracing more easily. The main idea of BSP is choosing a plane, then recursively partition the scene (all polygons) into halves, until some condition is met, which could be a minimum number of polygons in a node, or a certain depth of levels.

The BSP tree is a binary search tree for polygons, and leaf nodes have no children but a list of polygons. Theoretically, the creation of a BSP tree is a generally simple process made up of the following steps:

  1. Set the polygon list to the node (root if this is the first node).
  2. Calculate a plane that will be used as the splitter plane.
  3. Loop through all polygons to choose side. If there is a polygon spans the splitter plane, split it into two new planes.
  4. Repeat steps 1 to 3 for the font and back notes recursively until the stop condition is met.

The pseudo code can look like this:

listOfPolygons = new PolygonList(...);
bspTree = CreateBSPNode(listOfPolygons);

CreateBSPNode(listOfPolygons)
{
    node = new BSPNode();

    // stop recursion if threshold is met
    if(listOfPolygon.count <= MIN_NODE_POLY_COUNT)
    {
        node.polygonList = listOfPolygons;
        return node;
    }
    // else continue
    splitPlane = GetBestSplitter(listOfPolygons);

    for each(element i in listOfPolygons)
    {
        if(splitPlane.Classify(listOfPolygons[i]) == FRONT)
        {
            // front polygons
            subPolyListFront.push(listOfPolygons[i]);
        }
        else if(splitPlane.Classify(listOfPolygons[i]) == BACK)
        {
            // back polygons
            subPolyListBack.push(listOfPolygons[i]);
        }
        else
        {
            // Return two split polygons in pf and pb
            splitPlane.ClipPolygon(listOfPolygons[i], &pf, &pb);
            subPolyListFront.push(pf);
            subPolyListBack.push(pb);
        }
    }

    node.frontNode = CreateBSPNode(subPolyListFront);
    node.backNode  = CreateBSPNode(subPolyListBack);

    return node;
}

One of the challenges of making a BSP tree is to pick up a good splitter plane. If the tree is severely unbalanced, performance traversing the tree can suffer. We may choose it by a simple scoring algorithm that performs these steps:

  1. Loop through all polygons and create a plane for each one.
  2. For every plane add up the number of polygons on each side.
  3. Whichever plane has the lowest absolute difference (Math.abs(frontTotal – backTotal) is the best splitting plane, also know as the score.

This is how to implement a BSP tree, I will take a further look on using it in some real conditions later.