Game Development Reference
are completely included in the volume of another object (Sundaraj & Laugier, 2000).
To calculate the distance of interpenetration, the algorithms used for convex cases
are not suitable for concave cases; their collisions can be divided into several non-
connected components. Certain applications find only one distance, that of the smallest
translation that is sufficient to separate the objects, whereas other applications prefer
a measurement for each intersection zone. Though some methods are suggested (Kim
et al., 2002c), they are generally less robust and require very high calculation time.
We must also note that many recent approaches use distance maps (Eberhardt et al.,
2000; Guendelman et al., 2003): the position of a point is located on a pre-calculated
map and all we need to do is read the map and find at what depth the point is located.
This method requires updating during the deformations of the object (Fisher & Lin,
2001; Marchal et al., 2004). Approach used by Heidelberger et al. (2004b) avoids the
calculation (and update) of the distance map by using a tetrahedral mesh penetrating
an object. The edges of this mesh intersecting with the surface are found. Then the
approximate depth and direction of penetration of the vertices closest to the surface are
found. The same data for deeper vertices are calculated approximately by propagation
in the tetrahedral mesh. We would like to mention that these approaches for concave
objects also make it possible to detect the collisions of an object with itself (in case of
deformable objects, for example, fabrics).
17.1.4 Temporal approaches
The approaches described earlier are called spatial because they calculate the state of a
collision for a given state. Whereas, the detection required may not require character-
ising an intersection, but rather require the moment of contact. Thus it is necessary to
use methods which take the time component into account. However, this fourth dimen-
sion causes a significant increase in the complexity of calculations. The 4D methods
can be classified on the basis of the manner in which they consider the time parameter,
i.e. as a discrete function or as a continuous function.
184.108.40.206 Discrete temporal methods
The first group of methods is based on a discretisation of time 3 . In this case, the state
of the objects is inspected at the given moments of subdivision, using purely spatial
methods described above. Here we are talking about discrete temporal methods . The
moment of contact can be determined in various ways:
Dichotomy: A separation detection algorithm is used. When the response of the
algorithm is different at two successive moments, it means that the contact has
occurred at an intermediate moment. Then the interval is divided at its centre and
a new test is carried out at this moment. Then the interval where the response is
different at the two end points is selected The algorithm is reiterated until a small
interval that can give the desired finest approximation of the moment of contact
3 It involves discretisation of the interval separating two discrete times of the simulation loop.