Assignment 2 Lazy KDTree
Tarang Vaish
Date submitted: 26 Apr 2006
Code emailed: 26 Apr 2006
Description of implementation approach and comments
The implementation approach was to not refine any primitive in the constructor and lazily refine them on intersection with some rays. I tried to add more primitives into this kdtree initially but found the complexity overwhelming to debug and complex. Instead I replaced unrefined primitives with a new kdtree build upon the refined primitives of this primitive. This helped reusing the same kdtree implementation recursively.
Refinement is tried to be as late as possible, bigger leaf nodes are split into small chunks, so that a bunch of unrefined primitives do not get refined when a ray intersects a large node. Furthermore, intersection of a ray with the bounding box of the unrefined primitive was checked to make sure refinement was absolutely necessary. I found the number of primitives in any leaf to be a critical factor to performance and laziness. Longer depth can lead to longer access time to a primtive and shorter depths mean checking many primitives at the leaf nodes. The heuristic of max depth in the kdtree implementation also makes more sense when number of primitives are large.
I appreciate the original kdtree implementation for cleverly optimizing data structures and minimizing overheads. The kdTreeNode was kept the same size of 8 bytes as it is proportional to the number of primitives, I used a lazy bit in the pointer variable of this node to not check for more splits if this leaf node is no longer lazy. I refactored the Intersect, IntersectP functions into a commong Isect funtion.
I tried building part of the tree initially, but it doesnt help in performance because of the way we have to choose the memory layout. Since a node's child may not be adjacent to itself, building the tree to any depth is not going to be any better than building it later. The kdtree implementation used to benefit from this as they used to build all the tree once and were thus able to layout the parent leftchild nodes contigously. So I decided to not do any initial building and be lazy on buidling it in intersection functions.
Final Images Rendered with my implementation
killeroosview1.pbrt (Killeroos visible)

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
16.4s 
0.19s 
1.15% 
total time (secs) 
29.1s 
35.1s 
120.6% 
Num of nodes made 
2.752M 
2.545M 
92.4% 
Triangle ray intersections 
673.2K 
821.4K 
122% 
"killeroosview2.pbrt (Killeroos invisible)"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
16.3 
.6 
3.68% 
total time (secs) 
26.6 
13.6 
51.1% 
Num of nodes made 
2.752M 
52 
.00018% 
Triangle ray intersections 
758.4K 
776.1K 
102.33% 
"killeroosview3.pbrt (closeup)"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
16.3 
0.5 
3% 
total time (secs) 
30.637 
26.3 
85.84% 
Num of nodes made 
2.752M 
645.9K 
23.47% 
Triangle ray intersections 
644.1K 
901.3K 
139.9% 
"plantsview1.pbrt"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
42.5 
0.22 
0.5% 
total time (secs) 
612 
1365 
223% 
Num of nodes made 
14.862M 
6.6M 
44.4% 
Triangle ray intersections 
20.291M 
26.409M 
130.1% 
"plantsview2.pbrt"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
53.2 
0.22 
4.13% 
total time (secs) 
928.9 
2386 
256.86% 
Num of nodes made 
14.862M 
7.315M 
49.2% 
Triangle ray intersections 
25.843M 
29.523M 
114.2% 