Modelado y resolución de restricciones físicas

UNA restricción es una restricción sobre un objeto modelado físicamente dentro de una simulación. En general, un objeto comienza con seis grados de libertad, representando su capacidad para moverse y girar dentro del mundo simulado; Al restringir estos grados de libertad de varias maneras, podemos lograr muchos efectos interesantes y atractivos.

A medida que la CPU de las computadoras modernas se vuelve más y más poderosa, los cálculos se pueden utilizar para modelar y resolver muchos escenarios físicos interesantes. Las restricciones son una forma generalizada y matemáticamente respaldada de producir tales escenarios. Todos podemos agradecer a Erin Catto por su documento inicial sobre este tema: Dinámicas iterativas con coherencia temporal. Usaré este documento como referencia al escribir este post, así que sugiero que al menos echen un vistazo antes de seguir leyendo, aunque solo sea por respeto al trabajo de Erin (y sus recursos enumerados y un agradecimiento especial a cada uno de sus colaboradores). ).


Glosario

Hay algunos términos diferentes que se usan comúnmente cuando se habla de motores físicos. Para mayor claridad, aquí hay un breve glosario para usar como referencia al leer este post:

  • Cuerpo rígido: Un objeto simulado dentro de un motor de física. Se asume que el objeto es completamente rígido, como un diamante. La mayoría de las veces, los cuerpos rígidos rebotan, se deslizan uno sobre el otro y conforman el mundo físico de un juego..
  • Grado de libertad: Uno de los seis valores escalares utilizados para representar la posición y orientación de un cuerpo rígido dentro del mundo. Tres valores escalares representan la posición, y tres representan la orientación.
  • Restricción: Una limitación colocada sobre uno o más grados de libertad de un cuerpo rígido. Casi todas las restricciones son por pares, lo que significa que afectan a dos cuerpos rígidos en tándem.
  • Articulación: Una unión es una restricción por pares, aunque el tipo de restricción es no una restricción de interpenetración. Todos los demás tipos de restricciones se conocen como una unión.
  • Restricción de contacto: Una restricción por pares que no es una unión, lo que significa que es una restricción de interpenetración.
  • Contacto normal: La dirección en la que se debe resolver una restricción de interpenetración. Esto suele ser determinado por la detección de colisión.

Prerrequisitos

Se requieren algunos requisitos previos para aprovechar al máximo este artículo. Sin embargo, el lector general todavía puede disfrutar mucho del material, aunque es mejor tener una comprensión básica de:

  • Álgebra
  • Cálculo
  • Calculo vectorial
  • Habilidades de programación intermedia a avanzada (para escribir el código)

Tipos de restricciones

Dado que una restricción limita los grados de libertad, veamos qué hace un cuerpo rígido cuando utiliza seis a la vez:


El cuerpo rígido anterior está usando tres grados de libertad para traducirse a través del mundo. Los últimos tres se utilizan para cambiar constantemente la orientación de los tres ejes de rotación..

Veamos ahora un par de ejemplos diferentes de lo que realmente son las restricciones. La restricción más familiar sería una que impida que dos cuerpos rígidos penetren. Este tipo de restricción solo está activa cuando dos cuerpos se penetran entre sí, y los separa. Una vez que esta restricción de interpenetración está activa, es fácil ver que los grados de libertad de los cuerpos rígidos se vuelven limitados y afectados de tal manera que producen un resultado interesante (el resultado interesante es que los dos objetos pueden chocar entre sí) ):


El Hola Mundo de las restricciones sería el restricción de distancia, donde dos puntos en dos cuerpos rígidos están obligados a estar a una distancia exacta entre sí. Puedes imaginar una varilla sin masa que conecta dos puntos, donde esta varilla no se puede estirar ni comprimir:


Existen muchos tipos de restricciones para todo tipo de comportamientos interesantes, que incluyen: fricción, prismático, revoluta, soldadura, ángulo y más.


