Was sind die Vorteile von Constraint-basierten Solvern?

7

Ich bin ein ziemlich kompetenter Programmierer und ich bin nicht schlecht in Mathe. Ich arbeite seit ungefähr 2 Jahren an Simulationen der Spielphysik.

In einigen Büchern und Tutorials, die ich gelesen habe, werden Einschränkungen eingeführt. Sie berechnen jakobianische Matrizen und verwenden Baumgarte-Konstanten und all das komplizierte Zeug.

Selbst wenn ich mich sehr bemühe und ihrer Logik folge, fühle ich mich immer verloren. Es ist nicht so, dass die Mathematik oder die Algorithmen der Technik zu kompliziert sind. Es ist nur so, dass Dinge wie jakobianische Matrizen, die ins Bild kommen, nicht mehr intuitiv sind.

Nach meiner Erfahrung haben einfache Impulse zur Lösung von Kollisionen zu zufriedenstellenden Ergebnissen geführt.

Mein Anliegen ist also: Was verliere ich, wenn ich keine Einschränkungen nutze? Welche Situationen können von Einschränkungen profitieren? Vielleicht einige komplizierte Objekte mit Gelenken unter inverser Kinematik zum Beispiel?

Zum Beispiel: http://twvideo01.ubm-us.net/o1/vault/gdc09/slides/04-GDC09_Catto_Erin_Solver.pdf und http://www.bulletphysics.com/ftp/pub/test/physics/papers/IterativeDynamics .pdf

tupcuhamdi
quelle

Antworten:

1

Wenn Sie in Cattos Notizen nachlesen, dass Sie den Link zu der Stelle gepostet haben, an der er über die Verwendung eines iterativen Lösers spricht, der auf Impulsen basiert, ist dies in der Praxis wahrscheinlich nicht viel anders als das, was Sie möglicherweise tun, wie Sie sagen: "Einfach anwenden." Impulse zur Lösung von Kollisionen ". Obwohl der Jacobian wie eine komplizierte mathematische Idee klingt, ist es in Wirklichkeit nur eine Reihe von Vektoren, mit denen Sie 1) messen können, ob die Bedingung erfüllt ist, und 2) Ihnen die effizientesten Anweisungen zum Anwenden von Impulsen geben, um die Bedingung zu erfüllen . Wenn Sie bereits Impulse anwenden, um eine Einschränkung zu erfüllen, tun Sie wahrscheinlich etwas Ähnliches oder sogar Äquivalentes, ohne sich dessen bewusst zu sein.

Wenn es um dreidimensionale starre Körper und mehrdimensionale Einschränkungen wie Scharniere geht, bietet die jakobische Mathematik einen Rahmen, um die Einschränkung der linearen und Winkelgeschwindigkeiten auszudrücken und sowohl lineare als auch Winkelimpulse abzuleiten, um die Einschränkungen zu lösen. Es bietet auch eine Möglichkeit, alle Einschränkungen zusammen zu werfen (z. B. für eine Sammlung von Körpern mit vielen Einschränkungen) und sie gleichzeitig zu lösen. In der Praxis und insbesondere in Spielen tendieren wir jedoch dazu, iterative Löser zu verwenden, die mehr oder weniger eine ausgefallene Methode sind, um hier und dort einen kleinen Impuls zu geben, und so weiter, bis alles genau richtig ist.

Wenn Sie sagen, dass Sie "einfache Impulse anwenden, um Kollisionen aufzulösen", bedeutet dies möglicherweise, dass Sie die Position einschränken, aber nicht die Geschwindigkeiten einschränken? Ein solcher Ansatz kann in einigen Kontexten funktionieren, impliziert jedoch, dass Sie nur dann Impulse anwenden, wenn die Objekte eindringen? Wie wäre es, wenn ein Objekt unter dem Einfluss der Schwerkraft auf einer Oberfläche ruht? Ein Beschränkungslöser, der mit einer Geschwindigkeits- oder Beschleunigungsbeschränkung arbeitet, zeigt Ihnen die geeigneten und korrekten Kräfte an den Kontaktpunkten an, die es Ihnen ermöglichen, die richtige Reibung und dergleichen auszuführen, wohingegen eine Beschränkung nur auf Positionsebene zu Schwingungskräften führt, die schwingen und viel stärker sind instabil bei Änderungen der Bildrate. Z.B, Wenn Sie eine Positionsbeschränkung haben, bei der der Impuls proportional zur Penetrationsmenge ist, wird das Gleichgewicht nur an einer bestimmten Stelle erreicht, an der sich die Schwerkraft und der Beschränkungsimpuls gegenseitig aufheben. Das mag ein weiterer kritischer Unterschied zwischen Ihrem Ansatz und einem auf Einschränkungen basierenden Ansatz sein, aber es ist schwer zu sagen, ohne Ihren Algorithmus und Ihre Problemdomäne zu kennen (2D-Partikel in einer Meteorsimulation im Weltraum? 3D-Simulation eines menschlichen Körpers in einer Autounfallsimulation ?)

