Kamerafahrt Interpolation

Hallo,

ich habe einen Datensatz aus mehreren 3D-Punkten gegeben, aus diesem sich eine Kamerafahrt ergeben soll. Bisher bin ich diese Punkte immer linear abgefahren, wodurch die Kamerafahrt sehr hakelig wurde. Ich suche nun also eine Methode um diese Kamerafahrt weicher zu gestalten, ich möchte die Strecke zwischen den Punkten also interpolieren.
Mein Problem dabei ist einerseits, dass dies das erste mal ist, dass ich mit Interpolationen in Berührung komme und dabei nur Methoden zu 2D-Interpolationen, aber nichts zu 3D, finde. Die Interpolation soll dabei monoton sein.
Andererseits soll sich die Kamera mit einer konstanten Geschwindigkeit bewegen. Ich habe es so verstanden, dass sich bei einer (2D)-Interpolation eine Funktion ergibt, die jedem x ein eindeutiges y zuweist. Nun habe ich aber jeden Zeitschritt eine Zeitdifferenz dt seit dem letzten Schritt. Wie kann ich aus diesem dt ermitteln, wie groß dx zu wählen ist, damit die Länge von (dx,dy) äquivalent zu meiner Geschwindigkeit*Zeit ist?

Kennt ihr gute Quellen zu meiner ersten Frage und was soll ich bezüglich meiner zweiten Frage machen?

Vielen Dank im Voraus!

Th69

Schau dir mal Overhauser (Catmull-Rom) Splines for Camera Animation an - dies gilt auch für 3D (wird auch weiter unten per Code erklärt).

TGGC

Allein durch Punkte ist die Kamerafahrt aber nicht hinreichend beschrieben. Es ist auch noch die Ableitung der Bewegung in dem Punkt noetig (a.k.a. Geschwindigkeit). Ansonsten kannst du z.b. einfach ein lerp(cos(t/pi)) machen, dann ist die Geschwindigkeit immer 0 an den Punkten und damit die Ableitung stetig.

Finnegan

TGGC schrieb:

Allein durch Punkte ist die Kamerafahrt aber nicht hinreichend beschrieben. Es ist auch noch die Ableitung der Bewegung in dem Punkt noetig (a.k.a. Geschwindigkeit). Ansonsten kannst du z.b. einfach ein lerp(cos(t/pi)) machen, dann ist die Geschwindigkeit immer 0 an den Punkten und damit die Ableitung stetig.

Ne Normale für die Kamera je Punkt wäre auch nicht verkehrt (kann man getrennt von der Kurve interpolieren. Slerp! Slerp! :)).
Damit ist dann auch die Rotation der Kamera um den jeweiligen Tangentialvektor definiert, wenn man die Kameraposition
an den Punkten wirklich frei modellieren möchte (immer nach "oben" tuts natürlich je nach Anwendungsfall auch).

Kameramann schrieb:

Kennt ihr gute Quellen zu meiner ersten Frage und was soll ich bezüglich meiner zweiten Frage machen?

Zu deiner zweiten Frage: Falls dir Parametrische Kurven¹ nichts sagen sollten, empfehle ich dir, dich da ein wenig einzulesen.
Eine konstante Kamera-Geschwindigkeit hinzubekommen kann je nach Anspruch ein klein wenig komplizierter werden, als es sich zuerst anhört.

Kurz und knapp: Du musst die Kurve² ( $\mathbf x$ ) nach der Bogenlänge parametrisieren, bzw. du musst dein $t$ während der Kamerafahrt
nicht um $\Delta t$ erhöhen, sondern um $\frac{\Delta t}{s}$ , wobei $s$ die Länge der Kurve zwischen $\mathbf{x}(t)$ und $\mathbf{x}(t + \Delta t)$ ist. Die einfachste Variante ist wohl,
die Länge dieses Kurvensegments anzunähern, indem man den Bereich in eine Anzahl Intervalle unterteilt und die Distanzen zwischen
den Endpunkten dieser Intervalle auf der Kurve aufsummiert (siehe auch Trapezregel). Wenn dieses (unter Umständen recht grobschlächtige)
Ergebnis zufriedenstellt, dann herzlichen Glückwunsch! ... Ansonsten:

