De Boor's algorithm: Difference between revisions

Revision as of 10:34, 4 August 2017

Revision as of 10:35, 4 August 2017

Line 11:

== Outline of the algorithm==

Suppose we want to evaluate the spline curve for a parameter value <math> x \in [u_{0\ell},u_{p-\ell+1}] </math>.

We can express the curve as

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

where<ref>http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-basis.html</ref>

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

and

:<math>N_i^0(x)=\left\{\begin{matrix} 1, & \mbox{if }x \in [\bar u_{i},\bar u_{i+1}) \\ 0, & \mbox{otherwise } \end{matrix}\right.</math>

:<math>N_i^0(x)=\left\{\begin{matrix} 1, & \mbox{if }x \in [\bar u_{i},\bar u_{i+1}) \\ 0, & \mbox{otherwise } \end{matrix}\right.</math>

with the extended knot sequence

:<math>\bar u_i := \left\{\begin{matrix} u_0& \mbox{for }i=0,\ldots,n\\

u_{i-n}&\mbox{for }i=n+1,\ldots,p+n-1\\

u_{p-1}&\mbox{for }i=p+n,\ldots,p+2n.

\end{matrix}\right.</math>

Due to the spline locality property,

While evaluating the algorithm quotients with vanishing numerator and denominator have to be set to zero.

Let <math>\ell\in\{n,\ldots,p+n-2\}</math> be the index such that <math>x\in[\bar u_\ell,\bar u_{\ell+1})</math>. Due to the spline locality property,

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

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