Acepté el estudio de los procesos de reconocimiento de colisiones, y esto me llevó al algoritmo Gilbert-Johnson-Keerthi (GJK).

Todos los ejemplos de código en la publicación están escritos en TypeScript. Los ejemplos usan las estructuras que creé que no se discuten en detalle en la publicación. Son simples y se pueden ver en el repositorio de GitHub:

• Vector
• IShape
• Collision

Todo el código de la publicación se almacena en el repositorio de GitHub:

https://github.com/jthomperoo/gjk-ts-implementation

La publicación fue escrita sobre la base de este artículo y el video recomendado en él:

• http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
• http://mollyrocket.com/849

Introduccion

GJK es un algoritmo diseñado para determinar la intersección de dos formas convexas. Es simple e implementado utilizando una "función auxiliar" generalizada que le permite utilizar un enfoque más general; de la misma manera, puede procesar polígonos y formas que consisten en curvas, por ejemplo, elipses.

Informacion requerida

Suma de Minkowski

GJK usa un concepto llamado la suma de Minkowski. SM se calcula sumando todos los puntos de dos figuras. Por ejemplo, tome las dos figuras que se muestran a continuación:


Figura A (verde):


Figura B (púrpura):


Tomando los valores de la figura A y la figura B, podemos calcular la suma de Minkowski:

A + D = (0,1) + (0,-1) = (0,0)

A + E = (0,1) + (1,1) = (1,2)

A + F = (0,1) + (-1,1) = (-1,2)

B + D = (1,-1) + (0,-1) = (1,-2)

B + E = (1,-1) + (1,1) = (2,0)

B + F = (1,-1) + (-1,1) = (0,0)

C + D = (-1,-1) + (0,-1) = (-1,-2)

C + E = (-1,-1) + (1,1) = (0,0)

C + F = (-1,-1) + (-1,1) = (-2,0)

Si tomamos estos valores y hacemos un gráfico a partir de ellos, veremos qué figura será el resultado.

Suma de Minkowski para las figuras A y B:

Tenga en cuenta que AD en la tabla y el gráfico corresponde a A + D



Para comprender mejor la suma de Minkowski, podemos imaginar que tomamos una figura A y la obviamos con el contorno de una B. La figura resultante será la suma de Minkowski.

Diferencia de Minkowski

GJK usa una variación de la suma de Minkowski, en la cual no se toma A + B, sino A - B. En las fuentes que leí, esto se llama la "Diferencia de Minkowski". La diferencia de Minkowski tiene una propiedad interesante: si dos figuras se superponen / intersectan, entonces la diferencia de Minkowski resultante contendrá el origen. Y esta es la base del algoritmo GJK.

Tomando los valores de las figuras A y B, podemos calcular la diferencia de Minkowski:

A - D = (0,1) - (0,-1) = (0,2)

A - E = (0,1) - (1,1) = (-1,0)

A - F = (0,1) - (-1,1) = (1,0)

B - D = (1,-1) - (0,-1) = (-1,0)

B - E = (1,-1) - (1,1) = (0,-2)

B - F = (1,-1) - (-1,1) = (2,-2)

C - D = (-1,-1) - (0,-1) = (-1,0)

C - E = (-1,-1) - (1,1) = (-2,-2)

C - F = (-1,-1) - (-1,1) = (0,-2)

Si tomamos estos valores y los colocamos en el gráfico, veremos la cifra resultante.

Diferencia de Minkowski para las figuras A y B:

Tenga en cuenta que AD en la tabla y el gráfico se refiere a A - D

Algoritmo

Basado en estos conceptos, el algoritmo GJK los optimiza. Calcular la suma de Minkowski puede llevar mucho tiempo, especialmente si verifica la intersección de dos figuras que consisten en muchos puntos. Para evitar esto, GJK utiliza dos conceptos clave: funciones auxiliares y símplex.

Funciones de ayuda

