I’ve been enjoying thinking about the programming questions on stackoverflow.com, but I mostly haven’t been writing answers. Partly it’s that if I’m going to invest some time and effort in writing up some commentary, I’d like it to appear under my name and on my site. But mostly it’s because my answer would usually be of the form, “well it all depends on what you’re trying to achieve and what your requirements are” and no-one wants to hear that kind of answer.
Anyway, this article is an answer to this question:
What is the best method to detect ball-to-ball collision? Do I just have an O(n²) loop that iterates over each ball and checks every other ball to see if it's radius overlaps?
Well, Simucal, it all depends on what you’re trying to achieve and what your requirements are. What kind of trade-off do you want to make between physical accuracy and speed of computation? The more accurate you want to make the physics simulation, the longer it will take to compute the collisions (and the more work it will take to program) and so the fewer objects you can simulate before running into framerate slowdown.
I’ll start out with a simple but inaccurate approach in section 2, mention briefly how to make it run fast in section 3, describe how to get more accuracy using Minokwski sums in section 4, and put the whole thing together in section 5.
I’ll write positions, motions, and velocities as vectors, so everything I write here applied to the 3-dimensional case as well as the 2-dimensional case. In three dimensions the problem is one of finding collisions between spheres rather than circles, but the maths is identical.
Pick a small time step, δt. Ideally you’d pick this to be small enough that the distance that balls can travel during this time step is small compared with their diameter, but for the examples in this article I’ll use a δt that’s much larger than that, so that the diagrams are legible.
During each time step, move each ball, then determine for each pair of balls whether they intersect. This collision detection is cheap because the balls are circular: just compare the distance between the centres of the balls with the sum of their radii: see figure 2. (Better still, compare the square of the distance between the centres of the balls with the square of the sum of their radii, to avoid taking square roots, which is moderately costly.)
This approach is very simple and can be made to run very quickly if spatial partitioning is used to make the complexity more like O(n) rather than O(n²); see section 3. However, there are three notable problems:
Balls intersect before they are detected to have collided, so they don't bounce in quite the same direction they would in reality: see figure 3. For some applications this doesn’t matter; but for applications where accurate simulation is the point (consider a snooker game) or where small deviations from expected behaviour are noticeable to the user (consider something like Super Monkey Ball) this is not acceptable.
Objects may end up intersecting at the end of the time step, and may be drawn in intersecting position, which looks bad. Also, you then need to figure what to do in the next time step with these intersecting objects. Is their velocity enough to ensure they eventually separate? If not, do they need to be nudged apart?
Objects may pass through each other without colliding.
To avoid testing every pair of balls, use a space partitioning approach like a quadtree. Divide up the world into regions, assign balls to regions, and test only pairs of balls in the same region (or, depending on your exact partitioning scheme, in neighbouring regions).
To avoid intersections, instead of moving the balls and then checking for collisions, instead check for collisions anywhere along the path taken during the time step. That is, for each pair of balls, we work out whether they will collide if they both follow straight paths for the time step.
The way to make this tractable is to consider the problem in the frame of reference of one of the balls—that is, imagine that one of the balls is stationary and the other one is moving with the difference of the two velocities. Then imagine that the moving ball is shrunk to a point (so travelling along a straight line) and the stationary ball is inflated by the radius of the moving ball. If (and only if) the line intersects the stationary inflated ball then the two original balls collide. See figure 4.
This approach, of simplifying the determination of the collision of two geometric figures by deflating one to a point and inflating the other, is quite general. The inflated figure is known as the Minkowski sum of the two original figures.
This reduces the problem of determining whether (and when) the two balls collide to the problem of determining the intersection of a line with a circle.
In figure 5 we ask whether the line from p to p + d intersects with the circle with centre q and radius r. A point on the line has general position p + td for a parameter t. Such a point is on the circle when |p + td − q| = r, that is, when
t²d.d + 2t(d.p − d.q) + p.p + q.q − 2p.q − r² = 0
This is a quadratic equation in t, and if we write:
a = d.d,
b = 2(d.p − d.q),
c = p.p + q.q − 2p.q − r²
then if b² < 4ac there are no real solutions for t (that is, the line misses the circle), otherwise the two points of intersection are at the usual quadratic solutions:
t = −b ± √(b² − 4ac) / 2a
Call these two solutions t− and t+. The original line segment intersects the circle if the interval [t−,t+] intersects the interval [0,1]. In the usual case where p is outside the circle, this reduces to the condition 0 ≤ t− ≤ 1.
Translated back to the original, non-relativized problem, the solution t− is thus the time of first collision of the two balls, in units of δt.
The approach described above completely solves the collision problem for two balls. But if we have a system with more than two objects, the possibility arises that a single object will collide more than once during our chosen time step δt. So how do we organize the motion to take this into account?
Again, we need to trade accuracy against speed. One simple approximation is to move the balls one at a time. Choose the first ball and move it along its original path until its first collision. (We can find the first collision by finding the times t− of all possible collisions, and pick the smallest of these.) If there’s any time remaining, move the ball along its new path until the second collision. And so on, until time runs out. (We probably want to have some kind of limit to the number of collisions per ball per time step to avoid the simulation grinding to a halt when there are a very large number of collisions, for example due to a ball bouncing back and forth in an enclosed space.) Then move the second ball using the same approach, and so on.
This is probably good enough if the only reason why you didn’t want to allow intersection is because it looks bad when drawn. But if you want physics that’s accurate enough for snooker then this approach isn’t good enough.
We really want to move all the balls simultaneously. We can’t do that with a computer than only does one thing at a time. But we can move all the balls so long as none of them are colliding. Which suggests the following approach.
Consider all possible collisions between the balls and find the earliest of these, at time t₁.
Move all the balls for time t₁. There can’t be any collisions in this period, because the earliest possible collision was at time t₁.
Update the velocities for the two balls that just collided.
Now consider all possible collisions between the balls in their new positions and velocities (we can avoid some of the work at this step because only the possible collisions involving the two balls whose velocities changed at step 2 can be different). Find the earliest of these collisions, at time t₂.
Move all the balls up to time t₂.
Repeat until tn > δt.
Here’s an example. Figure 6 shows three balls about to collide, with arrows indicating the planned motion for this time step.
Figure 7 shows, for each pair of balls, the time of collision of that pair.
|A and B collide at t=0.9||B and C collide at t=0.7||A and C collide at t=0.5|
So balls A and C collide first, at time t=0.5, so we can move all the balls up to this time, and compute the new velocities for balls A and C which have just collided. Figure 8 shows the new position at time t=0.5, with arrows indicating the remaining motions for this time step.
I’ve glossed over some difficulties here; we want to make sure that the algorithm terminates in a sensible amount of time, so that might mean taking approximations at some point. But this is a basic sketch of a physics engine accurate enough for a game of snooker.
An excellent reference is Real-Time Collision Detection by Christer Ericson (Morgan Kaufmann Publishers, 2005). See section 5.5.5 (pages 223–226) for a moving sphere intersection test corresponding to my section 4 (with a neat simplification of the quadratic formula), and chapter 7 (pages 285–348) for many approaches to spatial partitioning.