Ray Tracing and the Cost of Asking Anywhere

Swap the two loops from the previous lesson. For each pixel, construct a ray from the eye through it, and find the nearest surface that ray meets. The outer loop is now over pixels and the inner loop is over geometry.

The immediate consequence is that visibility stops being tied to the camera. A ray is just an origin and a direction, so once the machinery exists it answers the same question from anywhere: from a surface point toward a light, from a mirror in the reflected direction, from a shading point in a random direction.

That generality is the entire reason the architecture exists. Arthur Appel introduced ray casting for visibility and shadows in 1968, and Turner Whitted made it recursive in "An Improved Illumination Model for Shaded Display", Communications of the ACM, volume 23, issue 6, 1980, pages 343 to 349, spawning rays at each hit to follow reflection and refraction.

Write the loop honestly and the problem is immediate. Testing every ray against every triangle is O(rays x triangles).

Put numbers on it. A 1920 by 1080 image is about two million primary rays. A modest scene has a million triangles. That is two times ten to the twelfth intersection tests for the first bounce, before a single shadow or reflection ray. At a billion tests per second that is over half an hour per frame.

And the exponent is the wrong shape. Doubling scene detail doubles the cost of every ray, which is not how the rasteriser behaved: there, extra triangles that end up hidden cost triangle setup and nothing more.

So ray tracing is not usable as stated. Everything practical about it comes from never performing most of those tests, and that requires knowing in advance which regions of space a ray cannot possibly hit.

The fix is a tree over the geometry. Wrap groups of triangles in simple volumes, usually axis-aligned boxes, and nest those volumes in larger ones up to a single root. That is a bounding volume hierarchy.

The traversal rule is one line of logic. Test the ray against a node's box. If it misses, every triangle beneath that node is discarded at once, with no further work. If it hits, descend into the children. At a leaf, test the handful of triangles directly.

A box test is cheap: for an axis-aligned box it is a few comparisons of interval overlaps along the three axes, with no square roots and no division beyond the reciprocal of the ray direction, which is computed once per ray.

The result turns the linear scan into something closer to logarithmic in scene size, which is the difference between half an hour and milliseconds.

The leverage is entirely in the right-hand branch. One box test removes every triangle under that node, however many there are, at a cost independent of that number.

That is why the shape of the tree matters more than the speed of the intersection code. A hierarchy whose boxes overlap heavily forces the ray to descend both children repeatedly, and the rejections stop happening. A hierarchy with tight, well-separated boxes rejects early and often.

So the real engineering question is not how to traverse a BVH. It is how to build one whose boxes are worth testing.

Splitting a node at the midpoint of its longest axis is easy and often poor. The standard answer estimates the cost of a proposed split before making it.

The key geometric fact: for rays with uniformly distributed origins and directions, the probability that a ray passing through a box also passes through a child box is proportional to the ratio of their surface areas. So a split's expected cost is SA(left)/SA(node) * N(left) + SA(right)/SA(node) * N(right), plus the cost of the box tests themselves.

Evaluate that for many candidate split positions and take the cheapest. This is the surface area heuristic, from J. David MacDonald and Kellogg S. Booth, "Heuristics for ray tracing using space subdivision", The Visual Computer, volume 6, 1990, pages 153 to 166.

Note what it optimises: not tree balance, but expected traversal cost. It will happily produce a lopsided tree if that isolates a dense cluster of geometry from empty space.

Traversal is a stack walk with one early exit that matters.

def trace(bvh, origin, direction, t_max=float("inf")):
    best_t, best_hit = t_max, None
    stack = [bvh.root]
    while stack:
        node = stack.pop()
        t_box = node.box.intersect(origin, direction)
        if t_box is None or t_box > best_t:
            continue                 # miss, or entirely behind a closer hit
        if node.is_leaf:
            for tri in node.triangles:
                t = tri.intersect(origin, direction)
                if t is not None and t < best_t:
                    best_t, best_hit = t, tri
        else:
            stack.append(node.far)   # push far first, pop near first
            stack.append(node.near)
    return best_hit, best_t

Two lines carry the performance. t_box > best_t prunes a node whose entire volume lies beyond the closest hit found so far. Pushing the far child first means the near child is visited first, which finds a close hit early and makes that prune fire more often.

A shadow ray can do better still: it does not need the nearest hit, only whether any hit exists, so it returns on the first one.

Two costs dominate, and neither is the arithmetic of ray against triangle.

The first is memory. Traversal is a pointer chase through a tree whose nodes are scattered, and each step depends on the result of the previous one. It is latency bound rather than compute bound, which is the opposite of the rasteriser's inner loop.

The second is divergence. On hardware that executes many rays in lockstep, rays in the same group take different branches through the tree. Once they diverge, the group runs the union of both paths, and the effective width collapses. Primary rays from neighbouring pixels stay coherent; reflection rays off a bumpy surface do not, and randomly scattered rays diverge almost immediately.

This is why hardware ray tracing units exist: they implement box tests and traversal directly, with memory layouts designed for the access pattern, rather than leaving it to general shader cores.

The BVH is a global structure built from the whole scene, which is exactly what the rasteriser avoided, and the bill arrives when the scene changes.

Moving one object invalidates every box containing it, up to the root. Rebuilding a high-quality tree with a full surface area heuristic is far too slow to do per frame for a large scene.

The standard resolution is a two-level structure. Each object gets its own BVH in its own coordinate frame, built once, and a small top-level tree holds one entry per instance with its transform. Moving an object updates only the top level, and a ray entering an instance is transformed into that object's local space rather than the object being rebuilt.

Deforming geometry, such as an animated character, is the case this does not solve. Its bottom-level tree must be refitted or rebuilt, and refitting preserves the topology while letting box quality decay as the pose drifts from the one it was built for.

The fifth row is what the previous lesson could not offer at any price, and it is why shadows, reflections, refraction and indirect light fall out of this architecture rather than being bolted on.

The sixth and seventh rows are what it gave up. A rasteriser needs no global structure and does not care whether anything moves.

Neither list dominates the other, which is the actual state of the field and the subject of the final lesson.