Graphics Reference
In-Depth Information
if (numObjects <= MIN_OBJECTS_PER_LEAF) {
pNode-
>
type = LEAF;
pNode-
>
numObjects = numObjects;
pNode-
>
object = &object[0];
// Pointer to first object in leaf
} else {
pNode-
>
type = NODE;
// Based on some partitioning strategy, arrange objects into
// two partitions: object[0..k-1], and object[k..numObjects-1]
int k = PartitionObjects(&object[0], numObjects);
// Recursively construct left and right subtree from subarrays and
// point the left and right fields of the current node at the subtrees
TopDownBVTree(&(pNode->left), &object[0], k);
TopDownBVTree(&(pNode->right), &object[k], numObjects - k);
}
}
Apart from the selection of what bounding volume to use, only a single guiding
criterion controls the structure of the resulting tree: the choice of how the input set
is partitioned into two subsets. As a set of
n
elements can be partitioned into two
nonempty subsets in 2
n
−
1
1 ways, it is clear that only a small subset of all partitions
can reasonably be considered.
To simplify the partitioning, the set is usually divided into subsets using a split-
ting hyperplane. As it is not possible to guarantee selecting a splitting plane that
does not cut across any primitives, any straddling primitives must be dealt with
when partitioning the set. One solution is to split the primitive into two, assign-
ing the parts to their respective subsets. Splitting of primitives allows the child
bounding volumes to be smaller, minimizing their overlap, possibly completely elim-
inating it. A drawback with splitting straddling primitives is that any split primitives
can again become subject to splitting, potentially giving rise to a huge increase of
primitives.
A perhaps more common solution is not to split the primitive but to let the position
of its centroid with respect to the splitting plane determine which subset it goes in.
Using the centroid to determine which subset to assign the primitive to attempts to
minimize the overlap between the sibling bounding volumes. This way, the bounding
volume will be extended in width by half the width of the primitive. If the primitive
had instead been arbitrarily assigned to either subset, in the worst case the bounding
volume for the subset could have been extended by the full width of the primitive.
−
6.2.1.1 Partitioning Strategies
A simple partitioning method is the
median-cut algorithm
. Here, the set is divided in
two equal-size parts with respect to their projection along the selected axis, resulting
