Assignment 2 Lazy KD-Tree

Doug Johnston

Date submitted: 27 Apr 2006

Code emailed: 27 Apr 2006

Description of implementation approach and comments

I started by manying the lazy tree nodes first, putting the geometry aside. I kept the same structure as the kdtree, adding a LZ-Data structure to the class. I made everything that was reasonable as a vector. The new structure contained the bounds0 and bounds1, the prims0 and prims1, as well as their counts (although they we not strictly needed as I could have used prims.size(), but I kept them for consistancy), as well as the depth, badrefines, and the # of children the node had assigned. I also kept a boolean indicating whether the node was lazy or not. When both children were refined, the node lost its lazy status, and all the memory allocated in the LZ-data structure was released dynamically. I made an IsLazy() function to return the status, thinking I might try to add the lazy flag into the existing node with some bit-wise trickery, but it ended up not being an issue.

I put checks in the two intersect routines to see if it was traversing a lazy node. If so, I would build its children. It took a little while and a little care to get all the const variables mutated (?) properly, but after that was done, there weren't many issues to deal with.

Next, I tackled making the geometry lazier, which I had a significantly more difficult time with, and ended up costing me in the form of two late days. I still dont have a great implementation, but at least now, I've figured out exactly why. My plan was to convert the static array used in the kd-tree into a vector, and then only refine geometry right before it was to be added to a leaf node, if it wasn't intersectable, and then depending on how many primitives it refined into, either place it in the leaf node, or relize it made too many primatives, which would prevent the leaf not from being created, and then turn it into a lazy node instead. All of this worked, but it was terribly slow!! The simple killeroo scenes were taking 1000's of seconds. Why? I finally figured out that is was due to the way I was adding data to my mailBoxPrim vector. It was not in contiguous memory, and the hopping around took a large hit. This may be exaggereated by the fact that I'm working on a computer with a small and slow L2 cache, but still, the results were not acceptable. I rewrote the way I did it, and attempted to use the contiguous memory structures in the same was is done for the kdtree nodes. However, I kept running into memory erros that I could not correct. Because the renders were so slow using the previous implementation, I ran the tests below with full sets of refined geometry.

Final Images Rendered with my implementation of heightfield.cpp

killeroos-view1.pbrt (Killeroos visible)

killerroos-view1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

41.57

7.4

17.8%

total time (secs)

70.07

50.2

71.6%

Num of nodes made

2.752M

1.06M

38.4%

Triangle ray intersections

673.2k

673.2k

100%

"killeroos-view2.pbrt (Killeroos invisible)"

killerroos-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

41.4

7.4

17.9%

total time (secs)

64.9

32.16

49.55%

Num of nodes made

2.752M

97

00.00001%

Triangle ray intersections

758.4k

758.4k

100%

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

killerroos-view3

KD Tree

Lazy KD Tree

Ratio

build time (secs)

41.11

7.6

18.4%

total time (secs)

72.91

41.17

56.47%

Num of nodes made

2.752M

272.9k

9.91%

Triangle ray intersections

644.1k

644.1k

100%

"plants-view1.pbrt"

plants-view1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

105.497

56.75

53.8%

total time (secs)

727.5

933.25

128.3%

Num of nodes made

14.86M

7.46M

50.2%

Triangle ray intersections

20.29M

20.29M

100%

"plants-view2.pbrt"

plants-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

%

total time (secs)

%

Num of nodes made

%

Triangle ray intersections

%

DougJohnston/assign2 (last edited 2006-04-28 06:56:55 by DougJohnston)