Il s'agit de la troisième partie de notre série en trois parties sur la physique des jeux vidéo. Pour le reste de cette série, voir:

Partie I: Une introduction à la dynamique des corps rigides
Partie II: Détection de collision pour les objets solides

---

Dans la première partie de cette série, nous avons vu comment le mouvement libre de corps rigides peut être simulé. Dans la deuxième partie, nous avons vu comment rendre les corps conscients les uns des autres grâce à des tests de collision et de proximité. Jusqu'à présent, cependant, nous n'avons toujours pas vu comment faire interagir réellement les objets les uns avec les autres. Par exemple, même si nous savons comment détecter les collisions et déterminer de nombreuses informations utiles à leur sujet, nous ne savons toujours pas quoi faire avec ces informations.

En d'autres termes, nous avons seulement décrit simulations sans contrainte . La dernière étape pour simuler des objets réalistes et solides consiste à appliquer contraintes , définissant des restrictions sur le mouvement des corps rigides. Quelques exemples de contraintes sont les articulations (comme les joints à rotule et les articulations de charnière), et contraintes de non-pénétration . Ce dernier type est ce qui est utilisé pour résoudre les collisions , en imposant un comportement qui empêche les corps de s'interpénétrer et les fait rebondir les uns sur les autres de manière réaliste.

Dans cet article, nous discuterons des contraintes d'égalité et des contraintes d'inégalité dans la physique des jeux vidéo. Nous les décrirons d'abord en termes d'approche basée sur les forces, où les forces correctives sont calculées, puis en termes d'approche basée sur les impulsions, où les vitesses correctives sont calculées à la place. Enfin, nous allons passer en revue quelques astuces intelligentes pour éliminer le travail inutile et accélérer le calcul.

Cet épisode impliquera des calculs plus lourds que la partie I ou la partie II, alors soyez averti. Si vous avez besoin de rafraîchir votre calcul, allez ici sur Khan Academy . Pour une revue des principes fondamentaux de l'algèbre linéaire, vous pouvez vous référer au annexe de la partie I , et pour l'algèbre linéaire plus complexe, telle que la multiplication matricielle, Khan Academy livre à nouveau . Wikipédia propose également d'excellents articles sur calcul et algèbre linéaire .

Que sont les contraintes?

Les contraintes sont essentiellement des règles qui doivent être satisfaites lors de la simulation, telles que 'La distance entre ces deux particules ne doit pas être supérieure à 2' ou «Ces deux points de cette paire de corps rigides doivent coïncider à tout moment» . En d'autres termes, une contrainte supprime degrés de liberté à partir d'un corps rigide. A chaque étape de la simulation, on peut calculer des forces ou impulsions correctives qui, lorsqu'elles sont appliquées sur les corps, vont les rapprocher ou les écarter, ainsi leur mouvement sera limité et les règles imposées par les contraintes resteront satisfaites.

En pratique, une contrainte est définie en termes de fonction de comportement ou fonction de contrainte C , qui prend l'état d'une paire de corps comme paramètres (par exemple, position et orientation) et produit un nombre scalaire. Lorsque la valeur de cette fonction est dans la plage acceptable, la contrainte est satisfaite. Ainsi, à chaque étape de la simulation, il faut appliquer des forces ou des impulsions sur les corps rigides pour tenter de garder la valeur de C dans la plage autorisée.

Un exemple: les contraintes d'égalité

Une classe courante de contrainte est connue sous le nom de contrainte d'égalité . Une contrainte d'égalité est une contrainte dans laquelle la seule valeur acceptable de C est zéro. Ainsi, à chaque étape de la simulation, on souhaite garder C aussi proche de zéro que possible. En d'autres termes, nous voulons minimiser C . Les contraintes d'égalité sont utilisées lorsque la position d'une particule ou d'un point doit toujours correspondre exactement à une condition prédéfinie. Un bon exemple est un joint à rotule, où deux corps rigides doivent toujours être connectés à l'emplacement du joint.

Prenons un exemple simple. Considérons une particule en deux dimensions, avec position p ( t ) = ( pX ( t ), pOui ( t )), qui est une fonction du temps qui donne la position de la particule à la fois t . Nous utiliserons la notation par points pour exprimer les dérivées du temps, ainsi, ṗ est le premier dérivé de p par rapport au temps, qui est la vitesse de la particule v ( t ), et p̈ est sa deuxième dérivée temporelle, ou c’est l’accélération.

Définissons une contrainte. Laisser C être la fonction de comportement suivante:

Cette fonction prend la position de la particule comme paramètre et affiche sa distance par rapport à l'origine moins l . Il sera nul chaque fois que la distance entre la particule et l'origine est l . Ainsi, cette contrainte a pour effet de maintenir la particule à une distance fixe l de l'origine, comme un pendule attaché à l'origine. Les valeurs de p qui satisfont C ( p ) = 0sont les positions juridiques de la particule.

