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].
Search Nedrilad ::

Custom Search