Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 49

Building BVHs by Recursive Scene Subdivision

Recommended resources

Hello! Welcome back.

In our last lesson, we mastered the implementation of a fast and robust ray-AABB intersection test. We focused on performance because we knew this function would be the workhorse of our scene acceleration structure. Today, we're going to build that structure.

This lesson is dedicated to constructing a Bounding Volume Hierarchy (BVH). The goal is to take a list of objects in our scene and organize them into a tree-like hierarchy of bounding boxes. This "divide and conquer" approach will allow us to quickly discard large parts of the scene that a ray doesn't intersect, dramatically speeding up our renders. By the end of this lesson, you will be able to implement the recursive logic that builds this crucial data structure.

1. The Core Idea: Boxes Within Boxes

Before diving into code, let's solidify the concept. A BVH is a binary tree.

  • The root node has a bounding box that encloses the entire scene.
  • Each internal node represents a spatial subdivision, containing two children whose bounding boxes, when combined, cover the same volume as the parent (though they may overlap).
  • The leaf nodes contain the actual geometric primitives (our hittable objects).

When a ray traverses the scene, instead of testing every single object, it first tests against the root node's box. If it misses, we're done with the entire scene! If it hits, we then recursively test the children. This process continues down the tree, rapidly culling objects and leaving us with only a tiny subset to test in detail.

BVH Algorithm Visualization with a 3D Model
This image illustrates the BVH concept. On the right, a complex model is enclosed in nested bounding boxes. A ray's path through these boxes corresponds to a traversal of the tree structure on the left, quickly isolating the relevant geometry.

The following video provides an excellent high-level introduction to this idea.

Coding Adventure: More Ray Tracing!

Sebastian Lague's 'Coding Adventure: More Ray Tracing!' offers a great visual explanation of why we need a BVH and the basic idea of recursively splitting the mesh.

Please watch from 3:44 to 4:48. Focus on the core idea of splitting a mesh in half, giving each half its own bounding box, and repeating this process recursively.

2. The bvh_node Class and Construction Logic

To build a tree, we need a node. Our bvh_node will itself be a hittable object, just like our spheres and lists of objects. This elegant design means we can treat a complex, BVH-accelerated scene as a single hittable object in our main render loop.

A bvh_node needs to store:

  1. Its own bounding box (aabb).
  2. Pointers to its left and right children (which are also hittables).

The construction of the tree happens inside the bvh_node's constructor and is a recursive process. Here is the high-level algorithm:

  1. Given a list of objects, determine a splitting axis (e.g., X, Y, or Z).
  2. Sort the objects along that axis based on the position of their bounding boxes.
  3. Split the sorted list into two halves.
  4. The current node's left child becomes a new bvh_node constructed from the first half of the list.
  5. The current node's right child becomes a new bvh_node constructed from the second half.
  6. This recursion stops when a node receives a small number of objects (e.g., one or two), at which point it becomes a leaf node.

The Ray Tracing: The Next Week book provides a clear and complete implementation of this logic. It's a great reference for our C++ implementation.

Ray Tracing: The Next Week

Peter Shirley's 'Ray Tracing: The Next Week' details the implementation of a bvh_node class and its recursive constructor. This will form the basis of our implementation.

Please read these two sections: The BVH Node Class: Familiarize yourself with the class definition. Note how it is also a hittable and stores shared_ptrs to its children. Splitting BVH Volumes: This is the core of the lesson. Study the bvh_node constructor. Pay close attention to how it handles the base cases (1 or 2 objects) and the recursive case (sorting the list and creating two new children). Don't worry about the box_compare functions yet; we'll cover those next.

3. The Splitting Strategy

The quality of our BVH—and thus its performance—depends heavily on how we choose to split the objects at each step. A good split results in child bounding boxes that are much smaller than the parent's and have minimal overlap.

Choosing the Axis

A simple and effective strategy is to always split along the longest axis of the current node's bounding box. If a box is wide but not tall or deep, splitting it along its width is likely to produce two more "squarish" and smaller sub-boxes.

Partitioning the Objects

Once we have an axis, we need to partition our list of hittable objects. As seen in the Ray Tracing: The Next Week resource, a very clean way to do this in C++ is with std::sort and a custom comparison function.

We'll need three comparison functions, one for each axis, that tell std::sort how to order two hittable objects based on the minimum coordinate of their bounding boxes.

Ray Tracing: The Next Week

Let's now look at the implementation of the comparison functions and the 'longest axis' optimization from 'Ray Tracing: The Next Week'.

Please read the following two sections: The Box Comparison Functions: Understand how the box_compare helper function works and how box_x_compare, box_y_compare, and box_z_compare use it. This is a great practical example of using function objects/pointers with the C++ STL. Another BVH Optimization: This section modifies the constructor to first compute the bounding box of all objects in the list, find its longest axis using longest_axis(), and then choose the appropriate comparator. This is the strategy we will implement.