Las funciones auxiliares son una forma de muestrear un punto en el borde de la diferencia de Minkowski sin construir la figura completa. La función auxiliar obtiene dos cifras comparadas y la dirección que debe verificarse. Luego, la función auxiliar recibe de cada figura un punto más alejado de dos direcciones opuestas. Usando estos dos puntos más distantes, puede calcular el punto auxiliar en la figura de la diferencia de Minkowski. Tomamos puntos de direcciones opuestas porque obtenemos un punto en la diferencia de Minkowski, lo que nos dará el área más grande, es decir, habrá una mayor probabilidad de que encerremos el origen en la figura. Dado que la diferencia de Minkowski es el a - b , la presencia del punto de la figura b muestreado desde la dirección opuesta nos dará un punto auxiliar lo más lejos posible en esta dirección.

La implementación de la función auxiliar es bastante simple:

 function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

Una de las ventajas de GJK es que FarthestPointInDirection se puede abstraer y aplicar a polígonos y curvas. Aquí está la implementación de FarthestPointInDirection para un polígono.

 class Polygon implements IShape { public points: Vector[]; ... public FarthestPointInDirection(direction: Vector): Vector { let farthestDistance = -Infinity; // If there are no points, just return point 0,0 let farthestPoint: Vector = new Vector(0,0); for (const point of this.points) { const distanceInDirection = point.Dot(direction); if (distanceInDirection > farthestDistance) { farthestPoint = point; farthestDistance = distanceInDirection; } } return farthestPoint; } } 

Si desea ver cómo se implementarán otras formas, consulte el repositorio de Git de esta publicación , que presenta la implementación de Circle .

Así se calculará el punto auxiliar en la dirección (1,0) para las figuras A y B:

1. Tome el punto más distante de la figura A; Resulta ser el punto B (1, -1) . (Puede calcularlo, como lo hace el algoritmo que se muestra arriba, o simplemente verlo mirando el gráfico).
2. Tome el punto más distante de la figura B; Resulta ser el punto F (-1, 1) .
3. Calcule B - F ; resulta ser el punto BF (2, -2) , será auxiliar .

Símplex

Un símplex es una muestra de puntos a lo largo de la figura de diferencia de Minkowski. Los símplex pueden contener hasta tres puntos. GJK los usa, tratando de construir un triángulo alrededor del origen para determinar la ocurrencia de una colisión.

Construcción simple

Los símplex se construyen iterativamente agregando puntos auxiliares en diferentes direcciones. Cada punto auxiliar debe apuntar en una nueva dirección, para que podamos construir lo más rápido posible un simplex que contenga un punto de origen. La dificultad radica en elegir la dirección para obtener el siguiente punto auxiliar.

Detección de colisión y selección de dirección

El algoritmo básico simplemente construye un simplex con la ayuda de una función auxiliar, tratando de encerrar un punto de origen en la figura. Podemos entender que no hay colisión / intersección verificando si el punto auxiliar calculado alcanza el origen, y si no lo hace, entonces el origen debe estar fuera de la diferencia de Minkowski; por lo tanto, podemos decir que no hay colisión / intersección.

 function Calculate(a: IShape, b: IShape): Collision | undefined { // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); } 

Toda la complejidad y el funcionamiento interno del algoritmo están en simplex.CalculateDirection . Esta función determina si el origen está en el simplex actual; de ser así, volverá undefined ; de lo contrario, devolverá una nueva dirección para obtener un punto auxiliar, que debe agregarse al simplex.

 class Simplex { private points: Vector[]; ... CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } return undefined; } // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; } } 

Te preguntarás: ¿por qué no verificamos el segmento BC? Porque podemos excluir incondicionalmente que el origen es a lo largo de su perpendicular. Dado que los puntos B y C ya están en el simplex, y no solo se han agregado, sabemos que se verificaron en la iteración anterior. Podrían verificarse como parte de un triángulo o como un segmento de los primeros dos puntos en un simplex, no importa. Por lo tanto, podemos omitir con seguridad la comprobación del segmento BC.

Explicación detallada

Tenemos mucho código y parece confuso. A continuación analizaré los pasos del algoritmo para las figuras A y B que se muestran arriba.

Puntos de las figuras A y B:

1. Preparación del algoritmo; tomamos (0,1) como la dirección inicial.
   
   

    // Build a new Simplex for determining if a collision has occurred const simplex = new Simplex(); // Choose an arbitrary starting direction let direction: Vector | undefined = new Vector(0,1); 

   
   
2. Obtenemos el primer punto auxiliar.
   
   

     // Get the first support point and add it to the simplex const initSupportPoint = support(a, b, direction); simplex.Add(initSupportPoint); // Flip the direction for the next support point direction = direction.Invert(); 

   
   Obtenemos el punto más alejado del punto A en la dirección (0,1) y del punto B en la dirección (0,-1) .
   
   aFar: (0,1) y bFar: (0,-1)
   
   Use estos valores para obtener el punto auxiliar.
   
   Soporte: aFar-bFar = (0,2)
   
   

     function support(a: IShape, b: IShape, direction: Vector): Vector { const aFar = a.FarthestPointInDirection(direction); const bFar = b.FarthestPointInDirection(direction.Invert()); return aFar.Sub(bFar); } 

   
   
3. Volteamos la dirección del siguiente punto auxiliar y comenzamos la iteración, calculando un nuevo punto auxiliar.
   
   Soporte: (0,-3)
   
   

     // Flip the direction for the next support point direction = direction.Invert(); // Keep iterating until the direction is undefined, this will occur when // 'CalculateDirection' doesn't return a direction, indicating that an // intersection has been detected while(direction) { const supportPoint = support(a, b, direction); 

4. Verifique si el punto auxiliar ha llegado al origen; si no, no debería haber intersección. Si ella llegó al origen, entonces agregue el punto al símplex.
   
   En este caso, el punto auxiliar ha llegado al origen.
   
   dirección: (0,-1)
   
   Soporte: (0,-3)
   
   supportPoint.Dot (dirección): 3
   
   

     // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } // Add the simplex and determine a new direction simplex.Add(supportPoint); 

   
   
5. En esta etapa, el simplex es un segmento, por lo que no puede contener un punto de origen; definir una nueva dirección en la que buscar el punto auxiliar.
   
   

     direction = simplex.CalculateDirection(); 

   
   
   1. Tomamos el último punto agregado al simplex y determinamos la dirección al origen, este será el recíproco de este punto.
      
      a: (0,-3) ao: (0,3)
      
      

        CalculateDirection(): Vector | undefined { // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { 

   2. Como el simplex es un segmento, no un triángulo, tomamos el segundo punto del segmento y calculamos el segmento del simplex.
      
      b: (0,2) ab: (0,5)
      
      

        // Otherwise the simplex is just a line // B is the penultimate point in the simplex, // in this case the other end of the line const b = this.points[0]; // Determine a -> b line const ab = b.Sub(a); 

   3. Calculamos la perpendicular a este segmento y verificamos que se dirija al origen. Esta será la nueva dirección para el próximo punto auxiliar.
      
      abPerp: (5, 0)
      
      abPerp.Dot (ao) 0
      
      abPerp: (-5, 0)
      
      
      
      
      

        // Get the perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face TOWARDS the origin if (abPerp.Dot(ao) <= 0) { abPerp = abPerp.Invert(); } return abPerp; 

6. Ahora tenemos una dirección para buscar el siguiente punto auxiliar. Regresamos al comienzo del ciclo y no salimos de él, porque si bien tenemos una dirección, y la intersección aún no se ha encontrado.
   
   dirección: (-5, 0)
   
   Soporte: (-2,-2)
   
   supportPoint.Dot (dirección): 10
   
   El punto auxiliar ha llegado al origen, por lo que no podemos decir que no hay intersección.
   
   

     while(direction) { const supportPoint = support(a, b, direction); // If the support point did not reach as far as the origin, // the simplex must not contain the origin and therefore there is no // intersection if (supportPoint.Dot(direction!) <= 0) { // No intersection return; } 

7. Agregue un nuevo punto auxiliar al simplex, creando un triángulo. Este triángulo puede contener el origen, y si es así, el símplex volverá undefined , y no una nueva dirección para la búsqueda.
   
   

     // Add the simplex and determine a new direction simplex.Add(supportPoint); direction = simplex.CalculateDirection(); 

   
   
   1. Toma los puntos del simplex del triángulo.
      a: (-2,-2) b: (0,-3) c: (0,2) ao: (2,2)
      
      

        // Get a, the last point added to the simplex const a = this.points[this.points.length - 1]; // Since a was just added, we know that the inverse of a points // towards the origin const ao = a.Invert(); // If the simplex is a triangle if (this.points.length == 3) { // B is the penultimate in the simplex // C is the oldest point in the simplex const b = this.points[1]; const c = this.points[0]; 

   2. Tome los segmentos ab y ac.
      
      ab: (2,-1) ac: (2,4)
      
      

        // Determine a->b and a->c lines const ab = b.Sub(a); const ac = c.Sub(a); 

   3. Calculamos el perpendicular al segmento ab, dirigido desde el simplex.
      
      abperp: (-1,-2)
      
      

        // Determine perpendicular of the a->b line let abPerp = new Vector(ab.y, -ab.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (abPerp.Dot(c) >= 0) { abPerp = abPerp.Invert(); } 

   4. Determinamos si el origen está fuera del símplex más allá de ab.
      
      abPerp.Dot (ao): -6
      
      El origen no se encuentra fuera del símplex más allá de ab.
      
      
      
      
      

        if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; } 

   5. Calculamos la perpendicular al segmento ac dirigido desde el simplex.
      
      acPerp: (-4,2)
      
      

        // Determine perpendicular of the a->c line let acPerp = new Vector(ac.y, -ac.x); // Check the handedness of the perpendicular, it should // face AWAY from the simplex if (acPerp.Dot(b) >= 0) { acPerp = acPerp.Invert(); } 

   6. Determine si el origen está fuera del símplex más allá de ac.
      
      acPerp.Dot (ao): -4
      
      El origen no está fuera del símplex más allá de ab.
      
      
      
      
      

        // If the origin lies outside of the simplex remove the // point and determine a new direction in the direction // of the perpendicular; aiming to try to encapsulate // the origin that lies outside if (acPerp.Dot(ao) > 0) { this.points.splice(1, 1); return acPerp; } 

   7. Dado que AB y AC se verificaron en esta iteración, y sabemos que BC se verificó en la iteración anterior, el origen debe estar dentro del simplex, por lo que se detectó una colisión / intersección, informando sobre esto, la función volverá undefined .
      
      
      
8. Como se ha detectado una colisión, se sale del bucle y se devuelve información de Collision sobre la colisión entre las dos figuras.
   
   

     direction = simplex.CalculateDirection(); } // No direction calculated, intersection detected return new Collision(a, b); 

Conclusión

Espero que este artículo te ayude a entender el algoritmo GJK. El algoritmo da una respuesta de sí / no sobre la presencia de un conflicto entre las dos figuras. Se puede ver un ejemplo de trabajo con polígonos y círculos en el repositorio de esta publicación . Puede expandir este código con algoritmos y técnicas adicionales al tratar de obtener la distancia de penetración entre las dos figuras, la colisión normal y el punto de contacto. La publicación dyn4j tiene enlaces a buenos recursos en varios algoritmos de reconocimiento de colisión / respuesta; si quieres expandir GJK, entonces debes estudiarlos.