Game Development Reference

In-Depth Information

measure for the error can be found by multiplying the upper and lower bounds by

v
k

:

2

v
k

−

v
k

·

w
k
.

This value is an upper bound for the squared distance between
v
k
and the closest

point of
A

B
[Gilbert et al. 88, van den Bergen 03].

For any pair of convex objects
A
and
B
, the sequence

−

{

v
k
}

indeed converges

to the closest point of
A

B
[Gilbert et al. 88,van den Bergen 03]. Therefore, Al-

gorithm 1, which describes the GJK distance algorithm in pseudocode, terminates

in a finite number of iterations for any positive error tolerance
ε
.

−

Algorithm 1
The GJK distance algorithm. Point
v
approximates the point closest to the

origin of
A − B
within a distance of
ε
.

v
←

arbitrary point in
A

−

B
;

W

←∅

;

w

←

s
A−B
(

−

v
);

2

w
>ε
2
do

while

v

−

v

·

begin

Y

←

W

∪{

w

}

;

v

←

point closest to the origin of
conv(
Y
);

W

←

smallest
X

⊆

Y
such that
v

∈

conv(
X
);

w

←

s
A−B
(

−

v
);

end
;

return

v

5.5

Johnson's Algorithm

For computing the point closest to the origin of a simplex, and for determining the

smallest subsimplex that contains the closest point, we use a subalgorithm called

Johnson's algorithm. Let
Y
=

be the set of vertices of a simplex.

Then, any point
x
of the simplex may be described as an
affine combination
of
Y

in the following way:

{

y
1
,...,
y
n
}

n

n

x
=

λ
i
y
i
,
where

λ
i
=1.

i
=1

i
=1

The coefficients (
λ
1
,...,λ
n
) are the barycentric coordinates of
x
with respect

to
Y
. In order for
x
to be contained in conv(
Y
), the barycentric coordinates must