Geekly articles weekly

Calcul de collision 2D: algorithme de Gilbert-Johnson-Kirti

image

J'ai repris l'étude des processus de reconnaissance des collisions, ce qui m'a conduit à l'algorithme Gilbert-Johnson-Keerthi (GJK).

Tous les exemples de code dans la publication sont écrits en TypeScript. Les exemples utilisent les structures que j'ai créées qui ne sont pas discutées en détail dans l'article. Ils sont simples et peuvent être consultés dans le référentiel GitHub:

  • Vector
  • IShape
  • Collision

Tout le code de la publication est stocké dans le référentiel GitHub:

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

Le message a été écrit sur la base de cet article et de la vidéo recommandée:


Présentation


GJK est un algorithme conçu pour déterminer l'intersection de deux formes convexes. Il est simple et implémenté à l'aide d'une «fonction auxiliaire» généralisée qui vous permet d'utiliser une approche plus générale - de la même manière, vous pouvez traiter des polygones et des formes constituées de courbes, par exemple des ellipses.

Informations obligatoires


Somme de Minkowski


GJK utilise un concept appelé la somme de Minkowski. SM est calculé en additionnant tous les points de deux chiffres. Par exemple, prenez les deux figures ci-dessous:


Figure A (verte):

UnBC
(0,1)(1, -1)(-1, -1)

Figure B (violet):

DEF
(0, -1)(1,1)(-1,1)

En prenant les valeurs des figures A et B, nous pouvons calculer la somme 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 nous prenons ces valeurs et en faisons un graphique, nous verrons quel chiffre sera le résultat.

Somme de Minkowski pour les figures A et B:

Notez que AD dans le tableau et le graphique correspond à A + D

Graphique de la somme de Minkowski des formes A et B

ADAeAFBdÊtreBfCDCECF
(0,0)(1,2)(-1,2)(1, -2)(2.0)(0,0)(-1, -2)(0,0)(-2,0)

Pour mieux comprendre la somme de Minkowski, nous pouvons imaginer que nous prenons une figure A et la contournons avec le contour d'un B. La figure résultante sera la somme de Minkowski.

Différence Minkowski


GJK utilise une variation de la somme de Minkowski, dans laquelle non A + B est pris, mais A - B. Dans les sources que j'ai lues, cela s'appelle la «différence Minkowski». La différence Minkowski a une propriété intéressante: si deux figures se chevauchent / se croisent, alors la différence Minkowski résultante contiendra l'origine. Et c'est la base de l'algorithme GJK.

En prenant les valeurs des figures A et B, nous pouvons calculer la différence 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 nous prenons ces valeurs et les mettons sur le graphique, nous verrons la figure résultante.

Différence de Minkowski pour les figures A et B:

Notez que AD dans le tableau et le graphique fait référence à A - D

Graphique de la somme de Minkowski des formes A et B

ADAeAFBdÊtreBfCDCECF
(0,2)(-1,0)(1,0)(-1,0)(0, -2)(2, -2)(-1,0)(-2, -2)(0, -2)

Algorithme


Sur la base de ces concepts, l'algorithme GJK les optimise. Le calcul de la somme de Minkowski peut prendre beaucoup de temps, surtout si vous vérifiez l'intersection de deux chiffres composés de nombreux points. Pour éviter cela, GJK utilise deux concepts clés: les fonctions d'assistance et les simplexes.

Fonctions d'assistance


Les fonctions auxiliaires sont un moyen d'échantillonner un point sur le bord de la différence de Minkowski sans construire la figure entière. La fonction d'assistance obtient deux chiffres comparés et la direction à vérifier. Ensuite, la fonction auxiliaire reçoit de chaque figure un point le plus éloigné de deux directions opposées. En utilisant ces deux points les plus éloignés, vous pouvez calculer le point auxiliaire sur la figure de la différence de Minkowski. Nous prenons des points de directions opposées parce que nous obtenons un point sur la différence de Minkowski, ce qui nous donnera la plus grande surface, c'est-à-dire qu'il y aura une probabilité plus élevée que nous incluions l'origine dans la figure. Puisque la différence de Minkowski est le a - b le a - b , la présence du point de la figure b échantillonné dans la direction opposée nous donnera un point auxiliaire qui est le plus loin possible dans cette direction.

