Surface Area Heuristic and the Cost Model Behind BVH Splits

A bounding volume hierarchy has no single correct shape. Any tree whose leaves partition the primitives and whose internal nodes bound their children is valid, and all of them produce identical images. What differs is the work: the number of box tests and primitive tests a ray performs before it reaches the geometry it must shade. Choosing the shape well is the whole job of the builder, and the standard objective is an estimate of exactly that work.

The cost function the heuristic minimises

Consider a node with children $A$ and $B$. A ray that reaches the node must be tested against both children’s boxes: two box tests. It then descends into any child whose box it crosses, and the probability of crossing a child’s box given that the ray crossed the parent’s box is modelled as the ratio of surface areas. This is the surface area heuristic’s central assumption: rays are distributed uniformly and isotropically in space, and a convex body’s probability of being hit by such a ray is proportional to its surface area.

The justification is a standard result in integral geometry. For a convex body, the average projected area over all viewing directions equals one quarter of the total surface area — Cauchy’s surface area formula. Since a ray’s hit probability is the projected area in the direction of travel, averaged over the uniform direction distribution, it is $A/4$. The factor of four cancels in every ratio, so the heuristic works with surface areas directly.

Given that model, the expected cost of a node is

$$C = C_{\text{box}} + \frac{A_A}{A}, C_A + \frac{A_B}{A}, C_B,$$

where $A_A$ and $A_B$ are the children’s surface areas, $A$ is the parent’s, and $C_A$, $C_B$ are the expected costs of the subtrees. When both children are leaves holding $n_A$ and $n_B$ primitives, the costs are $C_A = n_A C_{\text{test}}$ and $C_B = n_B C_{\text{test}}$, giving the leaf-level criterion

$$C = C_{\text{box}} + C_{\text{test}} \left( \frac{A_A}{A} n_A + \frac{A_B}{A} n_B \right).$$

This is the expression a builder evaluates for each candidate split. The ratio of the two constants, $C_{\text{box}}/C_{\text{test}}$, is the only tuning parameter that matters, and it controls the tree’s depth: a high box cost prefers fat leaves that avoid extra levels, a low box cost prefers thin leaves that prune tightly. The units are arbitrary — only the ratio enters — but the value differs between architectures, between box test implementations, and between primary and shadow rays, since a shadow ray stops at the first hit and a primary ray must find the nearest. A single constant is therefore always an approximation of an averaged workload.

float sah_cost(float area_parent, float area_a, float n_a,
               float area_b, float n_b, float c_box, float c_test)
{
    float pa = area_a / area_parent;
    float pb = area_b / area_parent;   /* pa + pb can exceed 1 for spatial splits */
    return c_box + c_test * (pa * n_a + pb * n_b);
}

The note in that comment is the interesting part. For an object split — a partition of the primitives into two disjoint sets — the children’s combined surface area can exceed the parent’s, because the union of two boxes is generally larger than either and each child cluster is separately bounded. The ratios then do not sum to one, and the “probability” interpretation breaks; the cost formula is still usable as a relative estimate but stops being an expected count of tests. For a spatial split, where the parent’s volume is partitioned by a plane and primitives may be split across both sides, the ratios do sum to something meaningful but primitives that are split appear in both children and are counted more than once, which overestimates the primitive test cost. Both deviations are known and both are tolerated because the heuristic is used to rank candidate splits against each other, not to predict absolute work.

Evaluating every split in linear time

The obvious implementation tries every axis, every candidate plane, and for each one counts and bounds the primitives on both sides: quadratic in the primitive count per node, and hopeless for large scenes. The standard fix is the sweep, which sorts the primitives by centroid along one axis and then walks the sorted array once, maintaining the running union box and primitive count from the left while a reverse pass provides the same from the right.

/* Arrays sorted by centroid along one axis. left_area[i] is the union
   area of primitives [0..i]; right_area[i] is that of (i..n-1]. */
float best_sweep(const float *centroid, const float *lo, const float *hi,
                 int n, float area_parent, float c_box, float c_test, int *split_at)
{
    float left_area[64], right_area[64];
    float mn = lo[0], mx = hi[0];
    for (int i = 0; i < n; i++) {                 /* forward prefix bounds */
        if (lo[i] < mn) mn = lo[i];
        if (hi[i] > mx) mx = hi[i];
        left_area[i] = area_of(mn, mx);
    }
    mn = lo[n - 1]; mx = hi[n - 1];
    for (int i = n - 1; i >= 0; i--) {            /* backward suffix bounds */
        if (lo[i] < mn) mn = lo[i];
        if (hi[i] > mx) mx = hi[i];
        right_area[i] = area_of(mn, mx);
    }
    float best = sah_cost(area_parent, left_area[n-1], n, 0.0f, 0, c_box, c_test);
    *split_at = n;                                /* fallback: keep as one leaf */
    for (int i = 1; i < n; i++) {
        float c = sah_cost(area_parent, left_area[i-1], i,
                           right_area[i], n - i, c_box, c_test);
        if (c < best) { best = c; *split_at = i; }
    }
    return best;
}

Three details make this correct in practice. First, the prefix and suffix sweeps must recompute the union box incrementally rather than recomputing bounds from scratch, which is what makes the pass linear. Second, the fixed-size buffers are a problem: a node with more than 64 primitives needs a different path, and the educational version above has a stack overflow for a large leaf. Production builders either allocate scratch space per thread or cap the leaf size so that large nodes are always split by the fallback strategy. Third, the split is indexed at a position in the centroid-sorted array, so the cost of a stable or unstable sort matters — an unstable sort that changes the order of equal centroids changes the candidate set and therefore the tree, which makes builds non-deterministic if the sort is parallel. Determinism requires a tie-break on primitive index.

