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

A function, g ( t ), defined over an arbitrary integration interval t 2 [ a , b ] can be converted to a function,

h ( u ) 1, 1] by the linear transformation shown in Equation 3.14 .

By making this substitution and the corresponding adjustments to the derivative, any range can be
handled by the Gaussian integration as shown in Equation 3.15 for arbitrary limits, a and b .
t ¼ f ðuÞ¼ ðb aÞ
2

¼g ( f ( u )), defined over the interval u 2 [

b þ a
2

u þ (3.14)

Z b Z þ 1

0

gðtÞdt ¼ gðf ðuÞÞf ðuÞdu

a 1

0
@

1
A

0
@

1
A du

(3.15)

Z þ 1

b a
2

ðb aÞ
2

b þ a
2

¼ g u þ

1

The weights and evaluation points for different orders of Gaussian quadrature have been tabulated
and can be found in many mathematical handbooks (see Appendix B.8.1 for additional details).
In using Gaussian quadrature to compute the arc length of a cubic curve, Equations 3.5-3.7 are used
to define the arc length function in the form shown in Equation 3.16 after common terms have been
collected into the new coefficients. Sample code to implement this is given below in the discussion on
adaptive Gaussian integration.

Z

1

p

Au

4

þ B u 3 þ Cu

2

þ Du þ E (3.16)

1

Adaptive Gaussian integration
Some space curves have derivatives that vary rapidly in some areas and slowly in others. For such
curves, Gaussian quadrature will undersample some areas of the curve or oversample some other areas.
In the former case, unacceptable error will accumulate in the result. In the latter case, time is wasted by
unnecessary evaluations of the function. This is similar to what happens when using nonadaptive for-
ward differencing.
To address this problem, an adaptive approach can be used [ 2 ]. Adaptive Gaussian integration is
similar to the previously discussed adaptive forward differencing. Each interval is evaluated using
Gaussian quadrature. The interval is then divided in half, and each half is evaluated using Gaussian quad-
rature. The sum of the two halves is compared with the value calculated for the entire interval. If the
difference between these two values is less than the desired accuracy, then the procedure returns the
sum of the halves; otherwise, as with the forward differencing approach, the two halves are added to
the list of intervals to be subdivided along with the reduced error tolerance, e /2 n , where, as before, e
is the user-supplied error tolerance and n is the level of subdivision.
Initially the length of the entire space curve is calculated using adaptive Gaussian quadrature.
During this process, a table of the subdivision points is created. Each entry in the table is a pair
( u , s ) where s is the arc length at parameter value u . When calculating LENGTH (0, u ), the table is
searched to find the values u i , u iþ 1 such that u i < u < u iþ 1 . The arc length from u i to u is then calculated
using nonadaptive Gaussian quadrature. This can be done because the space curve has been subdivided
in such a way that nonadaptive Gaussian quadrature will give the required accuracy over the interval
from u i to u i þ 1. LENGTH (0, u ) is then equal to s i þ LENGTH ( u i , u ). LENGTH ( u a , u b ) can be found by

calculating LENGTH(0 , u a ) and LENGTH(0 , u b ) and then subtracting. The code for the adaptive