Objective

In this programming assignment we will implement the Kd-tree, an adaptive spatial subdivision structure, to accelerate the visibility determination process. With the structure, we will be able to ray trace meshes with hundreds if not thousands of triangles!

Approach

Please refer to my solution. Here are the command files (with sample rendered images). You should download and unzip both of these files, then double click on the exe to run the sample program. You will integrate a Kd-tree into this starter project. Please download this starter project and unzip the source code.

The RayTracer Project

1. The command files. There are two new command parameters defined in the provided command files: <kd_max_depth> and <kd_max_in_leave>. These two parameters define the characteristic of the Kd-tree that will be build.

2. The user interface. When running the start project, you will notice the new DrawAccelStruct check box. Try comparing the start project results from the provided sample solution with this check box enabled. The preview system knows how to draw a Kd-tree.

3. RayTracer project Source code.

a. Acceleration/KdTree folder: KdTree.cs, KdTreeNode.cs. These are the minimal required definition in order to support the preview system interactively drawing the Kd-tree. This is where you will build the Kd-tree.

i. ComputeEntryAndExistSignedDistances(): This is a convenient utility function that computes the signed-distance interaction between a ray and the bounds of a KdTreeNode.

b. RTGeometry hierarchy: in order to properly support the building of a Kd-tree, it is convenient for all scene geometries to know its min and max extends. In this case, you must define the Min/Max accessors for Triangle, Sphere, and Rectangle. The implementation for Triangle is provided.

c. RTCore_Visibility.cs: to properly integrate visibility determination with Kd-tree, all we need to do is to modify and initiate visibility computation with Kd-tree in the computerVisibility() and isBlocked() functions. These two functions are properly modified, please do take a look and make sure you understand the change.

This is basically it. Build a correct Kd-tree, and you will see your tracer speeding up almost exponentially.

Credit Distribution

Here is how the credits are distributed in this assignment:

1. Proper Kd-tree respecting the command file parameters: 45%

Looks correct on the Preview system.

2. Proper support for visibility computation 50%

3. Proper submission + Misc. 5%

Extra Credit:

(10%) In addition to the Kd-tree, build a 2-level uniform structure.

(15%) In addition to spatial subdivision, build an adaptive bounding sphere hierarchy.

This programming assignment will count 15% towards your final grade for this class.

WARNING: The number of lines of code for this assignment is actually quite small. However, it is horribly difficult to score partial credit for this assignment. If your Kd-tree is built correctly, with the given functions, it is not too difficult to traverse it. If you cannot build a proper Kd-tree, you may not be able to receive much credits for this assignment! Do start early!!