Assignment 2 Lazy KDTree
Tom Brow
Date submitted: 25 Apr 2006
Code emailed: 25 Apr 2006
Description of implementation approach and comments
Lazy tree construction
In my implementation, I chose to expand each node of the tree only when it was intersected. I modified the function KdTreeAccel::buildTree tree such that instead of recursively calling itself on the children after a split, it would initialize either child as a "lazy" node with a pointer to a data structure that stored all of the parameters necessary to call buildTree on that node later. My approach required me to alter kdtree's original node allocation system, since that system does not allow for the tree to be built out of order. Because my new system requires that each node store the index of both of its children, I was forced to switch up to a 16byte node structure. I also made some of the memory chunks that are normally passed through buildTree into data members of KdAccelTree, since they are reused throughout rendering as the lazy tree is constructed.
Lazy primitive refinement
To avoid refining primitives that are not in fact visible to the camera, I refined each nonintersectable primitive (and replaced it with a new kdtree) only when the leaf node containing it was intersected. I did not treat nonintersectable primitives differently than geometric primitives during tree construction, possibly resulting in poorer splits. This would account for the fact that my implementation consistently calls more raytriangle intersections than the original kdtree.
Results
My implementation outperforms the original kdtree in two of the "killeroo" scenes, but performs significantly worse in the "plant" scenes. This may be because the runtime of intersections dominates over the time saved on tree construction and primitive refinement in those scenes.
Final Images Rendered with my implementation of lzkdtree.cpp
killeroosview1.pbrt (Killeroos visible)

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
3.5 
0.0 
inf% 
total time (secs) 
15.9 
16.3 
97.5% 
Num of nodes made 
546.2k 
587.4 
93.0% 
Triangle ray intersections 
675.5k 
826.9k 
81.7% 
"killeroosview2.pbrt (Killeroos invisible)"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
3.5 
0.0 
inf% 
total time (secs) 
14.1 
10.7 
131.8% 
Num of nodes made 
546.2k 
47 
1162127.7% 
Triangle ray intersections 
776.1k 
776.1k 
100.0% 
"killeroosview3.pbrt (closeup)"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
3.5 
0.0 
inf% 
total time (secs) 
17.2 
15.7 
109.6% 
Num of nodes made 
546.2k 
141.1k 
387.1% 
Triangle ray intersections 
645.6k 
1019k 
63.5% 
"plantsview1.pbrt"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
50.3 
0.0 
inf% 
total time (secs) 
630.9 
981.7 
64.2% 
Num of nodes made 
14.9M 
4.0M 
372.5% 
Triangle ray intersections 
20.3M 
27.6M 
73.5% 
"plantsview2.pbrt"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
41.3 
0.0 
inf% 
total time (secs) 
900.9 
1520.2 
59.3% 
Num of nodes made 
14.9M 
5.2M 
286.5% 
Triangle ray intersections 
25.8M 
31.2M 
82.7% 