Graphics Reference
In-Depth Information
Insertion strategies can be as fast as or even faster than top-down methods and
could produce better results. They are considered on-line methods in the sense that
not all objects need be present when the process starts. That they are on-line methods
also allows them to be used for updating an already existing tree, making them
useful for dynamic systems. It is therefore somewhat surprising that very few collision
detection systems report using incremental construction methods.
6.2.3.1 The Goldsmith-Salmon Incremental Construction Method
An interesting algorithm for constructing bounding volume hierarchies for use in
ray tracing is described in [Goldsmith87], with improvements found in [Haines88].
As before, objects are inserted one at a time, at the position deemed most optimal.
A single path from root to leaf is traversed by descending into the child with the
smallest increase in bounding volume surface area, were the object to be inserted as
a child of it.
The reason surface area is used follows from a result of projective geometry, stating
that the average projected area of a convex 3D volume is one-fourth its surface area.
Furthermore, the conditional probability that a random ray hits a confined bound-
ing volume B if it hits a parent bounding volume A can therefore be shown to be
proportional to the ratio of their surface areas. The root volume can conveniently be
used as volume A throughout all computations, allowing the division to be avoided
by directly comparing the conditional probabilities instead.
As surface areas are only used in ratios, they only have to be given within a constant
factor, as the constant factor cancels out. For a bounding box of dimensions x , y , and
z , the area can be computed as x ( y
+
z )
+
yz , and for a sphere of radius r the area can
be computed as r 2 .
Now when a ray hits the root volume at least an additional k intersection tests
must be performed, where k is the number of children of the root. This property also
holds for any node, not just the root. Accounting for the conditional probability that
a node is hit only if its parent is hit, the total average cost for hitting a node becomes k
times the node's surface area divided by the surface area of the root node. Specifically,
the cost of the root node is the number of children it has, and the cost of a leaf node
is zero (as its cost was included in the cost of the parent). The total cost for a tree can
now be calculated in O ( n ) time as the sum of the cost of all nodes.
The tree cost can also be computed incrementally as the tree is built. This is imple-
mented by passing on an incremental “inheritance cost” to the child nodes as the
hierarchy is traversed during insertion. This cost corresponds to the increase in vol-
ume for ancestor volumes, due to the insertion of the object into the tree. To this is
then added the cost of inserting the object at the current position according to the
three different choices for insertion:
1. The object and a leaf node are paired under a new node. The incremental change to
the inheritance cost for this case is d
=
2 Area (new node). This case also applies
when pairing the object and the old root under a new root.
Search WWH ::




Custom Search