• MattiasBergbom
• Assignment2

Assignment 2 Lazy KD-Tree

Mattias Bergbom

Date submitted: 27 Apr 2006

Code emailed: 27 Apr 2006

Description of implementation approach and comments

I went about this assignment a bit too optimistically, trying to regard to every last bit of memory space and ending up with a real kludge that just wouldn't work. Once I realized I wasn't going anywhere with that one, I restarted and went with a much simpler approach instead.

I use the same type of array to store the nodes as in the original kdtree but with the addition that it can grow dynamically, and with that risking being reallocated. Thus, I only store byte offsets instead of raw pointers. Nodes are initialized 2-by-2, siblings always neighboring eachother to avoid the need of an extra child pointer in the node data struct. I also borrowed an extra bit from the flags union to store an 'isLazy' flag, and added a pointer to a 'PendingData' struct to the other union, all in all keeping the size of the nodes to 8 bytes.

By using the Intersect() and IntersectP() loops and the stack from the original kd-tree, and only adding a special case for when a node is lazy, I was hoping to keep the extra complexity down. Once a lazy node is approached, I compute the split plane and divide the primitives just as usual, and create two new lazy nodes which I initialize with all the data necessary to resume building the tree there at a later point. And this is probably the most obvious place needing improvement; with some work one could easily avoid initializing one of the children as lazy, and thus avoid the memory fragmentation etc. involved in allocating a new PendingData struct on the heap and also a new array of ints to store all its primitives.

Anyhow, once reaching a leaf, I check for any unintersectable primitives, refine those one step, and if the result is more than one primitive I stick it in a new lazy kd-tree and replace the original reference in the global primitives vector with the new tree's reference.

And that's about it as far as implementation goes. The result is somewhat disappointing but given the amount of time I wasted on the first approach I'm quite happy I ended up with any images at all. There's obviously lots of room for improvement; given that the poor times posted for the plants scene depend heavily on memory restrictions and thus excessive swapping, one should probably focus on the memory consumption. Except eliminating for the double-allocation I mentioned above one could also imagine e.g. using more global buffers, such as for the edge tables, and also recursively building a node down a certain couple of steps, just to avoid extra allocations as far as possible.

Update: The code that I submitted has a fix in it that limits the max depth of the tree to 32 as opposed to a previous, debug-purposed value. This gives a more consistent behaviour (~160% time) in the larger scenes, mainly due to less swapping.

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