Impulse-based dynamic simulation library (IBDS)

Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Why you want to use Baumgarte terms in combination with my method...
This is just an idea if we wanted to skip the velocity constraints entirely. Since our velocity constraints wouldn't be satisfied then you can get problems with the energy. Barenbrug suggested a stabilization scheme in the case which is similar to Baumgarte. I think you mentioned once that this already looks quite nice and if we could for free stabilize this it might be a good idea...
if the sum of all impulses for a single joint is limited you can even repair total disintegrated models with my method.
What do you mean by this?
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany

Post by Jan Bender »

if the sum of all impulses for a single joint is limited you can even repair total disintegrated models with my method.
What do you mean by this?
If you have for example a model with bodies connected by ball joints. You could turn off the handling of joint constraints. Of course then all bodies will fall down. If you turn it on again, the simulation will step by step correct all constraints again and fix the model. So even if you have distances of multiple meters between the joint points the correction will work.

Jan
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine

Post by Erin Catto »

If you have for example a model with bodies connected by ball joints. You could turn off the handling of joint constraints. Of course then all bodies will fall down. If you turn it on again, the simulation will step by step correct all constraints again and fix the model. So even if you have distances of multiple meters between the joint points the correction will work.
You can also do this in Box2D (press P to toggle position correction). Of course we can't guarantee the model will be assembled in the correct kinematic branch. You can see this in demo 9 where sometimes the links will get twisted into a knot.

The post projection of position constraints in the super split method can use a Baumgarte factor of 1. In this context, using the Baumgarte parameter simply represents a damped Newton solver. Jan's solver is also a Newton solver, so it could be damped too.

Both methods can be run to any tolerance at the cost of increasing the iterations. I'm not sure if Jan ever rebuilds the Jacobian in the solver, but that is generally necessary for convergence.
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany

Post by Jan Bender »

You can also do this in Box2D (press P to toggle position correction). Of course we can't guarantee the model will be assembled in the correct kinematic branch. You can see this in demo 9 where sometimes the links will get twisted into a knot.
I just tried to start Box2D but it doesn't work with my glut32.dll. Doesn't matter.

I try to explain the difference between your method and mine. Please correct me, if I say something of wrong.

Let us assume you want to simulate two bodies connected by a ball joint. Then the position constraint is a-b=0 where a and b are the joint points.

Erin's method:

To simulate this constraint you differentiate the constraint equation with respect to time in order to get a constraint for the velocities. So in fact the position constraint is satisfied by keeping the velocities of the joint points equal. Then you compute the Jacobian J and solve the equation

M dV/dt = J^T lambda + Fext

for lambda. The problem is that the two joint points will drift apart due to numerical errors. Since the position of these points is not regarded in the velocity constraint it can't be corrected directly. So a stabilization method like the one from Baumgarte is required.

My method:

I don't differentiate the position constraint. The first step of my method is that a prediction for the positions of both joint points is made by integrating the equation

r' = omega x r

where r is the vector from the center of mass c to a joint point. The new positions at time t+h are

a(t+h) = r_a(t+h) + c(t+h)
b(t+h) = r_b(t+h) + c(t+h)

This prediction determines the positions of the joint points, if the bodies have a ballistic motion (without regarding the constraint). The distance at time t+h should be zero. So the constraint I try to satisfy looks like this:

d(t+h) = b(t+h)-a(t+h) = 0

Since the motion of the joint points is almost linear in a small time step, I use a linearization. So I determine an impulse that changes the velocities by d(t+h)/h by solving equation

K(t) * p = d(t+h)/h

where (here J is the inertia tensor not the Jacobian)

K = (1/m1+1/m2) I3 - (r_a* J1^-1 r_a* + r_b* J2^-1 r_b*)

Since K is symmetric, positive definite, constant for time t and regular (proof by Mirtich), the equation can be solved by inverting K. The resulting impulse p is applied to the bodies in opposite directions at time t (not t+h). Due to the velocity change at time t the distance d(t+h) gets smaller. In the next iteration the predicted value d(t+h) has to be computed again. Since K is constant for time t, the matrix has not to be inverted again. So in the second iteration the prediction and a simple matrix multiplication is all we need to compute the impulse.

One advantage of my method is that no additional stabilization method like Baumgarte is required, since the future distance d(t+h) is always zero after the time step.

Velocity constraint can be handled in an easier way since no prediction is required.