Dans cet exemple, C est une fonction de seulement deux variables qui produit un scalaire, nous pouvons donc facilement le tracer et examiner certaines de ses propriétés. Si nous définissons la distance de contrainte sur 2 (c'est-à-dire, l = 2), puis le graphique de C ressemble à ça:

C’est un cône à l’envers. L'anneau bleu contient les points où C = 0, qui sont les racines de C . Cet ensemble de points est connu sous le nom de contrainte hypersurface , et il contient toutes les positions juridiques de notre particule. L'hypersurface de contrainte est unes-surface dimensionnelle, oùsest le nombre de variables de C .

Les flèches vertes montrent dégradés de C , évalué autour de l'hypersurface, et indique les directions pour positions illégales de notre particule, où C ≠ 0. Si la particule se déplace le long de ces lignes de quelque manière que ce soit, soit dans la direction positive (loin de l'origine), soit dans la direction négative (vers l'origine), elle rompra la contrainte. Ainsi, les forces que nous générons pour pousser la particule dans des positions légales seront parallèles à ces lignes.

Bien que cet exemple simple ne comporte que deux variables, la plupart des fonctions de contrainte en ont plus, ce qui rend difficile de se représenter à quoi elles ressemblent. Mais le principe reste le même. A chaque étape, il faut générer des forces de contrainte parallèles au gradient de C à l'hypersurface.

Calcul des forces de contrainte

Ce serait bien de simplement définir p tel que C est toujours exactement zéro. En pratique, cela entraînera un comportement irréaliste, car notre particule sautera et tremblera autour de l'hypersurface. Garder C au plus près de zéro tout en conservant un comportement réaliste, une approche intuitive consiste à utiliser dynamique basée sur la force , et calculez la force nécessaire à appliquer à la particule afin qu'elle satisfasse les contraintes sans enfreindre les lois du mouvement de Newton.

Pour calculer la force de contrainte, nous devrons avoir une compréhension des accélérations et des vitesses admissibles de la particule. Pour cela, il faut obtenir les dérivés de C par rapport au temps.

Nous voulons nous assurer que la valeur de C restera égal à zéro et restera inchangé tout au long de la simulation. Cela signifie que la première fois dérivée, C. , doit être égal à zéro.

De même, pour C. pour rester fixe à zéro, la deuxième dérivée, C̈ , doit également être égal à zéro.

Nous n'avons pas à contraindre d'autres dérivés de C , parce que la deuxième dérivée est l'endroit où nos forces de contrainte seront appliquées.

Déterminons ces dérivés. Notre définition actuelle de C a une racine carrée, ce qui rend la différenciation un peu difficile. Nous pouvons réécrire C cependant, en utilisant des distances au carré:

Cela ne modifie pas la propriété qui C sera nul lorsque la distance entre la particule et l'origine est l . À partir de là, nous pouvons obtenir le premier dérivé de C par rapport à t :

Compte tenu d'une position juridique de p , toutes les vitesses ṗ qui satisfont C. ( p ) = 0sont des vitesses légales. Dans cet exemple, il ne doit s'agir que des vitesses tangentielles à l'hypersurface de l'image ci-dessus.

Le second dérivé de C par rapport à t est:

De manière équivalente, étant donné une position légale et une vitesse, toutes les accélérations p̈ qui satisfont C̈ ( p ) = 0sont des accélérations légales. Dans cet exemple, il ne doit s'agir que des accélérations qui sont directement vers ou loin de l'origine.

En utilisant la deuxième loi du mouvement de Newton, nous pouvons exprimer l’accélération en termes de force. On peut considérer qu'il y a deux forces agissant sur la particule: une combinaison de toutes les forces externes F ext , comme la gravité, le vent et les forces appliquées par l'utilisateur, ainsi que la force de contrainte F C. Ce dernier est celui que nous voulons déterminer. En supposant que la particule a une masse m , son accélération est:

En remplaçant cela par C̈ = 0on a:

Qui peut être réorganisé en:

Nous avons une seule équation et deux inconnues (les deux coordonnées de F C), il ne peut donc pas être résolu. Nous devons introduire une condition supplémentaire.

Intuitivement, nous savons que la force de contrainte doit être appliquée s'opposer dans la direction que nous voulons prévenir la particule de se déplacer. Dans cet exemple, les forces de contrainte pointeront toujours vers une direction perpendiculaire au cercle de rayon l , parce que la particule n'est pas autorisée à se déplacer en dehors de ce cercle. Ces forces perpendiculaires repousseront la particule dans la trajectoire circulaire chaque fois qu'elle essaiera de la quitter, ce qui rendra la composante de vitesse qui pointe dans ces directions à zéro. Ainsi, les forces de contrainte seront toujours perpendiculaires à la vitesse de la particule.

Donc:

L'équation de la première dérivée de notre contrainte dit que p · ṗ = 0. Puisque F C· ṗ = 0, nous avons que les deux F Cet p sont orthogonales à ṗ , et donc F Cet p sont parallèles. Ainsi, nous pouvons écrire l'un comme un multiple de l'autre

Nous y sommes presque! Le scalaire λ représente le amplitude de la force de contrainte à appliquer pour amener le système à un état valide. Plus notre système s'éloigne des états valides, plus λ sera afin de le repousser dans un état valide. À ce point λ est notre seule inconnue. En remplaçant ce qui précède dans notre équation précédente, nous obtenons:

Maintenant, nous pouvons calculer λ directement et obtenir F Cen le multipliant par p . Ensuite, nous appliquons simplement F Cà la particule, et laissez la simulation décrite dans la partie I faire le reste!

λ est également connu comme un Multiplicateur de Lagrange . Pour toute contrainte, le calcul consiste à déterminer la direction du vecteur de force, et sa magnitude, λ .

Quand appliquer des forces de contrainte

À partir de cet exemple, nous pouvons voir que le calcul des forces de contrainte nécessite que toutes les autres forces F ext sont déjà connus. Et bien sûr, nous devons appliquer les forces de contrainte avant de simuler le mouvement résultant. Ainsi, une séquence généralisée pour chaque étape de simulation ressemble à ceci:

1. Calculez toutes les forces externes F ext .
2. Calculer les forces de contrainte F C.
3. Appliquez toutes les forces et simulez le mouvement, comme décrit dans la partie I.

Systèmes de contraintes

C'était un exemple relativement simple d'une contrainte assez basique impliquant une seule entité. Nous souhaitons en fait pouvoir avoir de nombreuses contraintes et de nombreux objets dans notre simulation. Les contraintes ne peuvent pas être gérées isolément car les forces appliquées par une contrainte peuvent influencer les forces appliquées par une autre contrainte. Cela est clairement visible dans l'exemple d'une chaîne de corps rigides reliés par des articulations tournantes. Pour cette raison, les contraintes doivent être résolues dans leur ensemble, dans un système d'équations.

Mise en place

Nous allons maintenant travailler avec des vecteurs et des matrices qui contiennent l'état de toutes les entités de notre simulation, et les utiliser pour développer nos équations globales d'une manière similaire à ce que nous avons fait pour l'exemple de particule unique. Développons ces équations pour des corps rigides en deux dimensions.

Vecteur d'état

conception multimédia vs conception graphique

Dis que nous avons n corps rigides que nous simulons. Laisser quoi être un vecteur d'état qui a toutes les positions et angles des corps rigides:

où p je est un vecteur bidimensionnel représentant la position du je -ème corps rigide, et une je est son angle, qui est un scalaire. Donc, quoi a3néléments.

Dynamique: la deuxième loi de Newton

Laisser M être le suivant3npar3nmatrice diagonale:

où m je est la masse du je -ème corps rigide, et je je est son moment d'inertie.

Laisser F être un vecteur de force global contenant les forces et les couples agissant sur chaque corps. C’est la somme des forces externes et des forces de contrainte:

et:

F a aussi 3n éléments, puisque chacun F je est un vecteur à deux dimensions.

Nous pouvons maintenant écrire la deuxième loi du mouvement de Newton pour l'ensemble des corps avec une seule expression:

Contraintes

Enfin, configurons nos fonctions de comportement. Dis qu'il y a m contraintes, chacune représentant un maillon de la chaîne de corps rigides. Nous allons regrouper toutes nos fonctions de comportement en une seule fonction C ( quoi ):

C ( quoi )prend le3n-vecteur dimensionnel quoi comme entrée, et sort un m -vecteur dimensionnel. Nous voulons garder cette sortie aussi proche que possible du vecteur zéro, en utilisant un processus similaire à ce que nous avons fait ci-dessus.

Nous n'entrerons pas dans la définition de chaque fonction de comportement ici, car cela ne sera pas nécessaire, mais le Web propose d'excellents tutoriels sur contraintes d'articulation révolutionnaires .

Dérivés de C Heures supplémentaires

Comme précédemment, nous voulons également les dérivés de première et seconde fois de C être zéro vecteur. Développons ces équations.

Le dérivé de C par rapport au temps peut être donnée comme:

Notez l'utilisation de la règle de la chaîne. Nous pouvons développer cette équation plus loin, en définissant J comme:

C'est le Matrice jacobienne , ou la Jacobien de C . Le jacobien est une généralisation du gradient, qui est lui-même une généralisation de la pente. Il est également intéressant de noter que chaque ligne est le gradient de chaque fonction de comportement. Le jacobien nous dit comment chaque fonction de comportement réagit aux changements par rapport à chaque variable d'état.

Dans le cas de notre chaîne, ce sera une matrice clairsemée, car chaque contrainte n'implique que les deux corps rigides liés par cette contrainte. L'état de tous les autres corps n'aura aucun effet direct sur ce lien.

Nous pouvons maintenant exprimer la dérivée temporelle de C comme:

Beau.

Le second dérivé de C sera:

où:

En remplaçant notre expression de la deuxième loi de Newton, nous avons:

Calcul du vecteur de force de contrainte

Nous voulons la deuxième dérivée de C à zéro, définissons-le sur zéro et réorganisons:

Cette équation est analogue à celle que nous avons développée précédemment pour une seule contrainte:

Encore une fois, le nombre d'inconnues est supérieur au nombre d'équations, et encore une fois, nous pouvons utiliser le fait que les forces de contrainte sont orthogonales aux vitesses pour trouver une solution:

Nous voulons également le premier dérivé de C être nul. De C. = 0nous avons cela:

et donc on peut écrire le vecteur de force de contrainte F C en tant que multiple de J :

Le vecteur λ a m composantes scalaires, et dans cette multiplication matrice-vecteur, chaque composante λ je multiplie une ligne de J (qui est le gradient du je -th fonction de contrainte) et les additionne. C'est

F C est donc un combinaison linéaire des rangées de J , qui sont les gradients des fonctions de contrainte. Bien que ce système soit trop complexe pour pouvoir visualiser facilement l'hypersurface, comme nous l'avons fait pour l'exemple de particule, il se comporte exactement de la même manière que cet exemple: les gradients sont orthogonaux aux hypersurfaces des contraintes, et sont les directions dans lesquelles le système n'est pas autorisé à bouger. Il s'agit donc d'une combinaison linéaire de vecteurs qui pointent dans les directions interdites, ce qui signifie que les forces de contrainte seront limitées à ces directions et qu'elles pousseront les corps vers les états valides imposés par les contraintes.

La seule chose qui reste à résoudre est le λ vecteur, qui déterminera les amplitudes des forces de contrainte. Revenons à notre équation principale et remplaçons-y la dernière expression:

C'est un système d'équations linéaires où seulement λ n'est pas connu. Il y a beaucoup de bien connus méthodes pour résoudre efficacement un système linéaire comme celui-ci. Une fois que c'est résolu et que nous avons λ , nous pouvons calculer F C , appliquez les résultats aux corps rigides et simulez le mouvement résultant comme indiqué dans la partie I.

Pour une dérivation détaillée de ces équations, consultez Andrew Witkin Dynamique contrainte , partie de la Modélisation basée sur la physique: principes et pratique cours à l'Université Carnegie Mellon.

Contraintes d'inégalité

Jusqu'à présent, nous avons supposé que nos fonctions de comportement doivent être égales à zéro à tout moment pour que les contraintes soient satisfaites. Il existe, cependant, des types de contraintes qui nécessitent une certaine flexibilité, où les forces correctives ne seront pas appliquées pour une gamme plus large de valeurs de C que juste zéro. Un exemple d'une telle contrainte est la contrainte de non-pénétration , qui est souvent le type de contrainte le plus important dans les simulations de corps rigides, car il est responsable de résolution de collision , garantissant que deux corps ne s'interpénètrent jamais de manière irréaliste, et leur donnant un comportement solide naturel.

Comme nous l'avons décrit dans la partie II, après qu'une collision est détectée par le Algorithme GJK , nous aurons les points de contact sur les deux corps ainsi que la normale de surface au point de contact. Rappelez-vous que GJK est à la fois un test de collision et un test de proximité, et que deux corps peuvent être considérés comme «en collision» même s'ils ne se touchent pas réellement, mais la distance entre eux est très petite. Dans ce cas, les points de contact sur les deux corps sont considérés comme les points où ils sont les plus proches l'un de l'autre.

La contrainte de non-pénétration s'efforcera de maintenir les corps séparés en appliquant des forces correctives qui poussent les corps à part, mais seulement si les corps entrent en collision .

Considérons une paire de corps bidimensionnels À et B qui entrent en collision. Au moment du contact, À a la position p À et angle une À , et B a la position p B et angle une B . Appelons r À un vecteur qui va du centre de À au point de contact sur À , et définissons également r B De même. Laisser n être la normale de contact qui pointe de À à B .

Prenons une matrice de rotation 2D standard R ( θ )qui fait pivoter les vecteurs d'un angle donné θ :

Nous pouvons l'utiliser pour faire pivoter les vecteurs r À et r B par les angles une À et une B , respectivement. Cela nous permet de définir une fonction de comportement, C , comme:

Cette fonction de comportement semble intimidante, mais son action est simple. Il prend un vecteur entre le point de contact sur À et le point de contact sur B , le projette sur le vecteur normal n , et génère la longueur de ce vecteur de projection. En d'autres termes, il détermine la profondeur de pénétration dans le sens de la normale. Si C est supérieur ou égal à zéro, aucune force ne doit être appliquée, car les corps ne pénètrent pas. Ainsi, nous devons appliquer le inégalité C ≥ 0.

Si nous analysons les équations, nous constaterons que nous n'avons qu'à restreindre la valeur de λ pour chaque contrainte. Dans les contraintes d'égalité des exemples précédents, λ peut prendre n'importe quelle valeur, ce qui signifie que les forces de contrainte peuvent être dans une direction positive ou négative le long des gradients de comportement). Dans une contrainte d'inégalité telle que la contrainte de non-pénétration, cependant, λ doit être supérieur ou égal à zéro, ce qui représente les forces de contrainte qui ne peuvent que pousser un moyen les corps en collision un moyen de chacun d'eux.

