Game Development Reference
In-Depth Information
volumes), but only their projection on 3D space. It is clear that false collisions can then
be detected (the projections overlap whereas the hyper-volumes are disconnected).
17.1.5 Assessment of detection of collision between
objects and open problems
In this part, we discussed collision detection for convex objects and then for non-convex
objects. We saw that the algorithms of the first category, most of them, have a linear
complexity according to the number of vertices. If the object is concave, then methods
are quadratic or at best, as per O ( n
log( n )). Detection of collision between convex
objects is thus more effective. The methods shown however have some problems:
×
Assumption of convexity: If we remove the problems shown in figure 17.3, we must
admit that certain algorithms like determination of non-intersection or minimum
distance calculations tolerate decomposing the object into convex parts. Unfortu-
nately, in case of deformable objects, the decomposition is not stable in time and
must be validated or even readjusted after each deformation. But, the construction
process is slow (NP-hard), difficult to install, generates numerous superfluous ele-
ments (surfaces, edges and vertices) and finally increases the number of objects to
be taken into account (Ponamgi et al., 1995);
Robustness: The algorithms are generally not very robust. They generally have sev-
eral degenerate cases that require special processing. Worse still, several algorithms
do not guarantee convergence. A possible solution is using interval arithmetic, but
no approach has been suggested to date. This lack of robustness is also reflected
when the same algorithm is called several times, even though several solutions are
available (for example, several vertices are at the minimum distance between two
objects). In this case, the algorithm successively provides one solution or the other,
which leads to an instability detrimental to the application.
Please note that other types of models are not discussed here because they are too
specific (implicit surfaces, parametric surfaces, objects defined in the form of voxels in
discrete geometry, CSG, etc.).
17.2 DETECTION PIPELINE
17.2.1 Problem
The algorithms we described in the first part of this chapter are expensive (quadratic
complexity). Acceleration phases are thus necessary to reduce the detection time. This
phase, called approximate detection (narrow-phase) , aims at quickly specifying the
zones of objects affected by a possible collision, i.e. the parts of an object on which
an accurate detection will be applied. Since the result corresponds to some assumed
collisions, the main role of this phase in practice is detecting certain non-collisions.
Besides, virtual environments often include a number of moving objects. Since the
exact collision processes only the interaction between a pair of objects, it is applied
to each pair of objects. The number of object pairs to be assessed is N
1) / 2,
therefore a complexity of O ( N 2 ) where N is the number of objects in the scene. These
×
( N