Game Development Reference
In-Depth Information
Figure 17.9 Various types of spatial divisions: regular mesh, octrees and k-d trees
(b)
(f)
(c 1 )
(c 2 )
(d)
(e)
(e)
(f)
(b)
(a)
(c 1 )
(d)
(a)
(c 2 )
M
Figure 17.10 BSP Algorithm
These techniques are thus recommended in the N-body type of contexts. Please note
that every movement of an object implies updating the list of zones which it penetrates
or quits, which requires an additional processing time.
In 2-body contexts, it is more advantageous to use environment-based division
structures: BSPs ( Binary Space Partitioning ) are commonly used in video games not
only for visualisation, but also for collision detection (see figure 17.10). The principle is
based on the division of the space into two parts. The first sub-space is called “positive''
and the second sub-space is called “negative'' as per the given geometrical criterion. We
continue dividing the sub-spaces on the same principle and finally obtain a hierarchy
of sub-spaces which can be represented by a binary tree. It is also possible to use
suitable tetrahedral meshes (Held et al., 1995; Geiger, 2000) (the space is divided into
tetrahedrons; some of their surfaces are polygons of static objects of the environment).
17.2.2.2 Strategies of detection by topology and kinematics
The topological strategies use the position of objects with respect to each other to find
the pairs of close objects. The kinematic methods consider their movement and ignore
them if they are not moving towards each other or if their speed does not allow them
to meet. These methods are meant for N-body environments.
Certain topological approaches are based on a classification of objects. Several
classifications have been suggested (Held et al., 1995; Overmars & van der Stappen,
1996). Sweep and prune is the most commonly used algorithm among these approaches