Graphics Reference
In-Depth Information
0-simplex
1-simplex
2-simplex
3-simplex
Figure 3.20
Simplices of dimension 0 through 3: a point, a line segment, a triangle, and a
tetrahedron.
When a support point is a vertex, the point is commonly called a
supporting
vertex
.
A
support mapping
(or
support function
) is a function,
S
C
(
d
), associated with a convex
set
C
that maps the direction
d
into a supporting point of
C
. For simple convex
shapes — such as spheres, boxes, cones, and cylinders — support mappings can be
given in closed form. For example, for a sphere
C
centered at
O
and with a radius
of
r
, the support mapping is given by
S
C
(
d
)
r
d
/
d
(Figure 3.21b). Convex
shapes of higher complexity require the support mapping function to determine a
supporting point using numerical methods.
For a polytope of
n
vertices, a supporting vertex is trivially found in
O
(
n
) time
by searching over all vertices. Assuming a data structure listing all adjacent vertex
neighbors for each vertex, an extreme vertex can be found through a simple hill-
climbing algorithm, greedily visiting vertices more and more extreme until no vertex
more extreme can be found. This approach is very efficient, as it explores only a
small corridor of vertices as it moves toward the extreme vertex. For larger polyhedra,
the hill climbing can be sped up by adding one or more artificial neighbors to the
adjacency list for a vertex. Through precomputation of a hierarchical representation
of the vertices, it is possible to locate a supporting point in
O
(log
n
) time. These
=
O
+
d
P
=
S
c
(
d
)
P
=
S
C
(
d
)
C
C
(a)
(b)
Figure 3.21
(a) A supporting vertex
P
of polygon
C
with respect to the direction
d
. (b) A
supporting point
P
of circle
C
with respect to the direction
d
. In both cases,
P
is given by the
support mapping function
S
C
(
d
).
