Pros y contras de diferentes integradores [cerrado]

29

Al crear cosas como la física en los juegos, necesitas un integrador. He visto que la integración de Verlet menciona varios lugares como una gran alternativa a la integración de Euler. Por ejemplo en el famoso documento de Thomas Jakobsen . Sin embargo, en este artículo Glenn Fiedler escribe:

En lugar de presentarle la amplia gama de integradores diferentes que existen, voy a ir al grano e ir directamente a lo mejor. Este integrador se llama Runge Kutta Order 4 Integrator, también conocido como RK4.

Así que aparentemente no hay bala de plata. ¿Cuáles son los pros y los contras de los diferentes integradores? Con respecto a la simplicidad, velocidad, precisión, estabilidad, etc. ¿Qué integradores son los más adecuados para qué tipo de juegos? ¿Cuándo usarías Verlet, RK4 u otros? ¿Alguna vez deberías usar Euler?

paldepind
fuente
Hay una respuesta SO que te apetece stackoverflow.com/questions/2769466/…
teodron
Gracias por el enlace. Aunque ya soy consciente de ello.
paldepind

Respuestas:

27

Pros y contras de ambos métodos:

RK4 Pros:

  1. precisión (gracias a su mejor serie de aproximación produce una precisión de cuarto orden)
  2. la amortiguación artificial / inducida inherentemente (un poco como lo hacen los métodos implícitos) agrega estabilidad (mientras que un simple paso de Euler no lo hace; en realidad hace lo contrario, al introducir energía fantasma que se acumula y podría hundir el sistema en el caos)

RK4 Contras:

  1. gasto de cómputo: aunque no es tan exigente en comparación con los métodos implícitos o los métodos híbridos IMEX, RK4 es 4 veces más costoso que el Euler explícito, ya que requiere muchas más evaluaciones de funciones. Esto se muestra cuando se apunta a la vanguardia de la optimización.
  2. aún inestable: dependiendo del tipo de fuerzas involucradas, RK4 puede ser tan inestable como Euler. En promedio, RK4 es un poco más estable y tiende a obtener este beneficio de sus "habilidades" de amortiguación.
  3. No simpléctico: la amortiguación numérica tiene un costo; no puede simular sistemas donde la energía / volumen / etc. la pérdida no debería aplicar un efecto visible a lo largo del tiempo (p. ej., dinámica molecular, fuerzas derivadas del campo potencial, problemas de variación)

Verlet Pros:

  1. una o dos veces la complejidad de un paso de Euler (dependiendo de su sabor Verlet: posición o velocidad).
  2. simpléctico: conserva la energía interna
  3. precisión de segundo orden: muchos juegos no requieren resultados de punto flotante de alta precisión, y el segundo orden es más que agradable a la vista en un escenario de juego (además: se usó en una simulación de escenario que no es de juego cuando se "descubrió", por lo que No está tan mal)

Verlet Contras:

  1. estable, pero aún así: probablemente el mejor método explícito en términos de estabilidad. Tiende a ganar ventaja cuando se agregan restricciones duras al sistema, lo que permite menos dolores de cabeza al implementar restricciones proyectadas en motores de dinámica basados ​​en la posición. Se pone en marcha al infinito si el sistema se perturba con grandes fuerzas externas y no se agrega amortiguación / fricción. Aun así, hay ciertos límites impuestos numéricamente sobre cuán grandes pueden ser las fuerzas internas (de resorte), pero en promedio son más altos que lo que RK4 puede hacer.
  2. menor precisión: no es útil si desea estimaciones de alta precisión
  3. requiere, en promedio, pasos de tiempo más pequeños que RK4 para algunas simulaciones (RK4 se beneficia tanto de su precisión como de la amortiguación interna)

Usar uno sobre el otro depende del escenario. Si la rigidez y las grandes fuerzas externas y las energías virtuales son un problema, considere otros métodos que tengan la palabra "implícita" en su descripción / título.


