Compressed BVH Nodes and Quantized Bounds

A full-precision BVH node stores six 32-bit floats for its box, plus child references and metadata, landing around 32 bytes per internal node. A traversal that visits a billion boxes reads 32 billion bytes — a figure that dominates the cost on any machine whose bandwidth is a few tens of gigabytes per second. Compression attacks that number directly: store bounds as small integers relative to a parent range, reconstruct them with one multiply and one add per coordinate, and fit two or four nodes into the cache lines that used to hold one.

What is stored and what is thrown away

The observation that enables quantization is that a child’s box is almost always small relative to its parent’s. A hierarchy built by recursive spatial splitting produces children whose boxes sit inside their parent’s box, and the child’s corners are near the parent’s extremes. Storing six 32-bit floats per child repeats most of the parent’s range for no information. The compressed layout stores, for each child, six small integers — often 8 bits — that encode the child’s corner as a fraction of the parent’s extent on each axis.

The reconstruction is a linear map. If the parent’s box on one axis spans $[P_{\min}, P_{\max}]$, and the child’s quantized minimum is the byte $q_{\min}$ in $[0, 255]$, then

$$c_{\min} = P_{\min} + \frac{q_{\min}}{255},(P_{\max} - P_{\min}).$$

The scale factor is the parent extent divided by 255 (or 65535 for 16-bit), and it is precomputed once per axis per node. Reconstructing a child’s corner costs one multiply and one add per coordinate — the same arithmetic count as an uncompressed slab test, but the operands are bytes fetched from a node that is a quarter the size, so the cache line carries four times the boxes.

The quantization is lossy, and the loss must be directional. A child box stored with inward-rounded corners would be smaller than the true box, and a ray passing between the stored corner and the true corner would be falsely rejected — a miss, which is not allowed in a conservative hierarchy. The stored minimum must therefore be rounded toward the parent’s minimum and the stored maximum toward the parent’s maximum, so the reconstructed box contains the true box. This is the same outward-rounding discipline as the full-precision build, applied at the level of a byte quantum rather than an ulp: the error is now up to one 256th of the parent’s extent on each axis, not one ulp, and it is systematically outward.

The consequence is that a compressed hierarchy’s boxes are slightly loose by construction. A ray can test positive against a quantized box, descend, and find that no primitive inside is actually hit — a false descent that the uncompressed tree would also incur to a far smaller degree. The looseness is bounded by the quantum and vanishes as the quantum shrinks, so the 8-bit and 16-bit choices are a direct accuracy–memory trade: 8 bits halves the node size again but doubles the relative looseness.

Node layout and the arithmetic it implies

The canonical compressed layout packs two children into one node: the parent’s extent (shared, stored once at 32-bit or quantized against a grandparent), a scale factor per axis, and six quantized corners per child. Two children then occupy roughly 32 bytes — one parent extent, one scale triple, and twelve bytes of corners — against the 64 bytes two uncompressed children would need. Fitting a node in 32 bytes means two per 64-byte cache line, which is the layout Aila and Laine’s 2009 analysis identified as the sweet spot for GPU traversal, where a warp of threads tests boxes in parallel and the memory access pattern is dominated by how many lines the warp touches.

The traversal arithmetic changes in one important way: the slab test’s divisions are replaced by multiplies. The uncompressed test divides by the ray direction once per axis; the compressed test multiplies the reconstructed corner by a per-axis scale, and the ray direction’s reciprocal is still precomputed per ray as in the slab test. The multiply that reconstructs the corner and the multiply that forms the slab parameter compose into a single scale per axis, so the total operation count is a handful of multiplies and the usual min/max/compare — nearly the same as uncompressed, with the win coming entirely from the bytes fetched, not the arithmetic.

The reference and metadata fields shrink too. A leaf stores a primitive offset and count; an internal node stores two child references. With a two-child-per-node layout and an implicit addressing scheme, the child reference is an index into the node array, and because siblings are adjacent, only one reference plus a flag is needed. A leaf can be distinguished from an internal node by a sign bit in a count field, the same trick as the ordered traversal’s sentinel. The total is that a node is identified by its address, its type by one bit, and its children by adjacency, leaving the rest of the 32 bytes for bounds.

Where quantization fails

The scheme assumes a child sits inside its parent’s box. That assumption is the exact condition under which the child’s corners lie near the parent’s extremes and a small integer encodes them with little error. Two structures violate it.

The first is a hierarchy whose internal nodes do not bound their children tightly because of a refit after deformation. A skinned mesh refit bottom-up moves bounds without moving structure, and a node whose geometry stretched far from the parent’s original box now has children whose true boxes exceed the parent’s. Quantizing those children against a stale parent extent clamps them to the parent’s range — the reconstruction cannot express a corner outside it — so the stored box is not merely loose but wrong in the non-conservative direction: a child whose true box extends beyond the parent’s stored extent is clipped, and a ray that crosses the true box outside the stored extent is missed. The fix is to force the parent’s extent to contain its children after every refit, which a compressed tree must do explicitly and an uncompressed tree need not, because floats can express any range.

