Sign in to follow this  

Intelligently distributing impulses

This topic is 3848 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

I'm working on my physics engine right now. At first my goal was to easily allow stacking. I didn't want to use any of the fudging methods (putting objects to sleep, etc.), I wanted my engine to actually figure out the forces involved (normal force, etc.), cancel out forces where necessary, and produce a realistic simulation of what's happening. My idea was to change my physics engine to work thusly: 1. Calculate Forces 2. Integrate forces to find new velocity. 3. Transfer momentum between bodies that are touching. 4. Integrate velocities to find new position. 5. Respond to new collisions by transferring momentum and projecting objects away from each other. I'm having trouble with #3. What I'm trying to do is check for existing collisions before I move objects, to detect places where the energy would be distributed between bodies. For instance, take the case of this simple stack of circles: Free Image Hosting at www.ImageShack.us All three spheres would have a new downward velocity after integrating the forces. The bottom sphere collides with the wall (inelastically), basically transferring all its new momentum to the wall, with the end result causing it to have no new momentum at all. It would stay at rest. The sphere above the bottom one would also transfer its momentum to the wall, but it would do so indirectly, by colliding with the bottom sphere. So the algorithm would look something like this for step 3:
while there are still touching objects that are also moving towards each other
  for each object
    for each object touching this object
      if their relative velocity would cause them to collide then
        perform an inelastic collision between these two objects
I'm pretty sure the algorithm is correct, but it's rather slow. With the case of the stack of spheres, the momentum only gets transferred very slowly down the stack. Hope I've explained this well. I'm wondering if anyone has any ideas about how to distribute the impulses that's faster than pairwise colliding objects.

Share this post


Link to post
Share on other sites
I solved the speed issue by adding a small value that describes the desired separation amount between balls. I added that value * collision normal to the input velocities for the objects, basically, so that I would slightly overstate how much the objects velocities were penetrating. That solved that issue.

Share this post


Link to post
Share on other sites
Quote:
Original post by pTymN
I solved the speed issue by adding a small value that describes the desired separation amount between balls. I added that value * collision normal to the input velocities for the objects, basically, so that I would slightly overstate how much the objects velocities were penetrating. That solved that issue.


I'm not sure I understand how this will help. Keep in mind that what I'm doing is testing for collisions before I update positions. So I'm checking for collisions (actually, near collisions since the previous cycle should have fixed any) from the previous cycle to distribute impulses around before I actually integrate them to change positions.

At the moment I'm thinking my problem is related to statics. Like Bridge Builder.

Share this post


Link to post
Share on other sites
Are you following the paper "Impulse-based Rigid Body Dynamics with Stacking"?

Anyway,
the reason your simulation is slow (i think) is:

take the example of a single block resting on a surface.

you apply gravity.
so now, the block has a negative relative velocity with relation to the ground.
so now you do an inelastic collision.
the block now has a velocity of zero.

you rinse and repeat.

but now notice that EVERY SINGLE TIME STEP, your block will be "colliding" with the ground and will require an inelastic collision to resolve it.

I haven't tried pTyMn's solution but I imagine it works because:

when he detects that the block is colliding with the ground, he moves the block back to the surface. AND OVERCOMPENSATES.
This way, in the next (few) time steps, the block won't collide with the ground.
Thus requiring less collisions.

...it doesn't seem like a very solid fix to me. But I haven't tried it. pTyMn can tell you better himself about the advantages and pitfalls of his method.

Share this post


Link to post
Share on other sites
Quote:
Original post by CuppoJava
Are you following the paper "Impulse-based Rigid Body Dynamics with Stacking"?


I read the paper a while ago, but I didn't get much out of it. I probably should go back and read it again now that I have more experience.

Quote:

Anyway,
the reason your simulation is slow (i think) is:

take the example of a single block resting on a surface.

you apply gravity.
so now, the block has a negative relative velocity with relation to the ground.
so now you do an inelastic collision.
the block now has a velocity of zero.

you rinse and repeat.

but now notice that EVERY SINGLE TIME STEP, your block will be "colliding" with the ground and will require an inelastic collision to resolve it.


