De Boor's algorithm: Difference between revisions

Revision as of 09:22, 20 January 2008

Revision as of 14:29, 21 April 2008

Line 1:

In the [[mathematics|mathematical]] subfield of [[numerical analysis]] the '''de Boor's algorithm''' is a fast and [[numerically stable]] [[algorithm]] for evaluating [[spline curve]]s in [[B-spline]] form. It is a generalization of the [[de Casteljau's algorithm]] for [[BézierBezier curve]]s. The algorithm was devised by [[Carl R. de Boor]].

== Introduction ==

The general setting is as follows. We would like to construct a curve whose shape is described by a sequence of ''p'' points <math>\vecmathbf{d}_0, \vecmathbf{d}_1, \dots, \vecmathbf{d}_{p-1}</math>, which plays the role of a ''control polygon''. The curve can be described as a function <math> \vecmathbf{s}(x)</math> of one parameter ''x''. To pass through the sequence of points, the curve must satisfy <math>\vecmathbf{s}(u_0)=\vecmathbf{d}_0, \dots,

\vecmathbf{s}(u_{p-1})=\vecmathbf{d}_{p-1}</math>. But this is not quite the case: in general we are satisfied that the curve "approximate" the control polygon. We assume that ''u₀, ..., u_p-1'' are given to us along with <math>\vecmathbf{d}_0, \vecmathbf{d}_1, \dots, \vecmathbf{d}_{p-1}</math>.

One approach to solving this problem is by [[spline (mathematics)|spline]]s. A spline is a curve that is piecewise ''n^th'' degree polynomial. This means that, on any interval ''<nowiki>[</nowiki>u_i, u_i+1)'', the curve must be equal to a polynomial of degree at most ''n''. It may be equal to a different polynomials on different intervals. The polynomials must be ''synchronized'': when the polynomials from intervals ''<nowiki>[</nowiki>u_i-1, u_i)'' and ''<nowiki>[</nowiki>u_i, u_i+1)'' meet at the point ''u_i'', they must have the same value at this point and their derivatives must be equal (to ensure that the curve is smooth).

de Boor algorithm is an algorithm which, given ''u₀, ..., u_p-1'' and <math>\vecmathbf{d}_0, \vecmathbf{d}_1, \dots, \vecmathbf{d}_{p-1}</math>, finds the value of spline curve <math>\vecmathbf{s}(x)</math> at a point ''x''. It uses [[Big O notation|O]](n²) operations. Notice that the running time of the algorithm depends only on degree ''n'' and not on the number of points ''p''.

== Outline of the algorithm==

Line 14:

We can express the curve as

:<math> \vecmathbf{s}(x) = \sum_{i=0}^{p-1} \vecmathbf{d}_i N_i^n(x) , </math>

where

<math>N_i^n(x)=\frac{x-u_i}{u_{i+n}-u_i}N_i^{n-1}(x) - \frac{x-u_{i+n+1}}{u_{i+n+1}-u_{i+1}}N_{i+1}^{n-1}(x) ,</math>

Line 22:

Due to the spline locality property,

:<math> \vecmathbf{s}(x) = \sum_{i=\ell-n}^{\ell} \vecmathbf{d}_i N_i^n(x) </math>

So the value <math>\vecmathbf{s}(x)</math> is determined by the control points <math> \vecmathbf{d}_{\ell-n},\vecmathbf{d}_{\ell-n+1},\dots,\vecmathbf{d}_{\ell} </math>; the other control points <math>\vecmathbf{d}_i</math> have no influence. de Boor's algorithm, described in the next section, is a procedure which efficiently evaluates the expression for <math> \vecmathbf{s}(x) </math>.

== The algorithm ==

Suppose <math> x \in [u_{\ell},u_{\ell+1}] </math> and <math> \vecmathbf{d}_i^{[0]} = \vecmathbf{d}_i </math> for ''i = l-n, ..., l''.

Now calculate

:<math> \vecmathbf{d}_i^{[k]} = (1-\alpha_{k,i}) \vecmathbf{d}_{i-1}^{[k-1]} + \alpha_{k,i} \vecmathbf{d}_i^{[k-1]}; \qquad k=1,\dots,n; \quad i=\ell-n+k,\dots,\ell </math>

with

:<math> \alpha_{k,i} = \frac{x-u_i}{u_{i+n+1-k}-u_i}. </math>

Then <math> \vecmathbf{s}(x) = \vecmathbf{d}_{\ell}^{[n]} </math>.

== See also ==

*[[De Casteljau's algorithm]]

*[[BézierBezier curve]]

*[[NURBS]]