Detección de colisiones usando el teorema del eje de separación

() translation by (you can also view the original English article)

El teorema del eje de separación se usa a menudo para verificar las colisiones entre dos polígonos simples, o entre un polígono y un círculo. Al igual que con todos los algoritmos, tiene sus fortalezas y sus debilidades. En este tutorial, repasaremos las matemáticas detrás del teorema y mostraremos cómo se puede usar en el desarrollo de juegos con algunos ejemplos de código y demostraciones.

Nota: Aunque las demostraciones y el código fuente de este tutorial utilizan Flash y AS3, debería poder usar las mismas técnicas y conceptos en casi cualquier entorno de desarrollo de juegos.

Lo que dice el teorema

El Teorema del eje de separación (SAT para abreviar) establece esencialmente que si puedes trazar una línea para separar dos polígonos, entonces no chocan. Es así de simple.

En el diagrama anterior, puedes ver fácilmente las colisiones que ocurren en la segunda fila. Sin embargo, si intenta comprimir una línea entre las formas, fallará. La primera fila es exactamente lo opuesto. Puede dibujar fácilmente una línea para separar las formas, y no solo una, sino muchas de ellas:

Está bien, no exageremos esto; Creo que entiendes el punto. El argumento clave aquí es que si puede dibujar una línea de este tipo, entonces debe haber un espacio que separa las formas. Entonces, ¿cómo comprobamos esto?

Proyección a lo largo de un eje arbitrario

Supongamos por ahora que los polígonos a los que nos referimos son cuadrados: box1 a la izquierda y box2 a la derecha. Es fácil ver que estos cuadrados están separados horizontalmente. Un enfoque directo para determinar esto en el código es calcular la distancia horizontal entre los dos cuadrados, luego restar los medios anchos de box1 y box2:

//Pseudo code to evaluate the separation of box1 and box2
var length:Number = box2.x - box1.x;
var half_width_box1:Number = box1.width*0.5;
var half_width_box2:Number = box2.width*0.5;

var gap_between_boxes:Number = length - half_width_box1 - half_width_box2;
if(gap_between_boxes > 0) trace("It's a big gap between boxes")
else if(gap_between_boxes == 0) trace("Boxes are touching each other")
else if(gap_between_boxes < 0) trace("Boxes are penetrating each other")

¿Qué pasa si las cajas no están bien orientadas?

Aunque la evaluación de la brecha sigue siendo la misma, tendremos que pensar en otro enfoque para calcular la longitud entre los centros y las medias anchuras, esta vez a lo largo del eje P. Aquí es donde las matemáticas vectoriales son útiles. Proyectaremos los vectores A y B a lo largo de P para obtener las medias anchuras.

Vamos a hacer una revisión de matemáticas.

Revisión del vector matematico

Comenzaremos por recapitular la definición del producto punto entre dos vectores A y B:

Podemos definir el producto de puntos usando solo los componentes de los dos vectores:

\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
(A_x)(B_x)+(A_y)(B_y)
\]

Alternativamente, podemos entender el producto de puntos usando las magnitudes de los vectores y el ángulo entre ellos:

\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
A_{magnitude}*B_{magnitude}*cos(theta)
\]

Ahora, intentemos averiguar la proyección del vector A sobre P.

Refiriéndonos al diagrama anterior, sabemos que el valor de proyección es \ (A_ {magnitud} * cos (theta) \) (donde theta es el ángulo entre A y P). Aunque podemos seguir adelante y calcular este ángulo para obtener la proyección, es complicado. Necesitamos un enfoque más directo:

\[
A. P=A_{magnitude}*P_{magnitude}*cos(theta)\\
A.\frac{P}{P_{magnitude}}=A_{magnitude}*cos(theta)\\
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]

Tenga en cuenta que \ (\ begin {bmatrix} P_x / P_ {magnitud} \\ P_y / P_ {magnitud} \ end {bmatrix} \) es en realidad el vector unitario de P.

Ahora, en lugar de usar el lado derecho de la ecuación, como lo estábamos haciendo, podemos optar por el lado izquierdo y seguir llegando al mismo resultado.

Aplicación a un escenario

Antes de continuar, me gustaría aclarar la convención de nomenclatura utilizada para denotar las cuatro esquinas de ambas casillas. Esto se reflejará en el código más adelante:

