Detección de colisiones
La detección de colisiones es el problema computacional de detectar la intersección de dos o más objetos. La detección de colisiones es un tema clásico de la geometría computacional y tiene aplicaciones en varios campos de la computación, principalmente en gráficos por computadora , juegos de computadora, simulaciones por computadora , robótica y física computacional . Los algoritmos de detección de colisiones se pueden dividir en operaciones en objetos 2D y 3D. [1]
En la simulación física, se realizan experimentos, como jugar al billar . La física de las bolas de billar que rebotan se entiende bien, bajo el paraguas del movimiento de cuerpos rígidos y las colisiones elásticas . Se daría una descripción inicial de la situación, con una descripción física muy precisa de la mesa de billar y de las bolas, así como posiciones iniciales de todas las bolas. Dada una fuerza aplicada a la bola blanca (probablemente como resultado de que un jugador golpee la bola con su taco), queremos calcular las trayectorias, el movimiento preciso y los posibles lugares de descanso de todas las bolas con un programa de computadora .. Un programa para simular este juego constaría de varias partes, una de las cuales se encargaría de calcular los impactos precisos entre las bolas de billar. Este ejemplo particular también resulta estar mal condicionado : un pequeño error en cualquier cálculo provocará cambios drásticos en la posición final de las bolas de billar.
Los videojuegos tienen requisitos similares, con algunas diferencias cruciales. Si bien la simulación por computadora debe simular la física del mundo real con la mayor precisión posible, los juegos de computadora deben simular la física del mundo real de manera aceptable , en tiempo real y de manera sólida. Se permiten compromisos, siempre que la simulación resultante satisfaga a los jugadores del juego.
Los simuladores físicos difieren en la forma en que reaccionan ante una colisión. Algunos usan la suavidad del material para calcular una fuerza, que resolverá la colisión en los siguientes pasos de tiempo como es en la realidad. Debido a la baja suavidad de algunos materiales, esto requiere mucha CPU. Algunos simuladores estiman el tiempo de colisión por interpolación lineal , revierten la simulación y calculan la colisión por los métodos más abstractos de las leyes de conservación .
Algunos iteran la interpolación lineal ( método de Newton ) para calcular el tiempo de colisión con una precisión mucho mayor que el resto de la simulación. La detección de colisiones utiliza la coherencia de tiempo para permitir pasos de tiempo aún más finos sin aumentar mucho la demanda de la CPU, como en el control del tráfico aéreo .
Después de una colisión inelástica, pueden ocurrir estados especiales de deslizamiento y reposo y, por ejemplo, Open Dynamics Engine usa restricciones para simularlos. Las restricciones evitan la inercia y, por lo tanto, la inestabilidad. La implementación del descanso por medio de un escenario gráfico evita la deriva.
