= Assignment 2 Lazy KD-Tree =
== Paul Tarjan ==
== Date submitted: 26 Apr 2006 ==
== Code emailed: 26 Apr 2006 ==
=== Description of implementation approach and comments ===
I first fixed IntersectP to just call Intersect. Then I added the NULL test in Intersect to call Intersect on the subchild if isect is NULL. This made the code feel better.
bool KdTreeAccel::IntersectP(const Ray &ray) const {
return Intersect(ray, NULL);
}
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.
Now, I did something that doesn't fully refine at the begining. It just refines as you go. If you just do this optomization to the non-lazy kdTree, you get from about 63 seconds to 56 seconds for the kangaroo-view1. This moves all the time from the build to the run too. I couldn't get this to work with my implementation of lazy nodes, but judging by the render speedup here, I don't know if it would have been worth it.
== 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 :)
== Const ==
I never could get the const thing to go. I made all my data mutable and it still didn't like me. I had to use the const_cast hack. Sorry :(
== Tons of Build Messages ==
I did as Kayvon suggested and wraped the construction of my object in building StatCounters. Then It printed:
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (1.2s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.1s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.0s)
Building: [++++++++++++++++++++++++++++++++++++++++++++++++++] (0.3s)
I just summed these to get build time. Is this right? How come I am getting so many accelerators made?
=== Final Images Rendered with my implementation of lz-kdtree.cpp ===
'''killeroos-view1.pbrt (Killeroos visible)'''
attachment:killeroos-view1.png
|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 36.3 || 5.4 || __% ||
||total time (secs) || 72.7 || 63.8 || __% ||
||Num of nodes made || 2.752M || 845.6k || __% ||
|| Triangle ray intersections || 673.2k || 673.2k || __%||
"killeroos-view2.pbrt (Killeroos invisible)"
attachment:killeroos-view2.png
|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 36.6 || 5.4 || __% ||
||total time (secs) || 67.1 || 38.1|| __% ||
||Num of nodes made || 2.752M || 76 || __% ||
|| Triangle ray intersections || 758.4k || 758.4k || __%||
"killeroos-view3.pbrt (close-up)"
attachment:killeroos-view3.png
|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 36.7 ||5.4 || __% ||
||total time (secs) || 76.7 ||54.7 || __% ||
||Num of nodes made || 2.752M || 231.8k || __% ||
|| Triangle ray intersections || 644.1k || 644.1k || __%||
"plants-view1.pbrt"
attachment:plants-view1.png
|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 96.3 || __ || __% ||
||total time (secs) || 1334.3 || __ || __% ||
||Num of nodes made || 14.886M || __ || __% ||
|| Triangle ray intersections || 20.292M || __ || __%||
"plants-view2.pbrt"
attachment:plants-view2.png
|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 95.1 || __ || __% ||
||total time (secs) || 2229.0 || __ || __% ||
||Num of nodes made || 14.886M || __ || __% ||
|| Triangle ray intersections || 25.917M || __ || __%||