Strecke mit Punkten - Biegungsberechnung

SkiD

volkard schrieb:

Doch eine träge Kamera, die in den Kurven schlittert.
Oder durch Splines, Bezier-Kurven oder ähnliche weiche Kurven.

Also Kubische Splines sind genau das was ich suche, ich habe dafür HIER schon Hilfe gefunden, jedoch blicke ich da nicht recht durch.

Wie kann ich dann aus den Koordinaten meinen Spline bilden ?
Wie hier :

x aus [-4; -1]
S0(x) = 1/36·(x+4)^3 + 1/12·(x+4) - 2 
      = 1/36·x^3 + 1/3·x^2 + 17/12·x + 1/9 
x aus [-1; 0]
S1(x) = -1/12·(x+1)^3 + 1/4·(x+1)^2 + 5/6·(x+1) - 1 
      = -1/12·x^3 + 13/12·x
x aus [0; 1]
S2(x) = -1/12·x^3 + 13/12·x
      = -1/12·x^3 + 13/12·x
x aus [1; 4]
S3(x) = 1/36·(x-1)^3 - 1/4·(x-1)^2 + 5/6·(x-1) + 1 
      = 1/36·x^3 - 1/3·x^2 + 17/12·x - 1/9

Kann mir da jemand helfen, evtl. an einem nachvollziehbaren Beispiel ?

Grüße,
SkiD.

Sinthoras

Wenn du es per Hand rechnen musst, sind kubische Splines einigermaßen umständlich (geht natürlich, ist aber recht viel zu tun).

Was meist relativ schnell geht, ist Polynominterpolation.

Aber Vorsicht: Bei n Stützstellen, bekommst du ein Polynom vom (Höchst-)Grad n-1. Und je höhergradig das Polynom ist, desto stärker wird es (insbesondere) außerhalb des Bereiches, auf dem du interpoliert hast, oszillieren/"schwingen".
Wenn du also auch Werte der Funktion benutzen willst, die außerhalb dieses Bereichs liegen, müsstest du dich wohl mit Splines herumschlagen.

Hab mir jetzt nicht genauer deine Anforderungen durchgelesen. Entscheide das am besten erstmal selbst.
(Wollte dir Splines nicht ausreden, nur wenn du dich auf diesen Bereich beschränken willst, könntest du dir etwas Arbeit sparen.)

lg
Sinthoras

Sinthoras

Jetzt schreibe ich doch nochmal was genaueres zu kubischen Splines:

Der Grundgedanke ist erstmal der folgende: Du zerlegst das Intervall, auf dem du deine Funktion approximieren möchtest in n Teilintervalle.
Auf jeden dieser Intervalle bestimmst du eine Näherung niedrigen Grades (kubisch= 3. Grad).
An die resultierenden, kleinen "Funktionsstücke" stellst du dann noch bestimmte Anforderungen bspw. hinsichtlich der Glattheit. (Keine "Knicke" => Differenzierbarkeit, ...)

D.h.: Wenn du deinen Bereich in n Intervalle zerlegst, hast du n kubische Polynome der Form:
p_j = a_j + b_j (x - x_j-1 ) + c_j ( x - x_j-1 )² + d_j ( x - x_j-1 )³

Da du n Polynome dieser Form hast, musst du demnach 4n Parameter bestimmen (nämlich jeweis a_j, b_j, ... ).

Dafür nimmst du folgende Bedingungen:
(i) Stetigkeit/ Interpolationsbedingungen:
Für jedes der n Polynome weißt du, dass es an seinen Intervallgrenzen mit der zu approximierenden Funktion überein stimmt (sonst wäre deine Näherungsfunktion ja am Ende nicht stetig).
D.h. es gilt für alle p_j (mit j Element { 1, ... , n} )
p_j(x_j) = y_j
und
p_j-1(x_j-1) = y_j-1

(Du hast also jetzt schonmal 2n Bedingungen!)

(ii) Stetigkeitsbedingung der ersten Ableitung (Differenzierbarkeit der Grundfunktion) :

p_j ' (x_j) = p_j+1 ' (x_j) ,
für alle j Element { 1, ... , n-1 } ,
denn wenn deine approximierende Gesamtfunktion am Ende stetig sein soll, müssen die Ableitungen benachbarter Einzelteile an den "Nahtstellen" ja übereinstimmen.

