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. The size of each node is kept at 8 bytes for better caching

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. There were nodes that refined to a single intersectible primitive, so for those, I simply refined-fully to reduce the overhead of needing to travers multiple nodes to reach one primitive.

Analysis

In the case of the second and third killeroo images, the running time was considerably less because huge parts of the scene were not expanded. However, it did not help the time taken to render the plant scenes because everything ended up needing to be expanded. In the worst case, the lazy implementation takes longer because it needs to handle multiple levels of kd-trees. It also requires a lot more memory to maintain un-expanded nodes.

Final Images Rendered with my implementation of lz_kdtree.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%

"plants-view1.pbrt"

plants-view1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

1208.4

%

total time (secs)

10234.5

%

Num of nodes made

14.886M

4.022M

27%

Triangle ray intersections

20.257M

28.347M

140%

(unfortunately I can't tell because it thrashed too much, but lazy kd-tree took a lot longer)

"plants-view2.pbrt"

plants-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

1220.7

%

total time (secs)

10122.4

%

Num of nodes made

14.886M

5.001M

33.6%

Triangle ray intersections

25.945M

32.252M

124%

(unfortunately I can't tell because it thrashed too much, but lazy kd-tree took a lot longer)