Bisschen mehr Hintergrund: Wenn man es ganz präzise möchte, muss in jedem Schritt $s = \int_{t}^{t + \Delta t}\|\mathbf {\dot x}(t)\|dt$ berechnet werden (wobei $\mathbf {\dot x}(t)$ der
Tangentialvektor³ am Punkt $\mathbf x(t)$ ist) - also quasi die "kontinuierliche Summe" der Kurven-Geschwindigkeit, das ist die exakte Länge des Kurvensegments.
Das Integral wird meist schon bei simplen Kurven kaum zu bändigen, und im Allgemeinen löst man es mithilfe Numerischer Integration.
Die erwähnte Trapezregel ist eine Variante davon, wenn du es genauer benötigst, solltest du dich in weitere Verfahren einlesen.

¹: z.B. im $\mathbb{R}^{3}$ : $\mathbf {x}(t) = \begin{pmatrix}x(t)\\y(t)\\z(t)\end{pmatrix}$ , mit den Koordinatenfunktionen $x(t)$ , $y(t)$ und $z(t)$ . "Freie" Kurve im Raum, nichts mit "jedem x ein eindeutiges y", kann sich kreuzen, Schleifen und Pirouetten drehen

²: z.B. die von Th69 vorgeschlagenen Catmull-Rom-Splines, die ich auch empfehlen würde.

³: $\mathbf {\dot x}(t) = \begin{pmatrix}\frac{d}{dt}x(t)\\\frac{d}{dt}y(t)\\\frac{d}{dt}z(t)\end{pmatrix}$ , erste Ableitungen der Koodinatenfunktionen. "Geschwindigkeit" (Länge) und Richtung der Kurve.

Vielen Dank für die Antworten. Die Links und Erklärungen sind wirklich super!
Nach einigem Einlesen in die Materie habe ich ein paar Überlegungen angestellt, von denen ich gerne wissen würde, ob diese richtig und realisierbar sind.
Die Catmull-Rom Splines sehen wirklich überzeugend aus. Für das entlanglaufen der Kurve mit einer konstanten Geschwindigkeit habe ich unter anderem dieses Paper hier gefunden: http://www.geometrictools.com/Documentation/MovingAlongCurveSpecifiedSpeed.pdf
Wie in diesem schon angesprochen, ist die Reparametriesierung zur Laufzeit sehr Rechenintensiv, weshalb diese Methode für meine Zwecke nicht zu gebrauchen ist. Aus diesem Grund habe ich mir folgendes überlegt:
Bevor die Animation nun startet, rechne ich für jedes Segment - z.B. anhand der im Paper genannten Methode - seine Länge aus. Dadurch weiß ich automatisch, wie lang die Kurve insgesamt ist und wie viel Zeit ich bei einer festen Translationsgeschwindigkeit benötige um die Kurve zu durchlaufen. Ebenso kann ich anhand der Länge jedes Segments direkt auch die Rotationsgeschwindigkeit für jedes Segment ermitteln. Wie ich die Rotation interpoliere, muss ich mir noch überlegen.
Zur Laufzeit errechne ich jetzt in jedem Zeitschritt, wie viel Strecke s ich zurückgelegt habe. Dadurch ermittle ich, in welchem Segment der Kurve ich mich befinde. Für jedes Segment kann ich ganz einfach tmin, tmax (Kurvenparameter) und smin, smax (Bogenlänge zu Beginn und Ende des Segments) ermitteln. Mein gesuchter Kurvenparameter t wäre dann
$t = t_{min} + (t_{max} - t_{min}) * \frac{s - s_{min}}{s_{max}}$
Sind meine Überlegungen so richtig?

