Navigation

Tutoriel précédent : formes 2D simples   Sommaire   Tutoriel suivant : collision au pixel près (pixel perfect)

II. Introduction

Nous parlerons ici de collisions avec des objets plus complexes.
Vous aurez besoin de connaissances mathématiques avancées pour comprendre tous les concepts.
Si ce n'est pas le cas, vous pouvez néanmoins utiliser les fonctions proposées telles quelles.

III. Point dans polygone

Jusqu'à présent, nous avons vu les Axis Aligned Bounding Box (AABB) et les cercles. Comment tester si un point est dans une Oriented Bounding Box (OBB), dans un triangle, un hexagone, et plus généralement dans un polygone ?

III-A. Définitions

III-A-1. Polygone convexe

Sans reprendre la définition exacte d'un polygone (que vous trouverez en lien à la fin de ce paragraphe), nous allons définir ce qu'est un polygone convexe.
Pour cela, nous allons d'abord présenter les polygones non convexes :

Image non disponible

Les polygones sont en rouge. Si on regarde les trois polygones de gauche, on peut constater qu'à chaque fois, au moins une diagonale est hors du polygone. Les diagonales sont en bleu. Je rappelle que les diagonales d'un polygone sont des segments qui relient deux sommets quelconques du polygone, mais qui ne sont pas des côtés.

La quatrième figure est un cas tordu : un polygone croisé, c'est-à-dire qu'il y a intersection entre au moins deux de ses côtés. Nous allons vite oublier ce quatrième cas.

Un polygone convexe est un polygone non croisé, dont toutes les diagonales sont à l'intérieur du polygone.

Image non disponible

Les polygones ci-dessus sont donc convexes. Ils ne sont pas croisés, et il n'existe pas de diagonales à l'extérieur.

Pour en savoir plus sur les polygones, et leur classification, consultez Wikipédia.

Un triangle est toujours convexe. Une OBB aussi.

III-A-2. De non convexe à convexe

Un polygone non convexe peut être transformé en un ensemble de polygones convexes. Si on regarde la figure ci-dessus sur les polygones non convexes, j'ai ajouté des traits verts qui découpent les polygones en plusieurs triangles. Comme chaque triangle est convexe, on transforme ainsi le polygone non convexe en plusieurs polygones convexes.

Vérifier si un point est dans ce polygone non convexe reviendra à vérifier s'il est dans l'un des triangles qui le composent.

Un algorithme pour transformer le polygone non convexe en triangles peut être le suivant :

  1. On parcourt les points du polygone non convexe ;
  2. Pour un point i, on considère son voisin précédent et son voisin suivant. Si le triangle formé par ces trois points est dans le polygone, alors on ajoute le triangle à la liste, et on considère le polygone non convexe restant comme étant le même polygone auquel on retire le sommet i (on relie donc i-1 et i+1) ;
  3. etc.

C'est un algorithme glouton, et le polygone restant finit par être un triangle.

On peut tester l'appartenance du triangle en regardant si l'angle du point i est aigu ou obtus par rapport au sens de parcours.

III-B. Applications

Un jeu comme Risk peut recourir à cette collision. Chaque pays peut être vu comme un polygone (non convexe), donc par un ensemble de polygones convexes.

Image non disponible

Quand vous choisissez un pays en cliquant dessus, cette collision est appliquée.

III-C. Calcul de collision première méthode

III-C-1. Regardez à gauche

Pour cette méthode, nous considérons un polygone convexe (s'il n'est pas convexe, regardez ci-dessus comment faire pour le décomposer en plusieurs polygones convexes).

Image non disponible

Voici de nouveau mes polygones convexes. Cette fois j'ai rajouté des flèches. En effet, je vais parcourir mes points dans l'ordre, comme si je partais d'un point, et que j'avançais en voiture sur le tour de mon polygone. L'idée est de choisir le bon sens de façon à ce que l'intérieur du polygone soit à gauche.

Voici l'idée :

Un point est à l'intérieur du polygone si et seulement s'il est « à votre gauche » tout le long de votre parcours.

Il va donc falloir, pour chaque côté orienté, voir si le point testé est à gauche ou non. S'il est, ne serait ce qu'une fois, à droite, alors le point n'est pas à l'intérieur.

Image non disponible

Il ne reste plus qu'a savoir si un point est à gauche ou pas. Sur la figure ci-dessus, il y a un segment [AB]. On va de A vers B. Le Point P est-il à gauche ?

III-C-2. Le déterminant

Mathématiquement, un simple calcul de déterminant suffit.
Nous avons les points A, B, P.
Soit D le vecteur AB :

Image non disponible

Soit T le vecteur AP :

Image non disponible

Soit d le déterminant de D,T. Le déterminant se calcule simplement ainsi (règle du gamma) :

Image non disponible
  • Si d>0 alors P est à gauche de AB.
  • Si d<0 alors P est à droite de AB.
  • Si d=0 alors P sur la droite AB.

Pour le code, nous considérons le polygone comme un tableau de points, de taille nbp. Soit les structures suivantes :

 
Sélectionnez
struct Point
{
  float x,y;
};

