Game Development Reference

In-Depth Information

Expressing proximity queries in terms of configuration space results in a more

convenient problem description and fewer special cases, since only one object

needs to be considered in our computations. For instance, the point closest to the

origin in
A

B
is unique for convex objects, whereas multiple closest-point pairs

may exist for a pair of convex objects. All closest-point pairs collapse to a single

closest point in the CSO.

Let us take a closer look at a number of proximity queries and their equivalent

in configuration space. Object
A
and
B
intersect if and only if the origin (zero

vector) is contained in
A

−

−

B
:

A

∩

B

=

∅≡

0

∈

A

−

B
.

This can be seen by the fact that if
A
and
B
intersect, they have a common point,

and thus, the vector from this point to itself is contained in
A

B
. Phrased

differently, the zero translation trivially results in a configuration of intersecting

objects.

The distance between
A
and
B
is the distance from the origin to
A

−

−

B
, i.e.,

the length of the shortest vector in
A

−

B
:

d
(
A, B
)=min

{

x

:
x

∈

A

−

B

}

.

We see that the distance can be defined as the length of the shortest relative transla-

tion that brings the objects into contact. The shortest relative translation is unique,

although a pair of closest points is not necessarily unique. For nonintersecting ob-

jects, closest points must lie on the boundaries of the respective objects. This is

not true for intersecting objects.

There also exists a measure for the amount of penetration. The
penetration

depth
is defined as the length of the shortest relative translation that separates two

intersecting objects:

p
(
A, B
)=inf

{

x

:
x

∈

A

−

B

}

.

We use infimum rather than minimum since all objects, including CSOs, are con-

sidered to be closed sets. As with closest points, witness points of a positive

penetration depth must lie on the boundaries of the respective objects.

Note that for computing a pair of closest points, or a pair of witness points

of the penetration depth, the CSO offers insufficient information, since the CSO

reflects only the relative configuration of objects. This is true for witness points

of any type of query on a CSO. If witness points are required, then additional

information concerning the actual objects
A
and
B
needs to be collected while

performing the query, as we shall find out further on.