(Damit hast du also weitere n-1 Bedingungen)

(iii) Stetigkeitsbedingung der zweiten Ableitung (diesen Luxus kannst du dir leisten, weil du kubisch interpolierst ):

Äquivalent zu (ii):

p_j '' (x_j) = p_j+1 '' (x_j) ,
für alle j Element { 1, ... , n-1 }.

(Ergibt also weitere n-1 Bedingungen.)

Damit hast du insgesammt nun also 2n + n - 1 + n - 1 = 4n - 2 Bedingungen.
Da du aber 4n Parameter hast, bleiben also 2 freie Parameter.
Nimm da einfach, was du möchtest.
Meistens sagt man, man möchte eine geringe Krümmung am Rand und sagt daher:
Für S (das sei deine aus Einzelteilen zusammengesetzte Funktion) gelte:
S'' (x₀) = S'' (x_n) = 0
(also p₀ '' (x₀) = p_n '' (x_n) = 0 )

Durch Umformen dieser Bedingungen kommst du dann auf 4n Gleichungen, hast also deine approximierende Funktion gefunden:

(Dafür definiert man die so genannten "Momente" M_j := S''(x_j),
also die zweite Ableitung an der Stelle x_j).

Es gilt:
(1) p_j (x) = a_j + b_j (x - x_j-1 ) + c_j ( x - x_j-1 )² + d_j ( x - x_j-1 )³

(2) p_j' (x) = b_j + 2 c_j ( x - x_j-1 ) + 3 d_j ( x - x_j-1 )²

sowie

(3) p_j'' (x) = 2 c_j + 6 d_j ( x - x_j-1 )

Du kannst jetzt immer so nach a_j, ... , d_j umformen, dass du Abhängigkeiten von x_j u.ä. und diesen Momenten bekommst.
Theoretisch hast du damit also alle Variablen erschlagen.
Und aus den obigen Gleichungen kannst du (ich poste dir diese auf Wunsch gern, dann aber ohne Herleitung ...) auch ganz gut Bedingungen für deine M gewinnen.
Das Problem: Du wirst dabei stets eine Abhängigkeit von _drei_ benachbarten M (also M_j-1, M_j und M_j+1) bekommen.
Und das ist der Grund, warum ich meinte, dass das für Handrechnung meist etwas umständlich wird.
Wenn du möchtest, kannst du die Formel haben und gucken, ob es in deinem Fall geht.

Ansonsten würde ich empfehlen: Interpoliere erstmal ganz normal mit einem einzigen Polynom und guck dir dann an, ob das für deine Zwecke reicht.
(Oder lass dir von irgendwem - normalerwiese erklären sich nur Computer zu so etwas bereit - deine Splines berechnen.)

Kubische bezier-kurven sind wesentlich einfacher. Du müsstest allerdings an jedem Punkt noch eine Geschwindigkeit definieren.

Sinthoras

Oder nimm die "Hinguck-Lösung":

f(x):= sqrt ( x) für alle x >= 0
= - sqrt ( -x ) für alle x < 0

(edit: sqrt halt für Quadratwurzel)

(edit2: oder sollten die Werte nur als Beispiel dienen?!?)

SkiD

Guten Morgen!

Danke schön für die ausführlichen Erklärungen!

Ich habe mich noch weiter etwas umgeschaut um der Sache irgendwie Herr zu werden, was nicht gerade einfach ist, da es wohl eine Vielzahl von Interpolationsmöglichkeiten gibt, sowie Verfahren um Kurven zu berechnen.

Kurz zu Interpolation:
Auf einer Seite bin ich über die Möglichkeit von Linearer Interpolation gestoßen, die Berechnung hierzu ist einfach, diese kann ich Problemlos nachvollziehen.
Die Kurve die hier entsteht ist jedoch sehr mathematisch ^^
Ausprobieren werde ich es dennoch erstmal, vielleicht genügt dass schon.
// Edit: Lineare Interpolation bei Polynomen höheren Grades ist hier gemeint!

Hermite Kurven bringen mir nichts, da ich keinesfalls Tangenten gegeben habe, sondern nur Punkte.

