Améliorer la simulation et les performances au moyen d’un solveur de physique avancé
Créer une meilleure fidélité grâce au solveur en projection de Gauss-Seidel.
En 2016, nous avons ajouté le support à un ensemble diversifié de nouvelles contraintes physiques, incitant les développeurs à migrer vers le nouveau solveur et étendant les capacités créatives du moteur physique. Tous les nouveaux emplacements ont utilisé le solveur PGS par défaut avec la possibilité de revenir au solveur classique.
Nous avons résolu certains problèmes de stabilité associés à de grandes différences de masse et à des mécanismes complexes grâce à l'introduction du solveur hybride LDL-PGS à la mi-2018. Cela a rendu le vieux solveur obsolète, et il a été complètement désactivé en 2019 migrant automatiquement tous les emplacements vers le PGS.
En 2019, les performances ont encore été améliorées grâce au multithreading qui divise la simulation en tâches consistant en des îlots de pièces simulées connectées. Nous avions encore des problèmes de performance liés à la LDL que nous avons finalement résolus au début de l'année 2020.
Le moteur physique est toujours en cours d'amélioration et d'optimisation des performances et nous prévoyons d'ajouter de nouvelles fonctionnalités dans un avenir proche.
Mise en œuvre des lois de la physique
L'objectif principal d'un moteur physique est de simuler le mouvement des corps dans un environnement virtuel. Dans notre moteur physique, nous nous soucions des corps qui sont rigides, qui entrent en collision et qui ont des contraintes les uns avec les autres.
Un moteur physique est organisé en deux phases : la détection et la résolution des collisions. La détection des collisions trouve les intersections entre les géométries associées aux corps rigides générant des informations appropriées sur les collisions, telles que les points de collision, les normales et les profondeurs de pénétration. Ensuite, un solveur met à jour le mouvement des corps rigides sous l'influence des collisions qui ont été détectées et des contraintes qui ont été fournies par l'utilisateur.
Le mouvement est le résultat de l'interprétation par le solveur des lois de la physique telles que la conservation de l'énergie et de l'élan. Mais le faire avec une précision de 100 % est d'un coût prohibitif et l'astuce pour le simuler en temps réel est d'augmenter approximativement les performances à condition que le résultat soit physiquement réaliste. Tant que les lois fondamentales du mouvement sont maintenues dans une tolérance raisonnable, ce compromis est tout à fait acceptable pour une simulation de jeu sur ordinateur.
Avancer à petits pas
L'idée principale du moteur physique est de rendre le mouvement discret en utilisant le progression temporelle. Les équations de mouvement des corps rigides contraints et non contraints sont très difficiles à intégrer directement et précisément. La discrétisation subdivise le mouvement en petits incréments de temps où les équations sont simplifiées et linéarisées permettant de les résoudre approximativement. Cela signifie qu'à chaque pas temporel, le mouvement des parties pertinentes des corps rigides qui sont impliquées dans une contrainte est rapproché de manière linéaire.
[gallery link="none" size="full" columns="2" ids="eyJ1cmwiOiJodHRwOlwvXC9sb2NhbGhvc3RcL3dwLWNvbnRlbnRcL3VwbG9hZHNcLzIwMjBcLzA4XC9wZ3Mtc29sdmVyLXRlY2g0LmdpZiIsInRpdGxlIjoicGdzLXNvbHZlci10ZWNoNCIsImNhcHRpb24iOiIiLCJhbHQiOiIiLCJkZXNjcmlwdGlvbiI6IiJ9,eyJ1cmwiOiJodHRwOlwvXC9sb2NhbGhvc3RcL3dwLWNvbnRlbnRcL3VwbG9hZHNcLzIwMjBcLzA4XC9wZ3Mtc29sdmVyLXRlY2g1YS0xLnBuZyIsInRpdGxlIjoicGdzLXNvbHZlci10ZWNoNWEiLCJjYXB0aW9uIjoiIiwiYWx0IjoiIiwiZGVzY3JpcHRpb24iOiIifQ=="]
Bien qu'un problème linéarisé soit plus facile à résoudre, il produit une dérive dans une simulation contenant des comportements non linéaires, comme le mouvement de rotation. Nous verrons plus tard les méthodes d'atténuation qui permettent de réduire la dérive et de rendre la simulation plus plausible.
Résolution
Après avoir linéarisé les équations du mouvement pour un pas temporel, nous finissons par devoir résoudre un système linéaire ou problème de complémentarité linéaire (LCP). Ces systèmes peuvent être arbitrairement importants et peuvent encore être assez coûteux à résoudre précisément. Là encore, l'astuce consiste à trouver une solution approximative en utilisant une méthode plus rapide. Une méthode moderne pour résoudre approximativement un LCP avec de bonnes propriétés de convergence est la méthode de Gauss-Seidel (Projected Gauss-Seidel). C'est une méthode itérative, ce qui signifie qu'à chaque itération, la solution approximative est rapprochée de la solution réelle, et sa précision finale dépend du nombre d'itérations.
Cette animation montre comment un solveur PGS modifie les positions des corps à chaque étape du processus d'itération, l'objectif étant de trouver les positions qui respectent les contraintes de la rotule tout en préservant le centre de masse à chaque étape (c'est un type de solveur positionnel utilisé par le dragger IK). Bien que cet exemple ait une solution analytique simple, il démontre bien l'idée derrière le SGP. A chaque étape, le solveur fixe une des contraintes et laisse l'autre être transgressée. Après quelques itérations, les corps sont très proches de leurs positions correctes. Une caractéristique de cette méthode est la façon dont certains corps rigides semblent vibrer autour de leur position finale en particulier lors d'interactions de couplage avec des corps plus lourds. Si nous ne faisons pas assez d'itérations, la partie jaune pourrait être laissée dans un état visiblement invalide où l'une de ses deux contraintes est totalement transgressée. C'est ce qu'on appelle le problème du rapport de masse élevé qui a été le fléau des moteurs physiques car il provoque des instabilités et des explosions. Si nous faisons trop d'itérations, le solveur devient trop lent, si nous ne le faisons pas, il devient instable. L'équilibre entre les deux parties a été un processus long et douloureux.
Stratégies d'atténuation
Par conséquent, une grande partie de la complexité du solveur provient de la mise en œuvre de méthodes visant à minimiser l'impact des imprécisions de calcul. Notre mise en œuvre finale utilise des stratégies d'atténuation traditionnelles et nouvelles :
- Démarrage à chaud : partir de la solution d'une étape précédente pour augmenter le taux de convergence du solveur itératif.
- Post-stabilisation : reprojection du système vers le collecteur de contraintes pour éviter la dérive des contraintes
- Régularisation : ajout de la conformité aux contraintes garantissant qu'une solution existe et est unique
- Pré-conditionnement : utilisation d'une solution exacte à un sous-système linéaire, amélioration de la stabilité des mécanismes complexes
Les stratégies 1, 2 et 3 sont assez traditionnelles, mais nous avons perfectionné et amélioré la stratégie 3. De plus, bien que le chiffre 4 ne soit pas inconnu, nous n'en avons pas vu la mise en œuvre pratique. Nous utilisons une méthode originale de factorisation pour les grandes matrices à contraintes éparses et une nouvelle façon efficace de la combiner avec le PGS. La mise en œuvre qui en résulte n'est que légèrement plus lente par rapport au système purement SGP mais garantit que le système linéaire issu des contraintes d'égalité est résolu avec exactitude. Par conséquent, les contraintes d'égalité ne souffrent que de la dérive provenant de la discrétisation du temps. Des détails sur nos méthodes figurent dans ma présentation de la GDC 2020. Actuellement, nous étudions des méthodes directes appliquées aux contraintes et collisions d'inégalité.
Obtenir plus de détails
Traditionnellement, il existe deux modèles mathématiques pour les mécanismes articulés : il existe des méthodes de coordonnées réduites dont Featherstone est le fer de lance qui paramètrent les degrés de liberté pour chaque articulation et il existe des méthodes de coordonnées complètes qui utilisent une formulation lagrangienne
Nous utilisons la deuxième formulation car elle est moins restrictive et nécessite des mathématiques et une mise en œuvre beaucoup plus simples.
Le moteur Roblox utilise des méthodes analytiques pour calculer la réponse dynamique des contraintes, par opposition aux méthodes de pénalisation qui étaient utilisées auparavant. Les méthodes analytiques ont été initialement introduites par Baraff en 1989 et elles sont utilisées pour traiter de manière cohérente les contraintes d'égalité et de non-égalité. Baraff a observé que le modèle de contact peut être formulé en utilisant la programmation quadratique et il a fourni une méthode de solution heuristique (qui n'est pas la méthode que nous utilisons dans notre solveur).
Au lieu d'utiliser une formule basée sur la force, nous utilisons une formule basée sur l'impulsion de la vitesse dans l’espace initialement introduite par Mirtich-Canny en 1995 et encore améliorée par Stewart-Trinkle en 1996 et qui unifie le traitement des différents types de contact tout en garantissant l'existence d'une solution pour les contacts avec friction. À chaque progression temporelle, les contraintes et les collisions sont maintenues en appliquant les changements instantanés de vitesse dus à la force des impulsions. Une excellente explication de la supériorité de la simulation basée sur les impulsions est contenue dans la présentation de Catto au GDC 2014.
Les contacts sans frottement sont modélisés à l'aide d'un problème de complémentarité linéaire (LCP) tel que décrit par Baraff en 1994. La friction est ajoutée comme une projection non linéaire sur le cône de friction, entrelacée avec les itérations du Gauss-Seidel projeté.
La dérive numérique qui introduit des erreurs positionnelles dans les contraintes est résolue par une technique de post-stabilisation utilisant des pseudo-vitesses introduites par Cline-Pai en 2003. Il s'agit de résoudre un deuxième LCP de la position dans l’espace qui projette le système vers le collecteur de contraintes.
Les LCP sont résolus à l'aide d'un PGS / Impulse Solver popularisé par Catto en 2005 (voir aussi Catto en 2009). Cette méthode est itérative et considère chaque contrainte individuelle en séquence et la résout indépendamment. Au fil de nombreuses itérations et dans des conditions idéales, le système converge vers une solution globale.
De plus, les problèmes de rapport de masse élevée dans les contraintes d'égalité sont aplanis en pré-conditionnant le PGS à l'aide de la décomposition en LDL clairsemée de la matrice des contraintes d'égalité. Les sous-matrices denses de la matrice de contraintes sont scindées à l'aide d'une méthode que nous appelons Body Splitting. Cette méthode est similaire à la décomposition des LDL utilisée dans par Baraff en 1996 mais elle permet des systèmes mécaniques plus généraux et résout le système dans l'espace de contrainte. Vous pouvez regarder ma présentation au GDC 2020 pour de plus amples informations.
L'architecture de notre solveur suit l'idée de Guendelman-Bridson-Fedkiw dans laquelle la vitesse et la position des pas sont séparées par la résolution des contraintes. Notre séquence temporelle est :
- Vitesses d'avancement
- Résolution des contraintes de la vitesse et la position dans l’espace
- Positions d'avancement
Ce système présente l'avantage de n'intégrer que les vitesses valides et de limiter la latence dans l'application de la force externe tout en permettant une petite quantité de transgression perçue de la contrainte due à la dérive numérique.
Une excellente référence pour la simulation de corps rigides est le livre d’Erleben de 2005 qui a récemment été mis en libre accès. Vous pouvez trouver des conférences en ligne sur l'animation basée sur la physique, un blog de Nilson Souto sur la construction d'un moteur physique, une très bonne présentation à la GDC par Erin Catto sur les méthodes modernes de solveur et des forums comme le Bullet Physics Forum et GameDev qui sont d'excellents endroits pour poser des questions.
En conclusion
Le domaine de la simulation de la physique des jeux présente de nombreux problèmes intéressants qui sont à la fois passionnants et stimulants. Il y a des possibilités d'apprendre une quantité substantielle de mathématiques et de physique cool et d'utiliser des techniques d'optimisation modernes. C'est un domaine de développement de jeux qui marie étroitement les mathématiques, la physique et le génie informatique.
Même si Roblox possède un bon moteur de physique corporelle rigide, il y a des domaines où il peut être amélioré et optimisé. Nous travaillons également sur de nouveaux projets passionnants comme la fracturation, la déformation, le corps mou, le tissu, l'aérodynamique et la simulation de l'eau.
Ni Roblox Corporation ni ce blog ne cautionnent ni ne soutiennent aucune entreprise ou service. En outre, aucune garantie ou promesse n'est faite quant à l'exactitude, la fiabilité ou l'exhaustivité des informations contenues dans ce blog.
Cet article de blog a été publié à l'origine sur Roblox Tech Blog.