Carmen's Graphics Blog

Computer Graphics and Physics Simulation Tutorials and Articles
PostsAboutProjectsJobs

Dynamique basée sur la position étendue | XPBD

XPBD réduit les problèmes de stabilité et les erreurs qui surviennent dans les simulations PBD. Cette semaine, nous examinerons XPBD d'un point de vue générale pour voir comment il peut simplifier notre boucle de simulation.

Keywords: dynamique basée sur la position, simulation de tissu, lagrange, physique, infographie

By Carmen Cincotti  

Cette semaine, j’ai pas beaucoup de temps pour écrire un article. Cela dit, j’aimerais juste présenter le sujet sur lequel nous nous concentrerons à l’avenir. C’est le sujet de XPBD, qui en français se traduit par la position dynamique basée sur la position - étendue (extended position based dynamics).

XPBD est une réponse à un problème de rigidité rencontré avec le PBD. Si l’on inclut une constante de raideur, kk, dans le calcul de Δx\Delta x lors de la satisfaction des contraintes, par exemple :

Δx=ksM−1∇C(x) \Delta x = ks\mathbf{M}^{-1}\nabla C(\mathbf{x})

…il a été constaté que les contraintes deviennent infiniment rigides.

Plus précisément, kk est dépendant du pas de temps et du nombre d’itérations de la simulation. Les contraintes deviennent infiniment rigides au fur et à mesure que le nombre d’itérations se rapproche vers l’infini, ou que le pas de temps diminue.

Ainsi, notre objectif de cette semaine est d’explorer deux articles qui améliorent le PBD. Voici deux articles qui peuvent aider à fournir un contexte pour la discussion d’aujourd’hui :

XPBD

XPBD vise à éliminer les dépendances suivantes qui influencent la rigidité effective du système :

  • Le pas de temps
  • Le nombre d’itérations effectuées lors de la satisfaction des contraintes.

Ce problème se produit lors de simulations où plusieurs types de matériaux sont utilisés (c’est-à-dire des corps mous interagissant avec des corps rigides).

Pour résoudre ce problème, l’algorithme PBD est étendu pour avoir une correspondance directe avec la deuxième loi de Newton.

Regardons l’algorithme proposé :

Algorithme

La boucle de simulation de XPBD - Source

Rappelons que la boucle de la simulation de PBD dont nous avons déjà parlé dans mon article dernier. La différence la plus importante est cette idée de calculer itérativement λ\lambda à la ligne (9).

Plus précisément, le calcul du changement du multiplicateur de Lagrange, Δλ\Delta \lambda, au cours d’une itération du solveur est défini comme suit :

Δλ=−C(x)−α~λ∇C(x)M−1∇C(x)T+α~ \Delta \lambda = \frac{-C(\mathbf{x}) - \tilde{\alpha} \lambda}{\nabla C(\mathbf{x}) \mathbf{M}^{-1} \nabla C(\mathbf{x})^T + \tilde{\alpha}}

où α~\tilde{\alpha} est une matrice bloc-diagonale de compliance qui corresponde à l’inverse des constantes de raideur, 1k\frac{1}{k}. En plus, les contraintes sont régularisées avec α~\tilde{\alpha} qui résulte de la factorisation d’un potentiel d’énergie quadratique.

En termes de pas de temps, on peut dire que :

α~=αΔt2 \tilde{\alpha} = \frac{\alpha}{\Delta t^2}

Quand α=0\alpha = 0, on arrive à l’équation de PBD ! Ce fait n’est pas choquant si l’on considère qu’un facteur de compliance égale à 0 est pareil à un raider égal à l’infini, ∞=1/0\infty = 1 / 0.

Tout cela dit, nous pouvons définir Δx\Delta \mathbf{x} comme suit :

Δx=M−1∇C(x)TΔλ \Delta \mathbf{x} = \mathbf{M}^{-1}\nabla C(\mathbf{x})^T\Delta \lambda

N’oublions pas que nous ne verrons les équations finales que cette semaine. Nous traiterons de leurs dérivations dans un article ultérieur.

Des petits pas - (Small steps)

Il s’avère que nous pouvons rendre cette simulation encore meilleure. En prenant des pas de temps plus petits pour avancer la simulation, plutôt que de résoudre de manière itérative le système de contraintes pour chaque pas de temps plus grands, nous pouvons augmenter la stabilité du système et réduire les erreurs pour une large gamme de paramètres de rigidité.

Voici l’algorithme avec ce constat :

Algorithm of XPBD with small steps

Ce qui est intéressant, c’est que nous n’avons aucune raison de continuer à stocker λ\lambda parce que nous résolvons les fonctions contraintes une seule fois pour chaque petit pas. Autrement dit, la modification de λ\lambda ne se propage pas aux futures itérations de résolution de contraintes, ce qui est contraire à PBD.

De fait que nous n’effectuons qu’une itération par sous-pas de temps et que la valeur initiale du multiplicateur de Lagrange est 0, nous pouvons réécrire l’équation pour Δλ\Delta \lambda comme suit :

Δλ=−C(x)∇C(x)M−1∇C(x)T+α~ \Delta \lambda = \frac{-C(\mathbf{x})}{\nabla C(\mathbf{x}) \mathbf{M}^{-1} \nabla C(\mathbf{x})^T + \tilde{\alpha}}

Cette équation sera utilisée lors de la simulation du tissu !

Comme je l’ai déjà dit, cette semaine notre conversation serait courte, car j’ai une semaine chargée ! Dans un prochain article, nous verrons les dérivations de toutes les équations que nous venons de voir.

Des ressources (en français et anglais)

Comments for Dynamique basée sur la position étendue | XPBD

Written by Carmen Cincotti, computer graphics enthusiast, language learner, and improv actor currently living in San Francisco, CA.  Follow @CarmenCincotti

Contribute

Interested in contributing to Carmen's Graphics Blog? Click here for details!