= Assignment 2 =
== Implementation ==
=== Lazy Refinement ===
I realized that, when I needed to perform an intersection test upon a non-intersectable primitive, I could not simply refine it and spit any new primitives which result into the existing Kd-Tree.  Problems would arise because other nodes may contain this primitive as well. If this 1 primitive becomes 8000, it would be very difficult to update all the other nodes and let them know about their new contents. This would likely involve allocating new arrays a good deal of copying.

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 that contains the primitive. In the constructor of each new Kd-Tree I conduct the actual refinement. I look at my list of primitives and if this list contains one primitive which is non-intersectable then I refine until I have more than one primitive or the one primitive I have can be intersected. By not fully refining a primitive the first time I strike it, I support lazy refinement of primitives with multiple levels of containment, such as ShapeSets. By refining until I have at least one intersectable primitive, I avoid creating a Kd-Tree which immediately contains another Kd-Tree, as when a LoopSubdiv refines to a single TriangleMesh before finally refining to individual Triangles.

=== Data for Unfinished Nodes ===

BuildTree passed a fair amount of state data along as it created each node. It also passed along a number of temporary data structures that each iteration of the function would overwrite. In converting BuildTree to BuildNode, I had to figure out how to handle this.

vector<BBox> allPrimBounds; and  // bounding boxes of all primitives, saved
BoundEdge *edges[3]; // pre-allocated space for edge info
These I made members of KdTreeAccel. The disadvantage of keeping these available at all times is that they will never be deleted. However, allPrimBounds would only cease to be used if every single leaf were made, which is quite unlikely. If edges[3] were not kept around each call of BuildNode would have to recreate it. This would be an undesirable delay.

Unique state data needed by each node was stored in a new object I created, UnfinishedNodeData. Its members were:
{{{
u_int *primNums; // array containing index (in mailboxPrims) for each prim in this node
u_int nPrims; // number primitives in primNums
BBox nodeBounds; // bounds of this node
int depth; // number of splits we can do from here
int badRefines; // number of consecutive refines that scored (slightly) worse than parent
int weight; // sum weight of contained primitives
}}}
Most variables are necessary, as this data is specific to each unfinished node and must be remembered somewhere. weight could be recalculated but I thought the benefits of storing it outweighed the cost of constantly recalculating it.

s

- 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 || - ||
* My computer could not complete a render with the original implementation due to memory demands