L'implémentation de la fonction d'assistance est assez 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); }

L'un des avantages de GJK est que FarthestPointInDirection peut être abstrait et appliqué aux polygones et aux courbes. Voici l'implémentation de FarthestPointInDirection pour un polygone.

 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 vous souhaitez voir comment d'autres formes seront implémentées, consultez le référentiel Git de ce post , qui présente l'implémentation de Circle .

Voici comment le point auxiliaire dans la direction (1,0) sera calculé pour les figures A et B:

  1. Prenez le point le plus éloigné de la figure A; il s'avère être le point B (1, -1) . (Vous pouvez le calculer, comme le fait l'algorithme ci-dessus, ou simplement le voir en regardant le graphique).
  2. Prenez le point le plus éloigné de la figure B; il s'avère que c'est le point F (-1, 1) .
  3. Calculez B - F ; il s'avère que c'est le point BF (2, -2) - ce sera auxiliaire .

Simplexes


Un simplex est un échantillon de points le long de la figure de différence de Minkowski. Les simplex peuvent contenir jusqu'à trois points. GJK les utilise, essayant de construire un triangle autour de l'origine pour déterminer l'occurrence d'une collision.

Construction en simplex


Les simplexes sont construits de manière itérative en ajoutant des points auxiliaires dans différentes directions. Chaque point auxiliaire doit pointer dans une nouvelle direction, afin que nous puissions construire le plus rapidement possible un simplex contenant un point d'origine. La difficulté réside dans le choix de la direction dans laquelle obtenir le prochain point auxiliaire.

Détection de collision et sélection de direction


L'algorithme de base construit simplement un simplexe à l'aide d'une fonction auxiliaire, essayant d'inclure un point d'origine dans la figure. Nous pouvons comprendre qu'il n'y a pas de collision / intersection en vérifiant si le point auxiliaire calculé atteint l'origine, et si ce n'est pas le cas, alors l'origine doit être en dehors de la différence de Minkowski; par conséquent, nous pouvons dire qu'il n'y a pas de collision / intersection.

 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); }

Toute la complexité et le fonctionnement interne de l'algorithme sont dans simplex.CalculateDirection . Cette fonction détermine si l'origine est dans le simplexe actuel - si c'est le cas, elle retournera undefined ; sinon, il retournera une nouvelle direction pour obtenir un point auxiliaire, qui devra être ajouté au simplexe.

 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; } }

Vous vous demandez peut-être: pourquoi ne vérifions-nous pas le segment de la Colombie-Britannique? Parce que nous pouvons exclure inconditionnellement que l'origine est le long de sa perpendiculaire. Comme les points B et C sont déjà dans le simplexe, et qu'ils n'ont pas seulement été ajoutés, nous savons qu'ils ont été vérifiés lors de l'itération précédente. Ils peuvent être vérifiés soit en tant que partie d'un triangle, soit en tant que segment des deux premiers points d'un simplex - peu importe. Par conséquent, nous pouvons ignorer la vérification du segment BC en toute sécurité.

Explication détaillée


Nous avons obtenu beaucoup de code et cela semble déroutant. Ci-dessous, j'analyserai les étapes de l'algorithme pour les figures A et B ci-dessus.

Points des figures A et B:

