Graphics Reference
In-Depth Information
Bottom-up (or agglomerative) methods start with the input set as the leaves of the
tree and then group two or more of them to form a new (internal) node, proceeding
in the same manner until everything has been grouped under a single node (the root
of the tree). Although bottom-up methods are likely to produce better trees than the
other methods, they are also more difficult to implement.
Insertion methods build the hierarchy incrementally by inserting objects one
at a time into the tree. The insertion position is chosen so as to minimize some
cost measurement for the resulting tree. Insertion methods are considered on-line
methods, whereas both top-down and bottom-up methods are considered off-line
methods in that they require all primitives to be available before construction starts.
A benefit of on-line methods is that they allow updates to be performed at runtime.
Very little research has been done on insertion methods for constructing collision
detection hierarchies.
As noted earlier, even though most hierarchy construction takes place during a
preprocessing stage, it is still important to find fast construction methods. Any algo-
rithms of
O
(
n
2
) complexity and above are likely to be too slow for building hierarchies
from a larger number of primitives.
To simplify the presentation, in the following sections the discussion has primarily
been limited to binary trees. The same methods typically also apply to
n
-ary or even
general trees.
6.2.1
Top-down Construction
A top-down method can be described in terms of a recursive procedure. It starts out by
bounding the input set of primitives (or objects) in a bounding volume. These primi-
tives are then partitioned into two subsets. The procedure is now called recursively to
form subhierarchies for the two subsets, which are then connected as children to the
parent volume. The recursion stops when the input set consists of a single primitive
(or, if elected, earlier than that), at which point the procedure just returns after cre-
ating the bounding volume for the primitive. The following code fragment illustrates
how top-down construction can be implemented.
// Construct a top-down tree. Rearranges object[] array during construction
void TopDownBVTree(Node **tree, Object object[ ], int numObjects)
{
assert(numObjects > 0);
const int MIN_OBJECTS_PER_LEAF = 1;
Node *pNode = new Node;
*tree = pNode;
// Compute a bounding volume for object[0], ..., object[numObjects - 1]
pNode->BV = ComputeBoundingVolume(&object[0], numObjects);