Cosinus Interpolation sieht irgendwie ergonomischer aus, jedoch bin ich mir nicht sicher, ob man direkt bei einer Kamerafahrt auf dieser "Linie" einen Unterschied bemerken würde.

Es werden noch andere, wesentlich komplexere Verfahren genannt, aber ich glaube da nicht, dass ich diesen Möglichkeiten Herr werden würde.

Zu Splines:
Im Endeffekt würde die Berechnung von diesen Kurven sowieso als Algorithmus in einem Programm von statten gehen, jedoch müsste ich diese Berechnung ersteinmal händisch ausführen, damit ich diesen Algorithmus überhaupt ersteinmal entstehen lassen kann

Kubische Splines sahen im großen und ganzen mit ambesten aus, deswegen werde ich mir die Zeit heute oder morgen nehmen deine Anmerkungen zu dieser Berechnung durch zugehen und versuchen nachzuvollziehen.

@ ZomboBombo :
Das Problem an Bezier-Kurven ist, dass ich für die Kurve zwei weitere Punkte bräuchte um eine Bezier-Kurve zu erstellen.

Ich habe jedoch gegebenen Punkte, durch die die Kamera durchführen muss.
D.h. es muss eine unmittelbare Verbindung zwischen den Punkten existieren, welche ergonomisch geformt ist, also nicht linear.

Geschwindigkeit an den einzelnen Punkten habe ich geben, jedoch nach meiner Recherche führt die entstehende Kurve an den Punkten vorbei, bzw. werden die für die Biegung gebraucht.

@ Sinthoras :
Die gegeben Punkte waren nur ein Beispiel
Ich hätte auch genauso gut andere Punkte aus dem Koordinatensystem nehmen können.

Bspw. P1(0, 0); P2(3, 1); P3(1, 3); P4(0, 0); P5(-1, -3) usw.

Grüße und nochmals Danke für eure Zeit,
SkiD.

SkiD schrieb:

@ ZomboBombo :
Das Problem an Bezier-Kurven ist, dass ich für die Kurve zwei weitere Punkte bräuchte um eine Bezier-Kurve zu erstellen.

Ich habe jedoch gegebenen Punkte, durch die die Kamera durchführen muss.
D.h. es muss eine unmittelbare Verbindung zwischen den Punkten existieren, welche ergonomisch geformt ist, also nicht linear.

Geschwindigkeit an den einzelnen Punkten habe ich geben, jedoch nach meiner Recherche führt die entstehende Kurve an den Punkten vorbei, bzw. werden die für die Biegung gebraucht.

Wenn du den Geschwindigkeitsvektor an den Kurven gegeben hast, kannst du zwei weitere Punkte einfügen (Anfang + k*Geschwindigkeit, Ende - k*Geschwindigkeit). Dann geht Bezier durch Anfang und Ende (so machen das doch die vektorzeichenprogramme?) Durch die eingefügten geht es nicht, aber das ist auch egal.

Wenn du keine Geschwindigkeitsvektoren hast, kannst du dir immer noch welche aus den umgebenden Punkten basteln. Das ist auch nicht geschummelt, denn die Wahl des Interpolationsverfahrens ist ja auch willkürlich.

Sinthoras

SkiD schrieb:

Guten Morgen!

Danke schön für die ausführlichen Erklärungen!

wirklich gern

Zu Splines:
Im Endeffekt würde die Berechnung von diesen Kurven sowieso als Algorithmus in einem Programm von statten gehen, jedoch müsste ich diese Berechnung ersteinmal händisch ausführen, damit ich diesen Algorithmus überhaupt ersteinmal entstehen lassen kann

Für den Rechner sind die ideal. Dann würde ich die nehmen.
Die Formeln sind halt etwas aufwändig, aber wenn sich nur der PC quält, ist ja alles ok

Kubische Splines sahen im großen und ganzen mit ambesten aus, deswegen werde ich mir die Zeit heute oder morgen nehmen deine Anmerkungen zu dieser Berechnung durch zugehen und versuchen nachzuvollziehen.

@ Sinthoras :
Die gegeben Punkte waren nur ein Beispiel
Ich hätte auch genauso gut andere Punkte aus dem Koordinatensystem nehmen können.

