¿Cuál es la forma más rápida de verificar si dos AABB en movimiento se cruzan?

12

Tengo dos AABB que se mueven, ¿cuál es la forma más rápida de verificar si se cruzan debajo de un marco?

Al moverme me refiero no solo a verificar con el método usual de intersección de rectángulos, me refiero a algún tipo de prueba de barrido simple y simple que solo devuelve un valor booleano, sin tiempo de acierto ni nada más.

Lo que creo es simplemente hacerlo así:

Esta

Pero ese hexágono es bastante complejo y no sé cómo calcular una intersección AABB - Polígono, ¿hay alguna manera más fácil?

Cualquier lenguaje de programación que más te guste, puedo portarlo fácilmente.

Gracias.

súper
fuente
3
Estoy confundido. Usted menciona específicamente la "prueba de barrido", ¿ha probado la típica prueba de barrido AABB? Hace exactamente lo que quieres.
SomeWritesReserved
1
Estoy de acuerdo con el comentario anterior: ¿qué tiene de malo la prueba "clásica"? Además, la mayoría de las soluciones propuestas aquí son claramente más lentas que eso ... además algunas de ellas pueden dar resultados incorrectos (no robustas).
wondra
Podrías probar la Prueba de Eje Separativo gamedevelopment.tutsplus.com/tutorials/…
Pharap

Respuestas:

8

Usa la suma de Minkowski

Una buena manera de resolver este problema es considerar la intersección entre una línea de movimiento ( v ) traducida al origen ( v ' ) y la suma de A de Minkowski girada 180 grados en el origen ( A' ) y sus obstáculos (solo B en este caso): a'B .

En la siguiente imagen coloco A smack-dab en el origen de un sistema de coordenadas arbitrario. Esto simplifica la comprensión ya que la rotación de A en 180 grados da como resultado A ' , y v traducida al origen es igual a v' .

La suma de Minkowski es el rectángulo verde, y los puntos de intersección de una A en movimiento y una B estacionaria se pueden encontrar haciendo la intersección línea-AABB . Estos puntos están marcados con los círculos azules.

Suma de Minkowski - caso degenerado

En la siguiente imagen se utilizó un origen diferente y se encuentran los mismos puntos de intersección.

Suma de Minkowski: caso más general

Múltiples AABB móviles

Para que esto funcione para dos AABB que se mueven de manera lineal durante un período específico de tiempo, restarías el vector de velocidad de B del vector de velocidad de A y lo usarías como el segmento de línea para la intersección línea-AABB.

Pseudocódigo

def normalize(aabb):
    return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2),
            y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2),

def rotate_about_origin(aabb):
    return normalize({x1: -aabb.x1, x2: -aabb.x2
                      y1: -aabb.y1, y2: -aabb.y2})

# given normalized aabb's
def minkowski_sum(aabb1, aabb2):
    return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2,
            y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2}

def get_line_segment_from_origin(v):
    return {x1: 0, y1: 0, x2: v.x, y2: v.y}

def moving_objects_with_aabb_intersection(object1, object2):
    A = object1.get_aabb()
    B = object2.get_aabb()

    # get A'⊕B
    rotated_A = rotate_about_origin(A)
    sum_aabb = minkowski_sum(rotated_A, B)

    # get v'
    total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity())
    line_segment = get_line_segment_from_origin(total_relative_velocity)

    # call your favorite line clipping algorithm
    return line_aabb_intersection(line_segment, sum_aabb)

Respuesta de colisión

Dependiendo de la jugabilidad, realizaría una detección de colisión más fina (tal vez las AABB contienen mallas) o avanzaría a la siguiente fase: respuesta de colisión.

Cuando hay una colisión, el algoritmo de intersección línea-AABB devolverá 1 o 2 puntos de intersección dependiendo de si A finaliza su movimiento dentro de B o lo atraviesa, respectivamente. (Esto es descontar los casos degenerados en los que A roza a B a lo largo de sus lados o en una de sus respectivas esquinas).

De cualquier manera, el primer punto de intersección a lo largo del segmento de línea es el punto de colisión, lo traduciría de nuevo a la posición correcta en el sistema de coordenadas mundial (el primer círculo azul claro en la segunda imagen a lo largo de la v original , llámelo p ) y luego decida (p. ej., para colisiones elásticas al reflejar v a lo largo de la colisión normal en p ) cuál será la posición real de A al final del cuadro ( At + 1 ).

Respuesta de colisión

Si hay más de 2 colisionadores, esto se volverá un poco más complejo, ya que también querrá hacer una detección de colisión para la segunda parte reflejada de v .

Eric
fuente
Gracias, lo más interesante. ¿Podría explicar cómo maneja el caso cuando A y B se cruzan durante el movimiento, pero terminan el movimiento sin intersección?
GameAlchemist
@GameAlchemist Esa sería una respuesta de colisión, y no tanta detección de colisión (el tema original de la pregunta). Pero me gusta Paint, así que mira la edición. :-)
Eric
Gracias por la actualización (y hurra por los esquemas :-)), esta no era mi pregunta, pero me ayudó a entender que su algoritmo ya maneja el caso cuando A pasa completamente por B.
GameAlchemist
5

