ADV Assn - KD Trees

All code for this assignment can be found here

Key Observations:

For same-size KD-Trees, the SHA tended to outperform the median-splitting approach when traversing, though it did have an increased overhead when it came to creating the tree. This overhead was greatly reduced by modifying my SHA algorithm and by implementing binning.


Time to render without KD-Trees:

It took forever so I force-stopped it at the 5-hour mark lol


Method 1: Median Split

In this method of building KD-Trees, I was using a simple median split. This kind of implementation resulted in exceptionally fast times when it came to building the tree itself, but somewhat longer times when tracing through the tree. This is expected, as the median split does not pick optimal split planes 100% of the time.


Bunny Screenshot (Median Split Terminating with Voxel Size 0.1):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 0.149961 seconds, Ray Tracing Took : 53.3895 seconds.


Bunny Screenshot 2 (Median Split Terminating with Voxel Size 0.1):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 0.148001 seconds, Ray Tracing Took : 69.0459 seconds


Bunny Screenshot 3 (Median Split Terminating with Recursion Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 0.138039 seconds, Ray Tracing Took : 53.3901 seconds


Bunny Screenshot 4 (Median Split Terminating with Recursion Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 0.143001 seconds, Ray Tracing Took : 67.6355 seconds


Method 2: Surface Area Heuristic (slow)

In this method of building KD-Trees, I was using a surface area heuristic to calculate the optimal split plane. For each dimension (X, Y, Z) I would first sort all the primitives in the voxel (the value of each primitive when sorting would be the center of its bounding box in that dimension). Next, I would iterate over the min and max values of each primitive's bounding box (if there are N primitives in the voxel, then this runs 2N times) and use those values as the location of the split plane. For each split plane, I would then need to loop over all the primitives in the voxel once more to determine how many were in the "left" and "right" subvoxels (with an added early termination check e.g. since the list is sorted as soon as we reach a primitive that falls after the split plane we can terminate and calculate). I then calculated the SAH with traversal cost 1.0 and cost of intersection test 1.0. Therefore the cost was

COST_OF_TRAVERSAL + numInLeftNode * leftNodeSurfaceArea / parentSurfaceArea + numInRightNode * rightNodeSurfaceArea / parentSurfaceArea.

As you'll immediately notice, the time it takes to build the KD-Tree is huge, but at the same time tracing through the tree is noticably faster than the median split approach.


Bunny Screenshot 5 (Surface Area Heuristic Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 348.607 seconds, Ray Tracing Took : 32.143 seconds


Bunny Screenshot 6 (Surface Area Heuristic Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 349.331 seconds, Ray Tracing Took : 45.544 seconds


Method 3: Surface Area Heuristic (slightly more efficient)

This method is very similar to Method 2, however instead of checking both the min and max values of each AABB for the split plane, I only checked the max value. This was able to reduce the time needed to build the tree while also keeping the time needed to trace the tree fast. Despite being faster, it is still nowhere near the time needed for building using a median split.


Bunny Screenshot 7 (Modified Surface Area Heuristic Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 184.722 seconds, Ray Tracing Took : 32.0841 seconds


Bunny Screenshot 8 (Modified Surface Area Heuristic Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 170.035 seconds, Ray Tracing Took : 42.8825 seconds


Method 4: Surface Area Heuristic with Binning

This method uses SAH but with the added efficiency of binning. Binning is a technique that I discovered thanks to this article After doing some research, I implemented my version by doing the following:

Instead of looping through the primitives and calculating the cost using the planes at the min/max of the AABB for that primitive, I created several bins (when it comes to implementation, this is just an array of ints which serve as a counter for each bin). When looping through the primitives, I increment the bins that they span. For example, if we're looking at the x-axis and we divide the voxel into 16 bins, each with bin_width = voxel_width/num_bins, we might expect a primitive to cover bins 5-7. In this case, we would increment bins 5, 6, and 7. After doing that, I looped through all the bins (notice this is just a for-loop from 0->num_bins -- very efficient compared to the number of primitives) and populated two more arrays: leftCount and rightCount. Each index in leftCount is the number of primitives to the left of that bin, and the same logic applies for rightCount. I then looped through the number of bins once again to calculate the SAH Cost for each bin (note that the split plane for a bin is the left bound of the bin). I then found the bin with the minimum cost, compared it to the current minimum cost, and replaced it if it was lower.

You should notice that the cost of creating the tree is MUCH quicker and MUCH closer to the time for the median split, while also having a travel speed that is comparable to the other SAH methods.

As one would expect, increasing the number of bins results in a better KD-Tree and reduces traversal time.


Bunny Screenshot 9 (Surface Area Heuristic 16 Bins, Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 1.07297 seconds, Ray Tracing Took : 38.6169 seconds


Bunny Screenshot 10 (Surface Area Heuristic 16 Bins, Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 1.221 seconds, Ray Tracing Took : 48.3823 seconds


Bunny Screenshot 11 (Surface Area Heuristic 128 Bins, Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 1.08497 seconds, Ray Tracing Took : 29.6418 seconds


Bunny Screenshot 12 (Surface Area Heuristic 16 Bins, Terminating with Depth 10):

Number of objects in scene: 69451, Size of KD Tree: 1023, Building tree took: 1.08096 seconds, Ray Tracing Took : 44.9101 seconds