Texel
OpenGL | Index | Contact

Test de collisions 2D et 3D
Avec vecteur et Segments en 2D
Avec vecteur et Polygones en 3D



Cet article explique une méthode de détection de collisions utilisant des vecteurs (pour le mouvement) et des segments/polygones en 2D/3D. Pour faire simple, on va prendre l'exemple d'une collision en 2D en déterminant si un point (symbolisant un objet) a traversé un segment de droite (symbolisant un mûr). Si c'est le cas, nous allons voir comment faire rebondir notre point comme une balle sur un mûr. La méthode est adaptable pour la 3D.
La méthode de détection de collision présentée ici, est une méthode parmi d'autres. Elle a des avantages et des inconvénients. Je ne présente ici que la théorie. Pour l'appliquer dans un programme, il vous faudra réfléchir un peu et l'adapter à vos besoins.


En 2D

Rappel:

Equation d'une droite Alpha:

Ax + By + D = H    

x, y Coordonnée d'un point G(x,y) de l'espace.
A et B    Coordonné du vecteur normal à la droite respectivement suivant x et y.
D Distance entre l'origine du repère 2D (0,0) et le projeté de l'origine sur la droite.
H Distance entre un point G(x,y) de l'espace (Ex: notre objet) et le plan (ie le point I(xi,yi) issu de la projection de G sur Alpha).

Soit

N(xn,yn) Vecteur normal à la droite (normalisé).
V(xv,yv,zv)    Le vecteur vitesse du point (normalisé).

Rappel: Un segment est une portion finie d'une droite infinie.

Nous allons maintenant procéder par étapes.
Le caractère "*" représente une multiplication.
Le caractère "." représente un produit scalaire.
Le caractère "^" représente un produit vectoriel.
Tous les vecteurs sont normalisés dans cet article.



Le point a-t-il traversé la droite?

Nous déterminons d'abord si le point a traversé la droite qui supporte le segment en regardant si la valeur H a changé de signe. Si c'est le cas, nous verrons ensuite si le point a traversé la droite en passant à l'intérieur du segment (ça réduit les calculs inutiles). Pour cela il nous faut les valeurs de A, B et D. Elles peuvent être calculées à chaques boucle de jeu ou seulement au démarrage suivant que le segment est mobile ou non.

I. Chercher la valeur de A et B

Le vecteur normal à notre droite peut être calculé de la même façon que l'on calcul le vecteur normal d'une face d'un triangle.

Rappelons d'abord comment on calcul la normale d'un triangle:

Au lycée, nous avons appris que pour calculer la normale d'un plan, il nous faut calculer le produit vectoriel de deux vecteurs de ce plan. Pour un polygone, on utilise trois points successifs (une soustraction de deux points nous donne un vecteur).

N = AC ^ BC

Mais attention: Il faut faire attention au sens des vecteurs que l'on prend pour calculer notre normale (AC ^ BC != CA ^ BC). En effet, une normale à une direction et surtout un sens. Il faut donc toujours choisir nos trois points de la même manière.

Retournons à nos segments. Pour calculer sa normale, on crée un troisième point imaginaire pour pouvoir utiliser la méthode ci-dessus. Ce point, nous allons le créer à partir d'un des deux points du segmnt. On ajoute pour cela une composante z=0 aux coordonnées 2D des deux points du segment. Puis on crée le troisième point avec les coordonnées x et y d'un des points du segment plus une coordonnée z différente de 0.

Le sens des normales n'a pas d'importances si vos mûrs ne peuvent pas être traversés dans les deux sens.
Mais le sens des normales peut nous permettre de faire des mûres qui ne peuvent être traversé que dans un seul sens (comme les plates-formes de Super Mario Bros). L'ordre de déclaration des deux points de l'extrémité des segments peut servir à générer des normales dans un sens souhaité.

II. Chercher la valeur de D

Pour calculer D, on va chercher des valeurs de x,y et H que l'on connaît.
Dans l'équation de notre droite, on remplace x et y par les coordonnées d'un point de la droite (donc du segment).
On fixe donc H à zéro (le point est sur le droite).
On a déjà calculé A et B.

D= 0 - (A*x) - (B*y);


III. Chercher la valeur de H

Pour calculer la valeur de H qui correspond au point G(x,y,z) de notre objet, il ne nous reste plus qu'à utiliser l'équation de la droite.

H = Ax + By + D

Si la valeur H a changé de signe, le segment a été traversé.
Vous pouvez aussi vérifier que H n'est pas inférieur à une certaine valeur (pour gérer le rayon d'une balle par exemple).


Si oui, était-ce à travers le segment ?

Le point représentant notre objet a traversé la droite (H a changé de signe) mais pas forcement à travers notre segment. Pour le savoir, il faut calculer les coordonnées du point d'intersection I(xi,yi) entre la droite et la trajectoire de notre point.

I. On cherche la distance entre la position actuelle du point G(x,y) et sa position lorsqu'il a percuté le segment en I(xi,yi).

Soit R cette distance.
R = H / (N.V)

En effet, le produit scalaire N.V est égal au cosinus de l'angle entre la normal N et le vecteur vitesse V (sachant qu'on a pris la longueur des vecteurs N et V égale à 1). Et comme: La droite Alpha, le vecteur N et le vecteur V forme un triangle, on peut utiliser la règle:
hypothénuse = coté adjacent/cos(w).

II. On cherche les coordonnées du point I(xi,yi,zi).

On reconstitue le trajet en marche arrière.
xi = x - ( xv * R)
yi = y - ( yv * R)


III. On Cherche si le point I appartient au segment.

Si le point I(xi,yi) appartient au segment, l'angle qui relient I(xi,yi) aux deux sommets du segment est égale à 180 degrés (ou PI).
Si cet angle est égal à -180 degrés, le point G(x,y) est à l'extérieur du segment.
On utilise le produit scalaire pour trouver cet angle.
Attention aux extrémités des segments?

Note:

Le point G(x,y) appartiendra forcement à la droite donc l'angle est égal à -180 ou 180 degrés. Alors vous pouvez être très large dans le choix de votre marge d'incertitude.


Si oui, quel est le nouveau vecteur vitesse ?

NouveauVecteurVitesse= V + 2*(-V.N)*N.



En 3D


En 3D, c'est à peu près la même chose, sauf que les droites deviennent des plans et les segments des polygones.
Et les vecteurs ont bien sûre la composante z en plus.

Equation d'un plan P:

Ax + By + Cz + D = H

Pour déterminer si le point a traversé le polygone, il faut vérifier que la sommes des angles entre les vecteurs reliant le point I et les sommets du polygone est égale 360 degrés.


Conclusion:

Cette méthode est plus utilisée en 3D qu'en 2D car la précision n'est pas toujours nécessaire. Dans vos programmes, n'oubliez pas de gérer les extrémités des segments ou polygones et les coins (car un rebond peut en cacher un autre :) ).




Version originale: Mai 2003
Dernière mise à jour: Mai 2003
Par Grégory Smialek
www.texel.fr.fm