Differences between revisions 6 and 7

Assignment 2 Lazy KD-Tree

Tom Brow

Date submitted: 25 Apr 2006

Code emailed: 25 Apr 2006

Description of implementation approach and comments

Lazy tree construction

In my implementation, I chose to expand each node of the tree only when it was intersected. I modified the function KdTreeAccel::buildTree tree such that instead of recursively calling itself on the children after a split, it would initialize either child as a "lazy" node with a pointer to a data structure that stored all of the parameters necessary to call buildTree on that node later. My approach required me to alter kdtree's original node allocation system, since that system does not allow for the tree to be built out of order. Because my new system requires that each node store the index of both of its children, I was forced to switch up to a 16-byte node structure. I also made some of the memory chunks that are normally passed through buildTree into data members of KdAccelTree, since they are reused throughout rendering as the lazy tree is constructed.

Lazy primitive refinement

To avoid refining primitives that are not in fact visible to the camera, I refined each non-intersectable primitive (and replaced it with a new kd-tree) only when the leaf node containing it was intersected. I did not treat non-intersectable primitives differently than geometric primitives during tree construction, possibly resulting in poorer splits. This would account for the fact that my implementation consistently calls more ray-triangle intersections than the original kdtree.

Results

My implementation outperforms the original kdtree in two of the "killeroo" scenes, but performs significantly worse in the "plant" scenes. This may be because the runtime of intersections dominates over the time saved on tree construction and primitive refinement in those scenes.

Final Images Rendered with my implementation of lz-kdtree.cpp

killeroos-view1.pbrt (Killeroos visible)

attachment:kill1.jpg

	KD Tree	Lazy KD Tree	Ratio
build time (secs)	3.5	0.0	inf%
total time (secs)	15.9	16.3	97.5%
Num of nodes made	546.2k	587.4	93.0%
Triangle ray intersections	675.5k	826.9k	81.7%

"killeroos-view2.pbrt (Killeroos invisible)"

attachment:kill2.jpg

	KD Tree	Lazy KD Tree	Ratio
build time (secs)	3.5	0.0	inf%
total time (secs)	14.1	10.7	131.8%
Num of nodes made	546.2k	47	1162127.7%
Triangle ray intersections	776.1k	776.1k	100.0%

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

attachment:kill3.jpg

	KD Tree	Lazy KD Tree	Ratio
build time (secs)	3.5	0.0	inf%
total time (secs)	17.2	15.7	109.6%
Num of nodes made	546.2k	141.1k	387.1%
Triangle ray intersections	645.6k	1019k	63.5%

"plants-view1.pbrt"

attachment:plants1.jpg

	KD Tree	Lazy KD Tree	Ratio
build time (secs)	50.3	0.0	inf%
total time (secs)	630.9	981.7	64.2%
Num of nodes made	14.9M	4.0M	372.5%
Triangle ray intersections	20.3M	27.6M	73.5%

"plants-view2.pbrt"

attachment:plants2.jpg

	KD Tree	Lazy KD Tree	Ratio
build time (secs)	41.3	0.0	inf%
total time (secs)	900.9	1520.2	59.3%
Num of nodes made	14.9M	5.2M	286.5%
Triangle ray intersections	25.8M	31.2M	82.7%

Deletions are marked like this.	Additions are marked like this.
Line 13:	Line 13:
To avoid refining primitives that are not in fact visible to the camera, I refined each non-intersectable primitive only when the leaf node containing it was intersected. I did not treat non-intersectable primitives differently than geometric primitives during tree construction, possibly resulting in poorer splits. This would account for the fact that my implementation consistently calls more ray-triangle intersections than the original kdtree.	To avoid refining primitives that are not in fact visible to the camera, I refined each non-intersectable primitive (and replaced it with a new kd-tree) only when the leaf node containing it was intersected. I did not treat non-intersectable primitives differently than geometric primitives during tree construction, possibly resulting in poorer splits. This would account for the fact that my implementation consistently calls more ray-triangle intersections than the original kdtree.