= Assignment 2  Lazy KD-Tree =

== Doug Johnston ==
== Date submitted: 27 Apr 2006 ==
== Code emailed: 27 Apr 2006 ==



=== Description of implementation approach and comments ===
I started by manying the lazy tree nodes first, putting the geometry aside. I kept the same structure as the kdtree, adding a LZ-Data structure to the class. I made everything that was reasonable as a vector. The new structure contained the bounds0 and bounds1, the prims0 and prims1, as well as their counts (although they we not strictly needed as I could have used prims.size(), but I kept them for consistancy), as well as the depth, badrefines, and the # of children the node had assigned. I also kept a boolean indicating whether the node was lazy or not. When both children were refined, the node lost its lazy status, and all the memory allocated in the LZ-data structure was released dynamically. I made an IsLazy() function to return the status, thinking I might try to add the lazy flag into the existing node with some bit-wise trickery, but it ended up not being an issue.
I put checks in the two intersect routines to see if it was traversing a lazy node. If so, I would build its children. It took a little while and a little care to get all the const variables mutated (?) properly, but after that was done, there weren't many issues to deal with.
Next, I tackled making the geometry lazier, which I had a significantly more difficult time with, and ended up costing me in the form of two late days. I still dont have a great implementation, but at least now, I've figured out exactly why. My plan was to convert the static array used in the kd-tree into a vector, and then only refine geometry right before it was to be added to a leaf node, if it wasn't intersectable, and then depending on how many primitives it refined into, either place it in the leaf node, or relize it made too many primatives, which would prevent the leaf not from being created, and then turn it into a lazy node instead. All of this worked, but it was terribly slow!! The simple killeroo scenes were taking 1000's of seconds. Why? I finally figured out that is was due to the way I was adding data to my mailBoxPrim vector. It was not in contiguous memory, and the hopping around took a large hit. This may be exaggereated by the fact that I'm working on a computer with a small and slow L2 cache, but still, the results were not acceptable. I rewrote the way I did it, and attempted to use the contiguous memory structures in the same was is done for the kdtree nodes. However, I kept running into memory erros that I could not correct. Because the renders were so slow using the previous implementation, I ran the tests below with full sets of refined geometry.



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

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

http://people.stanford.edu/~dougjohn/killerroos-view1.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 41.57 || 7.4 || 17.8% ||
||total time (secs) || 70.07 || 50.2 || 71.6% ||
||Num of nodes made || 2.752M || 1.06M || 38.4% ||
|| Triangle ray intersections || 673.2k || 673.2k || 100%||


"killeroos-view2.pbrt (Killeroos invisible)"

http://people.stanford.edu/~dougjohn/killerroos-view2.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 41.4 || 7.4 || 17.9% ||
||total time (secs) || 64.9 || 32.16 || 49.55% ||
||Num of nodes made || 2.752M || 97 || 00.00001% ||
|| Triangle ray intersections || 758.4k || 758.4k || 100%||

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

http://people.stanford.edu/~dougjohn/killerroos-view3.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 41.11 || 7.6 || 18.4% ||
||total time (secs) || 72.91 || 41.17 || 56.47% ||
||Num of nodes made || 2.752M || 272.9k || 9.91% ||
|| Triangle ray intersections || 644.1k || 644.1k || 100%||

"plants-view1.pbrt"

http://people.stanford.edu/~dougjohn/plants-view1.jpg

|| || KD Tree || Lazy KD Tree || Ratio ||
||build time (secs) || 105.497 || 56.75 || 53.8% ||
||total time (secs) || 727.5 || 933.25 || 128.3% ||
||Num of nodes made || 14.86M || 7.46M || 50.2% ||
|| Triangle ray intersections || 20.29M || 20.29M || 100%||

"plants-view2.pbrt"

http://people.stanford.edu/~dougjohn/plants-view2.jpg

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