Curves in 3D - 3D Math Primer for Graphics and Game Development - page 658

Aitken's Algorithm

y i (t) = y i ,

y j−1
i

y j−1 (t i+j − t) (t) + (t − t i )

i+1 (t)

y i (t) =

.

t i+j − t i

Aitken's algorithm works because, at each level both curves being blended
already touch the middle control points. The two outermost control points
are touched by only one curve or the other, but for those values of t, the
blend weights reach their extreme values and all the weight is given to the
curve that touches the control point.
Now that we have the basic idea, let's apply it to our sideways S. Fig-
ure 13.4 shows Aitken's algorithm at work with our four data points. On
the left, the three linear segments are blended to form two quadratic seg-
ments. On the right, the two quadratic curves are blending, yielding the
final result that we've been seeking: a cubic spline that interpolates all four
control points.
So we've successfully interpolated the four control points, and accom-
plished the goal set out at the start of this section, right? Well, not exactly.

Figure 13.4
Two levels of Aitken's algorithm