Dann stellt sich mir noch eine mathematische Frage. Zum ermitteln der Bogenlänge benötigt man unter anderem die Ableitung der Kurve nach dem Kurvenparameter t. Reicht es in diesem Fall die vier Polynome b1...b4, wie in dem von Th69 geposteten Artikel beschrieben, einfach nach t abzuleiten? Oder habe ich hier einen Denkfehler?

Finnegan

Kameramann schrieb:

...ich unter anderem dieses Paper hier gefunden: http://www.geometrictools.com/Documentation/MovingAlongCurveSpecifiedSpeed.pdf

Das sieht beim groben Überfliegen nach einem guten Fund zu dem Thema aus. Das werd ich mir auch mal in mein Archiv packen, falls ich sowas auch nochmal machen muss

Kameramann schrieb:

Wie in diesem schon angesprochen, ist die Reparametriesierung zur Laufzeit sehr Rechenintensiv, weshalb diese Methode für meine Zwecke nicht zu gebrauchen ist.

zwei Sachen dazu:
1. Heutige Rechner sind meist schneller als man denkt. Aus dem Bauch heraus würde ich behaupten, dass man sich das für eine einzelne Kamerafahrt problemlos
leisten kann. Wenn man allerdings anfängt, das Verfahren für eine große Anzahl von Objekten zu verwenden (man könnte damit z.B. nicht nur die Kamera, sondern
auch Welt-Objekte entlang eines vorgegebenen Pfades bewegen), könnte es sich schon bemerkbar machen.
2. Das Paper bietet dafür unter "6. Avoiding the Numerical Solution at Runtime" auch eine Lösung an. Die Grundidee dabei ist, die Bogenlängenparametrisierung $s(t)$
selbst auch wieder durch ein Interpolationspolynom anzunähern.

Kameramann schrieb:

Aus diesem Grund habe ich mir folgendes überlegt:
Bevor die Animation nun startet, rechne ich für jedes Segment - z.B. anhand der im Paper genannten Methode - seine Länge aus. Dadurch weiß ich automatisch, wie lang die Kurve insgesamt ist und wie viel Zeit ich bei einer festen Translationsgeschwindigkeit benötige um die Kurve zu durchlaufen. Ebenso kann ich anhand der Länge jedes Segments direkt auch die Rotationsgeschwindigkeit für jedes Segment ermitteln.

Wenn ich das richtig verstanden hast, dann wirst du damit das Problem der variablen Geschwindigkeit innerhalb der Segmente haben.
Die Geschwindigkeit der Kurve ist von $t$ abhängig ( $\|\mathbf{\dot x}(t)\|$ , Länge des Tangentialvektors). D.h. es kann dir während du ein Segment durchläufst passieren, dass die Kamera spürbar schneller/langsamer wird.
Mit Rotationsgeschwindigkeit ist mir nicht ganz klar, was du in diesem Kontext damit meinst. Die Kurve gibt dir eine Position im Raum, das ist der Funktionswert der Kurve $\mathbf{x}(t)$ und eine Richtung,
das ist der Tangentialvektor $\mathbf{\dot x}(t)$ an dieser Position. Während der Kamerafahrt wird sich die Kamera an $\mathbf{x}(t)$ befinden und in Richtung $\mathbf{\dot x}(t)$ schauen.
Allerdings benötigst du tatsächlich eine Rotation (auch wenn diese sich nicht aus den Segmenten ermitteln lässt):
Die Rotation um den Tangentialvektor, oder anders ausgedrückt, die "Oben"-Richtung der Kamera (das was ich in meiner Antwort an TGGC angerissen habe).
Schließlich kann die Kamera beliebig um den Tangentialvektor rotiert sein und trotzdem immer in Richtung desselben "schauen".

Kameramann schrieb:

Wie ich die Rotation interpoliere, muss ich mir noch überlegen.

Ein guter Startpunkt für Rotations-Interpolation: Slerp
(Auch verlinkte Artikel beachten, Slerp ist nicht unbedingt für jeden Anwendungsfall das was man möchte)

