Today, we're going to continue our discussion of ray tracing, and specifically, how we compute the intersection of a ray with points on a scene. We want to think about ways to accelerate ray-scene intersection.
An acceleration structure is some form of data structure that we put this geometry into so that we can better short-circuit our algorithm so we don't have to test for lots of different things. There are two different types of data structures - right now, let's look at the non-heirarchal structure (grids).
We start by preprocessing to build an acceleration grid. To do this, we start by taking a collection of objects (e.g. five spheres) and finding the bounding box around this collection of objects. Then, we overlay this bounding box with a grid. We can then store each object in the appropriate locations inside the grid, based on what objects overlap with what cells. Then, we can use this acceleration structure to speed up ray traversal - for each grid cell, we can test the intersection with all objects stored at that cell.
Every time we enter a cell, we test it against all objects inside that cell for intersection.
The benefit of this grid is that it allows us to traverse through the scene in an order that makes sense ("ray traversal order"). We can either terminate when we find the first intersection ("intersection point of entrance"), or keep going until we hit the end of the bounding box.
How do we choose the grid resolution? If we choose one cell, we get no speedup. If we had very, very tiny grid cells, we'd see inefficiency due to extraneous grid traversal. The heuristic that we use is: # cells = C * # objs, where C ~ 27 in 3D.
If we perform our naive grid traversal, we might stumble upon edge cases that return incorrect results! Consider the case above: the first intersection found isn't necessarily the nearest intersection! Thus, in order to ensure that we don't run into this issue, we must check to see if the intersection point is inside the current cell.
When do uniform grids work well? These work well when we have large collections of objects that are distributed evenly in size and space.
When do uniform grids fail? The killer scene for grids is something like a "teapot in a stadium" – we want a smaller grid resolution for the teapot than we do for the stadium – so we have this massive inefficiency when we have an uneven distribution of objects inside a scene!
Often, we want non-uniformity in our ray-tracing acceleration data structures. We can do this using the concept of spatial hierarchies. The following diagram represents a K-D Tree - a data structure based on this notion of spatial hierarchies.
The original bounding box is now divided into non-uniform partitions of space in a tree-like data structure. The leaf nodes in the tree correspond to spatial regions in our bounding box. We can build this tree based on the spatial distribution of objects in the scene!
There are lots of spatial partitions that we can use! These principles will be visualized in 2D, but these concepts all extend to 3D.
Spatial Partitioning Variants