Spacetime Ray Tracing

Ray tracing is a great way to make images, but it’s slow. If you want to make movies, it’s even slower.

In some previous research, I showed how to speed up the ray-tracing of an image using a hierarchy of 3D boxes in space. Then I realized I could speed up the ray-tracing of a movie by placing everything inside a hierarchy of 4D shapes in static Euclidean spacetime.

The beauty of the idea is that the equations behind the rendering algorithm don’t change at all. We just work with objects with 4 dimensions rather than 3. Using 4D objects speeds things up because many of our temporal phenomena (such as object motion blur and shadow motion blur) are automatically “baked” into the acceleration data structure. In other words, to hit a moving object at a given moment we no longer have to adjust its position, orientation, and other geometry to put it where it needs to be at that moment. After all, in spacetime it’s already there! This can be a great time savings if computing an object’s changing location and shape over time is complex or physically-based.

The results are identical to the non-accelerated algorithm, but they come out far faster. Plus, it’s really cool to think of a movie as a single, 4-dimensional structure, rather than as a collection of moving objects!

My first real test of the technique was this 64-frame movie, titled “Dino’s Lunch.” Read the frames of the image (and the other movie grids below) like a book: starting in the upper-left, move right then down. The simple story is that a ball flies past Dino’s face. His eyes bulge in surprise, but he doesn’t otherwise react, so the ball flies by again, taunting him by slowing down and growing large. Dino takes the bait, and swings around so that the next time the ball returns, it flies right into his open mouth. The ball makes its way down his long neck as a traveling bulge. When it lands in his stomach, Dino returns to where he started, ready to start the cycle again.

When I worked on this research I didn’t have access to any kind of modeling software. I drew Dino’s head on graph paper using top, front, and side projections, and measured all of the vertices. Then I typed in each of his polygons, one vertex at a time, into a text file. The spheres for his body, eyes, and nose were the same. To draw the flying yellow sphere, I drew a path on the graph paper, again from all three projections, and marked off 63 roughly equal steps. Those were the keyframe positions. The neck animation was the same, but much trickier because I wanted the neck to form interesting curves. I did everything in pencil, and went through a lot of graph paper, and a lot of erasers! To get his eyes to bulge at the right time, I set the radius for those spheres (and the black pupil spheres) to larger values at the right keyframes. I made the first and last frames were the same so that the animation could run continuously as a loop. While eventually I managed to create and move my characters, I do not recommend this as a viable modeling and animation process!

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 graphics computer. To show the movie, I scrolled and zoomed the frame buffer to show one frame at a time. Two high-res frames are shown above. Note that all the images on this page were shot directly off the screen with a film camera and then developed at the local drugstore, so there are minor haloing and saturation artifacts.

In this 64-frame movie, three pairs of balls are orbiting a central ball, with motion blur on the balls and their shadows. On the right, you can see the orange and white balls are spread out, because they’re moving quickly in this frame, and thus leaving nice, streaky trails behind. Their shadows are also correctly blurred. The motion blur doesn’t have to be explicitly handled in any way; it just falls naturally out of the spacetime structure.

Here’s a shorter, 16-frame cyclic animation. These balls are moving much more slowly than the atoms above, so they’re not causing much motion blur. The eight green balls bouncing around in a regular octagon form a 16-frame cycle. Here I used a much smaller number of rays per frame so you can clearly see the 4-dimensional spacetime sampling at work.

The procedural modeling and animation of the last two examples was a whole lot easier than the modeling and animation of Dino at the top of the page. A couple of months after my research article was published, I got a great kick when Dino was selected for the cover of the May 1988 issue of IEEE Computer Graphics & Applications. I knew it was coming, but it was still a thrill to see him there!

There’s something very satisfying about thinking of a movie as a static, unchanging 4D structure, and that conceptual approach alone would have made this a fulfilling project to pursue. But getting huge speedups as a result makes it even nicer!

References

Glassner, Andrew S., “Spacetime Ray Tracing for Animation”, IEEE Computer Graphics & Applications, March 1988, volume 8, number 2, pp. 60-70