Grad und Ordnung

Spline-Kurven werden in der Regel entweder, wie oben beschrieben, über den Grad der stückweise zusammengesetzten Polynome definiert oder über deren Ordnung. Hierbei werden für den Grad meist die Buchstaben ${\displaystyle d}$ oder ${\displaystyle p}$ verwendet, während es üblich ist, für die Ordnung den Buchstaben ${\displaystyle k}$ zu verwenden. Hierbei gilt der Zusammenhang:

${\displaystyle k=d+1}$

Definition

Die als Basis-Splines (B-Splines) bezeichneten Basisfunktionen ${\displaystyle N_{i,p,\tau }\ (i=0,\ldots ,n-p-2)}$ des Grads ${\displaystyle p}$ mit Knotenvektor ${\displaystyle \tau =(\tau _{0},\ldots ,\tau _{n-1})\quad (n\geq 2\,p)}$ sind von Curry und Schoenberg 1947 bis auf die Normierung in folgender Form eingeführt worden:

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

Dabei steht ${\displaystyle [\tau _{i},\ldots ,\tau _{i+p+1}]_{\overline {u}}({\bar {u}}-u)_{+}^{p}}$ für die ${\displaystyle (p+1)}$-ste dividierte Differenz der abgeschnittenen Potenzfunktion ${\displaystyle (\tau -u)_{+}^{p}}$ bzgl. ${\displaystyle \tau }$. Die dividierte Differenz ${\displaystyle [x_{0},\ldots ,x_{d}]_{x}f(x)}$ ist der zu ${\displaystyle x^{d}}$ gehörige Koeffizient im (eindeutig gegebenen) Polynom ${\displaystyle c_{0}+c_{1}x+c_{2}x^{2}+\ldots +c_{d}x^{d}}$, das die Funktion ${\displaystyle f}$ an den Stellen ${\displaystyle x_{0},\ldots ,x_{d}}$ interpoliert. Stimmen die Werte von ${\displaystyle k}$ der Variablen ${\displaystyle x_{i}}$ überein, so interpoliert das Polynom die Funktion ${\displaystyle f}$ an dieser Stelle bis zur ${\displaystyle (k-1)}$-ten Ableitung (oskulierende Interpolation, engl.: `osculating interpolation').

In obiger Definition von ${\displaystyle N_{i,p,\tau }(u)}$ gilt ${\displaystyle ({\bar {u}}-u)_{+}^{p}=({\bar {u}}-u)^{p}}$ für ${\displaystyle {\bar {u}}=\tau _{i},\ldots ,\tau _{i+p+1}}$ solange ${\displaystyle u}$ kleiner ${\displaystyle \tau _{i}}$ bleibt. In diesem Bereich für ${\displaystyle u}$ ergibt sich also eine dividierte Differenz vom Grad ${\displaystyle p+1}$ für ein Polynom ${\displaystyle p}$-ten Grades, die trivialerweise null ist. Auf der anderen Seite ist für ${\displaystyle u>\tau _{i+p+1}}$ die Funktion ${\displaystyle ({\bar {u}}-u)_{+}^{p}}$ an allen für die dividierte Differenz auszuwertenden Stellen bei ${\displaystyle N_{i,p,\tau }(u)}$ gleich null, womit dort ebenfalls ${\displaystyle N_{i,p,\tau }(u)=0}$ gilt.

Der Träger von ${\displaystyle N_{i,p,\tau }(u)}$ liegt also innerhalb des Intervalls ${\displaystyle [\tau _{i},\tau _{i+p+1}]}$.

Unterscheiden sich die Stellen ${\displaystyle \tau _{i}}$ alle voneinander, so ist die dividierte Differenz in ${\displaystyle N_{i,p,\tau }}$ eine endliche Linearkombination von Funktionen ${\displaystyle u\mapsto ({\bar {u}}-u)_{+}^{p}}$ mit unterschiedlichen Werten für ${\displaystyle {\bar {u}}}$ und als solche ${\displaystyle (p-1)}$-mal stetig differenzierbar.

Eigenschaften

Die folgenden Eigenschaften zeichnen die B-Splines ${\displaystyle N_{i,p,\tau }(u)}$ mit ${\displaystyle i=0,\ldots ,n-p-2}$ im Raum der Splines ${\displaystyle S_{p,\tau }}$ mit Knotenvektor ${\displaystyle \tau =(\tau _{i})_{i=0}^{n-1}}$ und Maximalgrad ${\displaystyle p}$ aus:

• Nicht-Negativität: ${\displaystyle N_{i,p,\tau }(u)\geq 0}$
• Lokaler Träger: ${\displaystyle N_{i,p,\tau }(u)>0}$ falls ${\displaystyle u\in {]\tau _{i},\tau _{i+p+1}[}}$ und ${\displaystyle N_{i,p,\tau }(u)=0}$ falls ${\displaystyle u\not \in [\tau _{i},\tau _{i+p+1}[}$
• Zerlegung der Eins: ${\displaystyle \sum _{i=0}^{n-p-2}N_{i,p,\tau }(u)=1}$ für ${\displaystyle u\in [\tau _{p},\tau _{n-p-1}[}$

Effiziente Berechnung

Die Basis-Splines können effektiv mit der Rekursionsformel von de Boor/Cox/Mansfield berechnet werden:

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

und

${\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)}$ für ${\displaystyle p>0}$.

Die Elemente des Knotenvektors heißen auch Knotenpunkte (engl. knots) und müssen die Bedingungen ${\displaystyle \tau _{i}\leq \tau _{i+1}}$ und ${\displaystyle \tau _{i}<\tau _{i+p}}$ erfüllen.

Zur Berechnung der Ableitung eines B-Splines kann man obige Rekursionsformel mit der folgenden Vorschrift kombinieren:

${\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)}$ für ${\displaystyle p\geq 1}$.

Bemerkung:

Die Bedingungen an die Knotenpunkte ${\displaystyle \tau _{i}}$ erlauben es, dass in der Rekursionsformel unter Umständen Null als Nenner auftritt (nämlich wenn ${\displaystyle \tau _{i+p}=\tau _{i}}$ bzw. ${\displaystyle \tau _{i+p+1}=\tau _{i+1}}$ gilt). Allerdings ist dann die Funktion ${\displaystyle N_{i,p,\tau }}$ bzw. ${\displaystyle N_{i+1,p,\tau }}$ automatisch die Nullfunktion. Auf die entsprechende Fallunterscheidung wird hier verzichtet, man ignoriere die entsprechenden Summanden in diesen Fällen (ersetze sie durch Null). Dies entspricht auch dem Grenzverhalten für z. B. ${\displaystyle \tau _{i+p}\to \tau _{i}.}$

B-Spline-Kurve

Eine Spline-Kurve, deren Darstellung auf B-Splines beruht, nennt man B-Spline-Kurve. Bestimmt wird die Kurve durch sogenannte De-Boor-Punkte, mit denen sich das Aussehen der Kurve leicht steuern lässt: Die Kurve liegt immer in der konvexen Hülle der De-Boor-Punkte, wird also von ihnen eingeschlossen.

Eine B-Spline-Kurve ${\displaystyle C(u),\ u\in [\tau _{p},\tau _{n-p-1}[}$ des Maximalgrads ${\displaystyle p}$ mit Knotenvektor ${\displaystyle \tau }$ (s. o.) und Kontrollpunkten ${\displaystyle P_{i}\ (i=0,\ldots ,n-p-2)}$ (auch De-Boor-Punkte genannt) wird definiert durch

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

Für Kurven in der Ebene sind die Kontrollpunkte zweidimensional, für Kurven im Raum dreidimensional.

Eigenschaften:

• Lokalität: Der Kontrollpunkt ${\displaystyle P_{i}}$ beeinflusst die Kurve nur im Intervall ${\displaystyle [\tau _{i},\tau _{i+p+1}[}$
• Endpunkt-Interpolation: Es ist ${\displaystyle P_{0}=C(\tau _{p})}$, falls die ersten ${\displaystyle p+1}$ Knotenpunkte ${\displaystyle \tau _{0},\ldots ,\tau _{p}}$ gleich sind und ${\displaystyle P_{n-p-2}=C(\tau _{n-1-p})}$, falls die letzten ${\displaystyle p+1}$ Knotenpunkte ${\displaystyle \tau _{n-1-p},\ldots ,\tau _{n-1}}$ gleich sind.

Eine ähnliche Darstellung haben Bézierkurven. Diese basieren nicht auf der oben genannten Basis, sondern auf den Bernsteinpolynomen. Genau wie bei B-Spline-Kurven die De-Boor-Punkte gibt es hier die Bézier-Punkte, die das sogenannte Kontrollpolygon bilden und mit denen man die Kurve leicht graphisch darstellen kann.

Einen einfachen Zusammenhang von Bézierkurven und B-Spline-Kurven in Verbindung mit einer einfachen Berechnung stellt das Blossoming dar, welches von Paul de Faget de Casteljau Anfang der 1980er Jahre entdeckt und von Lyle Ramshaw verbreitet wurde.

Algorithmus von De Boor

Statt der Gleichung in obiger Definition für ${\displaystyle C(u)}$ wird zur effizienten Berechnung von B-Spline-Kurven ${\displaystyle C(u)}$ mit ${\displaystyle u}$ im Intervall ${\displaystyle [\tau _{p},\tau _{n-p-1}[}$ meist der im Folgenden beschriebene Algorithmus von De Boor verwendet.

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}}$.

Sind mehrere Splines, die sich nur durch die Koeffizienten ${\displaystyle P_{i}}$ unterscheiden, an derselben Stelle ${\displaystyle u}$ auszuwerten, so kann die in der Definition der B-Spline-Kurve aufgeführte Berechnungsvorschrift ${\displaystyle C(u)=\sum _{i=0}^{n-p-2}P_{i}N_{i,p,\tau }(u)}$ effizienter als der Algorithmus von De Boor sein.

B-Spline-Fläche

Eine B-Spline-Fläche der Maximalgrade ${\displaystyle p}$ und ${\displaystyle q}$ in der ersten beziehungsweise zweiten Variablen mit Knotenvektoren ${\displaystyle \tau =(\tau _{0},\ldots ,\tau _{n-1})\ (n\geq 2p+1)}$ und ${\displaystyle \mu =(\mu _{0},\ldots ,\mu _{m-1})\ (m\geq 2q+1)}$ und Kontrollpunkten (bzw. De Boor Punkten) ${\displaystyle P_{ij}}$ wird definiert durch

${\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)}$

Die Fläche ist definiert über dem Rechteck ${\displaystyle [\tau _{p},\tau _{n-1-p}]\times [\mu _{q},\mu _{m-1-q}]}$.

Eigenschaften:

• Lokalität: Der Kontrollpunkt ${\displaystyle P_{ij}}$ beeinflusst die Fläche nur im Rechteck ${\displaystyle [\tau _{i},\tau _{i+p}]\times [\mu _{j},\mu _{j+q}]}$
• Endpunktinterpolation: Werden die ersten ${\displaystyle p+1}$ Knotenpunkte in ${\displaystyle \tau }$ auf den gleichen Wert gesetzt, die letzten ${\displaystyle p+1}$ Knotenpunkte in ${\displaystyle \tau }$ auf den gleichen Wert gesetzt, die ersten ${\displaystyle q+1}$ Knotenpunkte in ${\displaystyle \mu }$ auf den gleichen Wert gesetzt und die letzten ${\displaystyle q+1}$ Knotenpunkte in ${\displaystyle \mu }$ auf den gleichen Wert gesetzt, dann gilt die Endpunktinterpolation, d. h. ${\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})}$ und ${\displaystyle P_{n-p-2,m-q-2}=C(\tau _{n-1-p},\mu _{m-1-q})}$