COMP770 Homework 3 -- Ray Tracer



In this assignment, you are asked to implement the KD-tree traversal algorithm and soft shadows. Please finish this assignment based on the simple ray tracing frame work provided by us. You can download it from here.

(Thanks to Christian for the code!)

About using the ray tracing framework:

We provide a very simplified version of our interactive ray tracing framework for this assignment. Right now, the code is only available in the form of a Visual Studio project that you should be able to compile (use a Glab machine if needed). The main ray tracing code is in the project "Common" whereas the demo applications using the ray tracer are Tester and Viewer. The former is a simple application that will render just one frame while the latter is an interactive viewer allowing you to navigate the scene using the mouse (right click the main screen for the context menu). You can bring out the context menu to load in different geometries in the executable directory, set default view point and so on.

The ray tracer is able to load models in VRML and PLY format (we provide several with the package) and render them. You can set options such as resolution etc. in the file options.xml in the same directory as the executable (Output/Debug or Output/Release depending on your compilation options). If the viewer complains about not being able to find options.xml, manually set the execution directory to ../Output/Release in the project options. The ray tracer will automatically generate an optimized kd-tree for your scene when you load it for the first time (may take a couple seconds), then save it to a file. Some statistics about the loaded scene (e.g. camera position, emitter position/intensity, geometry information etc.) are shown in the console window of the Viewer.

Contact Christian at if you have problems getting the code to compile. If you have any questions about this homework, please contact the TA, Zhimin Ren, at


Problems for you to work on:

Problem 1: Implement the kD-tree traversal algorithm.
We discussed in class how a ray can traverse the kd-tree for ray tracing. Using our ray tracing framework, implement the actual traversal code both for normal and for shadow rays using the kd-tree we provide you. The main traversal step is to test the distance of the ray against the split plane (defined by its axis and split coordinate that are stored in the kd-tree node) and then decide which of the two child nodes to intersect with. The basic kd-tree node structure is BSPArrayTree node and provides several methods for accessing all the information you need for traversal. See the example code on how to access the tree structure. Please refer to Christian¡¯s slides on kd-tree for more of the traversal algorithm description. (

Test your code on several example models and note the performance (e.g. FPS) of your traversal compared to the number of triangles. Is it logarithmic?

Notes: Our example implementation tests each ray against every triangle which is very slow, but illustrates how to use the kd-tree structure. We recommend you use the example code only with very small models (e.g. boxes.wrl) since it will take very long to generate images otherwise. You should use the existing method for intersecting a ray against a list of triangles. You will have to implement the main body of the function RayTreeIntersect() and isVisible() in kDTree.cpp to do so (Hint: implement and debug RayTreeIntersect() first, then copy and adapt the traversal algorithm for shadow rays that do not keep track of hit information)

Note 2: You may find that your traversal code has some numerical instabilities when the kd-tree split plane coincides with the triangles inside the node (happens e.g on models with many axis-aligned faces such as the box model). This is normal. If you want, you can eliminate this problem by introducing some fuzzy tests and using a very small epsilon as the error threshold. This is strictly optional.

Extra credit: implement the traversal without using recursion.

Problem 2: Implement soft shadows
One popular method from distributed ray tracing is to use multiple light source samples to generate shadows from area light sources as opposed to point lights. We want you to change the shadow ray code in the ray tracer to shoot a specified number of shadow rays to random samples on each light source. Several of the models in the frame work come with area light source information (called Emitters) that you can use. These emitters have triangular shape. You will have to implement a method that allows you to generate properly distributed point samples on each of the triangle emitters, then shoot rays towards these samples and use the results to find the average light source visibility, then shade the result accordingly.

Your implementation should change the function trace() in Scene.cpp. The current code will go through the array lightlist to test all light sources. Replace this with your routine that goes through the similar array emitterlist and computes the shadows. For a brief introduction to distributed ray tracing, please refer to Christian¡¯s slides (

For one scene of your choice, generate images using 4, 16 and 64 samples for each emitter.


Helpful resources:

The following resources may offer some extra information for an introduction to ray tracing and how to implement soft shadows etc.

1.       On probabilistic sampling (used for shading the soft shadows), please refer to the Global Illumination Compendium.

2.       An introduction to distributed ray tracing.

3.       An introduction book to ray tracing (available as an electronic book on UNC library website).

¡°Realistic Ray Tracing¡± 2nd edition ¨C Peter Shirley