Resting Contact in rigid body simulation. . .

[xissburg]

Hi, my first post here. I hope to get some good responses

I got a rigid body simulator working but with no resting contact support, then when the bodies comes to rest they inter-penetrate and another problems is that if a body receives two or more collisions at the same time-step, the impulses will not be applied correctly(the energy of the system increases though).

But, what the hell I want here?! Well, advices. What methods should I use to solve my problems(resting contact and multiple simultaneous collisions)? I want a physically correct simulation(but it doesn't need to be too much ), no penalty methods like in the Erin Catto 's Box2D where the bodies penetrates a lot sometimes and there a lot of visible inaccuracies, I don't like that. Recommend me some papers please .

Thanks.

[Dirk Gregorius]

Well, I think if you want to avoid penetration the most obvious way is continuous collision detection (CCD). Personally I doubt that you will get away without any penetration in all cases, so it is generally a good idea to have a simulator that can deal with this, like Erin Catto's Box2D. Note that Erin released an updated version that corrects the position error in the same frame as a post-stabilization step which should help a little with the penetration. Also note that this method is not a penalty method. One can reformulate a stiff differential equation as a constraint and those are equivalent only in the limit of an infinite stiff penalty term which I doubt is the case here. But I agree in the broad sense they are similar and one can see the constraints as an implicit channel. I never implemented a penalty method, but I think Ageia used a penalty method in the beginning and then switch to the constraint based apporach. Actually the constraint based approach works very good from my experience and deals naturally with multiple simultaneous collisions...

References are the papers of Redon and Mirtich. Erwin has also a draft on CCD here:

http://i3d.inrialpes.fr/~redon/
http://www.kuffner.org/james/software/d ... index.html
http://www.merl.com/reports/docs/TR2000-17.pdf
http://www.continuousphysics.com/Bullet ... ection.pdf
http://graphics.ewha.ac.kr/catch/
http://graphics.ewha.ac.kr/fast/

HTH,
-Dirk

[Dirk Gregorius]

BTW: One can proove that sequential impulses never add energy to the system, so when your system gains energy you most propably have a bug in your implementation.

[xissburg]

What I want is to solve the Af=b system. I've seen methods like Gauss-Seidel, but I'm not sure if its just use that to find f and apply the fs on the in contact bodies. If yes it seems quite easy though. What do you think?! thanks guys

[Dirk Gregorius]

Well, sequentiell impulses (SI) and Gauss-Seidel (GS) solve A*x = b iteratively. Both are mathematical equivalent. Note that for contact and limits you actually have a MLCP. So in this case you solve

w = A*x + b >= 0, x >= 0, x_i * w_i = 0

You could use a direct method like e.g. Dantzig or Lemke. IIRC the ODE also has a PCG solver. The problem is that the system usually is over-determined and these solver don't find a solution. I can't say if this can be adressed since I never implemented these methods though. The PGS/SI have the advantage that they can handle the over-determined system, basically by dividing the weight over all contact points. Another advantage is that with each iteration the solution improves usually. This is e.g. not the case for CG which is also an iterative method...

[xissburg]

Just to not rewrite that, could you please look at the last post in this thread at GameDev http://www.gamedev.net/community/forums ... _id=467533?!

I'm somewhat desperate to learn how to do this thing

Thanks =)

[Dirk Gregorius]

Look at my answers in this thread http://www.bulletphysics.com/Bullet/php ... f=4&t=1534.

