Resolving a Circle-Circle Collision

Question

I am writing software that extends Circle-Rectangle collision detection (intersection) to include responses to the collision. Circle-edge and circle-rectangle are rather straight-forward. But circle-circle has me stumped.

For example, let two circles collide, one red and one green, in a discrete event simulation. We might have the following situation:

Immediately after they collide we could have:

Here RIP and GIP were the locations of the circles at the previous clock tick. At the current clock tick, the collision is detected at RDP and GDP. However, the collision occurred between clock ticks when the two circles were at RCP and GCP. At the clock tick, the red circle moves RVy downward and RVx rightward; the green circle moves GVy downward and GVx leftward. RVy does not equal GVy; nor does RVx equal GVx.

The collision occurs when the distance between the circle centers is less than or equal to the sum of the circles' radii, that is, in the preceding figure, d <= ( Rr + Gr ). At a collision where d < ( Rr + Gr ), we need to position the DPs back to the CPs before adjusting the circles' velocity components. In the case of d == ( Rr + Gr ), no repositioning is required since the DPs are at the CPs.

This then is the problem: how do I make the move back to the CPs. Some authors have suggested that one-half of the penetration, given by p in the following figure, be applied.

To me that is just plain wrong. It assumes that the velocity vectors of the two circles are equal that, in this example, is not the case. I think penetration has something to do with the computation but how eludes me. I do know that the problem can be recast as a problem of right similar triangles in which we want to solve for Gcdy and GCdx.

The collision itself will be modeled as elastic, and the math for the exchange of inertia is already in place. The only issue is where to position the circles at collision.

Answer 1

"This then is the problem: how do I make the move."

It is likely that you want to know how "to position the DPs back to the CPs before adjusting the circles' velocity components."

So there are two issues, how to determine the CPs (where the collision occurs) and how to adjust the circles' motion going forward from that point. The first part has a rather easy solution (allowing for different radii and velocity components), but the second part depends on whether an elastic or inelastic response is modelled. In a Comment you write:

The collision will be modeled as elastic. The math for the exchange of inertia is already in place. The problem is where to position the circles.

Given that I'm going to address only the first issue, solving for the exact position where the collision occurs. Assuming uniform motion of both circles, it is sufficient to know the exact time at which collision occurs, i.e. when does the distance between the circles' centers equal the sum of their radii.

With uniform motion one can treat one circle (red) as motionless by subtracting its velocity from that of the other circle (green). In effect we treat the center of the first circle as fixed and consider only the second circle to be in (uniform) motion.

Now the exact time of collision is found by solving a quadratic equation. Let V = (GVx-RVx, GVy-RVy) be the relative motion of the circles, and let P = (GIPx-RIPx,GIPy-RIPy) their relative positions in the "instant" prior to collision. We "animate" a linear path for the relative position P by defining:

P(t) = P + t*V

and ask when this straight line intersects the circle around the origin of radius Rr+Gr, or when does:

(Px + t*Vx)^2 + (Py + t*Vy)^2 = (Rr + Gr)^2

This is a quadratic equation in unknown time t, all other quantities involved being known. The circumstances are such that (with collision occurring at or before position CP) a positive real solution will exist (typically two solutions, one before CP and one after, but possibly a grazing contact giving a "double root"). The solution (root) t you want is the earlier one, the one where t (which is zero at "instant" RIP,GIP positions) is smaller.

Answer 2

If you're looking for a basic reference on inelastic collisions for circular objects, Pool Hall Lessons: Fast, Accurate Collision Detection Between Circles or Spheres by Joe van den Heuvel and Miles Jackson is very easy to follow.

From least formal to most formal, here are some follow up references on the craft of implementing the programming that underpins the solution to your question (collision responses).

• Brian Beckman & Charles Torre The Physics in Games - Real-Time Simulation Explained
• Chris Hecker, Physics, Part 3: Collision Response, Game Developer 1997
• David Baraff, Physically Based Modeling: Principles and Practice, Online Siggraph '97 Course notes, of particular relevance are the Slides for rigid body simulations.

You're going to have to accept some approximations - Beckman demonstrates in the video that even for very simple cases, it isn't possible to analytically predict what would occur, this is even worse because you are simulating a continuous system with discrete steps.

Answer 3

To re-position the two overlapping circles with constant velocities, all you need to do is find the time at which the collision occurred, and add that factor of their velocities to their positions.

First, instead of two circles moving, we will consider one circle with combined radius and relative position and velocity. Let the input circles have positions P1 and P2, velocities V1 and V2, and radii r1 and r2. Let the combined circle have position P = P2 - P1, velocity V = V2 - V1, and radius r = r1 + r2.

We have to find the time at which the circle crosses the origin, in other words find the value of t for which r = |P + tV|. There should be 0, 1, or 2 values depending on whether the circle does not pass through the origin, flies tangent to it, or flies through it.

r^2 = ||P + tV|| by squaring both sides.

r^2 = (P + tV)*(P + tV) = t^2 V*V + 2tP*V + P*P using the fact that the L2-norm is equivalent to the dot product of a vector with itself, and then distributing the dot product.

t^2 V*V + 2tP*V + P*P - r^2 = 0 turning it into a quadratic equation.

If there are no solutions, then the discriminant b^2 - 4ac will be negative. If it is zero or positive, then we are interested in the first solution so we will subtract the discriminant.

a = V*V
b = 2 P*V
c = P*P - r^2
t = (-b - sqrt(b^2 - 4ac)) / (2a)

So t is the time of the collision.

Answer 4

You can actually derive an expression for the time required to reach a collision, given initial positions and velocity vectors.

Call your objects A and B, and say they have position vectors a and b and velocity vectors u and v, respectively. Let's say that A moves at a rate of u units per timestep (so, at time = t, A is at a; at time = t + 1, A is at a + u).

I'm not sure whether you want to see the derivation; it wouldn't look so great... my knowledge of LaTeX is pretty limited. (If you do want me to, I could edit it in later). For now, though, here's what I've got, using generic C#-ish syntax, with a Vector2 type that is declared Vector2(X, Y) and has functions for vector addition, scalar multiplication, dot product, and length.

double timeToCollision(Vector2 a, Vector2 b, Vector2 u, Vector2 v)
{
    // w is the vector connecting their centers;
    // z is normal to w and equal in length.
    Vector2 w = b - a;
    Vector2 z = new Vector2(-1 * w.Y, w.X);
    Vector2 s = u - v;
    // Dot() represents the dot product.
    double m = Dot(z, s) / Dot(w, s);

    double t = w.Length() / Dot(w, s) * 
              (w.Length() - sqrt( ((2 * r) ^ 2) * (1 + m ^ 2) - (m * w.Length()) ^ 2) ) / 
              (1 + m * m)

    return t;
}

As for responding to collisions: if you can fast-forward to the point of impact, you don't have to worry about dealing with the intersecting circles.

If you're interested, this expression gives some cool results when there won't be a collision. If the two objects are moving away from each other, but would have collided had their velocities been reversed, you'll get a negative value for t. If the objects are on paths that aren't parallel, but will never meet (passing by each other), you'll get a negative value inside the square root. Discarding the square root term, you'll get the time when they're the closest to each other. And if they're moving in parallel at the same speed, you'll get zero in the denominator and an undefined value for t.

Well, hopefully this was helpful! I happened to have the same problem as you and decided to see whether I could work it out on paper.

Edit: I should have read the previous responses more carefully before posting this... the mess of a formula above is indeed the solution to the quadratic equation that hardmath described. Apologies for the redundant post.