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
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
The surface area heuristic express the above conditional probability as the proportion of surface areas:
where
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 (
// 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.