Acceleration structures

To find what our ray intersects with in the scene, we’ve been performing a linear search over all the primitives in the scene.

• However, linear time is not efficient enough if we have many primitives in the scene.
• Compare our Cornell box scene ($n\approx 10$) to Mario’s OBJ file (thousands of triangles)

Grid acceleration

Divide space into grid of cubes, and each cube stores pointers to the elements inside of it. Then, we only need to check the cubes that our ray travels through

• Reduces time complexity to be $O(n)$, where $n$ is the number of cubes that our ray travels through. Still linear, but can get massive performance increases
• If a primitive spans multiple cubes, we have to store it in all the cubes

Octrees

A 3D version of quadtrees. Each node stores pointers to its 8 node children. We recursively subdivide if there are more than $n$ number of primitives in a cube, where we choose the limit of $n$.

k-d tree

Similar to octrees, but we divide the scene along one axis at a time and we attempt to split the number of objects equally across both divisions.

• Effectively splits our geometry in half with every division.
• For example, if a ray were to only intersect the upper half of the scene, then we can instantly discard half of the geometry of the whole scene.
• Great for a large collection of homogenous primitives, e.g. tons of triangle meshes.

This approach is more flexible than octrees (we don’t have to necessarily split in half exactly everytime), and has a great logarithmic time complexity. However, it is much harder to implement.

Bounding volume hierarchy (BVH)

The previous methods involved creating cells that are guaranteed to not overlap, but this meant that primitives may span multiple cells.

BVHs are the opposite: we create bounding boxes that are guaranteed to contain only one primitive, but these bounding boxes may overlap each other.

• Tighter bounding boxes than k-d trees and octrees, usually
• Easy to build and implement
• Organized as a recursive tree, where we keep grouping bounding boxes together and together until we’ve made up the whole scene (usually, we do this top-down though)
• Traversing the tree is more difficult because nodes overlap
• Choosing where to recursively split is extremely difficult and finding the optimal BVH tree is actually a NP-hard problem
• Great if for scenes with many different, heterogenous geometry