AABBs and Bounding Volume Hierarchies

Brute-force intersection tests every ray against every primitive. That cost dies on any real mesh. Acceleration structures skip work. The standard first structure is a bounding volume hierarchy of axis-aligned boxes.

If a ray misses a box, it misses every primitive inside the box. That single fact is the entire acceleration idea.

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)

If t_enter > t_leave, the ray misses. Zero direction components are a classic NaN source. Replace a zero component carefully or branch to an inside/outside test for that axis.

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 splits are easy and often mediocre on real assets. The surface area heuristic (SAH) estimates traversal cost from box area and child counts. Even a cheap binned SAH usually beats midpoint on 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.