• ShradhaBudhiraja
• Assignment2

The following 278 words could not be found in the dictionary of 615 words (including 615 LocalSpellingWords) and are highlighted below:

Assignment 2 Lazy KD-Tree

Shradha Budhiraja

Date submitted: 27 Apr 2006

Code emailed: 26 Apr 2006

NOTE: Have recently just uploaded image files instead of the links. I had to remove these files from AFS due to disk quota limitations. The image files are the same.

Description of implementation approach and comments

Lazy Implementation of KdTree

The kdtree was implemented to behave lazily. Initially, the tree only has one root with all primitives associated to it. The recursion was replaced by a lazy tree building. A node in the tree is split into its children only if it is intersected by a ray. Also the node was checked to have atleast 5 primitives. This number was arrived at empirically after trying out in different scenarios. This was done to avoid creating an extra node for very few primitives. This does have a tradeoff in the number of intersections per node, however it works better in some cases.

Lazy Refinement of Primitives

In the original implementation, all the primitives are fully refined into intersectables once they are alloted to a root node. In the lazy implementation, this was delayed until a ray intersected the node containing the primitive. Initially, the primitives were kept as they were received from the pbrt file. Whenever a ray intersects a node, its primitive/primitives is/are fully refined. The new set of primitives are built into another kdtree and this kdtree replaces the old primitive as a whole. This way the primitives did not have to be re-ordered or replaced in the original kdtree node and thus saved a lot of book-keeping. After a long discussion with Pat and some other students, I realised that it was not useful to restrict the level of refinement. This was because the surfaces used in these scenes do not have more than 2 levels of refinement, so it was not going to gain much. As a result, the primitives were refined in one step. Also, I tried to refine conservatively, meaning that a primitive was refined only if the ray actually hit it. But this seemed to work differently for the different scenes, it blew up the time in some cases. As a result, I did not include it in my final implementation.

Optimizations on a whole

The size of the node structure was not increased and was kept to 8 bytes to keep up with caching property. The children of a node were placed next to each other and as a result, above Child sufficed. Also, a bit in this union was used to specify if the node is lazy or not. Since mallocd pointers (pointing to Mailboxes) are byte aligned, the last bit could be used safely in this case. While accessing the pointer, however, this bit needed to be masked. The bounds of each node were not stored globally. They were calculated dynamically whenever the node was being split. Also, depth at each node was maintained in the loop that traversed the tree and built it as and when needed. I added a primitive id to Mailboxes to keep a track of the primitives. This, I believe led to some loss in time as we were no longer accesing just 8 bytes.

Performances

The killeroos did much better with the lazy implementation. However, killeroo1 either did the same or worse when the parameter of minimum primitives required in a node for it to be lazy was varied.

The plants scenes actually did worse. This was probably because, not only does it create a large number of primitives, but all of them are also visible. As a result, it was not really worth building the tree lazily and a one-time build would have been useful.

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"

In both the plant scenes, it apparently took a lot of time to load initial textures and this has not been included in the build time.

"plants-view2.pbrt"