Graphics Reference
In-Depth Information
In the rest of this section we shall assume the following:
(1) All surfaces
S
will be compact, connected, triangulated, and without boundary.
(2) All pwl curves in a surface
S
will have the property that if they meet a vertex
of
S
, then that vertex is a vertex for the curve.
(3) All pwl curves are assumed to be
simple
. All subdivisions will be proper.
Surfaces are assumed to be triangulated because triangular faces simplify argu-
ments. Fortunately, a polygon with v vertices and no holes or self-intersections can
always be triangulated in time O(v) (see Section 17.6). Furthermore, if a surface has
e edges, then it will have O(e) edges after triangulation. However, there is one point
that needs to be kept in mind with respect to the triangulation hypothesis. The number
of faces may have increased substantially. Therefore, if the big-O complexity of an
algorithm depends on the number of faces, then the triangulation has to be taken into
account.
Surfaces are not allowed to have a boundary because, like in the last section, the
boundary would cause problems that will not be addressed here. A typical surface
would therefore be the surface of a polyhedron in
R
3
. The assumption about pwl
curves being simple is justified by the fact that our goal is to find shortest curves and
these are all simple. Finally, note that subdividing either a curve or the surface has
no effect on the length of the curves or the geodesics in the surface.
The O(n
2
) solution to the discrete geodesic problem for polygonal surfaces with
n edges presented by Chen and Han in [CheH90] is too complicated to describe in its
entirety here, but we shall sketch the main steps for the convex case. Whether or not
a surface is convex has a great influence on the complexity of a shortest curve algo-
rithm. When a surface is not convex, one has to handle some complicating special
cases although the basic idea is the same as in the convex case.
The specific shortest path problem that we address is the “single source” shortest
path problem, namely, we seek an algorithm for finding a shortest pwl curve from
a fixed “start” point
s
of the surface
S
to all other points of
S
. We shall assume
that
s
is a vertex of the triangulation of
S
. The Chen and Han algorithm is actually
not the most efficient solution to the problem. Kapoor ([Kapo99]) has described an
O(n log
2
n) algorithm, but it is more complicated to describe. A number of other papers
prepared the ground for these algorithms. In particular, [MiMP87] is worthwhile
reading because it helps one see what the problems are when one is looking for short-
est paths. Other references can be found in that paper and in [CheH90]. The solution
in [MiMP87], which is not as efficient, is based on an argument that is similar to
Dijkstra's single-source shortest path algorithm for graphs.
Definition.
Two faces of
S
are
edge-adjacent
if they meet in a common edge. An
edge-adjacent sequence
of faces is a sequence F = (
f
1
,
f
2
,...,
f
k
) of faces
f
i
with
f
i
edge-adjacent to
f
i+1
. If
e
i
is the common edge of
f
i
and
f
i+1
, then the sequence
E = (
e
1
,
e
2
,...,
e
k-1
) is called the
edge sequence
defined by the sequence F. The
sequences F or E are said to be
simple
if no face or edge, respectively, appears more
than once in the sequence. Let
q
i
be a point in the
interior
of the edge
e
i
. The pwl
curve q = (
q
1
,
q
2
,...,
q
k-1
) is said to
connect
the edge sequence E. A pwl curve q in
S
of the form (
q
0
,
q
1
,
q
2
,...,
q
k-1
,
q
k
), where
q
0
and
q
k
are arbitrary points in
f
1
and
f
k
,
respectively, is said to
define
the edge sequence E.
