Graphics Reference
In-Depth Information
Following the logic of earlier sections, one of the more meaningful merging criteria
is to select the pair so that the volume of their bounding volume is minimized. A
brute-force approach for finding which two nodes to merge is to examine all possible
pairs, compute their bounding volume, and pick the pair with the smallest bounding
volume. The brute-force approach requires
O
(
n
2
) time. Repeated
n
−
1 times to form
a full tree, the total construction time becomes
O
(
n
3
).
6.2.2.1 Improved Bottom-up Construction
A more sophisticated implementation can improve on the performance of the
brute-force approach substantially. Instead of constantly recomputing the preferred
minimum volume pairings for each node, the nodes can keep track of their preferred
pairing nodes and the new volume for the pair. Then, at any given time the node with
the smallest stored volume and its stored pairing node would be the best pair of nodes
to merge. These (
node
,
pairing node
,
volume
)-tuples can be effectively maintained in a
data structure such as a priority queue (heap or binary search tree) sorted on volume,
allowing fast access to the minimum volume entry.
Whenever a new pair is formed, most of the stored minimum volume pairings
remain the same. Only the stored pairings involving either one of the two newly
paired nodes are affected. More importantly, when they change, the stored volume
for the pair can only increase. This allows the pairing node to be recomputed lazily,
delaying the calculation to the time the pair is extracted from the priority queue.
In effect, the algorithm becomes an iteration wherein the currently best pair is
removed from the queue. If the node has already been paired, the pair is simply
discarded and the next best pair is extracted. If not, the best pairing node for the node
is calculated. If it matches the stored pairing node, this pair must be the minimum
volume pair and they can be merged. If it does not match, the pairing node must have
been paired in an earlier step, so the node and the new pairing node are reinserted
into the priority queue under a new volume priority value.
The missing piece is how to quickly calculate the pairing node that forms the
smallest volume when paired with a given query node. Interestingly, a dynamic
bounding volume tree (in particular, the top-down incremental insertion algorithm
presented later on) is a suitable data structure for holding the bottom-up fragments
of the tree as it is constructed! Given such a structure, the pairing node is located
by searching from the top of the tree, descending into all children the query volume
intersects. When the query volume is found in the hierarchy, the pairing node is
the other child of the parent volume (that is, the sibling node). The following code
fragment demonstates how the improved algorithm can be implemented.
Node *BottomUpBVTree(Object object[], int numObjects)
{
PriorityQueue<Pair> q;
InsertionBVTree t;
