How to create awesome accelerators: The Surface Area Heuristic

7 min readApr 10, 2018

Acceleration structure heat map visualization of the Stanford Dragon

Motivation

We use acceleration data structures for various computer science topics. For example, we use a kd-tree to perform nearest neighbor searches or multidimensional key queries. Accelerators for ray tracing applications enable the fast selection of potential ray-triangle intersections. But why is this necessary? What about a brute-force solution?

Let’s consider the following example: We’d like to render a high polygon mesh with one million triangles. Plus, we’d like to render it in Full-HD (1920x1080 pixels). Without accelerators, we’d have to compute one million intersections for each ray. So if we’d shoot only one ray per pixel, we’d end up with two trillion intersection tests. And this doesn’t even include rays for reflections.

Phew. Let’s just say, it’s a lot of computation!

By introducing acceleration structures, we cut the search space into smaller parts. This is like a search in a binary search tree.

Describing it in a more formal way: Let n be the number of possible intersections. n reaches trillions when considering complex scenes, meshes, and high quality settings. Well built accelerators can then improve the performance of a naive O(n) ray tracing algorithm to O(log n). This can enable interactive ray tracing. Why? Because intersection tests account for around 95% of the performance burdens in complex scenes.

We can conclude: Creating intelligent data structures will skyrocket our algorithm performance.

Image rendered with Path Tracing by Joss Whittle. Wouldn’t it be amazing rendering this imagery in real-time? Accelerators support us accomplishing this ambitious vision.

A Bit of History

There are two common ways to approach accelerator creation. We call the first way object subdivision. It works by grouping objects together like it is performed by a Bounding Volume Hierarchy (BVH). We call the second way space subdivision. As the name suggests, it divides space into sub spaces and assigns contained objects to these spaces. One concrete example for such a partitioning theme is a kd-tree.

BVH visualization of a Stanford Bunny. Cyan boxes are left children, magenta boxes are right children. Images show how a BVH adjusts step by step to the mesh with several depth layers. From left to right: 1, 5, 9, 13.

The algorithms in the spirit of Divide & Conquer are relatively straight-forward. But there is currently no practical way determining the best split position of a node on each level. So we don’t know which objects we have to group together or where we have to cut space into two subsequent nodes for the best performance.

The first computer graphic pioneers had to select the objects within an accelerator in a manual fashion. First automatic creations forced nodes to split in the middle. Other methods stopped subdivision when reaching a predefined tree or hierarchy depth. Since these approaches don’t adapt to the scene structure, they fail for a plethora of scenes. Other uncertainties include the building speed and the selection of the split axis.

These are reasons why the research community assumes that creating an optimal accelerator is an NP-hard problem. So we have to fallback to heuristics or cost models. With them, we can build sophisticated structures with reasonable performance. Surface Area Heuristic (SAH) to the rescue!

SAH Concept

Before we get to the formal descriptions, let’s try to grasp what the SAH trys to do in an intuitive way. The SAH rewards small nodes with many triangles, while avoiding large nodes with few triangles. Consider the following image. Think about what choice of split position (magenta line) would be the best:

If you guessed the third one, you are correct.

The first image shows the result of dividing a node in the middle. This may seem to be okay and not too bad. But there is quite a big chance that a ray might pierce the right child node. Indeed, it is actually a 50:50 situation. If we assume uniformly distributed and directed rays, every second ray will need to perform intersection tests with nearly every triangle. Not very promising.

The second image shows an even worse situation. Dividing the node at the median resulted in both regions requiring a test for more than half of all present triangles.

The last image shows an optimized solution. The SAH chooses the area for most of the triangles as tight as possible. Also, it raises the probability of only having to test a single triangle as much as possible by growing the surface area of the “cheap” left node. Cool!

SAH Formula

In the following section, we’ll have a look at the formal description of the SAH. Bear with me!

MacDonald and Booth proposed the SAH. It predicts the cost of a defined split position on a per-node basis. The model states that:

C(A, B) is the cost for splitting a node into volumes A and B
t_traversal is the time to traverse an interior node
p_A and p_B are the probabilities that the ray passes through the volumes A and B
N_A and N_B are the number of triangles in volumes A and B
a_i and b_i are the ith triangle in volumes A and B
t_intersect is the cost for one ray-triangle intersection.

We can compute p_A and p_B as:

S_C and S_P are the surface areas of volumes C and P (We can simply compute the surface area of a node by summing all faces of a node)
p(C|P) is the conditional probability that a random ray passing through P will also pass through C, given that C is a convex volume in another convex volume P.

These definitions are taken from the book Physically-based Rendering.

Phew. Let that sink in for a minute.

With this formula, the SAH rewards many triangles in tight boxes which are not likely to get pierced by a ray.

We can compute the SAH for various split positions. Then, we select the one with the lowest cost. We can receive possible split positions by taking triangle bounds into consideration. Another method is called binning. It defines a certain amount of linearly distributed positions over an axis.

Further extensions to the SAH include a possible bonus for empty nodes. Also, there are improvements to the SAH assumptions, for example that rays are uniformly distributed in the scene.

Back to the Drawing Board

Now that we know about the formal details, let’s consider our previous example again. We will show why the third option is indeed the best choice according to the SAH. This way, we’ll get a better grasp of the SAH.

Let’s assume the costs t_traversal = 1 and t_intersect = 2. Then, we end up with:

According to the SAH, the algorithm would then choose the third split position because it has the lowest cost. Sweet!

The next figure shows a heat map visualization. It shades a mesh depending on the number of traversed nodes and ray-triangle intersection tests.

Sibenik cathedral heat map visualizations. Left: BVH built by always splitting the nodes in the middle. Right: BVH built with the SAH. We observe that the SAH lowers the number of traversed nodes and intersection tests significantly.

Conclusion

Well built acceleration structures are crucial for interactive ray tracing applications. The community assumes that building an optimal accelerator is an NP-hard problem. Thus, heuristics or cost models are vital to build high quality accelerators in reasonable time. The most prominent model in this field is the SAH. It tries to minimize the area of many adjacent triangles and maximize the area of smaller triangle groups. This reduces probabilities of ray-triangle intersection tests.

For a long time, I did not understand how to create accelerators in an adaptive way. I was very happy when I found out and hope that I supported you to grasp this idea too. If you’re eager to find out more about ray tracing and acceleration structures, be sure to check out Physically Based Rendering by Pharr et al. It’s an awesome piece of work covering a plethora of ray tracing topics, including acceleration structures. At the end of this article you’ll also find a list of references I used in this article.

I’m a great friend of free and accessible knowledge for everyone. If my work helped you out and you feel like giving something back, you can consider supporting me by sharing this article. I deeply appreciate your support, truly. Thanks!

All the best, Broman