AABBs and Bounding Volume Hierarchies

Brute-force intersection tests every ray against every primitive in the scene, a useful reference implementation whose cost becomes prohibitive for any substantial mesh. Acceleration structures avoid unnecessary primitive tests, and the standard initial structure is a bounding volume hierarchy composed of axis-aligned bounding boxes.

Because a ray that misses a conservative bounding box cannot intersect any primitive enclosed by that box, one inexpensive slab test can reject an entire subset of the scene; this observation is the essential idea behind hierarchical acceleration.

A BVH rejects large subsets of the scene with one slab test.

AABB slab test

For each axis, compute entry and exit parameters against the infinite slab between min and max:

invD = 1 / d[axis]
t0 = (min[axis] - o[axis]) * invD
t1 = (max[axis] - o[axis]) * invD
if invD < 0: swap(t0, t1)
t_enter = max(t_enter, t0)
t_leave = min(t_leave, t1)

When $t_{\mathrm{enter}}>t_{\mathrm{leave}}$, the intervals associated with the three slabs do not overlap and the ray misses the box. Zero direction components require explicit care, since a naive reciprocal introduces infinities or NaNs; a robust implementation either handles the parallel slab case directly or uses a well-defined reciprocal convention.

Construction

Build a binary tree over primitives:

1. Compute the bounding box of the current set.
2. Choose a split axis, often the longest extent.
3. Partition primitives, commonly by centroid.
4. Recurse until a leaf holds a small count, typically 4 to 8 primitives.

Midpoint splitting is simple but frequently mediocre on irregular production assets. The surface area heuristic estimates expected traversal cost from child bounds and primitive counts, and even a modest binned SAH implementation generally produces a more useful hierarchy for imported meshes.

Leaves store primitive indices. Interior nodes store child indices and a box. Pack nodes tightly. After the arithmetic is cheap, cache misses dominate.

Traversal

stack = [root]
while stack not empty:
    node = pop
    if ray misses node.box in [t_min, closest]:
        continue
    if node is leaf:
        test primitives; maybe shrink closest
    else:
        push far child
        push near child

Near-first order helps because a nearer hit shrinks closest and rejects farther boxes sooner. Shadow rays may return at the first hit.

Instancing

A two-level scheme works well: a BVH over a mesh, then a BVH over instances. Each instance stores a transform and a pointer to a shared mesh BVH. Transform the ray into object space, traverse the shared tree, transform the hit back. Identical props stay memory-cheap.

Quality metrics

After build, record maximum depth, average leaf size, and node count. If maximum depth resembles the primitive count, partitioning failed. Avoid empty leaves and single-child interior nodes.

Animated geometry needs refit or rebuild. Refit updates boxes and keeps topology. Rebuild is slower and higher quality when motion is violent.

Common errors

• Rebuilding static geometry every frame
• Leaving world-space boxes stale after skinning
• Testing leaves without shrinking t_max
• Declaring victory after “adding a BVH” without measuring box tests versus primitive tests

Count box tests and primitive tests per frame. If both remain huge, the tree is unbalanced or the ray interval never shrinks.

Leaf size tradeoff

Large leaves reduce node visits but increase primitive tests. Tiny leaves reverse the costs. Values between 4 and 8 primitives per leaf are common starting points. Measure. Scenes with long thin triangles may want different leaf sizes than scenes with compact props.

Traversal stack

A fixed array stack sized to maximum tree depth is simple and fast. If depth can exceed the array, you built a degenerate tree or need a larger bound. Do not silently drop nodes when the stack overflows. That produces missing geometry that looks like an intersection bug.