hässlicher Kojote
quelle
4

Das klassische Beispiel für ein eingeschränktes System ist ein Pendel. Unter der Annahme, dass das Seil des Pendels unter Spannung steht, ist die Position des Pendelbocks auf einen Kreis beschränkt. Sie können dieses System mithilfe der Newtonschen Gesetze simulieren, dh um die Schwerkraft und die Kraft zu simulieren, die das Seil auf den Bob ausübt. Das Problem bei diesem Ansatz ist jedoch, dass die Simulation komplizierter ist und der Bob aufgrund von Fehlerrunden während der Simulation den Kreis verlassen kann.

Beide Probleme verschwinden, wenn Sie ein eingeschränktes System verwenden. Sie müssen sich nicht mit Zwangskräften auseinandersetzen und Ihre Simulation erfüllt garantiert immer die Zwänge.

H. Rittich
quelle
2

Zusätzlich zu den anderen guten Antworten oben spart eine häufige Verwendung von Einschränkungen für Physiksimulationen Energie. Wie für die Beschränkung der Kreisbewegung eines Pendels erwähnt, ist es möglich, dass ein Rundungsfehler einen Löser von der bekannten korrekten Konfiguration des Systems abbringen kann. Wenn Sie wissen, dass Energie gespart werden sollte, kann diese Einschränkung sicherstellen, dass Sie nicht versehentlich magische Energie aus dem Nichts erhalten. Inverse Kinematik ist ein weiteres gutes Beispiel.

Das heißt, es hängt wirklich von Ihrem Anwendungsfall ab, den Sie nicht ausgearbeitet haben. Nach meiner Erfahrung ist dies normalerweise kein Problem, es sei denn, Sie haben unglaublich schlecht konditionierte Systeme, die kleine Fehler im Laufe der Zeit verschlimmern und sie zurückmelden, um größere Fehler zu erzeugen (denken Sie an den Schmetterlingseffekt der Chaostheorie). Ich bezweifle, dass Ihre durchschnittliche Spielmechanik sich mit auf Einschränkungen basierenden Lösern beschäftigt, es sei denn, sie benötigen eine hohe Präzision detaillierter kinematischer Interaktionen. Diese Löser sind viel ausgefeilter zu schreiben und korrekt einzurichten, wie Sie aus der gesamten Mathematik ersehen können.

Fazit: Wenn Sie nicht den Verdacht haben, dass durch die Einrichtung Ihrer mechanischen Systeme Wahnsinn auf QWOP-Ebene entstehen könnte, fügen Sie Ihrem System einfach genügend Dämpfung und ausreichend kleine Schrittgrößen hinzu, und Sie werden wahrscheinlich mit normalen Lösern zurechtkommen.

Bonus: Ein billiger Hack, wenn Sie sich Gedanken über die numerische Stabilität in Ihrem Fall machen, aber nicht über die wissenschaftliche Präzision (dies ist schließlich ein Spiel), besteht darin, dass regelmäßig kleine Einschränkungen / Erhaltungskorrekturen vorgenommen werden können, die visuell nicht erkennbar sind, aber erhalten bleiben Dinge überprüfen, ob der Fehler eine Toleranz überschreitet. Oder fügen Sie einige Hacky-Checks für die Berechnung von Kräften hinzu und stellen Sie sicher, dass sie keine extreme Schwelle durch Division durch Zahlen nahe Null überschreiten (z. B. aufgrund einer schlechten Genauigkeit bei einer Subtraktion im Nenner).

Für den Kontext habe ich einen Doktortitel in angewandter Mathematik und ein eigenes Löser- / Simulationspaket für Wissenschaftler entwickelt.

RHC
quelle
Vielen Dank für die tolle Antwort. Ja, Sie haben Recht, wenn Sie davon ausgehen, dass mir die numerische Stabilität und die Energieeinsparung nicht besonders wichtig sind.
Tupcuhamdi
1

Ich bin kein Experte für dieses Thema, aber ich habe die Präsentation gelesen und das Papier übersprungen.

Wie Rittich sagte, können Sie die Newtonschen Impulsberechnungen auf ein System von Pendeln anwenden, die durch Einschränkungen miteinander gepaart sind. In diesem Fall müssten Sie die Kraft, die auf das innere Pendel wirkt, dann das äußere Pendel und die Kräfte zwischen ihnen separat berechnen. Dieses Problem wird nur umso größer, je mehr Körper miteinander interagieren können, beispielsweise ein n-Element-Pendel.

Mit dem auf Einschränkungen basierenden Löser haben Sie Informationen für einen Körper erhalten, der aus mehreren Einschränkungen besteht, die über numerische Berechnungen gelöst werden können. Das heißt, anstatt die genaue Position jedes Mal zu berechnen, wenn eine Kraft auf die Kontraine wirkt, können Sie iterative Berechnungen verwenden, um die Ergebnisse zu approximieren.

Die Annäherung klingt problematisch, ist jedoch in den meisten Fällen nach einigen iterativen Schritten nicht erkennbar.

PSquall
quelle