Ja, ich hatte es schon befürchtet
Wäre aber auch zu schön gewesen...^^

Grüße und nochmals Danke für eure Zeit,
SkiD.

Ich kann dir gern auch noch die Gleichung für die Momente posten, wenn du möchtest.
Da du M_0 und M_n kennst (=0 setzt), sollte sich das ganze auch schön aufrollen lassen. Macht halt Arbeit.

Die auf der von dir geposteten Seite dargestellte Matrix sollte eigentlich die dazugehörige Tridiagonalmatrix sein (die sich so ähnlich auch aus den Momenten ergäbe.)
Ich finde die Darstellung so fast etwas besser.

Du musst nur diese Matrix (bzw. das dazugehörige Gleichungssystem) in deinem Programm umsetzen, und die resultierenden b_i in deine Formeln für a_i und c_i
einsetzen. (d_i ist ja schnell gemacht.)

Sag Bescheid, wenn du noch Hilfe brauchst. Ich werds gerne versuchen.

lg
Sinthoras

SkiD

Hallo zusammen,

also dagegen hätte ich nichts

Sinthoras schrieb:

Ich kann dir gern auch noch die Gleichung für die Momente posten, wenn du möchtest.
Da du M_0 und M_n kennst (=0 setzt), sollte sich das ganze auch schön aufrollen lassen. Macht halt Arbeit.

Die auf der von dir geposteten Seite dargestellte Matrix sollte eigentlich die dazugehörige Tridiagonalmatrix sein (die sich so ähnlich auch aus den Momenten ergäbe.)
Ich finde die Darstellung so fast etwas besser.

Du musst nur diese Matrix (bzw. das dazugehörige Gleichungssystem) in deinem Programm umsetzen, und die resultierenden b_i in deine Formeln für a_i und c_i
einsetzen. (d_i ist ja schnell gemacht.)

Sag Bescheid, wenn du noch Hilfe brauchst. Ich werds gerne versuchen.

Also ich denke Splines sind da wirklich besser, hoffe ich jedenfalls.
Ich habe es nun mit Interpolation versucht, sieht soweit auch schön und sauber aus, dass Problem ist nur, dass die Interpolationsformel extreme Ausmaße annimmt, wenn ich mehr als 6 Punkte habe.
Bei 9 Punkten schmirrt mir gar mein Entwicklungstool ab.

Ich weiss hier jedoch auch nicht ob Fehler entstehen, wenn ich jedesmal die Interpolation nach 1-2Punkten neu berechne für jeweils die nächsten 4 Punkte.
So könnte ich eine Strecke von 12-20 Punkten denke ich gut aufteilen ohne große meine Ressourcen zu belasten.

Splines an sich sahen schon wesentlich besser aus, bzw. sind eigentlich ideal, jedoch komme ich hier mit der Berechnung gar nicht klar.

Danke nochmals!

SkiD.

Sinthoras

Zur Polynominterpolation:
Bei 20 Punkten bekommst du ein Polynom vom (Höchst-) Grad 19.
Du hast 20 Gleichungen mit 20 Variablen. Das entsprechende Gleichungssystem sollte machbar sein, wenn du es mit dem
Gaußschen Eliminationsverfahren auflösen lässt.
Falls du vorhast, immer wieder verschiedene Funktionen (mit denselben Stützstellen) zu interpolieren, bietet sich die LR-Zerlegung an.
(Animation/ Erklärung zur LR-Zerlegung.)
(Ist dir LR-Zerlegung etc. ein Begriff oder verwirrt dich das jetzt?)

Zu Splines:
Wo hakt es bei den Berechnungen?
Kannst du mit Matrizen etc. umgehen oder wo drückt der Schuh?

lg
Sinthoras

SkiD

Sinthoras schrieb:

Zur Polynominterpolation:
Bei 20 Punkten bekommst du ein Polynom vom (Höchst-) Grad 19.
Du hast 20 Gleichungen mit 20 Variablen. Das entsprechende Gleichungssystem sollte machbar sein, wenn du es mit dem
Gaußschen Eliminationsverfahren auflösen lässt.
Falls du vorhast, immer wieder verschiedene Funktionen (mit denselben Stützstellen) zu interpolieren, bietet sich die LR-Zerlegung an.
(Animation/ Erklärung zur LR-Zerlegung.)
(Ist dir LR-Zerlegung etc. ein Begriff oder verwirrt dich das jetzt?)

