Quelle est la meilleure façon de gérer les collisions simultanées dans un moteur physique?

13

J'écris un moteur physique 2D en javascript afin de pouvoir en savoir plus sur la physique dans les jeux vidéo. Je le fais fonctionner correctement pour les collisions de corps rigides, sauf si un corps entre en collision avec deux ou plusieurs autres corps en même temps.

Actuellement, pour chaque paire de corps en collision (A, B), je modifie leurs vitesses et vitesses angulaires en fonction de l'impulsion de collision, et je les écarte les unes des autres afin qu'elles ne pénètrent pas. Mais alors la détection de collision et les calculs d'impulsion pour d'autres collisions impliquant A seront erronés.

Quelles approches puis-je explorer pour que mon moteur fonctionne avec plus de 3 objets entrant en collision les uns avec les autres?

Came
la source
2
Connexes: gamedev.stackexchange.com/questions/15836/… et gamedev.stackexchange.com/questions/26181/… et je suis sûr qu'il y a plus, je ne trouve tout simplement pas le moment.
MichaelHouse

Réponses:

11

J'utilise l'approche suivante (similaire à l'algorithme de fractionnement de masse de Tonge http://www.richardtonge.com/ ):

  • détecter toutes les paires en collision dans votre scène / contexte. Soit (A, B) une telle paire. Appliquez une idée de division fantôme / masse: si A est en contact avec M corps et B est en contact avec N autres corps, définissez temporairement la masse de A à m_A/Met celle de B àm_B/N
  • calculer les contributions des forces de réaction / restitution pour chaque paire (A, B) et stocker ces contributions dans les propres accumulateurs A et B
  • calculer les vitesses de restitution à partir des impulsions (comme vous l'avez indiqué) et les stocker de la même manière (en tant que résidus de vitesse deltaV dans leurs propres accumulateurs pour chaque paire (A, B))
  • calculer les déplacements de pénalité (encore une fois, accumuler les déplacements, ne les appliquez pas instantanément!)
    • réinitialiser les masses de tous les corps précédemment désignés comme parties dans les paires de collisions ( m_A = m_A * Met m_B = m_B * N)

Cette approche est similaire à la façon dont l'algorithme itératif de Jacobi fonctionne avec des systèmes d'équations simultanées linéaires. Et ce n'est pas garanti de converger, mais dans mon simulateur il fait le travail assez facilement .. en 3D (oui, une dimension supplémentaire ajoute deux fois la difficulté!).

Attention : corriger les positions et les vitesses uniquement après la fin de votre phase de détection / manipulation de collision! De cette façon, vous mettez simultanément à jour vos acteurs en collision. De plus, les forces de restitution doivent être prises en compte la prochaine fois lors de l'intégration pour les positions et les vitesses.

EDIT: Eh bien, je suppose que vous utilisez la méthode d'intégration Verlet déjà abusée (celle-ci est devenue un nom familier chez les amateurs de gamedev). Dans ce spectre de gestion et d'intégration des collisions, vous voudrez peut-être jeter un œil ici .

MISE À JOUR: Certaines des informations sur la façon d'aborder la collision (et l'auto-collision d'ailleurs) peuvent être trouvées dans ces articles:

L'approche que j'ai proposée n'est pas à long terme une contribution originale, de nombreux jeux l'utilisent avec des résultats plausibles et elle a été mieux utilisée par Jakobsen dans son moteur de jeu Hitman.

D'après une expérience quelque peu pratique, les forces de pénalité (similaires à des ressorts linéaires ou exponentiels obtenant leur entrée de la distance de pénétration) ne résolvent pas correctement les pénétrations lorsque d'autres forces des corps qui entrent en collision parviennent à être plus grandes qu'eux. C'est pourquoi j'ai choisi de combiner trois approches (presque redondantes): les forces de réaction newtoniennes (vous poussez le mur, le mur repousse), les vitesses dérivées des impulsions (les boules de billard entrent en collision) et une approche non naturelle "éloigne les corps géométriquement les uns des autres " Solution. Ensemble, ils semblent tout fournir: se débarrasser de la plupartvilains artefacts d'interpénétration, les corps en collision ont tendance à interagir les uns avec les autres sur le long terme (en raison des vitesses et des forces de restitution - au moins les forces qui avaient tendance à faire glisser les corps dans un scénario de collision sont annulées et les corps rebondissent les uns sur les autres) . Enfin, pour mieux comprendre ces concepts simples mais courants, je suggère d'analyser ces diapositives .

Mon épithète de «méthode abusée» décrivant les étapes d'intégration de Verlet vise une croyance de la culture populaire selon laquelle c'est le Saint Graal des méthodes d'intégration. Il est juste légèrement meilleur que son cousin Symplectic Euler (également appelé par certains Euler semi-implicite). Il existe des méthodes d'intégration beaucoup plus compliquées (et toutes portent le nom implicite). De puissants moteurs de jeu les utilisent, mais les développeurs indépendants n'ont pas le temps de les expérimenter depuis que Verlet, lorsqu'il est réglé sur un scénario spécifique, fait vraiment des merveilles. De plus, il n'y a absolument aucune méthode d'intégration capable de gérer des contraintes rigides sans un peu de tricherie (ne peut pas trouver le lien, mais le document auquel je fais référence devrait s'appeler "X.Provot -" Contraintes de déformation dans une masse modèle à ressorts pour décrire le comportement d'un tissu rigide "

teodron
la source
Merci (+1)! Que sont la «vitesse de restitution» et les «déplacements de pénalité»? Aussi, pourquoi dites-vous que l'intégration de Verlet est «abusée»? Pensez-vous que c'est une mauvaise méthode à utiliser?
Cam
Les vitesses de restitution sont exactement les vitesses que vous obtenez des impulsions, la seule différence est que je les calcule en tant que résidus (c'est-à-dire que je stocke la différence entre cette vitesse basée sur les impulsions et la vitesse actuelle tout en gardant la vitesse actuelle intacte pour les calculs ultérieurs). Les déplacements de pénalité sont des vecteurs dont la longueur est déterminée par l'interpénétration de deux objets et c'est le vecteur de longueur minimale qui peut traduire un objet complètement à l'extérieur de l'autre. J'ajoute généralement un tel déplacement à chaque objet en divisant la longueur par 2).
teodron
1
Brillante réponse! J'ai une autre question cependant. Disons que j'accumule les vitesses de restitution, ne s'ajouteront-ils pas à un nombre très peu réaliste? Si je traite chaque collision avec l'objet A séparément et additionne simplement les effets sur chaque objet, A ne verra-t-il pas son impulsion se propager entre les objets? Au lieu de cela, une impulsion complète sera appliquée à chacun, ce qui me semble intuitivement erroné
Cam
C'est une très bonne question .. d'un point de vue, il semble plausible que les impulsions contribuent de manière additive à la vitesse résultante. Voici mon raisonnement (peut-être défectueux!): Imaginez trois boules de billard / snooker entrant en collision. L'un d'eux devrait recevoir des contributions des deux autres de cette manière additive. Au début, je pensais peser ces contributions et calculer une moyenne pondérée pour la vitesse finale, mais comme je voulais des résultats rapides, j'ai sauté cette idée. Dans l'ensemble, la balle en collision doit obtenir des contributions de vitesse des deux autres. Peut-être qu'un manuel de lycée peut aider.
teodron
3
Peut-être que je ne comprends pas ce que vous avez expliqué, car l'exemple suivant me concerne toujours: considérons un rectangle horizontalement long tombant droit vers le bas, et supposons que le sol est dentelé (donc composé de plusieurs triangles côte à côte). S'il y a n triangles, en utilisant votre méthode cumulative, le rectangle rebondira à n fois la vitesse qu'il devrait! Comment résoudre cette situation?
Cam
1

Je suggère qu'au lieu de changer les vitesses, vous modifiez les forces agissant sur un objet. Ne pas les «pousser», plutôt, faites-le en douceur et en utilisant du code déjà existant. En faisant cela, les corps ne changeront pas immédiatement (et rapidement, je suppose) leurs vitesses.

Consultez Box2DJS pour un exemple: http://box2d-js.sourceforge.net/index2.html .

jcora
la source
-1

J'ai résolu analytiquement une équation d'impulsion pour des groupes de corps en collision. Le seul problème que j'ai rencontré était le manque de variables pour trouver la force d'interaction relative entre les contacts dans un groupe, que j'ai remplie d'intersection de profondeur de corps.

La solution pour les contacts de groupe n'est pas beaucoup plus difficile que le contact unique. Malheureusement, j'ai perdu un papier avec des calculs, donc incapable de le partager ici.

Edit: Probablement, j'ai trouvé quelque chose comme ça /physics/296767/multiple-colliding-balls

George Vinokhodov
la source