Rotationsmatrizen, Quaternionen oder beides?

[Krishty]

Hi,

Ich baue gerade meine Szenenhierarchie auf und weiß nicht, wie ich Rotationsinformation speichern soll. Dass ich noch nicht genau weiß, was ich brauche und was nicht, macht die Sache nicht leichter … was mir zur Auswahl steht:

• Eine Rotationsmatrix pro Objekt.
  Vorteile:
  • Ich brauche mit an Sicherheit grenzender Wahrscheinlichkeit das lokale Koordinatensystem jedes Objekts. Das sind wiederum nur die passenden Zeilen der Matrix – ich erhalte es also quasi gratis.
  • Weniger Implementierungsaufwand – Matrizen habe ich so oder so, und wenn ich noch eine Zeile für die Verschiebung dazuschreibe, habe ich nicht nur die Rotations- sondern direkt die fertige Transformationsmatrix, mit der ich die Hierarchie durchackern kann.
  Nachteile:
  • Vielleicht ist die Einbindung in Physik-Engines schwieriger – die benutzen doch bestimmt alle Quaternions. (?) – Zumindest PhysX benutzt 3×4-Matrizen.
  • Schwer interpolierbar.
  • Falls ich um beliebige Achsen rotieren will, wird es haarig – dann kommt der ganze Schmach mit Euler-Winkeln (Gimbal Lock) (?) – Das ist eine Eigenschaft jeder Parametrisierung, weil wir im dreidimensionalen Raum arbeiten.
  • Matrizenmultiplikationen sollen nicht gerade einfach verdaulich für die CPU sein. Wenn ich die ganze Hierarchie durchgehe ist es definitiv langsamer als es Quaternions wären.
• Ein Quaternion pro Objekt.
  Vorteile:
  • Gut, wenn ich Physik-Engines integrieren möchte. (?) s.o.
  • Beliebige Rotationsachsen aus dem Effeff.
  • Leichte Interpolierbarkeit.
  • Schnell.
  Nachteile:
  • Wenn ich die objektlokalen Achsen haben möchte, darf ich es erst zu einer Rotationsmatrix konvertieren. – Das geht mit Vektorbefehlen in wenigen Takten
  • Quaternions müsste ich erst implementieren und testen.
• Ein Hybrid. Vorteile und Nachteile? Keinen Plan.

Stimmt das mit den Physik-Engines und was ich sonst so mutmaße? Habe ich was vergessen? Empfehlungen?

Gruß, Ky

[Aramis]

Sprich was dagegen, beide zu speichern und sie jeweils transparent (und lazy) zu aktualisieren wenn sich das jeweils andere aendert? Die jeweiligen Vor- und Nachteile hast du ja schon genannt.

Bei Quaternionen kommt noch die leichte Interpolierbarkeit (SLERP) dazu.

[Krishty]

Sprich was dagegen, beide zu speichern und sie jeweils transparent (und lazy) zu aktualisieren wenn sich das jeweils andere aendert?

Naja, auch der Implementierungsaufwand – ich habe damit geliebäugelt, Quaternions direkt wieder zu vergessen falls sich herausstellen sollte, dass ihre Vorteile zu gering wären.

Bei Quaternionen kommt noch die leichte Interpolierbarkeit (SLERP) dazu.

Sehr guter Punkt – die brauche ich tatsächlich.

[kimmi]

Und die Tatasache, dass Quaternionen die Gimbal-Look-Problematik nicht haben. Dazu ist die Quaternionen-Multiplikation schneller als die mit Rotationsmatrixen.

Gruß Kimmi

[Krishty]

Den Leistungsvorteil habe ich schon aufgezählt … und:

Und die Tatasache, dass Quaternionen die Gimbal-Look-Problematik nicht haben.

Gimbal Lock ist aber keine Problematik von Rotationsmatrizen an sich, sondern eher von Euler-Winkeln und dass man zum Rotieren die falschen Achsen (die nicht-lokalen) benutzt, oder?

[Schrompf]

