Spline

Example of a spline with 8 nodes

Braid: The geometry of the horizontal branches can be described with splines

A spline of the nth degree (also known as a polynomial train ) is a function that is piecemeal composed of polynomials at most nth degree. Certain conditions are set at the points at which two polynomial pieces collide (one also speaks of nodes), such as that the spline is continuously differentiable ( n-1 ) times .

If the spline is a linear function in each of its sections , then the spline is called linear (it is then a polygon ), analogously there are square , cubic etc. splines.

Among the pioneers of spline research are Isaac Jacob Schoenberg (from the 1940s), Paul de Faget de Casteljau , Pierre Bézier and Carl de Boor .

General

The term spline was first used in an English publication by Isaac Jacob Schoenberg in 1946 for smooth, harmonic, compound mathematical curves of the third degree.

Splines are mainly used for interpolation and approximation . Due to the piecewise definition, splines are more flexible than polynomials and yet relatively simple and smooth. As a result, spline interpolation does not have the disadvantages that arise from the strong oscillation of polynomials of a higher degree and their unlimited nature in polynomial interpolation ( Runge's phenomenon ). Splines can also be used to represent curves . Here they are used in CAD . Mathematically analogously, not only curves but also surfaces can be described in both ways.

Origin of the word: The term comes from shipbuilding : a long, thin lath ( Straklatte , English spline ), which is fixed at individual points by pigs , bends exactly like a cubic spline with natural boundary conditions. The tension energy is minimal.

Spline space

Functions that are in each of the sub-intervals of a strictly increasing sequence of nodes as polynomials with maximum degree can be presented, hot piecewise polynomial functions on (with maximum degree ). ${\displaystyle p\colon {[\tau _{0},\tau _{n-1}[}\rightarrow \mathbb {R} }$ ${\displaystyle [\tau _{i},\tau _{i+1}[}$ ${\displaystyle \tau :=(\tau _{i})_{i=0,.\ldots ,n-1}\in \mathbb {R} ^{n}}$ ${\displaystyle d\in \mathbb {Z} _{\geq 0}}$ ${\displaystyle \tau }$ ${\displaystyle d}$

In addition to this simple structure from polynomial sections, maximum smoothness is also required for splines.

The spline space is the vector space of all -time continuously differentiable piecewise polynomial functions with a maximum degree . ${\displaystyle S_{d,\tau }}$ ${\displaystyle (d-1)}$ ${\displaystyle \tau }$ ${\displaystyle d}$

The truncated power functions are found in the construction of splines

${\displaystyle (u)_{+}^{d}:={\begin{cases}0&{\text{ für}}\quad u<0\\u^{d}&{\text{ für}}\quad u\geq 0\end{cases}}}$

with as useful. is for the step function , for the ramp function and for this function is continuously differentiable times. ${\displaystyle d=0,1,\ldots }$ ${\displaystyle (x)_{+}^{d}}$ ${\displaystyle d=0}$ ${\displaystyle d=1}$ ${\displaystyle d\geq 1}$ ${\displaystyle (d-1)}$

Each piecewise polynomial function on with maximum degree is uniquely determined coefficients , in the form ${\displaystyle \tau }$ ${\displaystyle d}$ ${\displaystyle c_{i,j}\in \mathbb {R} }$ ${\displaystyle (i=0,\ldots ,d;\ j=0,\ldots ,n-2)}$

${\displaystyle p(u)=\sum _{j=0}^{n-2}\sum _{i=0}^{d}c_{i,j}(u-\tau _{j})_{+}^{i}}$

representable. Since splines should be continuously differentiable times, the coefficients for the lower powers that do not meet the differentiability requirement must vanish at the inner nodes . So splines have the representation ${\displaystyle (d-1)}$ ${\displaystyle c_{i,j}}$ ${\displaystyle i=0,\ldots ,d-1}$ ${\displaystyle j=1,\ldots ,n-2}$ ${\displaystyle p\in S_{d,\tau }}$

${\displaystyle p(u)=\sum _{i=0}^{d}c_{i,0}(u-\tau _{0})_{+}^{i}+\sum _{j=1}^{n-2}c_{d,j}(u-\tau _{j})_{+}^{d}.}$

The ( restricted) functions for and for thus together represent a basis for the spline space . The spline space is -dimensional. ${\displaystyle [\tau _{0},\tau _{n-1}[}$ ${\displaystyle (u-\tau _{0})_{+}^{i}}$ ${\displaystyle i=0,\ldots ,d}$ ${\displaystyle (u-\tau _{j})_{+}^{d}}$ ${\displaystyle j=1,\ldots ,n-2}$ ${\displaystyle S_{d,\tau }}$ ${\displaystyle (n+d-1)}$

The multiple differentiability of the splines can be specifically weakened again at given nodes. In the illustration above, this is achieved by taking back selected basis functions of a lower degree at inner nodes. When the algorithm of the de Boor showing splines arises automatically when multiple nodes allows the node sequence, more precisely, the demand for weakening to for and for . ${\displaystyle (d-1)}$ ${\displaystyle \tau _{i}<\tau _{i+1}}$ ${\displaystyle i=0,\ldots ,n-2}$ ${\displaystyle \tau _{i}\leq \tau _{i+1}}$ ${\displaystyle i=0,\ldots ,n-2}$ ${\displaystyle \tau _{i}<\tau _{i+d+1}}$ ${\displaystyle i=0,\ldots ,n-d-2}$

The variants of the splines used in mathematics and technology, such as B-splines or cubic splines, differ essentially in the basis used for the spline space.

Degree and order

As a rule, spline curves are either defined via the degree of the piecewise composite polynomials, as described above, or via their order. The letters or are usually used for the degree , while it is common to use the letter for the order . The following applies here: ${\displaystyle d}$ ${\displaystyle p}$ ${\displaystyle k}$

${\displaystyle k=d+1}$

Cubic splines

See also : Cubic C ² spline  and bicubic filtering

Cubic splines are used, among other things, to calculate the path of roller coasters in order to avoid sudden changes in acceleration for the passengers. Cubic splines are also used for the precise laying of rails on high-speed rail lines . Splines are also important when designing curves and surfaces (so-called "free-form curves and surfaces"), as they often occur in shipbuilding, aircraft and automobile construction.

Splines are suitable for such applications because boundary conditions can be specified for each polynomial section both in the form of points and in the form of values ​​for the first and second derivative (and, depending on them, slope and curvature / curve radius). As a result, a constant curvature can be achieved over the entire course of the curve. In this way, transverse accelerations are always built up gradually when driving around the curve or the values ​​specified at the intersections are maintained.

Burmester templates represent cubic splines. These templates are used to fit curves to draw from values droves.

B-splines

B-spline is the short form of base spline . In the context of numerical processes, where splines are often used, the choice of the basis for the spline space decides on possible rounding errors and thus on the practical applicability. A certain basis has proven to be the most suitable here: it is numerically stable and allows the calculation of values ​​of the spline function using a three-term recursion . These so-called B-spline basis functions have a compact support , they only differ from zero over a small interval . Changes to the coefficients therefore only have a local effect.

Carl de Boor points out in his article B (asic) Spline Basics that the term B-Spline was originally introduced for certain splines with minimal support, but that in the area of Computer Aided Geometric Design the somewhat unfortunate use of the term B- Has naturalized spline for splines that are displayed in the B spline base.

See also : convolution (mathematics)

definition

The basic functions of the degree with node vector , known as basic splines (B-splines), were introduced by Curry and Schoenberg in 1947 except for the normalization in the following form: ${\displaystyle N_{i,p,\tau }\ (i=0,\ldots ,n-p-2)}$ ${\displaystyle p}$ ${\displaystyle \tau =(\tau _{0},\ldots ,\tau _{n-1})\quad (n\geq 2\,p)}$

${\displaystyle N_{i,p,\tau }(u)=(\tau _{i+p+1}-\tau _{i})[\tau _{i},\ldots ,\tau _{i+p+1}]_{\bar {u}}({\bar {u}}-u)_{+}^{p}}$

Here stands for the -th divided difference of the truncated power function with respect to . The divided difference is the associated coefficient in the (uniquely given) polynomial that interpolates the function at the points . If the values ​​of the variables match, the polynomial interpolates the function at this point up to the -th derivative (osculating interpolation). ${\displaystyle [\tau _{i},\ldots ,\tau _{i+p+1}]_{\bar {u}}({\bar {u}}-u)_{+}^{p}}$ ${\displaystyle (p+1)}$ ${\displaystyle (\tau -u)_{+}^{p}}$ ${\displaystyle \tau }$ ${\displaystyle [x_{0},\ldots ,x_{d}]_{x}f(x)}$ ${\displaystyle x^{d}}$ ${\displaystyle c_{0}+c_{1}x+c_{2}x^{2}+\ldots +c_{d}x^{d}}$ ${\displaystyle f}$ ${\displaystyle x_{0},\ldots ,x_{d}}$ ${\displaystyle k}$ ${\displaystyle x_{i}}$ ${\displaystyle f}$ ${\displaystyle (k-1)}$

In the above definition of applies to as long as remains smaller . In this area for there is a divided difference of the degree for a polynomial -th degree, which is trivially zero. On the other hand, for the function , all points to be evaluated for the divided difference are equal to zero, which also applies there. ${\displaystyle N_{i,p,\tau }(u)}$ ${\displaystyle ({\bar {u}}-u)_{+}^{p}=({\bar {u}}-u)^{p}}$ ${\displaystyle {\bar {u}}=\tau _{i},\ldots ,\tau _{i+p+1}}$ ${\displaystyle u}$ ${\displaystyle \tau _{i}}$ ${\displaystyle u}$ ${\displaystyle p+1}$ ${\displaystyle p}$ ${\displaystyle u>\tau _{i+p+1}}$ ${\displaystyle ({\bar {u}}-u)_{+}^{p}}$ ${\displaystyle N_{i,p,\tau }(u)}$ ${\displaystyle N_{i,p,\tau }(u)=0}$

So the carrier of lies within the interval . ${\displaystyle N_{i,p,\tau }(u)}$ ${\displaystyle [\tau _{i},\tau _{i+p+1}]}$

If the places are all different from one another, then the divided difference can be continuously differentiated into a finite linear combination of functions with different values ​​for and as such times. ${\displaystyle \tau _{i}}$ ${\displaystyle N_{i,p,\tau }}$ ${\displaystyle u\mapsto ({\bar {u}}-u)_{+}^{p}}$ ${\displaystyle {\bar {u}}}$ ${\displaystyle (p-1)}$

properties

The following characteristics distinguish the B-splines with in the space of splines with knots vector and maximum degree of: ${\displaystyle N_{i,p,\tau }(u)}$ ${\displaystyle i=0,\ldots ,n-p-2}$ ${\displaystyle S_{p,\tau }}$ ${\displaystyle \tau =(\tau _{i})_{i=0}^{n-1}}$ ${\displaystyle p}$

• Non-negativity: ${\displaystyle N_{i,p,\tau }(u)\geq 0}$
• Local carrier: if and if ${\displaystyle N_{i,p,\tau }(u)>0}$ ${\displaystyle u\in {]\tau _{i},\tau _{i+p+1}[}}$ ${\displaystyle N_{i,p,\tau }(u)=0}$ ${\displaystyle u\not \in [\tau _{i},\tau _{i+p+1}[}$
• Decomposition of the one : for ${\displaystyle \sum _{i=0}^{n-p-2}N_{i,p,\tau }(u)=1}$ ${\displaystyle u\in [\tau _{p},\tau _{n-p-1}[}$

Efficient calculation

The base splines can be effectively calculated using the de Boor / Cox / Mansfield recursion formula:

${\displaystyle N_{i,0,\tau }(u)={\begin{cases}1,&u\in \left[\tau _{i},\tau _{i+1}\right[\\0,&{\text{sonst}}\end{cases}}}$

and

${\displaystyle N_{i,p,\tau }(u)={\frac {u-\tau _{i}}{\tau _{i+p}-\tau _{i}}}\,N_{i,p-1,\tau }(u)\;+\;{\frac {\tau _{i+p+1}-u}{\tau _{i+p+1}-\tau _{i+1}}}\,N_{i+1,p-1,\tau }(u)}$for . ${\displaystyle p>0}$

The elements of the knot vector are also called knots and must meet the conditions and . ${\displaystyle \tau _{i}\leq \tau _{i+1}}$ ${\displaystyle \tau _{i}<\tau _{i+p}}$

To calculate the derivative of a B-spline, the above recursion formula can be combined with the following rule:

${\displaystyle {\frac {d}{du}}N_{i,p,\tau }(u)=N'_{i,p,\tau }(u)={\frac {p}{\tau _{i+p}-\tau _{i}}}N_{i,p-1,\tau }(u)-{\frac {p}{\tau _{i+p+1}-\tau _{i+1}}}N_{i+1,p-1,\tau }(u)}$for . ${\displaystyle p\geq 1}$

Comment:

The conditions on the nodes allow 0 to appear as a denominator in the recursion formula (namely if or applies). However, then the function or automatically the null function . The corresponding case distinction is dispensed with here, one ignores the corresponding summands in these cases (replace them with 0). This also corresponds to the limit behavior for z. B. ${\displaystyle \tau _{i}}$ ${\displaystyle \tau _{i+p}=\tau _{i}}$ ${\displaystyle \tau _{i+p+1}=\tau _{i+1}}$ ${\displaystyle N_{i,p,\tau }}$ ${\displaystyle N_{i+1,p,\tau }}$ ${\displaystyle \tau _{i+p}\to \tau _{i}.}$

B-spline curve

A spline curve whose representation is based on B-splines is called a B-spline curve . The curve is determined by so-called De-Boor points , with which the appearance of the curve can be easily controlled: The curve always lies in the convex envelope of the De-Boor points, i.e. is enclosed by them.

A B-spline curve of the maximum degree with a node vector ( see above ) and control points (also called de-boor points ) is defined by ${\displaystyle C(u),\ u\in [\tau _{p},\tau _{n-p-1}[}$ ${\displaystyle p}$ ${\displaystyle \tau }$ ${\displaystyle P_{i}\ (i=0,\ldots ,n-p-2)}$

${\displaystyle C(u)=\sum _{i=0}^{n-p-2}\;P_{i}\,N_{i,p,\tau }(u)}$.

The control points are 2-dimensional for curves in the plane and 3-dimensional for curves in space.

Properties:

• Locality: The control point only influences the curve in the interval ${\displaystyle P_{i}}$ ${\displaystyle [\tau _{i},\tau _{i+p+1}[}$
• End point interpolation: It is if the first nodes are the same and if the last nodes are the same. ${\displaystyle P_{0}=C(\tau _{p})}$ ${\displaystyle p+1}$ ${\displaystyle \tau _{0},\ldots ,\tau _{p}}$ ${\displaystyle P_{n-p-2}=C(\tau _{n-1-p})}$ ${\displaystyle p+1}$ ${\displaystyle \tau _{n-1-p},\ldots ,\tau _{n-1}}$

Bézier curves have a similar representation . These are not based on the above-mentioned basis, but on the Bernstein polynomials . Just like the De Boor points in B-spline curves, there are the Bézier points, which form the so-called control polygon and with which the curve can be easily represented graphically.

De Boor's algorithm

Instead of the equation in the definition above , the De Boor algorithm described below is usually used for the efficient calculation of B-spline curves with in the interval . ${\displaystyle C(u)}$ ${\displaystyle C(u)}$ ${\displaystyle u}$ ${\displaystyle [\tau _{p},\tau _{n-p-1}[}$

1. Suche  ${\displaystyle i\in \{0,\ldots ,n-p-2\}}$, so dass  ${\displaystyle u\in [\tau _{i},\tau _{i+1}[}$ gilt.
   Gibt es keinen solchen Index  ${\displaystyle i}$, so liegt  ${\displaystyle u}$ außerhalb des Definitionsbereiches der Splinekurve  ${\displaystyle C}$
   und es muss extrapoliert oder eine Fehlermeldung ausgegeben werden.
2. Initialisiere Hilfsgrößen  ${\displaystyle q_{0,j}:=P_{i+j}}$ für  ${\displaystyle j=0,\ldots ,d}$
3. Führe für  ${\displaystyle l=1,\ldots ,d}$ und  ${\displaystyle j=0,\ldots ,d-l}$ folgende Teilschritte 3.1 bis 3.3 iterativ aus:
3.1. Im Ausnahmefall gleicher Knoten  ${\displaystyle \tau _{i+j}=\tau _{i+j+l}}$ setze  ${\displaystyle q_{l,j}:=q_{l-1,j}}$ und fahre mit dem nächsten Iterationsschritt  ${\displaystyle j:=j+1}$ bei 3.1. fort.
3.2. Gilt dagegen  ${\displaystyle \tau _{i+j}<\tau _{i+j+l}}$, so berechne  ${\displaystyle \alpha _{l,j}:={\frac {u-\tau _{i+j}}{\tau _{i+j+l}-\tau _{i+j}}}}$.
3.3. Berechne damit  ${\displaystyle q_{l,j}:=q_{l-1,j}\cdot (1-\alpha _{l,j})+q_{l-1,j+1}\cdot \alpha _{l,j}}$.
4. Als Endergebnis der Iteration erhält man  ${\displaystyle C(u):=q_{d,0}}$.

If several splines, which only differ in their coefficients , are to be evaluated at the same point , the calculation rule given in the definition of the B-spline curve can be more efficient than the De Boor algorithm. ${\displaystyle P_{i}}$ ${\displaystyle u}$ ${\displaystyle C(u)=\sum _{i=0}^{n-p-2}P_{i}N_{i,p,\tau }(u)}$

B-spline surface

A B-spline area of ​​the maximum degrees and in the first and second variables with node vectors and and control points (or De Boor points ) is defined by ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \tau =(\tau _{0},\ldots ,\tau _{n-1})\ (n\geq 2p+1)}$ ${\displaystyle \mu =(\mu _{0},\ldots ,\mu _{m-1})\ (m\geq 2q+1)}$ ${\displaystyle P_{ij}}$

${\displaystyle C(u,v)=\sum _{i=0}^{\ n-p-2\ }\sum _{j=0}^{\ m-q-2\ }\;P_{ij}\,N_{i,p,\tau }(u)\,N_{j,q,\mu }(v)}$

The area is defined above the rectangle . ${\displaystyle [\tau _{p},\tau _{n-1-p}]\times [\mu _{q},\mu _{m-1-q}]}$

Properties:

• Locality: The control point only affects the area in the rectangle ${\displaystyle P_{ij}}$ ${\displaystyle [\tau _{i},\tau _{i+p}]\times [\mu _{j},\mu _{j+q}]}$
• Endpunktinterpolation: Will the first hubs set to the same value, the last nodes in set to the same value, the first hubs set to the same value and the last nodes in set to the same value, does the Endpunktinterpolation, ie , , and ${\displaystyle p+1}$ ${\displaystyle \tau }$ ${\displaystyle p+1}$ ${\displaystyle \tau }$ ${\displaystyle q+1}$ ${\displaystyle \mu }$ ${\displaystyle q+1}$ ${\displaystyle \mu }$ ${\displaystyle P_{0,0}=C(\tau _{p},\mu _{q})}$ ${\displaystyle P_{0,m-q-2}=C(\tau _{p},\mu _{m-1-q})}$ ${\displaystyle P_{n-p-2,0}=C(\tau _{n-1-p},\mu _{q})}$ ${\displaystyle P_{n-p-2,m-q-2}=C(\tau _{n-1-p},\mu _{m-1-q})}$

Further variants and generalizations

In addition to the B-splines, there are other variants of splines, for example the cubic Hermitian spline . A generalization of splines are NURBS , which are described by piecewise rational functions instead of polynomials. With NURBS curves, circles can be represented exactly.

literature

• Andrew Blake and Michael Isard: "Active Contours". Springer Verlag, 1998, ISBN 978-1-4471-1555-7
• Carl de Boor: A Practical Guide to Splines . Springer Verlag, New York 1978, ISBN 0-387-90356-9 and ISBN 3-540-90356-9 (Rev. Auf .. 2001 ISBN 0-387-95366-3 )
• Gerald Farin: Curves and Surfaces for CAGD. A practical guide. 5th Ed. Academic Press, San Diego 2002 ISBN 1-55860-737-4
• Günther Nürnberger: Approximation by Spline Functions. Springer Verlag, 1989, ISBN 3-540-51618-2 and ISBN 0-387-51618-2
• Hartmut Prautzsch, Wolfgang Böhm, Marco Paluszny: Bezier and B-Spline Techniques . Springer Verlag, Berlin 2001 ISBN 3-540-43761-4
• David Salomon: Curves and Surfaces for Computer Graphics . 2006 Springer Science + Business Media, Inc .; ISBN 0-387-24196-5
• Isaac Jacob Schoenberg: Contributions to the problem of approximation of equidistant data by analytic functions . Quart. Appl. Math., Vol. 4, pp. 45-99 and 112-141, 1946.

Web links

• LP - spaces of spline functions
• Java applet for calculating B-spline curves
• Website with explanations and a tool for calculating cubic splines
• TinySpline: Open Source C program library for NURBS, B-Splines and Bezier Splines with bindings for different languages

Individual evidence

1. ^ De Boor C. (1993): B (asic) –spline basics. In: Piegl L. (ed.): Fundamental Developments of Computer-Aided Geometric Modeling. Academic Press, San Diego, 27-49.
2. ^ Carl de Boor: A Practical Guide to Splines. Springer Verlag Berlin, 2001
3. ↑ http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-basis.html
4. ↑ http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/bspline-derv.html