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

B

B

A

C

C

A

Lengths A B C above error tolerance Lengths A B C within error tolerance

B

A

C

Lengths A B C erroneously report that the error is within tolerance

FIGURE 3.7
Tests for adaptive subdivision.

to hold the final table, a sequential search or, possibly, a binary search must be used. Once the appro-
priate entries are found, then, as before, a corresponding table entry can be used as an estimate for the
value or entries can be interpolated to produce better estimates.

Estimating the arc length integral numerically
For cases in which efficiency of both storage and time are of concern, calculating the arc length func-
tion numerically may be desirable. Calculating the length function involves evaluating the arc length
integral (refer to Eq. 3.3 ). Many numerical integration techniques approximate the integral of a func-
tion with the weighted sum of values of the function at various points in the interval of integration.
Techniques such as Simpson's and trapezoidal integration use evenly spaced sample intervals. Gauss-
ian quadrature [ 1 ] uses unevenly spaced intervals in an attempt to get the greatest accuracy using the
smallest number of function evaluations. Because evaluation of the derivatives of the space curve
accounts for most of the processing time in this algorithm, minimizing the number of evaluations is
important for efficiency. Also, because the higher derivatives are not continuous for some piecewise
curves, this should be done on a per segment basis.
Gaussian quadrature, as commonly used, is defined over an integration interval from

1to1.

The function to be integrated is evaluated at fixed points in the interval 1to þ 1, and each function

evaluation is multiplied by a precalculated weight (see Eq. 3.13 ) .

Z

1

X

f ðuÞ¼ w i f ðu i Þ (3.13)

i

1