Space Subdivision for
Fast Ray Tracing

Ray tracing is a technique for creating realistic images of 3D scenes. It’s easy to understand, and easy to program. But in 1984 it was 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 was a lot faster than the earlier 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.

In the upper-left of this page 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.

I was in a bit of a rush when I made the files for these images, as I was close to finishing my undergraduate degree and I wanted to graduate on time! I wish I’d had a bit more time to pick nicer colors and make the lighting better!

I took these images by pointing a camera at a color screen that was notoriously unreliable: the contrast and saturation levels changed almost every day. Once I’d shot the image, I took my roll of film to the neighborhood drug store, who a week later gave me back 3-by-5 color prints. Over time, I lost the originals. So these are color scans of the printed images from the publication, which I found in a box in the basement.

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 in lots of new directions, gaining yet more speed. The technique was also used, in one form or another, in many commercial software 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