Drawing De Boor's algorithm

Question

Assume we have 4 control points $[c_0, c_1, c_2, c_3]$ and uniform knot sequence $[0,1,2,3]$

If we were to draw an quadratic bezier we would be forced to use only 3 of the control points and then we would execute De Castlejeau's algorithm which can be sumarized as:

• Take $0 \leq t \leq 1$ now find the point on the line $[c_0, c_1]$ that is $t$ precent in between that segment and mark it $c'_0$.
• Do the same for the segment $[c_1, c_2]$ and mark the new point $c'_1$
• Find the point that is $t$ percent along the segment $[c'_0, c'_1]$ and mark it $c''_0$

And we are done.

For de boor's algorithm the percent changes, since on the first level we look at consecutive knots in the interval, then at knots separated by one value, then knots separated by 2 values...

I am not sure why, but I am having a really hard time walking myself through the algorithm.

So assuming infinitely many control points and infinitely many uniform knots (separated by a distance of 1) (to avoid boundary conditions).

Can someone please do a step by step explanation of drawing De Boors algorithm for a quadratic B-spline and an arbitrary parameter t assumed to be in the interval $[i, i+1]$?

Answer 1

First of all, any quadratic B-spline basis function is determined by 4 knots. Hence to have 4 control points you need 7 knots. Say they are $(1,2,3,4,5,6,7)$. Each basis function can be represented by the subsequence of knots which are used for computing it. They are $(1,2,3,4)$, $(2,3,4,5)$, $(3,4,5,6)$, $(4,5,6,7)$ and correspond to the control points $c_1$, $c_2$, $c_3$, $c_4$.

The range of the independent variable is only $x\in[3,5]$, because only within this interval do the basis functions sum to $1$. E.g. at $x=2.9$ the sum is less than $1$, because if the knot vector is extended by one more knot at the beginning, then a new basis function arises (represented by $(k_{new},1,2,3)$) for which $x=2.9$ is interior (implying that the basis function is nonzero at $x=2.9$).

Say you want to evaluate the curve at $x=3.2$. To find $c_0'$, $c_1'$, and $c_2'$ do the following:

1. For all but the first basis function subtract $x$ from the 2nd last knot of its representation.
   The result is $w_1=(0.8,1.8,2.8)$

2. For all but the last basis function subtract the 2nd knot of its representation from $x$.
   The result is $w_2=(1.2,0.2,-0.8)$

3. $c_0'$ is the weighted average of $c_0$ and $c_1$ with weights $0.8$ and $1.2$
   $c_1'$ is the weighted average of $c_1$ and $c_2$ with weights $1.8$ and $0.2$
   $c_2'$ is is irrelevant because a negative weight appears.
4. Consider the representations $(1,2,3,4)$, $(2,3,4,5)$, $(3,4,5,6)$, $(4,5,6,7)$.
   Remove the first one and the last knot of each (or the other way around).
   The result is $(2,3,4)$, $(3,4,5)$, $(4,5,6)$ which correspond to $c_0'$, $c_1'$, $c_2'$.

Repeat the steps to obtain $c_0''$, $c_1''$. After "degree" repetitions all but one control point will have been ruled out. The remaining ($c_0''$ or $c_1''$ in the quadratic case) is the point on the curve.

In step 3, if you get a pair of weights equal to $(0,0)$, then the curve is discontinuous. I suggest taking the arithmetic mean of the control points in that instance.

Note that the first and the last knot are never used. They only affect those basis functions outside the range of $x$ (where the basis isn't a partition of unity).

I found this image on google which I think explains the algorithm very clearly:

Answer 2

Look up "blossoming" or "polar forms". Blossoming provides (among other things) a good way to label points. The labeling properly reflects the fact that new points are linear (affine) combinations of old ones, and the geometry of the de Casteljau and deBoor algorithms becomes very clear. One of the first descriptions of this technique was Lyle Ramshaw's report entitled "Blossoming: A Connect-the-Dots Approach to Splines", written in 1987. It contains many pictures that will probably help you.