Assignment 2 Lazy KD-Tree

Sue Lee

Date submitted: 26 Apr 2006

Code emailed: 26 Apr 2006

Description of implementation approach and comments

Firstly, I'd like to say that my lazy tree doesn't work well. I need to figure out, but this time, I'd like to summit with this one.

For the lazy kd-tree, I made one interior node and two lazy leaf nodes before I start rendering. When I start rendering, then it checks if it is an interior node or not. If it is interior node, then it checks the next step to traverse. If the node is not a interior node, then it checks if the ray is hit and if it is a lazy node or not. Only if the hit occurs, then the lazy node start build its own node.

When a build tree is called, instead of building childen nodes recursively, it changes itself to interior node, and builds two "lazy" leaves.

I made a map that stores information for the next child, so that when I build the tree, then it uses that information. For the primitives, it is refined when it is intersectable.

One nice thing compare to the kd tree is that it shorten the building and rendering time, and also, for the killeroos-view2, it can be constructed only with 9 leaf nodes.

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)

3.34

0.39

11.7%

total time (secs)

546.2K

11.8

95.6%

Num of nodes made

546.2K

132

0.02%

Triangle ray intersections

673.2k

690.1k

102.5%

"killeroos-view2.pbrt (Killeroos invisible)"

killeroos-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

3.44

0.39

11.3%

total time (secs)

10.4

9.9

95.2%

Num of nodes made

546.2K

9

0.001%

Triangle ray intersections

776.1K

776.1k

100%

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

killeroos-view3

KD Tree

Lazy KD Tree

Ratio

build time (secs)

3.46

0.39

11.2%

total time (secs)

13.8

9.8

71%

Num of nodes made

546.2K

13

0.002%

Triangle ray intersections

645.6K

643.3K

99.6%

"plants-view1.pbrt"

blank700x400

KD Tree

Lazy KD Tree

Ratio

build time (secs)

%

total time (secs)

%

Num of nodes made

%

Triangle ray intersections

%

"plants-view2.pbrt"

blank700x400

KD Tree

Lazy KD Tree

Ratio

build time (secs)

%

total time (secs)

%

Num of nodes made

%

Triangle ray intersections

%