• MuradAkhter
• Assignment2

Revision 24 as of 2006-04-30 01:09:57

Assignment 2 Lazy KD-Tree

Murad Akhter

Date submitted: 29 Apr 2006

Code emailed: 28th & 29th Apr 2006

Comments

I had a phenomenally late start on the assignment since I was off campus most of this week. However, once I had gone section 4.4 of PBRT and read the well documented source code, the assignment went fairly smoothly. Unfortunately I emailed the wrong source file initially so please refer to my second email for grading.

Implementation

To get around const issues, I moved all the KdAccelTree members I needed to modify into a mutable struct. I also made the curMailboxId a static KdTreeAccel class variable to maintain the spirit of assigning monotically increasing ray id values in KdTree intersection routines since I chose to implement a KdTree of KdTrees. [BR]

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. Since the primitives pointers are byte aligned, it's reasonble to just check the least significant bit to differentiate between leaf and 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 and depth information). I just made sure to set the lazy bit after allocating memory and storing the lazyNodeInfo pointer and cleared the bit when I converted the lazy leaf node into an intermediate or regular leaf node.

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 as well. 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 new set of primitives and replace it with a kdtree built from those primitives. I chose to refine the primitive fully because for the sub-division surfaces we were rendering, only a few levels of refinement suffice. The main purpose of lazy refinement was to simply avoid the significant refinement cost 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. The most annoying bug I ran into had to do with infinitely traversing the tree because I hadn't considered the obvious case where a ray couldn't intersect a node and there were no futher children enqueued in the todos array. Kudos to gdb for letting me step through and figure this out.

I tried using a different cost function by checking for intersectable and non-intersectable primitives and weighting the latter more strongly since they require paying the costs of refining the primitive and constructing a new kdtree. I wasn't getting better results emperically so I left this out of my final implementation and submission.

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)

"killeroos-view2.pbrt (Killeroos invisible)"

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

"plants-view1.pbrt"

"plants-view2.pbrt"