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 |
|
|
% |