Ordered BVH Traversal and the Per-Ray Stack

A hierarchy with good bounds still has to be walked in an order that exploits them. The traversal algorithm is short enough to fit on a page, but every part of it is a decision about what to do with information already computed: which child to visit first, when to stop visiting a node whose box is crossed, and how to remember the sibling that was deferred. Getting those wrong does not produce a wrong image; it produces the same image much more slowly, or in the worst case a crash.

The traversal invariant

Traversal maintains a conservative bound on the answer: a parameter $t_{\max}$, initialised to the ray’s upper limit, which is the nearest confirmed hit so far. The invariant is that no unvisited subtree can contain a hit closer than the current best. When traversal reaches a leaf, every primitive in it is tested against the interval $(t_{\min}, t_{\max}]$; a hit replaces the best and lowers $t_{\max}$. When traversal reaches an internal node, the node’s two children are tested, and any child whose box does not intersect $(t_{\min}, t_{\max}]$ is discarded.

The invariant holds because a box conservative-tests its contents: if the box does not overlap the interval, nothing inside can produce a hit in it. This is why the box test must never produce a false negative, developed in the slab test’s conservatism, and why boxes are rounded outward when built.

The order in which children are visited follows directly from the invariant. If a child’s entry parameter is smaller, its contents are closer, so a hit found there has a better chance of lowering $t_{\max}$ enough to cull the other child. Visiting the far child first does not break correctness — the interval update still holds — but it does more work: the far child’s primitives are tested, a hit may be found, and the near child is then still visited because its box overlaps the interval. Visiting near-first gives the opposite: a hit close by, an interval that now excludes the far box, and the far child is never entered.

The saving depends on how often the near child’s subtree yields a hit before the far child’s box is excluded. For a ray that hits opaque geometry, the nearest hit is likely in the near subtree, and the saving is large. For a ray that misses everything, near-first saves nothing because no interval update ever happens; both subtrees are fully explored either way. Shadow rays are the extreme case: they stop at the first hit, so any hit is a complete answer and ordering maximises the chance of finding it early.

typedef struct { int left, right; } node;   /* -1 for a leaf in one field */

typedef struct { float tmin, tmax; int prim; } interval;

/* Returns the nearest hit's t, or INFINITY. */
float traverse(const node *nodes, int root, const ray *r,
               float tmin, float tmax, int *hit_prim)
{
    int stack[64];
    float stack_t[64];          /* entry t of each deferred sibling */
    int sp = 0;
    float best = tmax;
    stack[sp] = root; stack_t[sp] = -1.0f; sp++;

    while (sp > 0) {
        sp--;
        int idx = stack[sp];
        const node *n = &nodes[idx];

        float tn, tf;
        if (!box_hit_interval(n->box, r, tmin, best, &tn, &tf)) continue;
        if (tn > best) continue;                /* box outside the interval */

        if (n->left < 0) {                      /* leaf */
            for (int i = n->right, e = i + n->count; i < e; i++) {
                float t, u, v;
                if (ray_tri(r, &prims[i], tmin, best, &t, &u, &v)) {
                    best = t; *hit_prim = i;    /* shrink the interval */
                }
            }
            continue;
        }

        float t_l = 0.0f, t_r = 0.0f, exit;
        int hit_l = box_hit_interval(nodes[n->left].box,  r, tmin, best, &t_l, &exit);
        int hit_r = box_hit_interval(nodes[n->right].box, r, tmin, best, &t_r, &exit);
        if (hit_l && hit_r) {
            /* Push the farther child first so the nearer is popped next. */
            if (t_l <= t_r) {
                stack[sp] = n->right; stack_t[sp] = t_r; sp++;
                stack[sp] = n->left;  stack_t[sp] = t_l; sp++;
            } else {
                stack[sp] = n->left;  stack_t[sp] = t_l; sp++;
                stack[sp] = n->right; stack_t[sp] = t_r; sp++;
            }
        } else if (hit_l) { stack[sp] = n->left;  stack_t[sp] = t_l; sp++; }
        else if (hit_r) { stack[sp] = n->right; stack_t[sp] = t_r; sp++; }
    }
    return best;
}

The stack entries in that sketch are popped after the node’s own box is re-tested, which is redundant work — the entry parameter was already known when the node was pushed. This is the standard first implementation, and the optimisation is to skip the re-test for pushed nodes, since the interval has only shrunk since. Storing the entry parameter makes that possible, which is why the extra array exists in the sketch even where it is not used. Production kernels typically do not store it at all: they re-test, because a box test is cheap relative to the bookkeeping of a parallel array, and because the running best has usually shrunk enough that the re-test rejects the deferred node outright, which is the common case and is faster than the pop-plus-usage path.

One bug in the sketch is worth flagging because it appears in real code: the leaf branch uses n->count, but a node that stores both children in one struct with a sentinel for leaves has nowhere to put the count. The standard layouts are separate: either the leaf holds an index and a count in the same two fields the internal node uses for child indices, distinguished by a sign bit or an out-of-range index, or the tree is stored as two arrays with an implicit ordering. The choice affects the traversal’s arithmetic by a compare or two and the tree’s memory by a few bytes per node.

Stack depth is tree height, not scene size

