Théorème d'axe de séparation avec plusieurs polygones?

9

J'essaie d'implémenter le théorème de l'axe de séparation en C #. J'ai une fonction qui peut calculer le vecteur de translation minimum entre deux polygones. Cependant, je n'arrive pas à créer une fonction qui calcule le vecteur de translation minimum entre un polygone et plusieurs autres polygones. Honnêtement, j'y travaille depuis des mois et je ne suis pas plus proche d'une solution et je n'ai pas pu trouver de solution en ligne. Il y a toujours quelques cas marginaux qui ne renvoient pas le bon résultat, ce qui entraîne des bogues de haute priorité dans mon jeu.

Voici des cas courants qui ne fonctionnent pas correctement:

cas de bord

Existe-t-il une solution bien connue à ce problème? Tout ce que je peux trouver, ce sont des gens qui disent "il suffit d'exécuter le SAT sur chaque polygone" mais cela produit rarement le vecteur de translation minimum .

Toute aide serait très appréciée.

collision-detection separating-axis-theorem user40698
la source
Une idée, que je n'ai jamais vraiment testée, est que certains axes de séparation - ceux qui vous déplaceraient latéralement dans un polygone adjacent - pourraient être signalés pour ne jamais être considérés comme le minimum. Ensuite, une sorte de test répété donnerait de bons résultats (éventuellement avec une sorte de FIFO et / ou de limite d'itération pour éviter de rester coincé dans une boucle).
Andrew Russell
Une version encore plus difficile à résoudre de cela est lorsqu'un bord d'une forme n'est que partiellement recouvert par un autre. Par exemple, dans l'image en haut à droite, si le carré du milieu s'étend vers la droite, pour être un rectangle plus grand. Ceci est similaire à la sortie d'un code que j'utilise, qui prend des dizaines de milliers de cellules occupées / non occupées et réduit cela à moins d'une centaine de formes de collision plus importantes
Richard Tingle

Réponses:

2

Idéalement, vous ne construisez pas votre environnement à partir de polygones. Vous le construisez à partir d' arêtes (que vous calculez peut-être à partir d'un ensemble de polygones). Dans votre premier exemple, par exemple, il n'y a qu'un seul bord diagonal; dans le dernier exemple, la boîte repose sur un seul bord horizontal.

Le fait que votre éditeur ou vos outils utilisent des formes individuelles plus petites pour créer un niveau ne devrait pas avoir d'incidence sur l'exécution.

Une approche légèrement plus simple supprimerait simplement les bords "intérieurs" des formes de base. Pour votre dernier exemple, il y a deux bords entre les cases "sol"; ignorez-les pendant la détection de collision.

Vous pouvez trouver de meilleures images et des idées d'implémentation en lisant la section 4.5 (bords et chaînes de bords) dans la documentation de Box2D .

Sean Middleditch
la source
2
L'utilisation d'arêtes (en particulier les arêtes, c'est un peu mieux avec les chaînes d'arêtes) présente l'inconvénient majeur qu'il devient très facile pour les objets physiques de glitch à l' intérieur de la géométrie de niveau.
Andrew Russell
1
@AndrewRussell: ces problèmes sont évités avec les correctifs de tunnellisation habituels. Assurez-vous que vos objets en mouvement ont un volume / une surface assez décent, gardez leur vitesse maximale par image suffisamment basse pour qu'ils ne puissent pas bouger de plus de la moitié de leur dimension la plus courte (ou montez-la plusieurs fois si vous en avez besoin pour vous déplacer plus rapidement), évitez crevasses vraiment tranchantes et telles dans votre géométrie de niveau, répétez la résolution plusieurs fois jusqu'à ce que vous convergiez vers un emplacement final "sûr", etc.
Sean Middleditch