For a more visual demonstration of this process, the following video segment is very helpful.

Coding Adventure: More Ray Tracing!

Sebastian Lague's video visually demonstrates the process of recursively splitting bounding boxes along their longest axis.

Watch from 4:48 to 7:46. He first implements a simple split (always vertical) and then refactors it to split along the longest axis. Seeing the bounding boxes being drawn at each level of recursion provides great intuition for what our code is doing.

Test your understanding!

Imagine a bvh_node that contains 100 objects. Its bounding box has dimensions (width=10, height=50, depth=20).

  1. Which axis will our algorithm choose to split along?
  2. After calling std::sort with the appropriate comparator, what can we say about the arrangement of the 100 objects in our std::vector?
Show answer
  1. The algorithm will choose the Y-axis (height=50), as it is the longest axis of the bounding box.
  2. The std::vector of 100 hittable objects will be sorted in ascending order based on the min.y coordinate of each object's bounding box. The object with the smallest y bounding box coordinate will be at the beginning of the list, and the one with the largest will be at the end.

4. An Alternative: In-Place Partitioning

While std::sort is clean and easy to use, it does more work than necessary. We don't need the entire list to be perfectly sorted; we just need to partition it into two groups: "left" and "right".

For this, we can use an in-place partitioning algorithm, which should be familiar from your CS background as it's the core of QuickSort. This approach iterates through the list from both ends, swapping elements that are on the wrong side of a split plane until the list is correctly partitioned.

A crucial optimization here, especially for scenes with complex geometry (like triangle meshes), is to sort an array of indices, not the objects themselves. Swapping integer indices is much cheaper than swapping large object data structures.

How to build a BVH – Part 1: Basics - Jacco's Blog

For a more performance-oriented perspective, Jacco's Blog provides an excellent C++-centric guide that builds a BVH using an in-place partition and an index array. This is representative of techniques used in high-performance engines.

Skim through these sections to understand this alternative approach: Read the short section '2. Split the group in two halves'. This shows the QuickSort-like partitioning loop. Read the section 'One More Thing'. This explains the key insight of using an intermediate array of triangle indices (triIdx) to avoid moving heavy data. Finally, look at the full Subdivide function at the end. See how it combines these ideas: it determines the split axis, partitions the triIdx array in-place, and then recurses.

While we'll stick to the std::sort method from Peter Shirley's book for our initial implementation due to its simplicity, it's valuable to know about this more optimized partitioning strategy.

5. Advanced Splitting Heuristics: A Preview

The "split on the longest axis" method is a good heuristic, but it's not optimal. Production renderers like Arnold and Karma often use a more sophisticated method called the Surface Area Heuristic (SAH).

SAH works by evaluating the cost of a potential split. The cost is a function of the surface areas of the two potential children boxes and the number of primitives inside them. The algorithm then chooses the split (out of many possible candidates) that has the lowest predicted cost. This often results in a more "balanced" tree that is faster to traverse, at the expense of a longer build time.

You don't need to implement this now, but understanding that it exists is part of your goal to connect your project to production concepts.

I wrote a Ray Tracer from scratch... in a Year

This video by Jacob Gordiak provides a great conceptual overview of different splitting strategies, culminating in the Surface Area Heuristic.

Watch from 39:15 to 45:47. First, he compares the 'midpoint split' (which we are using, also called object median split) with the 'median split'. Then, he introduces the Surface Area Heuristic (SAH), explaining the cost equation conceptually. Don't worry about the math details; focus on the idea of choosing a split that minimizes a cost function.

Conclusion

In this lesson, we've laid out the complete blueprint for constructing a BVH. We've moved from the high-level concept of a bounding volume tree to the specific C++ implementation details of a recursive constructor.

Key Takeaways:

  • A BVH is a tree of hittable objects where each node stores a bounding box and pointers to its children.
  • The tree is built recursively by partitioning a list of objects and passing the sub-lists to child node constructors.
  • The recursion terminates when a node contains only one or two objects, becoming a leaf.
  • A good, simple splitting strategy is to partition objects along the longest axis of the parent node's bounding box.
  • In C++, this partitioning can be implemented cleanly with std::sort and a custom comparator, or more performantly with an in-place partition on an array of indices.
  • Advanced methods like the Surface Area Heuristic (SAH) exist to create even higher-quality trees.

Next Steps

We now know how to build the BVH. In the next lesson, we will implement the hit method for our bvh_node. This involves writing the traversal algorithm that navigates the tree, using our fast aabb::hit function from the previous lesson to efficiently find the closest intersection for a given ray.