In celebration of the 20 year anniversary of the SIGGRAPH 1989 animation MEGACYCLES created by John Amanatides and Don P. Mitchell while working at AT&T Bell Labs and to further my own knowledge of the mathematics underlying ray tracing, I coded a tiny Java application to render a similar animation.

I still remember seeing the original animation on a VHS copy of The Mind's Eye: A Computer Animation Odyssey back in 1990 and being completely mesmerized by what artists were doing with computers. All of the animations on that VHS would look extremely primitive a few short years later as CGI evolved at an exponential rate, but I’ve always maintained an appreciation of MEGACYCLES to this day. MEGACYCLES is appealing due to its abstract nature, resembling modern art. That was a consequence of the hardware limitations of the era for which it was conceived and decisions made by the artists.

MEGACYCLES consists of six scenes, each 10 seconds in length, portraying unicyclists riding on paths of increasing length and complexity. The final scene shows an apparently infinite landscape of unicyclists on an endlessly meandering path. Watching it always left me wondering what purpose do the unicyclists serve? Why are they riding on top of a labyrinthine path? Where did they come from and where did the path come from? Why do they keep going? Are there really an infinite number of unicyclists in the final scene? Is the path really fully connected and is it truly endless? In recreating the animation, I set out to answer some of those questions.

I want to make it clear that if you have a mixture of artistic talent and programming skills and you want to create your own 3D animation, you don’t need to start by reading up on linear algebra and ray tracing. There is plenty of 3D rendering software available out there, such as POV-ray, Autodesk 3ds Max, Autodesk Maya and RenderMan. I coded this up in Java from the underlying principles simply as a learning exercise.

I started exploring ray tracing while creating entries to the Java 4K game competition. The ray tracing formulas provided a way to render visually appealing 3D graphics in very little space.

 

Before coding up my MEGACYCLES renderer, I studied the high resolution image from the final scene of the animation available on John Amanatides’ homepage. I recognized the path from an xkcd comic. It was the Hilbert curve. The Hilbert curve is generated by iterative steps, each producing a new curve with higher complexity. It is possible to create an image of a truly infinite Hilbert curve by evaluating a visible point on the ground surface and applying the Hilbert curve iteration in reverse. If that technique was used, then the horizon should be completely flat; however, the horizon gradually peaks about 2/3 from the left border of the image. Hence, the path is not infinite, it’s just very large. The peak is actually one corner of the square-shaped bounds of the Hilbert curve approximation and the virtual camera is located close to the opposite corner.

Mathematically, the Hilbert curve is a path without any thickness since it is constructed out of line segments joining points on a plane. The points exist in a square-shaped grid. I chose 256×256 points, a large region which I hoped would conceal the fact that the landscape is not really infinite. To give the path thickness, each point is surrounded by a square separated by 2 other squares.

The 256×256 points are covered by 766×766 squares (i.e. 256 points + 2 squares between points × 255 such regions). Each line segment spans 4 squares, crossing 3 square boundaries between the points. Each of the intersections between a line and a square boundary is the starting point of a unicyclist. The curve visits all 65536 points only once, requiring 65535 line segments. Each of those carries 3 unicyclists. The 2 terminal points also have short line segments that leave the grid, each contributing an extra unicyclist. So, there are 3×65535 + 2 = 196607 unicyclists in total in my animation.

I generated the following 2 test images using those ideas. The horizon actually looks pretty flat.

Next, I constructed a model of the unicyclist out of spheres and cylinders. What appears to be ellipsoids are actually scaled spheres.

Finally, I merged the 2 together.

I completed the image with a fractal generated sky and landscape.

My ray tracer is not a general purpose ray tracer. You cannot feed it a file-based description of all the models to render. Rather, I hard coded everything into the program. Also, it’s not very optimized. It essentially uses bounded-box intersections to solve the ray intersections, but few other optimizations were applied. Also, I wanted 25 samples per pixel at 1280×720 resolution (HD quality). Together that meant that rendering each frame took between 90 and 210 minutes. Each scene contains a loop of 60 frames repeated 5 times across 10 seconds. There are 360 unique frames in total. To save me several weeks of rendering, I wrote the program such that you can launch it with command-line arguments, giving it a range of frames to generate. I asked several of my coworkers to help me split up the work by kicking off the application on all idle computers at their disposal primarily during several nights. I noted all contributors in the animation credits.

I grabbed some royalty-free music from http://incompetech.com/m/c/royalty-free/ and I put it all together with Windows Movie Maker and the SUPER video converter. Here are the results:

Here are some full resolution frames from the animation: scene 1 scene 2 scene 3 scene 4 scene 5 scene 6

Here is the NetBeans project containing the source code and 46K jar for rendering the animation. Feel free to hack it up (LGPL). If you want to render all frames of the animation yourself, execute as:

Make sure the destination directory exists. The rest of the arguments mean scene 1 through scene 6, frames 0 through 59.

2009.05.04