Entendiendo las ecuaciones de restricción

En forma general, una restricción es una ecuación escalar igual a algún valor (generalmente cero).

\ begin equation
C (l_1, a_1, l_2, a_2) = 0
\ label eq1
\ end ecuación

Los términos \ (l \) y \ (a \) en \ eqref eq1 son mi propia notación: \ (l \) se refiere a lineal mientras que \ (a \) se refiere a angular. Los subíndices 1 y 2 se refieren a los dos objetos dentro de la restricción. Como puede ver, existen entradas lineales y angulares en una ecuación de restricción, y cada una debe ser un valor escalar.

Demos un paso atrás para ver la restricción de distancia. La restricción de distancia quiere que la distancia entre dos puntos de anclaje en dos cuerpos sea igual a algún valor escalar:

\ begin equation
C (l_1, a_1, l_2, a_2) = \ frac 1 2 [(P_2 - P_1) ^ 2 - L ^ 2] = 0
\ label eq2
\ end ecuación

\ (L \) es la longitud de la varilla que conecta ambos cuerpos; \ (P_1 \) y \ (P_2 \) son las posiciones de los dos cuerpos.

En su forma actual, esta restricción es una ecuación de posición. Este tipo de ecuación de posición no es lineal, lo que dificulta su resolución. Un método para resolver esta ecuación puede ser, en cambio, derivar la restricción de posición (con respecto al tiempo) y usar una restricción de velocidad. Las ecuaciones de velocidad resultantes son lineales, lo que las hace solubles. Las soluciones se pueden integrar usando algún tipo de integrador de nuevo en forma posicional.

En forma general, una restricción de velocidad es de la forma:

\ begin equation
\ punto C (l_1, a_1, l_2, a_2) = 0
\ label eq3
\ end ecuación

El punto encima de \ (C \) en \ eqref eq3 se refiere a la derivada de \ (C \) con respecto al tiempo. Esta es una notación común cuando se trata del estudio de la física..

Durante la derivada, aparece un nuevo término \ (J \) a través de la regla de la cadena:

\ begin equation
\ punto C (l_1, a_1, l_2, a_2) = JV = 0
\ label eq4
\ end ecuación

