Graphics Reference
In-Depth Information
// Bound all objects in BV, forming leaf nodes. Insert leaf nodes into a
// dynamically changable insertion-built BV tree
InitializeInsertionBVTree(t, object, numObjects);
// For all nodes, form pair of references to the node and the node it pairs
// best with (resulting in the smallest bounding volume). Add all pairs to
// the priority queue, sorted on increasing volume order
InitializePriorityQueue(q, object, numObjects);
while (SizeOf(q) > 1) {
// Fetch the smallest volume pair from the queue
Pair *p = Dequeue(q);
// Discard pair if the node has already been paired
if (HasAlreadyBeenPaired(p->node)) continue;
// Recompute the best pairing node for this node to see if
// the stored pair node is still valid
Node *bestpairnode = ComputeBestPairingNodeUsingTree(t, p-
>
node);
if (p-
>
pairnode == bestpairnode) {
// The store pair node is OK, pair the two nodes together;
// link the nodes together under a new node
Node *n = new Node;
n-
>
left = p-
>
node;
n-
>
right = p-
>
pairnode;
// Add new node to BV tree; delete old nodes as not possible to pair with
Delete(t, p-
>
node);
Delete(t, p-
>
pairnode);
Insert(t, n);
// Compute a pairing node for the new node; insert it into queue
Node *newbestpairnode = ComputeBestPairingNodeUsingTree(t, n);
p = Pair(n, newbestpairnode);
} else {
// Best pair node changed since the pair was inserted;
// update the pair, reinsert into queue and try again
p = Pair(p->node, bestpairnode);
}
Enqueue(q, p, VolumeOfBVForPairedNodes(p));
// Queue, pair, priority
}
return Dequeue(q)-
>
node;
}
A similar approach, specifically for building sphere trees, is presented in [Omo-
hundro89].
