Assignment 2 Lazy KD-Tree

Murad Akhter

Date submitted: 29th 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 read section 4.4 of PBRT and gone through the source code, the assignment went fairly smoothly. Unfortunately I emailed the wrong source file when I submitted so please refer to my second email for grading.

Implementation

Const issues & Data structures

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 class variable to maintain the spirit of assigning monotically increasing ray id values in KdTree intersection routines as I had chosen to implement a KdTree of KdTrees.

To keep nodes 8 bytes I used several simple tricks. I stored child nodes adjancent to one another so I would only need to keep track of one index. A lazy node was a leaf node with no mailboxes and a pointer to a dynamically assigned data structure storing its bounds, an array of primitive indices, and parameters for node number, depth and bad refines. The pointer was part of the aboveChild/primitives union and I used its least significant bit to differentiate between standard leaf nodes and lazy nodes taking advantage of the fact that pointers are byte aligned. The only complexity here was that I had to mask this bit whenever I used the pointer but that was straightforward to do.

Tree traversal and lazy evaluation

I grew the tree one level at a time, starting with 1 root node and two lazy children. The lazy nodes were expanded in the Intersect/IntersectP routines. I expanded a lazy node if a ray intersected its bounding box. First I reset the lazy bit and then I called a modified version of the buildTree function which converted the node into a leaf or intermediate node (depending on the normal factors such as depth, number of primitives and splitting cost), freeing its associated lazy info data structure. For each intermediate node, two lazy nodes were automatically generated. I wanted to use my own memory allocation scheme for this to avoid reallocating large chunks of memory with malloc and free but did not have time in the end to do so

Primitive refinement

As required for the assignment 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 could have refined the primitive to just one level but this didn't give superior results emperically. The main purpose of lazy refinement was to simply avoid the significant refinement cost for a primitive that would never intersect a ray.

Cost function

Due to time limitation I stuck with the normal kdtree cost function. Potential improvement to this would have been to check for intersectable and non-intersectable primitives to weigh the cost in favor of the latter and to measure the distance to the camera position and weigh the cost in favor of the node further away.

Bugs & Gotchas

I 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 an infinite loop while traversing the tree for intersection tests. I hadn't considered the obvious case in which the ray didn't intersect the current lazy node's bounding box and where there were no futher children enqueued in the todos array. I found gdb and the assignment wiki page helpful in debuggin this.

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"