Ce changement transforme le système d'équations linéaires que nous avons en quelque chose de tout à fait différent (et plus compliqué) appelé un Problème de complémentarité linéaire mixte , ou MLCP. Il existe quelques bons algorithmes qui peuvent résoudre ce problème directement, tels que Algorithme de Lemke . Cependant, nous allons ignorer les détails ici et discuter d'une autre approche des contraintes qui est très populaire dans la physique des jeux.

Dynamique basée sur les impulsions

Jusqu'à présent, nous avons examiné le basé sur la force approche de l'application des contraintes. Nous calculons les forces de contrainte, appliquons ces forces sur les corps avec les forces externes, et les intégrons en utilisant les méthodes que nous avons décrites dans la partie I pour simuler les mouvements résultants. Il existe cependant une autre technique très populaire parmi les moteurs de physique de jeu, qui prend un basé sur les impulsions approche, opérant sur la vitesse des corps et non sur la force ou l'accélération. Cela signifie que le solveur de contraintes calcule et applique un changement direct des vitesses linéaires et angulaires des corps, au lieu de calculer et d'appliquer des forces correctives et de s'appuyer sur l'intégration pour ensuite modifier les vitesses.

Avec la dynamique basée sur les impulsions, le but est de trouver les impulsions qui aboutissent à des vitesses qui résolvent les contraintes. Ceci est quelque peu analogue à l'objectif basé sur la force de trouver les forces qui entraîneront des accélérations qui résolvent les contraintes. Cependant, nous travaillons à un ordre de grandeur inférieur et, par conséquent, les calculs sont moins complexes.

