= Assignment 2 =
== Implementation ==
=== Lazy Refinement ===
I realized that simply refining a primitive into the existing Kd-Tree upon ray intersection would be a problem because other nodes may contain this primitive as well. If this 1 primitive becomes 8000, how will I update all the other nodes to know? Therefore, since Kd-Trees are primitives as well, I decided that upon intersecting a leaf node containing an unrefined primitive, I would replace that primitive with a Kd-Tree and refine this primitive inside the new Kd-Tree.

My rules


- putting kd-trees in nodes b/c I don't want to dynamically increase the # of
  mailboxes, which would invalidate ptrs in nodes which haven't been finished

- kept node data at 8bytes by smart flagging and by only storing address of "below" child node, making sure "above" is allocated next.

- added Weight() function to all Primitives so that I can divide nodes fairly when they have unrefined primitives inside

- instead of using extra bit for unfinished flag (further reducing accuracy
  and halving the number of possibly contained primitives) I'm reserving 0xFFFFFFFF
  which only cuts down the number of possibly contained primitives by 1

- storing a number of parameters in UnfinishedNodeData. These are simply allocated and deleted, which bothers me. I do pass them on for re-use though. Once a node becomes a leaf it has to delete its unfinished data since it will have no more children to pass it to.

- moved some pre-allocated data into KdTreeAccel so it doesn't have to bloat UnfinishedNodeData

- hitting an unrefined primitive makes a new KdTreeAccel containing that primitive. Inside the new KdTree, I refine until I have at least 1 fully refined primitive OR I have more than 1 primitive.

== Results ==
=== View: 1 ===
attachment:manykilleroos_1_lazy.png
|| || pbrt K-D Tree || my Lazy K-D Tree || Ratio (lazy/non-lazy reference) ||
||build time (secs) || 580 || 413 || 0.71 ||
||total time (secs) || 1095 || 929 || 0.85 ||
||nodes made || 9.76M || 3.58M || 0.37 ||
|| Triangle ray intersections || 2231k || 2345k || 1.05 ||

=== View: 2 ===
attachment:manykilleroos_2_lazy.png
|| || pbrt K-D Tree || my Lazy K-D Tree || Ratio (lazy/non-lazy reference) ||
||build time (secs) || 585|| 302 || 0.52 ||
||total time (secs) || 1155 || 872 || 0.75 ||
||nodes made || 9.77M || 1.89M || 0.19 ||
|| Triangle ray intersections || 4.84M || 5.37M || 1.11 ||

=== View: 3 ===
attachment:manykilleroos_3_lazy.png
|| || pbrt K-D Tree || my Lazy K-D Tree || Ratio (lazy/non-lazy reference) ||
||build time (secs) || 582 || 98 || 0.17 ||
||total time (secs) || 1032 || 548 || 0.53 ||
||nodes made || 9.77M || 0.14M || 0.01 ||
|| Triangle ray intersections || 4.86M || 6.49M || 1.34 ||

=== View: 3 Refined ===
attachment:manykilleroos_3_lazy_mega.png
|| || pbrt K-D Tree || my Lazy K-D Tree || Ratio (lazy/non-lazy reference) ||
||build time (secs) || - || 238 || - ||
||total time (secs) || - || 689 || - ||
||nodes made || - || 0.36M || - ||
|| Triangle ray intersections || - || 6.78M || - ||