Détection de collision polygone vs polygone.
Il existe plusieurs méthodes pour détecter des collisions entre polygone, entre autre, celle de SAT.
ODFAEG utilise une méthode générique qui teste les collisions entre des polygones 2D et 3D.
ODFAEG permet de créer deux sorte de polygone, des polygones plats (polygones en 2D dans l’espace) ou bien des polygones non plat (polygones en 3D dans l’espace)
Le constructeur de la classe BoundingPolyhedron prend donc un paramètre booléen qui détermine si la polygone est plat ou non.
Pour que l’algorithme fonctionne les polygones doivent être convexe! (C’est à dire que les arrêtes du polygone ne peuvent pas se croiser)
Rechercher la région de voronoi.
ODFAEG possède une méthode pour rechercher si un point est plus proche d’une arrête, d’une face ou bien d’un sommets d’un polygone convexe.
Un polygone avec odfaeg est composé d’une liste de triangles, et donc, il suffit d’ajouter les sommets de chaque face pour définir le polygone.
Le théorème de SAT nécessite de faire beaucoup de projections, ce qui rend l’algorithme lent lorsque des polygones sont en collision.
L’idée est donc de rechercher quel est l’arrête, la face ou le sommet le plus proche des polygones en collision.
Voici une image qui montre les régions de voronoi pour un polygone en 2D :
Comme le montre l’image, ici je trace des rayons partant du centre et suivant les diagonales, ces régions portent le nom de région de Voronoi, ici le point P par exemple est dans la région 1.
Il va falloir rechercher pour chaque sommets du polygone 2, (celui comportant le point P), quel est le point le plus proche du polygone 1, pour cela je prend le milieu de chaque arrête du polygone un (les bissectrices) et la distance entre les bissectrices du polygone p1 et les sommets du polygone p2.
Pour le test de SAT il va falloir récupérer la normale de l’arrête de la région de voronoi du second polygone, et l’index du sommet du second polygone.
Mais la bissectrice la plus proche du point P n’est pas forcément la bonne, regardons par exemple ce dessin.
La normale la plus proche du point P est m2 car le côté opposé du triangle est plus court, mais ce n’est pas bon car M2 n’est pas dans la région du point P.
J’ai du donc rechercher une astuce, cette astuce consiste à faire ceci :
Pour savoir si la médiatrice se trouve dans la région il suffit de prendre les vecteurs délimitant la région, les vecteurs ne sont rien d’autres que les diagonales de l’arrête de la bissectrice, ensuite je prend le vecteur CP. (vecteur entre le sommet du polygone 2 et le centre de du polygone 1)
Je calcule ensuite les angles a et b, angles entre les diagonales et le vecteur PC, si la médiatrice est dans la région du point P, alors les angles a et b sont de signe différent.
Si a vaut 0, cela veut dire que P et à la frontière entre la région 1 et 2, si b vaut 0 ça veut dire que P est à la frontière entre les régions 1 et 3, dans ce cas là il est vraiment facile de déterminer si les polygones sont en collision.
Voila, je sais donc comment trouver le sommet du polygone 2 et la normale du polygone 1 la plus proche grâce aux région de voronoi, dans la suite, je vais faire la même chose mais pour un polygone en 3D, là il y aura en plus des sommets et des arrêtes, des faces!
Rechercher la région pour un polygone en 3D.
La technique vue ci-dessus n’est pas suffisante pour un polygone à 3 dimensions, en effet, observer l’image ci-dessous.
Par rapport au polygone 2D vu ci-dessus, on a 1 nouvelle région : celle des faces.
On peut remarquer que cette région est formée par 3 plans : ceux former par les côtés du triangle ABC sur le dessin.
Les normales des arrêtes du triangle pointeront toujours vers l’extérieur du triangle, on peut donc, grâce à ces normales, facilement trouvé les équations des plans formé par les arrêtes du triangle. (En prenant le centre du triangle et la normale de chaque arrête du triangle)
Le point P est dans la région de la face triangulaire lorsque, pour tout les plans des arrêtes du triangle, le point se trouve du même côté. (C’est à dire toujours du côté opposé aux normales des plans!)
Pour détecter si le point est dans la région d’une arrête du polygone 3D, la technique est la même que celle utilisée ci-dessus.
Voila désormais on sait comment trouver dans quel région se trouve le point susceptible d’entrer en collision, maintenant, il va détecter si il y a collision ou pas.
Collision entre un point et un polygone.
Il y a deux cas possible, soit le polygone est plat, soit il ne l’est pas.
ODFAEG possède une fonction permettant de récupérer l’index de la face ou l’arrête ou le point situé dans la région ou est susceptible d’avoir lieu la collision, cette fonction s’appelle checkNearestVertexFromShape.
Elle fonctionne comme ceci : Si la collision est susceptible d’avoir lieu sur un sommet du polygone alors elle retourne l’index du sommet et l’index de l’arrête et de la face vaut -1.
Si la collision est susceptible d’avoir lieu sur une face du polygone, alors elle retourne -1 et donne l’index de la face.
Sinon, même chose mais elle retourne l’index de l’arrête.
Pour un polygone plat ceci n’est pas très compliqué :
Si aucune face n’est renvoyée ça veut dire que le point n’est pas dans le triangle vu qu’il n’est pas entre les plans formé par les normales des arrêtes du triangle.
Sinon, il suffit de vérifier si le point est sur le plan formé par le triangle, si oui, alors le point est dans le triangle, sinon il ne l’est pas.
Pour un polygone non plat, il faut récupérer l’index du sommet de la face ou bien de l’arrête la plus proche, si c’est un sommet, c’est facile, il suffit de comparer la distance entre le sommet et le centre et le point et le centre, et si cette dernière est plus petite ça signifie que le point est dans le polygone.
Si c’est une face, cela est un peu plus compliqué, regardons l’image suivante :
Soit a qui est notre point, d’abord il faut trouver ec, ça, c’est simple, il suffit de projeter la bissectrice de la face la plus proche du point a sur la normal de cette même face.
Ensuite, je recherche b, pour cela il suffit de projeter ac sur le vecteur bc.
Comme les triangles rectangles cde et abc sont proportionnels, ont peut appliquer le théorème des rapport c’est à dire que distance bc / distance ec = distance cd / distance ac!
Il est donc facile de savoir si le point est dans le polygone, si c’est la cas alors la longueur du vecteur bc est inférieur à la longeur du vecteur ec!
Si c’est une arrête, j’applique le même procédé mais avec la normale et la bissectrice de l’arrête du polygone!
Et voila, ce n’est pas très compliqué, la difficulté ce situe surtout au niveau de la visualisation du problème, en effet, il n’est pas simple de représenter tout cela sur des feuilles de papier ou bien à l’écran, que ça soit aussi bien avec des logiciels pour faire de la 2D ou bien de la 3D.
Intersection polygone vs polygone.
Là, c’est plus compliqué car il y a 4 cas possibles!
Soit les 2 polygones sont plat, ou bien ils ne le sont pas, ou bien l’un est plat et l’autre ne l’est pas, pour ces différents cas de figure, il va falloir faire à chaque fois un test de collision différent.
Dans le cas ou les deux polygones sont plat, il faut vérifier si il y a au moins un point parmi les deux polygones qui est dans la région d’une face de l’autre polygone, si il n’y en a pas ça veut dire que les deux polygones ne sont pas en collision.
Il y a plusieurs cas possible, soit il y a deux faces, qui sont chacune dans la région d’un point, dans ce cas il suffit de récupérer les sommets de ces deux faces et de faire un test d’intersection entre les deux triangles les plus proches.
Ou bien il y a une face et une arrête, dans ce cas il suffit de faire un test d’intersection entre le triangle et l’arrête la plus proche.
Si l’un des deux polygones n’est pas plat, on fait la même chose mais en vérifiant en plus si les points du triangle ou du segment le plus proche de la forme plate est dans la forme non plate. (Car un triangle pourrait très bien être complètement à l’intérieur d’un polygone)
Si les deux triangles ne sont pas plat, il faut chercher quel est la distance la plus courte entre les sommets/arrêtes ou faces les plus proches et les points (une fonction de ODFAEG donne cette distance), et suivre le même raisonnement que le test point/polygone 3D!
Je ne vais pas m’étendre sur le sujet ici, car, un algorithme est plus parlant qu’un long discours ou bien qu’une image pour ce cas là.
Maintenant il ne reste plus qu’à savoir comment faire pour détecter les intersections triangles vs triangle et triangle vs segment.
Intersection triangle vs triangle.
L’intersection triangle vs triangle n’est pas très compliquée à détecter, il suffit de prendre le plan formé par le premier triangle et les côtés du second triangle et de tester si un côté du second triangle est en intersection avec le plan du premier triangle, mais attention, un plan est infini, il faut donc aussi tester si l’un des côtés du premier triangle est en intersection avec le plan formé par le second triangle.
Si oui, alors ça signifie que les deux triangles sont en intersection, sinon, ils ne sont pas en intersection.
Voici ce que donne l’algorithme : (soit deux triangles de normale n1, n2 et de point a1, a2 a3 et b1, b2 et b3)
1./ Plan p (n1, a1)
1.1/ si p intersecte côté b1 b2 ou p intersecte côté b2 b3 ou p intersecte côté b3 b1
Plan p2(n2, b1)
1.1.1/ si p2 intersecte côté a1 a2 ou p2 intersecte côté a2 a3 ou p2 intersecte côté a3 a1 alors
retourner vrai.
/1.1.1 fin si.
1.1/ fin si
retourner faux.
1./
Je pourrai même encore simplifier en faisant une seule condition!
Intersection rayon/plan.
La formule est la suivante :
d = n dot dir (ou n est la normale du plan et dir la direction du rayon et dot le produit scalaire.)
si d vaut 0 ça veut dire que le rayon est parallèle au plan, il y a donc deux cas à vérifier :
soit le rayon est dans le plan, pour le savoir il suffit de substituer le point d’origine du rayon dans l’équation du plan p : a * p.x + b * p.y + c * p.z + d et si ce résultat vaut 0 ça veut dire que le rayon est dans le plan donc il est en intersection avec le plan, sinon, il n’est pas en intersection avec le plan.
Pour trouver l’équation du plan, c’est simple, a b et c sont les coordonnées de la normal du plan p, et d se trouve grâce à un point p appartenant au plan, d se trouve comme ceci :
d = -(a * p.x + b * p.y + c * p.z)
si d est différent de 0 ça signifie que le rayon intersecte le plan, et donc il faut chercher ou à lieu l’intersection sur le rayon, pour ce faire, voici la formule à appliquer :
intersection = n dot (p – orig) / d (ou n est la normale au plan, p un point appartenant au plan, le point d’origine du rayon et d, la valeur qu’on vient de trouvé ci-dessus)
Voilà maintenant pour savoir si le côté du triangle intersecte le segment il suffit juste de vérifier si i est compris ente 0 et 1!
Intersection rayon/triangle.
Là aussi il y a plusieurs cas possible, si le rayon est parallèle au plan mais n’est pas dans le plan, alors il n’y a pas d’intersection, si le rayon est compris dans le plan, alors il y a deux intersections, on peut les trouver en recherchant les intersections entre le rayon et les segments des triangles.
Intersection rayon/segment.
La formule est la suivante :
soit da la direction du rayon, db la direction du segment et dc le vecteur entre les origines du segment et du rayon.
si dc dot (da cross (db)) vaut 0 ça signifie que le rayon et le segment ne sont pas sur le même plan, et donc, il n’y a pas d’intersection sinon :
s = dc cross (db) dot (da.cross (db)) / longueur au carré de da cross (db)
Ceci va donné l’intersection par rapport au rayon, mais attention, ici c’est une intersection rayon segment donc il faut aussi rechercher l’intersection sur le segment :
t = dc cross (da) dot (da.cross (db)) / longueur au carré de da cross (db)
Alors, si s est positif et que t est compris entre 0 et 1 ça signifie que le rayon est en intersection avec le segment.
Pour une intersection segment segment il suffit de vérifier si s est compris entre 0 et 1 et t également et pour une intersection rayon/rayon il suffit de vérifier si s est positif.
Mais ce n’est pas tout, ceci ne fonctionne que si le rayon est dans le plan formé par le triangle, si ce n’est pas le cas, il va falloir rechercher en utilisant un autre algorithme, et cet autre algorithme est extrêmement connu et s’appelle, l’algorithme de raytracing!
Voici une page qui explique brièvement le principe :Raytracing
Voilà, grâce à cet article, vous savez comment détecter des intersections entre polygones convexes en 2D et en 3D, de manière optimisée.
ODFAEG garde les distances et les longueurs élevées au carré pour des raisons d’optimisation lorsqu’il ne s’agit que de faire de la comparaison entre des distances et des longueurs.
Sur la page suivante, je vais vous présenter comment détecter des intersections entre formes simples. (Sphères/cercles orienté, Ellipses/ellipsoïdes orientée et boîtes/boîtes orientée)
Mon dev blog. 