Collisions en 2d : axes séparateurs
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... :)
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
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
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.