collision response w.r.t. mass ratios

[Ronin]

Hi,

I want to implement a multi-point collision constraint solver. It is important for me to overcome some limitations of sequential solvers with huge mass ratios. Therefore I'd like to solve all collisions simultaneously in one equations system.

I already wrote a simple conjugate gradients solver which I'd like to use for this task. But I have problems to create the equation system to solve. I followed the approach described in "Physics-Based Animation" by Erleben,Sporring,Henriksen,Dohlmann in Chapter 7 "Constrained-Based Multibody Animation". There a LCP is formed like: Ax + b >= 0 compl. to x >= 0. This should easily be translated into an equations system like: Ax = b.

My problem is: The matrix A has to be positive-definit to be solvable by a cg approach. How do I know if the matrix is positive-definit? I know the definitions, but I had to give up to find a prove, because it is too complex.

For anyone who read the book, I'm talking about the matrix which has this form:

Code: Select all

    | D^T C^T M^-1 C D   D^T C^T M^-1 C N   E  |
A = | N^T C^T M^-1 C D   N^T C^T M^-1 C N   0  |
    |      -E^T               Mu            0  |

Has anyone an idea, how to form the equations for multi-point contacts with friction, that are solvable by cg?

My primary concern is to overcome problems with mass ratios that come with iterative solvers. Btw, are there other problems with mass ratios besides the "heavy-object-resting-on-light-object" problem?

Is there maybe a better approach to this than cg? SOR, PGS, .... suffer all from this problem, right?

Btw, stable stacking is not a requirement for me, so I have not to take it into account anyway. Neither are any other constraints besides contacts, like joints, etc...

To conclude yet two general questions about cg:

1. I read cg gets slow, when "the active set" changes. What exactly is meant by "active set"? Does this correspond to activation/deactivation of rigid bodies?

2. What advantages has gradient projected cg over normal cg? Is it about faster converging? How much faster is it compared to cg with preconditioning?

Any pointers and hints are highly appreciated!

Thanks,
Ronin

[Dirk Gregorius]

Besides PD of the system matrix you have to makes sure that the system is solvable at all. That means you have no linear dependent contact constraints. I think it is impossible to guarantee this in a usual game scenario. E.g. even four contact points in a plane between just two bodies are already linear dependent. I think remember that somebody implemented a Lemke based solver which was able to solve this problem. It actually even came with Java source code. You might want to search the forum for it. If you don't find it I can send you the code. I never looked at it though.

[Dirk Gregorius]

I just read your post again and it seems that you want to solve the contacts with a CG solver. CG is an algorithm for solving system of linear equations. In the presence of contacts constraints you have to solve a LCP. This is where the projected CG (PCG) comes into play. So there is no difference of convergence between CG and PCG. They address different problems - LS vs LCP.

Active set has nothing to do with sleeping or deactivation of bodies. It basically says which constraints are currently active when solving a LCP or mixed LCP (MLCP). Look at the Danzig solver in the ODE for an example.

Note that there are much simpler and pragmatic ways to address the problem of large mass ratios. For a game engine I currently don't see any alternative to using a PGS like solver. It naturally handles over-constrained systems which you have a lot in games. Another example for this (besides contacts) would be a revolute (hinge) joint with active limit and motor. In this case you have seven constraints where the motor and limit might *fight* each other. I don't know how good the PCG handles these cases.

[Ronin]

This cleared some things up for me, thanks. I thought one can transform LS and LCP easily into eachother, because they look so similar. Now I've read some stuff about LCPs and have a better understanding. I have to keep on reading though, because english is not my main language and this complicates the math involved for me even further.

So I understand that I have to implement a LCP solver and your argument that PGS handles over-constrained systems well is definitly a good point for choosing it. It would be quite interesting to know, how well PCG handles this though. I weren't able to find any informations on this on the net so far.

Just to make sure I got it right: Linear dependent contact constraints are not avoidable, but PGS handles them well, because linear dependence leads to an over-constrained system, right? So with PGS I don't have to care about it?

What I don't really understand yet is the following:

