The Slab Test for Boxes and the Inverse-Direction Shortcut

Every acceleration structure needs a cheap conservative test, and the box is the cheapest conservative shape a ray can be tested against. The test costs about six subtractions, six multiplies, and six compares per box, which is small enough that it can dominate the total cost of a traversal only if it is done badly. Doing it well means understanding that the box test is an intersection of intervals, that the usual speed trick with reciprocal directions is only safe because of how IEEE 754 handles infinities and NaNs, and that the compiler is allowed to ruin the trick if the code is written carelessly.

Three intervals intersected

A ray intersects an axis-aligned box if and only if, for each of the three axes, the ray’s parameter range overlaps the slab of space between the box’s two planes on that axis. Along $x$, the ray is at $o_x + t d_x$; the condition for being inside the slab $[b_x^{\min}, b_x^{\max}]$ is

$$t_x^{\min} = \min!\left(\frac{b_x^{\min} - o_x}{d_x}, \frac{b_x^{\max} - o_x}{d_x}\right), \qquad t_x^{\max} = \max(\ldots),$$

with a swapped pair when $d_x < 0$. Note the min and max are there because dividing by a negative $d_x$ reverses the ordering. The ray hits the box if and only if

$$\max(t_x^{\min}, t_y^{\min}, t_z^{\min}) \le \min(t_x^{\max}, t_y^{\max}, t_z^{\max}),$$

and that common interval overlaps the ray’s own search interval. The whole test is therefore six divisions, three max operations, three min operations, and one final comparison — plus the interval test against $(t_{\min}, t_{\max}]$.

Two structural facts follow. First, the test never needs the intersection point, only whether an overlap exists; a traversal kernel that only needs a boolean can stop as soon as the running lower bound exceeds the running upper bound, which often happens before all three axes are processed. Second, the order of the axes matters for that early exit: processing the axis with the largest $|d|$ first tends to close the interval fastest, though the cost of deciding the order can exceed the saving unless the order comes from the ray’s own setup rather than per box.

The reciprocal trick and the infinities it produces

Six divisions per box is expensive. The standard optimisation replaces them with three reciprocals computed once per ray, together with a multiply per plane. The reciprocal $1/d_x$ is well defined whenever $d_x \ne 0$, and this is where the interesting case lives: an axis-parallel ray has $d_x = 0$ exactly, its reciprocal is $\pm\infty$, and multiplying by the numerator gives $\pm\infty$ or NaN.

The Williams et al. formulation, published in 2005 and now ubiquitous, handles this without a branch. It computes the two candidate parameters as

$$t_1 = (b^{\min} - o) \cdot r, \qquad t_2 = (b^{\max} - o) \cdot r,$$

where $r = 1/d$, and then takes the min and max of the pair. When $r = +\infty$ and the numerator is negative, both products are $-\infty$; when the numerator is positive, both are $+\infty$. When the numerator is exactly zero — the ray origin lies exactly on a slab plane — the product is $0 \cdot \infty$, which IEEE 754 defines as NaN.

The next step is what makes the trick work. The comparison $\max(t_1, t_2) \ge t_{\text{enter}}$ is false when either operand is NaN, so a NaN causes the box to be rejected. The rejection is the desired answer in the case that produces it: a ray lying exactly in a slab plane with zero direction component is parallel to that plane and coplanar with it, so it can only hit the box along the boundary, a measure-zero case that a conservative test should refuse. The trick, then, converts the degenerate case into a rejection without a branch, at the cost of a result that is correct only because the IEEE standard mandates the NaN comparison behaviour.

This is why the code must be compiled without fast-math. GCC’s -ffast-math and Clang’s equivalent, and MSVC’s /fp:fast, permit the compiler to assume that operands are never NaN and that reassociating floating-point expressions is safe. Under those assumptions the compiler may invert the comparison, fold $0 \cdot \infty$ into zero, or reorder the min and max, and the degenerate rejection silently becomes an acceptance. The box then reports a hit for a ray coplanar with its boundary, which is a false positive — conservative and therefore not a correctness bug in the strict sense, but it defeats the early-out and, in the shadow-ray case, can produce spurious occlusion when a box’s boundary coincides with a surface.

#include <math.h>

typedef struct { float lo[3], hi[3]; } box3;
typedef struct { float o[3], d[3], inv[3]; } ray3;

/* Precompute reciprocals once per ray. Division by zero is intended:
   it yields +/-inf, and the multiplies below then produce the correct
   all-in or all-out result. */
static inline void ray_setup(ray3 *r)
{
    for (int i = 0; i < 3; i++) r->inv[i] = 1.0f / r->d[i];
}

/* Conservative slab test. Returns 1 if the box may contain a hit in (tmin, tmax]. */
int box_hit(const ray3 *r, const box3 *b, float tmin, float tmax)
{
    for (int i = 0; i < 3; i++) {
        float t0 = (b->lo[i] - r->o[i]) * r->inv[i];
        float t1 = (b->hi[i] - r->o[i]) * r->inv[i];
        float tn = fminf(t0, t1);        /* NaN propagates through fminf as NaN */
        float tf = fmaxf(t0, t1);
        tmin = fmaxf(tmin, tn);
        tmax = fminf(tmax, tf);
        if (tmin > tmax) return 0;
    }
    return 1;
}

