Mejora de la simulación y el rendimiento con un solucionador físico avanzado
En 2016, añadimos compatibilidad con un conjunto variado de nuevas restricciones físicas, incentivando a los desarrolladores a migrar al nuevo solucionador y ampliando las capacidades creativas del motor físico. Cualquier lugar nuevo utilizaba el solucionador PGS por defecto, con la opción de volver al solucionador clásico.
Resolvimos algunos problemas de estabilidad asociados a grandes diferencias de masa y mecanismos complejos mediante la introducción del solucionador híbrido LDL-PGS a mediados de 2018. Esto dejó obsoleto al antiguo solucionador, que se desactivó por completo en 2019, migrando automáticamente todos los lugares al PGS.
En 2019, se mejoró aún más el rendimiento mediante el uso de multihilo, que divide la simulación en tareas compuestas por islas conectadas de piezas simuladas. Seguíamos teniendo problemas de rendimiento relacionados con el LDL que finalmente resolvimos a principios de 2020.
El motor físico sigue mejorándose y optimizándose para mejorar el rendimiento, y tenemos previsto añadir nuevas funciones en un futuro próximo.
Implementación de las leyes de la física
El objetivo principal de un motor físico es simular el movimiento de cuerpos en un entorno virtual. En nuestro motor físico, nos centramos en cuerpos rígidos que colisionan y tienen restricciones entre sí.
Un motor físico se organiza en dos fases: detección de colisiones y resolución. La detección de colisiones encuentra intersecciones entre las geometrías asociadas a los cuerpos rígidos, generando la información de colisión adecuada, como puntos de colisión, normales y profundidades de penetración. A continuación, un solucionador actualiza el movimiento de los cuerpos rígidos bajo la influencia de las colisiones detectadas y las restricciones proporcionadas por el usuario.
El movimiento es el resultado de la interpretación que hace el solucionador de las leyes de la física, como la conservación de la energía y el momento. Pero hacerlo con una precisión del 100 % resulta prohibitivamente caro, y el truco para simularlo en tiempo real consiste en realizar aproximaciones para aumentar el rendimiento, siempre y cuando el resultado sea físicamente realista. Siempre que las leyes básicas del movimiento se mantengan dentro de una tolerancia razonable, esta compensación es totalmente aceptable para la simulación de un videojuego.
Dando pequeños pasos
La idea principal del motor físico es discretizar el movimiento mediante pasos temporales. Las ecuaciones de movimiento de cuerpos rígidos con y sin restricciones son muy difíciles de integrar de forma directa y precisa. La discretización subdivide el movimiento en pequeños incrementos de tiempo, en los que las ecuaciones se simplifican y linealizan, lo que permite resolverlas de forma aproximada. Esto significa que, durante cada paso temporal, el movimiento de las partes relevantes de los cuerpos rígidos que están involucrados en una restricción se aproxima linealmente.
Aunque un problema linealizado es más fácil de resolver, produce una deriva en una simulación que contiene comportamientos no lineales, como el movimiento rotacional. Más adelante veremos métodos de mitigación que ayudan a reducir la deriva y hacen que la simulación sea más plausible.
Resolución
Esta animación muestra cómo un solucionador PGS cambia las posiciones de los cuerpos en cada paso del proceso de iteración, con el objetivo de encontrar las posiciones que respeten las restricciones de rótula y cavidad, al tiempo que se conserva el centro de masa en cada paso (este es un tipo de solucionador posicional utilizado por el arrastrador IK). Aunque este ejemplo tiene una solución analítica sencilla, es una buena demostración de la idea que subyace al PGS. En cada paso, el solucionador fija una de las restricciones y permite que se incumpla la otra. Tras unas cuantas iteraciones, los cuerpos se encuentran muy cerca de sus posiciones correctas. Una característica de este método es cómo algunos cuerpos rígidos parecen vibrar alrededor de su posición final, especialmente al acoplar interacciones con cuerpos más pesados. Si no realizamos suficientes iteraciones, la parte amarilla podría quedar en un estado visiblemente inválido en el que una de sus dos restricciones se incumple de forma drástica. Esto se denomina problema de alta relación de masas y ha sido la pesadilla de los motores físicos, ya que provoca inestabilidades y explosiones. Si realizamos demasiadas iteraciones, el solucionador se vuelve demasiado lento; si no lo hacemos, se vuelve inestable. Equilibrar ambos aspectos ha sido un proceso largo y arduo.
Estrategias de mitigación
Un solucionador tiene dos fuentes principales de imprecisiones: el paso de tiempo y la resolución iterativa (también existe la deriva de coma flotante, pero es menor en comparación con las dos primeras). Estas imprecisiones introducen errores en la simulación que hacen que se desvíe de la trayectoria correcta. Parte de esta desviación es tolerable, como velocidades ligeramente diferentes o pérdida de energía, pero otra parte no lo es, como las inestabilidades, las grandes ganancias de energía o las restricciones desalineadas.
Por lo tanto, gran parte de la complejidad del solucionador proviene de la implementación de métodos para minimizar el impacto de las imprecisiones computacionales. Nuestra implementación final utiliza algunas estrategias de mitigación tradicionales y otras novedosas:
- Inicio en caliente: comenzar con la solución de un paso de tiempo anterior para aumentar la tasa de convergencia del solucionador iterativo
- Postestabilización: reproyectar el sistema de vuelta a la variedad de restricciones para evitar la deriva de las restricciones
- Regularización: añadir cumplimiento a las restricciones para garantizar que existe una solución y que esta es única
- Precondicionamiento: uso de una solución exacta para un subsistema lineal, lo que mejora la estabilidad de los mecanismos complejos
Las estrategias 1, 2 y 3 son bastante tradicionales, pero la 3 ha sido mejorada y perfeccionada por nosotros. Además, aunque la 4 no es desconocida, no hemos visto ninguna implementación práctica de la misma. Utilizamos un método de factorización original para matrices de restricciones dispersas de gran tamaño y una nueva forma eficiente de combinarlo con el PGS. La implementación resultante es solo ligeramente más lenta en comparación con el PGS puro, pero garantiza que el sistema lineal derivado de las restricciones de igualdad se resuelva con exactitud. En consecuencia, las restricciones de igualdad solo sufren la deriva derivada de la discretización del tiempo. Los detalles sobre nuestros métodos se recogen en mi presentación en la GDC 2020. Actualmente, estamos investigando métodos directos aplicados a restricciones de desigualdad y colisiones.
Más detalles
Tradicionalmente, existen dos modelos matemáticos para los mecanismos articulados: los métodos de coordenadas reducidas, impulsados por Featherstone, que parametrizan los grados de libertad en cada articulación, y los métodos de coordenadas completas que utilizan una formulación lagrangiana.
Utilizamos la segunda formulación, ya que es menos restrictiva y requiere una matemática y una implementación mucho más sencillas.
El motor de Roblox utiliza métodos analíticos para calcular la respuesta dinámica de las restricciones, a diferencia de los métodos de penalización que se utilizaban anteriormente. Los métodos analíticos se introdujeron inicialmente en Baraff 1989, donde se utilizan para tratar tanto las restricciones de igualdad como las de no igualdad de manera coherente. Baraff observó que el modelo de contacto puede formularse utilizando programación cuadrática, y proporcionó un método de solución heurístico (que no es el método que utilizamos en nuestro solucionador).
En lugar de utilizar una formulación basada en la fuerza, utilizamos una formulación basada en impulsos en el espacio de velocidades, introducida originalmente por Mirtich-Canny en 1995 y mejorada posteriormente por Stewart-Trinkle en 1996, que unifica el tratamiento de los diferentes tipos de contacto y garantiza la existencia de una solución para contactos con fricción. En cada paso de tiempo, las restricciones y las colisiones se mantienen aplicando cambios instantáneos en las velocidades debidos a impulsos de restricción. En la presentación de Catto de 2014 en la GDC se ofrece una excelente explicación de por qué la simulación basada en impulsos es superior.
Los contactos sin fricción se modelan utilizando un problema de complementariedad lineal (LCP), tal y como se describe en Baraff (1994). La fricción se añade como una proyección no lineal sobre el cono de fricción, intercalada con las iteraciones del método de Gauss-Seidel proyectado.
La deriva numérica que introduce errores de posición en las restricciones se resuelve mediante una técnica de postestabilización que utiliza pseudovelocidades introducida por Cline-Pai 2003. Implica resolver un segundo LCP en el espacio de posiciones, que proyecta el sistema de vuelta a la variedad de restricciones.
Los LCP se resuelven utilizando un PGS / Impulse Solver popularizado por Catto 2005 (véase también Catto 2009). Este método es iterativo y considera cada restricción individual en secuencia, resolviéndola de forma independiente. Tras muchas iteraciones, y en condiciones ideales, el sistema converge hacia una solución global.
Además, los problemas de alta relación de masas en las restricciones de igualdad se resuelven precondicionando el PGS mediante la descomposición LDL dispersa de la matriz de restricciones de igualdad. Las submatrices densas de la matriz de restricciones se dispersan utilizando un método que denominamos «Body Splitting». Este es similar a la descomposición LDL utilizada en Baraff 1996, pero permite sistemas mecánicos más generales y resuelve el sistema en el espacio de restricciones. Para más información, puede consultar mi presentación en la GDC 2020.
La arquitectura de nuestro solucionador sigue la idea de Guendelman-Bridson-Fedkiw, en la que los pasos de velocidad y posición están separados por la resolución de restricciones. Nuestra secuencia temporal es:
- Avance de velocidades
- Resolución de restricciones en el espacio de velocidad y en el espacio de posición
- Avance de posiciones
Este esquema tiene la ventaja de integrar solo velocidades válidas y limitar la latencia en la aplicación de fuerzas externas, pero permitiendo una pequeña cantidad de violación de restricciones percibida debido a la deriva numérica.
Una referencia excelente para la simulación de cuerpos rígidos es el libro de Erleben de 2005, que recientemente se ha puesto a disposición de forma gratuita. Puedes encontrar conferencias en línea sobre animación basada en la física, un blog de Nilson Souto sobre la creación de un motor físico, una presentación muy buena de Erin Catto en la GDC sobre métodos modernos de resolución de ecuaciones, y foros como el Bullet Physics Forum y GameDev, que son lugares excelentes para hacer preguntas.
En conclusión
El campo de la simulación de la física en los videojuegos presenta muchos problemas interesantes que son a la vez emocionantes y desafiantes. Existen oportunidades para aprender una cantidad considerable de matemáticas y física interesantes y para utilizar técnicas modernas de optimización. Es un área del desarrollo de videojuegos que combina estrechamente las matemáticas, la física y la ingeniería de software.
Aunque Roblox cuenta con un buen motor de física de cuerpos rígidos, hay áreas en las que se puede mejorar y optimizar. Además, estamos trabajando en nuevos y emocionantes proyectos como la fracturación, la deformación, los cuerpos blandos, la simulación de telas, la aerodinámica y la simulación del agua.
Ni Roblox Corporation ni este blog respaldan ni apoyan a ninguna empresa o servicio. Asimismo, no se ofrecen garantías ni promesas respecto a la exactitud, fiabilidad o exhaustividad de la información contenida en este blog.
Esta entrada del blog se publicó originalmente en el blog técnico de Roblox.
