¿Cómo se prueba la colisión de dos cuadros de limitación orientados 2d en movimiento?

Question

Los OBB tienen una posición (x, y), una velocidad (x, y) y una orientación (Matriz). Dadas las actualizaciones periódicas, los OBB deben colisionar entre sí, devolviendo la fracción del movimiento que se consideró exitosa.

He examinado la prueba Polygon en GPWiki - http://gpwiki.org/index.php/Polygon_Collision - pero no tiene en cuenta los objetos en movimiento o un objeto que está completamente dentro de una OBB.

El libro Detección de colisiones en tiempo real cubre 3D OBB en el Capítulo 4: Volúmenes delimitados, pero el método para probar en 3 dimensiones es notablemente más complejo que en 2D.

Answer 1

Dice 2d, pero también menciona 3d como más complejo. Para la detección de colisiones, básicamente desea probar si dos formas se cruzan entre sí. En 2D, con cuadros delimitadores, estos son rectangles. Tendrá que usar un algoritmo para ver si los rectángulos se cruzan y también verificar si uno está completamente contenido dentro de otro (3 pruebas para el algoritmo simple). Para 3d, estos son cubos. La misma cosa. Mire este matrix de las intersecciones objeto-objeto y encuentre las que desee. Verifique la intersección de los objetos mismos, y también marchite uno está completamente contenido dentro del otro.

Este procedimiento puede extenderse no solo a los cuadros delimitadores, sino también a las speheres de delimitación oa los objetos reales en cáscaras convexas, polígonos u objetos 3D completos. El resultado final es, a medida que los objetos progresan a través del espacio y el tiempo, si sus superficies colisionan o si están dentro de la otra. En el caso donde su granularidad es demasiado gruesa y, en la situación que está modelando, deberían colisionar, pero terminan moviéndose uno al otro, debe hacer una prueba de intersección de un rayo adicional para ver si algún punto central ponderado en un el objeto se cruza con los límites del otro.

Answer 2

Si tiene dos cuadros delimitadores (es decir, rectángulos) con una orientación arbitraria (que supongo significa un poco de "rotación"), entonces me gustaría hacer lo siguiente:

• partir de una posición inicial (donde supongamos que los cuadros delimitadores no se intersecan), traduzca cada cuadro hacia adelante en función de su velocidad (sin embargo, está aplicando movimientos a lo largo del tiempo).
• Encuentra las coordenadas de las esquinas de cada cuadro delimitador traducido. Estas 4 coordenadas definen los puntos finales de los 4 segmentos de línea que forman los bordes del cuadro delimitador.
• Para el cuadro delimitador n. ° 1, pruebe una intersección entre cada uno de sus segmentos de línea y los cuatro segmentos de línea del cuadro delimitador n. ° 2. Puede hacerlo utilizando ecuaciones estándar para calcular el punto de intersección de dos líneas, como se describe en here, por ejemplo.
• Si hubo una intersección, determine la fracción de un movimiento que tuvo éxito usando las coordenadas de los puntos de intersección y la traducción conocida que aplicó.
• Repita los pasos anteriores para cada actualización.

EDIT: Un pseudocódigo en bruto (que incorpora lo que se discutió en los comentarios) se vería de la siguiente manera:

...test for intersections between the OBB edges... 
if any intersections are found{ 
    ...run code for when OBBs are partially overlapping... 
}else{ 
    P = line segment whose endpoints are the OBB centers; 
    ...test for intersections between P and OBB edges... 
    if P intersects edges of both OBBs{ 
     ...run code for when OBBs are not touching... 
    }else{ 
     ...run code for when one OBB is completely inside the other... 
    } 
} 

Answer 3

Para probar detección de colisiones entre los 2 cuadros delimitadores orientados, que haría uso de la separación de ejes teorema (SAT). De hecho, SAT se puede usar para detectar colisiones entre dos formas convexas. Esta técnica no es demasiado compleja de comprender y tiene un rendimiento razonable. El teorema se puede extender fácilmente a 3D.

EDIT:

El algoritmo intenta determinar es que es posible ajustar un plano entre dos objetos. Si tal plano existe, entonces el objeto está separado y no puede cruzarse. Para determinar si los objetos están separados, es simplemente una cuestión de proyectar los objetos en el plano normal, y comparar los intervalos y ver si se superponen.

Por lo tanto, obviamente hay un número infinito de planos que pueden caber entre dos objetos separados. Pero se ha demostrado que solo tienes que probar un puñado de aviones.

Se puede demostrar que, para las cajas, los planos de separación que se probarán son los planos con una normalidad igual a los ejes de ambas cajas. Entonces, para 2 cajas, solo necesita probar 4 planos de separación en total. De los 4 aviones, una vez que encontraste un plano de separación que separa las cajas, sabes que la caja no se puede cruzar, y devuelves una bandera de no colisión.

Si los 4 planos no pueden separar las cajas, entonces la caja debe ser una intersección, y allí tiene una colisión.

Answer 4

Otra sugerencia (que cubre la contención, y creo que es más barato):

Comprobar si cualquiera de los 4 vértices de # 1 están en el interior # 2, a continuación, comprobar si alguno de los 4 vértices de # 2 están en el interior # 1. Así es como sugeriría que fuera al respecto:

Supongamos que el vértice del # 1 que está comprobando es v, y los 4 vértices del # 2 son v1 ... v4. Giro inverso los 5 vértices por la orientación del # 2. (para girar inversamente un vector u por una matriz de orientación M, multiplicar u por M-transpuesto: M^T u, suponiendo que en tu convención la orientación funciona por multiplicación izquierda.) El 2 ° cuadro resultante, llámalo # 2 ' , ahora está alineado con el eje; puede verificar inmediatamente si v 'está contenido en él.

Si encontraste # 1-vertex dentro de # 2 - stop, tienes intersección. De lo contrario, continúe.

Algunas optimizaciones se me ocurren de inmediato (¿puede almacenar copias no giradas de los vértices en cada recuadro? Si los tamaños son fijos, tal vez pueda compararlos para eliminar inmediatamente una de las posibles contenciones, y guardar 3 posibles pruebas ?) pero a menos que lo esté aplicando en tropecientos millones de pares de cajas, esta prueba debería ser lo suficientemente barata como es.

En cuanto al movimiento, puede obtener la profundidad que desee allí: busque "colisión continua" y compruébelo usted mismo. (Recuerdo específicamente algunos buenos trabajos de Stephane Redon). Creo de todo corazón que ningún juego hace ninguna de estas cosas elegantes: si de hecho te estás moviendo extremadamente rápido, puedes subdividir tu paso de tiempo y realizar controles de colisión en cada sub-iteración de posición/orientación.

(editar :) Hubo otra discusión right here sobre eso, con buenas referencias.

Answer 5

Probablemente deba implementar un quadtree (vea wikipedia) para realizar un seguimiento de todos los objetos en el plano. Desafortunadamente, nunca he implementado uno para la detección de colisiones, pero parece que otros people han sido capaces de crear escenarios similares a los tuyos usando árboles cuádruples.