Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

The code below is from a Microsoft XNA sample here. This is quite a simple rigid body simulation that ignores many physical effects (such as angular momentum), but it does try to push objects (spheres) apart so that they are not penetrating one-another.

However, the simulation allows spheres not only to penetrate, but when many spheres are stacked on top of each other, small spheres can be almost completely inside of larger spheres. If I make all spheres have the same radius and mass, then the simulation performs reasonably well (with minimal interpenetration).

Can someone explain why there is any interpenetration at all? Since it moves the positions of the spheres, it seems like interpenetration should be impossible.

For each sphere in the simulation, this method is called on every other sphere.

/// <summary>
// Given 2 spheres with velocity, mass and size, evaluate whether
// a collision occured, and if so, excatly where, and move sphere 2
// at the contact point with sphere 1, and generate new velocities.
/// </summary>
private void SphereCollisionImplicit(Sphere sphere1, Sphere sphere2)
{
    const float K_ELASTIC = 0.75f;

    Vector3 relativepos = sphere2.Position - sphere1.Position;
    float distance = relativepos.Length();
    float radii = sphere1.Radius + sphere2.Radius;
    if (distance >= radii)
    {
        return; // No collision
    }

    // Add epsilon to avoid NaN.
    distance += 0.000001f;

    Vector3 relativeUnit = relativepos * (1.0f / distance);
    Vector3 penetration = relativeUnit * (radii - distance);

    // Adjust the spheres' relative positions
    float mass1 = sphere1.Mass;
    float mass2 = sphere2.Mass;

    float m_inv = 1.0f / (mass1 + mass2);
    float weight1 = mass1 * m_inv; // relative weight of sphere 1
    float weight2 = mass2 * m_inv; // relative weight of sphere 2. w1+w2==1.0

    sphere1.Position -= weight2 * penetration;
    sphere2.Position += weight1 * penetration;

    // Adjust the objects’ relative velocities, if they are
    // moving toward each other.
    //
    // Note that we're assuming no friction, or equivalently, no angular momentum.
    //
    // velocityTotal = velocity of v2 in v1 stationary ref. frame
    // get reference frame of common center of mass
    Vector3 velocity1 = sphere1.Velocity;
    Vector3 velocity2 = sphere2.Velocity;

    Vector3 velocityTotal = velocity1 * weight1 + velocity2 * weight2;
    Vector3 i2 = (velocity2 - velocityTotal) * mass2;
    if (Vector3.Dot(i2, relativeUnit) < 0)
    {
        // i1+i2 == 0, approx
        Vector3 di = Vector3.Dot(i2, relativeUnit) * relativeUnit;
        i2 -= di * (K_ELASTIC + 1);
        sphere1.Velocity = (-i2) / mass1 + velocityTotal;
        sphere2.Velocity = i2 / mass2 + velocityTotal;
    }
}

In particular, I though that this:

sphere1.Position -= weight2 * penetration;
sphere2.Position += weight1 * penetration;

Should completely disallow any interpenetration, why doesn't it?

share|improve this question

5 Answers 5

up vote 5 down vote accepted

I think your problem comes from multiple collisions.

Consider three spheres A, B & C.

A sits there.

B hits A. Fine.

C hits B. B is nudged into A. Oops.

share|improve this answer
    
Yes but now C will correct it's position against both A and then against B. I see what you mean, but the examples I have worked out with 3 spheres seem to work out -- so I'm not sure if that's really the problem. Also, I believe that this iterative method is exactly how most game physics simulations resolve collisions. Again, I could be wrong, I'm not sure. Maybe solving collisions one at a time this way only prevents interpenetration if you use continuous collision detection. –  Olhovsky May 10 '11 at 0:02
    
This may actually be exactly the reason. Brandon suggested something similar. +1 for the useful contribution, whether it turns out to be the exact reason or not. –  Olhovsky May 10 '11 at 0:08

This code is taking the collision between two spheres and moving them based on their masses and velocity.

Here's a really basic illustration to show why there is penetration between a blue ball and a green wall.

enter image description here

In this example the center of the ball is 5 feet from the edge of the wall. The ball is moving at 1 foot per second and you are running at a framerate of 1 frame per second. At frame 4 there is no penetration, but frame 5 will have penetration. There's no way of knowing that frame 5 will collide so you can't just say stop when it gets to the wall. Instead you check every frame if the ball is partially inside the wall. If it is, move it back by the amount of penetration and apply the reflective velocity. This is how most collision detection algorithms work. The alternative is to check each frame how far you are from colliding in a certain direction. The problem with that is you need to know what direction to check. This would not work in your situation so the route you are taking is the right one.

