# Why do objects interpenetrate in this simple collision solver?

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();
{
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?

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.

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

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.

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

• +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.

• 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

• 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