= 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. 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)''' attachment:killeroos-view1.png || || 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)" attachment:killeroos-view2.png || || 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)" attachment:killeroos-view3.png || || 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" attachment:plants-view1.png || || 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" attachment:plants-view2.png || || 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 || __ || __%||