= 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 and was easier to extend. 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 refinedm and I am wasting cycles (and memory) copying them between lazy nodes. 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. The main thing that it would have granted would be the extra copies between lazy nodes of the large primitive list. I later noticed (with the help of our lovely TA's) that you don't need the belowChild data (because it is always aboveChild+1). Also, I noticed that I could reuse a few more bytes without my funky bit shifts. After adding this, I saved 20 bytes, and the render time went down by about 10%. This was the second submission. == 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 call build_tree somehow, but if I made that const, then I had to call initLeaf, which called the memory Area stuff. I had to use the const_cast hack. Sorry :( == Run Machine == The tests were run on the machine fileserver.stanford.edu, which is a gentoo box. Intel 2.40 Gz, 1 Gig Ram, 3 Gig Swap. The swap is important because for the plants tests I ran over my memory using both the lazy and the real kdtree. == 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 || 14.88% || ||total time (secs) || 72.7 || 60.8 || 83.63% || ||Num of nodes made || 2.752M || 704.1k || 25.59% || || Triangle ray intersections || 673.2k || 673.2k || 100%|| "killeroos-view2.pbrt (Killeroos invisible)" attachment:killeroos-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 36.6 || 5.4 || 14.75% || ||total time (secs) || 67.1 || 36.2|| 53.95% || ||Num of nodes made || 2.752M || 68 || 0.000000025% || || Triangle ray intersections || 758.4k || 758.4k || 100%|| "killeroos-view3.pbrt (close-up)" attachment:killeroos-view3.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 36.7 ||5.4 || 14.71% || ||total time (secs) || 76.7 ||54.7 || 71.31% || ||Num of nodes made || 2.752M || 182.3k || 6.62% || || Triangle ray intersections || 644.1k || 644.1k || 100%|| "plants-view1.pbrt" attachment:plants-view1.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 96.3 || 2.0 || 2.08% || ||total time (secs) || 1334.3 || 1320.6 || 98.97% || ||Num of nodes made || 14.886M || 8.682M || 58.32% || || Triangle ray intersections || 20.292M || 19.510M || 96.14%|| "plants-view2.pbrt" attachment:plants-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 95.1 || 2.0 || 2.10% || ||total time (secs) || 2229.0 || 2001.5 || 89.79% || ||Num of nodes made || 14.886M || 10.874M || 73.02% || || Triangle ray intersections || 25.917M || 24.222M || 93.46%||