Graphics Reference
In-Depth Information
Vertex-
vertex
Vertex-
edge
Edge-
edge
Vertex-
face
Edge-
face
Figure 9.3
Feature pair transition chart in which solid arrows indicate strict decrease of
interfeature distance and dashed arrows indicate no change.
arrows indicate no change in distance taking place. Because the chart does not contain
a transition cycle of only dashed arrows, only a finite number of feature transitions
can be performed before the feature distance is strictly decreased. In addition, there
are no transitions that increase the interfeature distance. Therefore, convergence is
assured and the algorithm eventually terminates with the closest pair of features (and
thus, implicitly, with a closest pair of points).
One of the transitions in the chart of Figure 9.3 does not follow from the neighbor
definitions: the (solid) arrow from the vertex-face state back to itself. This transition
is present because it is possible for the V-Clip algorithm to become trapped in a local
minimum in the vertex-face state. The problem occurs for objects in configurations
similar to that shown in Figure 9.4, where the vertex
V
lies below the supporting plane
of face
F
and at the same time lies inside allVoronoi planes of theVoronoi region,
VR
(
F
),
of
F
. In this situation there are no legal state transitions per the chart of Figure 9.3.
Any attempted transition would either increase the interfeature distance or increase
the dimension of a feature while the interfeature distance stayed the same, neither
of which are allowed by the algorithm. When this problem situation is detected, an
O
(
n
) brute-force test is performed of the vertex
V
against all face planes of object
A
.If
V
lies inside all face planes, the objects are intersecting and the algorithm stops and
reports the objects as penetrating. Otherwise,
F
is updated to the face
G
of
A
that
V
has the largest positive signed distance from. This choice of a new face guarantees
there is no possibility of descending into the same local minimum again, in that
V
is
strictly closer to
G
than to
F
and is at least as close to
G
as to all other faces of
A
.
The test for the features being a closest pair of features is handled differently for
each of the five possible feature pair types, the details of which are too elaborate to
explore here. Unlike the Lin-Canny algorithm, V-Clip avoids explicitly computing
