Assignment 2 Lazy KD-Tree

Julie Tung

Date submitted: 26 Apr 2006

Code emailed: 26 Apr 2006

Description of implementation approach and comments

Storage strategies: A lot of temporary storage is needed (to store edges and the prims0 and prims1 arrays) for the splitting that occurs during the rendering stage now, because it's building the kd-tree lazily. At first I just allocated the exact size that I needed for each of these data structures, used them in the split, and then freed them. However, since this was done for every time a lazy node was split into an interior node, this became extremely time-wasting. Instead, I created global temporary data structures, first initializing them to a particular size. Before each use, I check to make sure the size is sufficient; if so, I proceed, if not, then I reallocate the structures and delete the old ones. Using this scheme, the structures are reallocated very few times, and we just keep reusing the same space, although we're frequently holding more space than we need, it's worth it to avoid the malloc/free costs each time. Also, since the data structures are global, all the kd-trees can share this same temporary storage. This temporary storage optimization saved my rendering time about 20% on the killeroos-1 image.

For the KdAccelNode, I was able to keep the storage for the struct to 8 bytes by doing the following: 1.

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)

19.8

0.0

0%

total time (secs)

30.9

28.0

90.6%

Num of nodes made

2.754M

1359.9k

49.4%

Triangle ray intersections

673.2k

826.8k

122.8%

"killeroos-view2.pbrt (Killeroos invisible)"

killeroos-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

19.1

0.0

0%

total time (secs)

28.2

9.9

35.1%

Num of nodes made

2.754M

47

.002%

Triangle ray intersections

758.4k

776.1k

102.3%

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

killeroos-view3

KD Tree

Lazy KD Tree

Ratio

build time (secs)

20.1

0.0

0%

total time (secs)

32.2

20.6

63.9%

Num of nodes made

2.754M

373.2k

13.5%

Triangle ray intersections

644.2k

1.018M

158.1%

"plants-view1.pbrt"

plants-view1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

49.9

0.1

0.2%

total time (secs)

493.8

844.6

171%

Num of nodes made

14.838M

4.044M

27%

Triangle ray intersections

20.264M

27.614M

136.3%

"plants-view2.pbrt"

plants-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

49.8

.3

0.5%

total time (secs)

784.3

1511.7

192.7%

Num of nodes made

14.838M

5.157M

34.8%

Triangle ray intersections

25.894M

31.217M

120.5%