Game Development Reference
In-Depth Information
be the face's normal and will be the point shared between areas A i =
G
( v i ) ,
i =0 ,...,n .
In SAT, we seek supporting features for opposite directions in two colliding
shapes A and B . Thus, to find the pair of supporting features for a direction s ,
we can find where
s lies in
G
( A ) for shape A support. For shape B ,we'llfind
where s lies in
G ( B ), or, equivalently, where
s lies in the negated Gauss map
−G ( B ), with each x ∈G ( B ) mapped to
x ∈−G ( B ).
Let's superimpose
G
( A ) and
−G
( B ) and call the result
S
. It lets us intuitively
and quickly see the pair of features for any direction s . 8
It also shows that if
the Gauss maps
( f B ) with features f A on A and f B on B do not
overlap, there is no separating direction where those features would be the pair of
supporting features, and it doesn't make sense to check them. For example, if the
Gauss maps of a pair of edges do not intersect, we don't have to check that pair
of edges. This eliminates a lion's share of edge pairs to check. It also has another
important consequence.
Whenever a pair of features overlap on
G
( f A ) and
−G
, those two features are the support-
ing features in any direction that belongs to both of them on
S
. There's no need
to build a DK hierarchy or perform a supporting feature search: in that direction,
we already have all the information to compute the translation distance. If edges
are collinear on
S
, we don't need to take them into account because there will be
several face-vertex feature pairs attaining the same distance. Vertex-vertex inter-
sections form an infinity of possible SA directions, but fortunately, we don't need
to check them if our shapes penetrate. If they don't penetrate, we can easily estab-
lish a candidate SA as a line going through both vertices. If the vertices coincide
(hence we can build no line), we can just assume the shapes penetrate.
If the normal n of a face in A is outside of
S
( v B ), we don't need to
check that face-vertex pair. We probably still need to check direction n as a
candidate SA, because n will surely be inside at least one spherical polygon
−A
−G
( v B ), unless we establish that the corresponding vertex cannot be a
separating supporting feature. It is possible to establish, for example, whether the
vertex is on the “far end” of the convex hull from the other shape (see http://www
.codercorner.com/blog/?p=24 for details of the idea). But more importantly, it lets
us reduce the support computation to a mere dot product. Wherever area
=
−G
−A
is
overlapped by n ,
will correspond to the supporting vertex v B on the shape
B . The signed distance of v B to f A is the separating distance between shapes A
and B in the direction n .
−A
8 However, we are not interested in just any direction due to SAT. For penetrating objects, the only
interesting directions are face normals and directions orthogonal to a pair of edges from both shapes.
The latter are the points of intersection between edges on S : remember that points on the Gauss map
are also unit vectors, defining directions in R 3 .