struct Vecteur
{
  float x,y;
};

Nous obtenons une fonction de collision comme ceci :

 
Sélectionnez
bool Collision(Point tab[],int nbp,Point P)
{
  int i;
  for(i=0;i<nbp;i++)
  {
     Point A = tab[i];
     Point B;
     if (i==nbp-1)  // si c'est le dernier point, on relie au premier
         B = tab[0];
     else           // sinon on relie au suivant.
         B = tab[i+1];
     Vecteur D,T;
     D.x = B.x - A.x;
     D.y = B.y - A.y;
     T.x = P.x - A.x;
     T.y = P.y - A.y;
     float d = D.x*T.y - D.y*T.x;
     if (d<0)
        return false;  // un point à droite et on arrête tout.
  }
  return true;  // si on sort du for, c'est qu'aucun point n'est à gauche, donc c'est bon.
}

À vous de voir si vous voulez qu'un point sur AB soit considéré comme dedans ou dehors, en mettant if (d<0) ou if (d<=0). Cependant, ça reste un cas limite.

Note : ceci fonctionne dans des repères directs. Dans les bibliothèques 2D, on manipule souvent des repères indirects (vecteur Y vers le bas). Dans ce cas, il faudra faire attention au sens de parcours. Notez que si vous « roulez à l'envers » sur le polygone, il suffira de tester si le point est toujours à droite (et non à gauche).

Cet algorithme marche aussi bien dans N² que dans R².

III-D. Calcul de collision deuxième méthode

La deuxième méthode permet de tester si un point est dans un polygone quelconque. Convexe ou non, cette méthode fonctionne dans tous les cas, même dans les cas de polygones croisés.
Il faudra cependant faire très attention à ce qu'on appellera les « cas limites ».

III-D-1. Point infini

Pour cet algo, nous allons chercher un point I qui sera en dehors du polygone.
Comment être sûr qu'un point est en dehors ? Il suffit de le prendre très loin.
Par exemple, on peut poser I(100000,0).

Nous partons du principe que notre polygone est sagement dans notre monde, et, notre monde étant par exemple compris entre -1000 et +1000, nous sommes sûr que le point I(100000,0) est hors du monde, et hors du polygone.

Image non disponible

Regardons le schéma ci-dessus. Des polygones, et des segments verts dont une extrémité est un des points P, Q, R, S, T, et l'autre extrémité est… loin ! (Le point I lointain.)

Voici la règle :

Comptez les intersections entre le segment vert et les segments du polygone. Si le nombre d'intersections est impair, alors le point est dans le polygone, sinon il est dehors.

Vérifions tout ça avec les exemples ci-dessus :

  • pour P, on coupe une fois : 1 est impair, P est à l'intérieur ;
  • pour Q, idem ;
  • pour R, on coupe deux fois. 2 est pair, on est à l'extérieur ;
  • pour S, on coupe 5 fois, impair, on est dedans ;
  • pour T, on coupe 4 fois, pair, on est dehors.

Cet algo revient donc à savoir combien de fois on coupe, donc il se base sur un algo d'intersection de segments.

III-D-2. Intersection de segments

Un segment est inscrit dans une droite. Nous allons donc considérer l'équation paramétrique d'une droite. Ceci est vu, me semble-t-il, à la fin du lycée.

Image non disponible

Une droite est définie par un point d'origine O, et un vecteur directeur : Image non disponible
En faisant varier t, on obtient tous les points de la droite.

Si on s'intéresse à un segment [AB], posons astucieusement :

Image non disponible

Nous aurons donc les règles suivantes :

  • si t = 0, alors P(t) = A ;
  • si t = 1, alors P(t) = B ;
  • si t appartient au segment [0..1] alors P(t) appartient au segment [AB], sinon, il n'est pas sur le segment.

Nous cherchons l'intersection de 2 segments [AB] et [IP]. Soit J, le point d'intersection. Nous cherchons donc :

Image non disponible

Où t et u seront les paramètres du point J sur chacune des deux droites (AB) et (IP).
Ce qui nous donne :

Image non disponible

Posons :

Image non disponible

Posons :

Image non disponible

Nous travaillons dans le plan, donc chaque point et chaque vecteur a une coordonnée x,y.
Ceci nous permet de poser le système suivant :

Image non disponible

Nous résolvons le système pour trouver t et u. Nous obtenons :

Image non disponible

Si le dénominateur (qui est le même pour t et u) s'annule, cela veut dire que les droites (AB) et (IJ) sont parallèles : donc J n'existe pas (ou alors l'intersection est l'ensemble de la droite).

Sinon, cela veut dire qu'il existe un point J, intersection des droites (AB) et (IJ). Mais nous, nous cherchons l'intersection des segments.
Il faut donc regarder si 0 <= t < 1 et 0 <= u < 1. Dans ce cas seulement, l'intersection se produit au niveau des segments.

