Graphics Reference
In-Depth Information
Input:
a convex surface
S
with n faces
a vertex
s
of
S
called the start point
Output:
a node tree T
node
= quadruple (
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
,
proj
s
,
e
is a subset of
e
that is a shadow of
s
node tree
T;
integer
i;
edge
e
¢;
point set
X
;
Initialize T to consist of simply a root that is a dummy node;
for
all faces
f
that have
s
as vertex
do
for
all edges
e
of
fdo
Insert (
e
,
f
,
s
,
e
) as child of root of T;
for
i:=1
to
n
do
for
all leaves N=(
e
,
f
,
p
,proj
s
,
e
) of T at ith level
do
begin
Let
f
¢ be the other face (π
f
) containing the edge
e
;
Let
e1
and
e2
be the edges of
f
¢ other than
e
;
Unfold
p
to
p
¢ in the plane of
f
¢;
for e
¢:=
e1
,
e2 do
begin
X
:= proj (
p
¢,proj
s
,
e
,
e
¢);
if X
πf
then
Insert the node (
e
¢,
f
¢,
p
¢,
X
) into T as a child of N;
end
end
;
return
T;
Algorithm 15.3.2.1.
A convex surface edge sequence algorithm.
The tree built by Algorithm 15.3.2.1 is called the
edge sequence tree
for
S
with
respect to the start point
s
. The reason for the name is that every path from the root
to a node in the tree defines an edge sequence for geodesics from
s
to a point
p
in the
node's shadow of
s
. These geodesics are not necessarily shortest paths but there is a
unique geodesic with that edge sequence from
s
to every point in the node's shadow
of
s
. To find the shortest path from
s
to an arbitrary point
p
in
S
one would first find
all the nodes N in the tree, so that
p
is in the shadow of
s
in N. These nodes would
define unique geodesics to
p
. We would simply select the shortest of those and that
would be the shortest path from
s
to
p
.
We now have a correct algorithm for finding shortest paths. The only problem is
that the edge sequence tree might be exponential in size. Figure 15.9(a) shows how
