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);
    }
}

 

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