Collisions en 2d : axes séparateurs

Soyez le premier à donner votre avis sur cette source.

Vue 12 955 fois - Téléchargée 1 101 fois

Description

Voici une petite source illustrant une technique très simple de test de collisions entre polygones en 2d qui peut être utilisée dans les jeux vidéos par exemple.

Le test de collision entre 2 polygones s'effectue en deux temps :
1) Test approximatif : test sur les enveloppes rectangulaire des deux polygones, si les rectangles se touchent, un test plus détaillé est effectué. Le test sur les rectangles permettent d'optimiser la vitesse de détection des collisions car le test entre 2 rectangles est très très rapide et simple
2) Si le test approximatif réussi, on effectue un test plus précis. Le test utilise la technique basée sur le théorème des axes séparateurs ! c'est une technique assez simple (il suffit de regarder le code de collision, il fait a peine 10 lignes) et assez précise.

Technique des axes séparateurs :
En gros, pour dire que deux polygones ne se chevauchent pas, il faut être capable de tracer une ligne entre les deux ne touchant pas les 2 polygones. Dans le cas contraire, les deux polygones se touchent.
Plus mathématiques :
1) On récupère tous les axes séparateurs possibles pour les deux polygones. Pour les polygones, les axes sont les normales a chaque face des polygones! donc il y a autant d'axes que de face et il est super facile de calculer une normale a une face (regarder vos cours de géométrie euclidienne!)
2) on projette les points des deux polygones sur chaque axes (un produit scalaire suffit...) et on prends pour les deux polygones, les points extrêmes des projections sur l'axe.
3) si le segment des points extrêmes du 1er polygone chevauche le segment du 2eme polygone, on dit que l'axe n'est pas séparateur (il est séparateur si les deux segments sont disjoints)
4) on dit que le polygone ne touche pas l'autre polygone s'il existe un axe pour lequel l'axe est séparateur. Si tous les axes ne sont pas séparateurs, les polygones se touchent!

Je recommande un petit coup d'oeil sur le site http://www.flashxpress.net/wikimedia/index.php/D%C3%A9tection_De_Collision qui illustre les axes séparateurs avec de jolies animations en Flash.

La source :

La code de démonstration montre des polygones 2d qui tombent, dés qu'un objet touche un autre, il s'arrête. C'est pas très beau mais c'est un bon exemple de démonstration de collisions. La source pourrait très bien servir de point de départ pour un bon vieux Tetris... :)

Conclusion :


Dans le zip, le projet pour Netbeans (j'ai codé sou Netbeans 6 beta mais je pense que le projet est compatible Netbeans 5.5) et est directement compilable/exécutable avec Java 6

Pour ceux qui ont pas Netbeans, il faut compiler le répertoire src/ et exécuter la classe MainFrame

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
194
Date d'inscription
vendredi 17 février 2006
Statut
Membre
Dernière intervention
1 mai 2009
28
La division en triangle est surtout utilisée pour les polygones sur des objets 3d. Il existe bien d'autre techniques de collision différentes (il suffit de voir sur Google), celle çi en est une qui est très simple et adaptée à pas mal de jeu
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
36
c'est interessant comme algo, moi je croyais que tout ca se faisait a partir de divisions en triangles et verification qu'aucune ligne ne se croise...

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.