The simplest method to accelerate ray tracing can't necessarily be considered as an acceleration structure, however this is certainly the simplest way to cut down render times. Each one of the grid from the teapot has potentially more than a hundred triangles: with 8 divisions, the grid contains 128 triangles, which requires a similar number of intersection test for each ray cast into the scene. What we can do instead, is ray trace a box containing all the vertices of the grid. Such box is called a bounding volume: it is the tightest possible volume (a box in that case but it could also be a sphere) surrounding the grid. Figure 1 shows the bounding boxes of each one of the 32 Bézier patches making up the teapot model.
We can first test if the ray intersects this box, and if it doesn't, we know for sure that it can't intersect the geometry contained in this bounding volume (figure 2). If we can ignore the triangles from this bounding box, we save 128 ray-triangle intersection tests. Considering that many of the bounding boxes from the scene are likely to fail this test as well, overall, we can save a significant number of calls to the ray-triangle routine. If the ray intersects the bounding box though, all the triangles contained in the volume will have to be tested for an intersection with this ray. In figure 2, we can see a ray intersecting the bounding boxes of the Bézier patches making up the teapot model. Only colored boxes are intersected by the ray, and only the grids contained by these boxes will be tested for an intersection with the ray. Patches contained by the boxes which are not intersected can be safely rejected.
The following pseudocode illustrates this process:
Calculating a bounding box for an object is very simple. We can loop over all the vertices making up the mesh to find the minimum and maximum value for each of the point's coordinate (the xyz points position). These values form what we call the object's minimum and maximum extent and define the two corners of the bounding box (see figure 3). The bounding box of an object is usually computed when the object is built (for instance in the constructor of the polygon mesh class) and stored in a member variable of the object's class (each primitive type may require a different method to compute this bounding box. The bounding volume of a quadratic sphere for instance can be computed from its radius). The following code snippet from the ray tracer shows how we compute the bounding box of a polygon object (line 13). The bbox variable is a member variable of the base Object class (the code is available in the last chapter of this lesson).
The rest of the code is very simple. We will use the ray-box intersection routine we have studied in lesson 7 (Intersecting Simple Shape):
We use the same as with the ray-triangle intersection method to count the number of times the ray-box intersection method has been called. A global variable numRayBoxTests declared in the box.cpp file is incremented using an atomic add operation each time the box intersect method is called. The final value is printed out at the end of the render with the other statistics.
We also created an AccelerationStructure base class which behaves very similarly to an objects. It holds an intersect method looping over all the objects from the scene (line 5). We first test for an intersection between the ray and the bounding box of the current object (line 7). If the test is successful, the ray is then tested against the object contained by the box (line 9). The rest of the code is very similar to the implementation of the trace function from lesson 11. Each time a triangle is intersected, we need to update the closest distance to the intersection point (lines 10-11) and keep a pointer to the intersected object (line 12):
Finally we need to update the trace function. Rather than looping over all the objects from the scene, we just need to call the intersect method from the AccelerationStructure class. If this method returns a valid pointer to an object from the scene, an intersection occurred and we can set the color of the pixel with the intersected object's color:
If we render the scene we used in the previous chapter, we now get the following statistics:
Render time was reduced by a factor of about 34. Logically the ratio between the number of ray-triangle tests performed with and without this basic acceleration structure is about the same: 38. The two number are not exactly the same because of the extra time it now takes to compute the ray-box intersections (9.83 million times). However the benefits we get from using this scheme largely outweighs the additional work these tests require.
The technique presented in this chapter works well in the case of the teapot because the model contains many grids whose resolution (in terms of polygon count) is reasonably low. The ape model on the other hand, is very complex and is made of one single piece. If we were to render this object, we would only save time when the primary rays don't intersect its bounding box (which is, for a typical frame, maybe less than a third of the total number of pixels). For all the over rays, we would still have to perform an intersection test against the hundred thousand triangles making up the model. In that particular case, the bounding box method would only bring a small benefit compared to the brute force approach. It is simple and fast to implement but is clearly not adapted to all situations and for this reason it is not considered as a very good acceleration method.
In the next chapter we will present a technique presented by Kajiya and Kay in 1986 to accelerate ray tracing. This method is based on what's now known as bounding voume hierarchy (or BVH).