SpeedTracer
While I've been trying to add features gradually to my raytracer over the years, I've never been satisfied with its performance. In the face of projects like OpenRT and CausticGL it was really pathetic that my tracer could only handle about 9k triangles and render them in a mere 10 minutes. Clearly I was doing something wrong and I decided that I needed to do some research.
I ended up coming across a great Siggraph 2005 presentation on using kD Trees to accelerate polygon ray tracing. While this isn't a new concept, it was new to me and I figured that I may as well take what I already knew about raytracing, learn a lot more about kD Trees, find out how you're really supposed to do a ray-triangle intersection, and put something together that runs in realtime.
My First Steps
Hardly an auspicious start, but here's the raytracer tackling 10,000 randomly placed triangles in a kD Tree. This initial version did little more than prove to me that the kD Tree functioned properly and was able to find triangles. This simple scene (no lighting calculations whatsoever) ran at a mere 0.5 - 2 frames per second.
Eventually I was able to load up what was probably the most complicated model I worked with in the old raytracer - a 9k polygon version of the Stanford Dragon. With the flat-shaded mesh and 2 point lights, I was able to push this all the way to 2fps. This certainly beat the multi-minute render times I was getting before but it was nothing to write home about.
Increasing Polygon Count
One thing that drew me to the kD Tree was that it has a way of getting your tracer to check the most likely (and closest) triangles traced first so that you only have to do about 5-10 triangle checks per pixel before finding a contact. As a result, the performance tends to throttle based not on the number of polygons on the scene, but on the number of rays. So, after writing a new file loader I went about seeing just how much of a difference there was by loading up a larger file.
Aside from some drawing errors introduced from improper multi-threading, this 20k polygon model of an angel statue (again taken from Stanford's 3D scanning repository) ran just wonderfully. The only noticeable difference in speed was that it ran faster than the dragon since it tended to take up less of the screen (and because I was able to introduce multi-threaded rendering).
Eventually I was able to render the full 414k model (seen here completely off-center) at an interactive framerate. Talking about models in these polygon counts can get a little abstract, so here's an indication of what a 300k model looks like at multiple zoom levels:
What's incredible about this image is that you can see the framerate increase as the renderer draws more and more of the model. Technically the thing is chewing through dozens of times more data by the time you get to the full zoomed-out view, but because so many rays miss the kD Tree entirely the overall compute time is significantly lower.
Also, you can see that the multi-threading errors are gone in this image. By this point in the process I was storing a copy of the model for each thread (though they could share a common read-only kD Tree, so the memory footprint didn't increase significantly).
Adding Materials
Previously I had been reading raw vertex data (Blender's RAW export) and applying a material to it programmatically. It was time to yet-again rewrite my file reader and move to a format that could handle materials and vertex normals (which can be time consuming to compute from 300k polygons with no connectivity data). For ease of use, I decided to go with Wavefront OBJ format. I had used it in previous projects and it was fairly simple to get colors and materials functioning properly.
Now with a way to specify materials, it was time to add in code for specular highlights and reflection. Since both are so similar, it was fairly easy to implement both at the same time.
And then, eventually, move on to loading textures. At this point, the program only supports windows 24-bit BMP files, and only for diffuse color, but it's a start.
And last, it was time to load an environment map. How else could I show off all those pretty reflections? The tracer supports RAW/FLOAT long/lat panoramas as exported by HDR shop. It should be fairly easy to make one from any light probe. Just leave it in the same directory as the executable in a file named "env.float" and the raytracer will use it.
More Polygons and More Materials
I will readily admit to many flaws in this tracer. For example - kD Tree building is incredibly slow. I'm sure it's my fault as I've seen times for other kD Tree builders and they're orders of magnitude faster, but I simply don't know how to speed that up. I've completely focused on setting things up to trace quickly, not build. As a result, kD Tree construction for very large models can take a very long time, so I needed a way to save trees to reuse later. I developed a way to write a kD Tree to a file and pair it with a Wavefront OBJ file so that if you viewed the same model twice you didn't have to rebuild the tree.
For multithreading I had also stopped storing copies of the triangles in the tree and instead started storing array index offsets. I considered moving to pointers, but this allowed me to also efficiently handle multi-threaded rendering. (Instead of returning the pointer to a universal array of triangles, I can use the offset and pointer arithmetic to get the equivalent triangle in the thread's local storage.) This significantly reduced the size of the kD Tree in memory and allowed me to load larger and larger models.
This is the full resolution Stanford Dragon from the Georgia Tech Large Geometric Models Archive. It clocks in at 871k triangles and renders about as quickly as the 9k version (but at 4x the resolution!). This is where the kD Tree really flexes its muscles. Since this was running without a hitch, it was time to shoot the moon - the 1.1 million triangle Stanford Happy Buddha statue:
Success! I was even able to make an OBJ file for this model to make the pedestal reflective.
And with that milestone reached, it was time to work a little bit more on improving materials and shading. Using a (now) seemingly small 250k triangle model of a Lotus Elise taken from Archive3D.net I set about adding transparency and reflection effects (like Fresnel gloss).
Archive3D.net's models are not free GPL models, but they do allow free private non-commercial use. I'm hoping that they'll agree with me that testing a renderer is a non-commercial use.
Videos
The following videos don't represent real-time output, but they are made from realtime frame dumps then played back at 30fps.
Download the Demo
I've provided a very small demo so that people can get their own idea about what I mean by "real-time." It's certainly not the 30fps we've come to expect from video games, but compared to traditional tracers it's at least fast enough to interact with. In order to preserve my server's bandwidth caps, I've only included 3 smaller models. Scroll down if you want information on creating your own very large files.
To open a .RAW or .OBJ file, simply drag it onto the raytracer executable.
Key Controls
- F1 - Demo mode - the model will rotate automatically, though you won't necessarily get dramatic views out of this mode
- F2 - Model mode - the camera and lights stay static as you move the model around
- W,S,A,D - move the model forward, backward, left, and right
- 1,Q - move the model up and down
- UP,DOWN,LEFT,RIGHT - rotate the model
- F3 - Camera mode - the model and lights stay static with relation to each other as you move the camera around the scene - because the camera starts at position (0,0,0) you may be in the middle of a model when you switch to this mode. If so, just hold S until the camera backs out of it.
- W,S,A,D - move the camera forward, backward, left, and right
- 1,Q - move the camera up and down
- UP,DOWN,LEFT,RIGHT - rotate the camera
Getting More Models
You can create new models using the free open source Blender 3D modeling tool. Open any Blender-readable model file, select the mesh you'd like to export, choose File->Export->Wavefront OBJ. Select a location for the file and click "Export OBJ." From the options menu, be sure to select "Material Groups" and "Normals" - my hastily-built incomplete OBJ file parser will not be able to parse a file without groups or normals.
If you're looking for some free high-quality models, I'd recommend Georgia Tech's Large Geometric Models Archive. While this raytracer can't use any of the models there natively, you can easily import most into Blender and then export the model as you need it.
If you feel like doing some research, look up instructions on using Blender's "Decimate" function. For manifold models (models with no seams) you can reduce the model geometry to any level you want.
Any time you re-export an OBJ file, you'll need to delete the .OBJ.KD file and let the raytracer re-generate it. However, you can alter the .MTL files without needing to do so. Material changes don't affect the geometry and therefore don't affect the kD Tree.
Generating an Environment Map
Download a copy of HDR Shop 1.0. It's free but you'll need to provide some contact information. Just keep in mind that it's academic software, not commercial, so even if you provide info they won't be contacting you about buying stuff.
Next, grab an angular map light probe from the Light Probe Image Gallery. .HDR format is generally the easiest to work with in this case. Open the .HDR file in HDR Shop. Select Image -> Panorama -> Panoramic Transformation. You're going from an Angular Map to Latitude/Longitude. You can use any 2:1 aspect ratio, but for now just use the default resolution. This will create a new image. Save that as a RAW/FLOAT image in the same directory as the raytracer executable and name it "env.float." Speed Tracer will automatically detect the file the next time it starts.