dimanche 10 janvier 2010

Tutorial - Détection des collisions

Je me suis enfin penché pour de bon sur la détection des collisions, sujet qui m'a toujours paru insurmontable. Mais cette fois-ci, et grâce à quelques recherches sur GameDev.net, j'ai fini par comprendre et implémenter la technique basée sur le théorème de séparation des convexes.

Le principe est simple: deux solides convexes sont séparés si et seulement si il existe un hyperplan (c'est à dire un plan pour la dimension 3, ou une droite pour la dimension 2) de telle sorte que l'un soit d'un côté, et l'autre de l'autre.



Quand bien même cette définition est utile pour tout solide, c'est pour les polygones et les polyèdres qu'elle devient foudroyante. Prenons la dimension 2, par exemple. S'il existe une infinité de droites potentiellement séparatrices, il suffit en fait de vérifier chaque droite correspondant à un côté de chacun de notre polygone. Et comment vérifie-t-on que les polygones sont séparés? Tout simplement en prenant une droite orthogonale à notre droite séparatrice, et en projetant chaque point de chaque polygone sur cette droite. Si les projetés sont séparés, l'on a une droite séparatrice, et l'on peut s'arrêter.



Toutes les faces ne fourniront pas une droite séparatrice, comme par exemple ici:



L'algorithme est donc très simple: l'on prend chaque face de chaque polygone. L'on prend la normale à la face, et l'on projette chaque point sur la normale, via un bête produit scalaire. L'on garde le plus petit et le plus grand des produits scalaires pour chacun des deux polygones, et s'il n'y a pas intersection, les polygones sont séparés et l'on s'arrête. Si après avoir testé toutes les faces des deux polygones, l'on a toujours pas réussi à les séparer, c'est qu'il y a collision.

En 3 dimensions, c'est pareil, l'algorithme permet de transformer un problème complexe en 3D en plusieurs problèmes triviaux en 1D. Voilà le pseudo code:


Pour chaque axe n de chaque polygone
pour chaque vertex v du polygone 1
p = v * n
min1 = min(tous les p)
max1 = max(tous les p)
pour chaque vertex v du polygone 2
p = v * n
min2 = min(tous les p)
max2 = max(tous les p)
si (min1, max1) séparé de (min2, max2)
pas de collision, sortir
Chaque axe a été testé négatif, collision, sortir


J'ai parlé d'axes au lieu de normales aux faces, c'est parce que certaines formes ont des faces qui ont des normales dans la même direction, et qu'il est donc inutile de dupliquer l'effort. Par exemple, pour un cube, on pourra se contenter de tester 3 axes au lieu des 6 normales.

2 commentaires:

Julien a dit…

Niveau complexite, c'est un peu bourrin comme methode, non?

M87 a dit…

Pas faux, c'est assez bourrin! De par son caractère peu efficace mais exact, cette technique aura sa place comme "dernière vérification". Je vois bien d'abord un octree pour n'extraire que les objets locaux, puis l'élimination rapide via sphères englobantes ou boites alignées sur les axes, puis enfin, pour les quelques objets récalcitrants, l'artillerie lourde du théorème de séparation des convexes.

A noter également que le théorème de séparation des convexes n'aide pas à trouver le point de collision, ce qui le rend moins utile pour gérer les collisions dynamiques, rebonds, etc.