Assignment 2 Lazy KD-Tree
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
killeroos-view1.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% |
"killeroos-view2.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% |
"killeroos-view3.pbrt (close-up)"
|
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% |
"plants-view1.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% |
"plants-view2.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% |