Surface area heuristic (SAH) is a heuristic commonly used in various spatial partitioning schemes, particularly in ray tracing acceleration structures.

The core idea of SAH is the assumption that the probability of a random ray intersecting with an object within a bounding volume is proportional to the ratio of the object’s surface area to the surface area of the bounding volume.

Example

If a bounding box with surface area is split into two children with surface areas and , the probabilities that a ray passing through also passes through and is given by and , respectively 1

Cost Function

The quality of an acceleration structure can be estimated in terms of the expected number of operations need to finding the nearest intersection with a given ray. The cost with root is given by the recurrence relation: 2

where

  • is the cost of the subtree with root
  • is the cost of traversing the node (usually a ray-box intersection)
  • is the cost of a ray-primitive intersection
  • is the number of primitives in the node
  • are children of
  • is the conditional probability of traversing child node given that is intersected

The constants and are usually rough approximations. In practice, their ratio is more important than their absolute values. This ratio impacts leaf sizes. Although traversal cost is typically much smaller than ray-primitive intersection cost, PBRT intentionally undertone a ratio of 2:1 to avoid very deep BVHs, which can harm data locality.

The surface area heuristic express the above conditional probability as the proportion of surface areas:

where is the surface area of the bounding box of node . Substituting back into the cost function, we get

By unrolling, we can remove the recurrence 2

where

  • and denotes the interior and the leaf nodes of a subtree with root , respectively

In Practice and Performance

In practice, we typically begin by selecting an axis to split and then apply a greedy algorithm to determine the split plane that minimizes the cost for the leaves. 1

Given n primitives, there are n-1 possible ways to split objects across an axis. A naive approach would use an O(n²) algorithm to compute the cost of each potential split: 3

const int split_count = primitive_count - 1;
std::vector<float> cost(split_cost);
 
for (int i = 0; i < split_count: ++i) {
    Bounds3f b0, b1;
    int count0 = 0, count1 = 0;
    for (int j = 0; j <= i; ++j) {
        b0 = bound_union(b0, primitives[j].bounds);
        count0 += primitives[j].count;
    }
    for (int j = i+1; j < primitive_count; ++j) {
        b1 = bound_union(b1, primitives[j].bounds);
        count1 += primitives[j].count;
    }
    cost[i] = traversing_cost 
      + (count0 * b0.surface_area() + count1 * b1.surface_area())
        / bounds.surface_area();
}

PBRT v4 improved this approach by using a forward scan followed by a backward scan ( in total), which drastically improved the performance despite they already use binned BVH building with a small . 1

// forward scan
int count_below = 0;
Bounds3f bound_below;
for (int i = 0; i < split_count; ++i) {
    bound_below = bound_union(bound_below, primitives[i].bounds);
    count_below += buckets[i].count;
    costs[i] += count_below * bound_below.surface_area();
}
 
// backward scan
int count_above = 0;
Bounds3f bound_above;
for (int i = split_count; i >= 1; --i) {
    bound_above = bound_union(bound_above, primitives[i].bounds);
    count_above += buckets[i].count;
    costs[i - 1] += count_above * bound_above.surface_area();
}
 
// Finalize costs
for (int i = 0; i < split_count; ++i) {
    costs[i] = traversal_cost + costs[i] / bounds.surface_area();
}

Binned BVH building (PBRT calls it “buckets”) is another optimization that can be performed. Instead of testing splits between every primitive (a very large number), we group them into a fixed number of bins to drastically reduce the number of splits to check. This can still produce reasonably high-quality results. 4

With all of that done, we can use a simple linear search over the potential splits to find the one with minimum cost. If the minimum cost is still higher than the cost of traversing all the primitives, we just create a leaf node instead of splitting.

Footnotes

  1. PBRT V4 7.3.2 The Surface Area Heuristic 2 3

  2. A Survey on Bounding Volume Hierarchies for Ray Tracing (note) 2

  3. PBRT V3 4.3.2 The Surface Area Heuristic

  4. How to build a BVH – part 3: Quick Builds – Jacco’s Blog