Graphics Reference
In-Depth Information
P
B
VR(V)
F
B
V,P
A
VR(F)
A
Figure 9.2
Two nonintersecting 2D polyhedra
A
and
B
. Indicated is the vertex-face feature
pair
V
and
F
, constituting the closest pair of features and containing the closest pair of points,
P
A
and
P
B
, between the objects.
9.2.1
The V-Clip Algorithm
The V-Clip algorithm operates on a pair of polyhedra and is based on the following
theorem, defining the closest points between the pair in terms of the closest features
of the polyhedra.
Theorem:
Let
F
A
and
F
B
be a pair of features from two disjoint convex polyhedra,
A
and
B
, and let
VR
(
F
A
) and
VR
(
F
B
) denote their Voronoi regions. Let
P
A
∈
F
A
and
P
B
∈
F
B
be a pair of closest points between the features. Then, if
P
A
∈
VR
(
F
B
) and
P
B
∈
VR
(
F
A
),
F
A
and
F
B
are a globally closest pair of features and
P
A
and
P
B
are a
globally closest pair of points between
A
and
B
(albeit not necessarily unique).
Figure 9.2 illustrates a pair of (2D) polyhedra satisfying the conditions of this
theorem.
V-Clip starts with two features, one from each input polyhedron. At each iteration
of the algorithm, the features are tested to see if they meet the conditions of the
theorem for being a closest pair of features. If so, the algorithm terminates, returning
a result of nonintersection along with the pair of closest features. If the conditions
are not met, V-Clip updates one of the features to a neighboring feature, where the
neighbors of a feature are defined as follows.
The neighbors of a vertex are the edges incident to the vertex.
●
The neighbors of a face are the edges bounding the face.
●
The neighbors of an edge are the two vertices and the two faces incident to
the edge.
●
Figure 9.3 shows a chart of the possible feature pairs and legal transitions between
them, according to the previously listed neighbor definitions. Solid arrows in the chart
indicate that the interfeature distance is strictly decreased by a transition. Dashed
