Ray Tracing Example

Go to the user instruction page that explains how to run this application.

Introduction

One of the best ways to learn a new programming language is to start with some existing, nontrivial, and well-written program, examine how it is written, and then modify or extend it in interesting ways. In fact, this is a good way to learn programming, period. The advantages of this approach is that the student sees code that is idiomatic and well designed. The initial experiments can be quite small, avoiding the "startup hump" that can be quite large when conceiving a system from scratch. Finally, since the student is responsible only for incremental improvements, even the initial version of a program can do something interesting or exciting, more substantial than the usual simple pedagogic example.

The example in this section has been derived from Paul Graham's ANSI Common Lisp (Prentice Hall 1996), pp 151-158. Although the amount of code is not large, it does something interesting and is easily extensible. The program implements "ray tracing" to draw (or "render") nontrivial computer graphics scenes.

For instructional purposes, this program has been set up in two portions. The first component is the ray-tracing system itself, essentially the example from Graham with a few improvements. It consists of a few lisp files that can define and render a scene in several graphic formats. The program emits an image either by writing a file or by writing to a stream. The renderer can be invoked directly from the top-level Lisp listener and the resulting image file can be viewed with a web browser or any appropriate image viewing program.

The second portion is a web-page-based controller for the ray-tracing program. This employs an existing open-source HTTP server (AllegroServe) written in Lisp, upon which runs a program that generates a HTML form that specifies the scene to be rendered. The web page dynamically computed by this code is served by the HTTP server. The server calls the web-page generator when the user visits the page, and the web-page generator in turn calls the ray-tracing system to generate images that are also served back to the user by HTTP.

Don't misunderstand the use of a HTTP server to "control" this application. Often a web server operates as a real web server, serving data to a large number of widespread internet clients. But a HTTP webserver is also useful in other contexts. An HTTP server may be included in some other sort of server application for the sole purpose of providing a "control panel" interface. This control panel might be protected with password or other authentication, and might be intended only to serve a single, rarely-connecting client. But HTML is often sufficient for a control or logging interface and (given the easy availability of a HTTP server and HTML generation software) is much easier and faster to implement than writing complex traditional user interface code. While the ray tracing web application can serve multiple users at once (notwithstanding that the application is limited by its heavy CPU load), one can also imagine that the web interface is intended for use by a single user on the local machine.

The Implementation

These two applications are built using defsystem, a semi-standard Common Lisp system construction tool. See the file defsys.lisp. defsystem forms define systems that are composed of multiple files, and allows specifications of the dependencies between files and between systems. It is similar in some ways to Unix Makefiles and the project tools of some other development systems. Once the defsys.lisp file is loaded into lisp the basic ray tracing application can be compiled (or recompiled) by executing the form (excl:compile-system :ray-trace) and then executing the form (excl:load-system :ray-trace) to ensure that the current compiled files have all been loaded. The program can then be tested by executing (ray-test) which will generate a file spheres.bmp that can be viewed in some appropriate image-viewing program. See the code to learn how to generate a gif file on Unix systems if that is easier to generate and view on your local system.

These are the other files comprising the basic ray tracing program:

The web control page depends upon (i.e. contains) the basic ray trace application. It itself adds only a single file, but also requires that the AllegroServe HTTP server and another small xml-generator system be loaded. Instructions for obtaining and comppiling AllegroServe are below, but these are the other files added by the web control application:

You can click on the above links to browse the source or use your browser to save the files to your local machine. Alternatively you can download all the source code as a single gzip'd archive.

AllegroServe is an open-source HTTP server that runs in Allegro CL (and which may plausibly be ported to other implementations). If no one has provided it for you locally you can download the source and documentation from the repository at http://allegroserve.sourceforge.net/. At the time of this writing AllegroServe does not use defsystem so you'll need to follow the build instructions it includes. At the time of this writing, the following will work:

Download the source and extract it into a aserve subdirectory of this raytracing application.
Start your ACL image in the aserve subdirectory.
Execute this command: :ld load
Execute this form: (make-aserve.fasl)
Execute this command: :exit

This will create the file aserve/aserve.fasl which will be loaded by the web ray trace application's defsystem. You will not need to modify or even examine the code of AllegroServe in order to run and extend the ray tracing application; you will only need to modify the code in webpage.lisp. However, the source is available if you want to explore other facets of this Lisp web server. The server code incidentally contains the simple code needed for a Lisp application to operate as an HTTP client, and very interesting web applications can be written based on this code. AllegroServe also supports operation as a proxy server, but all these things are beyond the scope of the current application.

The Ray Tracing Model

