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

== Analysis ==

In the case of the second and third killeroo images, the running time was considerably less because huge parts of the scene were not expanded.  However, it did not help the time taken to render the plant scenes because everything ended up needing to be expanded.  In the worst case, the lazy implementation takes longer because it needs to handle multiple levels of kd-trees.  It also requires a lot more memory to maintain un-expanded nodes.

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


"plants-view1.pbrt"

http://www.stanford.edu/~myilang/cs348b/hw2/plants-view1.gif

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 1208.4 || __ || __% ||
||total time (secs) || 10234.5 || __ || __% ||
||Num of nodes made || 14.886M || 4.022M || 27% ||
|| Triangle ray intersections || 20.257M || 28.347M || 140%||

(unfortunately I can't tell because it thrashed too much, but lazy kd-tree took a lot longer)

"plants-view2.pbrt"

http://www.stanford.edu/~myilang/cs348b/hw2/plants-view2.gif

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 1220.7 || __ || __% ||
||total time (secs) || 10122.4 || __ || __% ||
||Num of nodes made || 14.886M || 5.001M || 33.6% ||
|| Triangle ray intersections || 25.945M || 32.252M || 124%||

(unfortunately I can't tell because it thrashed too much, but lazy kd-tree took a lot longer)