I hope that helps to understand the difference between the methods.

Jan
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine

Post by Erin Catto »

Since the motion of the joint points is almost linear in a small time step, I use a linearization.
By using linearization, you are "differentiating" the position constraint. K represents the effective mass of the constraint computed using the Jacobian of the position constraint.

I assume that you also have a stage for fixing the velocity errors?

So I'm guessing you have:
- integrate velocities
- project position errors by altering the velocities
- integrate positions
- project velocity errors

Box2D with Baumgarte does this:
- integrate velocities
- project Baumgarted biased velocity errors
- integrate positions

This has the obvious problem that position correction is feeding into the momentum, hence we need a Baumgarte factor to reduce the instability. Yet there seems to be no faster way of dealing with constraints.

One of the standard ways of solving multibody DAEs is to:
- integrate velocities & positions
- project position errors
- project velocity errors

See "Solving Ordinary Differential Equations II" by Hairer and Wanner or "Numerical Methods in Multibody Dynamics" by Eich-Soellner and Fuhrer. However, this works at the acceleration level and supports arbitrary integrators. When dealing with friction, it is better to work at the velocity level.

Working at the velocity level, I think an ideal algorithm would:
- integrate velocities
- project velocity errors
- integrate positions
- project position errors

In this, the position errors are zero after the step and velocity errors are only slightly off (because the position changed).

The last method is what I used in the so-called super-split method:
http://gphysics.com/files/Box2D_SuperSplit.zip

Of course this method is more expensive than the Baumgarte approach, but handles joints better.

One downside of your method seems to be that your tentative future position error is computed using bad velocities. Why not correct the velocity errors first?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Jan, doesn't use Symplectic Euler, he uses

x(t+dt) = x(t) + v(t)*dt + 0.5 * a(t) * dt^2
v(t+dt) = v(t) + a(t) * dt

This way the position and velocity integration don't depend on each other like in Box2D, Bullet or ODE. Jan said on this forum that this is superior to symplectic Euler. I can't judge this...

So basically Jan builds candidate positions for two bodies using x(t+dt) = x(t) + v(t)*dt + 0.5 * a(t) * dt^2 then velocities are iteratitvely adjusted such that the position constraints are satisfied at the end of the timestep. Then in a second phase velocities are projected.

So the new thing is that position constraints change velocities. I always wondered if this physical correct. What is somehow strange is that the Jacobian seems constant over the time intervall. I would have assumed that those would update like in a Newton solver. I would still argue that we try to solve a system of non-linear equations, right?

Jan, your K matrix is constant over the integration interval since you build it from the positions at the beginning of the timestep, right?
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany

Post by Jan Bender »

Jan, doesn't use Symplectic Euler, he uses

x(t+dt) = x(t) + v(t)*dt + 0.5 * a(t) * dt^2
v(t+dt) = v(t) + a(t) * dt

This way the position and velocity integration don't depend on each other like in Box2D, Bullet or ODE. Jan said on this forum that this is superior to symplectic Euler. I can't judge this...
These are the exact equations, if the external forces are constant for one time step. If you want to simulate springs (with a high accuracy), you have to integrate numerically.
So basically Jan builds candidate positions for two bodies using x(t+dt) = x(t) + v(t)*dt + 0.5 * a(t) * dt^2 then velocities are iteratitvely adjusted such that the position constraints are satisfied at the end of the timestep. Then in a second phase velocities are projected.
Exactly.
So the new thing is that position constraints change velocities. I always wondered if this physical correct.
This is physical correct. My boss Prof. Dr. Schmitt has spent much time for the proof and finally found it. The proof is published in "On the Convergence and Correctness of Impulse-Based Dynamic Simulation".
I would still argue that we try to solve a system of non-linear equations, right?
Yes, since the motion of the joint points is in general non-linear. Weinstein solves the non-linear equation directly by Newton iteration which leads to some problems (a student of mine is just working on a comparison). In contrast to that I use my linearization to solve the equation.
Jan, your K matrix is constant over the integration interval since you build it from the positions at the beginning of the timestep, right?
The matrix K is constant for a time t, not for the whole interval. But you only need the matrix of the beginning of the interval to compute the impulses. So for the whole iteration process it is constant. You can even use the matrix once to satisfy the velocity constraints and the same matrix for the position constraints of the next time step, since both corrections are at the same point of time.

