Graphics Reference
In-Depth Information
these are not conclusive — especially because few experiments seem to have been
conducted with higher-degree trees.
Platform-architectural issues also play a significant role in what type of trees per-
form well. Ideally, trees should be laid out in memory so that nodes occur linearly
in memory during traversal. The issue of cache-efficient tree structures is revisited in
Chapter 13.
6.2 Building Strategies for Hierarchy Construction
As the number of possible trees grows exponentially in terms of the number of ele-
ments in the input set, an exhaustive search for the best tree is infeasible. This rules
out finding an optimal tree. Instead, heuristic rules are used to guide the construction,
examining a few alternatives at each decision-making step, picking the best alterna-
tive. Arriving at a suboptimal solution is not necessarily a problem, as there is usually
a very large number of trees that are not too far from optimal.
There are three primary categories of tree construction methods: top-down , bottom-
up , and insertion methods (Figure 6.2). Top-down (or divisive) methods proceed by
partitioning the input set into two (or more) subsets, bounding them in the chosen
bounding volume, then recursing over the bounded subsets. Thanks to the ease with
which they can be implemented, top-down methods are by far the most popular.
However, they do not generally result in the best possible trees.
Top-down
A B C D
A B
C D
ABCD
(a)
Bottom-up
ABCD
ABCD
ABCD
(b)
Insertion
C
A
A
B
AB
ABCD
(c)
Figure 6.2 A small tree of four objects built using (a) top-down,
(b) bottom-up, and
(c) insertion construction.
 
Search WWH ::




Custom Search