Nach meiner Einschätzung kannst Du Quaternions ignorieren, solange Du nicht explizit die Interpolation brauchst. Die sieht bei Matrizen nämlich schon ab ein paar Grad Winkeldifferenz reichlich mistig aus. Eine Quaternion-Vektor-Transformation ist nach meinem Wissen aber sogar langsamer als eine Matrix-Vektor-Trafo - Du kriegst ein Rudel sin()/cos() rein und die Anzahl der Muls/Adds ist grob die selbe. Ich würde jederzeit zur Nur-Matrix-Vorgehensweise raten. Die Anbindung an die Physik ist zumindest bei PhysX auch auf 4x3-Matrizen basiert. Für die Rotation um beliebige Achsen gibt es auch für Matrizen fertigen Code. Ich empfehle dazu jederzeit einen Blick in die Matrix&Quaternion-FAQ.

Lazy Update Schemes mögen in der Theorie ne feine Erfindung sein. In der Praxis würde ich das aber nur für wirklich komplexe Objekte machen. Man versaut sich damit die const correctness - und das nicht nur im Sinne des Compilers, sondern auch im Sinne der Korrektheit des Ergebnisses. Die Lazy Updates ruinieren Dir die Parallelisierbarkeit. Und die paar, die wir noch in unserem Szenegraph drin haben, sind der Hauptgrund dafür, dass wir noch nicht parallel rendern können. Ok, die Resourcenbehandlung über mehrere Threads - wird dieser Buffer noch gebraucht oder kann ich ihn locken und neufüllen? - sind auch nicht ganz ohne.

Gimbal Lock könnt ihr komplett vergessen. Das war *nur* ein Problem von Eulerwinkeln - Matrizen sind da ebenso gefeit wie Quaternions.

[Chromanoid]

Ich würde mich für Matrizen entscheiden und Interpolation/Animation möglichst unabhängig implementieren. Da kann dann was auch immer benutzt werden, nur was rauskommt muss eben ne Matrix sein. Falls ne Physikengine o.Ä. Quaternionen ausspuckt, kannst du die dann mit einem Adapter einfach auf deine Matrizen schieben.

[gdsWizard]

Ich verwende eigentlich fast überall Rotationsmatrizen. Für die Rotationgeschwindigkeit verwende ich eulersche Winkel. Das mache ich auch in meiner kleinen physic engine so.

[kimmi]

@Krishy: Stimmt, die Tatsache mit dem Gimbal-Look und Eulerwinkeln hatte ich mal als Problem mittels Quaternions zu lösen, daher habe ich das als Punkt mit eingebracht.

Und hier ist dazu ein ercht schönes Statement, wie ich finde:
http://omega.di.unipi.it/web/IUM/Waterloo/node147.html

Ich benutze die Quaternionen in der regel auch nur, um letztendich verschiedene Rotationen zusammenzurechnen und dann eine rotationsmatrix daraus zu generieren. Und ich benutze sie für First-person-Kameras. Dort aber eher aus Faulheit, weil ich eine recht geschickte Implementierung des Ganzen mal zusammengebaut hatte.

Gruß Kimmi

[eXile]

Gnaaaaaaaaaaaaaaarg. Einspruch euer Ehren! Die Gruppe der Rotationen SO(3) ist topologisch gesehen gleich dem dreidimensionalem projektiven Raum PR³, damit sind Rotationsmatrizen Mist.

