= Assignment 2 Lazy KD-Tree = == Tom Brow == == Date submitted: 25 Apr 2006 == == Code emailed: 25 Apr 2006 == === Description of implementation approach and comments === == Lazy tree construction == In my implementation, I chose to expand each node of the tree only when it was intersected. I modified the function KdTreeAccel::buildTree tree such that instead of recursively calling itself on the children after a split, it would initialize either child as a "lazy" node with a pointer to a data structure that stored all of the parameters necessary to call buildTree on that node later. My approach required me to alter kdtree's original node allocation system, since that system does not allow for the tree to be built out of order. Because my new system requires that each node store the index of both of its children, I was forced to switch up to a 16-byte node structure. I also made some of the memory chunks that are normally passed through buildTree into data members of KdAccelTree, since they are reused throughout rendering as the lazy tree is constructed. == Lazy primitive refinement == To avoid refining primitives that are not in fact visible to the camera, I refined each non-intersectable primitive only when the leaf node containing it was intersected. I did not treat non-intersectable primitives differently than geometric primitives during tree construction, possibly resulting in poorer splits. This would account for the fact that my implementation consistently calls more ray-triangle intersections than the original kdtree. == Results == My implementation outperforms the original kdtree in two of the "killeroo" scenes, but performs significantly worse in the "plant" scenes. This may be because the runtime of intersections dominates over the time saved on tree construction and primitive refinement in those scenes. === Final Images Rendered with my implementation of lz-kdtree.cpp === '''killeroos-view1.pbrt (Killeroos visible)''' [attachment:kill1.jpg] || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 3.5 || 0.0 || inf% || ||total time (secs) || 15.9 || 16.3|| 97.5% || ||Num of nodes made || 546.2k || 587.4 || 93.0% || || Triangle ray intersections || 675.5k || 826.9k || 81.7% || "killeroos-view2.pbrt (Killeroos invisible)" http://graphics.stanford.edu/courses/cs348b-06/Homework2/blank400x400.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 3.5 || 0.0 || inf% || ||total time (secs) || 14.1 || 10.7 || 131.8% || ||Num of nodes made || 546.2k || 47 || 1162127.7% || || Triangle ray intersections || 776.1k || 776.1k || 100.0% || "killeroos-view3.pbrt (close-up)" http://graphics.stanford.edu/courses/cs348b-06/Homework2/blank400x400.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 3.5 || 0.0 || inf% || ||total time (secs) || 17.2 || 15.7 || 109.6% || ||Num of nodes made || 546.2k || 141.1k || 387.1% || || Triangle ray intersections || 645.6k || 1019k || 63.5% || "plants-view1.pbrt" http://graphics.stanford.edu/courses/cs348b-06/Homework2/blank700x400.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 50.3 || 0.0 || inf% || ||total time (secs) || 630.9 || 981.7 || 64.2% || ||Num of nodes made || 14.9M || 4.0M || 372.5% || || Triangle ray intersections || 20.3M || 27.6M || 73.5% || "plants-view2.pbrt" http://graphics.stanford.edu/courses/cs348b-06/Homework2/blank700x400.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 41.3 || 0.0 || inf% || ||total time (secs) || 900.9 || 1520.2 || 59.3% || ||Num of nodes made || 14.9M || 5.2M || 286.5% || || Triangle ray intersections || 25.8M || 31.2M || 82.7% ||