Nuestro escenario es el siguiente:

Digamos que ambas cajas están orientadas a 45 ° del eje horizontal. Debemos calcular las siguientes longitudes para determinar la brecha entre las cajas.

Proyección de A en el eje P
Proyección de B en el eje P
Proyección de C en el eje P

Tome nota especial de las direcciones de las flechas. Mientras que la proyección de A y C en P dará un valor positivo, la proyección de B en P producirá un valor negativo ya que los vectores apuntan en direcciones opuestas. Esto se trata en la línea 98 de la implementación de AS3 a continuación:

var dot10:Point = box1.getDot(0);
var dot11:Point = box1.getDot(1);

var dot20:Point = box2.getDot(0);
var dot24:Point = box2.getDot(4);

//Actual calculations
var axis:Vector2d = new Vector2d(1, -1).unitVector;
var C:Vector2d = new Vector2d(
    dot20.x - dot10.x,
    dot20.y - dot10.y
)
var A:Vector2d = new Vector2d(
    dot11.x - dot10.x,
    dot11.y - dot10.y
)
var B:Vector2d = new Vector2d(
    dot24.x - dot20.x,
    dot24.y - dot20.y
)
var projC:Number = C.dotProduct(axis)
var projA:Number = A.dotProduct(axis);
var projB:Number = B.dotProduct(axis);

var gap:Number = projC - projA + projB;  //projB is expected to be a negative value
if (gap > 0) t.text = "There's a gap between both boxes"
else if (gap > 0) t.text = "Boxes are touching each other"
else t.text = "Penetration had happened."

Aquí hay una demostración usando el código anterior. Haga clic y arrastre el punto central rojo de ambos cuadros y vea los comentarios interactivos.

Para la fuente completa, revise DemoSAT1.as en la descarga de la fuente.

Los defectos

Bueno, podemos ir con la implementación anterior. Pero hay algunos problemas, permítanme señalarlos:

Primero, los vectores A y B son fijos. Entonces, cuando intercambias las posiciones de box1 y box2, la detección de colisión falla.

En segundo lugar, solo evaluamos la brecha en un eje, por lo que situaciones como la que se muestra a continuación no se evaluarán correctamente:

Aunque la demostración anterior es defectuosa, aprendimos de ella el concepto de proyección. A continuación, vamos a mejorarlo.

Resolviendo el primer defecto

Primero que todo, necesitaremos obtener las proyecciones de esquinas mínimas y máximas (específicamente los vectores desde el origen hasta las esquinas de las cajas) en P.

projection of minimum and maximum of two boxes

El diagrama de arriba muestra la proyección de las esquinas mínima y máxima en P cuando las cajas están bien orientadas a lo largo de P.

Pero, ¿qué pasa si box1 y box2 no están orientados en consecuencia?

projection if boxes are not oriented accordingly

El diagrama de arriba muestra cuadros que no están bien orientados a lo largo de P, y sus correspondientes proyecciones min-max. En esta situación, tendremos que recorrer cada esquina de cada casilla y seleccionar las correctas según corresponda.

Ahora que tenemos las proyecciones min-max, evaluaremos si las cajas están chocando entre sí. Como?

Al observar el diagrama anterior, podemos ver claramente la representación geométrica para la proyección de box1.max y box2.min sobre el eje P.

Como puede ver, cuando hay un espacio entre los dos cuadros, box2.min-box1.max será más que cero, o en otras palabras, box2.min> box1.max. Cuando se intercambian las posiciones de las cajas, box1.min> box2.max implica que hay una brecha entre ellas.

Traduciendo esta conclusión en código, obtenemos:

//SAT: Pseudocode to evaluate the separation of box1 and box2
if(box2.min>box1.max || box1.min>box2.max){
	trace("collision along axis P happened")
}
else{
	trace("no collision along axis P")
}

Codigo inicial

Echemos un vistazo a un código más detallado para resolver esto. Tenga en cuenta que el código AS3 aquí no está optimizado. Aunque es largo y descriptivo, la ventaja es que puedes ver cómo funcionan las matemáticas detrás de ellas.

En primer lugar, tenemos que preparar los vectores:

