Game Development Reference
In-Depth Information
Figure 5.1. Two convex objects (left) and their CSO (right).
types. An overview of GJK is presented in this chapter. But first let us get ac-
quainted with the concept of translational configuration space.
5.2 Configuration Space
Proximity queries on pairs of objects are often expressed more conveniently in
terms of the pair's configuration space. The translational configuration space
of two objects is the space of relative translations between the two objects. For
objects A and B being simultaneously translated over, respectively, vectors c A
and c B , the relative translation between A and B is the vector c B
c A .From
a collision detection point of view, we do not care too much about the absolute
translations and only need to focus on the relative translation.
We regard relative translations of a pair of objects as points in the objects'
configuration space. Some relative translations result in a configuration of inter-
secting objects. The set of such relative translations is called the configuration
space obstacle (CSO) of the pair of objects. (See Figure 5.1 .) For convex shapes,
the CSO is convex as well. In formal terms, the CSO of objects A and B is the
set of all vectors from a point of B to a point of A :
A
B =
{
A, b
B
}
a
b : a
.
The term “configuration space obstacle” originates from robot-motion planning,
where it denotes the set of coordinates in configuration space that are not admis-
sible. The CSO can be visualized as the object we get by “brushing”
B ,the
reflection of B in the origin, along each point of A . For example, the CSO of an
arbitrary object and a sphere centered at the origin is the original object enlarged
in all directions by the sphere's radius. Figure 5.1 shows the CSO of a box and a
cone.