UnBCDEF
(0,1)(1, -1)(-1, -1)(0, -1)(1,1)(-1,1)

  1. Préparation de l'algorithme; nous prenons (0,1) comme direction initiale.

     // 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. Nous obtenons le premier point auxiliaire.

      // 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();

    Nous obtenons le point le plus éloigné du point A dans la direction (0,1) et du point B dans la direction (0,-1) .

    aFar: (0,1) et bFar: (0,-1)

    Utilisez ces valeurs pour obtenir le point auxiliaire.

    Prise en charge: 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. Nous inversons la direction du prochain point auxiliaire et commençons l'itération, en calculant un nouveau point auxiliaire.

    Prise en charge: (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. Vérifiez si le point auxiliaire a atteint l'origine; sinon, il ne devrait pas y avoir d'intersection. Si elle a atteint l'origine, ajoutez le point au simplexe.

    Dans ce cas, le point auxiliaire a atteint l'origine.

    direction: (0,-1)

    Prise en charge: (0,-3)

    supportPoint.Dot (direction): 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. À ce stade, le simplexe est un segment, il ne peut donc pas contenir de point d'origine à l'intérieur; définir une nouvelle direction dans laquelle chercher le point auxiliaire.

      direction = simplex.CalculateDirection();

    1. Nous prenons le dernier point ajouté au simplexe et déterminons la direction vers l'origine, ce sera l'inverse de ce point.

      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. Puisque le simplexe est un segment, pas un triangle, nous prenons le deuxième point du segment et calculons le segment du simplexe.

      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. Nous calculons la perpendiculaire à ce segment et vérifions qu'il est dirigé vers l'origine. Ce sera la nouvelle direction pour le prochain point auxiliaire.

      abPerp: (5, 0)

      abPerp.Dot (ao) 0

      abPerp: (-5, 0)

      Carte de la ligne ab et sa perpendiculaire

        // 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. Maintenant, nous avons une direction pour rechercher le prochain point auxiliaire. Nous revenons au début du cycle et ne le quittons pas, car alors que nous avons une direction, et que l'intersection n'a pas encore été trouvée.

    direction: (-5, 0)

    Prise en charge: (-2,-2)

    supportPoint.Dot (direction): 10

    Le point auxiliaire a atteint l'origine, nous ne pouvons donc pas dire qu'il n'y a pas d'intersection.

      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. Ajoutez un nouveau point auxiliaire au simplexe, créant un triangle. Ce triangle peut contenir l'origine, et si c'est le cas, alors le simplex retournera undefined , et non une nouvelle direction pour la recherche.

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

    1. Prenez les points du simplexe du triangle.
      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. Prenez les segments ab et 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. Nous calculons la perpendiculaire au segment ab, dirigée à partir du simplexe.

      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. Nous déterminons si l'origine est en dehors du simplexe au-delà de ab.

      abPerp.Dot (ao): -6

      L'origine ne se situe pas en dehors du simplex au-delà de ab.

      Carte de la ligne ab et sa perpendiculaire

        if (abPerp.Dot(ao) > 0) { this.points.splice(0, 1); return abPerp; }
    5. Nous calculons la perpendiculaire au segment ac dirigé du simplexe.

      acPerpe: (-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. Déterminez si l'origine est en dehors du simplex au-delà de ca.

      acPerp.Dot (ao): -4

      L'origine n'est pas en dehors du simplex au-delà de ab.

      Carte de la ligne ac et sa perpendiculaire

        // 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. Puisque AB et AC ont été vérifiés dans cette itération, et nous savons que BC a été vérifié dans l'itération précédente, l'origine doit se trouver à l'intérieur du simplexe, donc une collision / intersection a été détectée - informant à ce sujet, la fonction retournera undefined .

      Lignes ab, ac et bc et perpendiculaires pertinentes
  8. Puisqu'une collision a été détectée, la boucle est fermée et les informations de Collision concernant la collision entre les deux figures sont renvoyées.

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

Conclusion


J'espère que cet article vous aidera à comprendre l'algorithme GJK. L'algorithme donne une réponse oui / non sur la présence d'un conflit entre les deux figures. Un exemple de travail avec des polygones et des cercles peut être consulté dans le référentiel de ce message . Vous pouvez développer ce code avec des algorithmes et des techniques supplémentaires en essayant d'obtenir la distance de pénétration entre les deux figures, la collision normale et le point de contact. Le post dyn4j a des liens vers de bonnes ressources sur divers algorithmes de reconnaissance de collision / réponse; si vous souhaitez développer GJK, vous devez les étudier.

Source: https://habr.com/ru/post/fr472404/

More articles:


All Articles