Two situations that aren't handled by any engine yet. (I think)

The LCP solver changes the constraint:

Vrel' = -e*Vrel

to

Vrel' > -e*Vrel

But this is still not correct.



This image shows the correct result of a perfectly elastic collision. But notice that the magnitude of the final relative velocity between blocks 1 and 2 is actually smaller than the magnitude of the initial relative velocity. Which violates

Vrel' > -e*Vrel

PS: Thanks for the link to the paper. That was the exact one that I used to implement my LCP solver, but, to my frustration, it still doesn't resolve the progation problems correctly.

Any suggestions?

I really want to be able to resolve the situation in my second drawing, but I can't find any way to do it.

Okay, I tested the Newton Engine and unfortunately it doesn't handle it either.

Here's what I did:

I downloaded the Newton Playground demo, and constructed the "simultaneous problem" situation in the first picture. I couldn't figure out how to turn off gravity so its not exactly the same as the picture. I put two blocks on the floor side by side, and I dropped another block exactly twice as big onto the two. The two blocks jumped up upon collision! This shouldn't be happening for perfectly rigid bodies.

Surely this sort of thing has been done, like in pool and snook games?

ace

Sorry i'm so unclear. I've been misunderstood again. It explains why i'm a coder and not a writer :)

Anyway, the equation
Vrel = -eVrel'
is directly talking about the relative velocities of the points. This is taken straight from Baraff's paper.



I'll try explaining the problem above again.

Before the collision, the relative velocity of the POINTS on block1 compared to block2 is say -3. And the relative velocity of the POINTS on block2 compared to block3 is smaller, say -1.

After the collision, the relative velocity of the points between block 1 and 2 SHOULD BE +1, and between block2 and 3 SHOULD BE +3.

But notice that

Vrel' > -Vrel
+1 is not greater than - (-3)

which means that LCP is wrong.

As on flipcode - you can't just through the propogation problem at a LCP solver and expect it to give the right result, because in that case the collisions are sequential, not simultaneous. Mr Anonymous doesn't explain how to differentiate between the situations... I suppose that depends on the exact details of how you process things.

Incidently, I set up a Newton's cradle in my stuff:
http://www.rowlhouse.co.uk/jiglib/

It basically works, but isn't perfect. Actually it doesn't even work any better when using a really high physics frequency/number of iterations (sleeping/shock propogation is turned off) - I'm not actually sure why!

I'd be interested to know why you're so hung up on this, CuppoJava?! For practical purposes (for games anyway), I'm not sure it's really an issue...

Off Topic:
Anonymous Poster, you seem to be quite helpful, why not register?

We need more people like you [wink]

Just out of curiosity...why are you using LCP for rigid bodies? Isn't it the standard practice to use some form of ODEs? I don't know the answer, I'm just curious from what little I've read of physically-based animation. I thought LCP was mainly used for soft-bodies.

Quote:

Original post by Anonymous Poster In your sketch assuming the collision happens at the same time, the restitution is 1.0, there is no friction, and there is only one contact at the center, or there contacts are perfectly symmetric, the solution you will get is what you show in the second part of the sketch. And that is exactly what and exact LCP solver will find. ... Vr = -eVr’

Can't you see that CuppoJava's first diagram (which you agree represents reality) results in velocity changes that are inconsistent with "Vr = -eVr'" - just consider the velocities between blocks 1 and 2. Therefore if you formulate it as a simultaneous collision problem and solve it with an LCP solver which enforces Vr = -eVr, then you'll get a physically incorrect result.

If you formulate it as a non-simultaneous collision problem (block 1 hits block 2, THEN block 2 hits block 3 etc) you'll get a correct result whatever collision solver you use (LCP or iterative), so long as you backstep to the time of first collision etc.

However, in CuppoJava's second post block 3 is actually moving to the left slightly - i.e. it IS a simultaneous collision problem, so I don't see how an LCP solver would get the correct result. Anonymous' post doesn't answer anything, as far as I can see... it just blindly says "physics=LCP=correct".