//preparing the vectors from origin to points
//since origin is (0,0), we can conveniently take the coordinates 
//to form vectors
var axis:Vector2d = new Vector2d(1, -1).unitVector;
var vecs_box1:Vector.<Vector2d> = new Vector.<Vector2d>;
var vecs_box2:Vector.<Vector2d> = new Vector.<Vector2d>;

for (var i:int = 0; i < 5; i++) {
    var corner_box1:Point = box1.getDot(i)
    var corner_box2:Point = box2.getDot(i)
    
    vecs_box1.push(new Vector2d(corner_box1.x, corner_box1.y));
    vecs_box2.push(new Vector2d(corner_box2.x, corner_box2.y));
}

A continuación, obtenemos la proyección min-max en box1. Puedes ver un enfoque similar usado en box2:

//setting min max for box1
var min_proj_box1:Number = vecs_box1[1].dotProduct(axis); 
var min_dot_box1:int = 1;
var max_proj_box1:Number = vecs_box1[1].dotProduct(axis); 
var max_dot_box1:int = 1;

for (var j:int = 2; j < vecs_box1.length; j++) 
{
    var curr_proj1:Number = vecs_box1[j].dotProduct(axis)
    //select the maximum projection on axis to corresponding box corners
    if (min_proj_box1 > curr_proj1) {
        min_proj_box1 = curr_proj1
        min_dot_box1 = j
    }
    //select the minimum projection on axis to corresponding box corners
    if (curr_proj1> max_proj_box1) {
        max_proj_box1 = curr_proj1
        max_dot_box1 = j
    }
}

Finalmente, evaluamos si hay una colisión en ese eje específico, P:

1	var isSeparated:Boolean = max_proj_box2 < min_proj_box1 \|\| max_proj_box1 < min_proj_box2
2	if (isSeparated) t.text = "There's a gap between both boxes"
3	else t.text = "No gap calculated."

Aquí hay una demostración de la implementación anterior:

Puede arrastrar cualquiera de los recuadros a través de su punto medio y girarlo con las teclas R y T. El punto rojo indica la esquina máxima para un cuadro, mientras que el amarillo indica el mínimo. Si un cuadro está alineado con P, es posible que estos puntos parpadeen al arrastrar, ya que esas dos esquinas comparten las mismas características.

Echa un vistazo a la fuente completa en DemoSAT2.as en la descarga de la fuente.

Optimización

Si desea acelerar el proceso, no es necesario calcular el vector unitario de P. Por lo tanto, puede omitir una gran cantidad de costosos cálculos del teorema de Pitágoras que involucran a Math.sqrt ():

\[ \begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]

El razonamiento es el siguiente (consulte el diagrama anterior para obtener una guía visual sobre las variables):

/*
Let:
P_unit be the unit vector for P,
P_mag be P's magnitude,
v1_mag be v1's magnitude,
v2_mag be v2's magnitude,
theta_1 be the angle between v1 and P,
theta_2 be the angle between v2 and P,

Then:
box1.max < box2.min
=> v1.dotProduct(P_unit) < v2.dotProduct(P_unit)
=> v1_mag*cos(theta_1) < v2_mag*cos(theta_2)
*/

Ahora, matemáticamente, el signo de desigualdad sigue siendo el mismo si ambos lados de la desigualdad se multiplican por el mismo número, A:

/*
So:
A*v1_mag*cos(theta_1) < A*v2_mag*cos(theta_2)

If A is P_mag, then:
P_mag*v1_mag*cos(theta_1) < P_mag*v2_mag*cos(theta_2)
...which is equivalent to saying:
v1.dotProduct(P) < v2.dotProduct(P)
*/

Entonces, si es un vector unitario o no, en realidad no importa, el resultado es el mismo.

Tenga en cuenta que este enfoque es útil si solo está comprobando la superposición. Para encontrar la longitud de penetración exacta de box1 y box2 (que para la mayoría de los juegos probablemente necesites), aún necesitas calcular el vector unitario de P.

Resolviendo la segunda falla

Así que resolvimos el problema para un eje, pero ese no es el final. Todavía tenemos que abordar otros ejes, pero ¿cuáles?

