I like ray tracing for making images. It's a simple algorithm, easy to program, and it makes nice results. But it's really slow.

In some previous research on space subdivision, I showed how to build three-dimensional boxes to speed up the process of making a ray-traced image. I then later realized that I could use the same technique to speed up the rendering of a film.

The idea is to represent the film as a single, unified four-dimensional structure. Three of the dimensions are spatial, and one is time, but the program has absolutely no knowledge of that. There are four dimensions and that's all there is to it. I trace four-dimensional rays in this four-dimensional space, using a 4D spacetime acceleration algorithm.

The results were terrific! The resulting images are identical to those that would have been rendered using traditional ray-tracing, but they're created at a tiny fraction of the cost. In essence, I'm rendering the whole movie at once, not frame by frame.

My first real test of the technique was this 64-frame move, "Dino's Lunch." I didn't have access to any tape output devices, so I rendered these 64 frames into a 512-by-512 frame buffer in an Ikonas computer, and then scrolled and zoomed the frame buffer to simulate frames of a movie. Two high-res frames are to the right. The 64-frame movie on the left was shot directly off the screen.

Here are two more examples. These are both procedural animations. The atoms film is 64 frames of a half-dozen balls orbiting in pairs around a nucleus. Notice the motion blur on the balls, and on their shadows. The motion blur doesn't have to be explicitly handled in any way; it just falls naturally out of the spacetime approach. The eight green balls in the lower film are bouncing around in a regular octagon in a 16-frame cycle. I don't have the original images, so these are cleaned-up versions of the figures scanned in from the published article, which themselves were photographed right off the Ikonas screen!

One of the beautiful things about linear algebra is that it just doesn't care about the dimensionality of the spaces involved. A vector is a vector, and that's that. Transform it, build matrices, compute null spaces - whatever you need to do, the dimensionality almost never makes a difference.

So that made implementation of this technique a snap. I modified all my 3D vector algebra libraries into 4D versions, and most of that part of the job was done.

The tricky part was finding an efficient way to build and store the four-dimensional spacetime bounding volumes. I ended up using a hierarchy of multilinear shells out of simple convenience and simplicity; there are probably better ways to go. I also didn't pull in the bounds of those shells as tightly as possible.

You can read all the details in my paper. Here's the complete citation:

Glassner, Andrew S., "Space Subdivision for Fast Ray Tracing", IEEE Computer Graphics & Applications, March 1988, volume 8, number 2, pp. 60-70