Interpolating Values - Computer Animation: Algorithms and Techniques - page 69

The analytic approach to computing arc length
The length of the curve from a point

P ( u a ) to any other point P ( u b ) can be found by evaluating the arc

length integral [ 4 ] by

Z u b

s ¼ jdP=dujdu (3.3)

u a

where the derivative of the space curve with respect to the parameterizing variable is defined to be
that shown in Equations 3.4 and 3.5 .

d P =du ¼ððdxðuÞ=ðduÞÞ; ðdyðuÞ=ðduÞÞ; ðdzðuÞ=ðduÞÞÞ (3.4)

q

ðdxðuÞ=duÞ

2 2 2

jd P =duj¼ þðdyðuÞ=duÞ þðdzðuÞ=duÞ (3.5)

For a cubic curve in which P ( u ) ¼ au 3 þ bu 2 þ cu þ d , the derivative of the x -coordinate equation

with respect to u is dx ( u )/ du ¼ 2 b x u þ c x . After squaring this and collecting the terms similarly

generated by the y - and z -coordinate equations, the expression inside the radical takes the form of
Equation 3.6 .

3 a x u 2 þ

4 3 2

Au þ Bu þ Cu þ Du þ E (3.6)

For the two-dimensional case, the coefficients are given in Equation 3.7 ; the extension to three-
dimensional is straightforward.

2 2

A ¼ 9 ða

x þ a y Þ

B ¼ 12 ða x b x þ a y b y Þ

2 2

C ¼ 6 ða x c x þ a y c y Þþ 4 ðb

x þ b y Þ

(3.7)

D ¼ 4 ðb x c x þ b y c y Þ

2 2

y

E ¼ c

x þ c

Estimating arc length by forward differencing
As mentioned previously, analytic techniques are not tractable for many curves of interest to animation.
The easiest and conceptually simplest strategy for establishing the correspondence between parameter
value and arc length is to sample the curve at a multitude of parametric values. Each parametric value
produces a point along the curve. These sample points can then be used to approximate the arc length by
computing the linear distance between adjacent points. As this is done, a table is built up of arc lengths
indexed by parametric values. For example, given a curve

P ( u ), approximate the positions along the

curve for u ¼ , 1.0. The table, recording summed distances and indexed by

entry number, is represented here as G [ i ]. It would be computed as follows:

0.00, 0.05, 0.10, 0.15,

...

G [0] ¼ 0.0

G [1] ¼ the distance between P (0.00) and P (0.05)

G [2] ¼ G [1] plus the distance between P (0.05) and P (0.10)

G [3] ¼ G [2] plus the distance between P (0.10) and P (0.15)

...
G [20]

¼ G [19] plus the distance between P (0.95) and P (1.00)