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.