delfiphan - Do 15.12.05 03:05
Titel: Bewegungsabläufe via Cubic Spline

---

Mit diesem sehr kleinen Tool kann man Bewegungsabläufe mit der Maus vorgeben und den entsprechenden Code dazu generieren lassen.

Im Zip-File ist das Tool und Sources inkl. die CubicSpline-Unit.

Lizenz: Free for any use, use at own risk

PS: Natürlich wären andere Spline-Sorten u.U. geeigneter. Den äquidistanten Cubic Spline hatte ich halt bereits schon implementiert.

Edit: Code etwas vereinfacht.

Bergmann89 - Fr 11.09.09 15:40

---

Hey,

ich benutz deine CubicSpline-Unit zur Zeit erfolgreich für mein Spiel. Und es gibt auch paar andere Leute die sich dafür interessieren und seshalb wollt ich n kleines Tutorial darüber schreiben wie man so ne CubicSpline implementiert. Aber ich komm nich ganz klar mit der Sache. Hast du evtl. n Link, wo das ausführlich erklärt wird oder sowas? Hab auch schon bei Wikipedia [http://de.wikipedia.org/wiki/Spline-Interpolation#Der_kubische_C2-Spline] gesucht, aber da versteh ich auch Bahnhof, weil die ja nichma richtig erklären welcher Buchstabe was bedeutet -.-

MfG Bergmann.

delfiphan - Fr 11.09.09 19:15

---

In Wikipedia ist eigentlich alles erklärt. Kubische Splines sind zusammengesetzte Funktionen. Jedes Teilstück ist eine kubische Funktion (ax^3+bx^2+cx+d=f(x)). Die Aufgabe besteht darin, für jedes Teilstück die Koeffizienten a, b, c, d zu bestimmen, und zwar genau so, dass diese durch die vorgegebenen Werte gehen und die Teile nahtlos ineinander übergehen. Als mathematische Bedingung für "nahtlos" setzt man die Werte an den Stützstellen zwischen zwei Funktionen gleich, zusätzlich auch die Ableitung (Steigung) und die zweite Ableitung (Krümmung).

Das ganze schreibt man sich als Gleichungssystem und setzt die gegebenen Sachen ein und löst nach den gesuchten Koeffizienten auf (pro Funktion jeweils a, b, c, d). Es ist aber so, dass es weniger Gleichungen als Unbekannte gibt. Also setzt man beim natürlichen Spline die 2. Ableitung der beiden Enden der Gesamtfunktion einfach gleich Null.

Das Gleichungssystem kann man sich als Matrix schreiben. Die hat eine tridiagonale Form, d.h. man kann sie in O(n) in einer simplen for-Schleife lösen.

Vielleicht helfen die letzten zwei Seiten dieses Dokuments [http://www.tyberis.com/download/special.pdf] weiter.

Bergmann89 - Fr 11.09.09 23:01

---

Hey,

mit der Erklärung kann ich schon mehr anfangen. Wenn ich das richtig seh, dann stehen in deinem Array, was die Function CreateCubicSpline zurück gibts immer die werte a,b,c,d,a,b,c,d,... oder?
Die PDF schau ich mir dann nochmal genauer an, damit sollte ich das jetzt hin bekommen.
danke.

€: So, ich hab mir das Ganze jetzt ma zu Gemüte geführt. Und ich komm noch net so ganz klar. Ich hab dir meine Berechnungen mal hoch geladen. Ich hab am Ende auch die gleiche Matrix wie auf der Folie raus. A*z = b dafür berechnest du ja erst die Werte für b, um damit z auszurechnen. Und dann wird dein berechnetes z zum c-Parameter der kubischen Funktion. Aber z wäre bei mir die 2. Ableitung. Und irgendwie wiederspricht sich das jetzt mit meiner Formel für c. Is das was ich angefangen hab bloß n anderer Weg das Ganze zu rechnen oder hab ich n Fehler gemacht. Wäre toll wenn du dir ma Zeit nehmen könntest da drüber zu schauen...

MfG Bergmann

delfiphan - Sa 12.09.09 09:37

---

Ja, im Array stehen die Koeffizienten. Wenn du dir in den Sources die Funktion getCubicSplineAt anschaust dann siehst du die kubische Funktion:
Result := K[I*4+0] + (K[I*4+1] + (K[I*4+2] + K[I*4+3]*p)*p)*p; // p := t-I-1
d.h. ausgeschrieben:
Result := K[I*4+0] + K[I*4+1]*p + K[I*4+2]*p^2 + K[I*4+3]*p^3

Sind also genau die Koeffizienten. Zwei Dinge muss man beachten:
1. Die Funktionen sind so konstruiert, als ob eine Stützstelle bei 0 wäre. Das Teilstück ist also verschoben und muss beim Zusammensetzen an die richtige Stelle gebracht werden. Dahinter stecken numerische Überlegungen.
2. Das lineare Gleichungssystem der Matrix berechnet nicht direkt alle a, b, c, d. Sondern erst mal nur die b's. Die restlichen Koeffizienten kann man direkt aus den restlichen Gleichungen bekommen. Das passiert in den letzten 4 for-Schleifen in der Funktion createCubicSpline. Die genauen Formeln dafür entnehme man den Herleitungen (siehe Links unten).

In deinem Dokument habe ich gesehen, dass du den allgemeinen Fall rechnest mit beliebigen h's. Bei meinen Splines werden alle h = 1 gesetzt, um die Rechnung zu vereinfachen (ergibt einen äquidistanten kubischen Spline).

Herleitungen
Eine Kurzherleitung (äquidistanter k. Spline) findest du hier: http://mathworld.wolfram.com/CubicSpline.html - hier wird jedoch eine etwas andere Matrix aufgestellt. Ohne nachgerechnet zu haben glaube ich, dass die Herleitung äquivalent ist. Der Unterschied wird durch entsprechend andere Formeln für die c's und d's "ausgeglichen".

Für eine dieser Implementation entsprechende, aber umfangreichere Herleitung, siehe z.B. http://numerik.iwr.uni-heidelberg.de/~lehre/notes/num0/numerik0.pdf Abschnitt 2.3