Rasterization vs. Ray Tracing and the Size of your Data

We all learn about rasterization and ray tracing in introductory computer graphics classes if we are computer graphicists. But, at a fundamental level, what it the difference? Teaching computer graphics has made me think about these things again. As an exercise, challenge yourself to write pseudocode for each algorithm in exactly 4 lines. Then keep reading.

I asked a number of graphics PhD students to do this tonight, and they dove straight into details about projecting triangles and computing viewing transformations, etc. But there is a fundamental difference at a much higher level that interacts with the way we make data to affect the computational complexity of these algorithms. My 4-liner versions of the algorithms look like this:

Rasterization:
for each shape:
for each pixel:
if the shape is visible in the pixel:
compute the color and draw it in the pixel

Ray tracing:
for each pixel:
for each shape:
if the shape is visible in the pixel:
compute the color and draw it in the pixel

These look almost exactly the same. We're really just swapping the order in which we iterate over data. But renderers, in practice, have to process a _lot_ of data. Way more than we can hold in memory, in the case of film quality scenes. And performance is tied to data locality, since data locality lets us avoid having to move stuff in and out of memory a lot, which makes things really slow. That constant on the memory transfer is big.

In either algorithm, we have to make an image, so we bite the bullet there and keep the image data around. It's also of fixed size and usually fits in memory, so it's not much of an issue. Shape data grows without bound, however. My experience in film production tells me to be careless about the size of your shape data until it becomes a real problem for other people, because artist time is really really really expensive and processor time is just expensive (until you hit your memory limit, where it becomes a constant multiplier on the next artist down the pipeline). So we push the size of shape data over the limit of what fits in memory on a regular basis.

Rasterizers deal with this by only processing each shape once, throwing the current shape data away at the end of the inner loop and ignoring global appearance interdependencies. Shapes are expensive to read in (we're accessing disks here), but it's O(n) in terms of how many times we read in shape data.

Ray tracers usually have to read all the shape data multiple times, since a lot of it has to get tossed out of memory _for each pixel_, since many shapes will often push memory limit bounds all on their own. And then ray tracers figure they've taken the performance hit already, so why not try to solve some of the global appearance interdependencies while we're at it. And now we have brute force solutions to the rendering equation, if we have good BRDFs. O(n^recursion depth), if my big oh is right (my math is bad on Fridays). Yikes. So we do things like bounding recursion and probabilistically killing recursive calls to keep this under control. Even if we completely ignore global appearance interdependencies, we have O(kn), where k is our number of pixels.

And when n is big, as it is for high-quality algorithms, that can mean days or weeks instead of minutes.