[This section needs to be written, and some diagrams added in case Graham is not available to the student. For now, refer to Graham. Also, there are some very useful collections of information on ray tracing and image rendering on the web. One in particular is http://www.mrl.nyu.edu/~dzorin/rendering/lectures/. The PDF documents there show much of the mathematics of ray tracing and lighting models.

Suggested Extensions to the Ray Tracing Application

There are a great many ways the ray tracing code can be extended. Graham suggested some of these, and others are new here. Feel free to try some or devise your own, but it would be wise to discuss any particularly ambitious plans with your instructor or other Lisp guru before getting in over you head.

Since the web-based application contains the smaller ray-tracing system, and since the HTTP server itself is esoteric and somewhat large, it is probably best to start by examining and making small changes to the ray-tracing code. After some success at this, perhaps by adding some capabilities to the ray-tracing code, you can extend the web form to support those new features. This will require a basic knowledge of HTML, but HTML is fairly simple and well worth learning at least the basics. A lot can be extended using only the existing HTML-generating code as a model; but for those who like the full treatment, the full definition of HTML (currently HTML 4.01) supported by most browsers can be found at http://www.w3.org/TR/html401/.

How would you go about making this code execute faster? Some observations and ideas are discussed in a separate section below, and indeed, this code can be made a lot faster.
The spheres modelled by the program are characterized a single uniform color over the entire surface. Extend the program to handle non-uniform surface color. One way to do this is to redefine the surface-color function (which is originally just a defstruct accessor) to be a generic function that takes an object and a point on that object. But to do this, you may need to add the notion of orientation to the sphere object -- in other words, instead of a sphere's position being characterized by four values {X,Y,Z,Radius} it would be characterized by seven values {X,Y,Z,Radius,[Vx,Vy,Vz]}. The [Vx,Vy,Vz] triple denotes the axis of the object. One convention is to represent this triple as a unit vector (i.e., Vx^2 + Vy^2 + Vz^2 = 1) but another is to use code rotations in radians around the three axes. These are equivalent in power, but one or the other may be computationally more convenient.

Once the spheres representation and surface-color have been extended, it should be possible to support interesting color shadings, patterns, and even images or text wrapped around the sphere.
Once the program can represent objects with orientation, extend the program so that it can render solids other than spheres. One typical approach is to model solids as a set of vertices straight-line edges, connected in turn by planar faces. The hard part is writing code that will compute the object's intersection with a ray. If the objects are restricted to those with some number of finite planar faces, the problem can be approached by computing checking the intersection with each such plane. Of course, this can be costly in time for complex objects. But usually is best approach is to do a rapid prototype, then optimize.
Sometimes it's useful to examine your scene from a different viewpoint. The default view is from {0,0,0} directed into the ZM axis [0,0,1]. A possible implementation would be to add six additional fields to the control form which specify the new eye point {x0,y0,z0} and view direction [0,0,1]. The direction vector may need to be normalized to a unit vector internally. An additional button would be useful to reset the view point and direction to the original value. Note that all this can be implemented entirely in the web page control by applying the geometric transform of the viewpoint to the object parameters before they are passed to the ray-tracing code.
Another interesting and popular image-rendering feature is making objects transparent. (The term "semitransparent" would be more correct since rendering completely transparent objects would be silly.) Treatment of surface effects, what happens when light strikes a surface, has been well developed in the animation industry, and effects Texture, transparency, translucence, and reflections have almost become cliches of the medium. Transparency is one of the simpler ones to model and least expensive computationally.

When light strikes a surface, some is absorbed (and lost), some is scattered, some is reflected, and some passes through. [Finish this explanation.]

To implement transparent objects you could encode the transparentcy as the fourth scalar of the color rgbi. The ray tracing algorithm would be modified so that instead of finding the closest intersection of each a ray with any object, each ray trace would collect all intersections. (Generally, there are two intersections for each object the ray strikes, the entry and the exit.) These would then be sorted on distance. The color to paint the image point represented by the ray would then be computed by iterating over the intersections from closest to furthest (and finally the background color, which obviously should have zero transparency). If transparency T is considered a value between 0 and 1, at each intersection the ray accumulates the indicated surface color times (- 1 T). The ray then continues through the intersection accumulating T time the color iterated over the more-distant intersections. [Is this clear enough?]

These changes aren't so very hard to accomplish. But be sure that they are done in a way that will continue to work independently if some of the other changes here are attempted. For instance, if the code is designed with a little forethought it should be possible to implement transparency independently of the extension to non-sphere objects.
When a large sphere is rendered at high resolution, you may see jagged edges ("jaggies") on the borders that are close to being horizontal or vertical. Research antialiasing techniques on the web and see if you can implement it in this program.

The model can be changed in several ways. [Finish this.]
The lighting model in Graham's program is very simple and even so has been described rather inaccurately. He implies that it models a source of light coincident with the view position. But if this were so, the amount of light reaching a remote surface would decrease with the square of distance, and the amount of light returned to the view position would also decrease with the square of distance, meaning that intensity of illumination would fall off with the fourth power of distance. (This is why photographic flashbulbs are so ineffectual against distance.) Graham's program rather models the effect of a large illumination source at great distance behind the viewpoint, so large and so distant that there is essentially zero falloff over the distances to the objects. This kind of planar illumination is the kind provided by the sun.

The model can be changed in several ways. [Finish this.]
Add code and necessary controls so that the form data can be to save to and restore from data files. Try to do it in a way that will continue to work if the nature and kinds of objects and their attributes are extended as suggested above. Hint: It would be natural to save the objects in the scene in XML format, given that XML-emitting code is already present in the program. To load a file back in requires an XML parser. Such a parser is available in Allegro 6.0 and later.
So far this ray tracing application generates only still images. It could be extended to do moving images (animaation) if two problems are solved:
- Figure out how to generate some appropriate moving-image format. Windows avi format is largely based on the dib format (bmp) already supported by the program, so it would be one obvious choice. Windows avi format is based on Windows dib format which our basic ray trace program already supports, but avi has many extra complications and the description of the format is based on obscure C++ data structure definitions, so expect this extension to be both tedious and hard.
- Figure out some high-level to control the animation. You can control objects by algorithmically specifying its trajectory in space/time, or some kind of physical or other model of object interaction can be devised (featuring gravity, collision, etc.). Consider allowing the view point (camera) to move as well. (This requires controlling all six degrees of freedom.)
Warning: This one is hard, so don't attempt it unless you have lots of time and nothing serious depends upon success.

Optimizing the Code

Graham's code is a beautiful example of a clean rapid prototype but it is hideously inefficient. This doesn't matter so much in a quick prototype, but it would matter a great deal if this code were ever used in production. Efficiency is nearly always essential for any sort of image-generation or -manipulation software because what the user is willing to ask the software to do is limited by how long he can wait for it to be done. It can be an interesting intellectual challenge to make the code faster, and even if it isn't interesting, if the code executes faster it is a lot more pleasant to perform other experiments with it. The code inefficiency comes from two entirely separate areas:

The computation is implementationally inefficient because Lisp operations are by default fairly generic. This facilitates rapid prototyping, but has runtime costs. Often a Lisp programmer will want to address these intelligently after the prototype works.
The computation is algorithmically inefficient, that is, it does computations that are unnecessary or in ways that are otherwise wasteful.

In practice both kinds of inefficiency need to be addressed. Details of code efficiency are mostly specific to Lisp (although some, such as careful use of integer instead of float arithmetic, apply across many languages). Algorithmic efficiencies often apply similarly across all languages.

The best way to address coding efficiencies is first to determine where the program is spending its time. It doesn't make much sense to try to improve the code efficiency in a bit of code where the program only spends a small fraction of its time, because even if you could make the speed of that code infinite, the most you would do is to eliminate that small fraction of the total time. Instead, you must focus on that portion of the code where the program actually spends significant time. In most programs (especially this like this one that do a lot of repetitive numeric calculation) just a few functions, and sometimes just one, will represent the largest portion of the execution time. Implementations have tools for discovering where an application spends its time. In Allegro, that tool is the profiler. See the documentation, but typical application to the basic ray tracing application might be done this way:

(prof:with-profiling ()
  (ray-test :res 2))
(prof:show-flat-profile)
(prof:show-call-graph))

Once the expensive functions in the application are identified you can try to improve their speed by judicious rewrites, by adding type (and optimization) declarations, and sometimes by inlining certain operations using macros and compiler-macros. The subject how to do this is too involved to include here, but see sources such as the Compiler chapter of the Allegro documentation. As you tweak the code, repeat the profile to check the effect of the changes. When optimization is successful, the total time and the time consumed by the routines receiving attention both go down, but the relative time consumed by other routines will (obviously) rise. You can continue giving attendion to the code so long as you feel it is productive.

There are several algorithmic inefficiencies in the prototype application that are well worth eliminating. One in particular is the way each ray trace checks for intersection with each of the multiple spheres (or other objects) in the scene. The shortest-distance (most foreground) intersection is returned and rendered. The several functions comprising this intersection computation is obviously where almost all the execution time is spent.

This algorithm is linear in the number of objects in the entire scene, regardless whether the area subtended by each individual sphere is small or large. The code wastes a lot of time checking for intersections with spheres that are far from the image pixel being traced. This can be improved by computing a bounding box for each sphere prior to doing any ray tracing. An object's bounding box is (typically) a rectangle defined by the maximum and minimum X and Y extents of the object in the viewing plane. When computing the image at a view point (i.e. the ray trace {x,y} one obviously need compute the intersection only for those objects for which the point falls inside the bounding box. While computing the bounding box for each object takes a little time, it needs be done only once for each image rendering. After the boxes are computed, the objects can be sorted on theit ordinates so that as the viewplane raster is scanned, spheres that are candidates for intersection can quickly be added and removed from the set of active objects. There are known graphic algorithms for maintaining lists of objects based on two-dimensional bounding boxes, but with a little experimentation it shouldn't be too hard to derive something good enough. The profiler can be used to determine whether and when the bounding box implementation is efficient enough not to contribute significant overhead to the total calculation.