Resting Contact in rigid body simulation. . .

[Erin Catto]

Hi xissburg,

You sound like you had some trouble with Box2D. I've attached the latest build of the Box2D test bed. Please let me know what issues you are concerned about. I want to make Box2D the best 2D physics library possible, so your feedback is important.

Please note that Box2D does not currently have continuous collision detection, so you will get some momentary visible overlap with fast moving objects. My hunch is that these errors a more obvious in 2D than in 3D. I'll be adding CCD to a future version of Box2D.

Cheers,
Erin

[xissburg]

It seems you have done some adjustments on this version because it is somewhat different than the one I tested(I think it was an old one =P).

Box2D does not currently have continuous collision detection

Thats why I see some penetrations and some collisions fail. But a thing that is unrealistic is the stacking when a fast vertically moving body hits the top of the stack, it seems that there are some springs at there pushing the bodies apart. When using more large boxes(big width, small height) its possible to see this effect better. I also think that the way the bodies behave when colliding and going to resting contact is somewhat unrealistic, don't know how to exactly explain that, its just a matter of compare that with what we actually see in real life. Any way, I think this is due to the SI technique.

[xissburg]

I have already said that in my last post.

[Dirk Gregorius]

Yeap, I deleted mine. We were answering at the same time...

[Erin Catto]

SI and PGS are not perfectly rigid solvers, especially when heavy objects hit light objects. This is because SI and PGS solve one constraint at a time and solving one constraint messes up the adjacent constraints and it takes a while for this to converge. However, SI and PGS are quite fast. So you have a performance versus accuracy tradeoff to consider.

If you want more accuracy, you have two fundamental choices:
- Use SI/PGS type of solver with a smaller time step and/or more iterations.
- Use a O(n^3) solver like the Lemke LCP solver.

SI has some tangible benefits you should consider:
- It is quite fast, taking O(n) time and space.
- It is stable (if not perfectly rigid) and supports stacking and joints.
- It is relatively easy to implement. See Box2D Lite http://www.gphysics.com/files/Box2D_Lite.zip.

SI and PGS are adequate for most game scenarios, and most games out there use these types of solvers. Normally we don't see pyramids of 325 boxes in a game. Also, real world objects are not perfectly rigid. How high of a vertical stack of boxes have you seen in real life?

If you value accuracy over performance, then a direct LCP pivoting solver (like Lemke) is the way to go. You can find examples of this in ODE and in the Doom3 SDK.

[xissburg]

Yeah . . . now I agree SI is the best method for games =) . . . I hate LCPs =P.

How high of a vertical stack of boxes have you seen in real life?

=D

Well, well . . . SI is the way to go . . . its time to read lots of things =). Thanks for the help guys and, could any of you please point me a nice SI paper/article? I'm starting to read some but I don't know if those are the good ones. Thanks .. .

[John Schultz]

Yeah . . . now I agree SI is the best method for games =) . . . I hate LCPs =P.

How high of a vertical stack of boxes have you seen in real life?

=D

Well, well . . . SI is the way to go . . . its time to read lots of things =). Thanks for the help guys and, could any of you please point me a nice SI paper/article? I'm starting to read some but I don't know if those are the good ones. Thanks .. .

See Danny Chapman's demo based on the Nonconvex rigid bodies with stacking paper: http://www.rowlhouse.co.uk/jiggle/; the demo looks nice. Read the Nonconvex...stacking paper- lots of good ideas. [edit] It appears his latest version has a shock step (notes on page) and also uses some of Erin's impulse ideas from Box2D: http://www.rowlhouse.co.uk/jiglib/index.html.

Read Jan Bender's paper (more recent); try out his demos (he provides source as well): http://www.impulse-based.de/

If you can make Box2D work to your liking, it's probably not too much work to extend to 3D.

In any case, there are many variations that work well. My current impulse-based simulator does not require any iteration (single-pass @ 100Hz), and allows for rigid box stacks (not springy). The trick was to use a tetrahedron (from Verlet-based RB experiments) to allow for a slight amount of deformation (resulting in translation and rotation), then using a kinetic energy corrector after movement (everything else is impulse-based). The end result is fast, stable, and non-springy stacks. It's not quite perfect- there can be a slight amount of momentary jitter, probably could fix (based on velocity), but is good enough for now. I don't believe most gamers will sit in the game looking for physics flaws; they'll be busy playing the game. Don't worry about making your physics perfect: I see weird stuff in popular game titles, but it does not hurt gameplay (other than getting stuck occasionally). Just make sure your engine is stable/does not crash and most players will be happy (and amused sometimes when finding strange physics bugs).

[Erin Catto]

SI isn't perfect, but improvements are being made all the time (like post projection of position errors). I'm glad you're giving SI a shot. Perhaps you can contribute some improvements/suggestions as you learn more about it.

You might find some of my tutorials useful. Go to this page and get the GDC'06 presentation and study it with the Box2D Lite code. After that, you can learn more by reading the GDC'07 presentation.

http://www.gphysics.com/downloads

[xissburg]

Thanks a lot for all this help guys, you're awesome though =)

Perhaps you can contribute some improvements/suggestions as you learn more about it.

