= Assignment 2  Lazy KD-Tree =
== Ranjitha Kumar ==
== Date submitted: 27 Apr 2006 ==
== Code emailed: 27 Apr 2006 ==


=== Description of implementation approach and comments ===
My implementation tried to preserve the built in efficiency of the original code; therefore, I tried to make the fewest possible changes to the data structures and main functions buildTree and Intersect.
 
==== Tree Representation ====
An extra structure called lazyInfo was added to store the temporary data that a lazy node would need to access to expand itself during traversal. This struct contains fields such as the bounding box, depth and badRefines count corresponding to the lazy node.  A pointer to this struct was placed in the second union of KDAccelNode. Another bit was allocated in the first union of KDAccelNode to distinguish a lazy leaf node from a regular node.

==== Tree Construction in the Constructor ====
The constructor builds only one lazy leaf node. Furthermore, every conglomerate object is refined and stored as a kdtree. The scenes were rendered quicker when the refinement was done upfront in the constructor than later during traversal; it especially helped the rendering time of killeroos1-view1 improve because the scene displays all four killeroos. 

==== Tree Construction during Traversal ====
During tree construction, if a lazy leaf is encountered it is built out to a certain depth. A depth of four was used to render the images below. Therefore, in addition to the depth parameter, the function buildTree takes a subdepth parameter which is decremented during the recursion. When the subdepth is equal to zero, further lazy leafs are created. BuildTree uses the same cost function as in the original kdtree. 

After the lazy leaf is converted into either an interior node or a true leaf, the traversal continues as normal. The only snafu which occured was pointer mismanagement: when buildTree allocates more memory for the tree, it copies the old tree into a new location; therefore, all the pointers stored in the KdToList may become invalid after reallocing. Unfortunately, this problem took a long time to resolve.

==== Results ====
As expected, the Lazy KD-Tree greatly reduced the rendering time for killeroos-view2 and killeroos-view3 since unnecessary parts of the tree were not being expanded to render the scene. The Lazy KD-Tree, however, did not seem to help speed up the rendering time of the plant files; it seems that the large number of triangle ray intersections increased the rendering time for lazy implementation. Therefore, in this case, the cost of triangle ray intersections overweighed the benefit of building fewer nodes.

=== Final Images Rendered with my implementation of lz-kdtree.cpp ===

'''killeroos-view1.pbrt (Killeroos visible)'''

attachment:killeroos1.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 16.0  || 1.9 || 842% ||
||total time (secs) || 28.8 || 26.3 || 110% ||
||Num of nodes made || 2.75M || 1.96M || 140% ||
|| Triangle ray intersections || 673.2K  || 826.8K || 81.4%||


"killeroos-view2.pbrt (Killeroos invisible)"

attachment:killeroos2.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 16.0 || 1.9 || 842% ||
||total time (secs) || 26.4 || 12.8 || 206% ||
||Num of nodes made || 2.75M || 64 || 4300% ||
|| Triangle ray intersections || 758.4K || 776.1K || 97.7%||

"killeroos-view3.pbrt (close-up)"

attachment:killeroos3.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 16.0 || 1.9 || 842% ||
||total time (secs) || 30.4 || 20.9 || 1.45% ||
||Num of nodes made || 2.75M || 468.1K || 587% ||
|| Triangle ray intersections || 644.1K || 1.01M || 63.8%||

"plants-view1.pbrt"

attachment:plants1.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 39.6 || .7 || 5657% ||
||total time (secs) || 587.5 || 872.8 || 67.3% ||
||Num of nodes made || 14.86M || 4.86M || 306% ||
|| Triangle ray intersections || 20.29M || 27.6M || 73.5%||

"plants-view2.pbrt"

attachment:plants2.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 39.6 || .7 || 5657% ||
||total time (secs) || 969.5 || 1509.4 || 64.2% ||
||Num of nodes made || 14.86M || 6.18M || 240% ||
|| Triangle ray intersections || 25.83M || 31.2M || 82.8%||