Assignment 2 Lazy KDTree
Bill Dwyer
Date submitted: 26 Apr 2006 (ish)
Code emailed: 26 Apr 2006
Description of implementation approach and comments
I relied heavily on the given implementation of the Kd Tree and basically made modifications to the existing code instead of starting from scratch. The PBRT book was incredibly helpful in understanding how the regular Kd Tree was implemented. It was also very clear that the regular Kd Tree was HIGHLY optimized. For example, all the nodes were allocated in aligned memory to make it faster when caching. However, since Lazy Kd Trees are built incrementally, it is not possible to rely on this optimization since nodes can be built in an arbitrary order (to some extent).
After understanding the original Kd Tree layout, I basically modified the node structure to contain the arguments that would normally be passed down through recursion, so that they could be accessed at a later time (i.e. when the interection is calculated). I only classify a node (interior or leaf) when it is called for by the intersection algorithm. After classification, two unclassified children are attached, and their arguments are initialized.
In the end, the speed up of the Lazy Kd Tree is good for interesting edge cases. However, if you don't intend to raytrace large amounts of the scene, it seems silly to have the geometry in there to begin with. For example, if we're only rendering the scene of killaroos from behind a wall, why even bother loading the killaroo geometry in the first place?
Final Images Rendered with my implementation of heightfield.cpp
killeroosview1.pbrt (Killeroos visible)

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
20.0s 
4.2s 
21.0% 
total time (secs) 
40.5s 
100s 
247% 
Num of nodes made 
2.752M 
837.9K 
30.4% 
Triangle ray intersections 
673.3k:4690.5k (14.35%) 
644.2k:10534.5k (6.11%) 
98.7%:224% (42.6%) 
"killeroosview2.pbrt (Killeroos invisible)"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
21.0s 
4.7s 
22.3% 
total time (secs) 
37.7s 
27.9s 
74.0% 
Num of nodes made 
2.752M 
82 
0.00298% 
Triangle ray intersections 
758.4k:2148.2k (35.30%) 
758.4k:2148.2k (35.30%) 
100%:100% (100%) 
"killeroosview3.pbrt (closeup)"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
20.2s 
4.7s 
23.3% 
total time (secs) 
41.6s 
47.9 
115% 
Num of nodes made 
2.752M 
229.9k 
8.35% 
Triangle ray intersections 
644.2k:10534.5k (6.11%) 
758.4k:2148.2k (35.30%) 
118%:20.4% (578%) 
"plantsview1.pbrt"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
22.1s* 
1.7s* 
7.69% 
total time (secs) 
816s 
1619s 
198% 
Num of nodes made 
14.866M 
6.581M 
44% 
Triangle ray intersections 
20.257M:421.737M (4.80%) 
20.257M:421.737M (4.80%) 
100%:100% (100%) 
"plantsview2.pbrt"

KD Tree 
Lazy KD Tree 
Ratio 
build time (secs) 
21.0s* 
1.3s* 
6.19% 
total time (secs) 
1465s 
2152s 
147% 
Num of nodes made 
14.866M 
7.991M 
54.0% 
Triangle ray intersections 
25.930M:754.291M (3.44%) 
25.930M:754.291M (3.44%) 
100%:100% (100%) 
omg, the last render took forever!
* this data was abnormal (there were many 100% progress bars presented after the intial readout of this final time so it might not be entirely accurate).