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