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...

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.

The problem is that engines using iterative methods, will find an approximation to that solution, due to the problems I mention before.

If you disagree with that result then it is not the LCP method you are having problem with, is the principle of conservation on momentum instead. Your problem is that the result does not make sense to you, but it is correct according to Newtonian mechanics.

Vr = -eVr’

Does not come from the LCP condition it comes from the principle of conservation of momentum applied to each contact point, and that is obeyed by all physics engines at the very fundamental level. If that was not the case, what you show there will be the least of the problems any physics engine would have, and for the most part the result produced by any of then agree with every day common events.

You may be on to something here, after all Aristotle law of motion stated that

f = m * v

And it was undisputed for over 1800 years until Galileo came along and proves it wrong.

If you disagree with the formulation as and LCP (linear complementarily problem) to find the solution for the relative accelerations, then you should be able to prove it rigorously, not just by intuition, if you can do that I can guarantee you will be very famous.

Also you said you implemented your LCP solver if you are getting the result you get by intuition, then your solver is correct. I would not worry about that too much, unless you fill very strong about it and like to go in the quest of your life.

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 MrRowl
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 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. You do not have critical thinking you just copied something from a paper, with the validation it most be right because you found in a paper.

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
Notice the sketch shown the bodies detached but at some point they will collide (just in case MrBowl was wondering).

The expression Vr = -eVr’, is a vector expression that when formulated in term of the participant elements lead to a linear system.

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

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

You can do it with conservation of momentum along the direction of motion and you can se the total amount pf momentum is also preserved.

If the problem is formulated terms of the principle of conservation of momentum as Baraff did on his 1994 paper, what you get is a linear system of equation in which the values of some of the variables have the restriction the some of the can not be negative when the right hand column value is positive, or there must be zero if the right hand value is negative.
The right hand is the relative acceleration between contact points.
This method for solving this kind of linear system is called Linear Complementarily Program, the method is very similar to solving a simplex method as the solution of both where invented by: George B Dantzig in 1940.
I had been using the method since the 70’s to solve very large optimization problems.

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