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. The assignment itself went fairly smoothly.

Implementation

To get around const issues, I moved all the KdAccelTree members I needed to modify into a struct which I declared mutable.

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)

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)"

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)"

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"

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"

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

%