Huh! I hope I can find some improvements during the development of my engine .

I'll try studying all those stuff and if I have any question I'll come back here ask for your help =P

Thank you all . . .. . . .

[bone]

It is funny, because one of the benefits of pair-wise applying impulses on rigidbodies (relaxation, Sequential Impulse) is very intuitive and easy to understand. So it would be good to explain this first in terms of bodies, velocities, impulses, instead of trying to explain it using the less intuitive approach (lots of math derivation, PGS, LCP etc). Later, once the intuition is there of the approach, we can introduce all the math formulaes etc.

Since we're talking about the simplicity of SI, I've had a question for awhile. We always talk about pairwise constraints, meaning constraints between two bodies (ignoring the special case of one body being static). But if you can come up with a constraint for three or more bodies, will SI still be able to iterate to a solution? If so, it's by far the most versatile and furthermore the easiest method to understand.

Why would I say that? By accumulating the results of the iteration in the actual bodies' velocities and positions, there's no need for external storage. You've basically made all of the constraints independent of each other, with no need to fill up a specific-size matrix. For example, I feel it would be very difficult to implement a three-body constraint (say an area constraint) using any other method (including the mathematically equivalent PGS). Am I off my rocker or no?

[John Schultz]

But if you can come up with a constraint for three or more bodies, will SI still be able to iterate to a solution? If so, it's by far the most versatile and furthermore the easiest method to understand.

Why would I say that? By accumulating the results of the iteration in the actual bodies' velocities and positions, there's no need for external storage. You've basically made all of the constraints independent of each other, with no need to fill up a specific-size matrix. For example, I feel it would be very difficult to implement a three-body constraint (say an area constraint) using any other method (including the mathematically equivalent PGS). Am I off my rocker or no?

The constraints are solved pair-wise between two bodies, with no limit to the number of pairs. If you add a displace-position-and-track energy step, SI can allow for relatively stiff solutions without iterating (for example single-pass @ 100Hz with no per-frame iteration).

Re: external storage- I store and track contacts (helpful for holding dynamic constraints such as static friction), though certainly much simpler than populating matrices.

[Erin Catto]

Yes, that is exactly the case. You can even embed a tree solver, like Baraff's linear time solver, inside SI. This gives you a macro-constraint that affects an arbitrary number of bodies simultaneously.

I have implemented such a system with good results.

[Erwin Coumans]

If you can make Box2D work to your liking, it's probably not too much work to extend to 3D.

Bullet implements a 3D version of sequential impulse. Box2D and Bullet might have slightly different variations (which will catch up) but they are essentially using the same concepts (the decoupling between velocity and positional correction is an example of a variation that will be synchronized soon).

There is no problem in mixing pair-wise impulsed based constraint solving with other constraint solving methods. The relaxation concept of sequential impulse (converging to a global solution by iteratively solving local solutions) allows to embed other constraint solving methods, including cloth, Featherstone etc.

Erwin

[Dirk Gregorius]

Yeah, I have Erin's linear time solver for trees implemented in 3D and this works great. One thing I learned is that you need to handle it exactly as any other constraint. From this point of view we are actually just extending the concept of blockwise constraint solving. There are some things to consider though:

It is very obvious that if the block is equivalent to the whole system (e.g. a mobilee) you have the correct global solution after one iteration. If you have several additional constraints (e.g. contacts) the blockwise solver doesn't improve the convergence of the global system too much. It just emphasizes the particular subblock, but this is actually good for ragdolls to avoid stretchyness and I could imagine that it also helps with big mass ratios. Mathematically one can show that the convergence improves by a factor of sqrt(2) for blockwise solving. One nice thing to learn was how much we are actually limited by the non-linearity of the position constraints in presence of high angular velocities. Even if you find the global solution of the impulses for a mobilee you still need several Newton iterations for the post impulses (PI) to project the positions back onto the constraint manifold. This is where PI is obvious superior to Baumgarte since Baumgarte is basically an implicit linearization of the system and if this breaks there is very few to do against it.

W.r.t to Featherstone I can imagine that it works with SI as well, though I also could imagine that there are problems because of the reduced coordinates when using CCD. Does anybody know how Featherstone will deal with errors in the positions? Antonio mentioned that this might be a problem with Featherstone. Any experiences with this?

[mewert]

GS can handle multi-body constraints quite easily with a special constraint.

I look at GS/SI like so:

1) Project the bodies velocities onto the constraint
I think of the Jacobian 'J' as a projection from normal world-space onto the constraint manifold ( constraint-space )
To do this, sum all the velocity contributions from the bodies at the constraint attachments points mulitplied by the appropriate J

2) solve for the constraint impulse
multiply the constraint-space velocity by (JMJ^t)^-1

3) apply the corrective constraint impulse to the bodies
now we go from constraint-space to world-space again.
mulitiply the constraint impulse by the appropriate J^t

For 2-body constraints you only have one J ( actualy you have two, but J1 = -J2 ). For multiple bodies you have one J for each body. Just go through those 3 steps and modify to use more than one J.

I've used this to implement block-and-tackle pully systems.

- Michael Alexander Ewert