Ten Minute Physics

Classical and continuum mechanics are hundreds of years old. A surprising amount of the numerics is pretty old too.

I have a question about the position-based dynamics approach. Since the constraints are solved iteratively for every element in the simulation, you can still end up with a system where the constraints do not hold for some of the elements.

Example: you have a link between A and B, and a link between B and C. If you adjust A and B according to the length of the link, and then B and C according to the other length, you've moved B again, and the firsts link might not have the right length anymore.

Depends on how you solve the constraints. The papers use an iterative method that might not converge to meet all constraints all the time but you can use others instead. In general though the constraint satisfaction is good enough with the iterative approach.

I’m writing a physics engine in my spare time for fun using XPBD so here’s a look at the iterative method in action: https://youtu.be/A3_W_EFFsm8

This is running in Chrome at 60Hz with fifteen sub-steps, each with one constraint solver iteration.

Am currently integrating rigid bodies which is fun.

These references helped me a lot when building a spatial hashed fluid sim that runs on the GPU:

https://developer.download.nvidia.com/presentations/2008/GDC... https://wickedengine.net/2018/05/21/scalabe-gpu-fluid-simula...

(See from page 16 on the NVIDIA presentation)

I think your question speaks to something deep and interesting about XPBD.

All classical mechanics sims revolve on some level around "integrating" Newton's second law of motion: F=ma. Force equals mass times acceleration. XPBD constraints correspond directly to forces, and acceleration is the second time derivate of position. So to update positions every frame, which is what we want our physics sim to do, we need to integrate F=ma.

Usually we want to use an integrator in the family of "unconditionally stable" integrators. These integrators are guaranteed not to blow up, no matter what weird, difficult input the user gives to the simulation. In realtime physics sims we generally use one called "Implicit Euler." And Implicit Euler is the worst one! It's the least accurate and it adds huge amounts of artificial damping, but it has one really big thing going for it. It's the most resilient to "under-converged" solutions to the equations of motion.

So, like you pointed out in your question, if you resolve the constraints one after the other, constraints further down the list are likely to violate previous constraints. Most of the time you can mitigate this by running over the list of constraints multiple times, but you'd have to do that many many times for your constraints to perfectly "converge," such that they are all simultaneously satisfied.

The more accurate and energy preserving unconditionally stable integrators, like "Implicit Midpoint," require perfectly converged solutions. If you don't resolve your constraints perfectly, the "unconditionally stable" Implicit Midpoint will explode! But good ol' Implicit Euler is much less up tight. You can give it surprisingly under-converged solutions and it'll keep on trucking. The shortcomings of Implicit Euler are reduced by taking smaller timesteps between frames, so you generally get the best bang for your buck by investing compute time into more frames with a sloppy, non-converging solver, than using a better integrator that forces convergence.

At least that's what it looks like now. There's still tons of active research going on in these areas. Maybe someone will discover a faster solver that makes convergence easier, in which case we'll all switch over to move sophisticated integrators.