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.
http://www.cs.unc.edu/~lauterb/RT_COMP236.zip
(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 cl@cs.unc.edu if you have problems getting the code to compile. If you have any questions about this homework, please contact the TA, Zhimin Ren, at zren@cs.unc.edu.
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. (http://www.cs.unc.edu/~dm/UNC/COMP236/LECTURES/Ray-Tracing1.pptx)
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 (http://www.cs.unc.edu/~dm/UNC/COMP236/LECTURES/Ray-Tracing2.pptx).
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.
http://www.cs.kuleuven.ac.be/~phil/GI/TotalCompendium.pdf
2. An introduction to distributed ray tracing.
http://www.cs.dartmouth.edu/~fabio/teaching/cs52-winter08/lectures/16_DistributionRayTracing_Web.pdf
3. An introduction book to ray tracing (available as an electronic book on UNC library website).
¡°Realistic Ray Tracing¡± 2nd edition ¨C Peter Shirley