The drawback of this approach is the jitteriness that you are probably experiencing. When this script tells a ball to move based on the last collision, then it may be moving to penetrate into another ball, which will then send the ball back to collide with the first. Making it jump back and forth. You can modify the mass of the objects to help with this. That will cause them to jump back slightly less drastically, or reduce the speed in which they collide in the first place.

share|improve this answer
    
Actually the problem is not the "jitteryness" (the instability). I'm okay with the instability, and can correct that later with a distance correction threshold at the cost of accuracy. The problem that I'm having (well, and that Microsoft is having, as it's their code), is that interpenetration is not being solved. That is, not only is it jittery, but there is also a lot of interpenetration, despite the code seeming to resolve penetration. Any idea why that is? Did I miss something in your answer? Thanks for the input btw! –  Olhovsky May 10 '11 at 0:05
    
Oh, I think you're saying that multiple collisions do not resolve correctly due to multiple balls being pushed out of one-another, similar to Loren's answer -- is that right? –  Olhovsky May 10 '11 at 0:07
    
Right, that's the jitteriness, which also causes them to not collide correctly –  brandon May 10 '11 at 2:30
    
Well not really. Instability != interpenetration. Objects can jitter (due to penetration resolution) without interpenetrating. Anyways +1 :) –  Olhovsky May 10 '11 at 2:51

You should read up on Speculative Contacts for catching when collisions will happen before you end up with this kind of penetration.

share|improve this answer
    
+1 for that good link. Actually I bought a membership to Paul's blog yesterday because of that article. –  Olhovsky May 10 '11 at 18:52

SphereCollisionImplicit() gets called after the spheres have moved. That movement could have ended up with collision & interpenetration, this method resolves that.

start frame:

  1. elsewhere in your code, the position is updated by velocity.

  2. Then this method is called to see if that resulted in collision/penetration.

  3. if so, it separates them & reflects/changes their velocities.

  4. next frame, positions are updated with new/changed velocity... goto 1.

share|improve this answer
    
I don't understand what you're trying to say. Currently in that XNA sample, it does exactly what your bullet points say, and drawing of the balls occurs right after step 3. So why is there still interpenetration? Like you said, we expect step 3 to separate them. –  Olhovsky May 9 '11 at 17:55
    
Step 1 & 4 can cause penetration, step 3 removes the penetration if it occurred. –  Steve H May 10 '11 at 19:23
    
The point of this question is that penetration is not being completely removed. See other answers for why that is. –  Olhovsky May 10 '11 at 20:07

There is interpenetration because every time a ball's position and velocity is changed, it needs to be checked to see if it has collided with any other ball that was checked earlier in the loop. For instance, given 3 balls:

Start 1. Ball #A is checked against Ball #B, no collision

  1. Ball #A is checked against Ball #C, no collision

  2. Ball #B is checked against Ball #A, no collision

  3. Ball #B is checked against Ball #C, found collision!! Ball #B and #C are moved.

  4. Ball #C is checked against Ball #A, no collision

  5. Ball #C is checked against Ball #B, no collision

Done

So... Step 2 may have moved Ball #B into Ball #A, causing interpenetration.

To fix, I think whenever a ball is moved, it needs to be re-checked against all the other balls, whenever it is moved. In this scenario, Ball #B bumps into Ball #C, richocheting Ball #B into Ball #A, richocheting Ball #A into Ball #C!, which hits Ball #B again....

How many richochets do you process in one frame? Do you also need to re-check against all the walls after each richochet also?

Start 1. Ball #A is checked against Ball #B, no collision

  1. Ball #A is checked against Ball #C, no collision

  2. Ball #B is checked against Ball #A, no collision

  3. Ball #B is checked against Ball #C, found collision!! Ball #B and #C are moved.

  4. Restart #B and #C loop...

  5. Ball #B is checked against Ball #A, found collision!! Ball #B and #A are moved

  6. Restart #B and #A loop...

  7. Ball #A is checked against Ball #B, no collision

  8. Ball #A is checked against Ball #C, found collision!! Ball #A and #C are moved

  9. Restart #A and #C loop

  10. Ball #A is checked against Ball #B, no collision

  11. Ball #A is checked against Ball #C, no collision

  12. Ball #B is checked against Ball #A, no collision

  13. Ball #B is checked against Ball #C, found collision!! Ball #B and #C are moved

  14. Restart #B and #C loop

  15. Ball #B is checked against Ball #A, no collision

  16. Ball #B is checked against Ball #C, no collision

  17. Ball #C is checked against Ball #A, no collision

  18. Ball #C is checked against Ball #B, no collision Done

share|improve this answer
    
Actually that's not it. Collisions are checked against all other balls, the problem is with the order of the checks (as suggested by the answer with the green checkmark :). Checking against all other balls is not enough by itself. –  Olhovsky Nov 3 '11 at 5:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.