Solving two contacts at once

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
User avatar
Dennis
Posts: 12
Joined: Sat Jun 23, 2007 9:13 pm
Location: San Francisco
Contact:

Solving two contacts at once

Post by Dennis »

Hey folks, I'm tinkering with a new physics engine as a side project. I always thought solving two contacts at once in the same manifold using a direct 2x2 matrix solver was a terrific idea. Erin Catto also seems to have success in this in Box2D as reported on gphysics.com. However, I cannot really get much improvement when trying it. I reorder my contacts in the manifold so that the points solved together are the ones farthest away from each other. I solve pairwise until done, or only one more contact in that manifold (which I solve in isolation), and I fall back to standard SI if the accumulated impulse turns negative, etc.

It works, but I cannot measure or visually confirm that this is any better than good ol' SI. It doesn't give the same solution, of course, just different. I was expecting this to really improve stacking of long objects, but I can't see much difference if any.

Did anyone else try this in 3D and got a significant benefit out of it?

Cheers,
Dennis
User avatar
Erwin Coumans
Site Admin
Posts: 4232
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Solving two contacts at once

Post by Erwin Coumans »

Hey Dennis,

Good to see you again, and happy new year (I've barely visited this section because of all the Bullet support and development)

I've tried it before with solving 4 points between rigid bodies at once, and it improved stability.
Doom 3 also does this, and the code for solving up to 5x5 matrices is in the Doom 3 SDK, as far as I remember (several years ago though).

If you are using solving only 2 points at a time and there are 4 points, I would use the diagonal axis, A,C and B,D in the picture (top view)
contact.png
contact.png (5.49 KiB) Viewed 4819 times
Improving the friction model improves stability and performance quite a lot: you could use central (rotational friction) friction and 2 linear friction axis (top view)
friction.png
friction.png (7.21 KiB) Viewed 4819 times
Cheers,
Erwin
User avatar
Dennis
Posts: 12
Joined: Sat Jun 23, 2007 9:13 pm
Location: San Francisco
Contact:

Re: Solving two contacts at once

Post by Dennis »

Hi Erwin, yes that's basically what I'm doing, but my problem is that I see no real benefit. I suspect that warm-starting might cancel out the effect of pair-wise solving, since contacts are likely to be initially separating, so it will fall back to SI very often. I'm not sure exactly what's going on. Is there a reason this is not in bullet if you tried it and saw an improvement?

I'm using central friction already :) How come Bullet does not use that? I think it could improve both solver performance and stability quite a bit.
User avatar
Erwin Coumans
Site Admin
Posts: 4232
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Solving two contacts at once

Post by Erwin Coumans »

Have you tried to solve 4 points simulaneously? And have you tried it with a single box resting on the ground without friction and only 1 iteration? Then you surely should see a difference, especially when you solve 4 points at a time.
[...] Is there a reason this is not in bullet [...] How come Bullet does not use that?
There are many things not in Bullet yet, that I tried before, it is a matter of priorities I suppose. I haven't worked on improving solver quality or performance much for Bullet, there are just too many areas to look into. Right now we are experimenting with OpenCL and GPU constraint solver has even fewer features than the original Bullet solver. Same for the PlayStation SPU version. Then, I'm also looking in better demos using Ogre and Irrlicht in this new GameKit project, to combine physics with animation etc.
If you have a patch or pseudo code for any improvement, I might apply it :-)

Thanks,
Erwin
User avatar
Dennis
Posts: 12
Joined: Sat Jun 23, 2007 9:13 pm
Location: San Francisco
Contact:

Re: Solving two contacts at once

Post by Dennis »

Yes, in the very simple case of one iteration and one body where no contact velocity is negative it does help. It is in a more realistic scenario, with multiple iterations, warm-starting and stacking that I cannot see any benefit.

I understand there are many priorities for bullet :) Kepp up the good work!
Dirk Gregorius
Posts: 875
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Solving two contacts at once

Post by Dirk Gregorius »

Hey Dennis,

I tried this as well and can second your observation. There was no noticeable improvement for me. If you looked at the Box2D implementation you might have noticed that I implemented this in collaboration with Erin. Did you shift variables to account for the clamping against the accumulated impulse? The LCP has basically the following form and can be solved very easy using Direct Enumeration (see Murty):

w = A * dP - b >= 0 and ( P + dP ) >= 0 and w * ( P + dP ) = 0

Here dP is the delta impulse and P is the accumulated impulse. So to make this all work you have to add A * P on both sides of w:

w = A * P + A * dP - b - A * P = A * ( P + dP ) - ( b + A * P ) >= 0

Now substitute: P' = P + dP and b' = b + A * P and you are done. It is easy to oversee this and work in the wrong coordinates. Anyway, I am sure you did all this :)

I did also expect improved behavior since in theory this should cancel out rotational effects and I expected imroved stacking similar to a sphere stack. Let us know what you find out :). It is really a long time ago I tried this and maybe there was a bug in the implementation.


Cheers,
-Dirk
Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Solving two contacts at once

Post by Erin Catto »

The block solver gives a big stability increase to Box2D. I have not implemented this in 3D, but I suspect you would need to solve all points (up to 4) in block form to get a similar benefit. This gets to be a bit expensive because 4 points has 16 permutations that must be tested and you need to solve a different matrix equation for each permutation.

There are some implementation details in Box2D that must be followed precisely in terms of warm starting and clamping. Dirk and I had to do a bit of derivation to make sure it was correct.
User avatar
Dennis
Posts: 12
Joined: Sat Jun 23, 2007 9:13 pm
Location: San Francisco
Contact:

Re: Solving two contacts at once

Post by Dennis »

Interesting you came to the same conclusion Dirk. Given the circumstances, and especially the computational overhead I think I'll give up on simultaneous solving in 3D, but I'll let you if I make any progress :)
Post Reply