Améliorer la simulation et les performances grâce à un solveur physique avancé
En 2016, nous avons ajouté la prise en charge d'un ensemble varié de nouvelles contraintes physiques, incitant les développeurs à migrer vers le nouveau solveur et élargissant les capacités créatives du moteur physique. Tous les nouveaux lieux utilisaient le solveur PGS par défaut, avec la possibilité de revenir au solveur classique.
Nous avons résolu certains problèmes de stabilité liés à des différences de masse importantes et à des mécanismes complexes grâce à l'introduction du solveur hybride LDL-PGS mi-2018. Cela a rendu l'ancien solveur obsolète, et il a été complètement désactivé en 2019, ce qui a entraîné la migration automatique de tous les lieux vers le PGS.
En 2019, les performances ont encore été améliorées grâce au multithreading, qui divise la simulation en tâches composées d’îlots connectés de pièces simulées. Nous avions encore des problèmes de performances liés au LDL, que nous avons finalement résolus début 2020.
Le moteur physique est toujours en cours d'amélioration et d'optimisation en termes de 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 de corps dans un environnement virtuel. Dans notre moteur physique, nous nous intéressons aux corps rigides qui entrent en collision et sont soumis à des contraintes les uns par rapport aux autres.
Un moteur physique s'organise en deux phases : la détection des collisions et la résolution. La détection des collisions identifie les intersections entre les géométries associées aux corps rigides, générant des informations de collision appropriées 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 détectées et des contraintes fournies par l'utilisateur.
Le mouvement résulte de l'interprétation par le solveur des lois de la physique, telles que la conservation de l'énergie et de la quantité de mouvement. 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 consiste à recourir à des approximations afin d'améliorer les performances, à condition que le résultat soit physiquement réaliste. Tant que les lois fondamentales du mouvement sont respectées dans une marge de tolérance raisonnable, ce compromis est tout à fait acceptable pour une simulation de jeu vidéo.
Par petites étapes
L'idée principale du moteur physique est de discrétiser le mouvement à l'aide d'étapes temporelles. Les équations du mouvement des corps rigides contraints et non contraints sont très difficiles à intégrer directement et avec précision. La discrétisation subdivise le mouvement en petits incréments de temps, où les équations sont simplifiées et linéarisées, ce qui permet de les résoudre de manière approximative. Cela signifie qu'à chaque étape temporelle, le mouvement des parties concernées des corps rigides impliqués dans une contrainte est approximé de manière linéaire.
Bien qu'un problème linéarisé soit plus facile à résoudre, il produit une dérive dans une simulation comportant des comportements non linéaires, comme le mouvement de rotation. Nous verrons plus tard des méthodes d'atténuation qui aident à réduire la dérive et à rendre la simulation plus plausible.
Résolution
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 rotule tout en préservant le centre de masse à chaque étape (il s'agit d'un type de solveur de position utilisé par le dragger IK). Bien que cet exemple ait une solution analytique simple, il illustre bien le principe du PGS. À chaque étape, le solveur fixe l'une des contraintes et laisse l'autre être violé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 avec des corps plus lourds. Si nous n'effectuons pas suffisamment d'itérations, la partie jaune pourrait rester dans un état visiblement invalide où l'une de ses deux contraintes est gravement violée. C'est ce qu'on appelle le problème du rapport de masse élevé, et il a longtemps été le cauchemar des moteurs physiques car il provoque des instabilités et des explosions. Si nous effectuons trop d'itérations, le solveur devient trop lent ; si nous n'en faisons pas assez, il devient instable. Trouver l'équilibre entre ces deux aspects a été un processus long et fastidieux.
Stratégies d'atténuation
Un solveur présente deux sources principales d'imprécisions : le pas de temps et la résolution itérative (il existe également la dérive en virgule flottante, mais elle est mineure par rapport aux deux premières). Ces imprécisions introduisent des erreurs dans la simulation, la faisant dévier de la trajectoire correcte. Certaines de ces dérives sont tolérables, comme des vitesses légèrement différentes ou une perte d'énergie, mais d'autres ne le sont pas, comme les instabilités, les gains d'énergie importants ou les contraintes désalignées.
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 implémentation finale utilise à la fois des stratégies d'atténuation traditionnelles et novatrices :
- Démarrage à chaud : partir de la solution d'un pas de temps précédent pour augmenter le taux de convergence du solveur itératif
- Post-stabilisation : reprojeter le système sur la variété des contraintes pour empêcher la dérive des contraintes
- Régularisation : ajouter une conformité aux contraintes pour garantir qu'une solution existe et qu'elle est unique
- Préconditionnement : utilisation d'une solution exacte d'un sous-système linéaire, améliorant la stabilité des mécanismes complexes
Les stratégies 1, 2 et 3 sont assez traditionnelles, mais la stratégie 3 a été améliorée et perfectionnée par nos soins. De plus, bien que la stratégie 4 ne soit pas inconnue, nous n’en avons vu aucune implémentation pratique. Nous utilisons une méthode de factorisation originale pour les grandes matrices de contraintes clairsemées et une nouvelle manière efficace de la combiner avec la PGS. La mise en œuvre qui en résulte n’est que légèrement plus lente que la PGS pure, mais garantit que le système linéaire issu des contraintes d’égalité est résolu exactement. Par conséquent, les contraintes d’égalité ne subissent que la dérive provenant de la discrétisation temporelle. Les détails de nos méthodes figurent dans ma présentation au GDC 2020. Actuellement, nous étudions des méthodes directes appliquées aux contraintes d’inégalité et aux collisions.
Plus de détails
Il existe traditionnellement deux modèles mathématiques pour les mécanismes articulés : les méthodes à coordonnées réduites, mises au point par Featherstone, qui paramètrent les degrés de liberté à chaque articulation, et les méthodes à coordonnées complètes qui utilisent une formulation lagrangienne.
Nous utilisons la seconde formulation, car elle est moins restrictive et nécessite des mathématiques et une implémentation beaucoup plus simples.
Le moteur Roblox utilise des méthodes analytiques pour calculer la réponse dynamique des contraintes, contrairement aux méthodes de pénalité utilisées auparavant. Les méthodes analytiques ont été initialement introduites par Baraff en 1989, où 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é à l'aide de la programmation quadratique, et il a proposé une méthode de résolution heuristique (qui n'est pas celle que nous utilisons dans notre solveur).
Au lieu d'utiliser une formulation basée sur les forces, nous utilisons une formulation basée sur les impulsions dans l'espace des vitesses, initialement introduite par Mirtich-Canny en 1995 et améliorée par Stewart-Trinkle en 1996, qui unifie le traitement des différents types de contact et garantit l'existence d'une solution pour les contacts avec frottement. À chaque pas de temps, les contraintes et les collisions sont maintenues en appliquant des variations instantanées de vitesse dues aux impulsions de contrainte. Une excellente explication des raisons pour lesquelles la simulation basée sur les impulsions est supérieure figure dans la présentation GDC de Catto en 2014.
Les contacts sans frottement sont modélisés à l'aide d'un problème de complémentarité linéaire (LCP), comme décrit par Baraff en 1994. Le frottement est ajouté sous la forme d'une projection non linéaire sur le cône de frottement, entrelacée avec les itérations de la méthode de Gauss-Seidel projetée.
La dérive numérique qui introduit des erreurs de position dans les contraintes est résolue à l'aide d'une technique de post-stabilisation utilisant des pseudo-vitesses introduite par Cline-Pai 2003. Elle consiste à résoudre un deuxième LCP dans l'espace de position, qui projette le système vers la variété des contraintes.
Les LCP sont résolus à l'aide d'un solveur PGS / Impulse Solver popularisé par Catto 2005 (voir également Catto 2009). Cette méthode est itérative et considère chaque contrainte individuellement, les unes après les autres, pour les résoudre indépendamment. Au bout de nombreuses itérations, et dans des conditions idéales, le système converge vers une solution globale.
De plus, les problèmes liés aux rapports de masse élevés dans les contraintes d'égalité sont résolus en préconditionnant le PGS à l'aide de la décomposition LDL clairsemée de la matrice des contraintes d'égalité. Les sous-matrices denses de la matrice des contraintes sont clairsemées à l'aide d'une méthode que nous appelons « Body Splitting ». Celle-ci est similaire à la décomposition LDL utilisée dans Baraff 1996, mais permet de traiter des systèmes mécaniques plus généraux et résout le système dans l'espace des contraintes. Pour plus d'informations, vous pouvez consulter ma présentation au GDC 2020.
L'architecture de notre solveur suit l'idée de Guendelman-Bridson-Fedkiw, où les pas de vitesse et de position sont séparés par la résolution des contraintes. Notre séquence temporelle est la suivante :
- Avance des vitesses
- Résolution des contraintes dans l'espace des vitesses et l'espace des positions
- Avance des positions
Ce schéma présente l'avantage de n'intégrer que des vitesses valides et de limiter la latence dans l'application des forces externes, tout en autorisant une légère violation perçue des contraintes due à la dérive numérique.
Une excellente référence pour la simulation de corps rigides est l'ouvrage d'Erleben (2005), récemment mis à disposition gratuitement. Vous trouverez des cours en ligne sur l'animation basée sur la physique, un blog de Nilson Souto sur la création d'un moteur physique, une très bonne présentation de la GDC par Erin Catto sur les méthodes de résolution modernes, ainsi que des forums tels que le Bullet Physics Forum et GameDev, qui constituent d'excellents endroits pour poser des questions.
En conclusion
Le domaine de la simulation physique dans les jeux vidéo présente de nombreux problèmes intéressants, à la fois passionnants et stimulants. Il offre l’occasion d’apprendre une quantité considérable de mathématiques et de physique passionnantes et d’utiliser des techniques d’optimisation modernes. C’est un domaine du développement de jeux vidéo qui allie étroitement les mathématiques, la physique et le génie logiciel.
Même si Roblox dispose d’un bon moteur de physique des corps rigides, il existe des domaines où il peut être amélioré et optimisé. De plus, nous travaillons sur de nouveaux projets passionnants tels que la fracturation, la déformation, les corps souples, les tissus, l’aérodynamique et la simulation de l’eau.
Ni Roblox Corporation ni ce blog ne cautionnent ou ne soutiennent aucune entreprise ou service. De plus, aucune garantie ni promesse n'est donnée quant à l'exactitude, la fiabilité ou l'exhaustivité des informations contenues dans ce blog.
Cet article a été initialement publié sur le blog technique de Roblox.
