Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / Game Design & Programming / Rigid Body Dynamics - Impulse method - Please give me some advice. Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
CuppoJava

January 03, 2005, 02:01 PM

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.

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

Thanks for considering the problem. To me, this seems like quite a fundamental problem, that I want to solve before even attempting friction.

 
I'M BRIAN FELLOWS

January 03, 2005, 02:41 PM

WHAT PROBLEM ARE YOU HAVING?

 
CuppoJava

January 03, 2005, 02:51 PM

Sorry I'll compress my message.

Basically, in the second picture i posted, I know how to do that. Its a propagation problem.
And in the first picture with the big block hitting the two smaller ones. I can do that too, I solve it simultaneously.

But I don't know how to distinguish between the two situations, such as when I need to solve it simultaneously and when I need to propagate.

LCP solver does not work. (Actually, I really* have no clue what the LCP solver is for, I used a linear equation solver instead and it gives the same results...which are not correct.)

 
Danny Chapman

January 03, 2005, 03:57 PM

CuppoJava wrote: LCP solver does not work. (Actually, I really* have no clue what the LCP solver is for, I used a linear equation solver instead and it gives the same results...which are not correct.)[/i]


LCP is used to ensure that the output does not contain negative impulses - i.e. ones that would act to push two objects together - that could be generated from a simple linear solver.

Sorry, I know that doesn't answer your real question.

 
CuppoJava

January 03, 2005, 07:53 PM

Hi,
Anyway, that's what I thought what a LCP solver did... but why

Vrel' > -eVrel (Complementarity problem)

instead of

Vrel' = -eVrel (Straight-forward linear equation solving)

They're both wrong anyway. The second picture violates both constraints.

PS: Are you Mr.Rowl from gamedev.net??

 
Rui Martins

January 04, 2005, 04:52 AM

... But I don't know how to distinguish between the two situations, such as when I need to solve it simultaneously and when I need to propagate.

There shouldn't be any specific code for propagation. It just happens as the normal behaviour of the system.

However, for multiple simultaneous collisions, you specifically have to handle those, like a special case, at least in the collision detection phase.
The Collision response can have the same implementation, as long as you determine the resulting net force(impulse) to apply for each object.

 
Danny Chapman

January 04, 2005, 05:10 AM

Rui Martins wrote: There shouldn't be any specific code for propagation. It just happens as the normal behaviour of the system.


Propogation is only going to work if you implement backstepping (potentially too expensive for games?), and consequently handle each collision sequentially, I think. I.e. detect collision between 1 and 2 at time t, handle it so that 1 stops and 2 moves, then detect a collision between 2 and 3 at t+0 etc. until the ball at the end shoots off.

Getting a LCP solver to treat this as a simultaneous collision system is wrong - hence the wrong result that you get.

I'm not quite sure what an iterative scheme (like the one I implemented) would result in (I should try it :) - it might actually work... though you'd need at least as many iterations as elements in the chain.


 
CuppoJava

January 04, 2005, 02:26 PM

Thanks for replying Mr.Chapman

I Completely agree with you. ONLY an iterative method will work for the second situation. and ONLY a simultaneous calculation will work for the first situation (the bigger block hitting the two smaller ones). But how do I choose between the two?

But you see the problem now right? I wish I could contact Baraff directly or something, it seems this is an unsolved problem in this field but no one has even mentioned it in their papers.

 
John Schultz

January 04, 2005, 06:13 PM

CuppoJava wrote: Thanks for replying Mr.Chapman I Completely agree with you. ONLY an iterative method will work for the second situation. and ONLY a simultaneous calculation will work for the first situation (the bigger block hitting the two smaller ones). But how do I choose between the two? But you see the problem now right? I wish I could contact Baraff directly or something, it seems this is an unsolved problem in this field but no one has even mentioned it in their papers.


I believe you can reach David Baraff here: http://www-2.cs.cmu.edu/~baraff/ (see the Pixar email address).

Many times there are no published solutions to problems (that does not mean they have not been solved). After viewing your diagrams, I'm surprised IBF didn't repond with:

THINK OUTSIDE THE BOX

which wouldn't be bad advice. Think of a way to solve the problem so that you get the desired visual result, not thinking about physics per se, just the desired behavior. Write some code, experiment.

As Danny stated, you don't need an LCP solver. Always consider the simplest methods first. You can deal with multiple contacts in (at least) three common (and relatively easy to implement) ways:

1. Apply impulses pairwise and immediately update the momentum for each contact pair's body. Not "exactly accurate" but totally stable and very fast. Perfectly suitable for games.
2. Store all contacts and apply a single, weighted impulse to each body. Can be energy accurate. Weighting based on momentum in the direction of the contact is a good weighting method.
3. Apply just one impulse per contact pair (using the deepest point, first contact point, etc.). Fastest, easiest to implement and perhaps oldest method. This method can jitter for resting objects (unless sleep code is implemented or other trick is used).

Game engines typically combine one of the above methods with a penalty spring or iterator/separator to keep objects from over-penetrating. This will give you plausible behavior for most types of games. Once you are at this stage, you'll find that the problems you listed aren't really problems (you'll also find that your above statement(s) aren't exactly accurate).

If you need perfect or near-perfect response for your example problems (for a specialized, physics-based game where such behavior is required for gameplay (pool/billiards-like game)), you can optimize your physics engine to (for example) sort and propagate, iterate (finite element deformation and restitution: "nothing in real-reality is truly-rigid"), etc. Otherwise, use one of the simpler methods, or invent something new!

(If you don't need a general solution, the problem is often an order of magnitude easier to implement for your specific case(s)).

 
This thread contains 9 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.