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


=== Description of implementation approach and comments ===

==== 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 struct. Another bit was allocated in the first union to distinguish a lazy leaf node from a regular node.

==== Tree Construction in the Constructor ====
In the constructor I built 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 ====


=== 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%||