Quote:Original post by Airo
In one of Brian Mirtichs papers and also in Baraff's paper I think is an example of a chair sitting on four legs. In this case an lcp solver, won't work because there are multiple solutions to the lcp possible. One would suspect that the force is evenly divided over the four legs.

Can such a thing also happen with a collision?

Does anyone have a good reference for solving lcp's, preferably online? The one i know is baraff 94. I want to improve this demo a win32 opengl app, demonstrating 2d domino.

yes, a collision force problem can just as well be overdefined as contact force problem. in real life the situation isnt overdefined, because there are other equation that play a role, namely those that govern the deformation of the bodies. however, in the case of rigid bodies, those are not considered, so youll have to come up with some hack.

As far as I know, using a LCP works even for overrelaxed systems. Like the case with four contact points, my LCP solver gave the same contact impulse at all four contacts when I tested with a cube falling on a plane.

First of all,
I want to thank everyone for replying to my topic. I certainly consider all responses equally important and I research extensively into all your posts.

Recently, I emailed Baraff himself to talk about this problem. Here's a transcription

-------------------------------------------------------------------



Dear Professor Baraff,
I am writing my own rigid body dynamics engine, and I read many of your papers regarding the subject, but I came across a problem regarding multiple simultaneous collisions that seems to be unsolved as yet.

I think I am running into the same problem that you stated in SIGGRAPH 89, where you mentioned that propagation and simultaneous solving yields different results.

The problem is regarding using an LCP solver is resolve multiple collisions.

In situation 1 on the diagram: the LCP solver is calculating incorrect final velocities, even though the answer satisfies

V+ = -e * V-

The only way that I know of to resolve situation 1 is through propagation. Consider pair-wise collisions and apply impulses, and cycle through the list until all collisions are resolved. But this solution will not work for situation 2, where it is necessary to solve for the impulses simultaneously to make sure the block bounces straight up without rotating. But how can the two situations be differentiated? In what cases do you use propagation and in what cases do you solve simultaneously?

Also, consider the last picture on the diagram. I have no idea whether to use propagation or simultaneous to resove that problem. Maybe I even need a combination of both?

Thank you for taking the time to read my email, and I would be thrilled if you replied.
Sincerely,
Patrick Li

-------------------------------------------------------------------

In the picture, all the numbers are directly calculated with an LCP .. so i'm not making them up.

And I'm extremely grateful for your help in the past Anonymous Poster. You provided many of the articles which I have used to since starting on my quest. But in this situation, I believe Mr.Rowl has the clearest understanding of my problem.

PS: Thank you for the new links Mr.Rowl. My engine is gonna be the best one around soon, after a little light-reading.

PPS: Why am I so hung up about this? I want this engine to be perfectly correct (for rigid bodies). And what really pisses me off is why everyone is doing research into friction already when such a fundamental problem is unsolved. Tell me really..isn't this more important than .. say "a correct model of Couloumb Friction that handles sticking and sliding contact".

I had a quick lookie at the articles that Mr.Rowl provided, here's some thoughts.

http://tam.cornell.edu/~ruina/hplab/downloads/collision_papers/latest_alg_law.pdf

For simultaneous collisions it proposes processing collisions in order of Highest approach velocity to lowest approach velocity. But in cases where the approach velocity is equal, as in "simultaneous problem" in my first diagram, it proposes

1) Change the initial conditions in the simulation (within a reasonable
space of initial uncertainty) to break the symmetry,

2) order the "equal-approach-velocity" collisions
arbitrarily (say, by taking the dot product of the position with a predened non-special direction), or

3)following Ivanov's recommendation for such problems randomize the collision order so that the genuine indeterminacy in the experiments would then be represented by indeterminacy in the collision law.

I don't understand the second proposition, but the other 2 doesn't sound like it will resolve a square falling flat onto a surface.

Anyway, it seems I'm barking up an unripe tree, so I'll take another stab at penalty-based approaches. My last try with penalty-forces was done without reading a single article so the final result was slow and sloppy.

Does anyone have any good papers to

Fast and Stable Penalty-Based Approaches?

AHA!!!

The 3rd article posted by Mr.Rowl.
http://www.mecheng.iisc.ernet.in/~anindya/papers/complementarity_preprint.pdf

