Contact handling, bullet method or Bender method??

[dneckels]

I'm getting a bit confused trying to answer my question looking at these forums and the bullet code, so I will ask (hopefully I haven't missed an obvious answer):

How does bullet handle contact? Specifically, does it use the lagrange multiplier approach to enforce the penetration distance > 0 + a penalty for penetration
(something like the method described in: http://www.gphysics.com/files/GDC2009_ErinCatto.zip)??
If not, is there a link to the approach?

If so, has anyone compared this approach to that of Jan Bender, i.e. predict the penetration at a contact point and apply an impulse to correct the penetration:

http://www.impulse-based.de/phpmv2/phpm ... BasedPaper

??

I've learned just enough with my own solver to be thouroughly confused how to proceed . Switching over to bullet might be on the horizon!!

So far (using Bender's method):
http://www.youtube.com/dneckels

I am very impressed with the blender demos.

-dn

[dneckels]

Addendum:

I found a better reference: is this the approach used in bullet?
http://www.continuousphysics.com/ftp/pu ... namics.pdf

thx

[ngbinh]

I think Bullet uses the same constraints like in the paper you found. But it uses a technique called "sequential impulse" to solve the system.

read here http://www.bulletphysics.com/Bullet/php ... =&f=&t=273 .

[dneckels]

Thanks for the link!

It seems like 'sequential impulses' refers to the method used for solving the MLCP that results from the resulting formulation? Is that the idea?

I wonder too, are colliding impacts dealt with in the same solve? I could see solving these first using a simple impulse iteration and then resolving the trickier contact and constraints with the lagrange multiplier method as a second step. Or does Bullet roll these into the same constraint solve?

The Bender method seems to add extra energy and cause some bounciness, probably because the position corrections end up causing some overshoot and increase the energy.....

[ngbinh]

it should solve in one go (but multiple iterations).

For Jan Bender method, I don't know the method exactly but it should be fairly stable. Your simulation captured in youtube do not seem to be stable at all. Are you using the same code from them or implement your own one?

[Dirk Gregorius]

Bullet implements a Projected Gauss-Seidel (PGS) in a special form called Sequential Impulses (SI). This solves indeed an MLCP. All methods you describe use Lagrange multipliers (either implicit or explicit). E.g. in Jan Benders Methods the K-Matrix is nothing else but the effective mass. You can easily show the collision matrix K and effective mass Me = (J*M^-1*JT)^-1 with C = (x2 + r2 - x1 - r1) * n and J = ( -n -r1 x n n r2 x n ) are equivalent.

Bender basically solves:

// First sweep
J*M^-1*J * lambda = -C/dt

// Second sweep
J*M^-1*JT * lambda = -J*v


Bullet solves (ignoring split impulses or similar projection methods which are also supported)

// Combined sweep using Baumgarte stabilization
J*M^-1*JT * lambda = -beta * C / dt - J * v


The videos look great. Well done! What do you use for collision detection?


HTH,
-Dirk

[dneckels]

Thanks, Dirk!

I am using an AABB sweep and prune followed by GJK for the collision detection. At some point I rolled a copy of the bullet simplex solver into my code since it was faster and more stable than my own.
I build a cache of contacts as bullet does, maximizing the area.

The simulation works somewhat, but is pretty unstable (blowups, etc...), so I'm looking at Bullet as an example since it seems to do quite a bit better!

I wonder; the Bender method applies an impulse to attempt to correct the position at the next time step, whereas it seems like the MLCP formulation applies a force to Null the velocity in the offending direction + a penalty for penetration?? I'm hoping this will help stop some of the 'chattering' I see.

What was the distinction between the two sweeps you mentioned? Is one for collisions, the other for contacts/constraints??

Edit: Ooops, I see. Bullet uses one phase with the positional correction and velocity projection together. The whole thing reminds of either a predictor corrector scheme or a projection type scheme (as with incompressible fluids).

thanks!

[Dirk Gregorius]

The distinction is between position constraints (e.g. offset at pivot points) and velocity constraints (e.g. relative velocity at pivot points). In the Catto solver they are combined.

I remember that Bender used a pretty small timestep in his demos. Personally I am not convinced by his method, but this is only my guts feeling and I have not tested the library. So maybe try to use a smaller timestep (e.g. 120 - 240 Hz) and see if this improves your simulation. The Catto solver (which is also used in Bullet) can easily simulate a scene with a timestep of 30 - 60 Hz.

Basically Bender solves such that his new velocities onto the constraint manifold. Note that solving for position is different that solving for position. When solving for position you walk on the surface of a non-linear manifold. When solving on the velocity level you walk on the tangent space of this manifold. Bender kind of combines both.

[dneckels]

it should solve in one go (but multiple iterations).

For Jan Bender method, I don't know the method exactly but it should be fairly stable. Your simulation captured in youtube do not seem to be stable at all. Are you using the same code from them or implement your own one?

I've rolled my own, figure

A straightforward approach of the Bender method applies a pretty serious impulse to correct any penetration (immediatly correct the offending position). Hoping that the LCP formulation with the exponentialy decaying correction will do better. Knowing my luck this will probably lead to worse penetrations and issues down that road.... The fun never ends!

[ngbinh]

it should solve in one go (but multiple iterations).

For Jan Bender method, I don't know the method exactly but it should be fairly stable. Your simulation captured in youtube do not seem to be stable at all. Are you using the same code from them or implement your own one?

I've rolled my own, figure

A straightforward approach of the Bender method applies a pretty serious impulse to correct any penetration (immediatly correct the offending position). Hoping that the LCP formulation with the exponentialy decaying correction will do better. Knowing my luck this will probably lead to worse penetrations and issues down that road.... The fun never ends!

That's a pretty nice try! In our little physics engine, we also correct all penetrations in one time step. It wouldn't be a big problem if you have the right collision detection.

Do you have any particular aims for the project?

[dneckels]

Do you have any particular aims for the project?

Mostly keeping myself interesting in programming by doing something fun and challenging!
Probably going to go in the flight simulator direction (know something about this from past work). Not sure how to integrate the physics engine into flight sim, though....

[dneckels]

Thanks for the help. Was able to get the PGS Schur complement approach working!!

http://www.youtube.com/watch?v=NnBeOZ5EgSw

Wasn't happy about constant friction; found it not so hard to add a simple friction cone to the LCP. Results are nice, but LCP convergence suffers. Am going to try the sub-iteration method (PGS-SM)(http://www.ece.northwestern.edu/~morale ... Solver.pdf).

Best part was that the whole approach lends itself to the matrix-free approach quite easily!!

Thanks for the help.

[KenB]

I am curious about the difference or likeness of "Sequential impulses" and projected Gauss-Seidel iterations. I really can't see any difference. "Sequential impulses" is really just an attempt to give meaning to the one-by-one equation approachs of the Gauss-Seidel method, which happens to result in an update to the lagrange multiplier we're solving for, and this update can be called an impulse, since that's obviously the unit it has. Also, since you typically don't build the matrices, you instead work on the equations on element form, and then the matrix solve is less obvious in the implementation in code. Unfortunately the impulse sequence has very little physical meaning. Typicall one wants the sequence that gives the best convergence rate, and there's no reason why this sequence should relate to a real collision sequence in the system. Typically is can be more efficient to iterate from bottom to top in the gravitational field since "impulses" then can propagate from the bottom layer constraint error all the way to the top in one iteration pass, but the actual physical sequence (if using microscopic timesteps and real electromagnetic forces) could be something completely different and the temporal resolution is at least 4-5 orders of magnitude away from the 50-100 Hz used in real-time physics.

Is there something else that makes the SI-method different from Gauss-Seidel?

[raigan2]

AFAIK Erin has always maintained that SI _is_ PGS; I think if you search these forums there should be a post where he explains the origins, IIRC it was a co-worker who pointed out the equivalence?

[bone]

Is there something else that makes the SI-method different from Gauss-Seidel?

Yup, they're basically equivalent, but the former tends to be more generic. It's easier to add a trilateral constraint, for example. Or, say, a self-iterating friction constraint.