Jan
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine

Post by Erin Catto »

x(t+dt) = x(t) + v(t)*dt + 0.5 * a(t) * dt^2
v(t+dt) = v(t) + a(t) * dt
I suggest you use symplectic Euler instead of this integrator. The parabolic integrator cannot simulate a mass spring system (no damping) without blowing up. Symplectic Euler is:

v(t+dt) = v(t) + a(t) * dt
x(t+dt) = x(t) + v(t+dt) * dt

This integrator can simulate a mass spring system of moderate stiffness while conserving energy.
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany

Post by Jan Bender »

I suggest you use symplectic Euler instead of this integrator. The parabolic integrator cannot simulate a mass spring system (no damping) without blowing up. Symplectic Euler is:

v(t+dt) = v(t) + a(t) * dt
x(t+dt) = x(t) + v(t+dt) * dt

This integrator can simulate a mass spring system of moderate stiffness while conserving energy.
As I already said, the equations can only be used, if the external forces are constant.

I have still a problem with your equations. If a body of 1kg is falling down for 1 second due to gravity of 10. Then v(t+dt) = 10m/s and x(t+dt) = 10m. But the exact solution is v(t+dt)=10 and x(t+dt) = 5.

Jan
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine

Post by Erin Catto »

There are two problems with your argument:

1) Physics engines for games usually run 15-60Hz.
2) You are only looking at the error after one time step. The global error is much less.

Here's the solution with dt = 0.1 (parabolic vs symplectic):

0 0
-0.0500 -0.1000
-0.2000 -0.3000
-0.4500 -0.6000
-0.8000 -1.0000
-1.2500 -1.5000
-1.8000 -2.1000
-2.4500 -2.8000
-3.2000 -3.6000
-4.0500 -4.5000
-5.0000 -5.5000

In the first step the error is 100%, but in the 10th step the error is 10%.

IMO it is a bad idea to publish anything that advocates using the parabolic integrator. What happens is that many people will implement the integrator because it is "exact". Then their simulations blow up because they add a spring and they don't have a clue how to fix it, so they give up on trying to simulate the simplest things.
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany

Post by Jan Bender »

In the first step the error is 100%, but in the 10th step the error is 10%.
Originally my simulation method was used for the simulation of robots. For this very accurate results were required. So a error of 10% was not acceptable at all. Anyway as long as no continuous external forces occur it is no problem to use the exact solution.
IMO it is a bad idea to publish anything that advocates using the parabolic integrator. What happens is that many people will implement the integrator because it is "exact". Then their simulations blow up because they add a spring and they don't have a clue how to fix it, so they give up on trying to simulate the simplest things.
I developed the method for my PhD. So accuracy is a important goal if you develop a method for research at the university. And I don't think it is a bad idea to use a more accurate equation if it costs you nothing (in the case that the external forces are constant for one time step).

The simulation of springs is a problem that you can't handle with my equation directly. Then either you have to use a numerical integrator or the symplectic Euler to solve the problem. An alternative is to reduce the accuracy just for springs by only regarding the spring force at the actual point of time. So the force is only regarded at discrete points of time and then handled as constant for the next time step. This is also not accurate but you have no problem with blowing up.

Jan
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

An alternative is to reduce the accuracy just for springs by only regarding the spring force at the actual point of time. So the force is only regarded at discrete points of time and then handled as constant for the next time step. This is also not accurate but you have no problem with blowing up.
You mean treating the spring force F_spring = -k*x - d * v as constant over the interval and add it to the gravity force? This will be indeed very unstable and explode.
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany

Post by Jan Bender »

You mean treating the spring force F_spring = -k*x - d * v as constant over the interval and add it to the gravity force? This will be indeed very unstable and explode.
Yes. I have done this already to simulate cloth with a mass spring system. The simulation was stable and the cloth model did not explode. It was not my main goal to simulate mass spring systems but this also works even when the spring forces are regarded as constant for one time step. In fact I didn't spend much time yet on springs since this was not so important for my work.

Jan
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Anyway, this explodes extremly fast. So if you only used soft springs for bending this might work and of course you can always use a sufficient small timestep...
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany

Post by Jan Bender »

Anyway, this explodes extremly fast. So if you only used soft springs for bending this might work and of course you can always use a sufficient small timestep...
Okay, if you want to solve a stiff differential equation, this is not the right method.

Jan