Ray Tracing Myths
Ray tracing is not the ultimate solution though, and it's time to tear down the myths that surround it.
First of all, many gamers think that ray tracing is intrinsically a better algorithm than rasterization because "it's what the movies use." That's false. The majority of films using synthesized images (and all of Pixar's) use an algorithm called REYES that's based on rasterization. Pixar added ray tracing to RenderMan, its rendering engine, only later for the production of Cars. But even for Cars, ray tracing was used sparingly to avoid excessive computing overhead. Until then, Pixar used an external module for its limited use of ray tracing, such as for ambient occlusion (AO) effects.
The second widespread myth among defenders of ray tracing has to do with the complexity of the scenes that can be rendered with ray tracing and with rasterization. To get a handle on this, we need to take a closer look at each algorithm.
Here's how rasterization works for each triangle of the scene:
- the set of pixels that the triangle covers is determined
- for each pixel covered, its depth is compared with that of the nearest pixel
The main rasterization loop is based on the number of triangles. The algorithm has a complexity of O(n), where n is the number of triangles. The algorithm thus operates in linear fashion as a function of the number of triangles, since for each frame, the list of triangles has to be processed, one after the other.
Conversely, ray tracing operates as follows:
For each pixel of the frame:
- a ray is cast to determine which triangles are the closest
- for each triangle, the distance is calculated from the triangle to the image plane
As you can see, the loop is inverted, in a sense. In the first case, we take each polygon and look for which pixels it covers, and in the other, we take each pixel and then see which polygon it corresponds to. So, you might think that ray tracing is less dependent on the number of triangles than rasterization, since the number of triangles doesn't affect the main loop. But in practice that isn't so. In fact, to determine which triangle will be intersected by our ray, we also have to process all the triangles in the scene. Here again, partisans of ray tracing say that, in practice, it's not necessary to process all the triangles in the scene with each ray. Using the appropriate type of data structure, they say it's very easy to organize the triangles in such a way that only a small percentage of them need to be tested for each ray, concluding that ray tracing therefore has a complexity of O(log n) where n is the number of polygons.
And in fact, they're quite right. But these pundits are being a little dishonest in that that's also true of rasterization. Game engines have been using binary space partitioning (BSP) trees and other techniques for years to limit the number of polygons that need to be processed for each frame calculated. Another debatable point about this line of reasoning is that the data structure is particularly effective for static data. All that's needed is to calculate data once, and then simply access the data, which produces very good results. But what about dynamic data? There, the data structure has to be recalculated for each image, and to do that, there's no miracle formula. Each polygon has to be examined.
