Técnicas de Detección de Colisión de Motor de Física Continua

Question

Estoy trabajando en un motor de física puramente continuo, y tengo que elegir algoritmos para la detección de colisiones de fase amplia y estrecha. "Puramente continuo" significa que nunca hago pruebas de intersección, sino que quiero encontrar formas de detectar cada colisión antes de que suceda, y poner cada una en la pila de "colisiones planificadas" ordenadas por TOI.

Amplio Fase El único método en fase continua amplio que puedo pensar es que encierra cada cuerpo en un círculo y probar si cada círculo volverá a superponerse otra. Sin embargo, esto parece terriblemente ineficiente y carece de cualquier sacrificio.

No tengo idea de qué análogos continuos pueden existir para los métodos discretos de eliminación de colisiones de hoy en día, como los árboles cuádruples. ¿Cómo puedo evitar las pruebas anómalas inapropiadas e inútiles, como lo hace un motor discreto?

Fase estrecha
he conseguido adaptar el estrecho SAT a una verificación continua más que discreta, pero estoy seguro de que hay otros algoritmos mejores por ahí en los documentos o de los sitios que ustedes podrían haber llegado a través.
¿Qué algoritmos rápidos o precisos sugieres que use y cuáles son las ventajas/desventajas de cada uno?

Nota final:
digo técnicas y no algoritmos porque todavía no hemos decidido cómo voy a almacenar diferentes polígonos que podrían ser cóncavos, convexos, redondos, o incluso tener agujeros. Planeo tomar una decisión sobre esto en función de lo que el algoritmo requiere (por ejemplo, si elijo un algoritmo que descompone un polígono en triángulos o formas convexas, simplemente almacenaré los datos del polígono de esta forma).

Answer 1

Has dicho círculos, así que supongo que tienes objetos en 2D. Puede extender su objeto 2D (o sus formas delimitadoras) en 3D agregando una dimensión de tiempo, y luego puede usar las técnicas normales para verificar las colisiones estáticas entre un conjunto de objetos 3D.

Por ejemplo, si tiene un círculo en (x, y) moviéndose hacia la derecha (+ x) con velocidad constante, entonces, cuando amplía eso con una dimensión de tiempo, tiene un cilindro diagonal en (x, y, t). Al hacer las intersecciones entre estos objetos 3D (solo trata el tiempo como z), puedes ver si dos objetos alguna vez se cruzan. Si el punto P es un punto de intersección, entonces usted sabe la hora de esa intersección simplemente mirando P.t.

Esto también se generaliza en dimensiones más altas, aunque las matemáticas se ponen difíciles (para mí de todos modos).

La detección de colisiones puede ser difícil si los objetos tienen rutas complejas. Por ejemplo, si su círculo está influenciado por la gravedad, entonces el objeto de espacio-tiempo extruido es un barrido de esfera parabólica en lugar de un simple cilindro. Podría rellenar un poco los objetos delimitadores y usar aproximaciones lineales en períodos de tiempo más cortos e iterar, pero no estoy seguro si eso viola lo que quiere decir con continuo.

Answer 2

Voy a suponer que quieres cosas como la gravedad u otras fuerzas conservadoras en tu simulación. Si ese es el caso, es muy probable que las trayectorias de sus objetos no sean líneas, en cuyo caso, tal como advirtió Adrian, las matemáticas serán algo más difíciles.No puedo pensar en una forma de evitar el control de todas las combinaciones posibles de curvas para colisiones, pero puede calcular la distancia mínima entre dos curvas con bastante facilidad, siempre que ambas sean soluciones a sistemas lineales (o, en general, si tiene una solución de forma cerrada para las curvas). Si sabes que x1(t) = f(t) y x2(t) = g(t) lo que quieres es hacer es calcular la distancia ||x1(t) - x2(t)|| y establecer su derivada a cero. Esta debería ser una expresión que depende de f(t), g(t) y sus derivados y le dará un tiempo tmin (o tal vez algunos posibles) en el que luego evaluará la distancia y verificará si es mayor o menor que r1+r2 - - la suma de los radios de los dos círculos delimitadores. Si es más pequeño, entonces tiene una colisión potencial en ese momento por lo que ejecuta el algoritmo de fase estrecha.