Bounding Volume Hierarchies - Real-Time Collision Detection - page 246

procedure repeats until the set consists of a single bounding volume representing the
root node of the constructed tree.
Node *BottomUpBVTree(Object object[], int numObjects)
{
assert(numObjects != 0);
int i, j;
// Allocate temporary memory for holding node pointers to
// the current set of active nodes (initially the leaves)
NodePtr *pNodes = new NodePtr[numObjects];
// Form the leaf nodes for the given input objects
for (i = 0; i < numObjects; i++) {
pNodes[i] = new Node;
pNodes[i]- > type = LEAF;
pNodes[i]- > object = &object[i];
}
// Merge pairs together until just the root object left
while (numObjects > 1) {
// Find indices of the two "nearest" nodes, based on some criterion
FindNodesToMerge(&pNodes[0], numObjects, &i, &j);
// Group nodes i and j together under a new internal node
Node *pPair = new Node;
pPair- > type = NODE;
pPair- > left = pNodes[i];
pPair->right = pNodes[j];
// Compute a bounding volume for the two nodes
pPair->BV = ComputeBoundingVolume(pNodes[i]->object, pNodes[j]->object);
// Remove the two nodes from the active set and add in the new node.
// Done by putting new node at index 'min' and copying last entry to 'max'
int min = i, max = j;
if(i>j)min=j,max=i;
pNodes[min] = pPair;
pNodes[max] = pNodes[numObjects - 1];
numObjects--;
}
// Free temporary storage and return root of tree
Node *pRoot = pNodes[0];
delete pNodes;
return pRoot;
}