Sign in to follow this  

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

This topic is 4719 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Here are two situations that my engine is having trouble with. I searched on the web extensively but could not find any engine that handles both problems correctly. The fundamental problem I think is : Vrel' = -eVrel only holds for two-particle collisions. It is not correct for collisions between more than two bodies. I'm not sure if its even correct for multiple contact points between only two bodies. I've implemented an LCP solver to see if it resolves this problem, but it does not. Thanks for considering the problem. To me, this seems like quite a fundamental problem, that I want to solve before even attempting friction. [Edited by - CuppoJava on January 1, 2005 2:54:28 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If properly implemented, using a LCP will resolve it... the whole purpose of using a LCP (Solving Ax=b, with constraints) is that it will resolve all contacts.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Almost forgot, try the paper "Complementarity Based Multiple Point Collision Resolution" :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Actually the Newton engine handles that situation correctly.
I think they even have demos with perfect Newton Cradles in there website

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Oh I see, I think your test conditions are incorrect.
I think you are a little confused as how physics engine works. All physics engine use LCP solvers to determine the relative acceleration or transfer of momentum between contact points of ridig bodies. The LCP is the method that will calculate this accelerations correctly, I recommend you to read the work of David Baraf, Andrew Witkin, and perhaps simpler the work of Chris Hecker.

The problem with you test is that you assume the objects are point particles, and a such the will be only on contact directed the center of the particle in each collision, but that is not truth when you deal with rigid bodies other than mass particles.

Physics engine used collisions system to calculates contacts based on objects interpenetration, points of impact are rearly exact. To resolve the penetration a small amount of penalty is added at each contact point though adding extra momentum to the collision solver. Also the contact calculation is based on geometrical algorithms that do not guarantee perfect symmetrical distribution of contacts.

In the example you proposes the when you say:

Vrel' = -e*Vrel

You are solving the problem analytically making the abstraction of one contact per object at the object center; you ignore angular momentum, and contact distribution, friction, etc.

That identity is the exact condition used by physics engine solvers (LCP), except the condition is applied to each contact point. The result you are expecting will only happens if the contacts distribution is perfectly symmetric, the object are not rotating and friction is not considered.

When you set your example those conditions do happen at each contact point at the moment of the impact however a tiny asymmetry lead to a small deviation, and because the physics engine has to continue the integration, since physics is an initial value problem, tiny errors in the initial condition lead to large error during the integration.

An easier way to test that theory is by using spheres, in a friction less surface that will prevent the spheres from rotating, and therefore they will behave more closely to point mass objects. An example of this is a Newton Cradle. Another example is a pool, even thought in a real pool game to reproduce that condition you need to be a very good player.

When I said the Newton engine handle that condition I was referring to the solver part, the Newton engine have and exact solver, which mean the solution is not and approximation to the LCP condition, after each step the LCP condition is satisfied 100%.
Currently Newton and ODE are the only two engines in the market with exact LCP solvers, the difference is that ODE recently changed to an iterative method.

Having an exact solver does not mean the result will be 100% predictable, for that to happens you need to do a better job at setting your parameters, and you environment. If you set your test condition correctly then Newton is the only physics engine that is capable of producing those results.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
Guest 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.

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.


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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".

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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."

Share this post


Link to post
Share on other sites

This topic is 4719 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this