L'approche basée sur les impulsions a été popularisée par Brian Mirtich dans sa thèse de doctorat de 1996 , qui reste l'une des références les plus importantes sur le sujet. Jan Bender et. au. ont également publié une série de articles importants sur le sujet .

La séquence générale d'une étape de simulation utilisant la dynamique basée sur les impulsions est quelque peu différente de celle des moteurs basés sur la force:

1. Calculez toutes les forces externes.
2. Appliquez les forces et déterminez les vitesses résultantes, en utilisant les techniques de la partie I.
3. Calculez les vitesses de contrainte en fonction des fonctions de comportement.
4. Appliquez les vitesses de contrainte et simulez le mouvement résultant.

Peut-être le plus grand avantage de la dynamique basée sur les impulsions par rapport à l'approche basée sur la force et d'autres est la simplicité relative des algorithmes. Il est également plus facile à comprendre intuitivement. Dans la plupart des cas, il est également plus efficace en termes de calcul, ce qui le rend plus attrayant pour les jeux, où les performances en temps réel sont souvent une priorité. Il y a cependant des inconvénients à prendre en compte, notamment la difficulté à gérer de manière réaliste des contacts stables (comme dans une pile de boîtes au repos) et une complexité accrue lors de la modélisation du frottement de contact. Néanmoins, nous pouvons contourner ces problèmes de plusieurs manières, comme nous le verrons plus loin.

Dans le langage de la physique, un impulsion est l'intégrale d'une force par rapport au temps. C'est:

comment collecter des données twitter

Ceci est égal au changer élan pendant ce temps.

Si une force constante F est appliqué pendant un certain temps h , alors l'impulsion est simplement:

Lorsque deux objets rigides entrent en collision, ils restent en contact pendant un très court laps de temps, pendant lequel ils se déforment et appliquent des forces égales et opposées l'une sur l'autre. Après cette brève interaction, leurs vitesses peuvent avoir changé radicalement, et donc leur élan aussi. Si les objets sont des corps parfaitement rigides, la durée pendant laquelle ils restent en contact est infiniment proche de zéro, et leurs vitesses changent immédiatement après une collision. Les corps parfaitement rigides n'existent pas dans la vie réelle, mais la simplification peut être utilisée pour simuler de manière réaliste le comportement d'objets très rigides.

Impulsions séquentielles

Notre objectif est de trouver les impulsions qui résolvent les contraintes du pas de temps courant de la simulation. Impulsions séquentielles est une technique que nous pouvons utiliser pour trouver ces impulsions. Il a été popularisé par Erin Catto, l'auteur du Box2D moteur physique . C'est un algorithme itératif, où l'idée est de se concentrer sur la vitesse de contrainte en appliquant des impulsions sur les corps rigides à chaque itération, et de répéter jusqu'à ce que l'erreur de vitesse résultante soit très petite, ou en d'autres termes, jusqu'à ce que C. est très proche de zéro.

Dans les impulsions séquentielles, nous ne créons pas un système monolithique d'équations et d'inégalités comme nous le faisions auparavant. Nous modélisons et résolvons chaque contrainte individuellement, un peu comme nous l'avons fait dans le premier exemple pour une particule. L'algorithme se résume à ces trois étapes:

1. Intégrez les forces appliquées en utilisant Euler semi-implicite comme dans la partie I, ce qui donne des vitesses provisoires. Ces vitesses peuvent violer les contraintes et doivent être corrigées avant d'être appliquées.

2. Appliquez des impulsions séquentiellement pour toutes les contraintes, pour corriger les erreurs de vitesse. Répétez pour plusieurs itérations, jusqu'à ce que les impulsions deviennent petites ou après qu'un nombre maximum d'itérations soit atteint.

3. Utilisez les nouvelles vitesses pour simuler le mouvement, en mettant à jour les positions, encore une fois en utilisant Euler semi-implicite.

Notez que ces étapes correspondent aux étapes 2 à 4 de la séquence générale des pas de temps basés sur les impulsions décrite ci-dessus.

Calcul des vitesses

Examinons les équations. Laisser q̇ un= q̇ ( t je -un)et q̇ 2= q̇ ( t je ). C'est, q̇ unet q̇ 2sont la vitesse dans le pas de temps précédent et la vitesse pour le pas de temps actuel (que nous voulons déterminer), respectivement. En utilisant le schéma d'intégration semi-implicite d'Euler, la tentative, non contraint la vitesse du pas en cours (indiquée par un astérisque) est:

Cette vitesse peut violer les contraintes, auquel cas elle doit être corrigée avec une impulsion.

Laisser P C être l'impulsion de contrainte. En le divisant par masse, nous obtenons le changement de vitesse et l'appliquons à la vitesse provisoire pour obtenir la vitesse désirée qui satisfait les contraintes:

Alors, comment déterminons-nous P C ? Si on reconnaît que l'impulsion sera appliquée dans le même sens qu'une force instantanée qui la produit, on peut à nouveau utiliser le fait que les forces de contrainte doivent être parallèles au gradient de la fonction de comportement, tout comme nous l'avons fait avec la force- contraintes fondées. Ainsi, on peut écrire:

où λ est à nouveau un vecteur de grandeurs.

L’approche basée sur les impulsions représente un raccourci qui contourne la deuxième loi de Newton. En sautant le calcul des forces et les accélérations qui en résultent, il peut générer des changements de vitesse instantanés et visibles qui peuvent provoquer une gigue indésirable. Pour atténuer ces effets, il est courant d’ajouter un biais factoriser aux contraintes de vitesse, pour adoucir les effets:

apprendre le c++ en une seule vidéo

Observe ceci J q̇ 2+ b = 0, puisque q̇ 2doit être une vitesse valide. Ensuite, en substituant et en réorganisant l'équation de vitesse valide, nous obtenons

Après avoir résolu cette équation pour λ on peut calculer l'impulsion de contrainte en utilisant P C = J T λ , et enfin mettre à jour la vitesse.

Nous devons résoudre chaque contrainte individuellement et appliquer les impulsions, mettre à jour les vitesses des corps, puis répéter cette étape plusieurs fois jusqu'à ce que la convergence soit atteinte ou qu'un nombre maximum d'itérations soit atteint. Cela signifie que nous accumuler les impulsions que nous itérons. Pour terminer le pas de temps, il suffit de mettre à jour les positions en utilisant les vitesses finales:

Contraintes d'inégalité

Pour les contraintes d’inégalité, nous devons limiter les impulsions et les conserver dans les valeurs autorisées au fur et à mesure que nous les accumulons, de sorte que les contraintes n’appliquent pas d’impulsions dans des directions ou des forces indésirables. Cette procédure de délimitation n'est pas aussi simple que d'appliquer simplement un min / max fonction, parce que nous voulons seulement lier l'impulsion finale accumulée, mais ne pas les impulsions intermédiaires générées lors de l'accumulation. Check-out GDC 2009 d’Erin Catto présentation pour plus de détails.

Démarrage à chaud

Une petite technique qui améliore considérablement la précision de l'algorithme est appelée démarrage chaud . L'algorithme commence par une estimation initiale pour λ , et progresse à partir de là. Étant donné qu'une simulation physique a beaucoup de cohérence temporelle et spatiale, il est naturel de penser à utiliser le λ trouvé à l'étape précédente comme point de départ, et c'est en quoi consiste le démarrage à chaud. Les corps ne se déplacent souvent pas beaucoup d’étape en étape, il est donc très probable que les impulsions que nous avons calculées à l’étape précédente seront presque les mêmes dans l’étape en cours. Démarrer notre algorithme à partir de là permet de converger plus rapidement vers une solution plus précise. Cela améliore la stabilité de la simulation, en particulier pour les contraintes telles que les joints et les contacts persistants entre les corps.

Projeté Gauss-Seidel

Une autre technique de résolution des contraintes basées sur les impulsions vient du fait qu'elle peut également être modélisée comme un MLCP. Projeté Gauss-Seidel (PGS) est un algorithme itératif de résolution de MLCP qui fonctionne bien pour la dynamique basée sur les impulsions. Il résout essentiellement un système linéaire À X = b , avec des limites X . PGS est une extension du Méthode Gauss-Seidel , où nous avons lié la valeur de X à chaque itération pour le maintenir dans la plage souhaitée.