That's not so bad. It would only be a single collision every cycle. The problem is when you have multiple objects stacking. Say you have two spheres on top of each other. They both would have the same velocity downwards, so they don't collide. Then the bottom one collides with the floor, and has zero velocity. Then the top one collides with the bottom, and they both have half velocity. Etc. etc. The result is basically a binary search for 0 (ie: 1, .5, .25, .125, until you arrive at some low threshold value). It gets even worse as you increase the height of the stack.

Quote:

I haven't tried pTyMn's solution but I imagine it works because:

when he detects that the block is colliding with the ground, he moves the block back to the surface. AND OVERCOMPENSATES.
This way, in the next (few) time steps, the block won't collide with the ground.
Thus requiring less collisions.

...it doesn't seem like a very solid fix to me. But I haven't tried it. pTyMn can tell you better himself about the advantages and pitfalls of his method.


Assuming it did manage to decrease the number of collisions over several frames, it doesn't address my primary purpose, which is to distribute impulses around before integrating position.

Share this post


Link to post
Share on other sites
"The result is basically a binary search for 0 (ie: 1, .5, .25, .125, until you arrive at some low threshold value). It gets even worse as you increase the height of the stack."

Yup, that's a pretty fundamental difficulty of using the impulse method. So far, it's ... more or less unresolved. There are a few hacks that we know of though.

The Dynamics with Stacking paper uses a "shock step", to resolve this.
The basic idea is: after an object collides with the ground, it inherits an "infinite mass" attribute that lasts for only that time step.
Leads to some awkward looking towers that look like they should fall...but don't.

Another approach is to use a LCP solver to solve for resultant velocities for multiple collisions simultaneously.
This approach leads to propagation problems, ie. certain Newton's cradle type situations don't work properly.

Yup...both hacks. But depending on your purposes, one of them might be sufficient for you. I personally would lean toward the "shock step". Neither hack guarantees any form of physical realism but at least the first one is easier to program.

Last choice:
Switch over to a penalty force method instead of using impulses.
Disadvantage: it's unstable..and blows up frequently.

Share this post


Link to post
Share on other sites
Congrats for trying to write the simulator though. More people should try it. It's a lot of fun. Are you addicted yet? =)

Good luck
-Cuppo

Share this post


Link to post
Share on other sites
I've been working on physics off and on since summer of 2005, so I guess I'm hooked ;)

If I limit myself only to the 1D case (objects stacking in a straight line), then I can think of it as building a collision tree (well, a tree without any branches for the 1D case. More of a linked list really) that records the collision points between objects.

If I further limit myself to having the floor as the final node in my tree, I could then traverse the tree (starting with the bottom, and working my way up) and perform collisions using any nodes under the current node as a single large object.

For instance, starting with the bottom sphere I collide it with the floor. Pretty standard. The next higher sphere collides with the sphere below it and the floor at the same time, like a single object. The floor's infinite mass gets added to the bottom sphere's (still infinite) to create a new object that the upper sphere collides with, and that second sphere ends up with 0 velocity too. You could work your way up the stack like that, and you'd have an effective way of eliminating the impulses gained from gravity of every sphere in your stack, with an algorithm that has a reasonable run time. Every sphere would treat the stack ob objects below it as a single huge object.

I believe it could even be generalized to a stack of objects not resting on the floor, though there are some tricky issues I haven't played with so I can't be sure (such as a stack of 3 objects that is in free fall, and a stack of 3 objects where only one of the spheres has any velocity. 3 stacking objects sandwiched between two "floors", etc.).

I'm not sure how you would generalize it to 2D or 3D cases though. Instinctively I think it's similar to Statics, where you determine how the stresses on structures propagate to support beams, etc.

Share this post


Link to post
Share on other sites
Okay, I'm confident this works for the 1D case. It just needs to be made more general for the case of 2D and 3D.

First, a collision only occurs if two objects are connected by a contact point and their relative velocities would cause them to collide when position is integrated.

The algorithm works like this:

Build the collision "tree"

While there are still collisions in the collision tree
For each collision in the collision tree
Find the string of objects with the same velocity as either collision-ee
Perform an inelastic collision between the two object strings


The string of objects for a collision-ee is just how far up or down the tree you can traverse and still encounter objects with the same velocity.

