Game Engine Architecture

618 12. Collision and Rigid Body Dynamics

single-point simplex is a point, a two-point simplex is a line segment, a three-

point simplex is a triangle, and a four-point simplex is a tetrahedron (see Fig-

ure 12.14).

GJK is an iterative algorithm that starts with a one-point simplex lying

anywhere within the Minkowski diff erence hull. It then att empts to build

higher-order simplexes that might potentially contain the origin. During each

iteration of the loop, we take a look at the simplex we currently have and

determine in which direction the origin lies relative to it. We then fi nd a sup-

porting vertex of the Minkowski diff erence in that direction—i.e., the vertex

of the convex hull that is closest to the origin in the direction we’re currently

going. We add that new point to the simplex, creating a higher-order simplex

(i.e., a point becomes a line segment, a line segment becomes a triangle, and

a triangle becomes a tetrahedron). If the addition of this new point causes the

simplex to surround the origin, then we’re done—we know the two shapes

intersect. On the other hand, if we are unable to fi nd a supporting vertex that

is closer to the origin than the current simplex, then we know that we can

never get there, which implies that the two shapes do not intersect. This idea

is illustrated in Figure 12.15.

Contains the Origin

y

x

A – B

Does not Contain

the Origin

y

A – B

A

B

A

B

x

Figure 12.13. The Minkowski difference of two intersecting convex shapes contains the origin,

but the Minkowski difference of two non-intersecting shapes does not.

Point Line Segment Triangle Tetrahedron

Figure 12.14. Simplexes containing one, two, three, and four points.