Assignment 2 Lazy KD-Tree
Yi Lang Mok
Date submitted: 25 Apr 2006
Code emailed: 25 Apr 2006
Description of implementation approach and comments
Handling Lazy Generation of Nodes
Initially, the tree contains a single lazy node that has contains all the primitives. As Intersect runs, it calls a modified BuildNode on the lazy node to convert it into either an interior node or a leaf node. In this way, only nodes that need to be traversed are expanded.
I reordered the way the flags within a node was stored so that I could use an extra bit to say whether a node was lazy. The size of each node is kept at 8 bytes for better caching
Handling Un-Intersectible Primitives
Since each primitive could potentially not be intersected, I added a field to each mailbox that could contain a sub-KdTree of the expanded primitive. When I encounter an un-intersectible primitive for the first time, I construct a new KdTree with the primitive's refined children and store that tree in the mailbox. There were nodes that refined to a single intersectible primitive, so for those, I simply refined-fully to reduce the overhead of needing to travers multiple nodes to reach one primitive.
Analysis
In the case of the second and third killeroo images, the running time was considerably less because huge parts of the scene were not expanded. However, it did not help the time taken to render the plant scenes because everything ended up needing to be expanded. In the worst case, the lazy implementation takes longer because it needs to handle multiple levels of kd-trees. It also requires a lot more memory to maintain un-expanded nodes.
Final Images Rendered with my implementation of lz_kdtree.cpp
killeroos-view1.pbrt (Killeroos visible)
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
39.7 |
0.4629 |
1.25% |
total time (secs) |
80.7 |
80.4 |
99.6% |
Num of nodes made |
2.752M |
1.429M |
51% |
Triangle ray intersections |
673.2K |
822.8K |
122% |
"killeroos-view2.pbrt (Killeroos invisible)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
44.1 |
0.0049 |
0.00% |
total time (secs) |
80.7 |
41.0 |
50.8% |
Num of nodes made |
2.752M |
49 |
0.00% |
Triangle ray intersections |
758.4K |
776.1K |
102% |
"killeroos-view3.pbrt (close-up)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
38.5 |
0.3467 |
0.90% |
total time (secs) |
81.4 |
76.1 |
93.5% |
Num of nodes made |
2.752M |
391.5K |
14.2% |
Triangle ray intersections |
644.1K |
1.018M |
158% |
"plants-view1.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
1208.4 |
|
% |
total time (secs) |
10234.5 |
|
% |
Num of nodes made |
14.886M |
4.022M |
27% |
Triangle ray intersections |
20.257M |
28.347M |
140% |
(unfortunately I can't tell because it thrashed too much, but lazy kd-tree took a lot longer)
"plants-view2.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
1220.7 |
|
% |
total time (secs) |
10122.4 |
|
% |
Num of nodes made |
14.886M |
5.001M |
33.6% |
Triangle ray intersections |
25.945M |
32.252M |
124% |
(unfortunately I can't tell because it thrashed too much, but lazy kd-tree took a lot longer)