Game Development Reference
measure for the error can be found by multiplying the upper and lower bounds by
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 }
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 ε .
arbitrary point in A
s A−B (
w >ε 2 do
point closest to the origin of conv( Y );
Y such that v
conv( X );
s A−B (
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 }
λ i y i , where
λ 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