Graphics Reference
In-Depth Information
ideas of accelerating the search for supporting vertices are further elaborated on in
Chapter 9.
A
supporting plane
is a plane through a supporting point with the given direction
as the plane normal. A plane is supporting for a polytope if all polytope vertices lie
on the same side of the plane as the polytope
centroid
. The centroid of a polytope
defined by the vertex set
{
P
1
,
P
2
,
...
,
P
n
}
is the arithmetic mean of the vertex positions:
(
P
1
+
P
n
)/
n
.
A
separating plane
of two convex sets is a plane such that one set is fully in the
positive (open) halfspace and the other fully in the negative (open) halfspace. An axis
orthogonal to a separating plane (parallel to its normal) is referred to as a
separating
axis
. For two nonintersecting convex sets, it can be shown that a separating axis
(or plane) always exists. The same is not necessarily true for concave sets, however.
Separating axes are revisited in more detail in Chapter 5.
The surface of a polyhedron is often referred to as a 2
-manifold
. This topological
term implies that the neighborhood of each point of the surface is topologically
equivalent (or
homeomorphic
) to a disk. A polyhedron surface being 2-manifold implies
that an edge of the polyhedron must connect to exactly two faces (or the neighborhood
of a point on the edge would not be disk-like).
The number of vertices
P
2
+···+
(
V
)
, faces
(
F
)
, and edges
(
E
)
of a polyhedron relate accord-
ing to the
Euler formula V
2. It is possible to generalize the Euler formula
to hold for polyhedra with holes. The Euler formula is revisited in Chapter 12.
+
F
−
E
=
3.8.1
Testing Polyhedral Convexity
Similar to the convexity test for a polygon, a polyhedron
P
is convex if and only if for
all faces of
P
all vertices of
P
lie (strictly) on the same side of that face. A separate
test for coincident vertices and collinear edges of the polyhedron faces is required to
make the test robust, usually with some tolerance added for determining coincidency
and collinearity. The complexity of this test is
O
(
n
2
).
A faster
O
(
n
) approach is to compute for each face
F
of
P
the centroid
C
of
F
,
and for all neighboring faces
G
of
F
test if
C
lies behind the supporting plane of
G
. If some
C
fails to lie behind the supporting plane of one or more neighboring
faces,
P
is concave, and is otherwise assumed convex. However, note that just as the
corresponding polygonal convexity test may fail for a pentagram this test may fail for,
for example, a pentagram extruded out of its plane and capped at the ends.
3.9
Computing Convex Hulls
Among other uses, convex hulls can serve as tight bounding volumes for collision
geometry. Many different algorithms for computing convex hulls have been proposed.
