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

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.

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.

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.

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.

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.