That is exactly my problem! The paper explains exactly what the problem is, and why it is presenting a lot of difficulty in solving it. (Currently, it is indeed an unsolved problem). It even mentions a few examples that I've run into and posted on the forum.

Unfortunately, an in-depth explanation of the problem is all that it is..it doesn't propose any answer as of yet.

However, to people looking for authoritative evidence that LCP is not the "be all, end all" solution for physical simulation. Here's a quote:

"In this light, the complementarity conditions at the velocity level should be viewed as typically inaccurate, but algorithmically convenient, constitutive assumptions."

In reality there is no such thing as a truely simultaneous collision, so processing collisions sequentially should give you a correct result - the exact order in which you process the collisions will determine the exact result you actually get, but since the collisions happen so closely together in time, it's arbitrary what order you process them.... If you don't like this then do your collision detection, process only the first collision and re-run the system from that time (but beware non-termination). I think this will give you a physically correct response, even if it isn't computationally convenient/efficient (using a LCP solver at this point is convenient, but physically wrong, Mr Anonymous), and you'll get artifacts if you're forced to terminate the loop before you're done.

To get correct resting contact behavious, I would solve the resting contacts separately and simultaneously with a LCP solver (if I had time to implement this!).

If I was modifying my code to do this it would just be a matter of passing the contacts to a LCP solver (via some code that sets up the matrices etc using the other constraints too) in the second collision processing step (where the restitution is set to 0 for all contacts).

Incidently, your "propogation" problem is a real-world problem it's important to get right, because it happens all the time (in pool etc). Your "simultaneous collision point problem" is rather artificial since in reality the collisions won't be simultaneous - therefore it's as good to get a physically plausable (asymmetric) result as it is to get the exact (symmetric) result you'd expect in this theoretical situation.

Well just to close my posting here.

As fast as I know when one formulate the equations for simulations impacts collisions using the principle of conservation of momentum, they lead to a linear system of equations. I think this is a fact and I stick to it.

In the past 6 or 7 year there have been few papers and dissertations proposing algorithms twists as to how to solve the problem faster. But these are just algorithmic formulations focusing on practical and faster solutions. The fact reminds that the theoretical formulation is a linear system and as such it have to be solve simultaneously.

MrRowl keep attacking me personally on his posts and keep citing papers as poof that impulsive contacts and resting forces can be calculated sequentially.
What he does not realize is that those papers are just based on empirical and intuitive experimentation, no were in the text you find a rigorous demonstration that validates their claims, the only validation is that is fast and it looks good.
Until these papers:
http://www.cs.ubc.ca/~rbridson/docs/rigid_bodies.pdf
http://www.mecheng.iisc.ernet.in/~anindya/papers/complementarity_preprint.pdf
Do not manage to proof their claim rigorously they are just algorithm mombo jumbo, and similar variance will continue popping every year.

Work like Baraff and Witking on the other hand is purely based on rigorous proof first and a practical formulation second.

To conclude I apologized to CuppoJava for misinterpreted your problem. I did not understand that you did not have a problem with the method of find the solution, you have a problem with the very foundation for classical mechanic.
If you people can figure out how to formulate the problem in a recurrent way, maybe you can write a theoretical paper that will complement all of the recent ones based only in heuristics and intuition. I am no saying this sarcastically there have been work proving that some type physics problems can be solve sequentially and correctly, Featherstone
algorithm is and example of that.

I think Baraff knows the problem but just isn't saying anything before he figures out how to solve it.

"It is emphasized that many authors in this area are aware of the possible physical inaccuracies behind the complementarity assumption. Baraff (personal communication) mentions that there is no reason to think that real systems obey the complementarity conditions."

Anyway, if I ever figure this out don't be surprised if I do publish a paper on it :) With full acknowledgements to Mr.Rowl and Anonymous Poster of course.


Until then, does anyone have good links to fast and stable penalty force methods?

RE: Penalty Methods.

While I don't consider myself an expert on solving simultaneous collisions and analytical collision response methods, I have dabbled quite a bit.

I consider David Wu the authority on robust physics in actual shipped games. He has done a ton of work on penalty methods and implicit integrators including handling the hard problems of friction models via penalty methods.

http://www.pseudointeractive.com/about.shtml

RE: David Wu

Yup I've heard good things about him and I stopped by his site. They're a little brief though and I was wondering if there's any more in-depth papers on penalty force, that focuses on speed and stability.