Résolution de collision en cas de collision avec plusieurs objets

15

J'ai des objets statiques et des objets mobiles. Les collisions sont détectées à l'aide du théorème de l'axe de séparation.

Par exemple, dans cette situation, j'ai deux objets statiques (en rouge):

entrez la description de l'image ici

et un objet mobile entre les deux:

entrez la description de l'image ici

Mon algorithme est capable de calculer la collision entre deux de ces objets, et il crache également un vecteur de résolution parfaite (c'est-à-dire un vecteur à déplacement minimum) à la collision.

Ainsi, par exemple, lorsque je vérifie la collision entre le rectangle vert et le rectangle rouge droit, l'algorithme crache un vecteur qui me dit comment je dois déplacer le rectangle vert pour résoudre la collision:

entrez la description de l'image ici

Remarquez que je viens de dessiner cela rapidement dans MSPaint, donc dans cette image, il se pourrait que le vecteur de traduction minimum pousse le rectangle vert en haut, mais je vais supposer ici que le pousser vers la gauche / le droit est en fait plus court.

La manière générale d'aborder cela serait de résoudre seulement la collision d'une collision par trame, au lieu de toutes à la fois. Mais dans mon cas, cela entraînerait une bascule:

Tout d'abord, le solveur détecte deux collisions mais ne résout que la collision entre le rectangle droit et le rectangle vert:

entrez la description de l'image ici

Ensuite, dans l'image suivante, il ne détecte qu'une seule collision entre le rectangle rouge gauche et le rectangle vert, et le résout:

entrez la description de l'image ici

Comme vous pouvez le voir, cela ne résout pas réellement la collision (par exemple en poussant le rectangle vert vers le haut), et au lieu de cela, bascule simplement entre les deux états à l'infini.

Comment puis-je résoudre ça?

TravisG
la source
Vous utilisez des rectangles dans votre exemple. Votre algorithme de collision ne résout-il la collision que sur un seul axe? Si c'est le cas, il est logique que le comportement que vous décrivez se produise.
chaosTechnician
Non, il peut les résoudre avec n'importe quel type de formes sur tous les axes possibles (pas seulement des rectangles, ils sont juste les plus faciles à dessiner avec MS paint: P) et il trouvera toujours le vecteur le plus court qui existe qui sépare les deux objets .
TravisG
+1 Bonne question. J'ai supprimé la "balise" (2D) du titre, c'est quelque chose que vous devez éviter (voir méta ).
bummzack

Réponses:

7

Selon ce que vous essayez d'atteindre (précision physique élevée ou simulation en temps réel suffisamment proche), vous pouvez essayer d'utiliser des contacts spéculatifs.

Voici les détails: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

Il décrit dans cet article ce que vous devez savoir pour l'implémenter, et c'est très simple par rapport à d'autres approches (telles que le lancer de sphère puis le tri des résolutions de collision par temps d'impact).

Si vous avez besoin / voulez plus, vous pouvez acheter son code source pour (IIRC) 7 $.

Voici une vidéo de mon implémentation en 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

Notez la stabilité de la simulation avec une seule itération. Vous pouvez facilement utiliser plusieurs itérations par image pour résoudre plusieurs collisions dans un état stable, ce qui serait plus précis.

Olhovsky
la source
2

Vous pouvez d'abord calculer tous les vecteurs nécessaires pour résoudre chaque collision, puis calculer une résultante à partir d'eux.

Le seul cas où cela peut vous octroyer est si ces vecteurs s'annulent, comme dans votre exemple. Dans ce cas, la collision ne peut pas être résolue.

Mihai Maruseac
la source
Ajouter un petit vecteur aléatoire d'une magnitude d'environ epsilon * 10 aux collisions? L'arithmétique en virgule flottante devrait faire le reste.
Martin Sojka
2
Oui, cela peut fonctionner, je suppose. Mais cela peut aussi créer des mouvements instables.
Mihai Maruseac
1
J'espère que je pourrai toujours obtenir une réponse à ce sujet: le calcul d'une résultante corrige le problème de la "boucle infinie", mais réintroduit le problème de la "fissure", où se déplacer en glissant sur un mur fait de tuiles de la même taille rend le corps coincé entre les "fissures" des carreaux. Existe-t-il un moyen de résoudre ces deux problèmes?
Vittorio Romeo
D'accord ... il n'y a pas de meilleure "bonne réponse" pour résoudre une collision de corps rigide impossible comme ça. Soit il tremble, soit vous autorisez un certain "flou" dans un ou plusieurs des objets.
david van brink
0

Si vous le regardez attentivement, cet état des objets est (ou devrait être) irréalisable.

Soit la forme rouge la plus à gauche la forme R1, et la forme rouge la plus à droite la forme R2. Que la forme verte soit G.

c'est-à-dire étant donné la taille et la géométrie des trois objets, et étant donné que tous les objets ne sont pas pénétrables:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

Maintenant, se résume à cela, si votre algorithme interroge vos objets un par un, c'est alors une question de concurrence, c'est-à-dire que dans un sens, l'algorithme est censé vérifier TOUS les objets en même temps, mais l'algorithme vous limite à faire objets et les traiter un à la fois ...

Si G est vérifié par rapport à R1 après avoir été vérifié par rapport à R2, alors G semble légalement être à droite de R1 (si G dit approche R1 avec la direction du vecteur <-1, -1> avec une amplitude (ou distance) arbitraire) ), car la vérification entre R1 et G le permet, et oublie la vérification entre R2 et G qui a été effectuée auparavant.

Une solution que vous pouvez faire est de collecter tous les vecteurs de déplacement minimum dans un tableau ou dans la structure de données que vous souhaitez, et en choisir un qui se révélerait légal pour TOUS les objets.

Notez qu'à une image donnée, l'objet (G par exemple) ne peut avoir qu'une seule direction. (oh mec, ça ressemble au boyband ...)

Liu Mao Hsing
la source