Impulse-Based Dynamic Simulation

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

IBDS algorithm:

This example shows the impulse-based dynamic simulation (IBDS) method [BFS05, BS06]. IBDS is a predictor-corrector method to perform a simulation step for a constrained system. For each position constraint $C(\mathbf x) = 0$ a corresponding velocity constraint is defined as the time derivative $\dot C(\mathbf x) = 0$.
  1. position constraint solver
  2. time integration
  3. velocity constraint
Position constraint solver:
  1. loop
  2. time integration to predict particle positions
  3. compute Lagrange multiplier
  4. determine correction impulse
  5. update velocities
Velocity constraint solver:
  1. loop
  2. compute Lagrange multiplier
  3. determine correction impulse
  4. 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 = 0,$$ where $d$ is the rest length between particles $\mathbf{x}_{i_1}$ and $\mathbf{x}_{i_2}$. The corresponding velocity constraints are defined as $$\dot C_i(\mathbf{x}_{i_1}, \mathbf{x}_{i_2}) = \frac{\mathbf x_{i_1} -\mathbf x_{i_2}}{\| \mathbf x_{i_1} -\mathbf x_{i_2} \|}(\mathbf v_{i_1} -\mathbf v_{i_2}) = 0.$$ Note that no inversion handling is implemented in this example. So the model might get tangled.

1. Position constraint solver loop

Correction impulses are computed and applied in a loop using a fixed number of iterations or until the error is within a user-defined tolerance.

2. Time integration

In the first step of the position constraint solver 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.

3. Compute Lagrange multipliers

The general form to compute the Lagrange multipliers in IBDS is $$\mathbf J \mathbf M^{-1} \mathbf J^T \boldsymbol \lambda = -\frac{1}{\Delta t} \mathbf C(\mathbf x^*),$$ 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)}{\Delta t \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 of the distance constraints 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. Correction impulse:

The correction impulse is determined as: $$\mathbf p = \mathbf J^T \lambda$$

5. Velocity update:

Finally, the velocity of a constrained particle is updated: $$\Delta \mathbf v = \frac{1}{m} \mathbf p$$

Velocity constraint solver loop

The velocity constraints $\dot C(\mathbf x) = 0$ are solved analogously to the position constraints. The Lagrange multipliers are determined by solving: $$\mathbf J \mathbf M^{-1} \mathbf J^T \boldsymbol \lambda = -\mathbf {\dot C}(\mathbf x).$$ However, note that no position prediction is required since the solve is performed after the time integration step.

Time integration

The particles are advected by numerical time integration. In our case we use a symplectic Euler method: $$\begin{align*} \mathbf v(t + \Delta t) &= \mathbf v(t) + \frac{\Delta t}{m} \mathbf f^{\text{ext}}(t) \\ \mathbf x(t + \Delta t) &= \mathbf x(t) + \Delta t \mathbf v(t + \Delta t), \end{align*}$$ where $\mathbf f^{\text{ext}}$ are the external forces.

References

  • [BS06] Jan Bender and Alfred Schmitt. Fast Dynamic Simulation of Multi-Body Systems Using Impulses. In Proceedings of Virtual Realitiy, Interactions, and Physical Simulation, 2006. Eurographics Association.
  • [BFS05] Jan Bender, Dieter Finkenzeller and Alfred Schmitt. An impulse-based dynamic simulation system for VR applications. In Proceedings of Virtual Concept 2005