The Main Idea

Ray Tracing is a technique for creating realistic images of 3D scenes. It’s easy to understand, and easy to program. But it’s really really really slow. This paper showed that you could speed things up a lot by using a hierarchy of boxes that filled your scene.

The basic insight is pretty simple. Suppose you’re on the East end of Main Street, and you need a can of red paint. Your map shows five hardware stores on Main Street. What’s the fastest way to get your paint?

Here’s the dumb way to do it. List the stores in alphabetical order, and visit them in that order. If a store has a can of red paint, mark it on your map. When you’re done, return to your starting point at the East end of the street, and look at your map. Find the nearest store with red paint, go in, and buy it.

That’s obviously silly. You should start at the nearest store, and if they have red paint, you buy it and you’re done. Only if they’re out would you move on to the other stores, working your way down the street until you found your paint.

That’s the idea. It’s pretty simple, but you need to do a little work to convert it into ray-tracing terms. Once you do so, you have an algorithm that’s a lot faster than the old way of doing things.

Here are the original results from the paper. I have a soft spot for these images, because they’re my first published rendered pictures. You can probably tell that these are photographs of a monitor screen. The upper-left is that most canonical of all ray-traced images, mirrored balls and checkerboards! The others are objects made of hundreds or thousands of objects, which in 1984 was a level of complexity that was just unthinkable for ray tracing.

The technique of using spatial subdivision for accelerating ray tracing has gone on to be further developed by many researchers who have taken the approach to levels of sophistication I never dreamed of. The technique is also used, in one form or another, in many commercial products.

My research paper was published in the October 1984 issue of IEEE Computer Graphics & Applications. It was a real honor when I discovered that they’d selected one of my images for the cover!

References

Glassner, Andrew S., “Space Subdivision for Fast Ray Tracing”, IEEE Computer Graphics & Applications, October 1984, Volume 4, Number 10, pages 15-22, 1984