On-Line Geometric Modeling Notes
THE DEBOOR-COX CALCULATION

Overview

In 1972, Carl DeBoor and M.G. Cox independently discovered the relationship between the analytic and geometric definitions of B-splines. Starting with the definition of the normalized B-spline blending functions, these two researchers were able to develop the geometric definition of the B-spline. It is this calculation that is discussed in this paper.

Definition of the B-Spline Curve

A B-spline curve , is defined by

 (1)

where
• the are the control points,
• is the order of the polynomial segments of the B-spline curve. Order means that the curve is made up of piecewise polynomial segments of degree ,
• the are the normalized B-spline blending functions''. They are described by the order and by a non-decreasing sequence of real numbers

normally called the knot sequence''. The functions are described as follows

 (2)

and if ,

 (3)

• the parameter ranges throughout the interval .

We note that if, in equation (3), either of the terms on the right hand side of the equation are zero, or the subscripts are out of the range of the summation limits, then the associated fraction is not evaluated and the term becomes zero. This is to avoid a zero-over-zero evaluation problem.

The order is independent of the number of control points (). In the B-Spline curve, unlike the Bézier Curve, we have the flexibility of using many control points, and restricting the degree of the polymonial segments.

The DeBoor-Cox Calculation

In the DeBoor-Cox calculation, we substitute the definition of given in equation (3), into the right-hand side of

and simplify. This will give us the definition of in terms of , which is of lower degree. The general idea is to continue this process until the sum is written with functions, which we can evaluate easily.

So here we go. If [ ), then by substituting equation (3) into the equation (1), we have

 Distributing the sums, we obtain

Now since the support of a B-spline blending function is the interval , we have that is non-zero only if [ ), which is outside the interval (where is defined). Thus, . Also is non-zero only if [ ), which is outside the interval . Thus, and we have

 If we change the summation limits, we get

If we denote

then the above result may be written

Now we have written the summation terms of equation (1) in terms of blending functions of lower degree. Of course, we have transferred some of the complexity to the s, but we retain a similar form with control points s weighted by blending functions, and we can repeat this calculation again.

Once again then, repeating the calculation and manipulating the sums, we obtain

where

(Note the appearance of the s on the right-hand side of the equation.)

If we continue with this process again, we will manipulate the sum so that the blending functions have order . Then again with give us , and eventually we will obtain blending functions of order 1. We are lead to the following result: If we define

 (4)

where

Then, if is in the interval , we have

This can be shown by continuing the DeBoor-Cox calculation times. When complete, we arrive at the formula

where is given in equation (4). (Note the algebraic simplification that the 's provide.) If , then then the only nonzero term of the sum is the th term, which is one, and the sum must equal .

This enables us to define the geometrical definition of the B-spline curve.

Geometric Definition of the B-Spline Curve

Given a set of Control Points

and a set of knots

The B-Spline curve of order is defined to be

if

where

and

It is useful to view the geometric construction as the following pyramid

Any in this pyramid is calculated as a convex combination of the two functions immediately to it's left.

Summary

The DeBoor-Cox calculation is a fundamental result in the geometric modeling field. It was used to exhibit the relation between the analytic definition of the B-Spline curve and the geometric definition of the curve. The geometric definition of the curve, because of its computational stability has become the primary technique by which points on these curves are calculated.

Ken Joy
2000-11-28