One detail of that code is deliberately not the fast version. fminf and fmaxf are specified to return the non-NaN operand when exactly one is NaN, so they do not propagate NaN the way a bare t0 < t1 ? t0 : t1 does. With fminf, a coplanar ray’s NaN is silently dropped and the axis contributes nothing, so the box is accepted rather than rejected. That behaviour is still conservative — the ray is in the plane, so any hit is on the boundary — and it is arguably safer than relying on NaN propagation. But it means the two formulations differ in the degenerate case, and a renderer that mixes them between primary and shadow paths can get inconsistent answers for a boundary-coplanar ray. Using the ternary operator restores the NaN-propagating behaviour; using fminf restores branch-freedom. The choice must be made once and applied everywhere.

Making the test conservative on purpose

A box test in a hierarchy is not allowed to miss. It may report a hit for a box that contains nothing the ray can reach — the leaf’s own test will reject that — but it may not report a miss for a box that does contain a reachable primitive, because a miss prunes a subtree irrevocably. This asymmetry determines every rounding decision in the implementation.

The direct consequence is that the box must be at least as large as the true bounding box of its contents, which means the saved bounds should be rounded outward, not to nearest. Building a box by taking the minimum and maximum of vertex coordinates rounds twice: once when the coordinates are computed, once when the min and max are taken. Rounding the stored minimum downward by one ulp and the maximum upward by one ulp costs two operations per box and removes the possibility that the box’s plane cuts inside the geometry. For a hierarchy built once and traversed many times, that cost is amortised to nothing. For a hierarchy rebuilt every frame, it is a real cost that shows up in frame time, and then the question becomes whether the tree’s contents are quantised in a way that already guarantees outward rounding — which is what a compressed node format does, as the compressed-node discussion examines.

The t sides of the test carry the same asymmetry. A traversal kernel updates its running $t_{\max}$ with the nearest hit so far, and a box whose near-intersection is exactly equal to $t_{\max}$ must be visited, because the primitive inside might produce a hit at a $t$ that is formally the same and must be considered for a tie-break. That means the test against the upper bound is inclusive and the test against the lower bound is strictly exclusive, mirroring the ray interval convention: tmin starts at the ray’s lower bound and the exit condition is tmin > tmax with tmax initialised to the ray’s upper bound.

Why the box test is not the whole traversal cost

The slab test is about six multiplies and a handful of compares, but a traversal visits many boxes and the branch structure around each visit costs more than the arithmetic. A BVH with a branching factor of two visits roughly $2k$ nodes to reach $k$ leaves, and every internal node visit is a box test plus a decision about which child to process first. That decision is what ordered traversal is about: the near child’s distance can be obtained from the same arithmetic the slab test already computed, at the cost of storing the entry parameter rather than discarding it.

There is a real trade in returning the entry distance instead of a boolean. Storing it costs a register, and using it costs a comparison per node, but it lets traversal descend into the near child first, which grows the running $t_{\max}$ less often and prunes more. For coherent rays the ordering buys more than it costs; for incoherent rays the near-child-first strategy is still not harmful, because an unordered traversal is also correct, just slower in expectation. The measurement that decides it is the ratio of box tests to primitive tests, which the renderer can instrument without any difficulty: a hierarchy that prunes well shows a large ratio, and a hierarchy that prunes badly is suffering from a build problem, not a traversal problem.

The other hidden cost is memory. A box is six floats, 24 bytes, and a node needs the box, two child references or an index and a count, and possibly the entry distance. Padding to a cache line is common, taking the node to 32 or 64 bytes. A 64-byte node means one node per cache line, which is the best case for a traversal that jumps between levels; a 32-byte node means two per line, which is better for a traversal that mostly walks sibling pairs. The choice interacts with the layout of the tree: depth-first traversal with a small stack touches nodes scattered across the array, while breadth-first layouts arrange levels contiguously and make the sibling pair adjacent. That is a build-time decision with a traversal-time consequence, and the two must be designed together rather than separately.

Bounds that are not boxes

Nothing forces the conservative volume to be a box. Spheres are cheaper to test — one quadratic, as in the stable quadratic form — but bound loose for elongated geometry, and their looseness means more false descents. Convex hulls of small clusters, oriented boxes, and tetrahedra have all been used; each trades a more expensive setup for a tighter fit, and the tightness only pays if the geometry inside is elongated relative to the box.

A box’s failure mode as a bound is that it ignores the correlation between axes. A flat, diagonally oriented quad has a box with twice the area of the quad; a long thin cylinder oriented along a diagonal has a box containing most of the empty space around it. In those cases the box reports a hit for a ray that passes through empty space inside the box, and the leaf test then rejects. Nothing is wrong; the pruning is just less effective than the geometry’s tightness would suggest. A hierarchy over such geometry is measurably worse than one over well-conditioned geometry with the same primitive count, and the usual response is a different splitting strategy rather than a different bound.

The last thing the box test must tolerate is a degenerate box. A box whose minimum equals its maximum on one axis is a plane, and a ray parallel to it can produce the coplanar NaN case described above; a box that is inverted, with a minimum greater than a maximum, should never be produced by the builder but a corrupt or empty leaf can produce one, and the slab test will reject it in every direction because the entry parameter exceeds the exit parameter on that axis. A box containing a single point is the limit of that behaviour and is likewise rejected for any ray not passing exactly through it. These are all safe failures, which is the property that makes a branch-free test acceptable in a kernel that cannot afford exception handling.