El análisis de las cajas es bastante sencillo: comparamos dos ejes P y Q. Para confirmar una colisión, la superposición en todos los ejes debe ser cierta: si hay algún eje sin superposición, podemos concluir que no hay colisión.

¿Qué pasa si las cajas están orientadas de manera diferente?

Haga clic en el botón verde para pasar a otra página. Por lo tanto, en los ejes P, Q, R y S, solo hay un eje que no muestra superposición entre cuadros, y nuestra conclusión es que no hay colisión entre los cuadros.

Pero la pregunta es, ¿cómo decidimos qué ejes comprobar para la superposición? Bueno, tomamos las normales de los polígonos.

En una forma generalizada, con dos cuadros, tendremos que revisar ocho ejes: n0, n1, n2 y n3 para cada box1 y box2. En una forma generalizada, con dos cuadros, tendremos que revisar ocho ejes: n0, n1, n2 y n3 para cada box1 y box2.

n0 y n2 de box1
n1 y n3 de box1
n0 y n2 de box2
n1 y n3 de box2

Así que no necesitamos pasar por los ocho; sólo cuatro lo harán. Y si box1 y box2 comparten la misma orientación, podemos reducir aún más para evaluar solo dos ejes.

¿Qué pasa con otros polígonos?

Desafortunadamente, para el triángulo y el pentágono de arriba no hay tal atajo, así que tendremos que ejecutar controles a lo largo de todas las normales.

Cálculo de las normales

Cada superficie tiene dos normales:

El diagrama de arriba muestra la normal izquierda y derecha de P. Observe los componentes conmutados del vector y el signo de cada uno.

Para mi implementación, estoy usando una convención en el sentido de las agujas del reloj, así que uso las normales de la izquierda. A continuación se muestra un extracto de SimpleSquare.as que demuestra esto.

public function getNorm():Vector.<Vector2d> {
    var normals:Vector.<Vector2d> = new Vector.<Vector2d>
    for (var i:int = 1; i < dots.length-1; i++) 
    {
        var currentNormal:Vector2d = new Vector2d(
            dots[i + 1].x - dots[i].x, 
            dots[i + 1].y - dots[i].y
        ).normL	//left normals
        normals.push(currentNormal);
    }
    normals.push(
        new Vector2d(
            dots[1].x - dots[dots.length-1].x, 
            dots[1].y - dots[dots.length-1].y
        ).normL
    )
    return normals;
}

Nueva implementación

Estoy seguro de que puedes encontrar una manera de optimizar el siguiente código. Pero solo para que todos tengamos una idea clara de lo que está sucediendo, he escrito todo en su totalidad:

//results of P, Q
var result_P1:Object = getMinMax(vecs_box1, normals_box1[1]);
var result_P2:Object = getMinMax(vecs_box2, normals_box1[1]);
var result_Q1:Object = getMinMax(vecs_box1, normals_box1[0]);
var result_Q2:Object = getMinMax(vecs_box2, normals_box1[0]);

//results of R, S
var result_R1:Object = getMinMax(vecs_box1, normals_box2[1]);
var result_R2:Object = getMinMax(vecs_box2, normals_box2[1]);
var result_S1:Object = getMinMax(vecs_box1, normals_box2[0]);
var result_S2:Object = getMinMax(vecs_box2, normals_box2[0]);

var separate_P:Boolean = result_P1.max_proj < result_P2.min_proj || 
                         result_P2.max_proj < result_P1.min_proj
var separate_Q:Boolean = result_Q1.max_proj < result_Q2.min_proj || 
                         result_Q2.max_proj < result_Q1.min_proj
var separate_R:Boolean = result_R1.max_proj < result_R2.min_proj || 
                         result_R2.max_proj < result_R1.min_proj
var separate_S:Boolean = result_S1.max_proj < result_S2.min_proj || 
                         result_S2.max_proj < result_S1.min_proj

//var isSeparated:Boolean = separate_p || separate_Q || separate_R || separate_S
if (isSeparated) t.text = "Separated boxes"
else t.text = "Collided boxes."

Verás que algunas de las variables no se calculan necesariamente para alcanzar el resultado. Si cualquiera de separate_P, separate_Q, separate_R y separate_S es verdadero, entonces están separados y no hay necesidad de continuar.

