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