Tenga en cuenta que algunos autores / libros usan el término Euler semi-implícito para un integrador de Euler explícito real llamado método de Euler simpléctico (o Euler Cromer) del cual Verlet se deriva realmente. Verlet también es llamado por algunas personas como el "método leapfrog". Velocity Verlet y el método del punto medio son bastante similares ya que una estimación en un paso de tiempo det + 0.5*dtse requiere para un paso tipo predictor-corrector. Los métodos IMEX (implícito-explícito) también se utilizan para nombrar dos enfoques similares pero no idénticos: separe los cálculos en partes rígidas y no rígidas y use diferentes integradores en ellos (el explícito para no rígido, implícito para rígido) O resuelva la velocidad con un paso de actualización implícito y actualizar la posición de manera explícita (este es un método híbrido semi-implícito que cae en la clase de métodos IMEX porque las partes rígidas afectan más al cálculo de la aceleración). Los métodos implícitos son más engorrosos y requieren resolver un sistema de ecuaciones no lineales simultáneas para toda la configuración. Los métodos implícitos se usan para cuerpos deformables y generalmente no se usan para cuerpos rígidos desacoplados.

Como se indicó en uno de los comentarios, si puede, no use Euler. Utilice el método del punto medio, el Euler semi-implícito o, al mismo costo, la posición-Verlet. Todos ellos tienen una precisión ligeramente mayor y sensiblemente más estabilidad que el integrador explícito de Euler.

Lectura recomendada de mini comparación:

http://wiki.vdrift.net/Numerical_Integration

Gabriel Conrad
fuente
Una observación: ambas variantes de Verlet se pueden codificar para evaluar la aceleración solo una vez por actualización de cuadro.
teodron
1
¡Gracias por la respuesta! Más o menos lo que estaba buscando.
paldepind
3

Las implementaciones de Euler tienden a ser muy rápidas, pero mucho menos estables que las alternativas. Runge Kutta es más lento que Euler, pero mucho más preciso y estable.

No estoy muy bien informado sobre la integración de Verlet, así que no tengo idea de cómo se compara con Euler y Runge Kutta.

Si necesita que sus simulaciones sean más exactas, o incluso una prueba numérica, Runge Kutta es la mejor de las dos.

Si necesita física rápida y de bajo costo para un juego simple, Euler es la mejor opción.

Timothy Groote
fuente
2
Runge Kutta es MUCHO MÁS ESTABLE QUE EULER. Sigue siendo Euler, hecho 8 veces por fotograma en lugar de 1 (con un poco de predicción y corrección pero aún así ...) foros.evilmana.com/game-programming-theory/…
teodron
2
Depende de lo que necesites para ser 'estable'. quizás debería haber explicado, runge kutta es numéricamente más estable que euler. farside.ph.utexas.edu/teaching/329/lectures/node35.html
Timothy Groote
3
Por lo que puedo entender, no hay razón para que Verlet sea más lenta que Euler. Entonces, en comparación con Verlet, Euler no tiene ventaja de velocidad y sigue siendo mucho más preciso y más estable. Por lo tanto, creo que su afirmación de que Euler es mejor para una física rápida y simple es incorrecta.
paldepind
44
Aquí hay una publicación de
blog que
2
En el último nivel de Transformers (PS2, 2004), el modelo de vuelo que implementé utilizaba un integrador Euler que actualicé 2000 veces por cuadro. (Por supuesto, era un modelo de vuelo bastante realista que se aceleraba a velocidades supersónicas y se colocaba dentro de un campo de gravedad curvo, por lo que sus requisitos de estabilidad eran bastante intensos. Y no había mucho más CPU intensivo en ese nivel, así que Pude salirse con la suya). Lanzar iteraciones adicionales en Euler es a menudo mucho más fácil que cambiar a un iterador diferente.
Trevor Powell
1

En primer lugar, creo que debería usar Euler hasta que experimente una necesidad directa de usar un esquema de integración más avanzado. Es rápido y fácil de implementar.

Si experimenta problemas de estabilidad, como sistemas de resortes que nunca se detienen o si su simulación requiere un alto nivel de precisión, comience a experimentar con los demás.

Uno que no he visto mencionado anteriormente es el método de punto medio, que es muy fácil de implementar y solo requiere un paso de integración adicional.

Mikael Högström
fuente
1
Creo que Verlet es simplemente una aplicación simple y fácil de implementar
paldepind
Nunca lo he usado, pero por lo que entiendo es probable que tengas razón.
Mikael Högström