Thread: simplest collision detection: two fast-moving circles

Hi. Forgiving me for asking what must be a rather old question, but nevertheless: what would be the simplest method for calculating whether a collision has occurred (or perhaps, will occur) between two circles that are moving at high velocities? I'm thinking in a simple video game context, where the positions of two objects are updated every few milliseconds, and the next position is based on the previous position and the current velocity, and the "body" of each object is represented by a simple radius. Obviously it is not difficult to see if a collision is occuring at any particular point in time, by checking if the circles overlap, which would be good enough for me; however, since the objects are moving so fast, it is possible that a "leap over" scenerio might occur, in which the collosion occurs in between steps and thus is not detected. It is not good, either, to simply check if their movement vectors intersect, because then it is possible for them to pass very close to each other in what should be a collision, but is not detected. (E.g., two very close, but parallel lines of movement).

Hmmm... I figured that my problem would be child's play on a Web site with forums like "Differential Geometry", "Calculus", and "Advanced Applied Math". Apparently not. Us lesser minds will have to do our best, I guess. I'll share the approach I've been working on, hoping for a better answer:

The basic approach to this problem I have been exploring is to see the situation as a distance graph and to find some way to analyze the graph that tells me if a collision has occurred. That is, a graph where the y-axis is the distance between the center of the two circles, and the x-axis is time -- specifically, the frame of time in which I am testing for collision (likely only a few milliseconds in the video game). The solution to the question of "has a collision occurred" is the same as "does the distance graph ever dip low enough that the value is less than or equal to the sum of the radii of the circles?" But the difficult question is, how do I figure that out (efficiently).

One method is calculate lots of points on the graph, and test if any are low enough. The more points I test, the more likely my result is to be correct. A workable approach, but perhaps too CPU intensive...?

Another approach is an estimate, that should be accurate enough most of the time:

Logically, If the velocity of the two objects does not change, and we are limiting ourselves to a finite time frame, all distance graphs should fit one of four types:

1. A single straight line with a positive slope. This is the case in which the path of the two objects do not intersect (in the limited time frame) but are moving farther apart.
2. A single straight line with a negative slope. The paths do not intersect, but are moving closer together.
3. A single straight line with a zero slope. The two objects have the same velocity (i.e., direction and speed).
4. A "V" shape, in which the distance decreases steadily, but then begins to increase steadily at some point. This is either the case in which the two paths actually intersect (zero distance) or the two objects pass by each other at close proximity (heading opposite directions).

If I were to test the distance at the first instance of time and then the last distance of time, this would be a sufficient test to cover the first three graph types mention above. But what if it is a V shaped graph? Well, I could also get one point just a little bit to the right of the first point on the graph, and one point just a little bit to the left of the last point on the graph, and use these four points to calculate the slope of the two lines of the V-shape. If I then treated the distance graph itself like geometry, I could use the two slopes to calculate the intersection point of the V, which would be the bottom most point. If the bottom most point is less than or equal to the sum of the circle radii, then I have a collision. Otherwise, I don't.

The problem with this approach is the marginal cases, in which the dip in the V occurs in between the first and second point, or the third and last point, which then might give me an intersection higher than the real one. But in such marginal cases, the objects will likely be close enough that the initial point and last point tests would have detected a collision anyway. Yet, there is still a chance of a detection failure.

This would be much easier if their was someway to measure "negative distance", as is the case of two objects moving on a one-dimensional plane. (Just subtract the first point from the second, and after they pass each other, the distance will be negative.) Then I could just figure out whether or not the distance graph crosses the x-axis. But I do not know how to get a meaningful "negative distance" in a 2-D distance calculation using the pythagorean theorem.

So, that's the best I've got so far. If all that seems silly to you math geniuses, I'm certainly open to better suggestions.

The simplest way to determine whether two circles are in contact or have collided in the last time interval is to calculate the distance between their centers and see if it is less than or equal to the sumof the radii of the two circles. You can speed up the calculation a little by not taking the square root in the distance calculation and comparing it to the square of the sum of the radii, since it is a little faster to square than to take the square root.

That is, if the center of one circle is , which vary with time, with radii , a constant, and the other has center and radius . Then the circles will be in contact or have collided since the last time you checked if or, a little faster, .

Originally Posted by HallsofIvy

The simplest way to determine whether two circles are in contact or have collided in the last time interval is to calculate the distance between their centers and see if it is less than or equal to the sumof the radii of the two circles. You can speed up the calculation a little by not taking the square root in the distance calculation and comparing it to the square of the sum of the radii, since it is a little faster to square than to take the square root.

That is, if the center of one circle is , which vary with time, with radii , a constant, and the other has center and radius . Then the circles will be in contact or have collided since the last time you checked if or, a little faster, .

That certainly is the simplest approach (just checking the distance once), but doesn't it fall prey to the concern I mentioned in my original post: the "leaping" problem? Supposing, for example, we had a circle at (0, 1.0) with a radius of 0.1, and another circle at (0, 0) with a radius of 0.1. And let's say that the first circle has a velocity of (0, -1.0) and the second circle has a velocity of (0, 1.0). And let's say we can run our check once every 1 unit of time. If we check distance either at the beginning of movement, or at the end, in either case the distance calculates to 1 unit, which is greater than the sum of the radii (0.2). Thus, it appears as though no collision has occurred. However, we know (intuitively) that the paths come sufficiently close in between those two points of time to close the distance gap to less than 0.2.