Graphics Reference
In-Depth Information
This solves the first problem posed above; that is, given
u
a
and
u
b
find
LENGTH
(
u
a
,
u
b
). To solve
the second problem of finding
u
, which is a given distance,
s
, away from a given
u
a
, numerical
root-finding techniques must be used as described next.
Find a point that is a given distance along a curve
The solution of the equation
s LENGTH
(
u
a
,
u
)
0 gives the value of
u
such that the point
P
(
u
)isat
arc length
s
from the point
P
(
u
a
) along the curve. Since the arc length is a strictly monotonically
increasing function of
u
, the solution is unique provided that the length of
dP
¼
(
u
)/
du
is not identically
0 over some interval. Newton-Raphson iteration can be used to find the root of the equation because it
converges rapidly and requires very little calculation at each iteration. Newton-Raphson iteration
0
p
n
¼ p
n
1
f ðp
n
1
Þ=f
ðp
n
1
Þ
(3.17)
In this case,
f
is equal to
s LENGTH
(
u
1
,
U
(
p
n
1
)) where
U
(
p
) is a function that computes the
parametric value of a point on a parameterized curve. The function
U
() can be evaluated at
p
n
1
using
precomputed tables of parametric value and points on the curve similar to the techniques discussed
above for computing arc length;
f
0
is
dP/du
evaluated at
p
n
1.
Two problems may be encountered with Newton-Raphson iteration: some of the
p
n
may not lie on
the space curve at all (or at least within some tolerance) and
dP/du
may be 0, or very nearly 0, at some
points on the space curve. The first problem will cause all succeeding elements
p
n þ
1
,
p
n þ
2
,
to be
undefined, while the latter problem will cause division by 0 or by a very small number. A zero para-
metric derivative is most likely to arise when two or more control points are placed in the same position.
This can easily be detected by examining the derivative of
f
in
Equation 3.17
. If it is small or 0, then
binary subdivision is used instead of Newton-Raphson iteration. Binary subdivision can be used in a
similar way to handle the case of undefined
p
n
. When finding
u
such that
LENGTH
(0,
u
)
...
¼ s
, the sub-
division table is searched to find the values
s
i
,
s
i þ
1
such that
s
i
< s <s
i þ
1
. The solution
u
lies between
u
i
and
u
iþ
1
. Newton-Raphson iteration is then applied to this subinterval.
An initial approximation to the solution is made by linearly interpolating
s
between the endpoints of
the interval and using this as the first iterate. Although Newton-Raphson iteration can diverge under
certain conditions, it does not happen often in practice. Since each step of Newton-Raphson iteration
requires evaluation of the arc length integral, eliminating the need to do adaptive Gaussian quadrature,
the result is a significant increase in speed. At this point it is worth noting that the integration and root-
finding procedures are completely independent of the type of space curve used. The only procedure that
needs to be modified to accommodate new curve types is the derivative calculation subroutine, which is
usually a short program.
3.2.2
Speed control
Once a space curve has been parameterized by arc length, it is possible to control the speed at which the
curve is traversed. Stepping along the curve at equally spaced intervals of arc length will result in a
constant speed traversal. More interesting traversals can be generated by speed control functions that
relate an equally spaced parametric value (e.g.,
time
) to arc length in such a way that a controlled tra-
versal of the curve is generated. The most common example of such speed control is
ease-in/ease-out
Search WWH ::
Custom Search