Nous considèrerons qu'un point est sur le segment si t (ou u) vaut 0, mais pas s'il vaut 1. En effet, au niveau des sommets du polygone, si nous ne voulons considérer qu'un seul point d'intersection, nous dirons qu'il est sur un seul des segments, celui de paramètre 0.

Nous nous appuierons sur la fonction d'intersection de segments suivante :

 
Sélectionnez
int intersectsegment(Point A,Point B,Point I,Point P)
{
   Vecteur D,E;
   D.x = B.x - A.x;
   D.y = B.y - A.y;
   E.x = P.x - I.x;
   E.y = P.y - I.y;
   double denom = D.x*E.y - D.y*E.x;
   if (denom==0)
       return -1;   // erreur, cas limite
   t = - (A.x*E.y-I.x*E.y-E.x*A.y+E.x*I.y) / denom;
   if (t<0 || t>=1)
      return 0;
   u = - (-D.x*A.y+D.x*I.y+D.y*A.x-D.y*I.x) / denom;
   if (u<0 || u>=1)
      return 0;
   return 1;
}

Vous pouvez constater que je retourne 0 si les segments ne se touchent pas, 1 s'ils se touchent, et -1 dans les cas limites. Nous en aurons besoin pour la suite.

III-D-3. Fonction de collision

Nous en arrivons à la fonction de collision. Nous allons prendre un point I au hasard, mais loin. Puis nous allons calculer le nombre d'intersections avec chacun des segments. Si nous avons un nombre impair d'intersections, alors le point sera dedans, sinon dehors.
Nous ajoutons que si on tombe sur un cas limite (une droite parallèle à un des côtés), nous choisirons à nouveau un autre I.

 
Sélectionnez
bool Collision(Point tab[],int nbp,Point P)
{
  int i;
  Point I;
  I.x = 10000 + rand()%100;   // 10000 + un nombre aléatoire entre 0 et 99
  I.y = 10000 + rand()%100;
  int nbintersections = 0;
  for(i=0;i<nbp;i++)
  {
     Point A = tab[i];
     Point B;
     if (i==nbp-1)  // si c'est le dernier point, on relie au premier
         B = tab[0];
     else           // sinon on relie au suivant.
         B = tab[i+1];
     int iseg = intersectsegment(A,B,I,P);
     if (iseg == -1)
         return Collision(tab,nbp,P);  // cas limite, on relance la fonction.
     nbintersections+=iseg;
  }
  if (nbintersections%2==1)  // nbintersections est-il impair ?
     return true;
  else
     return false;
}

Note : la fonction peut être récursive en cas d'échec (cas limite). Elle pourrait donc planter si par malchance tous les rand donnaient chacun un cas limite, ce qui lancerait une récursivité infinie. Ceci est extrêmement improbable. Il faudrait un polygone comportant beaucoup de côtés, et vraiment… vraiment tordu !

Cet algorithme marche aussi bien dans N² que dans R².

IV. Segment cercle

Nous allons maintenant voir si un cercle touche un segment ou une droite.
Nous allons faire pas mal de maths ici, si ça vous fait peur, vous pouvez prendre les fonctions finales.

IV-A. Applications

Un jeu de flipper par exemple : vous testez les collisions entre la boule et chaque bord, représenté par des segments. Même les flips sont comme des segments pour les collisions.

Image non disponible

Contre exemple : Les casse-briques. Les casse-briques, c'est une balle qui touche une raquette « horizontale ». Il suffit de regarder, quand le y de la balle est en deçà d'une certaine valeur, si la raquette est en dessous ou non. De même on considèrera souvent la balle comme une AABB.

Ici, je parlerai d'un cas général de collision entre un cercle et un segment quelconque.

IV-B. Calcul de collision

Un petit schéma pour commencer.

Image non disponible

Nous avons le cercle de centre C et de rayon r. Nous avons la droite d'équation paramétrique : Image non disponible
Nous souhaitons avoir la distance CI, avec le point I projection orthogonale de C sur la droite. Nous ne connaissons pas I.

Je rappelle que si on a 2 points A et B, on peut définir l'équation paramétrique de la droite en posant :

Image non disponible

et

Image non disponible

La règle est simple, et facile à voir en regardant le schéma :

Le cercle touche la droite si et seulement si la distance CI est plus petite que le rayon du cercle.

Pour un segment, il y aura une précaution supplémentaire à prendre en compte que nous verrons plus loin.

IV-B-1. La distance CI

Un petit peu de trigonométrie, considérons le triangle ACI rectangle en I. Le point I est inconnu, mais A et C sont connus.
Nous cherchons la distance CI.

Nous connaissons la distance AC, c'est la norme du vecteur Image non disponible

Je rappelle que la norme d'un vecteur v est sa longueur, et qu'elle se calcule ainsi :

Image non disponible

Dans notre triangle ACI, nous pouvons écrire que : Image non disponible, donc que
Image non disponible (1)

avec a l'angle formé entre les deux vecteurs Image non disponible et Image non disponible

