= Assignment 2 Lazy KD-Tree = == Murad Akhter == == Date submitted: 28 Apr 2006 == == Code emailed: 28 Apr 2006 == === Comments === I had a phenomenally late start on the assignment since I was off campus most of this week for offsite interviews. However, once I had gone through the code, the assignment went fairly smoothly. === Implementation === To get around const issues, I moved all the KdAccelTree members I needed to modify into a mutable struct. To keep nodes 8 bytes I used several simple tricks such as storing child nodes adjancent to one another, adding a lazyNodeInfo pointer to the aboveChild/primitives union and using its least signifiant bit to check for lazy nodes. Whenever I wanted to create a lazy node, I would set the flags parameter to the 'leaf' value and dynamically allocate memory for a LazyNodeInfo struct (which stored the node bounds, primitives array, badRefines, depth etc). I just had to make sure to set the lazy bit after storing the pointer. Since the primitives pointers are byte aligned, it's reasonble to just check the least significant bit to differentiate between leaf and lazy nodes. I grew the tree one level at a time, starting with a root node and two lazy leaf node children. In the Intersect/IntersectP routines I would then lazily evaluate a node and convert it into a regular leaf or intermediate node as long as its bounding box intersected the ray. Whenever I created an intermediate node I always created its two lazy children. I didn't refine primitives unless I had reached a leaf node and discovered a primitive that couldn't be intersected. In this case I would refine the primitive fully into a set of primitives and replace the original primitive with a kdtree composed of those primitives. I chose to refine primitives fully because I figured (and experimentally verified) that it wouldn't add any value to refine sub-division primitives incrementally. The main purpose of lazy refinement was to simply avoid the significant refinement costs for primitives that would never intersect a ray. I considered merging the Intersection and IntersectionP routines since they share all but 3 lines of code, however, I decided against it because the code reuse comes at the expense of additional conditional statements that I felt were unnecessary and wasteful to add. I also ran into issues with the KdToDo pointers getting invalidated when the nodes array was reallocated and switched to using indices to the nodes array rather than actual pointer values. === Final Images Rendered with my implementation of heightfield.cpp === I had mixed results with my lazy kd tree. It performed significantly better than the regular implementation for the second and third killeroos scenes and marginally better on the first one. It performed worse on the plant scenes due to the incremental cost of additional triangle ray intersections. '''killeroos-view1.pbrt (Killeroos visible)''' attachment:killeroos-view1.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 15.8 || 0.0 || 0.0% || ||total time (secs) || 29.989 || 29.13 || 97% || ||Num of nodes made || 2.752M || 1.357M || 49.29% || || Triangle ray intersections || 673.2k || 827.7k || 122.95%|| "killeroos-view2.pbrt (Killeroos invisible)" attachment:killeroos-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 16.5 || 0.0 || 0.0% || ||total time (secs) || 27.554 || 14.53 || 52.73% || ||Num of nodes made || 2.752M || 18 || 0.00065% || || Triangle ray intersections || 758.4k || 776.1k || 102.33%|| "killeroos-view3.pbrt (close-up)" attachment:killeroos-view3.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 16.7 || 0.0 || 0.0% || ||total time (secs) || 30.943 || 22.7 || 73.36% || ||Num of nodes made || 2.752M || 373.3k || 13.56% || || Triangle ray intersections || 644.1k || 1.018M || 158.05%|| "plants-view1.pbrt" attachment:plants-view1.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 41.2 || __ || __% || ||total time (secs) || 721.281 || __ || __% || ||Num of nodes made || 14.884M || __ || __% || || Triangle ray intersections || 20.295M || __ || __%|| "plants-view2.pbrt" attachment:plants-view2.png || || KD Tree || Lazy KD Tree || Ratio || ||build time (secs) || 47.7 || || __% || ||total time (secs) ||1192.75 || __ || __% || ||Num of nodes made || 14.884M || __ || __% || || Triangle ray intersections || 25.902M || __ || __%||