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 presented a way to speed up the process by a dramatic amount.

Here are the original results from the paper. I have a soft spot for these images - they're my first published rendered pictures. As you can tell, they 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.

I was particularly happy that this paper turned into my first cover image!

The basic insight is pretty simple. Suppose you're looking for a can of red paint, and there are five hardware stores on the main street of town. You're at the East end of the street, and you want to find the nearest can of red paint, buy it, and go on about your day.

Here's one thing you could do: go to all five stores, search the shelves, and see if they have a can of red paint. If they do, mark it down on a piece of paper. Once you've made it to the West end of the street and you've checked all the stores, return to the East end of the street. Now look at your list and find the most Eastern store that had red paint. Enter the store and buy your paint!

That's obviously silly. What you would want to do is stop as soon as you found the first can of paint. So of course you would enter the first store, and if they had red paint, you'd buy it and be done with it. You'd know this was the closest can to your starting point because all the other stores are farther away. If this store doesn't have it, then you move on to the next store in a Western direction, and so on.

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.

You can see all the details of the algorithm in my paper. Here's the complete citation:

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