Position-Based Dynamics

Your browser does not support the HTML5 canvas tag.
0.00 s
0.00 ms
0
0

PBD algorithm:

This example shows the position based dynamics method introduced by Müller et al. [MHHR06,BMM17].
  1. time integration to predict particle positions
  2. loop
  3. compute Lagrange multipliers
  4. determine position correction
  5. update velocities
In this example we use distance constraints $$C_i(\mathbf{x}_{i_1}, \mathbf{x}_{i_2}) = \| \mathbf x_{i_1} -\mathbf x_{i_2} \|-d,$$ where $d$ is the rest length between particles $\mathbf{x}_{i_1}$ and $\mathbf{x}_{i_2}$.

1. Time integration

In the first step the particle positions are advected using a symplectic Euler method to obtain predicted positions $\mathbf x^*$: $$\begin{align*} \mathbf v^* &= \mathbf v(t) + \Delta t \mathbf a_\text{ext}(t) \\ \mathbf x^* &= \mathbf x(t) + \Delta t \mathbf v^*, \end{align*}$$ where $\mathbf a_\text{ext}$ are accelerations due to external forces.

2. Solver loop

Position corrections are computed and applied in a loop using a fixed number of iterations.

3. Compute Lagrange multipliers

The general form to compute the Lagrange multipliers in position-based dynamics is $$\mathbf J \mathbf M^{-1} \mathbf J^T \boldsymbol \lambda = -\mathbf C(\mathbf p),$$ where $\mathbf J = (\partial C / \partial \mathbf x)^T$ is the Jacobian of the constraint function and $\mathbf M$ denotes the mass matrix.

Since the distance constraint is a scalar function the Lagrange multiplier is determined as $$\lambda_i = - \frac{C_i(\mathbf x)}{\sum_j \frac{1}{m_j} \| \partial C_i(\mathbf x) / \partial \mathbf x_j\|^2},$$ where $j$ denotes the indices of the particles which are influenced by the constraint.

To compute the Lagrange multipliers, the constraint gradients are required which are computed as:

Constraint gradients:

$$\begin{align*} \frac{\partial C_i}{\partial \mathbf x_{i_1}} &= \frac{\mathbf x_{i_1} -\mathbf x_{i_2}}{\| \mathbf x_{i_1} -\mathbf x_{i_2} \|} \\ \frac{\partial C_i}{\partial \mathbf x_{i_2}} &= - \frac{\mathbf x_{i_1} -\mathbf x_{i_2}}{\| \mathbf x_{i_1} -\mathbf x_{i_2} \|} \end{align*}$$

4. Position correction:

The position correction for a particle is determined using the Lagrange multiplier: $$\begin{align*} \Delta \mathbf x_{i_1} &= \frac{1}{m_{i_1}} \frac{\partial C_i}{\partial \mathbf x_{i_1}} \lambda_i = -\frac{\frac{1}{m_{i_1}}}{\frac{1}{m_{i_1}} + \frac{1}{m_{i_2}}}(\|\mathbf{x}_{i_1} - \mathbf{x}_{i_2}\|-d)\frac{\mathbf{x}_{i_1}- \mathbf{x}_{i_2}}{\|\mathbf{x}_{i_1} - \mathbf{x}_{i_2}\|} \\ \Delta \mathbf x_{i_2} &= \frac{1}{m_{i_2}} \frac{\partial C_i}{\partial \mathbf x_{i_2}} \lambda_i = +\frac{\frac{1}{m_{i_2}}}{\frac{1}{m_{i_1}} + \frac{1}{m_{i_2}}}(\|\mathbf{x}_{i_1} - \mathbf{x}_{i_2}\|-d)\frac{\mathbf{x}_{i_1}- \mathbf{x}_{i_2}}{\|\mathbf{x}_{i_1} - \mathbf{x}_{i_2}\|} \end{align*}$$ and the correction is applied to update $\mathbf x^*$ as $$\mathbf x^* := \mathbf x^* + \Delta \mathbf x.$$

5. Velocity update:

The final positions and velocities are computed as: $$\begin{align*} \mathbf x_i(t+\Delta t) &= \mathbf x_i^* \\ \mathbf v_i(t+\Delta t) &= \frac{1}{\Delta t} (\mathbf x_i(t+\Delta t) - \mathbf x_i(t)) \end{align*} $$

References

  • [MHHR06] Matthias Müller, Bruno Heidelberger, Marcus Hennix, John Ratcliff. Position Based Dynamics. In Proceedings of Virtual Realitiy, Interactions, and Physical Simulation, 2006. Eurographics Association.
  • [BMM17] Jan Bender, Matthias Müller, Miles Macklin. A Survey on Position Based Dynamics, 2017. Eurographics Tutorials, 2017