Ce qui nous embête maintenant, c'est cet angle, qu'il faudrait calculer. Soit on le calcule, soit on le vire. Une astuce est d'invoquer le produit vectoriel des deux vecteurs. Une des formules du produit vectoriel est la suivante :

Image non disponible

donc : Image non disponible (2)

En combinant (1) et (2), nous obtenons :

Nous obtenons donc : Image non disponible(3)

Nous nous sommes débarrassé de l'angle. Nous n'avons plus qu'un produit vectoriel et deux normes à calculer. Un produit vectoriel considère des vecteurs dans l'espace. Cependant, nous sommes dans le plan, donc c'est comme si nous étions dans l'espace, mais que les coordonnées z des vecteurs étaient à 0.
À partir de la, la norme d'un produit vectoriel sera un vecteur Image non disponibledont les composantes x et y seront nulles, et seule sa composante z sera non nulle. Prendre la norme de ce vecteur reviendra à prendre la valeur absolue de cette composante z, comme ceci :

Image non disponible

et donc, dans notre cas :

Image non disponible

Il suffira de diviser cette valeur absolue par la norme de u pour obtenir CI.

Et il nous suffira donc de savoir si CI est plus grand que le rayon ou non… Voici le code pour tester si le cercle C touche la droite AB :

 
Sélectionnez
bool CollisionDroite(Point A,Point B,Cercle C)
{
   Vecteur u;
   u.x = B.x - A.x;
   u.y = B.y - A.y;
   Vecteur AC;
   AC.x = C.x - A.x;
   AC.y = C.y - A.y;
   float numerateur = u.x*AC.y - u.y*AC.x;   // norme du vecteur v
   if (numerateur <0)
      numerateur = -numerateur ;   // valeur absolue ; si c'est négatif, on prend l'opposé.
   float denominateur = sqrt(u.x*u.x + u.y*u.y);  // norme de u
   float CI = numerateur / denominateur;
   if (CI<C.rayon)
      return true;
   else
      return false;
}

IV-B-2. Restriction au segment

Image non disponible

Tout d'abord, si le cercle ne touche pas la droite (AB), il ne touchera jamais le segment [AB]. Ensuite, si le cercle touche la droite, il touchera le segment si le point d'intersection I est entre A et B (cas 2 ci-dessus), mais aussi si A ou B sont dans le cercle (cas 3 contre cas 1 ci-dessus)

Pour le test d'un point dans un cercle, je vous renvoie au début de ce tutoriel.

Alors l'idée est de savoir si I est entre A et B.

Image non disponible

Pour cela, nous allons utiliser le produit scalaire, rapide, et qui a des propriétés bien sympathiques. Regardez le dessin de gauche.
J'ai les points A,B qui me donnent un vecteur \Image non disponible, qui part de A.
Au point A, on imagine une frontière verte, orthogonale au vecteur. Si on appelle P l'un des points (rouge ou bleu), le signe du produit scalaire Image non disponible. Image non disponible nous permet de savoir de quel côté de la ligne verte on est. Si le produit scalaire est positif, on est du côté de B, sinon, on est de l'autre côté.

Cette astuce est fort utile dans les jeux vidéo. Imaginons que vous soyez un héros au point A, que vous regardez en direction du point B. Un monstre arrive (c'est un point P). Comment savoir si le monstre est devant vous ou derrière vous ? Image non disponible. Image non disponible… Et ainsi selon que le signe de ce produit scalaire est positif ou non, vous voyez le monstre ou non.

Maintenant, nous voulons savoir si I est entre A et B. Regardons le dessin de droite ci-dessus. Comme I est le projeté orthogonal de C sur la droite, alors pour savoir si I est entre A et B, il suffit de regarder si C est dans la bande verte ou non. Pour cela, on applique deux produits scalaires :

Image non disponible
Image non disponible

Si pscal1>0 ET pscal2>0, alors C est dans la bande verte, et donc I entre A et B.

Cela nous donne la fonction suivante :

 
Sélectionnez
bool CollisionSegment(Point A,Point B,Cercle C)
{
   if (CollisionDroite(A,B,C) == false)
     return false;  // si on ne touche pas la droite, on ne touchera jamais le segment
   Vecteur AB,AC,BC;
   AB.x = B.x - A.x;
   AB.y = B.y - A.y;
   AC.x = C.x - A.x;
   AC.y = C.y - A.y;
   BC.x = C.x - B.x;
   BC.y = C.y - B.y;
   float pscal1 = AB.x*AC.x + AB.y*AC.y;  // produit scalaire
   float pscal2 = (-AB.x)*BC.x + (-AB.y)*BC.y;  // produit scalaire
   if (pscal1>=0 && pscal2>=0)
      return true;   // I entre A et B, ok.
   // dernière possibilité, A ou B dans le cercle
   if (CollisionPointCercle(A,C))
     return true;
   if (CollisionPointCercle(B,C))
     return true;
   return false;
}

IV-B-3. Le point d'impact

Actuellement, nous avons une information sur l'entrée en collision ou non. Mais il peut être utile de savoir à quel endroit on touche. On touche au point I bien entendu, mais comment calculer I ?

Nous avons vu que notre droite a pour équation : Image non disponible dans notre cas) I appartient à la droite, donc il existe t_i tel que : Image non disponible (5)

