Game Development Reference
environments are called N-body environments . To be effective, a collision detection
must therefore be applied only to those object pairs whose probability of collision is
high. In other applications, only the object handled by the user is moving ( 2-body
environments ). The detection then consists of inspecting the collision between the
object handled and the other objects of the environment, which represents a linear
complexity. In these environments, it is clearly desirable to apply collision detection
only to the objects close to the moving object. We observe that whether it is a 2-body
environment or an N-body environment, an acceleration phase that helps restricting
the collision detection to object pairs that are in probable collision is essential. This
phase is called proximity detection (broad-phase) .
The entire process of collision detection can thus be structured in the form of a
pipeline. The first step is finding the proximity. It eliminates the object pairs that will
never collide with each other and finds out the object pairs on which a more minute
detection needs to be applied. This phase is followed by an approximate detection
which lists the primitive pairs of an object intervening in the collision and thus requiring
a detailed processing. The third step called exact detection, provides, as per the case,
the primitives in intersection, inter-primitive distances, interpenetration depths, etc.
As we have already seen, several exact detection algorithms offer quick convergence
techniques, which can be compared to an acceleration (mainly distance calculation
algorithms). The last two steps are often found to be merged into a single step.
17.2.2 Proximity search (broad-phase)
If certain objects can never be connected by construction, a collision matrix made up of
Booleans indicating whether the two objects are likely to collide can be used (Garcia-
Alonso et al., 1994). In general, the proximity search uses two types of strategies:
Division of the space: Object pairs not in the same portion of the space are
Topological and kinematics criteria: The relative placement of objects with respect
to each other is considered. Sometimes the placement is associated with the speeds
(possibly relative) of displacement. If the objects are too far or if their speed is too
low for them to meet in the near future, the collision is impossible.
18.104.22.168 Strategies of detection by division of the space
The basic idea of the algorithms using spatial division is very simple: two objects
situated at far away locations in the space will never collide with each other in the near
future. By subdividing the space, we fix well separated zones and find in which zone
each object or each part of the object is located. Only the objects or parts of the object
in the same zone undergo a more minute detection. A natural division of the space
consists of dividing it into a regular mesh (Turk, 1989; Thatcher, 2000; Meseure et al.,
2003). If we want to save the memory when a fine mesh is used, uniform hierarchical
approach like octree (Turk, 1989; Bandi &Thalmann, 1995; Smith et al., 1995) or k-d
tree (Held et al., 1995) proves to be a good solution. Using a hash function can also
be very useful (Teschner et al., 2003). These space divisions are shown in figure 17.9.
The cutting planes in these approaches are relatively independent of the environment.