Es stimmt zwar, dass Rotationsmatrizen keinen Gimbal-Lock haben, aber nur, weil dieser Begriff dazu keinen Sinn ergibt! Damit man die Rotationsmatrizen sinnvoll benutzen kann, muss man sie parametrisieren, und dazu nimmt man nun einmal in der Regel Euler-Winkel. Alternativ kann man sie auch aus der Rotation, die durch einen Quaternion beschrieben wird, parametrisieren, aber dann kann man ja direkt Quaternionen benutzen. Worauf ich hinaus will: Durch eine solche Parametrisierung der Rotationsmatrizen erhält man sehr wohl ein Äquivalent zum Gimbal-Lock: Nämlich Singularitäten in der Parametrisierung (ich glaube, man muss einfach mal den ersten Winkel auf Pi/2 und den zweiten auf 0 setzen, das bastel ich auch noch mal raus). Und es wird noch besser: Es muss diese Singularitäten in der Parametrisierung geben, es geht gar nicht anders! Denn der SO(3) ist topologisch nun einmal der PR³; und den letzteren kann man nicht mit drei Parametern parametrisieren, denn sonst würden alle eure homogenen Koordinaten nur drei Werte (x, y, z) und nicht [x, y, z, w] aufweisen -- letzterer unterteilt nämlich gerade den Raum der homogenen Koordinaten in die jeweiligen Äquivalenzklassen der Geraden durch den Ursprung. Könnten wir Rotationen im dreidimensionalen Raum nämlich mit nur drei Parametern ohne Singularitäten beschreiben, könnten wir auch die Erde auf eine Karte ohne Singularitäten abrollen, aber das geht nun einmal nicht. Nun, was können wir also tun, wenn wir mit drei Koordinaten das Teil nicht in den Griff kriegen? Einfach vier nehmen, die Quaternionen. Dadurch erhält man auch eine nicht-isomorphe Abdeckung: Nämlich werden alle Rotationen durch zwei Quaternionen beschrieben; ein Quaternion hält eine Drehung bis 720° vor. Dadruch erreicht man genau eine doppelte Abdeckung des Rotationenraumes, der sogenannte Quaternion double cover. Das bringt auch ein paar Vorteile in der Animation, das muss ich aber noch einmal aus meinem Favoriten hervorkramen.

Warum sagt eigentlich hier niemand etwas zur Deorthogonalisierung von Rotationsmatrizen? Das ist eine totale Misthaufen; und wenn ich das wieder anständig orthogonal haben möchte, muss ich erstmal einen modifizierten Gram-Schmidt drüberjagen. Toll. Da doch lieber Quaternionen: Nicht-"orthogonalisierte" Quaternionen, d.h. nicht-Einheitsquaternionen kann man einfach normalisieren, und das Teil ist wieder eine Rotation.

Wie man sieht, mag ich Quaternionen. :)

Nachtrag: Warum kommen immer so spannende Threads, wenn ich Klausuren schreibe?

[kimmi]

Deorthogonalisierung -> siehe mein Post, ich habe sagen lassen. Und zum Thema SLERP wurde schon recht viel positives gesagt, was für Animationen ja sehr von Vorteil ist, wenn man es benutzt :).

Gruß immi

[Schrompf]

Ja, man sieht die Zuneigung. Rotationsmatrizen muss man nämlich gar nicht parametrisieren, man kann sie auch einfach verwenden und mit ihnen rechnen. Wenn man die auf 3 Parameter runterbricht, bekommt man natürlich wieder Gimbal Lock rein. Deswegen lässt man das ja auch sein.

Dass Matrizen mit vielen iterativen Rechenschritten langsam deorthogonalisieren, stimmt allerdings. Wir gehen nach xtausend Berechnungen irgendwann mal über die Rotationsmatrizen und renormieren und orthogonalisieren die Basisvektoren wieder. In der Praxis war das bisher nie nötig, aber aktuell gibt es ja auch noch keine langlebigen Spielstände und sowas, wo man das bemerken könnte.

Aus mathematischen Gesichtspunkten haben Quaternions durchaus ihre Vorteile. Aus Sicht eines Szenegraphen würde ich aber trotzdem zu Matrizen raten - die können auch Translationen, Skalierungen und noch ein paar Späße. Es ist für komplexere Rumrechnereien im Szenegraphen von Vorteil, wenn man alle möglichen Transformationen durch eine einzige Matrix abdecken kann.

[eXile]

Deorthogonalisierung -> siehe mein Post, ich habe sagen lassen. Und zum Thema SLERP wurde schon recht viel positives gesagt, was für Animationen ja sehr von Vorteil ist, wenn man es benutzt :).

