Assignment 2 Lazy KD-Tree

Bill Dwyer

Date submitted: 26 Apr 2006 (ish)

Code emailed: 26 Apr 2006

Description of implementation approach and comments

I relied heavily on the given implementation of the Kd Tree and basically made modifications to the existing code instead of starting from scratch. The PBRT book was incredibly helpful in understanding how the regular Kd Tree was implemented. It was also very clear that the regular Kd Tree was HIGHLY optimized. For example, all the nodes were allocated in aligned memory to make it faster when caching. However, since Lazy Kd Trees are built incrementally, it is not possible to rely on this optimization since nodes can be built in an arbitrary order (to some extent).

After understanding the original Kd Tree layout, I basically modified the node structure to contain the arguments that would normally be passed down through recursion, so that they could be accessed at a later time (i.e. when the interection is calculated). I only classify a node (interior or leaf) when it is called for by the intersection algorithm. After classification, two unclassified children are attached, and their arguments are initialized.

In the end, the speed up of the Lazy Kd Tree is good for interesting edge cases. However, if you don't intend to ray-trace large amounts of the scene, it seems silly to have the geometry in there to begin with. For example, if we're only rendering the scene of killaroos from behind a wall, why even bother loading the killaroo geometry in the first place?

Final Images Rendered with my implementation of heightfield.cpp

killeroos-view1.pbrt (Killeroos visible)

KD Tree

Lazy KD Tree

Ratio

build time (secs)

20.0s

4.2s

21.0%

total time (secs)

40.5s

100s

247%

Num of nodes made

2.752M

837.9K

30.4%

Triangle ray intersections

673.3k:4690.5k (14.35%)

644.2k:10534.5k (6.11%)

98.7%:224% (42.6%)

"killeroos-view2.pbrt (Killeroos invisible)"

KD Tree

Lazy KD Tree

Ratio

build time (secs)

21.0s

4.7s

22.3%

total time (secs)

37.7s

27.9s

74.0%

Num of nodes made

2.752M

82

0.00298%

Triangle ray intersections

758.4k:2148.2k (35.30%)

758.4k:2148.2k (35.30%)

100%:100% (100%)

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

KD Tree

Lazy KD Tree

Ratio

build time (secs)

20.2s

4.7s

23.3%

total time (secs)

41.6s

47.9

115%

Num of nodes made

2.752M

229.9k

8.35%

Triangle ray intersections

644.2k:10534.5k (6.11%)

758.4k:2148.2k (35.30%)

118%:20.4% (578%)

"plants-view1.pbrt"

KD Tree

Lazy KD Tree

Ratio

build time (secs)

22.1s*

1.7s*

7.69%

total time (secs)

816s

1619s

198%

Num of nodes made

14.866M

6.581M

44%

Triangle ray intersections

20.257M:421.737M (4.80%)

20.257M:421.737M (4.80%)

100%:100% (100%)

"plants-view2.pbrt"

KD Tree

Lazy KD Tree

Ratio

build time (secs)

21.0s*

1.3s*

6.19%

total time (secs)

1465s

2152s

147%

Num of nodes made

14.866M

7.991M

54.0%

Triangle ray intersections

25.930M:754.291M (3.44%)

25.930M:754.291M (3.44%)

100%:100% (100%)

omg, the last render took forever!

* this data was abnormal (there were many 100% progress bars presented after the intial readout of this final time so it might not be entirely accurate).