When I use Coloumb friction model in the LCP, then I get a matrix similar to the one I mentioned above. Is it a requirement for PGS that the matrix has to be symmetric? (I read that somewhere in this forum...) Because if so, which approach could solve it? Are there other requirements for PGS I have to look out for?

Or the question the other way around: Which friction model could you choose, to generate a LCP that is solvable by PGS? Or even by PCG, because I read that some people here did implement it. I wonder how they form there matrix to guarantee that it is solvable.

And what are those simple and pragmatic ways to handle mass ratios that you mentioned in your last post? Do you mean, instead of a sequential approach, to solve one big matrix with all contacts simultaneously with a PGS solver?

[Dirk Gregorius]

Note that non of the iterative solvers I know build a big matrix, but solve each constraint either independently using a sparse PGS or sequential impulses (SI). I recommend looking at Box2D or Bullet and start with SI. PGS and SI are equivalent when using Erin's impulse clamping.

The ODE has a PCG solver. You might want to experiment with it.

[Ronin]

So that means any iterative solver (PGS, PCG, SOR, ...) is definitly a sequential and never a simultaneous solver? And they are not suitable for solving all collisions in one big LCP?

That's bad, because my motivation on this issue is to implement a simultaneous solver in order to overcome some limitations of sequential solvers regarding large mass ratios, when the bodies would inject an impulse on each other which leads to an infinite number (theoretically) of iterations. (E.g. a light body gets squished between two heavy bodies.)

Are there any examples on simultaneous solvers? What method is suitable for them?

Are there other approaches to overcome the large-mass-ratio-problem? Is the example mentioned above in fact the only limitation w.r.t. mass ratios or do the mass ratio has also other effects? E.g. on the actual LCP solving process (either just one contact or all simultaneous)?

[Dirk Gregorius]

So that means any iterative solver (PGS, PCG, SOR, ...) is definitly a sequential and never a simultaneous solver? And they are not suitable for solving all collisions in one big LCP?

Jein

If you use PGS or SI your are essentially applying sequential impulses. Still it might converge against the same solution as a direct solver. Large mass ratios slow down the convergence.

That's bad, because my motivation on this issue is to implement a simultaneous solver in order to overcome some limitations of sequential solvers regarding large mass ratios, when the bodies would inject an impulse on each other which leads to an infinite number (theoretically) of iterations. (E.g. a light body gets squished between two heavy bodies.)

Is this really a problem that needs so much attention? You can try a shock step to solve the problem. I think the "Simple Physic Engine" does this (it looks really good in my opinion). You might want to have a look there and if you want to implement it look at the paper by Erin Guendelman and Bridson. Their PhDs are also excellent reads.


http://spehome.com/
http://graphics.stanford.edu/papers/rigid_bodies-sig03
http://graphics.stanford.edu/~erang/pap ... thesis.pdf
http://www.cs.ubc.ca/~rbridson/docs/rbridson_phd.pdf

HTH,
-Dirk

[bone]

My opinion is that large mass ratios are a real problem with PGS/SI methods. I know one solution is to 'not have large mass ratios'. That's not always an option, especially in non-game applications.

One possible solution is to detect such situations and solve a smaller subsystem using a more exact (but less robust) solver. Where possible, one could implement a linear time Baraff chain (for example, two contacts on each side of the small object that's sitting between two large objects). Whatever the solver, you can solve the subsystem as part of the PGS/SI solving of the full system.

[Chris Elion]

Hi Dirk,
How are things going in Munich?

Just out of curiosity, what actually happens to the system when the mass ratios are large? Is is just a matter of the condition number increasing (so that iterative methods converge more slowly) or does something more complicated happen to the LCP?

-Chris

[Dirk Gregorius]

Hey Chris,

Munich is nice. I hope you have web access at home now and that you are not working

It has been a while that I looked at this. In terms of impulses - IIRC the large mass acts basically like a barrier and slows down the propagation of the impulses through the system. I don't know how this effects the condition number though. It might also effect the diagonal dominance of the system matrix. A good example is just two stacked spheres and I think I did this example a while ago. There is still some stuff left in Cologne and dig this out for you next time I am there.

Cheers,
-Dirk