Ne, SLERP meinte ich nun diesmal nicht, sondern eher, dass durch den Quaternion double cover man Rotationen zu 720° unterscheiden kann, und damit weniger in Gefahr läuft, zur rest pose falsch zu matchen. Beispielsweise den Arm aus Versehen um 360° zu verdrehen.

Irgendwie kann ich das mit der Deorthogonalisierung immer noch nicht sehen, wahrscheinlich habe ich einfach Tomaten auf den Augen :)

Ja, man sieht die Zuneigung. Rotationsmatrizen muss man nämlich gar nicht parametrisieren, man kann sie auch einfach verwenden und mit ihnen rechnen. Wenn man die auf 3 Parameter runterbricht, bekommt man natürlich wieder Gimbal Lock rein. Deswegen lässt man das ja auch sein.

Und wie erstellst du dir deine Rotationsmatrizen dann, wenn nicht über (wie auch immer geartete) drei Parameter? Einfach aus dem Vakuum ziehen? ;)

[Schrompf]

Ja, man sieht die Zuneigung. Rotationsmatrizen muss man nämlich gar nicht parametrisieren, man kann sie auch einfach verwenden und mit ihnen rechnen. Wenn man die auf 3 Parameter runterbricht, bekommt man natürlich wieder Gimbal Lock rein. Deswegen lässt man das ja auch sein.

Und wie erstellst du dir deine Rotationsmatrizen dann, wenn nicht über (wie auch immer geartete) drei Parameter? Einfach aus dem Vakuum ziehen? ;)

Gute Frage. Es gibt ja viele Verwendungsmöglichkeiten für Matrizen. Die Trafomatrizen von Grafikobjekten entstehen grob auf drei Arten:

a) Anfang als Einheitsmatrix, dann Anwendung von äußeren Rotationen und sonstigen Trafos durch den Nutzer im Editor.
b) Erstellung aus Basisvektoren - je nach Kontext muss man einen oder zwei vorgeben, die übrigen werden passend generiert.
c) Import aus 3D-Szenen.

Wer jetzt nochmal "Eulerwinkel" sagt, muss dreimal Notepad nachcoden. Die kommen nirgends vor und sind meiner Meinung nach auch dringend zu vermeiden.

[kimmi]

Deorthogonalisierung -> siehe mein Post, ich habe sagen lassen. Und zum Thema SLERP wurde schon recht viel positives gesagt, was für Animationen ja sehr von Vorteil ist, wenn man es benutzt :).

Ne, SLERP meinte ich nun diesmal nicht, sondern eher, dass durch den Quaternion double cover man Rotationen zu 720° unterscheiden kann, und damit weniger in Gefahr läuft, zur rest pose falsch zu matchen. Beispielsweise den Arm aus Versehen um 360° zu verdrehen.

Irgendwie kann ich das mit der Deorthogonalisierung immer noch nicht sehen, wahrscheinlich habe ich einfach Tomaten auf den Augen :)

Lese den Link und du wirst Erleuchtung finden, sofern ich dich richtig verstehe. Schließlich ist es nicht möglich, aus einer Rotationsmatrix eineindeutige Winkel rückzurechnen, Quaternionen können das IMHO schon.

Gruß Kimmi

[dot]

Schließlich ist es nicht möglich, aus einer Rotationsmatrix eineindeutige Winkel rückzurechnen, Quaternionen können das IMHO schon.

Was für Winkel? Eulerwinkel? Wenn man Eulerwinkel verwendet ist man praktisch immer am Holzweg. Und Eulerwinkel sind auch kein Feature von Matritzen oder sowas, ich kann genauso eine Quaternion aus Eulerwinkeln bauen und werd dabei die gleichen Probleme haben. Was das "Rückrechnen" angeht: Aus einer Quaternion kann ich einfach die Achse und den Winkel rausrechnen. Bei einer Matrix genauso (Eigenvektor zum Eigenwert 1, Spur der Matrix). Allerdings will man sowieso niemals auf Winkel zurückrechnen. Sobald man irgendwas mit Winkeln rummurkst macht man schlicht und einfach was falsch. Quaternionen haben Vorteile was numerische Stabilität angeht. Die einfache sphärische Interpolation würde ich auch noch als Vorteil ansehen. Das wars. Matritzen haben z.B. den Vorteil dass ich jede beliebige affine Transformation als Matrix darstellen kann...

