Game Development Reference

In-Depth Information

need to find at most one face aligned with the contact plane. Then intersect that

face with the other shape's face—and we have our contact manifold. High-poly

objects (like a curvy sports car) may need to have a lot of faces aligned with the

contact plane, so this simple method needs to be adjusted. But let's examine the

toy cubes.

Usually we can recover a shape feature (vertex, edge, or face) that is closest

to the support contact plane from our collision algorithm. If we have a degenerate

case like edge-face, face-face, or a pair of parallel edges, we'll usually have a

vertex-face or edge-edge pair to start with, but we want to expand both features to

larger features (edge-edge

face-face). From the smaller shape feature (vertex

or edge), we can examine all adjacent edges and faces and choose the one (edge

or face) that is most aligned with the support contact plane within some tolerance

α
. That is, we want to find a face that is tilted at most by angle
α
from
s
.Ifno

face is aligned, we want an edge. And if no edge is aligned enough, we'll have

to live with one vertex. Whatever feature we find, let's call it the contact feature

(contact vertex, edge, or face).

To find a contact face, we just need to compute the alignment of the edges be-

cause for a face to be aligned with the contact plane, its edges need to be aligned.

Another important reason is more subtle: to compute how aligned the edges are,

we compute the dot product of the edge vector and the contact normal. When it's

close to zero, the value of the dot product is approximately the length of the edge

multiplied by the angle between the edge and the contact plane. That's a good

number to compare to the threshold. Equivalently, we could compute the differ-

ence between the heights of the edge vertices above the contact plane—a value

we may already have cached when we computed the support function, if we deal

with really low-poly shapes like cubes.

If we compute a face's alignment with the contact plane using
n

→

s
,we'll

end up with the cosine of the face tilt angle relative to
s
. That value needs to

be close to 1
.
0 for the face to be aligned, and it isn't very sensitive to the face

tilt at small angles, but it is very sensitive to round-off errors. That is because

unlike the dot product of the edge vector with the normal, this cosine is changing

as 1

·

o
(
x
2
) instead of
o
(
x
).Thevariable
x
is the very small angle between the

face (or edge) and the contact plane, so
x
2
isn't a good value to compare to a very

−

G
(
F
)

Gauss map of feature
F

n
0
∠
n
1

Angle between vectors
n
0
and
n
1

S
2

Unit sphere:
{
n
∈
R
3
:
||
n
||
=1
}

Spherical cap on
S
2
:
{
x
∈
S
2
:(
s
∠
x
)
≤ α}

C
(
α,
s
)

The border of
C
,thecircle:
{
x
∈
S
2
:(
s
∠
x
)=
α}

δC

Ta b l e 4 . 5 .
Notation guide.