Game Development Reference

In-Depth Information

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.

17.1.4.1 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

is found;

3
It involves discretisation of the interval separating two discrete times of the simulation loop.

Search Nedrilad ::

Custom Search