[kimmi]

Du hast natürlich recht, ich hatte das mit der Reihenfolge von Rotationen für Matrizen durcheinander gebracht.

Gruß Kimmi

[Tiles]

Allerdings will man sowieso niemals auf Winkel zurückrechnen

Och. Bei einem Kompass oder ähnlichen Instrumenten wäre es schon ganz Nett zu wissen in welchem Winkel sich das Objekt gerade befindet :)

[kimmi]

Habe ich für einen Modell-Editor auch mal versucht. Wenn man Single-Precision nimmt ( also Floats ) kommt man durch Rundungsfehler in Teufels Küche. Ich habe dann mir einfach die Winkel vorher gemerkt und fertig war der Lack!

Gruß Kimmi

[Schrompf]

Vor allem brauchst Du da auch für den Kompass keinen Winkel, sondern eine Transformation des Zeigers relativ zum Kompass.

Eulerwinkel sind wirklich nutzlos. Im Ernst. Ich bin denn mal weg, Notepad nachcoden.

[Krishty]

Vor allem brauchst Du da auch für den Kompass keinen Winkel, sondern eine Transformation des Zeigers relativ zum Kompass.

Genau; Skalarprodukt aus normalisierter Kompassnadel und magnetischer Erdachse, acos(), fertig
Über den Rest msus ich jetzt erstmal grübeln … doch eine Menge, was hier zusammengekommen ist … wow

[Krishty]

Nochmal eine Frage: Rotationsmatrizen müssen wegen Rechenungenauigkeit früher oder später renormiert und orthogonalisiert werden. Bei Quaternions entfällt zumindest die Reorthogonalisierung; wie sieht es mit der Normierung aus?

[Schrompf]

Die Renormierung ist nach meinem Kenntnisstand genauso nötig.

[joeydee]

Vor allem brauchst Du da auch für den Kompass keinen Winkel, sondern eine Transformation des Zeigers relativ zum Kompass.

Genau; Skalarprodukt aus normalisierter Kompassnadel und magnetischer Erdachse, acos(), fertig
Über den Rest msus ich jetzt erstmal grübeln … doch eine Menge, was hier zusammengekommen ist … wow

Nö, eben nicht acos(), da rechnest du ja doch den Winkel zurück ;-) Vektor der Zeiger-Nordstellung durch die Inverse der Kamera jagen, fertig ist der Lack :-)

[Krishty]

Hmm, habe ich falsch verstanden. Tiles fragte imo nach dem Anwendungsfall, wo man die Transformation eines Objekts hat und nun wissen will, wie viel Grad es gegenüber Norden rotiert ist, um das z.B. als Kompass auf dem HUD anzuzeigen. Aber ich hatte eindeutig Z-Achse des Kompass statt normalisierter Kompassnadel schreiben wollen, denn die zeigt ja eh immer genau auf den Nordpol -.-

[dot]

Winkel brauchst du eigentlich ausschließlich nur dann wenn du den Zahlenwert des Winkels ausgeben willst. Alles andre lässt sich praktisch immer über Vektorrechnung viel eleganter lösen...

[Krishty]

Ja, keine Frage. Wie gesagt; ich dachte da an einen HUD-Kompass oder an einen Level-Editor.

[Krishty]

Oh wow … ich habe eben die Matrizenmethode implementiert, und die Interpolation (Matrizen => Quaternions => Slerp => Matrix) ist ja wirklich der letzte Scheiß!

