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

∈