Graphics Reference
In-Depth Information
After the MST has been calculated and the edges sorted into a list in ascending order
of weight, the weights are grouped into a set of families.
The first two weights in this list form the first family
F
0
. Defining
u
i
and
s
i
as the
mean and standard deviation of the weights in family
F
i
, a subsequent weight
w
on
the list is considered belonging to the family
F
i
if
w
2
s
i
. Whenever a weight
is added to a family, the associated mean and standard deviation of the family are
updated. When a weight is found not to belong to a family, it and the next weight
on the list form a new family. This process repeats until all weights on the list have
been assigned to a family. Finally, when all families have been determined the BCT
is transformed into an
n
-ary tree by merging all adjacent clusters that belong to the
same family.
<
u
i
+
6.2.3
Incremental (Insertion) Construction
The last type of construction approach is the
incremental
or
insertion
method. Here,
the tree is built by inserting one object at a time, starting from an empty tree. Objects
are inserted by finding the insertion location in the tree that causes the tree to grow
as little as possible according to a cost metric. Normally the cost associated with
inserting an object at a given position is taken to be the cost of its bounding volume
plus the increase in volume its insertion causes in all ancestor volumes above it in
the tree.
If the object being inserted is large compared to the existing nodes, it will tend
to end up near the top of the hierarchy. Smaller objects are more likely to lie within
existing bounding volumes and will instead end up near the bottom. When the new
object is far away from existing objects it will also end up near the top. Overall, the
resulting tree will therefore tend to reflect the actual clustering in the original set of
objects.
Because the structure of a tree is dependent on the objects inserted into it and
because insertion decisions are made based on the current structure, it follows that
the order in which objects are inserted is significant. Using the objects in the order
defined by the authoring tool can result in bad hierarchies that do not reflect the actual
object clustering. Sorting the data suffers from the same problem, only more so. To
avoid degenerate behavior, the best approach seems to be to randomly shuffle the
objects before insertion.
A simple insertion method implementation would be to perform a single root-leaf
traversal by consistently descending the child for which the insertion into would be
cheaper. Then the insertion node would be selected from the visited nodes along the
traced path such that the total tree volume would be minimized. As an
O
(log
n
) search
is performed for each object inserted, the total complexity becomes
O
(
n
log
n
). A more
advanced implementation would examine the entire tree, proceeding in a best-first
manner by maintaining a search front using a priority queue, descending into the
currently best node at all times. Both methods are described in [Omohundro89] in
terms of creating sphere trees.
