Discussion :

[Luigicube]

Bonjour tout le monde !

Je cherche une solution (la plus simple possible) pour savoir si 2 polygones convexes se touchent.
J'ai plusieurs hypothèses :
- Les polygones sont plans
- Un des polygones est dans un plan fixe en X, Y ou Z (horizontal ou vertical), mais ça ne devrait pas changer grand chose
- L'autre polygone n'est pas dans un plan fixe
- Ils sont convexes comme déjà mentionné

J'ai rencontré pas mal de méthodes, certaines pour du 2D, dont Separating Axis Theorem. J'ai donc cherché SAT pour du 3D et je suis tombé sur http://www.gamedev.net/topic/606539-...nvex-polygons/ cette discussion.

Est-ce que la méthode proposée par "taz0010" vous paraît pertinente ? Elle me semble pas mal, mais j'ai un doute et je ne trouve pas d'autre trace sur le web.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
1. loop through each line segment that makes up Polygon A, checking whether each segment intersects with Polygon B's plane. If no segments intersect, break early and return Polygon B's plane as the separating plane.
2. loop through each line segment that makes up Polygon B, checking whether each segment intersects with Polygon A's plane. If no segments intersect, break early and return Polygon A's plane as the separating plane.
3. If both 1 and 2 did find intersections, see if the two line segments overlap. If they do overlap, there is an intersection. Splitting one of the polygons down the line of intersection will resolve the intersection.
4. If the segments did not overlap, then the polygons do not intersect. To construct the separating plane, we use the cross product of the normals of the two planes as the normal, and for the location we select a point (let's say half way between) the two line segments (though any point within this region should be valid).

Merci d'avance,

Luigi

[N_I_C_S]

Oui, l'algo me semble correct pour des formes convexes, les 2 segments à tester représentent chaque "tranche" d'un poly traversant le plan de l'autre, leur intersection signifie l'intersection des polys. Et ça peut être bien accéléré si on sait qu'un poly est sur les axes .

[Luigicube]

Merci d'avoir pris le temps de répondre NICS !

Quand tu dis que ça peut être accéléré lorsqu'un des polygones est sur les axes, tu veux dire qu'un des polygones est dans le plan {X;Y}, {Y;Z} ou {X;Z} ?
C'est le test d'intersection qui peut être accéléré (simple comparaison des coordonnées qui ne sont pas sur les axes) ?

[N_I_C_S]

De rien, je passais par là ^^ .

Quand tu dis que ça peut être accéléré lorsqu'un des polygones est sur les axes, tu veux dire qu'un des polygones est dans le plan {X;Y}, {Y;Z} ou {X;Z} ?

Oui, déjà trouver les 2 points d'intersection du polygone "quelconque" est très rapide car la distance (point-plan sur les axes) est immédiate.
Et le test final d'intersection des 2 segments peut être ramené à un test 2D, dans le plan sur les axes (car les droites portant les 2 segments ne peuvent pas se "rater").

[Luigicube]

Si quelqu'un d'autre passe par là, est-ce-que quelqu'un voit un cas où ça ne marche pas dans le cas où un des polygones est concave ?

Edit : En y réfléchissant, je vois un cas probable... lorsqu'un des polygones 'englobe' l'autre.

[N_I_C_S]

Et ben j'étais encore là...

hmm, pour un poly concave à priori la différence est que tu peux avoir plusieurs segments d'intersection avec le plan du poly convexe. Il faut alors tous les tester,
ça revient à tester plusieurs zones convexes du poly concave.
Et pour reconstituer les segments avec les points d'intersection, prendre les paires de points dans l'ordre : 1ere segment, 2e espace, 3e segment, etc...
Le nombre de paires ne peut qu'être...impair .

Je fais du zèle, désolé ^^ .