Assignment 2 Lazy KD-Tree

Tarang Vaish

Date submitted: 26 Apr 2006

Code emailed: 26 Apr 2006

Description of implementation approach and comments

The implementation approach was to not refine any primitive in the constructor and lazily refine them on intersection with some rays. I tried to add more primitives into this kdtree initially but found the complexity overwhelming to debug and complex. Instead I replaced unrefined primitives with a new kdtree build upon the refined primitives of this primitive. This helped reusing the same kdtree implementation recursively.

Refinement is tried to be as late as possible, bigger leaf nodes are split into small chunks, so that a bunch of unrefined primitives do not get refined when a ray intersects a large node. Furthermore, intersection of a ray with the bounding box of the unrefined primitive was checked to make sure refinement was absolutely necessary. I found the number of primitives in any leaf to be a critical factor to performance and laziness. Longer depth can lead to longer access time to a primtive and shorter depths mean checking many primitives at the leaf nodes. The heuristic of max depth in the kdtree implementation also makes more sense when number of primitives are large.

I appreciate the original kdtree implementation for cleverly optimizing data structures and minimizing overheads. The kdTreeNode was kept the same size of 8 bytes as it is proportional to the number of primitives, I used a lazy bit in the pointer variable of this node to not check for more splits if this leaf node is no longer lazy. I refactored the Intersect, IntersectP functions into a commong Isect funtion.

I tried building part of the tree initially, but it doesnt help in performance because of the way we have to choose the memory layout. Since a node's child may not be adjacent to itself, building the tree to any depth is not going to be any better than building it later. The kdtree implementation used to benefit from this as they used to build all the tree once and were thus able to layout the parent leftchild nodes contigously. So I decided to not do any initial building and be lazy on buidling it in intersection functions.

Final Images Rendered with my implementation

killeroos-view1.pbrt (Killeroos visible)

killeroos1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

16.4s

0.19s

1.15%

total time (secs)

29.1s

35.1s

120.6%

Num of nodes made

2.752M

2.545M

92.4%

Triangle ray intersections

673.2K

821.4K

122%

"killeroos-view2.pbrt (Killeroos invisible)"

killeroos2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

16.3

.6

3.68%

total time (secs)

26.6

13.6

51.1%

Num of nodes made

2.752M

52

.00018%

Triangle ray intersections

758.4K

776.1K

102.33%

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

killeroos3

KD Tree

Lazy KD Tree

Ratio

build time (secs)

16.3

0.5

3%

total time (secs)

30.637

26.3

85.84%

Num of nodes made

2.752M

645.9K

23.47%

Triangle ray intersections

644.1K

901.3K

139.9%

"plants-view1.pbrt"

plants1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

42.5

0.22

0.5%

total time (secs)

612

1365

223%

Num of nodes made

14.862M

6.6M

44.4%

Triangle ray intersections

20.291M

26.409M

130.1%

"plants-view2.pbrt"

plants2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

53.2

0.22

4.13%

total time (secs)

928.9

2386

256.86%

Num of nodes made

14.862M

7.315M

49.2%

Triangle ray intersections

25.843M

29.523M

114.2%

TarangVaish/Assignment2 (last edited 2006-04-27 08:54:37 by tarangvaish)