Si on regarde le triangle AIC rectangle en I, de nouveau, avec un peu de trigonométrie, on trouve :

Image non disponible

, avec a angle au sommet A.

Image non disponible (6)

Ici, il est astucieux de considérer la formule suivante du produit scalaire.

Image non disponible (7)
Sachant que Image non disponible

En utilisant (6) et (7), on trouve :

Image non disponible

Si on veut t_i, il faut diviser par la norme de u. Cela donne :

Image non disponible

Cela nous épargnera, au niveau optimisation, de calculer la racine carrée de la norme de u puisqu'on la considère au carré.

Nous obtenons la formule finale suivante :

Image non disponible

Au niveau du code nous avons donc une droite (AB), et un point C à projeter :

 
Sélectionnez
Point ProjectionI(Point A,Point B,Point C)
{
  Vecteur u,AC;
  u.x = B.x - A.x; 
  u.y = B.y - A.y; 
  AC.x = C.x - A.x;
  AC.y = C.y - A.y;
  float ti = (u.x*AC.x + u.y*AC.y)/(u.x*u.x + u.y*u.y);
  Point I;
  I.x = A.x + ti*u.x;
  I.y = A.y + ti*u.y;
  return I;
}

IV-B-4. La normale

La normale est le vecteur orthogonal à la tangente qui « regarde » le point C. Avoir la normale au point d'impact permet de calculer un rebond par exemple.
Sur une droite, la normale est constante en tout point.

On utilise souvent le produit vectoriel pour calculer des normales. Ici, on fera pareil, en utilisant deux produits vectoriels, un pour calculer un vecteur v orthogonal à notre plan Image non disponible , puis on refera un autre produit vectoriel pour trouver notre normale n Image non disponible.
L'avantage de cette méthode, c'est que la normale « regardera » toujours C, qu'il soit d'un côté ou de l'autre de la droite.
Cet algorithme fonctionne aussi dans l'espace, pour trouver le vecteur Image non disponible.

Si on applique les formules des deux produits vectoriels, on trouve simplement, pour la normale :

Image non disponible

Il est d'usage qu'une normale soit normalisée… autrement dit que sa norme (sa longueur) soit 1. Il suffit de diviser N par sa norme :

Image non disponible

Au niveau du code, cela nous donne la chose suivante :

 
Sélectionnez
Vecteur GetNormale(Point A,Point B,Point C)
{
  Vecteur AC,u,N;
  u.x = B.x - A.x;  
  u.y = B.y - A.y;
  AC.x = C.x - A.x;  
  AC.y = C.y - A.y;
  float parenthesis = u.x*AC.y-u.y*AC.x;  // calcul une fois pour les deux
  N.x = -u.y*(parenthesis);
  N.y = u.x*(parenthesis);
  // normalisons
  float norme = sqrt(N.x*N.x + N.y*N.y);
  N.x/=norme;
  N.y/=norme;
  return N;
}

IV-B-5. Une utilisation de tout ça : le rebond

Voici une utilisation pratique de tout ça : un calcul de rebond. Un jeu de flipper par exemple : votre balle arrive sur un mur en biais, vous voulez calculer le rebond : dans quel sens va-t-elle repartir ?

Image non disponible

