How to create awesome accelerators: The Surface Area Heuristic
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.
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.
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!
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!
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 sides 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.
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. Still, if my work helped you out and you feel like giving something back, you can consider supporting me with a donation or clapping if you’d like. It would help me to put more time into preparing and sharing my knowledge with the world. I deeply appreciate your support, truly. Thanks!
All the best, Broman
References (in order of appearance)
- Morgan McGuire, Computer Graphics Archive, July 2017
- J. Goldsmith and J. Salmon. Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl., 7(5):14–20, 1987
- T. Whitted. An improved illumination model for shaded display. Commun. ACM, 23(6):343–349, 1980
- M. R. Kaplan. The uses of spatial coherence in ray tracing. In SIGGRAPH ’85 Course notes no 11., 1985
- T. Aila, T. Karras, and S. Laine. On quality metrics of bounding volume hierarchies. In Proceedings of the 5th High-Performance Graphics Conference, HPG ’13, pages 101–107. ACM, 2013
- D. J. MacDonald and K. S. Booth. Heuristics for ray tracing using space subdivision. Vis. Comput., 6(3):153–166, 1990
- M. Pharr, J. Wenzel, and G. Humphreys. Physically Based Rendering, Third Edition: From Theory To Implementation. Morgan Kaufmann Publishers Inc., 3rd edition, 2016
- I. Wald. On fast construction of sah-based bounding volume hierarchies. In Proceedings of the 2007 IEEE Symposium on Interactive Ray Tracing, RT ’07, pages 33–40. IEEE Computer Society, 2007