Oft steht man vor der Aufgabe, eine Reihe von Punkten durch eine möglichst elegante Kurve zu verbinden. Das kann z.B. bei Meßwert - Tabellen sein oder bei der Konstruktion von aerodynamischen Karosserien oder beim Rastern von Vektorschriften.
Die einfachste Möglichkeit ist, zwischen diesen Punkten ein Polynom zu interpolieren. Man erhält eine stetige Kurve, die durch alle Punkte führt. Die Nachteile liegen auf der Hand: Um über n Punkten zu interpolieren, braucht man i.A. ein Polynom vom Grad n-1. Bei vielen Punkten steigt also der Grad der Polynome sehr schnell. Außerdem fängt die Kurve an zu schwingen. D.h. die Kurve verläuft zwar durch alle Punkte, hat aber dazwischen Maxima und Minima, die weit ab von einer eleganten Verbindungskurve liegen.
Die Lösung sind Splines. Zwischen je zwei aufeinander folgenden Punkten werden Polynome niederen (i.A. dritten) Grades interpoliert. Damit sich diese einzelnen Polynome zu einer schönen Kurve zusammenfügen, braucht man noch weitere Bedingungen: An den Endpunkten darf jeweils kein Knick entstehen. D.h. an einem Punkt, wo jeweils zwei Kurven aufeinander stoßen, müssen die ersten Ableitungen dieser beiden Kurven gleich sein. Damit kann man sich eine schöne Kurve basteln.
B-Splines sind eine Weiterentwicklung der Splines. Hier sieht man davon ab, daß die Kurve die gegebenen Punkte berühren muß. Statt dessen übt jeder Stützpunkt eine Art Anziehungskraft auf die Kurve aus, und bestimmt damit ihren Verlauf. Berühren muß die Kurve nur Anfangs- und Endpunkt.
Die Definition dieser B-Splines ist in der Datei "Bspline" näher beschrieben. Ausführlichere Informationen mit erklärenden Illustrationen findet man in der DOS International 8/92 S. 202.
Wer kann mir die Rekursionsformel für B-Splines erklären ?
Die Rekursionsformel über D[k,i] lautet
D[k,i] = (1-t[k,i])*D[k-1,i-1] +
t[k,i]*D[k-1,i]
mit
| x-u[i] | |
| t[k,i] = | --------------- |
| u[i+g+1-k]-u[i] |
bei vorgegebenen D[0,*].
Man könnte auch sagen: Die rekursive Definition der normierten B-Splines ist so strahlend schön, daß man zu einer derart wahnsinnig einfachen Rekursionsformel kommt :-)
Das einzige, was ich versuchen kann, ist, die rekursive Definition der B-Splines intuitiv zu verdeutlichen. Der Rest ergibt sich dann eigentlich ganz einfach. :-)
Sei ein Knotenvektor u[0]<=u[1]<=u[2] vorgegeben.
Der normierter B-Spline N[i,k] der Ordnung k (Grad k-1) besitzt die Trägermenge [u[i],u[i+k]). Er ist rekursiv definiert als
| x-u[i] | u[i+k]-x | |||
| N[i,k](x) = | ------------- | *N[i,k-1](x) + | --------------- | *N[i+1,k-1](x) |
| u[i+k-1]-u[i] | u[i+k] - u[i+1] |
Mit N[j,1](x) = 1([u[j],u[j+1]))(x).
Hierbei ist zu beachten, daß ein Summand alpha*N[j,k-1] nur dann gebildet wird, wenn die Trägermenge des beteiligten N[j,k-1] nicht leer ist, d.h. nur dann, wenn u[j] < u[j+k-1]. Ist u[j]=u[j+k-1], gilt N[j,k-1](x)=0, da die Trägermenge der N[j,1] und damit die Trägermenge sämtlicher B-Splines schlauerweise als halboffenes Intervall definiert ist. [a,a) = EMPTY und damit 1([a,a))(x) = 0;
Die Bedeutung der Faktoren kann man sich wie folgt veranschaulichen:
Der B-Spline N[i,k-1] hat die Trägermenge [u[i],u[i+k-1]). Der erste Faktor ist eine Gerade, die für x=u[i] (den linken Rand der Trägermenge) den Wert 0 und für x=u[i+k-1] (den rechten Rand der Trägermenge) den Wert 1 hat. Sie ist also eine Gewichtsfunktion bezüglich der Position von x innerhalb des Intervalls.
N[i+1,k-1] hat die Trägermenge [u[i+1],u[i+k]). Der zweite Faktor ist eine lineare Funktion, die für u[i+1] (linker Rand) den Wert 1 und für u[i+k] (rechter Rand) den Wert 0 hat. Die dazu komplementäre Gewichtsfunktion.
Daraus kann man leicht ein iteratives Schema zur Berechnung eines Funktionswertes herleiten. Ich führe einen Schritt exemplarisch für eine Spline-Kurve 3. Ordnung vor. Der allgemeine Beweis läßt sich daraus ganz leicht ableiten:
Sei x in I=[u[2],u[3]), u[2] < u[3]. I ist der Durchschnitt der Trägermengen von N[0,3], N[1,3] und N[2,3]. Daher werden zur Berechnung des Funktionswertes genau die Koeffizienten dieser B-Splines benötigt: Links steht die Summe, rechts jeweils die Trägermenge des betreffenden B-Splines:
| f(x)= | D0*N[0,3](x) + | | [u[0]..u[3]) |
| D1*N[1,3](x) + | | [u[1]..u[4]) | |
| D2*N[2,3](x) | | [u[2]..u[5]) |
| x-u[0] | u[3]-x | ||||
| = | D[0] * ( | ----------- | * N[0,2](x) + | --------- | * N[1,2](x) ) + |
| u[2]-u[0] | u[3]-u[1] | ||||
| x-u[1] | u[4]-x | ||||
| D[1] * ( | --------- | * N[1,2](x) + | --------- | * N[2,2](x) ) + | |
| u[3]-u[1] | u[4]-u[2] | ||||
| x-u[2] | u[5]-x | ||||
| D[2] * ( | --------- | * N[2,2](x) + | --------- | * N[3,2](x) ) | |
| u[4]-u[2] | u[5]-u[3] |
Der erste Summand der ersten Zeile fällt weg, da x nicht in der Trägermenge von N[0,2] liegt (N[0,2](x)=0), ebenfalls der letzte Summand der letzten Zeile, da x nicht in der Trägermenge von N[3,2] liegt (N[3,2](x)=0). Jetzt faßt man diagonal die Glieder mit N[1,2] und N[2,2] zusammen. Man erkennt ganz nebenbei, daß deren Faktoren jeweils die Summe 1 haben. Man hat den Ausdruck also reduziert:
| u[3]-x | x-u[1] | ||||
| f(x) | = D[1,1]*N[1,2](x) = (D0* | --------- | + D1* | --------- | ) * N[1,2](x) |
| u[3]-u[1] | u[3]-u[1] | ||||
| u[4]-x | x-u[2] | ||||
| + D[1,2]*N[2,2](x) = (D0* | --------- | + D1* | --------- | ) * N[2,2](x) | |
| u[4]-u[2] | u[4]-u[2] |
In Worten: D[1,1] liegt auf der Geraden zwischen D0 und D1. Wobei die Gewichte von D0 und D1 jeweils die relativen Positionen von x innerhalb der Durchschnittsmenge der Trägermengen von N[0,3] und N[1,3], also [u[1],u[3]), sind.
Vielleicht wird die geometrische Bedeutung klarer, wenn man die Zeilen in asymmetrischer Form schreibt, so daß z.B. der Faktor der ersten Zeile als Gerade in Punkt-Richtungsform D0 + lambda*(D1-D0) erscheint:
| x-u[1] | ||
| f(x) = D[1,1]*N[1,2](x) = (D0 + (D1-D0)* | --------- | ) * N[1,2](x) |
| u[3]-u[1] |
Führt man jetzt dieselbe Teilung für D[1,1] und D[1,2] durch - Teilungsparameter ist hier die relative Position von x im Intervall [u[2],u[3]) - so bleibt man auf
| u[3]-x | x-u[2] | ||||
| f(x) = D[2,2] = | ( D[1,1]* | --------- | + D[1,2]* | --------- | ) * N[2,1](x) |
| u[3]-u[2] | u[3]-u[2] |
| x-u[2] | ||
| ( D[1,1] + (D[1,2]-D[1,1]) * | --------- | ) * N[2,1](x) |
| u[3]-u[2] |
sitzen. N[2,1] ist 1 für alle x aus [u[2],u[3]), also ist der Faktor der gesuchte Funktionswert.
Bemerkenswert bei dieser Herleitung ist, daß alle in die Berechnung eingehenden Differenzenquotienten das betreffende Intervall [u[j],u[j+1]) umfassen, so daß überraschenderweise keine Fallunterscheidungen bei degenerierten B-Splines auf mehrfachen Knoten benötigt werden. Üblicherweise wird ja eine offene Kurve der Ordnung k mit n Polygonpunkten über einem Knotenvektor der Länge n+k mit je k identischen Knoten am Anfang und am Ende dargestellt.
Da wir gerade bei Formeln sind: Wolfgang BOEHM (TU Braunschweig) hat 1984 einen wunderschönen Algorithmus angegeben, mit dem in einem Schlag sämtliche Ableitungen einer B-Spline-Kurve berechnet werden können. Sei A(k) der Rechenaufwand für die Berechnung eines Funktionswertes einer Splinekurve k-ter Ordnung nach dem obigen Algorithmus. Dann benötigt der BOEHM-Algorithmus einen einmaligen Aufwand von A(k) für ein Intervall [u[j],u[j+1]) und danach einen Aufwand von je A(k) für die Berechnung sämtlicher Ableitungen an einem beliebigen Punkt aus dem Intervall. Interesse ?
Von Horst Krämer @ 2:2410/601.16
Erstellt von Ralf Wiebicke, letzte Änderung
27.03.97