Assignment 2
Implementation
Lazy Refinement
I realized that, when I needed to perform an intersection test upon a non-intersectable primitive, I could not simply refine it and spit any new primitives which result into the existing Kd-Tree. Problems would arise because other nodes may contain this primitive as well. If this 1 primitive becomes 8000, it would be very difficult to update all the other nodes and let them know about their new contents. This would likely involve allocating new arrays a good deal of copying.
Therefore, since Kd-Trees are primitives as well, I decided that upon intersecting a leaf node containing an unrefined primitive, I would replace that primitive with a Kd-Tree that contains the primitive. In the constructor of each new Kd-Tree I conduct the actual refinement. I look at my list of primitives and if this list contains one primitive which is non-intersectable then I refine until I have more than one primitive or the one primitive I have can be intersected. By not fully refining a primitive the first time I strike it, I support lazy refinement of primitives with multiple levels of containment, such as ShapeSets. By refining until I have at least one intersectable primitive, I avoid creating a Kd-Tree which immediately contains another Kd-Tree, as when a LoopSubdiv refines to a single TriangleMesh before finally refining to individual Triangles.
Data for Unfinished Nodes
- putting kd-trees in nodes b/c I don't want to dynamically increase the # of
- mailboxes, which would invalidate ptrs in nodes which haven't been finished
- kept node data at 8bytes by smart flagging and by only storing address of "below" child node, making sure "above" is allocated next.
- added Weight() function to all Primitives so that I can divide nodes fairly when they have unrefined primitives inside
- instead of using extra bit for unfinished flag (further reducing accuracy
- and halving the number of possibly contained primitives) I'm reserving 0xFFFFFFFF which only cuts down the number of possibly contained primitives by 1
- storing a number of parameters in UnfinishedNodeData. These are simply allocated and deleted, which bothers me. I do pass them on for re-use though. Once a node becomes a leaf it has to delete its unfinished data since it will have no more children to pass it to.
- moved some pre-allocated data into KdTreeAccel so it doesn't have to bloat UnfinishedNodeData
- hitting an unrefined primitive makes a new KdTreeAccel containing that primitive. Inside the new KdTree, I refine until I have at least 1 fully refined primitive OR I have more than 1 primitive.
Results
View: 1
|
pbrt K-D Tree |
my Lazy K-D Tree |
Ratio (lazy/non-lazy reference) |
build time (secs) |
580 |
413 |
0.71 |
total time (secs) |
1095 |
929 |
0.85 |
nodes made |
9.76M |
3.58M |
0.37 |
Triangle ray intersections |
2231k |
2345k |
1.05 |
View: 2
|
pbrt K-D Tree |
my Lazy K-D Tree |
Ratio (lazy/non-lazy reference) |
build time (secs) |
585 |
302 |
0.52 |
total time (secs) |
1155 |
872 |
0.75 |
nodes made |
9.77M |
1.89M |
0.19 |
Triangle ray intersections |
4.84M |
5.37M |
1.11 |
View: 3
|
pbrt K-D Tree |
my Lazy K-D Tree |
Ratio (lazy/non-lazy reference) |
build time (secs) |
582 |
98 |
0.17 |
total time (secs) |
1032 |
548 |
0.53 |
nodes made |
9.77M |
0.14M |
0.01 |
Triangle ray intersections |
4.86M |
6.49M |
1.34 |
View: 3 Refined
|
pbrt K-D Tree |
my Lazy K-D Tree |
Ratio (lazy/non-lazy reference) |
build time (secs) |
- |
238 |
- |
total time (secs) |
- |
689 |
- |
nodes made |
- |
0.36M |
- |
Triangle ray intersections |
- |
6.78M |
- |