Assignment 2 Lazy KD-Tree

Yi Lang Mok

Date submitted: 25 Apr 2006

Code emailed: 25 Apr 2006

Description of implementation approach and comments

Handling Lazy Generation of Nodes

Initially, the tree contains a single lazy node that has contains all the primitives. As Intersect runs, it calls a modified BuildNode on the lazy node to convert it into either an interior node or a leaf node. In this way, only nodes that need to be traversed are expanded.

I reordered the way the flags within a node was stored so that I could use an extra bit to say whether a node was lazy.

Handling Un-Intersectible Primitives

Since each primitive could potentially not be intersected, I added a field to each mailbox that could contain a sub-KdTree of the expanded primitive. When I encounter an un-intersectible primitive for the first time, I construct a new KdTree with the primitive's refined children and store that tree in the mailbox.

Final Images Rendered with my implementation of heightfield.cpp

killeroos-view1.pbrt (Killeroos visible)

killeroos-view1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

39.7

0.4629

1.25%

total time (secs)

80.7

80.4

99.6%

Num of nodes made

2.752M

1.429M

51%

Triangle ray intersections

673.2K

822.8K

122%

"killeroos-view2.pbrt (Killeroos invisible)"

killeroos-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

44.1

0.0049

0.00%

total time (secs)

80.7

41.0

50.8%

Num of nodes made

2.752M

49

0.00%

Triangle ray intersections

758.4K

776.1K

102%

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

killeroos-view3

KD Tree

Lazy KD Tree

Ratio

build time (secs)

38.5

0.3467

0.90%

total time (secs)

81.4

76.1

93.5%

Num of nodes made

2.752M

391.5K

14.2%

Triangle ray intersections

644.1K

1.018M

158%

TO BE DONE AS SOON AS MY COMPUTER FINISHES RENDERING (thrashing badly)

"plants-view1.pbrt"

plants-view1-400x400

KD Tree

Lazy KD Tree

Ratio

build time (secs)

%

total time (secs)

%

Num of nodes made

%

Triangle ray intersections

%

"plants-view2.pbrt"

plants-view2-400x400

KD Tree

Lazy KD Tree

Ratio

build time (secs)

%

total time (secs)

%

Num of nodes made

%

Triangle ray intersections

%