Jump to content
  • Advertisement
Sign in to follow this  
Numsgil

Intelligently distributing impulses

This topic is 4003 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!