Graphics Reference
In-Depth Information
(a)
(b)
(c)
Figure 3.25
The three types of Voronoi feature regions of a 3D cube. (a) An edge region.
(b) A vertex region. (c) A face region.
between two neighboring Voronoi feature regions considered to belong to only one
of the regions. Because the Voronoi regions create a partitioning of the space exterior
to a polyhedron, they can be used, for instance, to determine the closest point on a
convex polyhedral object to some point
Q
in space. This determination is done by
walking from region to region until
Q
is found to be inside the region. The closest
point on the object to
Q
is then the projection of
Q
onto the feature with which the
given region is associated. For repeated queries, it is possible to exploit coherence by
remembering from frame to frame which region the closest point was in and start the
new search from there. The concept of Voronoi regions is used in several intersection
tests, described in Chapter 5. Voronoi regions are also discussed in Chapter 9, in the
context of intersection of convex polyhedra.
3.11
Minkowski Sum and Difference
Two important operations on point sets will be referred to throughout parts of this
topic. These operations are the
Minkowski sum
and the
Minkowski difference
of point
sets. Let
A
and
B
be two point sets, and let
a
and
b
be the position vectors corre-
sponding to pairs of points in
A
and
B
. The Minkowski sum,
A
⊕
B
, is then defined
as the set
=
a
B
,
⊕
+
:
∈
∈
A
B
b
a
A
,
b
where
a
b
is the vector sum of the position vectors
a
and
b
.Visually, the Minkowski
sum can be seen as the region swept by
A
translated to every point in
B
(or vice versa).
An illustration of the Minkowski sum is provided in Figure 3.26.
+
