Assignment 2 Lazy KD-Tree

Ryan Smith

Date submitted: 25 Apr 2006

Code emailed: 25 Apr 2006

Description of implementation approach and comments

Lazy Refinement of Primitives:

Initially, I build a Lazy Kd Tree with primitives that are not refined -- in other words, primitives that can't be intersected. When the primitives need to be intersected by a ray, I fully refine the primitive and use the new refined primitives to build a new Lazy Kd Tree. This Lazy Kd Tree plugs directly into the place where the old single, non-refined primitive was in the current Kd Tree. This trick comes straight from the Grid accelerator.

I chose to fully refine the primitives because the scenes we deal with most are made of subdiv surfaces, which refine into first a Triangle Mesh and then into a lot of Triangles. I thought that the step of a turning a primitive into a single Triangle Mesh essentially made a "wasted node" in the current Lazy Kd Tree.

However, I did put in some code to make sure that we refine only when we need to. Instead of just refining as soon as we even think about intersecting a primitive, I perform a bounding box test and only refine if the ray hits the bounding box. This actually saves some primitives in one of the killeroos scenes, and actually improved my performance ever so slightly.

Lazy Refinement of KD Tree:

I build the Lazy Kd Tree one level at a time. This is the most conservative way to do it, and it guarantees that you build only the levels of the tree that you need. It also has the nice property that you can maintain a fixed relationship between "aboveChild" and "belowChild" and avoid changing the size of the node structure.

The conservative, one-level-at-a-time approach isn't that great if you end up building the tree all the way anyways. Even though we build only a small portion of the tree in the plants images, the paths that are traversed take a lot of time building incrementally. I thought of changing the incremental depth that I would build the tree out to, but I decided not to do that because I had already committed to having a fixed relationship between "aboveChild" and "belowChild".

Stashing Temporary Data:

I wanted there to be a very quick lookup time between a Lazy node and the required data to continue building the tree when we traversed the Lazy node. I ended up using the "aboveChild"/primitives union to keep a flag (in the lowest bit) that was the Lazy flag. It turns out that pointers returned from malloc on linux are always 8 byte aligned, so I can use the bottom bit of a pointer without losing any data. I added a Lazy Params pointer to the "aboveChild" union -- you have to clear the bottom bit before you can use it, but it is directly available from the Lazy node when you go to convert it. It also means the node stays 8 bytes. This helped my performance on the bigger scenes, but it wasn't really the crux of the problem.

I've added some triangle counts to the tables below, because I thought they were interesting. My Lazy Kd Tree build times are 0.0 because I just added up what the progress reporter would tell me. For the total time, i've just used the "time" command.

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)

18.2

0.0

0%

total time (secs)

31.55

29.57

93.7%

Num of nodes made

2.752M

1.722M

62.6%

Triangle ray intersections

673.2K

826.8K

122.8%

Triangles created

532.2K

532.2K

100%

"killeroos-view2.pbrt (Killeroos invisible)"

killeroos-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

18.2

0.0

0%

total time (secs)

29.005

11.844

40.8%

Num of nodes made

2.752M

58

0%

Triangle ray intersections

758.4K

776.1K

102.3%

Triangles created

532.2K

6

0%

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

killeroos-view3

KD Tree

Lazy KD Tree

Ratio

build time (secs)

18.2

0.0

0%

total time (secs)

33.178

21.773

65.6%

Num of nodes made

2.752M

441.4K

16.0%

Triangle ray intersections

644.4K

1.018M

157.9%

Triangles created

532.2K

399.2K

75%

"plants-view1.pbrt"

plants-view1

KD Tree

Lazy KD Tree

Ratio

build time (secs)

50.4

0.0

0%

total time (secs)

625.791

964.148

154.1%

Num of nodes made

14.862M

4.545M

30.6%

Triangle ray intersections

20.291M

27.554M

135.8%

Triangles created

1.172M

1.172M

100%

"plants-view2.pbrt"

plants-view2

KD Tree

Lazy KD Tree

Ratio

build time (secs)

50.4

0.0

0%

total time (secs)

952.46

1621.34

170.2%

Num of nodes made

14.862M

5.816M

39.1%

Triangle ray intersections

25.843M

31.184M

126.1%

Triangles created

1.172M

1.172M

100%

RyanSmith/Assignment2 (last edited 2006-04-26 05:04:33 by RyanSmith)