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

These techniques reduce the error somewhat blindly. There is no measure for the error in the cal-
culation of the parametric value; these techniques only reduce the error globally instead of investing
more computation in the areas of the curve in which the error is highest.

Adaptive approach
To better control error, an adaptive forward differencing approach can be used that invests more com-
putation in areas of the curve that are estimated to have large errors. The approach does this by con-
sidering a section of the curve and testing to see if the estimate of the segment's length is within some
error tolerance of the sum of the estimates for each of the segment's halves. If the difference is greater
than can be tolerated, then the segment is split in half and each half is put on the list of segments to be
tested. In addition, at each level of subdivision the tolerance is reduced by half to reflect the change in
scale. If the difference is within the tolerance, then its estimated length is taken to be a good enough
estimate and is used for that segment. Initially, the entire curve is the segment to be tested.
As before, a table is to be constructed that relates arc length to parametric value. Each element of the
table records a parametric value and the associated arc length from the start of the curve. It is also useful
to record the coordinates of the associated point on the curve. A linked list is an appropriate structure to
hold this list because the number of entries that will be generated is not known beforehand; after all
points are generated, the linked list can then be copied to a linear list to facilitate a binary search. In
addition to the list of entries, a sorted list of segments to be tested is maintained. A segment on the list is
defined and sorted according to its range of parametric values.
The adaptive approach begins by initializing the table with an entry for the first point of the curve,

< . The

procedure operates on segments from the list to be tested until the list is empty. The first segment on
the list is always the one tested next. The segment's midpoint is computed by evaluating the curve at the
middle of the range of its parametric value. The curve is also evaluated at the endpoint of the segment;
the position of the start of the segment is already in the table and can be retrieved from there. The length
of the segment and the lengths of each of its halves are estimated by the linear distance between the
points on the curve. The sum of the estimated lengths of the two halves of the segment is compared to
the estimated length of the segment. Equation 3.12 shows the test for the initial entire-curve segment.
jjPð

0.0, P (0) > , and initializing the list of segments to be tested with the entire curve, < 0.0,1.0 >

Þ < e 0 : 0 ÞPð 1 : 0 Þjj jjP 0 ð : 0 ÞPð 0 : 5 Þjj þ jjPð 0 : 5 ÞPð 1 : 0 Þjj (3.12)

If the difference between these two values is above some user-specified threshold, then both halves, in
order, are added to the list of segments to be tested along with their error tolerance ( e /2 n where n is the
level of subdivision). If the values are within tolerance, then the parametric value of the midpoint is
recorded in the table along with the arc length of the first point of the segment plus the distance from the
first point to the midpoint. Also added to the table is the last parametric value of the segment along with
the arc length to the midpoint plus the distance from the midpoint to the last point. When the list of
segments to be tested becomes empty, a list of < parametric value, arc length > has been generated

for the entire curve.
One problem with this approach is that at a premature stage in the procedure two half segments
might indicate that the subdivision can be terminated ( Figure 3.7 ) . It is usually wise to force the sub-
division down to a certain level and then embark on the adaptive subdivision.
Because the table has been adaptively built, it is not possible to directly compute the index of a
given parametric entry as it was with the nonadaptive approach. Depending on the data structure used