La derivada temporal de \ (C \) crea un vector de velocidad y un jacobiano. El jacobiano es una matriz 1x6 que contiene valores escalares correspondientes a cada grado de libertad. En una restricción de pares, un jacobiano normalmente contendrá 12 elementos (suficientes para contener los términos \ (l \) y \ (a \) para ambos cuerpos \ (A \) y \ (B \).

Un sistema de restricciones puede formar un articulación. Una junta puede contener muchas restricciones que restringen los grados de libertad de varias maneras. En este caso, el jacobiano será una matriz donde el número de filas es igual al número de restricciones activas en el sistema..

El jacobiano se deriva fuera de línea, a mano. Una vez que se adquiere un jacobiano, se puede crear un código para calcular y usar el jacobiano. Como puede ver en \ eqref eq4, la velocidad \ (V \) se transforma de espacio cartesiano a espacio de restricción. Esto es importante porque en el espacio de restricción se conoce el origen. De hecho, cualquier objetivo puede ser conocido. Esto significa que se puede derivar cualquier restricción para producir un jacobiano que pueda transformar fuerzas del espacio cartesiano para restringir el espacio.

En el espacio de restricción, dado un escalar objetivo, la ecuación puede moverse hacia o lejos del objetivo. Las soluciones se pueden obtener fácilmente en el espacio de restricción para mover el estado actual de un cuerpo rígido hacia un estado objetivo. Estas soluciones se pueden transformar del espacio restringido de nuevo en espacio cartesiano, de esta manera:

\ begin equation
F = \ lambda J ^ T
\ label eq5
\ end ecuación

\ (F \) es una fuerza en el espacio cartesiano, donde \ (J ^ T \) es el jacobiano inverso (transpuesto). \ (\ lambda \) (lambda) es un multiplicador escalar.

Piense en el jacobiano como un vector de velocidad, donde cada fila es un vector en sí mismo (de dos valores escalares en 2D y tres valores escalares en 3D):

\ begin equation
J = \ begin bmatrix
l_1 \\
a_1 \\
l_2 \\
a_2 \\
\ end bmatrix
\ label eq6
\ end ecuación

Multiplicar \ (V \) por \ (J \) matemáticamente implicaría la multiplicación de matrices. Sin embargo, la mayoría de los elementos son cero, y es por eso que tratamos al jacobiano como un vector. Esto nos permite definir nuestra propia operación para computar \ (JV \), como en \ eqref eq4.

\ begin equation
JV = \ begin bmatrix
l_1 & a_1 & l_2 & a_2
\ end bmatrix
\ begin bmatrix
v_1 \\
ω_1 \\
v_2 \\
ω_2 \\
\ end bmatrix
\ label eq7
\ end ecuación

Aquí, \ (v \) representa la velocidad lineal, y \ (ω \) (omega) representa la velocidad angular. \ eqref eq7 se puede escribir como algunos productos de puntos y multiplicaciones para proporcionar un cálculo más eficiente en comparación con la multiplicación de matriz completa:

\ begin equation
JV = l_1 \ cdot v_1 + a_1 \ cdot ω_1 + l_2 \ cdot v_2 + a_2 \ cdot ω_2
\ label eq8
\ end ecuación

El jacobiano puede considerarse como un vector de dirección en el espacio de restricción. Esta dirección siempre apunta hacia el objetivo en la dirección que requiere menos trabajo por hacer. Dado que esta "dirección" jacobiana se deriva fuera de línea, todo lo que debe resolverse es la magnitud de la fuerza que debe aplicarse para mantener la restricción. Esta magnitud se llama \ (\ lambda \). \ (\ lambda \) puede ser conocido como el multiplicador de Lagrange. Yo mismo no he estudiado formalmente la Mecánica Lagrangiana, sin embargo, no es necesario un estudio de la Mecánica Lagrangiana para simplemente implementar restricciones. (¡Soy una prueba de eso!) \ (\ Lambda \) se puede resolver usando un solucionador de restricciones (más sobre esto más adelante).


Resolviendo para los jacobianos

En el artículo de Erin Catto, existe un esquema simple para los jacobianos que derivan las manos. Los pasos son:

  1. Comience con la ecuación de restricción \ (C \)
  2. Derivado del tiempo de cómputo \ (\ dot C \)
  3. Aislar todos los términos de velocidad
  4. Identificar \ (J \) por inspección

La única parte difícil es calcular el derivado, y esto puede venir con la práctica. En general, las restricciones derivadas de las manos son difíciles, pero se hacen más fáciles con el tiempo.

Derivemos un jacobiano válido para usarlo en la resolución de una restricción de distancia. Podemos comenzar en el Paso 1 con \ eqref eq2. Aquí hay algunos detalles para el Paso 2:

\ begin equation
\ punto C = (P_2 - P_1) (\ punto P _2 - \ punto P _1)
\ label eq9
\ end ecuación

\ begin equation
\ punto C = (P_2 - P_1) ((v_2 + ω_2 \ times r_2) - (v_1 + ω_1 \ times r_1))
\ label eq10
\ end ecuación

\ (r_1 \) y \ (r_2 \) son vectores desde el centro de masa hasta el punto de anclaje, para los cuerpos 1 y 2 respectivamente.

El siguiente paso es aislar los términos de velocidad. Para ello, haremos uso de la identidad del producto triple escalar:

\ begin equation
(P_2 - P_1) = d
\ label eq11
\ end ecuación

\ begin equation
\ punto C = (d \ cdot v_2 + d \ cdot ω_2 \ veces r_2) - (d \ cdot v_1 + d \ cdot ω_1 \ veces r_1)
\ label eq12
\ end ecuación

\ begin equation
\ punto C = (d \ cdot v_2 + ω_2 \ cdot r_2 \ times d) - (d \ cdot v_1 + ω_1 \ cdot r_1 \ times d)
\ label eq13
\ end ecuación

El último paso es identificar al jacobiano por inspección. Para hacer esto, todos los coeficientes de todos los términos de velocidad (\ (V \) y \ (ω \)) se utilizarán como elementos jacobianos. Por lo tanto:

\ begin equation
J = \ begin bmatrix -d & -r_1 \ times d & d & r_2 \ times d \ end bmatrix
\ label eq14
\ end ecuación

Algunos mas jacobianos

Restricción de contacto (restricción de interpenetración), donde \ (n \) es el contacto normal:

\ begin equation
J = \ begin bmatrix -n & -r_1 \ times n & n & r_2 \ times n \ end bmatrix
\ label eq15
\ end ecuación

Restricción de fricción (activa durante la penetración), donde \ (t \) es un eje de fricción (2D tiene un eje, 3D tiene dos):

\ begin equation
J = \ begin bmatrix -t & -r_1 \ times t & t & r_2 \ times t \ end bmatrix
\ label eq16
\ end ecuación


Resolviendo restricciones

Ahora que entendemos qué es una restricción, podemos hablar sobre cómo resolverlos. Como se indicó anteriormente, una vez que un jacobiano se deriva de la mano, solo necesitamos resolver para \ (\ lambda \). Resolver una sola restricción de forma aislada es fácil, pero resolver muchas restricciones a la vez es difícil y muy ineficiente (computacional). Esto plantea un problema, ya que los juegos y simulaciones probablemente querrán tener muchas restricciones activas al mismo tiempo..

Un método alternativo para resolver todas las restricciones simultáneamente (resolver globalmente) sería resolver las restricciones de forma iterativa. Al resolver las aproximaciones de la solución y aplicar soluciones anteriores a las ecuaciones, podemos converger en la solución.

Uno de esos solucionadores iterativos se conoce como Impulsos secuenciales, como lo apodó Erin Catto. Sequential Impulses es muy similar a Projected Gauss Seidel. La idea es resolver todas las restricciones, una a la vez, varias veces. Las soluciones se invalidarán entre sí, pero a lo largo de muchas iteraciones, cada restricción individual convergerá y se podrá lograr una solución global. ¡Esto es bueno! Los solucionadores iterativos son rápidos.

Una vez que se logra una solución, se puede aplicar un impulso a ambos cuerpos en la restricción para hacer cumplir la restricción..

Para resolver una sola restricción, podemos usar la siguiente ecuación:

\ begin equation
\ lambda = \ frac - (JV + b) JM ^ - 1 J ^ T
\ label eq17
\ end ecuación

\ (M ^ - 1 \) es la masa de la restricción; \ (b \) es el sesgo (más sobre esto más adelante).

Esta es una matriz que contiene la masa inversa y la inercia inversa de ambos cuerpos rígidos en la restricción. La siguiente es la masa de la restricción; tenga en cuenta que \ (m ^ - 1 \) es la masa inversa de un cuerpo, mientras que \ (I ^ - 1 \) es la inercia inversa de un cuerpo:

\ begin equation M ^ - 1 =
\ begin bmatrix
m_1 ^ - 1 & 0 & 0 & 0 \\
0 & I_1 ^ - 1 & 0 & 0 \\
0 & 0 & m_2 ^ - 1 & 0 \\
0 & 0 & 0 & I_2 ​​^ - 1
\ end bmatrix
\ label eq18
\ end ecuación

Aunque \ (M ^ - 1 \) es teóricamente una matriz, por favor no la modele como tal (¡la mayoría es ceros!). En su lugar, sé inteligente sobre qué tipo de cálculos haces.

\ (JM ^ - 1 J ^ T \) se conoce como masa de restricción. Este término se calcula una vez y se usa para resolver para \ (\ lambda \). Lo calculamos para un sistema así:

\ begin equation
JM ^ - 1 J ^ T = (l_1 \ cdot l_1) * m_1 ^ - 1 + (l_2 \ cdot l_2) * m_2 ^ - 1 + a_1 * (I_1 ^ - 1 a_1) + a_2 * (I_2 ^ - 1 a_2)
\ label eq19
\ end ecuación

Tenga en cuenta que debe invertir \ eqref eq19 para calcular \ eqref eq17.

¡La información anterior es todo lo que se necesita para resolver una restricción! Una fuerza en el espacio cartesiano puede resolverse y usarse para actualizar la velocidad de un objeto, a fin de imponer una restricción. Por favor recuerde \ eqref eq5:

\ begin equation
F = \ lambda J ^ T \\
V_ final = V_ inicial + m ^ - 1 * F \\
∴ \\
\ begin bmatrix
v_1 \\
ω_1 \\
v_2 \\
ω_2 \\
\ end bmatrix + = \ begin bmatrix
m_1 ^ - 1 & 0 & 0 & 0 \\
0 & I_1 ^ - 1 & 0 & 0 \\
0 & 0 & m_2 ^ - 1 & 0 \\
0 & 0 & 0 & I_2 ​​^ - 1
\ end bmatrix \ begin bmatrix
\ lambda * l_1 \\
\ lambda * a_1 \\
\ lambda * l_2 \\
\ lambda * a_2 \\
\ end bmatrix
\ label eq20
\ end ecuación


Restricción de la deriva

Debido a la linealización de las ecuaciones de posición no lineales, se pierde cierta información. Esto da como resultado soluciones que no satisfacen completamente la ecuación de posición original, pero sí satisfacen las ecuaciones de velocidad. Este error se conoce como deriva de restricción. Uno puede pensar que este error es el resultado de una aproximación de línea tangente.

Hay algunas maneras diferentes de resolver tales errores, todos los cuales se aproximan al error y aplican alguna forma de corrección. El más simple se conoce como Baumgarte.

Baumgarte es una pequeña adición de energía en el espacio de restricción y representa el término \ (b \) en las ecuaciones anteriores. Para tener en cuenta el sesgo, aquí hay una versión modificada de \ eqref eq4:

\ begin equation
\ punto C = JV + b = 0
\ label eq21
\ end ecuación

Para calcular un término de Baumgarte y aplicarlo como un sesgo, debemos inspeccionar la ecuación de restricción original e identificar un método adecuado para calcular el error. Baumgarte está en la forma:

\ begin equation
JV = - \ beta C
\ label eq22
\ end ecuación

\ (\ beta \) (término Baumgarte) es un factor sintonizable, dependiente de la simulación, sin unidades. Por lo general es entre 0.1 y 0.3.

Para calcular el término de sesgo, veamos la ecuación para la restricción de no penetración \ eqref eq15 antes de derivar con respecto al tiempo, donde \ (n \) es el contacto normal:

\ begin equation
C = \ begin bmatrix -x_1 & -r_1 & x_2 & r_2 \ end bmatrix \ cdot \ vec n
\ label eq23
\ end ecuación

La ecuación anterior dice que el error escalar de \ (C \) es la profundidad de penetración entre dos cuerpos rígidos.


Conclusión

Gracias a Erin Catto y su artículo sobre resolución de restricciones, tenemos una manera de resolver las restricciones de posición en términos de velocidad. Muchos comportamientos interesantes pueden surgir de las restricciones, y es de esperar que el artículo sea de utilidad para muchas personas. Como siempre, no dude en hacer preguntas o hacer comentarios a continuación.

Consulte Box2D Lite para obtener un recurso sobre la resolución de varios tipos de restricciones 2D, así como información sobre muchos detalles de implementación que no se tratan aquí..