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.

−