Source: http://bitybyte.angelluispg.es/2017/05/
Timestamp: 2020-02-29 05:35:08+00:00

Document:
mayo | 2017 | Bit y Byte
Resolución de colisiones mediante impulsos en ALPhysics
Posted on 30 mayo, 2017 by angelluis
Tengo pendiente desde hace ya bastante tiempo hacer una serie de artículos sobre motores gráficos y motores físicos, pero por falta de tiempo nunca he podido llevar a cabo dicho proyecto. Hoy he tenido un poco de tiempo y me he atrevido a publicar una entrada sobre resolución de colisiones en motores físicos de tiempo real, concretamente sobre la resolución de la velocidad en un sistema de resolución de colisiones.
Un motor físico en tiempo real es un programa informático que es capaz de hacer simulaciones físicas en tiempo real, estos motores al ser en tiempo real no son 100% precisos pero si que se puede obtener una precisión bastante alta. El uso típico de los motores físicos en tiempo real son los videojuegos y películas 3D.
El movimiento de los cuerpos en un videojuego tras una colisión, o cuando se encuentran en el aire y descienden debido a la fuerza de la gravedad, no son movimiento preestablecidos por los programadores, dichos movimientos son debidos a la acción de las fuerzas físicas sobre los cuerpos.
Un motor físico en tiempo real está formado típicamente por 3 subsistemas:
Resolutor de Colisiones
El detector de colisiones detecta que se ha producido una colisión, además de detectar si ha habido colisión o no, el detector de colisiones suele proporcionar una serie de datos que son importantes para el resolutor de colisiones, como por ejemplo:
El punto en donde se ha producido la colisión
La interpenetración que ha ocurrido entre los cuerpos en colisión
El coeficiente de restitución que afectará a la colisión
El coeficiente de fricción entre los cuerpos
La normal de la colisión. Esto hace referencia a la dirección en la que se ha producido la colisión.
Mencionar que el coeficiente de restitución es la cantidad del momento que se desea conservar después de la colisión. En una colisión totalmente elástica donde se tiene un coeficiente de restitución de 1, los objetos en colisión se alejan a la misma velocidad a la que se acercaban antes de la colisión. Por el contrario, una colisión inelástica tiene un coeficiente de restitución de 0. Tras la colisión los 2 cuerpos quedan juntos, sin separarse.
De los datos mencionados arriba que necesita el resolutor de colisiones hay uno que es artificial y no existe en la realidad, este es la interpenetración. Este dato informa sobre la distancia que un cuerpo ha interpenetrado en el segundo cuerpo. Esto en la realidad no pasa, dos cuerpos en colisión no sufren una interpenetración (lo que suele ocurrir a escalas microscópicas es que los 2 cuerpos en colisión se deforman, la cantidad de deformación que sufren los cuerpos tiene que ver con los materiales involucrados en la colisión). Sin embargo en una simulación por ordenador tenemos que la simulación se va realizando en pasos, si tenemos un sistema de 60 FPS estos pasos serán de 16,66 ms. Esto significa que los cálculos de las físicas (y también del renderizado 2D-3D) se hace de forma discreta cada 16,66ms pudiendo darse el caso de que en un momento determinado parte de un cuerpo haya penetrado en otro cuerpo. Este efecto se ve incrementado cuanto mayor sea la velocidad de los cuerpos en colisión, llegando incluso a ignorar la colisión si los cuerpos llevan mucha velocidad. Aquí entran en juego la detección continua de colisiones, pero ese es otro tema.
Como decia, el sistema detector de colisiones entrega una serie de datos al resolutor de colisiones, el resolutor de colisiones debe ser capaz de resolver la colisión con los datos que le ha entregado el detector de colisiones.
Por último, el sistema Integrador es el encargado de actualizar las variables físicas para actualizar los cuerpos. El integrador suele actualizar la velocidad lineal y angular, la posición y la orientación.
Como he dicho anteriormente en esta entrada me voy a centrar en el resolutor de colisiones. En el mundo real la interacción entre cuerpos a escala humana se rige por la mecánica Newtoniana, dicha mecánica se basa en 3 reglas
Un cuerpo sobre el que no actúa ninguna fuerza mantiene su estado indefinida, ya se encuentre en reposo o en movimiento.
La aceleración de un cuerpo es directamente proporcional a la fuerza que se le aplica e inversamente proporcional a la masa del cuerpo. Esta ley se resume en la famosa ecuación: .
Toda fuerza genera una fuerza de la misma intensidad pero en sentido contrario. Lo que se conoce como el principio de Acción-Reacción.
El movimiento de los cuerpos en la mecánica newtoniana es debido a las fuerzas. Las fuerzas son las que hacen que un cuerpo pase de reposo a movimiento y viceversa. Lo que provoca una fuerza es un cambio instantáneo en la aceleración de los cuerpos.
Para simplificar un poco las cosas en los resolutores de colisiones no se suele usar la fuerza para hacer los cálculos, sino que se suele usar el Impulso. El impulso se define como
El impulso provoca un cambio instantáneo en la velocidad. Análogamente a lo que hace una fuerza, que es un cambio instantáneo en la aceleración.
Los datos que necesita el resolutor de colisiones son:
La normal de la colisión.
Los puntos de colisión relativos a cada cuerpo .
La velocidad de los cuerpos que intervienen en la colisión.
El coeficiente de restitución.
Lo que tenemos que hacer es calcular la velocidad de separación de los cuerpos, en base a esta velocidad de separación y con el coeficiente de restitución calculamos la velocidad que tendrán los cuerpos después de la colisión. A continuación calculamos la cantidad de velocidad que le damos al cuerpo por cada unidad de impuso y por último dividimos la velocidad deseada entre la que se obtiene por unidad de impulso, después de este cálculo tendremos el impulso que se le debe dar a los cuerpos, lo único que resta es aplicar dicho impulso a los cuerpos.
Vamos a detallar el procedimiento anterior para que quede mucho más claro. Antes de empezar con el procedimiento detallado es necesario especificar que el sistema va a trabajar con sólidos rígidos (Rigid Body) que tienen tanto componente lineal (posición, velocidad lineal) como componente angular (rotación, velocidad angular).
Para llevar a cabo los cálculos de forma mas sencilla se ha creado una matriz de cambio de sistema de coordenadas, para pasar de las coordenadas del mundo a las coordenadas de la colisión y viceversa. Para crear esta matriz de cambio de sistema de coordenadas, se ha elegido la normal de la colisión como el eje X, y el eje Y se ha elegido como , por último, haciendo el producto vectorial obtenemos otro vector perpendicular a los anteriores. En este proceso es necesario tener en cuenta si el resultado del producto vectorial es 0, en ese caso tanto el vector normal del impulso que se ha elegido como eje X y el eje Y son paralelos y deberemos elegir otro eje Y.
La velocidad de un punto cualquiera en un Sólido Rígido viene dada por la ecuación
Como he dicho anteriormente primero tenemos que calcular la velocidad de separación entre los cuerpos, que es una velocidad relativa, y es calculada como
Si sustituimos y s=2$ obtenemos
Este cálculo se ha realizado en las coordenadas del mundo, para que todo nos resulte mas sencillo el cálculo del impulso se va a hacer en las coordenadas de la colisión, por tanto necesitamos pasar dicha velocidad de las coordenadas del mundo a las coordenadas de la colisión, para ello basta multiplicar por la matriz que he comentado antes de cambio de base, que es una matriz ortonormal.
Una vez que tenemos la velocidad de separación entre ambos cuerpos en coordinadas de la colisión podemos calcular el cambio en la velocidad que deben sufrir los cuerpos para alcanzar la velocidad deseada después de la colisión. Para ello usamos la siguiente ecuación
De esta forma tenemos que el incremento en la velocidad de separación es
Dejando esto más bonito obtenemos:
Recordemos que la restitución es el coeficiente que determina cuanto de elástica es una colisión. Un coeficiente de 1 hace que los cuerpos se separen con la misma velocidad con la que se acercaban, un coeficiente de 0.8 hace que la velocidad después del impacto sea un 80% la velocidad de antes del impacto.
Una vez que hemos calculado el cambio en la velocidad que queremos darle al cuerpo necesitamos hallar cuanto impulso es necesario darle para dar al cuerpo ese cambio en la velocidad.
Para ello tenemos que calcular primero el cambio que se produce en la velocidad cuando aplicamos un impulso unitario. Para ello tenemos que calcular el torque impulsivo que se produce por unidad de impulso. El torque impulsivo se define como
Que a diferencia del torque, , que es la capacidad que tiene una fuerza para producir un cambio de estado en la rotación del cuerpo y que se define como
El torque impulsivo es la cantidad de torque que se produce por el impulso aplicado.
El vector normal que nos proporciona el detector de colisiones puede ser considerado como un vector que actúa en la dirección del impulso y es un vector unitario, por tanto lo podemos usar como impulso unitario. De esta forma la ecuación anterior se queda así
Una vez calculado el torque impulsivo podemos calcular la variación en la velocidad angular debido a dicho torque impulsivo (y por tanto debido a un impulso unitario). La ecuación es la siguiente
Esto nos devuelve la cantidad de velocidad angular generada por una unidad de impulso en las coordenadas del mundo, pero necesitamos dicha cantidad en las coordenadas de la colisiones, en este caso basta con realizar el producto dot de y la normal de la colisión (recordemos que la normal la hemos elegido como eje X de la matriz del cambio de coordenadas).
es el tensor de inercia. El tensor de inercia es para el movimiento angular lo mismo que la masa para el movimiento lineal, es aquello que se opone al movimiento. El tensor de inercia en 3 dimensiones es una matriz calculada de una forma especial que se merecerá en un futuro un articulo dedicado a ella.
Si recordamos la ecuación de la velocidad de un punto en un cuerpo
podemos obtener la componente angular obviando la componente lineal
Con esto hemos calculado lo más difícil que es el cambio que se produce en el componente angular cuando aplicamos un impulso unitario. Ahora nos falta el cambio en el componente lineal que se produce a la hora de aplicar un impulso unitario.
Así de sencilla es, la inversa de la masa del cuerpo.
Si hubiese más de un cuerpo en la colisión habría que calcular el componente lineal y angular del segundo cuerpo y añadirlo a los del primero.
Si sumamos ambas componentes tenemos el cambio en velocidad que se produce por un impulso unitario.
Tenemos la cantidad de velocidad que debemos de dar a los cuerpos para que alcancen la velocidad deseada y tenemos la cantidad de velocidad que se produce por un impulso unitario. Con la siguiente ecuación obtenemos el impulso que le tenemos que dar a los cuerpos
Ya tenemos el impulso, ahora falta aplicarlo, para aplicarlo tenemos que aplicarlo a la componente lineal y a la componente angular por separado. La componente lineal es relativamente sencilla, antes hemos visto que
Como he dicho anteriormente el impulso es un cambio instantáneo en la velocidad, es decir, lo que queremos calcular es la nueva velocidad que van a tener los cuerpos, para ello despejamos quedando
El cambio en la velocidad angular, , es un poco más complejo. Básicamente debemos aplicar las ecuaciones que hemos aplicado antes para averiguar el cambio en la componente angular por unidad de impulso pero en vez de usar la normal como impulso para hacer los cálculos, debemos utilizar el impulso J calculado anteriormente.
Como antes primero calculamos el torque impulsivo generado por el impulso J
Ahora podemos calcular el cambio en la velocidad angular que genera dicho torque impulsivo
Con esto ya hemos calculado el cambio en el movimiento angular y en el movimiento lineal del cuerpo, basta sumar esas cantidades a la velocidad lineal y velocidad angular actual y tendremos la resolución del impulso.
Si en la colisión hubiese más de un cuerpo ahora necesitamos invertir el signo del impulso y aplicar los últimos cálculos al segundo cuerpo.
Un ejemplo de este algoritmo explicado aquí se puede ver en la siguiente demo:
http://angelluispg.es/AL3D/examples/Pendulum/
Nota: El sistema resolutor de colisiones suele es más complejo que lo mostrado aquí, dentro de un resolutor de resoluciones se lleva a cabo una resolución de la velocidad, que es lo que hemos hecho nosotros aquí, y una resolución de la interpenetración. Además estos algoritmos se aplican de forma iterativa, es decir, el algoritmo mostrado aquí solamente resuelve una colisión, el sistema debe recorrer todas las colisiones generadas y resolverlas, pero además es posible que se revisiten colisiones porque al resolver una colisión es posible que se genere otra nueva. Un buen sistema de resolución de colisiones debe ordenar las colisiones en función de la gravedad e ir resolviéndolas una a una y tener en cuenta si se producen nuevas.
Nota 1: Por lo general las colisiones siempre son entre 2 cuerpos pero en simulaciones en tiempo real a veces se da el caso de que solo interviene 1 cuerpo, aunque realmente intervengan 2. Esto sucede cuando un cuerpo dinámico, por ejemplo una pelota, colisiona con el suelo del escenario. En el mundo real esta colisión es tratada como una colisión entre 2 cuerpos, pero en una simulación en tiempo real si en la colisión interviene un cuerpo estático, que por lo general es representado como un cuerpo que tiene masa infinita, o cuya inversa de la masa es 0, se trata como una colisión de un solo cuerpo.
Posted in Games Graphics Physics
¿Por que Bit y Byte?
Posted on 28 mayo, 2017 by angelluis
Este tipo de entradas normalmente se redactan al poco tiempo de estar disponible el blog, y realmente esa era la idea, pero debido a la falta de tiempo que siempre padezco y a que simplemente es una curiosidad decidí dejarlo para más tarde, y aquí estoy ahora, publicando una entrada de porque el blog se llama Bit y Byte.
La razón de dicho nombre es realmente sencilla, desde siempre me ha interesado trabajar a bajo nivel con la máquina, entendiendo exactamente lo que hace cada cosa.
Recordando una pequeña anecdota que viene al caso recuerdo que con un compañero de facultad y con un profesor de Sistemas Operativos tuve una charla en la que defendía que no deberiamos usar la función "printf" del lenguaje de programación C (y por extensión porque no deberiamos usar ninguna función). Mi defensa se basaba siempremente en que no se debía usar algo que no se conocía y estoy seguro que más del 95% de ingenieros no saben como funciona la función "printf". Por tanto mi razonamiento era de crearnos nosotros mismos una función printf que supieramos como funciona y usar dicha función, y así con todos y cada una de las funciones.
Hoy día como Ingeniero en un mundo ideal con recursos ilimitados creo que tenía y tengo razón en dicho planteamiento. Ahora bien, como Ingeniero que se tiene que adaptar a un mundo con recursos limitados y tiempos de entrega creo que estaba equivocado. No podemos construir todo desde 0 si queremos avanzar.
Dejando de lado esta pequeña anécdota, cuando acabé la carrera tuve la suerte de caer en una empresa (y sigo en ella), Cuma Sistemas Electrónicos, donde he tocado temas de bajo nivel trabajando a nivel de bits, basicamente para ahorrar espacio en memoria, ya que trabajamos con microcontroladores donde la memoria es un bien escaso.
En Cuma se han diseñado formatos de ficheros propietarios, tanto de fuentes de letra como de video.
Y bueno, básicamente esta es la razón por la que el blog se llame Bit y Byte.

References: Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución