À la mi-2015, Roblox a dévoilé une mise à niveau majeure de son moteur physique: le solveur physique projeté Gauss-Seidel (PGS). Pour la première année, le nouveau solveur était en option et offrait une fidélité améliorée et de meilleures performances par rapport au solveur à ressort précédemment utilisé.
En 2016, nous avons ajouté la prise en charge d'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 utilisaient 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 à des différences de masse élevées et à des mécanismes complexes par l'introduction du solveur hybride LDL-PGS à la mi-2018. Cela a rendu l'ancien 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 été encore améliorées grâce au multi-threading qui divise la simulation en tâches constituées d'îlots connectés de pièces de simulation. 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 des performances, et nous prévoyons d'ajouter de nouvelles fonctionnalités dans un avenir prévisible.
Mettre en œuvre les 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 rigides, qui se heurtent et ont des contraintes les uns avec les autres.
Un moteur physique est organisé en deux phases: détection et résolution des collisions. Détection de collision trouve 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. Puis 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 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 faire cela à 100% avec précision est d'un coût prohibitif, et le truc pour le simuler en temps réel est de se rapprocher pour augmenter les performances, tant que le résultat est physiquement réaliste. Tant que les lois de base du mouvement sont maintenues dans une tolérance raisonnable, ce compromis est tout à fait acceptable pour une simulation de jeu sur ordinateur.
Faire de petits pas
L'idée principale du moteur physique est de discrétiser le mouvement en utilisant pas de temps. 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é permettant de les résoudre approximativement. Cela signifie qu'à chaque pas de temps, le mouvement des parties pertinentes des corps rigides qui sont impliquées dans une contrainte est approché linéairement.
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 un mouvement de rotation. Plus tard, nous verrons des méthodes d'atténuation qui aident à réduire la dérive et à rendre la simulation plus plausible.
Résoudre
Après avoir linéarisé les équations de mouvement pour un pas de temps, 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 volumineux et peuvent encore être assez coûteux à résoudre exactement. Encore une fois, 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 le Gauss-Seidel projeté (PGS). C'est un méthode itérative, ce qui signifie qu'à chaque itération la solution approximative est rapprochée de la vraie solution, 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 sphériques tout en préservant le centre de gravité à chaque étape (c'est un type de solveur positionnel utilisé par le dragger IK). Bien que cet exemple présente une solution analytique simple, il constitue une bonne démonstration de l’idée derrière le PGS. A chaque étape, le solveur corrige 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 du couplage d'interactions avec des corps plus lourds. Si nous n’effectuons pas suffisamment d’itérations, la partie jaune risque de rester dans un état visiblement invalide où l’une de ses deux contraintes est violée de manière dramatique. C'est ce qu'on appelle le rapport de masse élevé problème, et il 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, sinon il devient instable. Équilibrer les deux côtés a été un processus douloureux et long.
Stratégies d'atténuation
Un solveur a deux sources majeures d’imprécision: le pas de temps et la résolution itérative (il existe également une dérive en virgule flottante mais elle est mineure par rapport aux deux premiers). Ces inexactitudes introduisent des erreurs dans la simulation, la faisant dériver du bon chemin. Une partie de cette dérive est tolérable comme des vitesses légèrement différentes ou une perte d'énergie, mais d'autres ne sont pas comme des instabilités, des gains d'énergie importants ou des contraintes disloquées.
Par conséquent, une grande partie de la complexité du solveur provient de la mise en œuvre de méthodes pour minimiser l'impact des inexactitudes de calcul. Notre implémentation finale utilise des stratégies d'atténuation traditionnelles et novatrices:
- Démarrage à chaud: en commençant par 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 vers le collecteur de contraintes pour éviter la dérive des contraintes
- Régularisation: ajouter la conformité aux contraintes garantissant l'existence d'une solution et son caractère unique
- Pré-conditionnement: utilisant une solution exacte à un sous-système linéaire, améliorant la stabilité de mécanismes complexes
Les stratégies 1, 2 et 3 sont assez traditionnelles, mais la 3 a été améliorée et perfectionnée par nous. De plus, bien que 4 ne soit pas inconnu, nous n’en avons vu aucune mise en œuvre 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 le PGS. L'implémentation qui en résulte n'est que légèrement plus lente par rapport au PGS pur 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 souffrent que de la dérive provenant de la discrétisation temporelle. Des détails sur nos méthodes sont contenus dans ma présentation GDC 2020. Actuellement, nous étudions les méthodes directes appliquées aux contraintes d'inégalité et aux collisions.
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 dirigées par Featherstone, qui paramétrent les degrés de liberté à 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énalité utilisées auparavant. Les méthodes d'analyse ont été initialement introduites dans Baraff 1989, où elles sont utilisées pour traiter les contraintes d'égalité et de non-égalité de manière cohérente. 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 formulation basée sur la force, nous utilisons une formulation basée sur les impulsions dans l'espace des vitesses, initialement introduite par Mirtich-Canny 1995 et encore améliorée par Stewart-Trinkle 1996, qui unifie le traitement des différents types de contact et garantit l'existence d'une solution pour les contacts avec frottement. A chaque pas de temps, les contraintes et les collisions sont maintenues en appliquant des changements instantanés de vitesses dus à des impulsions de contrainte. Une excellente explication de la raison pour laquelle la simulation basée sur les impulsions est supérieure est contenue dans la présentation GDC de Catto 2014.
Les contacts sans frottement sont modélisés en utilisant un problème de complémentarité linéaire (LCP) comme décrit dans Baraff 1994. Le frottement est ajouté comme une projection non linéaire sur le cône de friction, entrelacé avec les itérations du Gauss-Seidel projeté.
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 introduites 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é de contraintes.
Les LCP sont résolus en utilisant un PGS / Impulse Solver popularisé par Catto 2005 (voir aussi Catto 2009). Cette méthode est itérative et considère chaque contrainte individuelle dans l'ordre 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é dans les contraintes d'égalité sont aplanis en préconditionnant le PGS à l'aide de la décomposition LDL éparse de la matrice de contraintes des contraintes d'égalité. Les sous-matrices denses de la matrice de contraintes sont sparsifiées à l'aide d'une méthode que nous appelons Body Splitting. Ceci est similaire à la décomposition LDL utilisée dans Baraff 1996, mais permet des systèmes mécaniques plus généraux et résout le système dans l'espace de contraintes. Pour plus d'informations, vous pouvez voir ma présentation GDC 2020.
L'architecture de notre solveur suit l'idée de Guendelman-Bridson-Fedkiw, où la vitesse et le pas de position sont séparés par la résolution de la contrainte. Notre chronologie est:
- Vitesse d'avance
- Résolution des contraintes dans l'espace de vitesse et l'espace de position
- Avancer des positions
Ce schéma a l'avantage d'intégrer uniquement des vitesses valides, et de limiter la latence dans l'application de la force externe mais de permettre une petite quantité de violation de contrainte perçue due à la dérive numérique.
Une excellente référence pour la simulation de corps rigides est le livre Erleben 2005 qui a été récemment mis à disposition gratuitement. 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 GDC par Erin Catto sur les méthodes de solveurs modernes et des forums comme le Bullet Physics Forum et GameDev qui sont d'excellents endroits pour poser des questions. des questions.
En conclusion
Le domaine de la simulation physique des jeux présente de nombreux problèmes intéressants qui sont à la fois passionnants et stimulants. Il existe des opportunités d'apprendre une quantité substantielle de mathématiques et de physique sympas et d'utiliser des techniques d'optimisation modernes. C’est un domaine du développement de jeux qui marie étroitement les mathématiques, la physique et l’ingénierie logicielle.
Même si Roblox a un bon moteur de physique des corps rigides, il y a des domaines où il peut être amélioré et optimisé. En outre, nous travaillons sur de nouveaux projets passionnants tels que 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 n'approuvent ou ne soutiennent aucune entreprise ou service. De plus, aucune garantie ou promesse n'est faite concernant l'exactitude, la fiabilité ou l'exhaustivité des informations contenues dans ce blog.
Cet article de blog a été initialement publié sur le blog Roblox Tech.
