Game Development Reference
In-Depth Information
smooth shape that goes through the points.” Unfortunately, this doesn't
unambiguously define a curve—we need to provide some other criteria to
nail down the shape, and one way to do this is to associate time values with
each control point. In typical applications of polynomial interpolation, we
want to be able to specify the values of the dependent variable, because
we are trying to fit a function to some known data points. There are some
reasonable ways we can synthesize this information if we don't have it—for
example, by making the difference between adjacent t values proportional
to the Euclidian distance between the corresponding control points. How-
ever, the general fact that polynomial interpolation needs us to provide the
t values when we often don't have a good way to decide what they should
be is a harbinger of later discoveries.
Now that we've set the ground rules, let's try to create this curve. We
first take a geometric approach in Section 13.2.1. Then, in Section 13.2.2 , we
look at the problem from a slightly more abstract mathematical perspective.
13.2.1 Aitken's Algorithm
Our first approach to polynomial interpolation is a recursive technique due
to Alexander Aitken (1895-1967). Like many recursive algorithms, it works
on the principle of divide and conquer. To solve a di cult problem, we
first divide it into two (or more) easier problems, solve the easier problems
independently, and then combine the results to get the solution to the
harder problem. In this case, the “hard” problem is to create a curve
that interpolates n control points. We split this curve into two “easier”
curves: (1) one that interpolates only the first n − 1 points, disregarding
the last point; and (2) another that interpolates the last n−1 points without
worrying about the first point. Then, we blend these two curves together.
Let's take the important cubic (third-degree) case as an example. A
cubic curve has four control points y 1 ...y 4 that we wish to interpolate at
the corresponding times t 1 ...t 4 . Applying the “divide-and-conquer” ap-
proach, we split this up into two smaller problems: one curve to interpolate
y 1 ...y 3 , and another curve to interpolate y 2 ...y 4 . Since each of these
curves has three control points, they are quadratic (second-degree) curves.
Of course, quadratic curve-fitting is still a “hard” problem for us, and so
each curve must be further subdivided.
Consider the first quadratic curve, between y 1 , y 2 , and y 3 . We further
divide this curve into two parts, the first part between y 1 and y 2 and the
other part between y 2 and y 3 . These two curves have only two control
points each; they are straight line segments. Finally, a problem that is
truly “easy”!
Since we have lots of curves at this point, we should invent some notation
for them. We let y i (t) denote the linear curve between y i and y i+1 , the
 
Search WWH ::




Custom Search