Esto significa que podemos guardar una buena cantidad de evaluación, solo marcando cada uno de esos booleanos después de que se hayan calculado. Requeriría volver a escribir el código, pero creo que puede trabajar en él (o revisar el bloque comentado en DemoSAT3.as).

Aquí hay una demostración de la implementación anterior. Haga clic y arrastre los cuadros a través de sus puntos intermedios, y use las teclas R y T para rotar los cuadros:

Reflexiones posteriores

Cuando se ejecuta este algoritmo, comprueba los superposiciones a través de los ejes normales. Tengo dos observaciones aquí para señalar:

SAT es optimista de que no habrá colisión entre polígonos. El algoritmo puede salir y concluir felizmente "sin colisión" una vez que cualquier eje no muestre superposición. Si hubo una colisión, el SAT tendrá que recorrer todos los ejes para llegar a esa conclusión; por lo tanto, cuantas más colisiones haya en realidad, peor será el rendimiento del algoritmo.
SAT utiliza la normal de cada uno de los bordes de los polígonos. Así que cuanto más complejos sean los polígonos, más caro será el SAT.

Detección de colisión hexágono-triángulo

Aquí hay otro fragmento de código de ejemplo para verificar una colisión entre un hexágono y un triángulo:

private function refresh():void {
//prepare the normals
var normals_hex:Vector.<Vector2d> = hex.getNorm();
var normals_tri:Vector.<Vector2d> = tri.getNorm();

var vecs_hex:Vector.<Vector2d> = prepareVector(hex);
var vecs_tri:Vector.<Vector2d> = prepareVector(tri);
var isSeparated:Boolean = false;

//use hexagon's normals to evaluate
for (var i:int = 0; i < normals_hex.length; i++) 
{
    var result_box1:Object = getMinMax(vecs_hex, normals_hex[i]);
    var result_box2:Object = getMinMax(vecs_tri, normals_hex[i]);
    
    isSeparated = result_box1.max_proj < result_box2.min_proj || result_box2.max_proj < result_box1.min_proj
    if (isSeparated) break;
}
//use triangle's normals to evaluate
if (!isSeparated) {
    for (var j:int = 1; j < normals_tri.length; j++) 
    {
        var result_P1:Object = getMinMax(vecs_hex, normals_tri[j]);
        var result_P2:Object = getMinMax(vecs_tri, normals_tri[j]);
        
        isSeparated = result_P1.max_proj < result_P2.min_proj || result_P2.max_proj < result_P1.min_proj
        if (isSeparated) break;
    }
}

if (isSeparated) t.text = "Separated boxes"
else t.text = "Collided boxes."
}

Para obtener el código completo, consulte DemoSAT4.as en la descarga de origen.

La demostración está abajo. La interacción es la misma que en las demostraciones anteriores: arrastre a través de los puntos centrales y use R y T para rotar.

Detección de colisión de caja-círculo

La colisión con un círculo puede ser una de las más simples. Debido a que su proyección es la misma en todas las direcciones (es simplemente el radio del círculo), podemos hacer lo siguiente:

private function refresh():void {
    //prepare the vectors
    var v:Vector2d;
    var current_box_corner:Point;
    var center_box:Point = box1.getDot(0);
    
    var max:Number = Number.NEGATIVE_INFINITY;
    var box2circle:Vector2d = new Vector2d(c.x - center_box.x, c.y - center_box.y)
    var box2circle_normalised:Vector2d = box2circle.unitVector
    
    //get the maximum
    for (var i:int = 1; i < 5; i++) 
    {
        current_box_corner = box1.getDot(i)
        v = new Vector2d(
            current_box_corner.x - center_box.x , 
            current_box_corner.y - center_box.y);
        var current_proj:Number = v.dotProduct(box2circle_normalised)
        
        if (max < current_proj) max = current_proj;
    }
    if (box2circle.magnitude - max - c.radius > 0 && box2circle.magnitude > 0) t.text = "No Collision"
    else t.text = "Collision"
}

Echa un vistazo a la fuente completa en DemoSAT5.as. Arrastra el círculo o la caja para verlos chocar.

Conclusión

Bueno eso es todo por ahora. Gracias por leer y deje sus comentarios con un comentario o pregunta. ¡Nos vemos en el siguiente tutorial!