Graphics Reference
In-Depth Information
P
lies in the Voronoi region associated with edge
Q
1
Q
2
if and only if the following
inequalities are satisfied:
(
P
−
Q
1
)
·
(
Q
2
−
Q
1
)
≥
0
(
P
−
Q
2
)
·
(
Q
1
−
Q
2
)
≥
0
(
P
−
Q
1
)
·
((
Q
2
−
Q
1
)
×
n
123
)
≥
0
(
P
−
Q
1
)
·
(
n
142
×
(
Q
2
−
Q
1
))
≥
0,
where
n
123
=
(
Q
2
−
Q
1
)
×
(
Q
3
−
Q
1
)
n
142
=
(
Q
4
−
Q
1
)
×
(
Q
2
−
Q
1
).
If
P
does not lie in a vertex or edge Voronoi region, face regions are tested by
checking if
P
and the remaining point from
Q
lie on opposite sides of the plane
through the three points from
Q
chosen to form the face. For example,
P
lies in the
Voronoi region of
Q
1
Q
2
Q
3
if and only if the following inequality holds:
((
P
−
Q
1
)
·
n
123
)((
Q
4
−
Q
1
)
·
n
123
)
<
0,
where again
n
123
=
(
Q
2
−
Q
1
)
×
(
Q
3
−
Q
1
).
Analogous sets of inequalities can be defined for testing containment in the
remaining vertex, edge, and face Voronoi regions. Note that most of the computed
quantities are shared between different Voronoi region tests and need not be recom-
puted, resulting in an efficient test overall. Simplex sets of fewer than four points are
handled in a corresponding way.
If what was just described seems familiar, it is because the routines given in
Sections 5.1.2, 5.1.5, and 5.1.6 — for finding the point on a segment, on a trian-
gle, and on a tetrahedron closest to a given point, respectively — utilize exactly
the same approach. Indeed, the original implementation of the GJK algorithm also
uses this optimized case-based approach to implementing the distance subalgorithm
[Ruspini].
