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
Solving two contacts at once
-
- Posts: 12
- Joined: Sat Jun 23, 2007 9:13 pm
- Location: San Francisco
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Solving two contacts at once
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) 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) Cheers,
Erwin
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) 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) Cheers,
Erwin
You do not have the required permissions to view the files attached to this post.
-
- Posts: 12
- Joined: Sat Jun 23, 2007 9:13 pm
- Location: San Francisco
Re: Solving two contacts at once
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.
I'm using central friction already

-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Solving two contacts at once
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.
If you have a patch or pseudo code for any improvement, I might apply it
Thanks,
Erwin
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.[...] Is there a reason this is not in bullet [...] How come Bullet does not use that?
If you have a patch or pseudo code for any improvement, I might apply it

Thanks,
Erwin
-
- Posts: 12
- Joined: Sat Jun 23, 2007 9:13 pm
- Location: San Francisco
Re: Solving two contacts at once
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!
I understand there are many priorities for bullet

-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Solving two contacts at once
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
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

Cheers,
-Dirk
-
- Posts: 316
- Joined: Fri Jul 01, 2005 5:29 am
- Location: Irvine
Re: Solving two contacts at once
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.
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.
-
- Posts: 12
- Joined: Sat Jun 23, 2007 9:13 pm
- Location: San Francisco
Re: Solving two contacts at once
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 
