Assignment 2 Lazy KD-Tree
Shradha Budhiraja
Date submitted: 26 Apr 2006
Code emailed: 26 Apr 2006
Description of implementation approach and comments
Lazy Implementation of KdTree
The kdtree was implemented to behave lazily. Initially, the tree only has one root with all primitives associated to it. The recursion was replaced by a lazy tree building. A node in the tree is split into its children only if it is intersected by a ray. Also the node was checked to have atleast 5 primitives. This number was arrived at empirically after trying out in different scenarios. This was done to avoid creating an extra node for very few primitives. This does have a tradeoff in the number of intersections per node, however it works better in some cases.
Final Images Rendered with my implementation of heightfield.cpp
killeroos-view1.pbrt (Killeroos visible)
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
16.95 |
0.4s |
2.35% |
total time (secs) |
29.55 |
35.23s |
119.2% |
Num of nodes made |
2.752M |
2.686M |
97.6% |
Triangle ray intersections |
673.2K |
753.5K |
119.2% |
"killeroos-view2.pbrt (Killeroos invisible)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
16.77 |
0.3 |
2.38% |
total time (secs) |
27.07 |
14.62 |
54% |
Num of nodes made |
2.752M |
17 |
0.0006% |
Triangle ray intersections |
758.4K |
776.1K |
102.3% |
"killeroos-view3.pbrt (close-up)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
16.82 |
0.4 |
2.38% |
total time (secs) |
31.09 |
26.34 |
84.72% |
Num of nodes made |
2.752M |
1.38M |
50.1% |
Triangle ray intersections |
644.1K |
649.2K |
100% |
"plants-view1.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
98.81 |
|
% |
total time (secs) |
633.31 |
|
% |
Num of nodes made |
14.862 |
|
% |
Triangle ray intersections |
20.291 |
|
% |
"plants-view2.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
|
|
% |
total time (secs) |
|
|
% |
Num of nodes made |
|
|
% |
Triangle ray intersections |
|
|
% |