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. I'm pretty sure that the plants images go so slowly because I am just adding overhead to the same tree that would have been built in one fell swoop originally. 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 primitive 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-view2.pbrt (Killeroos invisible)"

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

"plants-view1.pbrt"

"plants-view2.pbrt"