Graphics Reference
In-Depth Information
10.3
Testing Concave Objects
A method that avoids the false positives on concave geometry returned by the algo-
rithm of Section 10.2 is found in [Knott03a, Knott03b] and is described here. Recall
that two objects
A
and
B
(whether convex or concave) are in collision if and only if
they have a point in common. When
A
and
B
are polyhedral, they intersect if and
only if part of an edge of one object lies inside the volume of the other object. Thus,
if
A
and
B
intersect there exists a point on some edge of either object that belongs to
both objects. A ray cast from this point — in any direction, but in particular toward
the viewer — passes through the boundary of object
A
(or object
B
) an odd number
of times (effectively exiting the solid object one more time than it is entering it). This
scenario is illustrated in Figure 10.4. In (a), objects
A
and
B
are shown in perspective,
with only the edges of object
B
drawn. Illustration (b) shows the objects from the side,
here with four rays cast from different edges of
B
toward the viewer. Of the four rays,
one passes through the boundary of object
A
an odd number of times, indicating that
A
and
B
must be intersecting. To ensure proper collision detection, a ray test must be
performed for all points on all edges of object
B
against the volume of object
A
.Ifan
intersection is not detected, the edges of object
A
must be tested against the volume
of object
B
in a second pass.
Using graphics hardware, all required ray intersection tests of one pass can be
effectively performed in parallel with the help of stencil buffer tests. Three major
steps are involved.
0. Initialize:
Disable color buffer writes.
●
Initialize depth and stencil buffers.
●
Enable depth buffer testing.
●
B
0
4
1
2
B
A
A
(a)
(b)
Figure 10.4
Drawing the edges of
B
and then testing these against the faces of
A
using
the described algorithm corresponds to performing a point-in-polyhedron query for all pixels
rasterized by the edges of
B
, testing if any ray from a pixel toward the viewer intersects object
A
an odd number of times.
