Game Development Reference
In-Depth Information
(Klosowski et al., 1998; Larsson &Möller, 2001). The choice of the BVH used is made
from a compromise between:
The speed of processing and the level of subdivision: In fact, the time for passing
through and processing the hierarchy of bounding volumes can become critical if
a certain level of subdivision is crossed;
Storage memory: It is necessary to take into account the additional cost of storing
the structure used for the hierarchy or spatial subdivision;
Update of the positions during the movement : This step, if not optimised, can
prove to be expensive in terms of calculation time. Besides, certain volumes require
updates even in case of simple rotations (AABB, k -DOP) and all the volumes need
to be updated in case of deformable objects;
Useful volume/bound volume ratio: This ratio must ideally be close to 1 (for
example, it is not optimal to use a sphere for a rod, as the space occupied by
the sphere is relatively too large than the rod, which might lead to carrying out
too many pointless tests. Another criterion to measure the appropriateness of the
bounding volume is minimising the Hausdorff distance, defined as the upper limit
of all the lower distances between the points of the object and the bounding volume.
Numerous optimisations, not related to the type of volumes, are necessary to avoid
losing the time taken in thoroughly passing through the tree structures: using spa-
tial and temporal coherence by Generalized Front Tracking (Ehmann & Lin, 2001):
between two hierarchies, we do not start by inspecting the roots, but immediately test
the bounding volumes that have proved the non-collision of two objects in the previous
time interval. Though a number of BVH installations were offered, very few use all the
acceleration techniques. Moreover, to ensure detection at critical times, the approaches
do not aim at detecting all the collisions, but only the most important ones: stopping
the collision at a lower level after a time out (Hubbard, 1996), detection depend-
ing on the perception (O'Sullivan & Dingliana, 1999), stochastic detections (Klein &
Zachmann, 2003; Kimmerle et al., 2004).
These hierarchies are designed for polyhedrons of complex shapes, often concave,
or polygon soups. They make it possible to quickly find the primitive pairs that are
either in collision or are closest to each other. However, the hierarchical structure is
more suitable for rigid bodies than deformable bodies. In case of deformation, it is
necessary to recalculate the volumes in every node of the tree (i.e. 2 n
1 nodes to be
inspected for n primitives stored in the tree). Therefore the hierarchies for deformable
bodies are mainly based on AABB (Smith et al., 1995; Bergen, 1998; Meseure et al.,
1998) or k -DOP tree structures because updating them in case of deformations is
quicker. A study by Larsson and Möller (2001) shows that one update from the top of
the hierarchy rather than from the bottom is quicker because it reduces the recalculation
to only the tested bounding volumes.
Recently, a method was suggested in James et al. (2004); it helped determining
the position and the shape of any bounding volume in the hierarchy on the basis of
an approximate description of the deformation (assumed to be low). Then, Larsson
and Möller (2001) indicated that a construction using the topological surroundings is
generally more effective after deformation than a construction using the geometrical
surroundings of the non-deformed object. However, this argument is null and void if
Search Nedrilad ::




Custom Search