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

−

Search Nedrilad ::

Custom Search