Game Development Reference
In-Depth Information
y 2
y 1
0
Figure 5.4. The Voronoi regions of the subsimplices of a triangle are bounded by dashed
lines. The origin lies in the Voronoi region of
{ y 1 }
. The plane test for subsimplex
{ y 1 ,
y 2 }
at y 1 is negative, since Δ { y 1 , y 2 }
2
= y 1 · ( y 1 y 2 ) < 0 .
Now, let v be the point closest to the origin of the simplex given by Y ,and
let X be the smallest subsimplex of Y that contains v . It is not very difficult to
see that v is also the closest point of the affine hull of X . So, a naive solution
for computing the closest point of a simplex would be to compute the closest
point of the affine hull of each subsimplex, reject the subsimplices for which
the barycentric coordinates of the closest point are not all positive, and of the
remaining subsimplices select the one that is closest to the origin.
However, we can do better than that. There is a cheaper way to determine
the closest subsimplex, and for this purpose, we introduce the concept of Voronoi
regions. Each subsimplex has a region of space associated with it in which the
origin must lie in order for that subsimplex to be the closest one. We call this the
Voronoi region of the subsimplex. Figure 5.4 shows the Voronoi regions of the
subsimplices of a triangle in two dimensions. In three dimensions, the Voronoi
regions are bounded by planes. By testing the origin against the planes, we can
quickly find the closest subsimplex. The Δ i values tell us on which side of a
Voronoi region the origin lies. A positive value indicates that the origin lies on
the inside of the associated Voronoi plane. The associated Voronoi plane of Δ i
is the plane orthogonal to X not containing y i . For example, in Figure 5.4, the
plane orthogonal to the edge
through y 1 is associated with Δ { y 1 , y 2 }
{
y 1 , y 2 }
.
2
The smallest X
Y such that v
conv( X ) can now be characterized as
I X and (b) Δ X∪{ y j }
the subset X for which (a) Δ i
> 0 for each i
0
j
for all j
I X . Thus, the origin lies within the bounds of subsimplex X but
not within the bounds of a bigger subsimplex containing X . Johnson's algorithm