Jump to content
  • Advertisement
Sign in to follow this  
IntegralKing

Why do objects interpenetrate in this simple collision solver?

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

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?

More generally, when doing rigid body simulations, is it enough to compare only two objects at a time, and respond to their collisions, or is it common to compare all objects that are colliding with an object simultaneously (e.g. by computing some average position of all collisons)?

Share this post


Link to post
Share on other sites
Advertisement
Well, that equation doesn't move the stuff out geometrically. The weights are calculated from stuff, that has nothing to do with the geometry. I'd say to perfectly move them out of collision, you have to use 0.5 as both weights. But to be honest I don't get those weight calculations, maybe someone can shed some light on it.

I, for one, wouldn't move objects out of collision at all. Sure, in real life, objects cannot penetrate each other. But in real life objects CAN deform, while that deformation is not simulated in the program. And in real life, the initial, undeformed shapes CAN penetrate each other. Since you can only simulate the undeformed shapes, they SHOULD penetrate each other at collision. So in you case, small balls would "disappear" inside big objects. This kind of simulation is also more stable and easier to handle. Moving objects explicitly out collision is very problematic, multiple collisions, colliding with corners etc.

Share this post


Link to post
Share on other sites

Well, that equation doesn't move the stuff out geometrically. The weights are calculated from stuff, that has nothing to do with the geometry. I'd say to perfectly move them out of collision, you have to use 0.5 as both weights. But to be honest I don't get those weight calculations, maybe someone can shed some light on it.


It moves them both by a total amount equal to the amount that they are intersecting. It chooses how much to move each of them based on their relative weights. For example, sphere1 might have a total relative weight of 0.7, and then sphere2 would have a relative weight of 0.3. Sphere1 would be moved by 0.7 of the intersection, and sphere2 would be moved by 0.3 of the intersection. In total, the balls are moved apart by exactly the size of the intersection.


My understanding is that all/most rigid body physics simulations (e.g. Bullet, BEPU, JigLib), try to avoid interpenetration, but if it does happen, then they force the objects out of each other. Different simulators do it in different ways, with varying levels of speed/accuracy/stability.

I would expect the method shown above to be unstable, but I don't get why it allows objects to interpenetrate though.

Share this post


Link to post
Share on other sites

I describe exactly this scenario in my blog post on physics, and how to solve it:

http://www.wildbunny...es-for-dummies/

Hope it helps!

Cheers, Paul.


Oops, you posted a few seconds before me. Funnily enough, I was about to post a question on your article about speculative contacts, which is what sparked my interest in physics simulations to begin with.

Thanks for the link, I didn't see that article on your site earlier :)

Share this post


Link to post
Share on other sites

More generally, when doing rigid body simulations, is it enough to compare only two objects at a time, and respond to their collisions, or is it common to compare all objects that are colliding with an object simultaneously (e.g. by computing some average position of all collisons)?


For a moving spheroid against static bodies you usually collide against a list of objects one by one and adjust the new position sequentially. Check here (the source is in white links at the middle).

Share this post


Link to post
Share on other sites

I describe exactly this scenario in my blog post on physics, and how to solve it:

http://www.wildbunny...es-for-dummies/

Hope it helps!

Cheers, Paul.

So I read through the article, (it was great by the way), however it doesn't answer the question in the OP. As far as I can tell, this code *does* resolve the collisions (by forcing the positions to move apart by an amount equal to the intersection of the objects). It should be pretty unstable (jittery) without using a method of relaxing or a threshold or speculative contacts that you described. Before I move on to something like that, I want to understand why this simulation doesn't work properly though :/



[quote name='IntegralKing' timestamp='1304928520' post='4808425']
More generally, when doing rigid body simulations, is it enough to compare only two objects at a time, and respond to their collisions, or is it common to compare all objects that are colliding with an object simultaneously (e.g. by computing some average position of all collisons)?


For a moving spheroid against static bodies you usually collide against a list of objects one by one and adjust the new position sequentially. Check here (the source is in white links at the middle).
[/quote]

That's what the code in the OP does. The method in the OP is called by each sphere on every other sphere in the simulation. So collision response gets done on every sphere sequentially -- hence my confusion. Thanks for the link, I'll check it out!

Share this post


Link to post
Share on other sites

So I read through the article, (it was great by the way), however it doesn't answer the question in the OP. As far as I can tell, this code *does* resolve the collisions (by forcing the positions to move apart by an amount equal to the intersection of the objects). It should be pretty unstable (jittery) without using a method of relaxing or a threshold or speculative contacts that you described. Before I move on to something like that, I want to understand why this simulation doesn't work properly though :/


Does the code correctly resolve the collision when there are only two spheres involved?

Have you tried iterating a few times to see if it converges in the case of multiple spheres?

Cheers, Paul.

Share this post


Link to post
Share on other sites

Does the code correctly resolve the collision when there are only two spheres involved?

Yes, it appears to. Or if there is some error, it's too small to see it.

Have you tried iterating a few times to see if it converges in the case of multiple spheres?

I have tried running the collision code 10 times per frame, which doesn't appear to change the simulation at all.

Like this:


// Resolve sphere-sphere collisions
for (int k = 0; k < 10; k++)
{
for (int i = 0; i < numSpheres; i++)
{
for (int j = 0; j < numSpheres; j++)
{
SphereCollisionImplicit(spheres, spheres[j]);
}
}
}

Share this post


Link to post
Share on other sites

Like this:


// Resolve sphere-sphere collisions
for (int k = 0; k < 10; k++)
{
for (int i = 0; i < numSpheres; i++)
{
for (int j = 0; j < numSpheres; j++)
{
SphereCollisionImplicit(spheres, spheres[j]);
}
}
}



Very odd... Just a quick aside; you probably want to do this:


for (int i = 0; i < numSpheres-1; i++)
{
for (int j = i+1; j < numSpheres; j++)
{
SphereCollisionImplicit(spheres, spheres[j]);
}
}


which compares objects A and B only once, whereas your loop compares A and B and B and A.... :)

If you removed all the code from the function you're using apart from something like this:



private void SphereCollisionImplicit(Sphere sphere1, Sphere sphere2)
{
Vector3 relativepos = sphere2.Position - sphere1.Position;
float distance = relativepos.Length();
float radii = sphere1.Radius + sphere2.Radius;
Vector3 relativeUnit = relativepos * (1.0f / distance);

float pen = distance-radii;

if (pen < 0)
{
sphere2.Position -= relativeUnit*pen/2;
sphere2.Position += relativeUnit*pen/2;
}
}


And then iterated that, I would expect that to converge to some extent the more times you iterated... Note, this is untested code - you might need to reverse the signs on the code inside the penetration check :)

Cheers, Paul.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!