For a class last year (and also as a fun project) I wrote a ray-tracer in C++. There are many resources online explaining ray tracing, so I’m not going to cover that here.

Implementing the basic shapes in a ray tracer (sphere, rectangle, plane, etc) is relatively straightforward. But those shapes aren’t very exciting. If you want more interesting images from your ray tracer, you’re going to have to implement some kind of way to read in and detect triangle-based geometry. I chose to add an OBJ-reader to my ray tracer. There are other file formats, but OBJs are simple and fairly common.

The test for intersection between a ray and a triangle is pretty easy, but you’ll find that it is extremely slow to test each triangle of a large OBJ. Say you want to render the classic Stanford bunny, which is made up of approximately 70,000 triangles. Depending on the efficiency of your ray tracer and the specs of your rendering machine, rendering this object can be extremely slow. My ray tracer, before any optimizations, took almost an hour to render a 600×600 pixel image of the a 5000-face simplified Stanford bunny on minimal settings (1 sample per pixel, no shadows, no reflection or refraction, etc).

Obviously, this is not ideal. We don’t want to wait nearly an hour to see if our image will turn out properly, and it’s not feasible to render any sort of animation when a small frame with no aliasing or shadows takes so long. So how can we improve the running time?

To render the image, we cast a ray from the camera point through each pixel of the image, and test that ray for intersections with the scene objects. But what about, for example, the corners of the image? The bunny is located in the center of the frame, but rays cast through the corner and edge pixels will still check for intersections with the bunny, despite not being anywhere near it. We can improve this case by implementing simple bounding boxes. We give the bunny a bounding box slightly bigger than the bunny’s largest dimensions, and then all the rays we cast initially only have to test for intersection with the rectangular planes of the bounding box, which is much simpler than testing for intersections with every one of the thousands of triangles.

What if a ray *does* intersect with the bounding box? In that case, we again have to test for intersection with each of the thousands of triangles. It would be better if we could limit the number of possible triangles we have to test. We can do this by using a KD-tree. For my ray tracer, I created a KD tree of bounding boxes. Each node in the tree has a list of pointers to triangles contained within the bounding box, a bounding box that surrounds those triangles, and pointers to child nodes.

To build the tree, we start at the root, which contains all the triangles in the object and a bounding box surrounding the whole thing. At each level down the tree, we split on a different axis. We could do it in order – X, Y, Z, X, Y, Z, but I did order by longest axis. For each level of the tree, we:

1. Find the midpoint of all the triangles in the node

2. Find the longest axis of the bounding box for that node

3. For each triangle in the node, check whether, for the current axis, it is less than or greater than the overall midpoint

– if less than, push the triangle to the left child

– if greater than, push the triangle to the right child

Now, this is almost enough to create the tree. We just need to tell the tree when to stop subdividing. We could subdivide all the way down to one triangle per bounding box/node, but that is unnecessary. There are various metrics that can be used to determine when to stop subdividing. I decided to just stop when >50% of the triangles in each child match.

So now we’ve built our KD Tree – how does this help us? In order to gain the benefits this data structure gives us, we have to alter our hit function to use it. I made my hit function recursive – we first check the root node for intersections with the bounding box, and then recurse down the structure until we reach a leaf, where we test the ray for intersection with all of the leaf’s triangles.

After the addition of this KD tree and a quick addition of multithreading (4 threads, for my ray tracer), the bunny shown previously could be rendered in a few seconds – a significant improvement! This tree enabled me to render much more complicated objects, such as this Stanford dragon, at ~100,000 faces:

The full version of this image was 1280×720 with 16 samples per pixel and includes shadows and reflection and refraction. It took about 12 minutes to render.

If you have any questions about this blog post, leave a comment below.

BlogSlayer is the official blog of FrogSlayer, a custom software product development shop in Bryan/College Station, Texas. Our specialty is getting your product to market in 90 days or less. If you would like a free consultation for your project or big idea, email us at howdy@frogslayer.com. You can also connect with us on Twitter, Facebook, or LinkedIn.