• alexli
• hw2

You are not allowed to do AttachFile on this page. Login and try again.

Assignment 2 Lazy KD-Tree

Alex Li

Date submitted: 26 Apr 2006

Code emailed: 26 Apr 2006

Description of implementation approach and comments

I based my approach on the suggestions in the assignment handout. The first optimization I tried was the lazy construction of the kdtree. I initially build out the tree to a certain depth, and mark all unfinished nodes as "lazy". Then when we do the ray traversal, when a ray hits a lazy node, I determine whether it should be a leaf or interior and build the node accordingly. If it is an interior node, the split is found and two lazy children are created below it. The traversal code than proceeds the same as the old kdtree code (handling the newly minted leaf or interior node just as it would in a normally built kdtree). I tested with different initial build depths -- it turns out that whether building out to 5 initially or not at all results in about the same performance. In the end, I opted to be super lazy, and not build out the tree initally at all.

I ran into some trouble keeping the kdtreenode at its original 8 byte size. Because we were creating nodes on the fly, we could not use the convention of storing the first child immediately after the parent in order to save holding the first child pointer. I got around that by storing child pointers next to eachother. Although we lose a little of the caching benefits of having one child immediately next to the parent, this is a worthwhile optimization simpley because it keeps the node at 8 bytes. The other problem was where to stick the bit that denotes a lazy node. Since both the lazy node and leaf node holds a pointer in its bottom 4 bytes, we could hide the flag in the lowest order bit and just mask it out when using the pointers. Hence, the kdtree node is still 8 bytes.

The other major optimization was to do lazy refining of primitives. My approach was pretty simple. No refining of the primitive initially. When we hit a leaf, and the primitive(s) is unrefined, we refine it one level then create a new kd-tree with the refine primitves, then intersect the tree. (The object-oriented approach is nice, cuz we can call Intersect regardless of whether its a real primitive or another kdtree).

Final Images Rendered with my implementation of heightfield.cpp

killeroos-view1.pbrt (Killeroos visible)

"killeroos-view2.pbrt (Killeroos invisible)"

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

"plants-view1.pbrt"

"plants-view2.pbrt"