The algorithm effectively performs its 1st pass as a pairwise. Afterwards it slowly builds up large groups of objects with the same velocity. These groups basically act as a single large body.

Here's what it looks like on a stack of 5 objects (arrows point velocity direction)

initial:
0 0 0 0 0
> - < > <

1st pass:
0 0 0 0 0
.5> .5> < - -

2nd pass:

0 0 0 0 0
- - - - -


I'm not sure how you would generalize this to 2D or 3D though.

Share this post


Link to post
Share on other sites
You should really read the Guendelman paper CuppoJava referred to, you'll find that your "collision tree" idea is in fact a contact graph: graphics.stanford.edu/~fedkiw/papers/stanford2003-01.pdf

And you should _absolutely_ read this paper, which deals specifically with various aspects of the construction and use of contact graphs: http://www.diku.dk/publikationer/tekniske.rapporter/2004/04-06.pdf

The distinction between tree and graph is important -- in your 1D case the graph will never have loops, so it's possible to consider it a tree, but in the general 2d/3d case there _will_ be loops, which means some operations like traversal won't be as easy.

Share this post


Link to post
Share on other sites
Thanks for the links, I'll print both papers out and read them at work today. As I said before, I read the first paper once but it didn't make much sense to me. I think I have the background now to figure it out. I've never seen that second paper though. Should be an interesting read.

Share this post


Link to post
Share on other sites
Okay, I've read the papers. It looks like for the paper on stacking they're doing something very similar. They work up the contact tree, setting the objects to infinite mass below the current level. I can see why they would set it up this way, but I'm looking for something a little more general.

I can also see the pathological case of a circuit. Something like 3 knives layed so that the all rest on one knife while the other knife rests on them. But let's set this pathological case aside for the moment. I'll limit myself just to stacking spheres for the moment.

The simplest 2D case I can imagine is 3 spheres stacked in a pyramid. In this case, the top sphere delivers it's entire impulse to the bottom two spheres (since the normal force from the bottom spheres are orthogonal to each other). This force gets partially cancelled by the floor and results in a lateral motion by the bottom two spheres.

I might be able to come up with a system like this, but I get lost when the contact forces aren't normal to each other. Imagine 3 large spheres and a smaller one set up in such a way that the top large sphere rests on the smaller sphere and the two larger spheres. How would the forces get distributed in such a case?

Share this post


Link to post
Share on other sites
That second paper walks through their implementation of a full contact graph -- it should be able to handle any sort of weird cyclical stacking situation.

Share this post


Link to post
Share on other sites
You mean the first paper right? I didn't see any discussion of handling cycles in the second paper. The first paper works its way from the floor up, resolving collisions between objects in the current layer and the layer below by setting the lower layer's mass to infinity. For cycles, all objects in the cycle are treated as existing on the same level. It's a decent solution, but my issue with this is that it requires global information-- which end is up, which end is down, and if there's a floor or not.

I'm imagining something more general, with the case of objects stacking on the floor as simply a usecase. Something like a self propelled cube in space colliding into a dense rubble field, for instance, and effectively pushing the rubble field forward.

I think I'm slowly working towards a general case like this, but I'm running into some issues. Let me try to present them in an easily digestable format, and see if people can present some ideas about how to solve them.

The first is the case where there's more contacts than are necessary to provide equilibrium. Take the case of a rigid bar being hung from a ceiling by 3 strings. Two attach to either end while the third passes through the center of mass.

Trying to find the tension in the wires, you find that there's actually a system of solutions. My initial instinct is to solve these sorts of issues by telling the engine that tensions should be distributed "evenly". Problem is I'm not sure how to define "evenly". Does it mean that the normal components of tension should be even, or that the magnitude of the whole vector should be equal for all wires? And when can I apply it?

The second case that confuses me consists of a rigid body and two wires. One wire passes through one end and is completely vertical. The second wire passes through the other end and makes a 45 degree angle with the horizon.


| /
| /
| /
-----------


Clearly this system is not in equilibrium. Exactly what sort of forces result from a situation like this? Intuitively I'd say that there isn't any torque, just a translational force. But I'm not sure how to show this mathematically.

Share this post


Link to post
Share on other sites
Sign in to follow this