Elastic collision of circles and spheres

Inspired by a question on StackOverflow I decided to write a short article about the physics of elastic collisions. The principle is always the same. But for reasons of simplicity I will explain everything by taking the example of sphere collisions. Due to the nature of spheres the algorithms can be used directly for hyper spheres of any dimension, especially for the two-dimensional circle or the three-dimensional ball.

Detecting a collision

For spheres a collision detection is particularly easy. Let’s have a look at a sphere’s definition first:

Sphere definition

Let V be any vector space. Then a sphere consists of all points x with a distance to the sphere’s center that is less than its radius. This makes collision detection very easy. Two spheres collide (or intersect) if there is at least one point that is in the range of both spheres. And this is the case if and only if the spheres’ centers are at most radius1 + radius2 apart.

The superposition principle

The superposition principle is a method that can be applied to a wide range of areas. For the purposes of this article we want to use the superposition principle for velocities. It means that any velocity can be decomposed into other velocities and vice versa.

Superposition principle for velocities

An object that moves with velocity v can be seen as moving with both velocities v1 and v2 simultaneously. The combination of several wind directions is a pretty imaginable example. If there are some steady wind sources and you stand at a certain position, you will not recognize each direction, but only one combined wind direction.

This principle helps us in the collision resolution because a collision usually takes place in a single direction. We can decompose the object’s velocity into a component that is parallel to the collision direction and the remainder that is not influenced by the collision.

Resolve a collision of two spheres

A collision resolution system can be very complex. For the purpose of this article I will focus on the resolution of a two-sphere collision which is sufficient for most cases.

The key point for collision resolution is a consistent state. Our algorithm has to ensure that we never run into an inconsistent state, i.e. two or more spheres intersect. An intersection will never happen in the real world, because there would have been a collision beforehand. The following examples will consider a simple simulation with uniformly moving spheres. In each frame, the spheres’ positions are updated as follows:

foreach(var sphere in spheres)
{
    //seconds is the elapsed time since the last frame
    sphere.Position += sphere.Velocity * seconds;        
}

So our simulation or game runs, we regularly check for collisions and suddenly it happens – two spheres intersect. What do we do now?

Remember the key point. An intersection will never happen in the real world. So we have to turn back the time to the point were the collision actually happened. However, determining this amount of time is not that easy. For uniformly moving objects this can be calculated with a closed form formula. For more complex movements this can become a bit tricky. A way that is always possible is stepping back in time with very small steps until there is no intersection anymore.

But we have a uniform movement and therefore we can calculate the amount of time. If p1 and p2 are the spheres’ positions, v1 and v2 are the sphere’s velocities and r1 and r2 are the spheres’ radii, then we want to find the amount of time t where both spheres touch:

Touch Point of Spheres

Usually there are two points that fulfill the above equation. The point that we are looking for and a point somewhen after the collision, assuming that the spheres continue to move in their directions. So we are looking for the positive solution of t. If you like, you can calculate the solution yourself. Or just believe me that the following code is correct:

var backTimeRoot = 0.5 * Math.Sqrt(4 * Math.Pow(p1x * (v1x - v2x) +
    p2x * (-v1x + v2x) + (p1y - p2y) * (v1y - v2y), 2) -
    4 * (p1x * p1x + p1y * p1y - 2 * p1x * p2x + p2x * p2x - 2 * p1y * p2y + p2y * p2y -
    r1 * r1 - 2 * r1 * r2 - r2 * r2) * (v1x * v1x + v1y * v1y - 2 * v1x * v2x + v2x * v2x -
    2 * v1y * v2y + v2y * v2y));
var backTimeSummand = p1x * v1x - p2x * v1x + p1y * v1y - p2y * v1y - p1x * v2x + p2x * v2x - p1y * v2y + p2y * v2y;
var backTimeDivisor = v1x * v1x + v1y * v1y - 2 * v1x * v2x + v2x * v2x - 2 * v1y * v2y + v2y * v2y;
var backTime = (backTimeSummand + backTimeRoot) / backTimeDivisor;
backTime += 0.001; //compensate for floating point errors

sphere1.Position -= sphere1.Velocity * backTime;
sphere2.Position -= sphere2.Velocity * backTime;

Now we have reestablished a consistent state and can go about resolving the collision.

As I already mentioned, we want to decompose the velocities. But what directions do we need? Every simple collision can be seen as a collision with a plane. So we have to find a plane that represents the sphere-sphere collision. It should be perpendicular to the surfaces at the touching point. So for two spheres it must be perpendicular to the connection line between the spheres’ centers. That’s all we need to characterize the plane.

Collision Plane of two spheres

The difference vector of the centers can be used as the plane’s normal.

Vector collisionNormal = sphere1.Position - sphere2.Position;
collisionNormal *= 1 / collisionNormal.Length;

Now is the time to decompose the sphere’s velocity v1 into a component that actually collides v1Collide and a component that is not affected by the collision v1Remainder:

Velocity decomposition

We made the collision normal a unit vector, so the decomposition is very simple and can be achieved with the dot product:

//Decompose v1 in parallel and orthogonal part
var v1Dot = Vector.Dot(collisionNormal, sphere1.Velocity);
var v1Collide = collisionNormal * v1Dot;
var v1Remainder = sphere1.Velocity - v1Collide;

//Decompose v2 in parallel and orthogonal part
var v2Dot = Vector.Dot(collisionNormal, sphere2.Velocity);
var v2Collide = collisionNormal * v2Dot;
var v2Remainder = sphere2.Velocity - v2Collide;

Now comes the physics part. An elastic collision preserves both the overall kinetic energy and overall momentum. Wikipedia has the formulae to calculate the velocities after the collision. That’s just what we are going to use. We now operate on a single dimension (the collision direction). Therefore, it is sufficient to calculate with the vector’s lengths and scale them afterwards:

//Calculate the collision
var v1Length = v1Collide.Length * Math.Sign(v1Dot);
var v2Length = v2Collide.Length * Math.Sign(v2Dot);
var commonVelocity = 2 * (sphere1.Mass * v1Length + sphere2.Mass * v2Length) / (sphere1.Mass + sphere2.Mass);
var v1LengthAfterCollision = commonVelocity - v1Length;
var v2LengthAfterCollision = commonVelocity - v2Length;
v1Collide = v1Collide * (v1LengthAfterCollision / v1Length);
v2Collide = v2Collide * (v2LengthAfterCollision / v2Length);

v1Collide and v2Collide now have the correct values that are present after the collision. All we need to do is to recombine both components to a single velocity:

//Recombine the velocity
sphere1.Velocity = v1Collide + v1Remainder;
sphere2.Velocity = v2Collide + v2Remainder;

That’s all. Well, almost. Remember we turned back the time? We have to undo that so it does not look weird.

sphere1.Position += backTime * sphere1.Velocity;
sphere2.Position += backTime * sphere2.Velocity;

That’s how to resolve a two-sphere collision. If we’re unlucky there is another collision just after the resolution which we should handle. This is a very complex task. In most cases it is sufficient to resolve the two-sphere collision and let the system handle any additional collision in the next frame.

I put the code together in a small WPF sample application. The Visual Studio 2012 solution and executable can be downloaded here. The executable needs at least .Net Framework 4.5.

Advertisements

, ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: