Ray Tracer Project Report
Ammon Bartram
12-14-08
I set out to develop a ray tracer with enough features to render visually interesting images. I had not studied ray tracing before, however, and I was uncertain how long it would take to build the basic framework. Acknowledging the limitations of the time frame, I decided to emphasize lighting and rendering calculations, and only support a few primitives (these primitives would be transformable by arbitrary matrices, however). I wanted the renderer to handle materials with diffuse, specular, emissive, reflective and transparent channels, as well as bump mapping of normals and refraction of rays through solid objects. Each materials channel would be specifiable as either a flat color of as a mapped image. These materials would be applied to simple sphere and plane primitives. In my initial specification, I also left open the idea of an XML file format to allow the creation of more complex scenes.
Design:
To keep the project manageable, I decide not to design with performance in mind. I would build a simple and intuitive, not fast, ray tracer. My initial design had five primary components: a base primitive, a base light, a color source, a material, and a scene manager.
The base primitive class provides a single method which takes a ray and returns an intersection point. To keep primitive classes free from constraints while still allowing for the arbitrary transformation of primitives, I designed the system to transform only rays. Before a ray is tested against a primitive, the ray is transformed by the inverse transformation of the primitive. And after the intersection point is found, it is transformed again by the forward transformation of the primitive. This design means that intersection calculations only have to be done against primitives in a default orientation, which removes the requirement that primitives themselves be transformable by a matrix and simplifies intersection calculations.
The base light class would represent a light. To allow for different types of light, the base light class simply defines three methods to, given a point, return a list of vectors for shadow testing, and diffuse as well as specular light values.
The color source class is an abstraction of one channel in a material. Color sources take a set of texture coordinates as well as a sample scale (derived from the distance to the camera and the dimensions of the texture as mapped in the image) and return a color. A flat color source class would simply return a single color without considering the parameters. A texture color source, however, would sample an image at the given coordinates and scale and return the color.
The material class simply consists of a list of color sources, one for each channel in the material, as well as the object parameters of refraction index and Phong highlight exponent.
The scene manager is the central ray tracer. It maintains lists of lights and primitives as well as camera information, and does the actual ray tracing. It has a method to cast primary rays from the camera location, and a method to recursively recast secondary rays. This method, given a ray, simply finds the nearest point of intersection in the scene, applies lighting calculations using the intersected object’s material, determines if the point is in shadow, and finally recursively casts secondary rays (taking into account bump mapping and refraction) to calculate the reflected and refracted component of the point’s color.
Implementation:
Ray tracing, in spite of the complex images that it can produce, is simple and intuitive. I had the rare experience of a programming project going faster than planned. I did encounter a few problems; my initial naive texture mapping routine ended up sampling thousands of texels when drawing pixels at great distance, and I put in a coffee-fueled night getting mipmaps to solve this problem. But everything else followed my initial design smoothly, and, just ten days into the project, I had essentially met my initial specification. Thus I got to sit down and add features.
First I added tori. The only complication was finding the intersection between a torus and a ray. Substituting the parametric equation for a ray into the equation for a torus gives a 4th degree polynomial, I realized after some algebra. While there is, of course, a closed-form expression of the roots of 4th degree polynomials, it is pages long. So I ended up writing a numerical root finder for arbitrary degree polynomials. The idea, basically, is to find the polynomial’s critical points by recursively finding the roots of the derivative. Any roots, then, must be bracketed by these points (and an upper and lower limit on the range of interest), and can be found by testing the sign of the function at these points and using the false position method (I used Newton's method at first, but this had a tendency to get lost in the polynomial’s hinterlands never to return).
Next, I added volume based transparency (as opposed to surface transparency). This was simply a matter of determining if we were casting a ray from inside of the primitive with which it intersects (as will always be the case for the refracted secondary ray from a primitive with volume) and if so, using Beer’s law to calculate the attenuation (Beer’s ‘law’ empirically models the exponential absorption of photons as they travel through a partially opaque medium).
Mesh primitives came next. To keep things simple, I wrote a loader for *.raw mesh files (simple lists of vertex triplets), and tested rays against meshes by exhaustively testing for intersection with every triangle (bounding spheres are used optimize misses).
Finally, I added area lights with soft shadows. The idea here was to create a light class where light emanated from a square in 3d space rather than from a point. Shadows, then, rather than having sharp edges, would have soft edges as the area light became partially obscured. I used Monte Carlo sampling to calculate how much light reached specific point. A number of sample points are spread over the light, and ‘jittered’ by random amounts (jittered evenly spread points gave better results than truly random samples), and shadows as well as defuse and specular lighting was calculated as the average from all of these sample points.
To take advantage of these new features, I created a scene file format. Rather than use XML, as originally considered, I decided to use a scripting language that I wrote in Spain (AmmonScript for lack an another name). I designed AmmonScript to allow easy extension in java, so integrating it with the ray tracer was simple. And using scene scripts rather than simple scene files made it possible to support animation. Specifically, I created a library of functions to create and modify ray tracer primitives and materials. Scene scripts, than, are simply scripts that define two functions (lambda expressions in AmmonScript): one to initialize the scene, and another in update the scene in between frames.
Weaknesses:
This ray tracer has only been a month-long project, and some issues consequently remain. The first is optimization. Rendering an image with more than a few object, complex materials and soft shadows presently takes several hours. It does not need to be this slow. Storing mesh faces in a BSP-tree and primitives in a Kd-tree (the tree type recommended in the literature) would drastically reduce the number of intersection tests performed. Additionally, my design choice of transforming rays and not primitives results in a vast increase in the number of matrix multiplies. Modifying intersection methods to test against transformed primitives (in most cases no more costly than against a primitive in a default orientation) and transforming all primitives once would produce a significant saving. To still allow for untransformable primitives, the primitive class could return a flag indicating whether it needed rays in model space, or whether it could handle world space. And beyond optimization, mesh support and texture mapping currently have some caveats. Raw mesh files do not contain normals, and my mesh loading code assigns a normal to every vertex that is the average of every face touching in. In cases of sharp corners or small faces, this can produces strange results. Additionally, texture coordinates and texture axes (used to convert texture space to world space in bump mapping) are calculated for meshes via sphere mapping. This can lead to severe texture deformation on less-than-spherical meshes. And even for other primitive types where texture mapping is correct, there is presently no support for scaling, rotating or otherwise customizing texture coordinates (it would, however, be relatively simple to add such support).
Further Development:
Were I to continue this project, I would start by fixing the abovementioned weaknesses. Beyond this, Boolean operations with primitives (not, and, or) would allow more complex geometry without resorting to meshes, and could be implemented relatively easily using the decorator design pattern. Similarly, the color source class could be extended with the decorator design pattern to allow complex combinations of texture maps. It would also be very interesting to attempt to add photon maps, or a true global illumination algorithm, perhaps path tracing. These techniques, however, would require fundamental changes to the program’s structure.
Conclusion:
I am satisfied with this project. The intuitive nature of ray tracing allowed me to go beyond my initial specification and produce nuanced images. The project additionally allowed me to use my scripting system for the first time, and it was a pleasure for me to see it in operation. My ray tracer is slow. It takes hours to render images that other ray tracing packages can produce in minutes. High performance, however, was not a design goal. I designed the ray tracer to produce complex images with as simple an algorithm as possible. And in this regard, the ray tracer is a success.