Vor- und Nachteile verschiedener Integratoren [geschlossen]

Wenn Sie Dinge wie Physik in Spielen erstellen, benötigen Sie einen Integrator. Ich habe gesehen, dass die Verlet-Integration an mehreren Stellen eine großartige Alternative zur Euler-Integration ist. Zum Beispiel in dem berühmten Dokument von Thomas Jakobsen . In diesem Artikel schreibt Glenn Fiedler jedoch:

Anstatt Sie mit den zahlreichen verschiedenen Integratoren bekannt zu machen, gehe ich auf den Punkt und gehe direkt zu den Besten. Dieser Integrator wird als Runge Kutta Order 4-Integrator oder RK4 bezeichnet.

Es gibt also anscheinend keine Silberkugel. Was ist das Für und Wider der verschiedenen Integratoren? In Bezug auf Einfachheit, Geschwindigkeit, Genauigkeit, Stabilität usw. Welcher Integrator eignet sich am besten für welche Arten von Spielen? Wann würden Sie Verlet, RK4 oder andere verwenden? Sollten Sie jemals Euler verwenden?

Vor- und Nachteile beider Methoden:

RK4 Vorteile:

1. Genauigkeit (dank der besseren Approximationsreihe ergibt sich eine Genauigkeit 4. Ordnung)
2. künstliche / inhärent induzierte Dämpfung (ein bisschen wie implizite Methoden) erhöht die Stabilität (während ein einfacher Euler-Schritt das Gegenteil bewirkt und Geister-Energie einbringt, die sich aufbaut und das System ins Chaos stürzen könnte)

RK4 Nachteile:

1. Rechenaufwand: Obwohl RK4 im Vergleich zu impliziten Methoden oder hybriden IMEX-Methoden nicht besonders anspruchsvoll ist, ist es viermal teurer als das explizite Euler, da es wesentlich mehr Funktionsauswertungen erfordert. Dies zeigt sich, wenn auf die Blutungsgrenze der Optimierung abgezielt wird.
2. immer noch instabil: Je nach Art der Kräfte kann RK4 genauso instabil sein wie Euler. Im Durchschnitt ist RK4 etwas stabiler und zieht diesen Vorteil eher aus seinen "Fähigkeiten" als Dämpfer.
3. Nicht symplektisch: Numerische Dämpfung ist mit Kosten verbunden - Sie können keine Systeme simulieren, bei denen Energie / Volumen / usw. Verlust sollte keinen sichtbaren Effekt über die Zeit haben (z. B. Molekulardynamik, potenzielle feldabgeleitete Kräfte, Variationsprobleme)

Verlet Pros:

1. ein- oder zweimal so komplex wie ein Euler-Schritt (abhängig von Ihrem Verlet-Geschmack: Position oder Geschwindigkeit).
2. symplektisch: spart innere Energie
3. Genauigkeit zweiter Ordnung: Viele Spiele erfordern keine hochpräzisen Gleitkommaergebnisse, und die zweite Ordnung ist für das Auge in einem Spielszenario mehr als erfreulich ist doch nicht so schlimm)

Verlet Nachteile:

1. stabil, aber immer noch: wahrscheinlich die beste explizite Methode in Bezug auf Stabilität. Es gewinnt tendenziell den Vorteil, wenn dem System harte Einschränkungen hinzugefügt werden, wodurch weniger Kopfschmerzen bei der Implementierung von projizierten Einschränkungen in positionsbasierten Dynamik-Engines auftreten. Wenn das System durch große äußere Kräfte gestört wird und keine Dämpfung / Reibung hinzugefügt wird, setzt es sich ins Unendliche. Trotzdem gibt es bestimmte numerisch festgelegte Grenzen, wie groß die inneren (Feder-) Kräfte sein können, aber sie sind im Durchschnitt höher als das, was RK4 kann
2. Geringere Genauigkeit: Nicht nützlich, wenn Sie Schätzungen mit hoher Genauigkeit wünschen
3. erfordert für einige Simulationen im Durchschnitt kleinere Zeitschritte als RK4 (RK4 profitiert sowohl von seiner Genauigkeit als auch von seiner internen Dämpfung)

Die Verwendung von übereinander hängt vom jeweiligen Szenario ab. Wenn Steifheit und große externe Kräfte und virtuelle Energien ein Problem darstellen, sollten Sie andere Methoden in Betracht ziehen, deren Beschreibung / Titel das "implizite" Wort enthält.

Hinweis einige Autoren / Bücher den Begriff semi-impliziter Euler für einen tatsächlichen expliziten Euler-Integrator verwenden, der als symplektische Euler-Methode (oder Euler-Cromer) bezeichnet wird, von der Verlet tatsächlich abgeleitet ist. Verlet wird von manchen auch als "Bocksprung-Methode" bezeichnet. Velocity Verlet und die Mittelpunktmethode sind seit einer Schätzung in einem Zeitschritt von ziemlich ähnlicht + 0.5*dt ist für einen Predictor-Corrector-ähnlichen Schritt erforderlich. IMEX-Methoden (implizit-explizit) werden auch verwendet, um zwei ähnliche, aber nicht identische Ansätze zu benennen: Trennen Sie die Berechnungen in steife und nicht steife Teile und verwenden Sie unterschiedliche Integratoren (explizit für nicht steife, implizit für steife) ODER lösen Sie nach die Geschwindigkeit mit einem impliziten Aktualisierungsschritt und eine explizite Aktualisierung der Position (dies ist eine hybride halbimplizite Methode, die in die IMEX-Methodenklasse fällt, da die steifen Teile die Beschleunigungsberechnung am meisten beeinflussen). Implizite Methoden sind umständlicher und erfordern die Lösung eines Systems simultaner nichtlinearer Gleichungen für die gesamte Konfiguration. Implizite Methoden werden für deformierbare Körper verwendet und normalerweise nicht für entkoppelte starre Körper.

Wie in einem der Kommentare angegeben, sollten Sie Euler nicht verwenden, wenn Sie können. Verwenden Sie entweder die Midpoint-Methode, den semi-impliziten Euler oder auf die gleiche Kosten das Positions-Verlet. Alle haben eine etwas höhere Genauigkeit und deutlich mehr Stabilität als der explizite Euler-Integrator.

Empfohlene Mini-Vergleichslesung:

http://wiki.vdrift.net/Numerical_Integration

Euler-Implementierungen sind in der Regel sehr schnell, aber weit weniger stabil als die Alternativen. Runge Kutta ist langsamer als Euler, aber viel präziser und stabiler.

Ich bin nicht sehr gut informiert über die Verlet-Integration, daher habe ich keine Ahnung, wie sie sich gegen Euler und Runge Kutta schlägt.

Wenn Ihre Simulationen genauer oder sogar numerisch beweisbar sein müssen, ist Runge Kutta die bessere von beiden.

Wenn Sie eine schnelle und kostengünstige Physik für ein einfaches Spiel benötigen, ist Euler die bessere Wahl.

In erster Linie denke ich, dass Sie Euler verwenden sollten, bis Sie feststellen, dass ein fortgeschritteneres Integrationsschema erforderlich ist. Es ist schnell und einfach zu implementieren.

If you experience stability issues such as systems of springs that never come to rest or if your simulation requires a high level of accuracy then start experimenting with the others.

Eine, die ich oben nicht gesehen habe, ist die Midpoint-Methode, die sehr einfach zu implementieren ist und nur einen zusätzlichen Integrationsschritt erfordert.