= Assignment 2 Lazy KD-Tree = == Shradha Budhiraja == == Date submitted: 27 Apr 2006 == == Code emailed: 26 Apr 2006 == === Description of implementation approach and comments === === Lazy Implementation of KdTree === The kdtree was implemented to behave lazily. Initially, the tree only has one root with all primitives associated to it. The recursion was replaced by a lazy tree building. A node in the tree is split into its children only if it is intersected by a ray. Also the node was checked to have atleast 5 primitives. This number was arrived at empirically after trying out in different scenarios. This was done to avoid creating an extra node for very few primitives. This does have a tradeoff in the number of intersections per node, however it works better in some cases. === Lazy Refinement of Primitives === In the original implementation, all the primitives are fully refined into intersectables once they are alloted to a root node. In the lazy implementation, this was delayed until a ray intersected the node containing the primitive. Initially, the primitives were kept as they were received from the pbrt file. Whenever a ray intersects a node, its primitive/primitives is/are fully refined. The new set of primitives are built into another kdtree and this kdtree replaces the old primitive as a whole. This way the primitives did not have to be re-ordered or replaced in the original kdtree node and thus saved a lot of book-keeping. After a long discussion with Pat and some other students, I realised that it was not useful to restrict the level of refinement. This was because the surfaces used in these scenes do not have more than 2 levels of refinement, so it was not going to gain much. As a result, the primitives were refined in one step. Also, I tried to refine conservatively, meaning that a primitive was refined only if the ray actually hit it. But this seemed to work differently for the different scenes, it blew up the time in some cases. As a result, I did not include it in my final implementation. === Optimizations on a whole === The size of the node structure was not increased and was kept to 8 bytes to keep up with caching property. The children of a node were placed next to each other and as a result, above Child sufficed. Also, a bit in this union was used to specify if the node is lazy or not. Since mallocd pointers (pointing to Mailboxes) are byte aligned, the last bit could be used safely in this case. While accessing the pointer, however, this bit needed to be masked. The bounds of each node were not stored globally. They were calculated dynamically whenever the node was being split. Also, depth at each node was maintained in the loop that traversed the tree and built it as and when needed. I added a primitive id to Mailboxes to keep a track of the primitives. This, I believe led to some loss in time as we were no longer accesing just 8 bytes. === Performances === The killeroos did much better with the lazy implementation. However, killeroo1 either did the same or worse when the parameter of minimum primitives required in a node for it to be lazy was varied. The plants scenes actually did worse. This was probably because, not only does it create a large number of primitives, but all of them are also visible. As a result, it was not really worth building the tree lazily and a one-time build would have been useful. === Final Images Rendered with my implementation of heightfield.cpp === '''killeroos-view1.pbrt (Killeroos visible)''' attachment:killeroos-view1.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 16.95 || 0.4s || 2.35% || ||total time (secs) || 29.55 || 35.23s || 119.2% || ||Num of nodes made || 2.752M || 2.686M || 97.6% || || Triangle ray intersections || 673.2K || 753.5K || 119.2%|| "killeroos-view2.pbrt (Killeroos invisible)" http://www.stanford.edu/~shradha/killeroos-view2.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 16.77 || 0.3 || 2.38% || ||total time (secs) || 27.07 || 14.62 || 54% || ||Num of nodes made || 2.752M || 17 || 0.0006% || || Triangle ray intersections || 758.4K || 776.1K || 102.3%|| "killeroos-view3.pbrt (close-up)" http://www.stanford.edu/~shradha/killeroos-view3.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 16.82 || 0.4 || 2.38% || ||total time (secs) || 31.09 || 26.34 || 84.72% || ||Num of nodes made || 2.752M || 1.38M || 50.1% || || Triangle ray intersections || 644.1K || 649.2K || 100%|| "plants-view1.pbrt" http://www.stanford.edu/~shradha/plants-view1.jpg In both the plant scenes, it apparently took a lot of time to load initial textures and this has not been included in the build time. || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 98.81 || 1.2 || 1.21% || ||total time (secs) || 633.31 || 1485.23 || 234.4% || ||Num of nodes made || 14.862 || 7.2M || 48.44% || || Triangle ray intersections || 20.291 || 27.2M || 74.5%|| "plants-view2.pbrt" http://www.stanford.edu/~shradha/plants-view2.jpg || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 135.19 || 1.4|| 1.03% || ||total time (secs) || 1033.49 || 2663.67 || 257.73% || ||Num of nodes made || 14.862 || 7.514M || 50.55% || || Triangle ray intersections || 25.829M || 29.343M || 113.6%||