10.2 The de Boor Algorithm

B zier curves are evaluated using the de Casteljau algorithm; B-spline curves are evaluated using the de Boor algorithm, named after Carl de Boor, who did pioneering work on B-splines. The algorithm uses repeated linear interpolation to compute a point x( u) on the curve and it proceeds as follows.

Let the evaluation parameter u be within the range of domain knots. Determine the index I such that

In other words, let

An exception must be made for u = u _K-n: set I = ? n ? 1, the last domain interval.

The de Boor algorithm computes

The point on the curve is

Just as for the de Casteljau algorithm, a convenient schematic tool for describing the algorithm is to arrange the involved points in a triangular diagram:

The column to the far left consists of the control points of the curve, or d ⁰ _i. Notice that one evaluation involves n+1 de Boor points. This is why B-splines are known for local control. The points in successive columns, stages k = 1, , n will be referred to as intermediate de Boor points. We know they are points since (10.2) is a barycentric combination.

A geometric interpretation of the de Boor algorithm is as follows: (10.2) is simply linear interpolation and we know this may be viewed as an affine map of the span [ u _i+n-k,, u _i