The second is a tree built with spatial splitting, where a primitive is duplicated across children and the children’s boxes can overlap or extend beyond the parent’s in degenerate configurations. The same clipping failure applies, and the builder must expand the parent extent to contain the union of children before quantizing, which costs accuracy because the expansion is itself then quantized outward.

The general lesson is that quantization assumes a nested hierarchy. A builder that guarantees nesting — children’s boxes contained in the parent’s, which the SAH build does when it computes parent bounds as the union of child bounds rather than as an independent pass — is safe. A builder that computes bounds independently, or a refit that does not re-expand, is not, and the failure mode is silent: the image is missing triangles in thin slivers along the boundary of the clipped region, and no assertion fires because the arithmetic is all within range.

Memory traffic as the actual metric

The value of compression cannot be judged by node size alone. A traversal reads a node, tests it, and either descends or moves to a deferred sibling. The deferred sibling’s address determines whether the next read hits the same cache line as the current node. With two children packed adjacently, a descent into one child and a deferral of the other touch two consecutive nodes, which are on the same line or adjacent lines depending on the layout — that is the structure that makes two-children-per-32-bytes so effective, because the near-descent and the far-deferral are both close in memory.

The metric that exposes compression’s effect is cache misses per ray, not bytes per node. Halving the node size halves the memory footprint, which for a hierarchy that does not fit in the last-level cache can convert misses into hits — but only if the traversal’s access pattern is contiguous enough that the smaller working set is actually resident. A traversal that jumps randomly across a large tree still misses regardless of node size; the benefit of compression is therefore largest when the tree is close to fitting in cache, and it tapers off both when the tree fits easily (everything is a hit anyway) and when it is far too large (nothing can fit).

This is the context for the measured result in the Aila–Laine work: compression on a GPU was a win primarily because it reduced the working set enough to matter, not because the arithmetic got faster, and the win was contingent on the traversal’s scheduling. The same reasoning explains why CPU renderers, with their larger caches and different access patterns, have historically shown a smaller and more workload-dependent benefit from compression than GPUs.

Quantization of the leaf data

The same idea applies to the leaves’ primitive data. A triangle stored as nine 32-bit floats is 36 bytes; three quantized vertices at 16 bits each, relative to the leaf’s own bounds, is 18 bytes plus the leaf’s extent. The reconstruction is the same linear map, and the error is now in the vertex positions, which means the intersection test runs on vertices that are slightly different from the true ones — a different failure mode from box looseness, because a wrong vertex moves the surface, not just the bound.

A surface moved by half a quantum is a visible displacement if the quantum is large relative to the scene. A 16-bit quantization over a leaf of extent 1 metre has a quantum of about 15 micrometres, invisible; over a leaf of extent 1 kilometre it is 15 millimetres, which is visible at close range. The quantization must therefore be tied to the leaf’s extent, and leaves with large extents relative to their primitives — which the SAH build produces when it stops splitting early — need more bits or an uncompressed leaf. This is why compressed formats typically carry a per-leaf “uncompressed” escape flag for the few leaves where quantization would be unacceptable, accepting a small number of large leaves in exchange for compressing the many small ones.

The interaction with the watertight guarantee is worth naming explicitly. The watertight edge test relies on two adjacent triangles evaluating a shared edge from identical vertex coordinates. If quantization rounds the two triangles’ copies of a shared vertex differently — because the two leaves have different extents, which they do — the shared edge’s two evaluations disagree, and the pinhole artifact returns. A compressed format that deduplicates shared vertices by quantizing them once, globally or per-cluster, preserves the guarantee; a format that quantizes each leaf independently does not. This is a real constraint on compressed mesh formats and the reason some of them store an index into a shared quantized vertex array rather than per-leaf vertex data.

The build-side cost

Compression is a post-pass, not a different tree. The builder constructs an uncompressed tree with full-precision bounds, then walks it once to quantize every node against its parent, computing the per-node scale factors and rounding outward. That pass is linear in the node count and cheap relative to the SAH build, so compression can be added to an existing renderer without touching the build’s complexity or its results, only the stored form.

The pass must also decide the quanta. A fixed 8-bit scheme is simple and is the common default; a variable scheme that chooses 8 or 16 bits per node based on the node’s looseness pays a bit of header space per node and a branch per reconstruction, and is worth it only when the tree contains a mix of large loose leaves and tight ones — the typical case after a refit-heavy animation. The simplest correct scheme, quantizing every node to the same width and accepting a uniform looseness, is the one most renderers ship, and the escape to uncompressed leaves handles the pathological remainder.

The one build-time number that must be exposed rather than hidden is the root’s extent, because it sets the scale of the entire tree. A scene whose root box is computed from the geometry’s true extent quantizes finely; a scene where an outlier primitive inflates the root box by a factor of a thousand quantizes every other node against that outlier’s scale, and the whole tree is loose by a thousandth of the root’s extent on every axis. Expanding bounds or clamping the root to a reasonable region is a scene-conditioning decision that compression makes visible, and it is the same conditioning that the origin-offset logic warns about in its own way: coordinates far from the origin cost precision, and a compressed tree converts that cost into memory and false descents rather than into a wrong hit point.