Graphics Reference
In-Depth Information
∂
∂
j
∂
∂
j
(
()
)
=
(
)
¥
(
)
=-
(
)
n
g
t
t
cos
q
,
t
sin
q
t
cos
q
,
t
sin
q
2
t
cos
q
,
-
2
t
sin
q
,
1
u
v
and
(
)
-
()
=
(
()
)
¥
()
=+
2
(
)
bn
t
g
t
g
t
14
t
sin
q
, cos
q
,
0
.
Clearly,
b
(t) • g≤(t) = 0, so that g(t) is a kinematic geodesic (but not a geodesic since
g≤(t) is not a normal to the surface).
15.3.2
Generating Discrete Geodesics
The last section dealt with smooth geodesics and had to do with smooth curves lying
in smooth surfaces. What if our surface is not smooth but polygonal? See [KSHS03]
for a discussion of two algorithms that generate discrete geodesics given a start
point and a start direction. It is obvious how to proceed here except in the case where
the geodesic passes through a vertex (we preserve angles when crossing edges just
like in the plane). The decision made at a vertex is especially critical if the surface
came from a tessellation of a smooth surface and we are trying to approximate a
smooth geodesic. One needs to take into account the discrete curvature at the point
that could be defined in terms of the sum of angles around the point or the normals
to the faces that meet at the point.
In this section we discuss the other and much harder variant of the geodesic
problem where we are given two endpoints and we want to find the locally shortest
polygonal curves connecting the two points. Before establishing that this is a mean-
ingful question and getting to the main results, we need to introduce some terminol-
ogy. In particular, we pause to make the definition of a polygonal curve (to be called
a piecewise linear curve) more precise. It is hoped that the reader will not despair
because of the rather large number of detailed definitions of what may seem like
obvious terms, but that is the cross that one has to bear when one tries to be un-
ambiguous. The requirement that piecewise linear curves are defined by a sequence
of at least
two
points is motivated by the fact that other definitions are then less
complicated.
Definition.
A
piecewise linear curve
or
pwl curve
p in
R
n
is a sequence (
p
0
,
p
1
,...,
p
k
),
k > 0, of points of
R
n
. The
length
of p, Length(p), is defined using the standard
Euclidean metric by
()
=
Length p
pp
+
pp
+
...
+
p
p
.
01
12
kk
-
1
The curve p is said to be
closed
if
p
0
=
p
k
. The
path
or
underlying space
of p, |p|, is
defined by
=
[
]
»
[
]
»»
[
]
p
pp
,
pp
,
...
p
,
p
.
01
12
k
-
1
k
If
X
Õ
R
n
and |p|Õ
X
, then we say that p is a pwl curve
in
X
. The pwl curve p is said
to be
simple
if