Puisque nous travaillons sur la vitesse, nous pouvons éliminer l’accélération en écrivant une approximation de celle-ci comme le rapport entre le changement de vitesse et le temps delta pour le pas de temps actuel. Laisser q̇ un= q̇ ( t je -un)et q̇ 2= q̇ ( t je ), puis:

où, encore une fois, q̇ unest la vitesse calculée à l'étape précédente, et q̇ 2est la vitesse que nous voulons trouver pour le pas en cours. De la deuxième loi de Newton, nous avons:

En substituant notre approximation et F C = J T λ , on a:

Puisque C. = 0, nous avons ça J q̇ 2= 0 , car q̇ 2sera une vitesse légale après que cela soit résolu. Réorganiser et multiplier par J des deux côtés, on obtient:

Ce MLCP est légèrement différent de ce que nous avons pour l'approche basée sur la force, car il utilise une accélération approximative. Une fois que nous aurons résolu le problème avec PGS, nous aurons λ , puis q̇ 2peut être calculé en utilisant l'équation précédente:

Les positions et orientations mises à jour découlent facilement du schéma d'Euler semi-implicite:

Fait intéressant, une enquête approfondie révèle que PGS équivaut à des impulsions séquentielles! Nous faisons essentiellement la même chose ici. Le démarrage à chaud peut à nouveau être utilisé, en prenant λ calculé à l'étape précédente comme point de départ. La différence est que la formulation des impulsions séquentielles est plus intuitive, mais la formulation PGS est plus générale et permet un code plus flexible. Par exemple, nous pouvons expérimenter en utilisant d'autres outils pour résoudre le MLCP.

Pour plus de détails sur l'utilisation de PGS dans une simulation basée sur les impulsions, consultez Présentation et article d’Erin Catto sur la GDC en 2005 .

Simulation de la friction à l'aide d'impulsions

La Modèle de friction de Coulomb est simple et fonctionne bien. Il définit deux cas différents lorsque deux surfaces solides sont en contact l'une avec l'autre:

• Frottement statique : Résistance au mouvement tangentiel lorsque les surfaces ne bougent pas les unes par rapport aux autres, car il n'y a pas assez de force pour surmonter le frottement. La force de frottement pointe dans la direction opposée de la force tangente nette et lui est égale en grandeur.
• Frottement cinétique : Résistance au mouvement tangentiel lorsque les surfaces glissent. La force de frottement pointe dans la direction opposée du mouvement et est inférieure aux forces tangentes nettes en amplitude.

La force de frottement est proportionnelle à la force normale, qui est la composante de la force nette dans la direction du vecteur normal de la surface de contact. En d'autres termes, la force de frottement est proportionnelle à la force poussant les deux objets l'un vers l'autre. Il peut être exprimé par:

où F F est la force de frottement, F n est la force normale et μ est le coefficient de friction (qui peut être différent pour le frottement statique et cinétique).

Pour simuler le frottement à l'aide d'un modèle de contraintes, nous devons écrire directement une contrainte de vitesse:

Où v p est le vecteur de vitesse relative au point de contact p , et t est un vecteur unitaire tangent aux surfaces. Nous voulons ramener la vitesse tangentielle à zéro.

Selon l'équation de frottement, nous devons limiter la valeur de l'impulsion de frottement à l'impulsion normale multipliée par le coefficient de frottement. Cela signifie que nous devons garder notre λ entre- μ λ net μ λ n, où λ nest la magnitude de l'impulsion normale.

Ainsi, le frottement est un autre exemple de contrainte d'inégalité.

En trois dimensions, les choses se compliquent un peu. Dans son Présentation GDC 2005 , Erin Catto présente une approche qui utilise deux vecteurs tangents et une paire de contraintes. Cependant, limiter l'impulsion de frottement par un multiple de l'impulsion normale dans ce cas couple les deux contraintes, et rend les choses difficiles à résoudre. Il contourne cela en le limitant plutôt par une valeur constante proportionnelle à la masse du corps et à l'accélération gravitationnelle.

Optimisations

Nous avons décrit plusieurs méthodes pour déterminer soit les forces, soit les impulsions à appliquer à nos corps rigides afin d’imposer nos contraintes. Dans chaque cas, les calculs impliquent une bonne quantité de démarches. Examinons maintenant quelques stratégies d'optimisation intelligentes pour supprimer une partie de ce travail lorsque cela n'est pas nécessaire.

îles

Dans une simulation physique contrainte, on peut observer que certains objets influencent le mouvement d’autres, tandis que d’autres non.