Zu Splines:
Wo hakt es bei den Berechnungen?
Kannst du mit Matrizen etc. umgehen oder wo drückt der Schuh?

lg
Sinthoras

Okay was Polynominterpolation angeht, dass habe ich so gelöst, da ich von der gegebenen Punktemenge, jeweils immer 4 herausnehme und diese interpoliere.
So kann ich mir Rechenaufwand und Ressourcen sparen.
Leider kann ich nicht mehr als 9 Punkte interpolieren, da meine Umgebung, wo das Programm läuft, nicht gerade sehr stark rechenfähig ist!

Hier habe ich nun ein anderes Problem:
Zu jeden gegebenen Punkt habe ich eine Geschwindigkeit gegeben, welche Aufschluss darüber gibt, wie schnell (meter / sekunde) sich die Kamera von einem Punkt zum anderen Punkt bewegt.

Beispiel:
P0.geschwindigkeit = 2.5
P1.geschwindigkeit = 1

D.h. 
Die Kamera bewegt sich von P0 zu P1 mit einer Geschwindigkeit von 2.5 meter/sekunde, ab P1 bis P2 bewegt diese sich mit einer Geschwindigkeit von 1 meter/sekunde.

(Hier soll keine Beschleunigung oder Abbremsung berücksichtigt werden)

Ich weiss nur leider nicht, wo ich das anbringen kann, bzw. wo ich die Geschwindigkeit mit einberechnen soll.

Gegeben habe ich eigentlich alles was ich benötige, wie Gesamtzeit der Bewegung über die gesamte Strecke, die Punkte selbst, die Formel die mir die Interpolationskurve verschafft, den t Wert, der mir beschriebt an welche Position ich mich auf der Kurve befinde zum Zeitpunkt t, wieviel Zeit schon vergangen ist (der Algorithmus und die Aktualisierung des Bildes findet alle 33.33ms statt, was bedeutet dass ich in der Sekunde ca. 30.03 FPS schaffe).

Meine Vorgehensweise ist wie folgt:
1.) t-Werte festlegen
2.) Erstellung der t-Matrix und deren Inverse
3.) P-Vektroen für Dimensionen bilden
4.) Inverse Matrix mit P-Vektoren multiplizieren
5.) Interpolationsformel bilden und die Werte zu dem gegebenen t berechnen

Demnach komme ich auf die x,y und z Koordinaten, allerdings nur mit konstanter Geschwindigkeit. Wenn ich die Geschwindigkeit erhöhen möchte um einen bestimmten Faktor, weiss ich nicht genau wo.

Zu Splines:
Bei Splines finde ich gar keinen Halt, ich weiss nicht direkt, wie man da anfangen soll und wie die genauen Schritt sind.

Der Formelwald auf Hilfeseiten (wie HIER) ist für mich nur wenig hilfreich, da ich die Vorgehensweise meist nur an Beispielen verstehe, wie bei der Polynominterpolation auch.

Mit Matrizen und Vektoren kann ich umgehen!

Liebe Grüße,
SkiD.

Sinthoras

Zu Splines:
(Ich halte mich dafür jetzt mal an deine Internetseite, also d_i als Koeffizient für x^0, c_i für x^1 usw.)

Du hast i einzelne, kubische Polynome, für die du jeweils a_i, b_i, c_i und d_i bestimmen musst.
Das i-te Polynom/ der i-te Spline, also p_i, ist deine Näherung für den Bereich x_i bis x_i+1.

Dabei sind deine d_i ja schonmal klar - wenn deine Splines die Funktion gut wiedergeben sollen, werden sie an den Stellen x_i wohl auch die Funktionswerte y_i der Funktion haben - also d_i = y_i.

Die Gleichungen (III) und (V) auf deiner Seite geben dir deine a_i und c_i, du brauchst dafür nur b_i.

Das einzig aufwendig ist es jetzt, b_i zu bestimmen.
Dies erreichst du über die Gleichung (VI), wobei es - wie schon erwähnt - Probleme bereitet, dass die Gleichung stets drei b_i erfasst.
Prinzipiell erhälst du aus (VI) aber i Gleichungen der Form:

(bla) * b_i-1 + (blabla) * b_i + (blablabla) * b_i+1 = (blablubb)

bla und so weiter sind fest und bekannt, da sie nur von x_i und d_i abhängen und du diese kennst.
Jetzt passiert im nächsten Schritt nichts anderes, als dass diese i Gleichungen als ein lineares Gleichungssystem aufgefasst werden (k-te Zeile entspricht k-ter Gleichung).
Nämlich als:
M * b = r
mit:
-der Matrix M als Koeffizientenmatrix des LGS, also deine "bla" usw...
(auch dabei entspricht die k-te Zeile den Koeffizieten der k-ten Gleichung).
-b als Vektor deiner b_i.
(der k-te Eintrag entspricht dem k-ten b_i (also b_k). Dieser Vektor ist unbekannt und ist das, was bestimmt werden soll!)
-r als Vektor der rechten Seite des LGS.
(die Einträge sind also die rechten Seiten - "blablubb" - deines LGS)

Mit bekanntem M und r kannst du dieses LGS (wie auch immer du gern möchtest) lösen und erhälst (ein dank der Gestalt der Matrix sogar eindeutigen) Vektor b, welcher alle deine b_i als Einträge enthält.

Mit diesen b_i errechnest du wie oben beschrieben alle a_i und c_i und bist damit dann fertig.

lg
Sinthoras

http://farside.ph.utexas.edu/teaching/329/lectures/node63.html

SkiD

Okay also folgendes:

Ich habe das versucht an deiner Erklärung und einem anderen Beispiel nachzuvollziehen, ich schreibe dir meine Schritt mal nacheinander auf (da wo ich nicht weiter kam, bzw. keine Lösung hatte steht ein Fragezeichen):

Punkte (Stützstellen):

P0[-2,  0]
P1[-1,  0]
P2[ 0,  1]
P3[ 1,  0]
P4[ 2,  0]

Das erste was ich gemacht habe ist mir eine Tabelle gebastelt: (^^)

i  0  1  2  3  4 
x -2 -1  0  1  2
y  0  0  1  0  0

Anschleißend wollte ich h[i] und t[i] berechnen mit den Formeln:

h[i] = x[i+1]-x[i]
t[i] = (x- x[i]) / h[i]

D.h. dann

i      0   1   2   3   4 
x[i]  -2  -1   0   1   2
y[i]   0   0   1   0   0
------------------------
h[i]   1   1   1   1   ?
t[i] x+2 x+1   x x-1 x-2

Dann berechnete ich m[i], bzw. erstellte die Formeln:

i = 0    
b1: 2*m[0] + m[1]     = 3 * (y[1] - y[0]) / h[1]

i = n    
b2: m[n-1] + 2 * m[n] = 3 * (y[n] - y[n-1]) / h[n-1]

i = 1 bis n-1
f4: h[i]/(h[i-1]+h[i]) * m[i-1] + 2 * m[i] + h[i-1]/(h[i-1]+h[i]) * m[i] + 1 = 
    3/(h[i]+h[i-1]) * (h[i-1]*(y[i+1]-y[i])/h[i] + h[i] * (y[i]-y[i-1])/h[i-1])

So dann komme ich nicht weiter, da ich nicht weiss ob ich mich verrechnet habe, wenn ich meine Ergebnisse mit der aus dem Beispiel abgleiche.

Ich bilde m[i]

m[0]    m[1]    m[2]    m[3]    m[4]
 2       1       0       0       0
 1       2       1       0       0
 0       1       2       1       0
 0       0       1       2       1
 0       0       0       1       2

Stimmt das soweit ?
Bei dem Beispiel kam da mehrmals 1/2 raus, wobei ich nicht glaube dass das stimmt, wenn ich dem HIER recht geben darf (siehe Koeffizientenmatrix).

Erstmal bis hierher, bevor ich jetzt weiterrechne, möchte ich lieber Nummer sicher gehen, dass es in soweit stimmt!

Ach ja, ich kann gar nicht weiterrechnen fällt mir gerade ein, weil ich nicht weiss wie ich auf m[0] ... m[4] komme...

Kannst du mir einen Tipp geben ?

Grüße,
SkiD.