The stack must hold at most one deferred sibling per level of the tree that the ray currently occupies. Depth-first traversal pushes the farther sibling and descends into the nearer, so the stack’s contents at any moment form a path from the root to the current node with one entry per level. A tree of height $h$ needs $h$ entries, and a balanced tree over $N$ primitives has height around $\log_2 N$ for a binary tree, so a million primitives needs about 20 levels. Indexing the tree from the root with a heap-like layout means depth can be stored with the node and no stack is needed at all; that is the origin of the “no stack” BVH traversal used on some hardware, where the parent index is derived as (i - 1) / 2 and the sibling is i + 1 - 2 * ((i + 1) & 1). The heap layout requires a perfectly balanced tree, though, and every level that is not full wastes storage, so it trades memory for the stack.

The worst case is not balanced. An SAH-built tree on adversarial geometry can be highly unbalanced, and a tree built by inserting primitives one at a time can degenerate to a list of depth $N$. The stack must therefore be sized by the build’s maximum depth, which the builder can compute and store in a header, or capped and paired with a rebuild path that flattens any subtree exceeding the cap. A fixed stack of 64 entries is safe for any tree with depth below 64, and a builder that enforces a depth limit — as the SAH recursion described in the build article does — can guarantee that bound. Without the guarantee, a stack overflow in the traversal is not a graceful failure: it is a memory corruption in the middle of a render, and it depends on the geometry and the ray, so it will not reproduce reliably.

Restarting instead of stacking

An alternative traversal removes the stack entirely for some workloads. The “restart” technique walks down from the root along the current best-first path; when it reaches a leaf and finds a hit, it shrinks $t_{\max}$ and restarts from the root, skipping any node whose entry parameter exceeds the new bound. It is stateless, which makes it attractive for a GPU where registers are scarce, and it needs no push or pop.

The cost is repeated descent. When the interval has shrunk a lot, most of the re-descent is pruned immediately by the entry test, so the repetition is cheap; when the interval shrinks little, the re-descent repeats almost the entire path. The technique’s published motivation is the register pressure and divergence of a stack-based traversal on a SIMD machine, and it is a win when hit rates are high and intervals shrink sharply — primary rays against dense, opaque geometry — and a loss when they do not. It is also naturally robust: no stack means no overflow, which matters on a device where a corruption is unrecoverable.

The hybrid used in practice is a stack keyed on the ray: a few registers for the top of the stack and a spill array for the rest. The depth at which the spill begins is a tuning constant, and the trade is register pressure against a memory access per level.

Coherence and the cost of an unordered walk

Ordering is not just about the near-first heuristic. Rays in a packet tend to hit similar parts of the scene, and the traversal’s memory accesses then share cache lines. That benefit disappears when the rays diverge, and the standard remedy is to sort the rays by their first-hit order or by the leaf they land in, so that the packet’s members traverse overlapping paths. The sorting costs a pass over the ray set and pays for itself whenever the divergence is severe — refraction through a lens, for instance, where neighbouring pixels take wildly different paths.

Within a single ray, the memory access pattern is a function of the tree’s layout. A depth-first array has parents and children adjacent, so a descent touches a contiguous run of nodes; that is good for the first pass but bad for the deferred sibling, which is far away in memory. A breadth-first layout puts a whole level contiguously: a level’s nodes are one sequential scan, but a descent through ten levels touches ten widely separated regions. Since a traversal descends before it defers, the depth-first layout’s benefit to the descent usually outweighs its cost to the sibling, which is why builders typically emit nodes in depth-first order even when they compute the tree top-down.

The other layout decision is where the primitive data lives. Leaves holding indices into a shared primitive array require two memory accesses — one for the leaf, one for the primitive — and the second is at a location determined by the scene, not the tree. Leaves holding the primitives inline cost a larger node but remove the indirection, and the two cache lines a leaf occupies then contain everything needed to test it. For a hierarchy that is rebuilt rarely, inlining wins; for one rebuilt per frame, the copy cost may not.

Termination and the empty result

Traversal ends when the stack is empty. The answer is the best hit found, or a miss if best is still the initial upper bound. Two bugs in this termination are common enough to be worth naming.

The first is failing to distinguish “no hit found” from “a hit at the initial upper bound”. If the caller’s upper bound is INFINITY, the sentinel is unambiguous; if it is a finite maximum path length, a legitimate hit at exactly that parameter is indistinguishable from a miss. The renderer should carry a separate flag or a separate sentinel value strictly greater than any allowed bound.

The second is discarding the deferred sibling when the interval has shrunk past it while it sits on the stack. That is fine if the sibling is re-tested on pop — the test rejects it — and a correctness bug if the optimisation described above trusts a pre-computed entry parameter. The pre-computed parameter was correct when pushed and is stale after any hit; trusting it accepts a subtree whose box is outside the interval. With a conservative box test that is only a waste of work, but a stale parameter also breaks the “no unvisited subtree contains a nearer hit” invariant in the other direction when a subtree is skipped for the wrong reason: it was pushed with an entry parameter beyond the old bound, and the bound has since grown, which cannot happen — bounds only shrink — so the invariant actually survives. What does not survive is a subtree skipped because the parameter was computed against a bound that has since shrunk, which is exactly the case the re-test catches and the trust-the-parameter path misses. The conclusion: trust stored parameters for choosing order, re-test for admission.

For shadow rays the same traversal runs with a stopping condition at the first hit rather than the nearest, which means ordered descent is even more valuable and the interval update can be a simple boolean. That variant is a few lines different and considerably faster per ray, and the lower-bound handling that keeps shadow rays from re-hitting their own surface is the interval problem treated in the origin offset article.