Regardons le dessin ci-dessus. La balle (qu'on ne voit pas) arrive avec une trajectoire suivant le vecteur v rouge (de A vers I).
Après rebond, il faudra qu'elle reparte avec la trajectoire v_2 violet, de I vers B.

Nous calculons grâce à la fonction de collision si on touche la droite. Ensuite, si on touche, il faut faire rebondir. Pour cela, on aura besoin de la normale (en bleu) au segment (qu'on calculera comme vu au-dessus).

Le vecteur v_2 est tel que la normale soit la bissectrice des vecteurs v et v_2 au point I. Sur le dessin, j'ai mis les angles égaux.

J est le projeté orthogonal de A sur la droite faite par le point I et la normale.
Le vecteur v_3 est le même que le vecteur v_2, en partant de A au lieu de I, mais c'est le même vecteur.
Géométriquement, on peut démontrer que J est le milieu de [IK], et J est aussi le milieu de [AB].

Le vecteur Image non disponible est normalisé : rappelez-vous, les normales sont normalisées.

La longueur IJ (qu'on pourra aussi appeler d) s'obtient à partir d'un produit scalaire :

Image non disponible (7)
Je considère IA et non AI pour avoir une longueur positive.

On veut calculer le vecteur Image non disponible, donc Image non disponible
Géométriquement :

Image non disponible

On simplifie :

Image non disponible

En injectant (7), je trouve :

Image non disponible

Enfin, un petit code pour terminer cette grande partie. On donne le vecteur Image non disponible incident, et la normale, et on calculera le vecteur de rebond :

 
Sélectionnez
Vecteur CalculerVecteurV2(Vecteur v,Vecteur N)
{
  Vecteur v2;
  float pscal = (v.x*N.x +  v.y*N.y);
  v2.x = v.x -2*pscal*N.x;
  v2.y = v.y -2*pscal*N.y;
  return v2;
}

V. Segment segment

Voici maintenant une collision Segment-Segment.

V-A. Pourquoi cette collision ?

Nous pouvons penser que ce genre n'est pas trop utilisé, car un personnage est rarement représenté par un segment. Il peut être représenté par un point, par une AABB, un polygone, un cercle… Mais rarement un segment.

Cependant, en raisonnant comme cela, vous pensez à un état figé.

Maintenant, regardez ce schéma :

Image non disponible

Votre personnage est le point O. Il y a un mur, représenté par le segment AB. Il veut avancer vers le point P (donc selon le vecteur OP). Se prend-il le mur ?

Pour le savoir, nous regarderons la collision entre les segments [AB] et [OP].

V-B. Applications

Image non disponible
Quoi ? Un jeu 3D comme Doom dans la rubrique 2D ? o_O
Image non disponible

Oh que oui… Le premier Doom, une merveille, un jeu faussement 3D. Un amas de trapèzes qui nous font penser à la 3D, mais un jeu en interne bien 2D…

Image non disponible

Quel beau monde en 3D n'est-ce pas ? Un beau couloir multicolore… Dites merci à votre cerveau de vous faire voir un monde en 3D, parce que moi je n'ai dessiné que des trapèzes… (un rectangle est un trapèze particulier). Des trapèzes dont les bases sont alignées sur l'axe des Y, bien droit. Voilà, dans Doom, tous les murs sont des trapèzes.
Mais ça, c'est l'affichage. En réalité, dans Doom, en mémoire, il n'y a qu'une map 2D (comme la 2e image que je présente ici, ces segments rouges et jaunes (mais pas à petits pois, la génération Dorothée comprendra la blague).

Donc dans Doom, le personnage est un point dans une carte 2D faite de plein de segments qui représentent les murs.

Nous sommes donc tout à fait dans le cas vu plus haut, à savoir que nous sommes un point O, nous voulons avancer vers P. Touchons-nous le segment [AB] ?

V-C. Calcul de collision

Nous allons calculer cette collision en deux étapes :

Tout d'abord, il peut y avoir collision seulement si O et P ne sont pas du même côté de la droite (AB).

En effet, si P et O sont du même côté de la droite (AB), on peut tout de suite dire « il n'y aura pas collision ». On peut donc calculer la collision entre le segment [OP] et la droite (AB)

V-C-1. Calcul de collision entre segment et droite

Rappelez-vous le calcul du déterminant de 2 vecteurs qui me dit si un point est « à gauche » ou « à droite » d'une droite. Si on considère le vecteur AB, et le vecteur AP, le déterminant de Image non disponible me dit si mon point P est à gauche ou à droite du mur (en considérant le mur comme « démarrant » au point A et « regardant » le point B.

  • Si (d > 0), P est à gauche.
  • Si (d < 0), P est à droite.
  • Si (d == 0), P est dans le mur : on va éviter ce cas-là.

On va partir du principe que P n'est jamais dans le mur. En effet, dans un jeu comme Doom, on commence hors d'un mur, et quand on évolue, on ne permet pas d'aller « dans » le mur. On permet d'aller proche, mais jamais dedans. Donc on n'est jamais « dans » un mur. Donc d n'est jamais égal à 0.

Maintenant, on calcule le déterminant Image non disponible et Image non disponible pour savoir de quel côté sont P et O.

  • Si d_P > 0 et d_O > 0 alors ils sont du même côté ;
  • Si d_P < 0 et d_O < 0 alors ils sont du même coté ;
  • Si d_P > 0 et d_O < 0 alors ils ne sont pas du même côté ;
  • Si d_P < 0 et d_O > 0 alors ils ne sont pas du même côté.

ça nous fait quatre conditions à voir, sauf si on pense aux propriétés de la multiplication, qui vont nous simplifier le travail :

  • Si d_P * d_O > 0 alors ils sont du même côté ;
  • Si d_P * d_O < 0 alors ils ne sont pas du même côté.

Au niveau du code, cela donne ceci :

 
Sélectionnez
bool CollisionDroiteSeg(Point A,Point B,Point O,Point P) 
{ 
  Vecteur AO,AP,AB; 
  AB.x = B.x - A.x; 
  AB.y = B.y - A.y; 
  AP.x = P.x - A.x; 
  AP.y = P.y - A.y; 
  AO.x = O.x - A.x; 
  AO.y = O.y - A.y; 
  if ((AB.x*AP.y - AB.y*AP.x)*(AB.x*AO.y - AB.y*AO.x)<0) 
     return true; 
  else 
     return false; 
}

V-C-2. Calcul de collision entre segment et segment

Une idée simple pour calculer la collision entre segment et segment est de se servir deux fois de la formule ci-dessus.
Si vous avez quatre points ABOP, que vous voulez calculer la collision entre le segment [AB] et le segment [OP], il suffit de calculer la collision entre la droite (AB) et le segment [OP], puis la collision entre la droite (OP) et le segment [AB]. Si les deux collisions sont valides, alors les segments se touchent.

Au niveau du code, cela donne :

 
Sélectionnez
bool CollisionSegSeg(Point A,Point B,Point O,Point P) 
{ 
  if (CollisionDroiteSeg(A,B,O,P)==false) 
     return false;  // inutile d'aller plus loin si le segment [OP] ne touche pas la droite (AB) 
  if (CollisionDroiteSeg(O,P,A,B)==false) 
     return false; 
  return true; 
}

V-C-3. Calcul de collision entre segment et segment, forme paramétrique

Cette méthode est plus complexe que la précédente, mais permettra de calculer le point d'intersection.
Grâce au calcul segment/droite, on sait que les points O et P sont de part et d'autre de la droite (AB), mais il y a collision segment/segment seulement si le point d'intersection I est entre A et B. Sinon, le personnage passe à côté du mur : il n'y a pas collision.

Nous allons donc voir si l'intersection est entre A et B ou non. De cette condition dépendra notre collision.

Posons la forme paramétrique de la droite (AB) :

Image non disponible

Avec cette forme, nous pouvons affirmer que I est entre A et B si et seulement si 0 <= k <= 1

Il ne reste plus qu'à trouver k.

I appartient également à la droite (OP), donc :

Image non disponible

Du coup, on peut écrire :

Image non disponible

Nous sommes dans le plan, nous pouvons décomposer les points et les vecteurs comme suit :

Image non disponible

Nous avons donc deux équations, et deux inconnues (k et l).
Si nous résolvons ce système, nous obtenons :

Image non disponible
Image non disponible

Notez que pour notre cas, nous n'avons pas besoin de l. Je le mets quand même, car on en aura besoin plus loin si on veut s'approcher au plus près du mur.

Voici la fonction de Collision Segment-Segment :

 
Sélectionnez
bool CollisionSegSeg(Point A,Point B,Point O,Point P) 
{ 
  if (CollisionDroiteSeg(A,B,O,P)==false) 
     return false;  // inutile d'aller plus loin si le segment [OP] ne touche pas la droite (AB) 
  Vecteur AB,OP; 
  AB.x = B.x - A.x; 
  AB.y = B.y - A.y; 
  OP.x = P.x - O.x; 
  OP.y = P.y - O.y; 
  float k = -(A.x*OP.y-O.x*OP.y-OP.x*A.y+OP.x*O.y)/(AB.x*OP.y-AB.y*OP.x); 
  if (k<0 || k>1) 
     return false; 
  else 
     return true; 
}

V-C-4. Ne pas aller dans le mur

Pour terminer ce chapitre, quelques idées pour éviter de se retrouver dans le mur.
Si vous êtes le point O et que vous allez vers le mur, alors il y aura collision. L'idée est d'avancer quand même « jusqu'au mur ».

Comme nous allons dans le mur, nous ne déplacerons pas notre joueur selon le vecteur Image non disponible, qui nous amènerait au-delà du mur (au point P).
Nous ne le déplacerons pas non plus selon le vecteur Image non disponible, qui nous amènerait dans le mur exactement (ce que nous voulons absolument éviter, il ne faut jamais être « dans » le mur).
Nous déplacerons le joueur selon le vecteur Image non disponible où e est un nombre positif très petit (un « epsilon » dit-on dans le jargon mathématique), par exemple 0.001.
Ainsi, nous nous approcherons au plus près du mur, sans être dedans ni passer à travers.

Bien que ce genre d'algorithme pourrait marcher avec des nombres entiers, (dans N²) en faisant attention aux arrondis, il est préférable d'utiliser des coordonnées réelles (dans R²) pour cet algorithme.

VI. Cercles - Axis Aligned Bounding Box

Nous cherchons maintenant à déterminer la collision entre un cercle et une AABB.

Cette collision pourra, dans certains cas tordus, être un peu calculatoire.
C'est pour cela que l'idée sera d'éliminer le plus rapidement possible les cas triviaux.
Comme ces cas seront majoritaires, la collision sera en moyenne très rapide.

Regardons le schéma suivant :

Image non disponible

Je souhaite tester la collision entre le cercle vert, et la AABB rouge.

Première étape, le cercle peut être lui-même inscrit dans une AABB, que l'on peut calculer facilement.
Mieux, si votre sprite est une balle, sa surface porteuse sera rectangulaire, et sera directement la AABB violette : vous n'aurez donc même pas à la calculer, il suffira de passer la surface porteuse !

VI-A. Premier test

Premier test, nous allons tester la collision AABB vs AABB de nos deux AABB rouge et violette. Ce test est rapide, et élimine déjà tous les cas ou les objets sont suffisamment loin.
En effet, s'il n'y a pas collision entre ces deux AABB, inutile d'aller plus loin : il n'y a pas collision.

Vous éliminez ici d'entrée la grande majorité des cas ! :)

S'il y a collision AABB, alors nous sommes dans l'un de ces cas :

Image non disponible

Nous allons continuer à éliminer rapidement les cas triviaux.

VI-B. Deuxième test

Nous allons voir si un des sommets de la AABB rouge est dans le cercle, grâce à la collision rapide « Point dans Cercle ».
Nous pourrons alors dire qu'il y a collision dans les cas A et D, et sortir de l'algorithme.

VI-C. Troisième test

Afin de détecter le cas C, nous allons faire une collision « Point dans AABB » sur le centre du cercle et la AABB rouge. Nous pouvons alors sortir de l'algorithme dans ce cas.

À partir d'ici, cela devient plus calculatoire : nous sommes soit dans le cas B, soit dans le cas E. La bonne nouvelle, c'est que dans la majorité des cas, nous serons sortis avant.

VI-D. Quatrième test

Il faut donc lever l'ambiguïté entre le cas B, et le cas E.
La différence entre ces deux cas se situe au niveau des segments de la AABB.
Nous allons considérer chacun des 4 segments de la AABB.
Pour chacun de ces segments, nous allons projeter le point centre du cercle sur le segment. Si la projection est sur le segment, alors nous sommes dans le cas E, si elle est hors du segment, alors on est dans le cas B.

Si on regarde le schéma suivant :

Image non disponible

Nous avons le segment AB. Nous projetons un point dessus, soit le rouge, soit le vert, soit le bleu. Seul le vert est projeté sur le segment, les deux autres sont hors du segment.
Cela signifie que le point vert est entre les deux droites bleu ciel, droites passant respectivement par A et B et perpendiculaires au segment AB.

Pour déterminer si le point sera projeté sur le segment ou dehors, c'est assez simple.
Soit C le point à tester. Nous allons considérer les produits scalaires suivants :

Image non disponible

Le signe de ces produits scalaires va nous donner immédiatement la réponse :

  • si s1 > 0 et s2 > 0, alors nous sommes hors du segment, côté B (point bleu) ;
  • si s1 < 0 et s2 < 0, alors nous sommes hors du segment, côté A (point rouge) ;
  • si s1 > 0 et s2 < 0, alors nous sommes dans le segment (point vert) ;
  • si s1 < 0 et s2 > 0, alors nous avons un grave problème mathématique…. Ce cas n'existe pas !

Évidemment, nous avons aussi les cas limites où s1 == 0, s2 == 0.

Mais pour simplifier, basons-nous sur la règle des signes :

  • si s1 * s2 > 0, on est dehors ;
  • sinon, on est dedans.

Vous pouvez remplacer > 0 par >= 0 si vous considérez le segment comme ouvert : ]AB[ au lieu de [AB].

Après avoir fait ces projections sur les 4 segments de la AABB (en réalité, deux suffisent, car les segments sont parallèles et « en face » deux à deux) ; si les points calculés sont tous dehors, nous sommes dans le cas B (pas de collision), sinon nous sommes dans le cas E (collision).

Et pour finir, petit algorithme formel pour illustrer :

 
Sélectionnez
bool CollisionCercleAABB(Cercle C1,AABB box1) 
{ 
   AABB boxCercle = GetBoxAutourCercle(C1);  // retourner la bounding box de l'image porteuse, ou calculer la bounding box. 
   if (CollisionAABBvsAABB(box1,boxCercle)==0) 
      return false;   // premier test 
   if (CollisionPointCercle(box1.x,box1.y,C1)==1 
    || CollisionPointCercle(box1.x,box1.y+box1.h,C1)==1 
    || CollisionPointCercle(box1.x+box1.w,box1.y,C1)==1 
    || CollisionPointCercle(box1.x+box1.w,box1.y+box1.h,C1)==1) 
      return true;   // deuxieme test 
   if (CollisionPointAABB(C1.x,C1.y,box1)==1) 
      return true;   // troisieme test 
   int projvertical = ProjectionSurSegment(C1.x,C1.y,box1.x,box1.y,box1.x,box1.y+box1.h); 
   int projhorizontal = ProjectionSurSegment(C1.x,C1.y,box1.x,box1.y,box1.x+box1.w,box1.y); 
   if (projvertical==1 || projhorizontal==1) 
      return true;   // cas E 
   return false;  // cas B   
} 

int ProjectionSurSegment(int Cx,int Cy,int Ax,int Ay,int Bx,int By) 
{ 
   int ACx = Cx-Ax; 
   int ACy = Cy-Ay; 
   int ABx = Bx-Ax; 
   int ABy = By-Ay; 
   int BCx = Cx-Bx; 
   int BCy = Cy-By; 
   int s1 = (ACx*ABx) + (ACy*ABy); 
   int s2 = (BCx*ABx) + (BCy*ABy); 
   if (s1*s2>0) 
     return 0; 
   return 1; 
}

Nous verrons avec le temps les collisions d'autres objets complexes.

Navigation

Tutoriel précédent : formes 2D simples   Sommaire   Tutoriel suivant : collision au pixel près (pixel perfect)