Assignment 2 Lazy KD-Tree
Paul Tarjan
Date submitted: 26 Apr 2006
Code emailed: Not Yet
Description of implementation approach and comments
I implemented this twice. The first time, I fullyRefined the primitives right at the start, trying to use some of my build cost so that I don't have to do it later. I didn't realize that some of the nodes might not have to be refined. I also added the bounding box, the depth, and a boat load of other data into the node. The numbers you see below are for this implementation.
I then reduced the size of the node class by 12 bytes (from 56 to 44) and noticed a preformance DECREASE. It was due to all the fancy things I was doing to store the data in unused bits and all the math that had to be done to undo the fancy things. I didn't submit this code.
I'm currently working on a version that doens't refine anything until it needs it. Keep posted.
Count a bit off
One thing about the counts, is a lazy node becomes another node when it is made "unLazy". Should I count this as being 2 nodes created, or just one? I counted it as just 1 node to make my numbers look better
Final Images Rendered with my implementation of lz-kdtree.cpp
killeroos-view1.pbrt (Killeroos visible)
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
36.3 |
5.4 |
% |
total time (secs) |
36.4 |
58.4 |
% |
Num of nodes made |
2.752M |
845.6k |
% |
Triangle ray intersections |
673.2k |
673.2k |
% |
"killeroos-view2.pbrt (Killeroos invisible)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
36.6 |
5.4 |
% |
total time (secs) |
30.9 |
32.7 |
% |
Num of nodes made |
2.752M |
76 |
% |
Triangle ray intersections |
758.4k |
758.4k |
% |
"killeroos-view3.pbrt (close-up)"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
36.7 |
5.4 |
% |
total time (secs) |
40.0 |
49.3 |
% |
Num of nodes made |
2.752M |
231.8k |
% |
Triangle ray intersections |
644.1k |
644.1k |
% |
"plants-view1.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
96.3 |
|
% |
total time (secs) |
1238 |
|
% |
Num of nodes made |
14.886M |
|
% |
Triangle ray intersections |
20.292M |
|
% |
"plants-view2.pbrt"
|
KD Tree |
Lazy KD Tree |
Ratio |
build time (secs) |
95.1 |
|
% |
total time (secs) |
2133.9 |
|
% |
Num of nodes made |
14.886M |
|
% |
Triangle ray intersections |
25.917M |
|
% |