Respuesta de colisión del juego 2D: ¿SAT y desplazamiento mínimo a lo largo de un eje dado?

Estoy tratando de implementar un sistema de colisión en un juego 2D que estoy haciendo. El teorema del eje de separación (como se describe en el tutorial de colisión de metanet ) parece una forma eficiente y robusta de manejar la detección de colisión, pero no me gusta el método de respuesta de colisión que utilizan. Al desplazarse ciegamente a lo largo del eje de menor superposición, el algoritmo simplemente ignora la posición anterior del objeto en movimiento, lo que significa que no choca con el objeto estacionario tanto como entra y luego rebota.

Aquí hay un ejemplo de una situación en la que esto sería importante:

De acuerdo con el método SAT descrito anteriormente, el rectángulo simplemente saldría del triángulo perpendicular a su hipotenusa:

Sin embargo, de manera realista, el rectángulo debe detenerse en la esquina inferior derecha del triángulo, ya que ese sería el punto de la primera colisión si se moviera continuamente a lo largo de su vector de desplazamiento:

Ahora, esto podría no importar realmente durante el juego, pero me encantaría saber si hay una manera de lograr de manera eficiente y generalmente desplazamientos precisos de esta manera. ¡Me he estado estrujando el cerebro durante los últimos días, y aún no quiero rendirme!

(Publicación cruzada de StackOverflow, ¡espero que eso no esté en contra de las reglas!)

Aquí está el método que encontré. Puede ser defectuoso, pero aún no he encontrado ningún problema en mi análisis superficial. También funciona para polígonos arbitrarios con algunas modificaciones menores.

En las siguientes ilustraciones, el objeto azul se está moviendo y el objeto rojo está estacionario. Paso 1: Para cada polígono, encuentre los dos puntos más lejanos a lo largo de la proyección de ese polígono en la línea perpendicular al vector de movimiento. Paso 2: Divida cada polígono a lo largo de la línea que conecta estos puntos. La mitad del polígono que se enfrenta al otro polígono a lo largo del vector de movimiento es el "casco delantero". Esta es la única parte del polígono que posiblemente puede colisionar. Paso 3:Proyecte un vector desde cada punto en el "casco delantero" de cada polígono a lo largo del vector de movimiento hacia el polígono opuesto, y verifique la intersección con cada borde del "casco delantero" del polígono opuesto. (Posiblemente lento, pero las computadoras son bastante rápidas hoy en día, ¿verdad?) (Perdón por la flecha inclinada. Todas las flechas deben ser paralelas). Paso 4: Tome el vector más corto. Esta es la distancia exacta de colisión. Paso 5: ¡Voila!

Echa un vistazo a esta pregunta similar: resolución de colisión

Y también, desde http://www.metanetsoftware.com/technique/tutorialA.html#section5 (al cual publicó un enlace :))

SECCIÓN 5: Objetos de movimiento rápido

Como se mencionó anteriormente, los objetos pequeños y / o de rápido movimiento pueden producir problemas al usar una prueba de colisión estática. Hay varios enfoques que se pueden tomar para manejar tales objetos: el más simple es restringir el diseño de su juego para que dichos objetos no sean necesarios.

Si debe tenerlos absolutamente, existen dos métodos comunes para manejar objetos pequeños y / o de movimiento rápido: pruebas de colisión barrida y muestreo múltiple.

- = pruebas de barrido = -

En lugar de probar la intersección entre dos formas estáticas, podemos crear nuevas formas barriendo las formas originales a lo largo de su trayectoria y probando la superposición entre estas formas barridas.

La idea básica se describe en [Gómez], para las pruebas de barrido círculo-círculo y AABB-AABB.

- = multimuestreo = -

Una alternativa mucho más simple a las pruebas de barrido es la multimuestra; en lugar de realizar una única prueba estática en la nueva posición del objeto, realice varias pruebas en varias posiciones ubicadas entre la posición anterior y la nueva del objeto. Esta técnica se utilizó para colisionar con la muñeca de trapo en N.

Si se asegura de que las muestras siempre estén espaciadas a distancias inferiores al radio del objeto, esto producirá excelentes resultados. En nuestra implementación, limitamos el número máximo de muestras, por lo que velocidades muy altas a veces pueden causar problemas; Esto es algo que puede modificarse en función de su aplicación específica.

EDITAR

En resumen y AFAIK, hay algunas soluciones.

1. Limite su juego para que nunca tenga un objeto pequeño y / o de rápido movimiento que pueda causar esto.
2. Implemente un sistema que evite que ocurran colisiones, como se describe en el primer enlace que publiqué
3. Aumente su frecuencia de muestreo para objetos rápidos y / o pequeños en movimiento
4. ... posiblemente más, pero no soy un experto.

Depende si solo desea un movimiento lineal, o si también necesita hacer frente al movimiento angular.

Una alternativa al uso de SAT:

En el caso de lineal, solo puede emitir rayos contra la diferencia de Minkowski de los dos polígonos desde el origen en la dirección de la velocidad lineal delta de los objetos.

Si el rayo golpea el MD, los dos objetos colisionarán y el punto de golpe le indicará la hora t en que colisionaron.

Ahora, si los objetos se mueven y giran, se vuelve más difícil, pero aún puede usar una técnica similar. El avance conservador le permitirá lidiar con este caso. Esta técnica es iterativa; cada iteración generará un nuevo MD y lo acercará al momento de la intersección.

Aquí está el borrador original del documento sobre el avance conservador:

http://www.continuousphysics.com/BulletContinuousCollisionDetection.pdf

Escribí un artículo explicando la técnica en detalle aquí:

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

Espero que estos ayuden!