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

Search Nedrilad ::

Custom Search