Multiple Impulse and Collision Solving

[goruka]

Hi! Well, I finally managed to implement physics and collision detection properly, things collide against each other fine and the responses also seem ok.
I seem to have two issues left, which I can't seem to find much info about..

First, I'm still not sure on how to solve multiple collisions (say, a collision draft), I tried a few simple methods, like doing the pair separations in random order, or always in the same order, but without much success, as the system seems to be a bit unstable (shakes bit).

Which methods exist for this? are there any papers I can read? I seem to read everywhere that most physics engines use iterative solvers, but I also can't find much info on this.
I found Mirtich's paper, which says i should sort the contact list by estimated TOI and solve in order, then re-sort. but i feel may be overkill. His paper is like, 20 years old also, so i'm sure that things probably improved. So, pointers to documments in the right direction on this are very highly appreciated.

Second, I'm also not sure on how to make the system stable. Are there any methods to drive down the physics into stability? For example, I can see my objects shake very very little vertically because of the constant action of gravity, and things get worse when i stack them together.. well, this is probably part of the first problem, but I also can't find much information on this.

So, thanks in advance!

[Dirk Gregorius]

For multiple simultaneous contacts you just treat each contact separat. The only difference to your spheres is that it is now crucial that you clamp against the accumualted impulse. See Erin's presentation for a good explanation of this or look into Bullet to see an example implementation. Just start with two boxes and no warmstarting. The system should be stable between 10-20 iterations. Also don't forget to add slob (this means to allow some penetration). Finally don't be greedy with the stabilization (Baumgarte). Use bias = clamp( 0.1f * penetration / dt, -MaxPenetrationRecovery, MaxPenetrationRecovery ). Look in the ODE for a good default value for MaxPenetrationRecovery. I think it is called something like MaxSeparatingVelocity. Anyway you should find it dxContact::GetInfo2() or so. Sorry, it is a while ago that I did this. Let me know if you can't find it.

[goruka]

Just start with two boxes and no warmstarting. The system should be stable between 10-20 iterations.

I finally got time to try this out, however, I try to stack 2 boxes and I don't seem to be getting a stable system this way... the top box starts rotating over the bottom one slowly.. Maybe my problem is in the collision side? Right now I'm using a simple minkowski difference between the boxes to find the point with the most penetration (and was thinking in switching to gjk once that works), and I set it as the contact. Is this the best way to obtain contacts for two stacked boxes? or should I try something different?

Thanks

[Dirk Gregorius]

Basically you have two options, GJK and SAT. Since GJK only finds the closest point between two disjoint convex shapes you need to trick a little. Bullet uses a margin around its shapes (sometimes refered to as spherical expansion) and reports a contact as soon as the distance falls below the sum of the margin of both shapes (this is called shallow contact). When the objects actually intersect (what is called deep contact) you need another algorithm, e.g. EPA. Since GJK and EPA usually only return one point you need to collect these points in a persistent mainfold to build the full contact geometry over several frames. ( See Gino's book and Erin's contact presentation for this and also look at Bullet for a nice example implementation ).

The other alternative is SAT. The main limitation is that it only works for convex polyhedra, so you need to approximate quadrics (e.g. cylinders and cones) as polytopes. It is also much more difficult to implement this efficiently. Note that Bullet has an example implementation of this as well in the Extra folder, but the implementation has some issues. Still I personally favor this approach since in my opinion it is more robust and creates the better contact geometry (one shot manifolds) for the physic solver. On the other side there are ways to extend GJK such that you find the full contact patch as well, but I have no numbers how efficient these are.

Good contact generation is actually much more difficult then writing a physic solver, so you might consider using Bullet's collision detection as a start.