GPU BVH Building: Binned SAH in GLSL

Constructing high-performance Bounding Volume Hierarchies (BVHs) on modern graphics hardware requires balancing build speed with the traversal quality governed by the Surface Area Heuristic (SAH). In compute-driven shading pipelines like GLSL, the standard algorithm used to evaluate SAH cost functions efficiently is the Parallel Binned SAH algorithm. By quantizing primitive centroids into discrete spatial bins and processing them with parallel reductions and prefix scans, this algorithm avoids the prohibitive \(O(N \log N)\) cost of sorting full primitive sets on the GPU, achieving high-quality acceleration structures entirely inside compute shaders.

The Parallel Binned SAH Algorithm

Exact SAH evaluation requires testing every potential split plane between sorted geometric primitives, which creates heavy divergence and memory bottlenecks on the GPU. The binned approach, originally introduced by Ingo Wald, simplifies the search space by dividing the current node’s bounding box along a given axis into \(B\) equidistant bins (typically \(B = 8, 16, \text{or } 32\), closely matching GPU warp/workgroup widths).

Instead of evaluating thousands of split positions, the algorithm evaluates only \(B - 1\) split planes per axis.

The cost function evaluated at each split plane \(k\) follows the standard SAH formulation:

\[C(k) = C_t + \frac{S_L(k)}{S} \cdot N_L(k) \cdot C_i + \frac{S_R(k)}{S} \cdot N_R(k) \cdot C_i\]

Where:

  • \(C_t\) is the traversal cost, and \(C_i\) is the primitive intersection cost.
  • \(S\) is the total surface area of the current parent bounding box.
  • \(S_L(k)\) and \(S_R(k)\) are the surface areas of the left and right bounding boxes formed by split plane \(k\).
  • \(N_L(k)\) and \(N_R(k)\) represent the number of primitives contained in the left and right partitions.

GLSL Compute Shader Implementation Workflow

Evaluating the Binned SAH cost in GLSL occurs in compute passes using workgroup shared memory (shared) and parallel scan techniques:

  1. Bin Assignment and Accumulation: Threads within a compute workgroup load primitive bounding boxes. For each primitive, the centroid coordinate along the candidate axis is mapped to an integer bin index:

    int binIdx = clamp(int((centroid[axis] - nodeMin[axis]) * scale[axis]), 0, NUM_BINS - 1);

    Each workgroup accumulates both the primitive count and the extended bounding box for each bin using shared memory atomics or intra-workgroup reduction trees.

  2. Parallel Prefix Scans (Cumulative Extents): Evaluating the split cost requires knowing the cumulative surface areas and primitive counts from both sides of every split candidate:

    • A left-to-right inclusive prefix scan generates \(N_L(k)\) and merges bounding boxes to calculate \(S_L(k)\) for each bin index \(k\).
    • A right-to-left exclusive prefix scan accumulates \(N_R(k)\) and merges bounding boxes to calculate \(S_R(k)\).

  3. Cost Evaluation and Minimum Reduction: With cumulative counts and areas stored in shared memory, a single warp evaluates the SAH formula across all \(B-1\) split planes across the \(X, Y,\) and \(Z\) axes simultaneously. A final parallel reduction over the evaluated cost values identifies the partition plane yielding the lowest cost. If the minimum cost found is greater than the cost of creating an un-split leaf node (\(S \cdot N \cdot C_i\)), the subdivision terminates.

Treelet Restructuring with SAH in GLSL

For real-time pipelines requiring faster initial builds, engines often combine Morton-code-based Linear BVHs (LBVH/HLBVH) with localized SAH evaluation. In this hybrid approach, Karras's treelet restructuring algorithm extracts small subtrees (e.g., 7 to 9 leaves) into compute workgroup local memory, where the binned or exact SAH permutation search is computed in GLSL registers to dynamically optimize lower-quality sections of the hierarchy.