Do you understand that you need to solve a DAE to simulate constrained dynamics?
Do you understand that geometric/positions constraints also impose restrictions on the velocity and acceleration?
Do you understand that at the end of the timestep all these constraints must be satisfied?
Do you understand Lagrange multipliers ( http://en.wikipedia.org/wiki/Lagrange_multiplier )?
Do you understand that contacts only work in one direction and that you therefore need to solve a LCP (as MrRowl correctly pointed out)

A good idea might be to simulate a simple pendulum and a dropping ball. Implement different solution approaches (e.g. Jacobsen, Catto or Baraff) and compare the results to the correct solutions and understand the differences...

[xissburg]

:^(

Q:Do you understand that you need to solve a DAE to simulate constrained dynamics?
A: yes

Q:Do you understand that geometric/positions constraints also impose restrictions on the velocity and acceleration?
A: yes

Q:Do you understand that at the end of the timestep all these constraints must be satisfied?
A: yes

Q:Do you understand Lagrange multipliers?
A : a little

Q: Do you understand that contacts only work in one direction and that you therefore need to solve a LCP (as MrRowl correctly pointed out)
A: yes

Then my workaround is invalid : ( . It seems that Baraff techniques are not easy though . . . I think I have to go with Sequential Impulses . Well, I'll try reading something about that . . . thanks

[Dirk Gregorius]

The classical way to solve a DAE that arises from constrained dynamics is to differentiate the constraint equations twice and solve for the Lagrange multipliers. Assume that you can always compute a solution even for overdetermined systems. Now that you have the Lagrange multipliers (LM) you can use any integrator you want, e.g. RK4. Even with the correct constraint forces (LM) you still may end up with errors in the position and velocity constraints. Think of a pendulum. If your velocity is tangential to the arc you still might end up "outside" the arc even though you have the correct constraint forces. So what you need to do is to project the bob back onto the arc or more generally you need to project the position and velocties back onto the constraint manifolds. So what you need to do is first correct positions and then the velocities using the corrected positions for the Jacobian. With this approach you find C(t+dt) = 0 and dC/dt(t+dt) = 0. This approach suffers from infinite friction forces. See the PhD of Anitescu that explains this if you are interested.

The velocity approach doesn't differentiate the constraint equations twice, but only once and approximates the acceleration using the differential quotient. E.g.:

dv/dt = W * ( f_ext + JT * lambda )
dx/dt = v

C(x,t) = 0

Now we approximate dv/dt ~ ( v(t+dt) - v(t) ) / dt

( v(t+dt) - v(t) ) / dt = W * ( f_ext + JT * lambda ) <=> v(t+dt) = v(t) + W * ( f_ext + JT * lambda ) * dt

We know that dC/dt = del_C/del_x * dx/dt + del_C/dt = J * v + del_C/dt. Let's assume for simplicity that C doesn't explicetely depent on t we get dC/dt = J * v

So what we want is that v(t+dt) satisfies the velocity constraints:

J * v(t+dt) = 0 <=> J * [ v(t) + W * ( f_ext + JT * lambda ) * dt ] = 0 <=> J*W*JT * lambda = - [ v(t) / dt + W * f_ext ] = A * x = b with A = J*W*JT, x = lambda and b = - [ v(t) / dt + W * f_ext ].

This is the system that the ODE solves using PGS. In the presence of constact or limit constraints we add inequalities and therefore need to solve a MLCP.

So look at the system and how PGS solves this. You will find out that this is equivalent to apply sequential impulses...


HTH,
-Dirk

[Erwin Coumans]

Thanks for the explanation Dirk.

It is funny, because one of the benefits of pair-wise applying impulses on rigidbodies (relaxation, Sequential Impulse) is very intuitive and easy to understand. So it would be good to explain this first in terms of bodies, velocities, impulses, instead of trying to explain it using the less intuitive approach (lots of math derivation, PGS, LCP etc). Later, once the intuition is there of the approach, we can introduce all the math formulaes etc.

Dirk, have you already tried explaining the process of sequential impulse just in terms of iterations, positional error, velocity error, clamping the accumulated impulse, rigidbodies, impulses, without reverting to PGS and math formulaes? It seems useful.

Thanks,
Erwin

[Dirk Gregorius]

Let me try.

We have several rigid bodies which are subject to position and velocity constraints. The idea is now to forget about the global solution and solve the pairwise constraints in an iterative loop. This is often refered to as pairwise relaxation. There exist lots of "dialects" of this method. E.g.

a) Relaxing position constraints using a Verlet integrator (actually this is the Rattle algorithm from molecular dynamics introduced to the game community by Jacobsen)
b) Relaxing velocity constraints using impulses and symplectic Euler (like found in Solid, Bullet or Box2D)
c) Relaxing velocity constraints using impulses and relaxing position constraints in a second sweep using pseudo impulses directly on the position and orientation (like found in the new Box2D)

Of course you can come up with many other variations, e.g. Jan Bender's method. Anyway the principle idea stays the same that you solve the individual constraints independently and find the global solution by iteration. One gotcha you need to understand is that you have several constraint levels, namely position-, velocity- and acceleration constraints.

My personal opinion though is that you need to come top-down with all this nasty math stuff to understand the limitations of the solving approach so you can adress this when you run into problems. But I agree for introduction you should look at it as simple pairwise relaxation...

[xissburg]

I'm very frustrated : (

I really don't like the sequential impulses method . . . it is unrealistic and inaccurate and have lots of problems that I could see in some simulations in Box2D, and it also need some workarounds to make things look a bit better. What I wanna know now is what method do the developers of games like Need For Speed Underground/ProStreet, Gran Turismo, Test Drive Unlimited, etc use?! I cant believe they use SI, but if they do, its a very different SI because I don't see any problems at there. . . Could someone PLEASE say me what method is that?! I'm desperate : (

Thanks for the help : D

[John Schultz]

I'm very frustrated : (
. . . it is unrealistic and inaccurate and have lots of problems that I could see in some simulations in Box2D, and it also need some workarounds to make things look a bit better. What I wanna know now is what method do the developers of games like Need For Speed Underground/ProStreet, Gran Turismo, Test Drive Unlimited, etc use?! I cant believe they use SI, but if they do, its a very different SI because I don't see any problems at there. . .

The racing games mentioned, since I don't recall much (any) stacking or complex configurations (knocking over light posts, mailboxes, etc., in addition to car bumping), could be using simple penalty-spring methods or weighted/averaged impulses (which are easy to implement, fast, and work very well when there is no stacking or complex configurations).

While it's not clear what problems you see with Box2D, many more demos, papers, and source examples exist which show that SI is one of the best ways to implement real-time physics.
Check out the videos next to Nonconvex rigid bodies with stacking: http://www.graphics.stanford.edu/~erang/.

http://www.cs.ubc.ca/~rbridson/
http://www.graphics.stanford.edu/~fedkiw/

Jan Bender's page: http://www.impulse-based.de/, see the videos and try the demos (http://i31www.ira.uka.de/docs/LinearTime.pdf (papers) and source code as well).

Impulse-based methods are fast, accurate, look great, and can realistically handle stacking and complex configurations.

[xissburg]

Impulse-based methods are fast, accurate, look great, and can realistically handle stacking and complex configurations.

Except in Box2D then =). Well, I really think that the only escape for me is SI though =/. Could you point me "THE" Sequential Impulses tutorial/paper/article?!(I think you have already pointed it out on those links but I'm not sure what is 'THE' one). I'll go with that . . .

Thanks a lot =D

[xissburg]

OH and I forgot to mention the 3dsmax (Havok's) reactor. Do anyone know it? And do anyone have any idea about how it works?!