OBB: cuadro delimitador orientado. Aquí hay un tutorial

Efectivamente, un cuadro delimitador alineado con el vector de velocidad del objeto A como el eje y (arriba). Su ancho y alto se pueden calcular mediante los puntos de inicio y finalización del objeto A. Luego, compara esto con el AABB del objeto B (tratándolo como un OOBB), y tu dorado.

Si solo está buscando una prueba de intersección rápida para ver SI PODRÍAN intersectarse, podría crear un AABB que rodee el AABB del objeto A en las posiciones inicial y final. Si un AABB no se cruza con este AABB que abarca todo, entonces no hay intersección; Sin embargo, esto podría conducir a falsos positivos, por lo que solo debe usarlo como prueba preliminar.

Wolfgang Skyler
fuente
4

No necesita OOB y no necesita usar la detección de colisión de paso de tiempo. Simplemente use la prueba de barrido AABB normal, vea este enlace . En esencia, hace exactamente lo que tiene en su diagrama: el AABB en movimiento es "barrido" desde el punto inicial al punto final y luego se usa para la detección de colisiones contra otros AABB estáticos.

Si le preocupa que esta prueba de barrido sea más costosa porque devuelve un "tiempo de impacto", creo que está optimizando prematuramente.

Se puede encontrar más información detallada sobre las pruebas de barrido en el excelente libro: Detección de colisiones en tiempo real por Christer Ericson.

SomeWritesReserved
fuente
3

Debilidad de caso de borde de aproximación AABB

Primero deberá descomponer el movimiento en pasos más pequeños y usar esa información para calcular un AABB de alto nivel. Si las AABB grandes se cruzan, puede verificar los pasos más pequeños para ser más precisos.

Estimar si ha habido o no una colisión al verificar AABB (u OOBB) usando solo las posiciones de inicio y finalización puede perder colisiones si alguno de los objetos gira rápidamente y es más largo en una dimensión que en otra.

Para calcular una estimación más precisa de AABB, descomponga el movimiento en pasos más pequeños, y usando solo el AABB inicial (no la malla del objeto), gire el AABB (ahora solo un cuadro, no alineado con el eje) como el objeto rotaría y se movería en cada paso. Los puntos máximo y mínimo para cada eje le darán el AABB que encierra todo el movimiento del objeto.

Si hay una intersección con el AABB más grande, puede usar los AABB más pequeños que ya se calcularon para determinar dónde pudo haber estado la colisión. Para cada uno de los AABB más pequeños que se cruzan con el otro objeto, puede hacer la detección de intersección de malla más costosa.

Constablebrew
fuente
2
o precalcular la anchura máxima de la lata BB para cualquier rotación y el uso que
de trinquete monstruo
2

Tendrás que descomponer el movimiento en pasos de movimiento más pequeños. Por ejemplo:

Desea descomponer el movimiento utilizando los componentes más grandes (en este caso, el eje X) y luego verificar la colisión en cada paso.

Esto puede parecer demasiado costoso, pero tenga en cuenta que un objeto que se mueve más rápido que su propio ancho en cada ciclo será EXTREMADAMENTE rápido, por lo que este escenario no es tan común como podría pensar al principio.

León
fuente
2
Este método es malo, porque no detectará algunos casos (por ejemplo, un cuadro que está cerca del primero y el segundo que dibujó) y aumentar el muestreo sería excesivo. La prueba de polígono simple con SAT debe ser lo suficientemente rápida y confiable.
Sopel
1
Sí, esta es una buena solución, pero no demasiado buena. La precisión disminuye rápidamente cuando la colisión se acerca a las esquinas de los objetos, el rendimiento disminuye a medida que aumenta la velocidad (o la precisión, dependiendo de la implementación), y es innecesariamente hacky.
BWG
2

También debe usar velocidades relativas para la verificación de colisión, de modo que un AABB sea "estático" y el otro se mueva a una velocidad propia menos la velocidad del "estático".

La forma más rápida de ver si pueden cruzarse es expandir el AABB en movimiento con la velocidad.

por ejemplo, el AABB se mueve hacia la derecha con 0.1 x / cuadro, luego lo extiende para que el borde izquierdo permanezca igual y el borde derecho esté 0.1 más. Entonces puedes consultar con el nuevo AABB. Si es falso, entonces no hay colisión. (retorno temprano y preciso para pequeñas velocidades).

Luego puede verificar si el final e iniciar AABB del objeto en movimiento se cruza. si es verdadero, entonces devuelve verdadero.

De lo contrario, debe verificar si la diagonal se cruza con la ABB estática.

Esto implica obtener las coordenadas de la diagonal donde x = borde izquierdo de la estática y el borde derecho ver si la y está dentro de la parte inferior y superior. (repita al revés)

monstruo de trinquete
fuente