= Assignment 2  Lazy KD-Tree =
== Yi Lang Mok ==
== Date submitted: 25 Apr 2006 ==
== Code emailed: 25 Apr 2006 ==


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

== Handling Lazy Generation of Nodes ==

Initially, the tree contains a single lazy node that has contains all the primitives.  As Intersect runs, it calls a modified BuildNode on the lazy node to convert it into either an interior node or a leaf node.  In this way, only nodes that need to be traversed are expanded.

I reordered the way the flags within a node was stored so that I could use an extra bit to say whether a node was lazy.  The size of each node is kept at 8 bytes for better caching

== Handling Un-Intersectible Primitives ==

Since each primitive could potentially not be intersected, I added a field to each mailbox that could contain a sub-KdTree of the expanded primitive.  When I encounter an un-intersectible primitive for the first time, I construct a new KdTree with the primitive's refined children and store that tree in the mailbox.  There were nodes that refined to a single intersectible primitive, so for those, I simply refined-fully to reduce the overhead of needing to travers multiple nodes to reach one primitive.

=== Final Images Rendered with my implementation of lz_kdtree.cpp ===

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

http://www.stanford.edu/~myilang/cs348b/hw2/killeroos-view1.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 39.7 || 0.4629 || 1.25% ||
||total time (secs) || 80.7 || 80.4 || 99.6% ||
||Num of nodes made || 2.752M || 1.429M || 51% ||
|| Triangle ray intersections || 673.2K || 822.8K || 122%||

"killeroos-view2.pbrt (Killeroos invisible)"

http://www.stanford.edu/~myilang/cs348b/hw2/killeroos-view2.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 44.1 || 0.0049 || 0.00% ||
||total time (secs) || 80.7 || 41.0 || 50.8% ||
||Num of nodes made || 2.752M || 49 || 0.00% ||
|| Triangle ray intersections || 758.4K || 776.1K || 102%||

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

http://www.stanford.edu/~myilang/cs348b/hw2/killeroos-view3.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 38.5 || 0.3467 || 0.90% ||
||total time (secs) || 81.4 || 76.1 || 93.5% ||
||Num of nodes made || 2.752M || 391.5K || 14.2% ||
|| Triangle ray intersections || 644.1K || 1.018M || 158%||


=== TO BE DONE AS SOON AS MY COMPUTER FINISHES RENDERING (thrashing badly) ===

"plants-view1.pbrt"

http://www.stanford.edu/~myilang/cs348b/hw2/plants-view1-400x400.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || __ || __ || __% ||
||total time (secs) || __ || __ || __% ||
||Num of nodes made || __ || __ || __% ||
|| Triangle ray intersections || __ || __ || __%||

"plants-view2.pbrt"

http://www.stanford.edu/~myilang/cs348b/hw2/plants-view2-400x400.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || __ || __ || __% ||
||total time (secs) || __ || __ || __% ||
||Num of nodes made || __ || __ || __% ||
|| Triangle ray intersections || __ || __ || __%||