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.
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.
Final Images Rendered with my implementation of heightfield.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% |
TO BE DONE AS SOON AS MY COMPUTER FINISHES RENDERING (thrashing badly)
"plants-view1.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
|
|
% |
total time (secs) |
|
|
% |
Num of nodes made |
|
|
% |
Triangle ray intersections |
|
|
% |
"plants-view2.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
|
|
% |
total time (secs) |
|
|
% |
Num of nodes made |
|
|
% |
Triangle ray intersections |
|
|
% |