Strecke mit Punkten - Biegungsberechnung
-
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?!?)
-
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.
-
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 kannFü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 okKubische 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
-
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.
-
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
-
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
SinthorasOkay 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 berechnenDemnach 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.
-
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
-
-
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 0Anschleiß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-2Dann 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 2Stimmt 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.