I don't have time to re-read this now, but this paper:
http://www.cs.unc.edu/~schmidl/papers/fics-tvcg.pdf
describes how the authors encountered exactly this problem when using QP to solve simultaneous collisions - they resorted to using a couple of passes of sequential impulses before using their QP solver.

Is this relevant?
http://tam.cornell.edu/~ruina/hplab/downloads/collision_papers/latest_alg_law.pdf

[Edited by - MrRowl on October 3, 2006 4:16:07 PM]

Quote:

Original post by Anonymous Poster I think you are the one that do not understand the problem at all, how could you, you implemented a system based on a paper that is totally wrong, it violates every physical principle there is, yet you get upset when somebody try to answer something differently.

Firstly, I'm not upset. Secondly, it's definitely not true to say that "I don't understand the problem at all", so I don't get why you think it's necessary or helpful to say that. Thirdly, that paper doesn't "violate every physical principle there is", so I don't get why you think it's necessary or helpful to say that.

Quote:

The sketch represents the collision of three bodies simultaneously. It is a typical case of a central impact collision, sample of that can be found in any physics textbook, or on the Internet: here is an example: http://theory.uwinnipeg.ca/physics/mom/node3.html

Bad example - that page doesn't discuss the collision of three bodies simultaneously, so I don't get why you mentioned it.

Quote:

I simple check of the consevation of energy or conservation of momentum prove the solution is correct, here it is Total energy before impact: (assume mass = 1) E = m1 * v1 * v1 + m2 * v2 * v2 + m2 * v3 * v3 = 1 * (-1) * (-1) + 0 + 1 * (-3) * (-3) E = 10 Total energy after impact: (assuming restitution) 1 E = m1 * v1 * v1 + m2 * v2 * v2 + m2 * v3 * v3 = 1 * (1) * (1) + 0 + 1 * (3) * (3) E = 10

Unfortunately, you got this wrong. You've written:
before:
v1 = -1
v2 = 0
v3 = -3
after:
v1 = 1
v2 = 0
v3 = 3

It doesn't help that you've decided to use a different direction for the sense of the 1-2 collision and 2-3 collision. Anyway, what you wrote would violate conservation of momentum.

What it should be (now using the convention that +ve vel is from left to right)
before:
v1 = 1
v2 = 0
v3 = -3
after:
v1 = -3
v2 = 0
v3 = 1

This conserves momentum and energy. If you consider the collisions as occuring slightly staggered you get the same end result whether or not:
A) 1 hits 2, then 2 hits 3, then 2 hits 1
or
B) 3 hits 2, then 2 hits 1, then 2 hits 3

Also, if you consider the collisions as occuring staggered (not simultaneous) then Vr = -eVr' is true for each individual collision.

Since you get the same result whatever order the collisions occur in, you must also get the same result if the collisions occur simultaneously.

However, it is clear from the numbers above that when you consider the situation as a whole (i.e. if you treated it as a genuine 3-body simultaneous collision - as you would if you passed it to a LCP solver), "Vr != -eVr'" for every pair of contacts - this is clear when you consider balls 1 and 2: then |Vr| = 3 and |Vr'| = 1.

"Vr = -eVr" IS true between balls 1 and 3 - i.e. it's as if ball 2 (or any other intervening ball) isn't there. But that's not the point.

Quote:

When the system is solved using what ever method you like to used the condition Vr = -eVr’ is satisfied 100%

Can you explain this in the light of what I just wrote? I think I just showed that your statement is incorrect.

I suppose the point is that the "Vr = -eVr'" relationship is derived from (1) conservation of momentum and (2) conservation of energy for a two-body problem. Isn't it just an assumption to assume that it holds in a 3-body problem. Can you prove the assumption is correct (or point to somewhere that does)? Doesn't what I and CuppoJava write prove that it isn't?

Using an LCP solver to resolve a 3-body simultaneous collision rests on this assumption. If the assumption is incorrect, then I guess you would agree that using an LCP solver in this specific situation is wrong too.

Note - I'm just asking for an explanation - I'm not interested in having a go at anyone, and I don't have an axe to grind etc.

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.

Another possibly relevant paper (haven't read it yet)
http://www.mecheng.iisc.ernet.in/~anindya/papers/complementarity_preprint.pdf

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.

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.

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?