Assignment 2 Lazy KD-Tree

Joyce Pan

Date submitted: 27 Apr 2006

Code emailed: 27 Apr 2006

Description of implementation approach and comments

My implementation was to start off with a single lazy node. Intersect runs the same as it did before, only my implementation would first check to see if the node was lazy. If lazy, then it would build on the lazy node. The new build function is similar to the original, only after splitting the node, it then checks to see which of the children the ray intersects. Then it will recursively build the children node that are intersected, and leave the non-intersected ones as lazy nodes. When it fits the requirements for a leaf, my implementation checks to see if the node carries refined primitives. Upon calling build, either all the primitives will be refined, or none. If the node is about to become a leaf, but if unrefined, then a function refines only the primitives inside the node and calls build on the node with new parameters carrying refined primitives. Therefore, the nodes for the KDtree were always consistent; I didn't create a kdtree of kdtrees.

The refined primitives were stored in a new struct called smallPrim. Each mailbox had a *smallPrim which pointed to a list of the refined primitives. The nodes therefore had smallPrim *oneprimitive and smallPrim** primitives.

The node had added on variables of two bools, refined and lazy, and the below child. At first, I attempted to union them similar to how the flags/split/nPrims was, but I separated them for debugging purposes. Other things I would've tried, had I more time, would be to not have a below child, since all the children were created next to each other (this was unplanned, but I noticed it as I ran my code).

For some odd reason, the 3rd image was the first to render, but after some debugging, it would stall, so I was never able to get the final stats on it. The first one also stalled, and didn't return the proper hit boolean. I'm going to put up images 2 and 3 of the killeroos and the stats for 2.

On a side note, I'm not sure what "build time" refers to, but mine should be 0, because it just establishes the first node.

Final Images Rendered with my implementation of heightfield.cpp

killeroos-view1.pbrt (Killeroos visible)

blank400x400

	KD Tree	Lazy KD Tree	Ratio
build time (secs)			%
total time (secs)			%
Num of nodes made			%
Triangle ray intersections			%

"killeroos-view2.pbrt (Killeroos invisible)"

killeroos-view2

	KD Tree	Lazy KD Tree	Ratio
build time (secs)		0	0%
total time (secs)	17.2	16.8	97.7%
Num of nodes made	2.754M	84	0.00003%
Triangle ray intersections	758.4K	776.1K	102.3%

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

killeroos-view3

	KD Tree	Lazy KD Tree	Ratio
build time (secs)			%
total time (secs)			%
Num of nodes made			%
Triangle ray intersections			%

"plants-view1.pbrt"

blank700x400

	KD Tree	Lazy KD Tree	Ratio
build time (secs)			%
total time (secs)			%
Num of nodes made			%
Triangle ray intersections			%

"plants-view2.pbrt"

blank700x400

	KD Tree	Lazy KD Tree	Ratio
build time (secs)			%
total time (secs)			%
Num of nodes made			%
Triangle ray intersections			%

$/!\$ Edit conflict - other version:

$/!\$ Edit conflict - your version:

$/!\$ End of edit conflict