Game Development Reference
In-Depth Information
Collision detection
Philippe Meseure and Abderrahmane Kheddar
Virtual environments include static scenes and moving objects. These mobile objects
are either manipulated by the user or animated by a behavioural simulation following
the rules of physics or the interpretation of animation scripts. For a “realistic'' multi-
modal rendering, mainly in an interactive mode, the behaviour of the simulation and
hence that of the objects has to be credible for the operator's perception. The possible
interpenetration of virtual objects, when they collide and when they interact, reduces
this realism. Moreover, in case of rigid objects, it was observed that non-penetration
increases the perception of rigidity which helps offset the limitations of certain hap-
tic interfaces in terms of their capacity of force rendering. However, when we know
how a physical simulation engine operates and the foundations of the current graphic
libraries, we can very well guess that nothing can be predefined to prevent virtual
objects from interpenetrating. To avoid such unrealistic situations, the physical engine
controlling the simulation must check at very short and regular intervals whether two
objects are occupying the same position in space at the same time. This management
of interactions between objects is generally known as collision detection.
However, collision detection includes several techniques and goes beyond the scope
of merely the calculation of intersection between objects. The first part of this chap-
ter presents the concepts covered under collision detection. Whereas the latter part
describes the standard methods of collision detection assuming that the environment
is made up of polygons (which is in fact true in a large majority of virtual reality appli-
cations). We will then see how to adapt these methods to real time contexts by a series
of acceleration techniques. Finally, we will discuss the solutions that help processing
collision to either eliminate it or at least restrict it.
Implementation and installation of a collision detection algorithmdepend on the choice
of model that we make to represent the geometry of virtual objects. Some specific
collision detection models were suggested for objects defined by parametric surfaces
(for example, in CAD) or implicit surfaces (animation of organic structures). However,
most of the efficient algorithms were designed for polygon-based representations. In
that case, detection is between simple geometric primitives : polygon/polygon or even
triangle/triangle, which can be further reduced to the basic canonical tests: vertex
(point), edge (segment), surface. This representation has the advantage of being generic
Search Nedrilad ::

Custom Search