Kameramann schrieb:

Zur Laufzeit errechne ich jetzt in jedem Zeitschritt, wie viel Strecke s ich zurückgelegt habe. Dadurch ermittle ich, in welchem Segment der Kurve ich mich befinde. Für jedes Segment kann ich ganz einfach tmin, tmax (Kurvenparameter) und smin, smax (Bogenlänge zu Beginn und Ende des Segments) ermitteln. Mein gesuchter Kurvenparameter t wäre dann
$t = t_{min} + (t_{max} - t_{min}) * \frac{s - s_{min}}{s_{max}}$
Sind meine Überlegungen so richtig?

Siehe oben. Das ist eine lineare interpolation ("Verbinden mit gerader Linie") der Segmentlänge.
Du wirst damit zwar für jedes Segment die gleiche Zeit benötigen, um dieses zu durchlaufen, aber innerhalb des Segments kann die Geschwindigkeit dennoch merklich schwanken.

Tip: Versuch erstmal die benötigte Länge der Kurve zwischen $\mathbf{x}(t)$ und $\mathbf{x}(t + \Delta t)$ auf einfache Weise Anzunähern, so wie hier z.B ("Trapezregel").
Wenn das nicht reicht, dann mit dem Verfahren aus dem Paper, und wenn das dann immer noch zu lahm sein sollte, versuch es mit Punkt 6. aus dem Paper.

Kameramann schrieb:

Dann stellt sich mir noch eine mathematische Frage. Zum ermitteln der Bogenlänge benötigt man unter anderem die Ableitung der Kurve nach dem Kurvenparameter t. Reicht es in diesem Fall die vier Polynome b1...b4, wie in dem von Th69 geposteten Artikel beschrieben, einfach nach t abzuleiten? Oder habe ich hier einen Denkfehler?

In diesem Fall: ja.

Die Kurve $\mathbf{P}(t)$ (die ich hier weiterhin mit $\mathbf{x}(t)$ bezeichne) ist ja durch die Kontrollpunkte

$P\_1 = \begin{pmatrix}x\_1\\y\_1\\z\_1\end{pmatrix}, ..., P\_4 = \begin{pmatrix}x\_4\\y\_4\\z\_4\end{pmatrix}$

und die Polynome $b\_1, ..., b\_4$ definiert:

$\mathbf{x}(t) = b\_1 P\_1 + b\_2 P\_2 + b\_3 P\_3 + b\_4 P\_4 = \begin{pmatrix}b\_1 x\_1 + b\_2 x\_2 + b\_3 x\_3 + b\_4 x\_4\\b\_1 y\_1 + b\_2 y\_2 + b\_3 y\_3 + b\_4 y\_4\\b\_1 z\_1 + b\_2 z\_2 + b\_3 z\_3 + b\_4 z\_4\end{pmatrix}$

Eigentlich müsste man jede Koordinatenfunktion (Zeile des obigen Vektors) getrennt nach $t$ ableiten.
Aufgrund Summen- und Faktorregel reicht es jedoch, nur die Polynome abzuleiten, um $\mathbf{\dot x}(t)$ zu bestimmen:

$\mathbf{\dot x}(t) = \begin{pmatrix}\frac{d}{dt}(b\_1 x\_1 + b\_2 x\_2 + b\_3 x\_3 + b\_4 x\_4)\\\frac{d}{dt}(b\_1 y\_1 + b\_2 y\_2 + b\_3 y\_3 + b\_4 y\_4)\\\frac{d}{dt}(b\_1 z\_1 + b\_2 z\_2 + b\_3 z\_3 + b\_4 z\_4)\end{pmatrix} = (\frac{d}{dt}b\_1) P\_1 + (\frac{d}{dt}b\_2) P\_2 + (\frac{d}{dt}b\_3) P\_3 + (\frac{d}{dt}b\_4) P\_4$

Hoffe, das ist hilfreich, und dass ich selbst auch keinen Stuss eingebaut habe :D.
Finnegan