Graphics Reference
In-Depth Information
15.3.2.5
Lemma.
Assume that
S
is a convex surface with n faces.
(1) A shortest path cannot traverse more than n faces.
(2) Two shortest paths from the start point
s
can only intersect in
s
and their
endpoint.
Proof.
See [ShaS86].
We now look for a criterion that rejects edge-adjacent sequences of faces that
cannot possibly come from a shortest curve.
Definition.
Given a point
p
and a set
X
, define infCone(
p
,
X
), the
infinite cone on
X
from
p
, by
(
)
=+
{
[
)
}
inf
Cone
pX
,
p
s
px
s
Υ
0
,
,
x X
Œ
.
Definition.
Given a point
p
and sets
X
and
Y
, define proj(
p
,
X
,
Y
), the
projection of
X
on
Y
from
p
, by
(
)
=
(
)
«
proj
pXY
,
,
inf
Cone
pX
,
Y
.
Now let F
k
= (
f
1
,
f
2
,...,
f
k+1
) be an edge-adjacent sequence of faces in
S
with
associated edge sequence E
k
= (
e
1
,
e
2
,...,
e
k
) and unfolding map n
k
. Recall that n
k
maps all faces
f
i
into the plane of
f
k+1
. Assume that the start point
s
is the vertex of
f
1
opposite the edge
e
1
. Let
s
¢ and
e
¢ be the unfolding of
s
and
e
i
with respect to n
k
,
respectively.
Definition.
Define the subsets proj
s
,i
, 1 £ i £ k, of
e
i
recursively as follows:
proj
proj
=
=
e
,
s
,
1
1
proj
(
nn
()
s
,
(
proj
)
,
e
)
,
i
>
1
.
s
,
i
i
i
s i
,
-
1
i
Call proj
s
,i
a
shadow
of the start point
s
on edge
e
i
. We shall call
f
i+1
a face
shadowed
by the edge
e
i
with respect to the sequence F
i
.
Figure 15.8(b) shows what the shadow proj
s
,5
would look like. Because our surface
is convex, we could stop our edge-adjacent sequence of faces at that point since
e
6
cannot belong to a shortest edge sequence. In fact, proj
s
,6
would be the empty set.
Basically, proj
s
,i
defines a cone from
s
in which all shortest paths with edge sequence
(
e
1
,
e
2
,
e
3
,
e
4
,
e
5
) would have to lie. The algorithm for finding shortest paths for convex
surfaces uses these shadows to control the search that one has to perform. Algorithm
15.3.2.1 is an outline of an algorithm for finding shortest edge sequences. One builds
a tree whose nodes, other than the root, consist of quadruples of the form
N = (
e
,
f
,
p
,proj
s
,
e
), where
e
is an edge of the face
f
in the surface
S
,
p
is a point in the plane of
f
that is an unfolding of
s
, that is,
p
=n(
s
) where n is
an unfolding map to the plane of f, and
proj
s
,
e
is a subset of
e
that is a shadow of
s
.
Note that a face can be shadowed by each of its three edges.
Definition.
The set cone(
p
,proj
s
,
e
) «
f
is called the
shadow of
s
in N
.