Ich musste erstmal explizite Quaternion-Normierungen einbauen damit nicht die Hälfte der Rotationen wie blöd zittert. Jetzt ist es halbwegs stabil, bei schnellen Bewegungen habe ich aber noch Sprünge (bestimmte Rotationen lassen sich garnicht ansteuern, Hüpfer (Rotationen weit über 360 ° werden in die Gegenrichtung interpoliert), Gummieffekte (Interpolation oszilliert hin und her, fängt sich langsam) und strudelförmige Bewegungen.

Die Interpolation brauche ich „nur“ für die Kamerasteuerung; die wollte ich später sowieso komplett neu und anders machen … bis dahin halte ich es wahrscheinlich aus. Ich hoffe nur inständigst, dass ich nicht später noch irgendwas wichtiges interpolieren muss …

[Top-OR]

Puuuuuuh! Ich habe die meisten Rotationen bei meinem Kram als Quaternionen hinterlegt.

Obs die "beste Entscheidung" war, weiß ich nicht (besonders Angesichts dieser Diskussion) und wie ich sehe: Wie mans macht, macht mans falsch.

Ein bissel beruhigt es mich, dass auch andere sie fragen, wie man dieses Thema abfackelt.

Die Pro-Args für Quaternionen damals waren bei uns/mir: Quaternionen haben kleineren Speicherverbrauch (Jaaajaaa, 2002 hab ich mir/wir uns darum ne Platte gemacht - heute fliegen die MB nur so wech)
und man kann schön interpolieren. Außerdem kann man sich die Rotation als Quaternion "schön vorstellen" bzw. "schön definieren" (Achse+Winkel) und Interpolationen sind die Sahne!

Dann hast du aber wieder das Prob, dass die meisten Libs mit Interfaces für Matrizen um die Ecke kommen. Dann musst du, wie beschrieben, kostenintensiv umrechnen.
(z.B. wenn du die Rot direkt nach OpenGL schieben willst)
Mal ganz davon abgesehen, dass ich für ne Transformation immer die Rotation + Rest (Skalierung, Translation) extra machen muss, anstatt den Vektor einmal durch die Matrix zu schieben.

Wie gesagt: Alles irgendwie nicht perfekt, aber es läuft...irgendwie.

Edit: @Krishty - solche Effekte, wie du Sie beschreibst, hatte ich auch mal. Der Fehler lag in den Umrechungen zwischen Quaternion und Matrix. Da hab ich die lustigsten Effekte (Gummi) bekommen, da ich diese Rotationen bei skeletaler Animation beobachtet hatte: Das Model ist beim Drehen um sich selbst fast "bis zu 2D" plattgedrückt worden und wurde nach ein paar Grad weiterer Drehung "ganz fett". Vielleicht läuft deine Umrechnung irgendwo nicht sauber oder sowas?

[Schrompf]

Bone Animations kommen ja meist von Haus aus bereits als Quaternions daher. Die zu interpolieren geht eigentlich sauber. Sonderfälle wie Rotationen >180° gehen eigentlich auch, wenn man zwischendurch nicht in ne Matrix umrechnet. Die Pipeline vom 3D-Modeller bis zur Engine muss also passen. Gut, dass das (bis auf exotische Sonderfälle wie z.B. Flugzeug-Rotoren) in der Realität praktisch nicht vorkommt.

Ich hatte früher auch mit kollabierenden oder explodierenden Bones zu tun, wenn ich Quaternion-Animationen abgespielt habe. Die Probleme haben sich aber immer als Bug in der Matrix<->Quaternion-Umrechnung herausgestellt. Bzw. zu Teilen auch im Import der Daten. Hartnäckiges Debuggen heilt.

Alternativ kannst Du ja, wenn es nur um Kamera geht, manuell interpolieren. Du hast eine Kameratrafo am Start und eine am Ende. Du rechnest die Differenzmatrix aus, konvertierst die in eine Achse-Winkel-Darstellung und interpolierst nur noch den Winkel zwischen 0 und Ende. Ist im Endeffekt das gleiche wie eine Quaternion-Interpolation, nur halt mit alternativem Code. Die Matrix&Quaternion-FAQ müsste für alle Teilschritte fertigen Code bereithalten.