Game Development Reference

In-Depth Information

be non-negative, in which case
x
is a
convex combination
of
Y
. The smallest

X

. In other words, the

set
X
is found by discarding all the points
y
i
from
Y
whose coordinate for
x
is

zero.

Having to deal with inequality constraints that bound the coordinate domain is

quite inconvenient. So as a first step, we seek to compute the closest point of the

affine hull rather than the convex hull of a set of vertices. The
affine hull
aff(
X
)

of a set of points
X
is the set of affine combinations of
X
. The affine hull of a set

of vertices is a point, a line, a plane, or the whole space. Barycentric coordinates

of points on an affine hull still sum to one; however, they can be negative.

The barycentric coordinates of the point
v
closest to the origin of an affine

hull can be computed by solving a linear system of equations. Let
v
=
λ
1
y
1
+

···

⊆

Y
such that
x

∈

conv(
X
) is the set
X
=

{

y
i
:
λ
i
>
0

}

+
λ
n
y
n
. First of all, the barycentric coordinates need to sum to one, so

λ
1
+

+
λ
n
=1is the first equation. Secondly, the vector (from the origin

to point)
v
is orthogonal to the affine hull. More specifically,
v

···

·

(
y
i
−

y
j
)=0for

any
y
i
,
y
j
∈

1 linearly in-

dependent equations. For example, in order to warrant that a vector is orthogonal

to a triangle, the vector must be orthogonal to two edges of the triangle. Thus, for

asetof
n
points, we have
n
linear equations that uniquely determine the closest

point.

Johnson's algorithmuses a recursive formulation for the solution of the system

of equations. Each subsimplex
X
of
Y
is represented by a set of indices
I
X
⊆

{

X
. Substituting
v
by the expression above yields
n

−

be a

subsimplex. Then, the barycentric coordinates of the closest point of aff(
X
) are

given by

1
,...,n

}

,where
n
is the number of vertices in
Y
.Let
X
=

{

y
i
:
i

∈

I
X
}

λ
i
=
Δ
i

Δ
X
,

and Δ
i

is defined recursively as

Δ
{
y
i
}

i

=1
,

=

i∈I
X

Δ
X∪{
y
j
}

j

Δ
i
(
y
i

·

(
y
k
−

for
j

∈

I
X
and any
k

∈

I
X
,

y
j
))

and finally, Δ
X

is defined as

Δ
X
=

i

Δ
i
.

∈

I
X

This recursive solution is obtained by applying Cramer's rule and cofactor expan-

sion [van den Bergen 03].