Graphics Reference
In-Depth Information
2.
The object is added as a new child to an existing node.
The cost of the exist-
ing old node is
c
=
kArea
(old node). The new node will have a cost of
c
c
−
=
(
k
+
1)
Area
(new node). The incremental cost is therefore
d
=
c
=
k
(
Area
(new node)
−
Area
(old node))
+
Area
(new node).
3.
The object is added lower in the tree by means of recursing into a child volume.
In
this case, the number of children remains the same for the currently exam-
ined node. However, the node may change in size as a result of inserting the
object lower in the tree. The difference in cost becomes
d
=
k
(
Area
(new node)
−
Area
(old node)).
After examining the increase in cost for all available insertion alternatives, the least
expensive option is chosen at each step. It may happen that two or more subtrees
have the same increase in cost. Typically, this occurs toward the end of the con-
struction when objects lie fully within already existing bounding volumes. In this
case, Goldsmith and Salmon suggest breaking ties by inserting the object into the
bounding volume whose center it is closest to, or to use random selection.
Haines points out that a better selection rule is to apply insertion methods 1 and
2 to all available insertion alternatives and pick the one giving the best result. As a
convincing example he considers a node with two children, one large (50% of the
parent) and one quite small (1% of the parent). A new small object is added that
would cause no increase to the larger child but triple the size of the smaller child
to 3%. According to the original method, the new object would be inserted below
the larger child. However, when the root node is intersected the larger child is hit
50% of the time, and therefore the new object must also be intersected half the time.
In comparison, if the new object had been inserted below the smaller child the new
object would only be intersection tested 3% of the time. By applying both methods
1 and 2 and picking the node corresponding to the smaller value of the different
increases in cost, the better insertion position is selected.
6.3
Hierarchy Traversal
To determine the overlap status of two bounding volume hierarchies, some rule must
be established for how to descend the trees when their top-level volumes overlap. Is
the one hierarchy fully descended before the other one is? Are they both descended?
This descent rule is at the heart of the overlap code, and several alternatives are
explored ahead.
The two most fundamental tree-traversing methods are
breadth-first search
and
depth-first search
(Figure 6.4a and b). Breadth-first search (BFS) explores nodes at
a given depth before proceeding deeper into the tree, whereas depth-first search
(DFS) proceeds into the tree, searching deeper rather than wider, backtracking up
the tree when it reaches the leaves. Pure breadth-first and depth-first traversals are