Dans l'image ci-dessus, la boîte B est un objet statique qui ne bouge pas. C’est la parole. Les objets de gauche sont empilés, en contact les uns avec les autres. Si l'un d'entre eux bouge, les autres bougeront potentiellement aussi, car il y a des contraintes de contact entre eux. Toute force ou impulsion appliquée à l'un de ces corps peut se propager dans les autres corps. Cependant, le triangle au milieu est juste assis seul sur la boîte fixe B . Les forces appliquées sur les objets empilés sur la gauche n'affecteront jamais le mouvement du triangle, car il n'y a aucune connexion entre les objets empilés et le triangle. La même chose peut être dite à propos de la chaîne de boîtes sur la droite. Ils sont tous reliés par des articulations de révolution, et le mouvement de l'un d'entre eux peut donc générer une réaction le long des contraintes, influençant le mouvement de toutes les autres boîtes faisant partie de la chaîne. Mais ils n'influenceront jamais l'état du triangle, ni les objets empilés sur la gauche, à moins qu'une nouvelle contrainte ne soit créée entre l'un d'entre eux, comme une contrainte de contact / non-pénétration due à leur mouvement les faisant entrer en collision avec l'autre. objets.

Sur la base de cette simple observation, nous pouvons regrouper ces objets dans ce que nous appelons îles , qui sont des groupes de corps autonomes qui peuvent influencer le mouvement les uns des autres dans le groupe par des forces / impulsions de contrainte, mais n'influenceront pas le mouvement des objets appartenant à une autre île.

Cette séparation nous permet de résoudre de plus petits groupes de contraintes, créant des systèmes plus petits au lieu d'un seul grand système pour tout le monde de la physique. Cela élimine une quantité potentiellement énorme de travail inutile que l'ordinateur doit effectuer.

Si nous regardons le monde comme un graphe, où les corps sont des nœuds et les contraintes sont des arêtes, nous pouvons construire les îles en utilisant un recherche en profondeur d'abord sur ce graphique. En théorie des graphes, nos îles sont appelées composants connectés .

Box2D fait cela dans son b2World::Solve méthode, qui est chargée de résoudre toutes les contraintes de chaque étape . Il construit les îles puis appelle b2Island::Solve sur chacun d'eux. Cette méthode résout les contraintes de cet îlot en utilisant des impulsions séquentielles.

En train de dormir

Lorsqu'un corps s'immobilise pendant la simulation, sa position restera naturellement inchangée pour toutes les étapes ultérieures de la simulation, jusqu'à ce qu'une force externe le fasse bouger à nouveau. Ceci attire notre attention sur une autre optimisation possible: on peut arrêter de simuler un îlot donné lorsque les vitesses linéaires et angulaires de tous ses corps restent en dessous d'une tolérance donnée pendant un petit laps de temps. Cette condition s'appelle en train de dormir .

Après la mise en veille d'un îlot, ses corps sont exclus de toutes les étapes de la simulation, à l'exception de la détection de collision. Si un corps à l'extérieur de l'île entre en collision avec un corps de cette île, l'île «se réveille» et revient à nouveau dans la simulation. Si une autre force ou impulsion externe est appliquée sur l'un de ses corps, il se réveille également.

C'est une technique assez simple qui peut grandement améliorer les performances des simulations contenant de nombreux objets.

Conclusion - Physique du jeu vidéo et simulation de corps rigide contraint

Ceci conclut notre série en trois parties sur jeu vidéo la physique. Nous avons vu comment la physique peut être simulée dans les jeux, en se concentrant sur la simulation de corps rigides, qui est un sous-ensemble fondamental de la simulation physique qui est souvent suffisant pour rendre les jeux dynamiques et amusants. Nous avons vu comment le mouvement des corps rigides peut être simulé, comment les collisions entre eux peuvent être détectées et résolues, et aussi comment d'autres interactions entre eux peuvent être modélisées.

Les techniques que nous avons vues sont utilisées dans les moteurs de physique de jeu populaires tels que Box2D , Physique Chipmunk et Physique des balles . Ces méthodes peuvent être utilisées pour créer des jeux avec un comportement réaliste et dynamique, avec des objets qui se déplacent et se heurtent, et permettent également aux objets d'être connectés les uns aux autres de différentes manières via des articulations de nombreux types. Il peut être intéressant de noter que ces mêmes méthodes trouvent même des applications dans d'autres domaines au-delà du jeu, comme la robotique.

Comme d'habitude, les choses peuvent être belles en théorie, mais en pratique se révèlent être une autre histoire. De nombreuses simplifications astucieuses sont nécessaires pour obtenir une implémentation stable et efficace, notamment en ce qui concerne la dynamique contrainte. De nombreux développements importants ont été réalisés au cours des dernières années concernant la détection des collisions, le temps de calcul de l'impact, la résolution MLCP, etc., et pourtant il y a encore beaucoup de choses qui peuvent être améliorées. La Forum de physique des balles est un bon endroit pour se tenir au courant de ce qui se passe dans le monde de la simulation du jeu et de la physique des corps rigides, en particulier le Discussion sur la recherche et le développement sur la détection des collisions et la simulation physique section, où les membres discutent des techniques modernes de simulation physique de toutes sortes.