Assignment 2 Lazy KD-Tree
Sue Lee
Date submitted: 26 Apr 2006
Code emailed: 26 Apr 2006
Description of implementation approach and comments
Firstly, I'd like to say that my lazy tree doesn't work well. I need to figure out, but this time, I'd like to summit with this one.
For the lazy kd-tree, I made one interior node and two lazy leaf nodes before I start rendering. When I start rendering, then it checks if it is an interior node or not. If it is interior node, then it checks the next step to traverse. If the node is not a interior node, then it checks if the ray is hit and if it is a lazy node or not. Only if the hit occurs, then the lazy node start build its own node.
When a build tree is called, instead of building childen nodes recursively, it changes itself to interior node, and builds two "lazy" leaves.
I made a map that stores information for the next child, so that when I build the tree, then it uses that information. For the primitives, it is refined when it is intersectable.
One nice thing compare to the kd tree is that it shorten the building and rendering time, and also, for the killeroos-view2, it can be constructed only with 9 leaf nodes.
Final Images Rendered with my implementation of heightfield.cpp
killeroos-view1.pbrt (Killeroos visible)
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
3.34 |
0.39 |
11.7% |
total time (secs) |
546.2K |
11.8 |
95.6% |
Num of nodes made |
546.2K |
132 |
0.02% |
Triangle ray intersections |
673.2k |
690.1k |
102.5% |
"killeroos-view2.pbrt (Killeroos invisible)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
3.44 |
0.39 |
11.3% |
total time (secs) |
10.4 |
9.9 |
95.2% |
Num of nodes made |
546.2K |
9 |
0.001% |
Triangle ray intersections |
776.1K |
776.1k |
100% |
"killeroos-view3.pbrt (close-up)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
3.46 |
0.39 |
11.2% |
total time (secs) |
13.8 |
9.8 |
71% |
Num of nodes made |
546.2K |
13 |
0.002% |
Triangle ray intersections |
645.6K |
643.3K |
99.6% |
"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 |
|
|
% |