The sweep gives $O(n \log n)$ per node with $n$ the node’s primitive count, dominated by the sort, or $O(n \log n)$ total if the sort is shared between levels as in the binned variant. The binned variant — evaluating only a fixed number of candidate planes, typically 16 to 32 per axis, and bucketing primitives by their centroid’s bin — reduces the sweep to a single pass over the primitives with no sort at all, at the cost of choosing among a coarse set of planes. For a hierarchy built at load time and traversed for hours, the extra accuracy of the full sweep is worth it. For a hierarchy rebuilt every frame from deforming geometry, the binned build is the only affordable option.

Object split or spatial split

An object split assigns each primitive wholly to one child. It is cheap: the child boxes are the union boxes of their primitive sets, no primitive is duplicated, and the leaves’ primitive arrays are permutations of the node’s own primitives. Its weakness is overlap: two large triangles that interleave in space cannot be separated, so both children’s boxes cover both triangles, and every ray that crosses either box crosses both. The tree then has regions where pruning stops working, and the number of primitive tests grows even though the slab test reports both boxes correctly.

A spatial split partitions the space, and a primitive straddling the partition plane goes into both children. That removes the overlap: the children’s boxes are disjoint (or as disjoint as the plane allows), and a ray cannot cross both. The price is duplication — a large triangle crossing many splitting planes can appear in many leaves — and the bookkeeping: each primitive in a leaf needs a reference to its original plus a clipped range, and the intersection routine must test only the portion inside the leaf’s region, or accept hits outside it and rely on the interval to reject them, which reintroduces the overlap as false hits. A triangle stored whole in a leaf that covers only part of it will be hit at points outside the leaf’s box, which is a correctness problem for anything that depends on the leaf’s extent — hierarchical occlusion culling, for instance, or the assumption that a box hit implies the primitive hit lies inside it.

In practice the trades are: object splits build faster and use less memory, spatial splits prune better on scenes with large interpenetrating primitives. Hybrid approaches split objects for the first few levels, where the geometry is coherent, and apply spatial evaluation to the nodes that the SAH reports as unprofitable. The 2006 Wald and Havran analysis showed that the full SAH sweep can be done in $O(N \log N)$ over the whole build, which is what made high-quality builds practical for offline rendering; the same paper established that the loss from a poor split strategy is bounded but substantial, and that a hierarchy built with a low-quality heuristic can require noticeably more tests per ray than one built with a thorough one.

Terminating the recursion

The SAH is used to choose how to split, not when to stop, and the stopping criterion needs to be tied to the same constants or the tree’s leaves will be mis-sized. Three conditions are commonly combined:

• Max depth. A depth limit prevents pathological recursion when the geometry is adversarially arranged. A depth of about 64 is enough for most scenes and short enough that a per-ray traversal stack of fixed size can hold the path.
• Max primitives per leaf. A cap, often 4 to 16, bounds the leaf’s brute-force cost and keeps the leaf small enough to fit its primitives in one or a few cache lines.
• SAH improvement. If the best split’s estimated cost exceeds the cost of leaving the node as a leaf — that is, if no split reduces the expression above — the recursion stops. This criterion is the one that adapts to the geometry: a node whose primitives are all far apart splits readily; a node whose primitives are already tightly clustered stays whole.

The interaction between the third criterion and the constant ratio is where builds are usually misconfigured. If c_box is set too high, the SAH concludes that almost no split is worthwhile and produces a tree of enormous leaves; traversal then does many primitive tests per node and the hierarchy is nearly pointless. If it is too low, the builder splits until every leaf has one primitive, producing a deep tree whose levels each cost a box test. The correct constant is on the order of the ratio of an average box test to an average primitive test for the architecture and workload, and the way to check it is to count both kinds of tests for a representative frame; a hierarchy whose ratio of box tests to primitive tests is low relative to its leaf occupancy is under-splitting. The same constants govern how tight the quantized bounds of a compressed tree can be before the builder stops recursing.

What the heuristic cannot see

Rays are not uniformly distributed. They start at the camera, so they all pass through a region near the camera; secondary rays start at surfaces and are biased toward the visible side. A hierarchy built for the uniform model therefore over-allocates to the interior of the scene and under-allocates near the camera. For primary rays this bias is mild because the near-camera region is small; for shadow rays it is severe, since they originate all over the lit surfaces.

Two responses are known. The first is to keep a separate hierarchy for shadow rays, built with different constants or different splitting weights, which doubles the memory and the build time. The second is to weight the SAH by a per-primitive measure of how often it is likely to be tested — for instance, by area times an estimate of visibility — which requires a pre-pass over the scene that the offline renderer can afford and the interactive one cannot. Neither changes the shape of the algorithm; both change the constants, and both are refinements on top of a heuristic that is already only approximate.

The last limitation is geometric rather than statistical. The SAH’s cost model assumes each primitive test costs the same, which is false: a large triangle is more expensive to test than a small one only through the box test around it, and a triangle with a cheap rejection — one whose bounding box fails immediately — costs nearly nothing. A builder that discriminates between primitive types by cost would have to know their rejection rates in advance, which is what a pre-pass on a sample frame would give it. That is the boundary between a build that is fast and good and a build that is slow and better, and the difference is measured in a few percent of traversal time on typical scenes rather than in kind.