Comment résoudre les collisions de formes composées en utilisant SAT?

16

SAT est un moyen décent de déterminer les collisions entre des polygones convexes arbitraires. Vous obtiendrez même le vecteur nécessaire pour résoudre une collision.

Pour résoudre les collisions entre des formes complexes (non convexes), je pensais à une sorte de forme composée qui se compose de plusieurs polygones convexes. Si une collision se produit dans la phase large (par exemple, cercle contre cercle ou AABB contre AABB), la collision serait résolue en vérifiant chaque polygone de la forme composée par rapport à chaque polygone de l'autre forme composée.

Je me demande quelle est la meilleure façon de séparer les objets? Une approche naïve serait de simplement prendre le vecteur avec la plus grande ampleur et de l'utiliser pour la séparation. Dans l'image suivante, ce serait V 2

Exemple 1 de SAT

Cependant, si les vecteurs de séparation pointent dans des directions différentes, la collision ne peut pas être résolue immédiatement et peut nécessiter plusieurs itérations. Donc, dans l'image suivante, nous séparerions en utilisant V 1 et dans une autre itération par V 2 (ou quelque chose de proche de V 2 , car la forme se serait déplacée de la quantité de V 1 ).

Exemple 2 de SAT

Cette approche échouera avec des vecteurs de séparation qui pointent dans la direction opposée les uns des autres ou dans un cas comme indiqué dans l'image suivante:

Exemple 3 de SAT

Ici, nous répéterions sans cesse entre l'État de gauche et l'État de droite.

Donc, pour poser une vraie question ici: Quelle est une approche raisonnable de ce problème? Je suppose que l'utilisation de polygones composés pour des formes complexes est une idée raisonnable, mais je me demande vraiment comment résoudre les collisions dans ce cas? Comment puis-je détecter une impasse comme indiqué dans la troisième image?

bummzack
la source
Pouvez-vous préciser à quoi vous voulez utiliser le vecteur?
Le
@Will Le vecteur doit être utilisé pour résoudre la collision, afin que les formes ne se chevauchent plus. Je pouvais donc déplacer l'objet jaune par le vecteur résultant et les deux objets ne se heurteraient plus.
bummzack

Réponses:

7

Je pense que vous essayez peut-être d'insérer une clé carrée dans un trou rond en appliquant SAT de la manière dont vous êtes ici. De toute évidence, il n'est pas conçu pour les collisions concaves-concaves, et bien que je salue vos efforts pour l'adapter à cette fin, il y a des considérations qui rendent cela improbable.

Le réalisme

L'impulsion angulaire et ses effets d'entraînement sont le nom du jeu ici.

L'ordre des points de contact est important pour une résolution de collision réaliste. Dans le monde réel, un de ces points va toujours frapper avant un autre. Et ce n'est qu'en émulant cet ordre de contact et les résultats de chaque "sous-collision" représentée par cela, que vous pouvez vous attendre à obtenir un résultat réaliste dans la simulation. C'est l'une des raisons mêmes pour lesquelles vous divisez votre concave en convexe, en premier lieu - cela permet la détection par morceaux de la partie qui a frappé en premier. Bien sûr, cela peut également être imité selon mon commentaire sous la rubrique "Moins de réalisme".

Vos appareils convexes se combinent pour donner à l'objet à la fois son contour et son centroïde (et bien sûr, dans des simulations plus complexes, chaque appareil peut également affecter la densité différemment). La raison pour laquelle je mentionne ceci est que pour résoudre des collisions de manière réaliste, vous devrez calculer non seulement une impulsion linéaire mais également angulaire, après chaque "sous-collision" de vos points de contact. Ce n'est pas aussi simple que la «séparation» de base que vous appliquez avec SAT.

Cela change alors complètement la nature de votre problème, car comme vous pouvez le voir, il est inutile d'obtenir et d'essayer d' utiliser 2 points de contact ou plus, car ce n'est vraiment que le premier qui compte. Une fois que vous avez résolu le premier en termes d'impulsion linéaire et angulaire, vous devrez recalculer pour d'autres collisions, car les orientations de chaque objet auront changé. De plus, la détection de chaque contact individuel dans l'étape peut alors ou non avoir besoin d'être effectuée au cours de cette même étape - en fonction de la synchronisation entre les contacts lorsque le premier point de contact des objets touche, une impulsion linéaire et angulaire ultérieure est appliquée, deuxième contact point de contact, etc.

Moins de réalisme

Bien sûr, en supposant que vous n'êtes pas du tout intéressé par la résolution de l'impulsion angulaire, alors le mieux que vous puissiez faire avec SAT devient essentiellement exactement ce que vous feriez si vous enveloppiez ces polygones comme convexes en utilisant quelque chose comme Graham's Scan: Écarter par la seule séparation vecteur. En d'autres termes, cela n'a pas de sens d'essayer de résoudre trois vecteurs en tandem, comme vous l'avez démontré. C'est le plus gros du peloton qui compte.

MODIFIER en réponse à votre question

Ce que vous devez faire si vous souhaitez une approche simpliste est la suivante:

  • Déterminez la bonne direction de déplacement. Cela se fait le plus facilement en décortiquant chaque coque et en déterminant les normales à l'axe de séparation.

  • Vous devez maintenant déterminer l' amplitude du déplacement . Pourquoi ne pouvons-nous pas simplement utiliser l'ampleur donnée par SAT? Parce que si vous y réfléchissez, les profondeurs d'interpénétration seront potentiellement plus grandes pour les coques convexes que pour leurs coques concaves assorties - pensez à deux E avec leurs dents l'une dans l'autre! Comme vous l'avez fait ci-dessus, recherchez tous les points de contact pour une étape donnée, mais trouvez-les parallèles aux normales d'axe, car c'est la bonne direction de déplacement. Déterminez maintenant lequel de ces vecteurs de chevauchement parallèles est le plus long. Déplacez-vous par celui-ci, jetez le reste et passez à l'étape suivante de la physique.

Ingénieur
la source
Je pense que je vois ce que tu veux dire. Donc, dans le scénario "moins de réalisme", je ne ferais pas qu'évaluer les vecteurs (les plus courts) donnés par SAT pour les polygones individuels, mais je devrais également tenir compte des autres chevauchements (plus grands) et, dans le pire des cas, utiliser la coque convexe?
bummzack
Voir (dernière) modification.
Ingénieur