Game Development Reference

In-Depth Information

the body goes through topological modifications (ruptures, cuts, etc.). In general, the

BVHs for deformable bodies are usually at least one order of magnitude slower than

the methods meant for rigid bodies.

17.2.3.2 Strategies using graphic hardware

An original approach for collision detection involves using graphic supports, provided

that all the objects processed are made up of triangular surfaces. The first group of

methods detect the collision by recovering the triangles present in a bounding volume

defined by the sight cone (Lombardo et al., 1999). This approach is restricted by the

only two types of sight cones that can be used by the graphic hardware (parallelepiped

box or pyramid with truncated rectangular base, which can possibly be modified by

cutting planes). The second group of solutions uses the data once the triangles are

converted into pixels on the screen (Forgue & Shinya, 1991; Zachmann, 1994; Baciu

et al., 1999; Hoff et al., 2001; Kim et al., 2002b; Heidelberger et al., 2004a). These

approaches work in the memory
space
of frame, depth and stencil. The stencil is

essential in most of the approaches suggested. Each pixel of the memory of the frame

is associated with an integer which can be modified by various elementary operations

at the same time as the associated pixel. Collision detection is based on the following

principle. There is an intersection between two objects if at least one point of one of the

objects is found inside the other. The test of inclusion is simple. A point of an object
A

is inside an object
B
, if odd number of surfaces of B are cutting the segment joining the

point of
A
with the observer (assumed to be sufficiently far in order to be outside
B
).

More specifically, we can also say that there is an additional front face compared to the

number of rear faces. The problem then lies in finding a point verifying this property.

For this purpose, after having traced object
A
, we display the front faces of
B
by

increasing the values of the stencil and display the rear faces of
B
by decreasing these

values. Thanks to the depth test (
Z-buffer
algorithm), only those parts of faces of
B

which are located between the observer and the points of
A
are traced. Once the tracing

is completed, in each pixel, the stencil contains the difference between the number of

front faces and the number of rear faces for all the segments between the observer

and the points of
A
. If one of the values in the stencil is an odd number (in fact 1),

then the corresponding point of
A
is in
B
. The general principle of the algorithm is as

follows:

Algorithm 1
: Detection by Stencil

Set all buffers to 0

Activate the test and the writing of the Z-buffer

Selective tracing
of object
A

Deactivate the writing in the
Z-buffer

Activate the incrementation of the stencil

Display the
front faces
of object
B

Activate the decrementation of the stencil

Display the
rear faces
of object
B

Read the stencil

Check if the stencil contains an odd integer

Search Nedrilad ::

Custom Search