C:Collision detection between two circles

From GPWiki
Jump to: navigation, search

One of the most common methods of collision detection is the radius hit test which is used to see if two circles intersect. The routines to perform the check are fairly quick, and often more computationally expensive checks (such as between convex polygons) benefit by performing the radius hit test first.

The idea is that if two circles intersect, the distance between the centers is less than or equal to the sum of the circles' radii. The distance can be computed using the Pythagorean Theorem.

Getting started

There are usually three possible scenarios to consider in checking whether two circles intersect. The first scenario is obvious: no collision is occurring. In this case, the circles are too far apart to collide. There would be no reason to do any further collision detection at this point. The second scenario is when the circles are just touching with no overlap. In the often-cited Billiards example, this would be the ideal moment since two of the balls cannot share the same place at the same time. The third scenario, if it is to be considered, is when the circles do overlap. This is typically important if the radius hit test is being used before some other algorithm.

If you are using C++, then one way to flag these scenarios is with an enumeration. The one used for this tutorial looks much like the following:

enum CollisionResults { NO_COLLISION, TOUCHING, OVERLAPPING };

In many cases touching and overlapping can be considered synonymous, but knowing the difference may be useful. Consider a Tetris™ clone where several blocks are being tracked at one time. The engine expects two tetrominoes to fit snugly together without any overlap at all. In fact, an overlap may signal a failure in the engine to properly handle the collision. On the other hand, a bullet colliding with a target can probably be treated the same way whether it is touching or whether it is overlapping.

To find out if two circles overlap, we'll need to know a couple things about them. Specifically, we need to know the coordinates of the centers of the circles and the radius of each circle. Then, the distance between them is computed. We will also add the radii of the circles together and compare the result with the distance. The comparison will show if the circles are intersecting in any way.

Three variables are needed per circle, but a simple structure would make things easier to read:

struct Circle { double x, y, radius; };

This structure uses double-precision variables rather than single-precision variables because modern 64-bit processors perform most calculations in double. Your implementation may benefit slightly from using single precision especially if the rest of the app already uses singles or the target platform is 32-bit, but the choice is yours to make.

Since we can never guarantee that 0.00000000000001 and 0.0000000000001 are not treated equally due to the way floats are stored, we will be making a delta-epsilon comparison. This simple check takes the difference of two numbers, called the delta, to see if it is smaller than a third number, called the epsilon. It looks very similar to this "neighborhood" check:

-\epsilon < a - b < \epsilon\,

In this case, we will call our epsilon TOUCH_DISTANCE and set it to a very tight number:

const double TOUCH_DISTANCE = 0.00000000000001;

The TOUCH_DISTANCE chosen has thirteen zeroes after the decimal point. This is how close two objects will need to be in order to be considered "touching". This number is insanely precise, as even at 1000 frames per second distances on the order of 0.001 units would usually be the smallest. Indeed, even using our squaring trick below the smallest value expected (at 1000 fps) is 0.00001. You should pick a reasonable precision for your game that strives to be unforgiving. That said, calculating distance is easy:

Figure 1

The distance between two points can be computed using the Pythagorean Theorem. This formula, a^2 + b^2 = c^2, is commonly used to find the length of the hypotenuse of a triangle when the sides are known. Figure 1 shows an example of how this theorem might be applied to two circles.

Considering the Circle structure introduced above, it becomes obvious that points P and Q would be the known coordinates. Both lines A and B are known as long as P and Q are known, so the the unknown is line C. The length of line C is the distance between the circles. Point R is not important in this case because it provides no extra information.

Mathematically, the distance is described as:

C = \sqrt{(P_x - Q_x)^2 + (P_y - Q_y)^2}

However, before implementing this formula it deserves mention that the square root function is slow. Several methods are commonly used to determine square roots, some going so far as to use a look-up table with others using essentially a sequence of guesses. Take a look at this page for an interesting read on this problem.

If you are going to use the distance formula provided above, don't bother taking the square root at the end. Instead, square the value you are comparing to. Multiplication will always be faster than determining (read: guessing) a square root. Likewise, there is very little appeal to a CPU iterating over a table of values. So, keep the formula looking like this:

C^2 = (P_x - Q_x)^2 + (P_y - Q_y)^2\,

Now, knowing C^2, we will need a value to compare it too. This value is computed by adding the radii of the circles together. Since we are keeping the distance in its squared state, we will need to square the total radius as well. The comparable looks like this:

D^2 = (P_r + Q_r)^2\,

That's about it! Comparing the values of C^2 and D^2 with our TOUCH_DISTANCE tells us whether the circles touch, overlap, or neither.

Example

Consider figure 1 above. The two circles are obviously not overlapping and they are too far apart to touch. There is no collision, but proving this mathematically is a another story. We will assign some values to points P and Q as follows:

Circle p; Circle q;

p.x = 30.0; p.y = 20.0; p.radius = 37.0; q.x = 180.0; q.y = 145.0; q.radius = 50.0;

At this point, an implementation could check P_r + Q_r < \max(|P_x - Q_x|, |P_y - Q_y|) as an early out from the multiplication operations to follow. However, this has the overhead of calling three functions as well as some obscurity as to how absolute values are calculated. Furthermore, if the test actually does fail the rest of the calculations need to be performed anyway. This trick would be beneficial to rectangles, but probably not circles.

With the numbers plugged into our circles, we will use the squared distance formula above with our P(x,y) and Q(x,y) values:

double distance_squared = ((p.x - q.x) * (p.x - q.x)) + ((p.y - q.y) * (p.y - q.y));

Once again, the temptation to use a function creeps in. In this case, the pow(b,e) function could be used to bypass a subtraction operation and thereby improve readability. However, this would again incur the overhead of calling the function as well as raise questions on how the compiler has implemented it. It is best to just multiply it out yourself.

Finally, we calculate the sum of the radii of the circles and then square it, again staying away from using function calls for the work:

double radii_squared = (p.radius + q.radius) * (p.radius + q.radius);

Whether or not the circles are colliding is now a question of which of these two results, distance_squared or radii_squared is larger than the other. If distance_squared is larger, there is no collision. If the values are the same, the circles are touching. If radii_squared is larger, the circles are overlapping. A simple comparison is all that is needed:

if ( -TOUCH_DISTANCE < radii_squared - distance_squared && radii_squared - distance_squared < TOUCH_DISTANCE) { // ... touching } else if (radii_squared > distance_squared) { // ... overlapping } else { // ... no collision }

Take a close look at the first comparison being made. It would be much easier to check if radii_squared == distance_squared but that cannot be relied on. If this test is called just a microsecond before true collision and then a few ticks after, the actual moment may be missed solely due to a rounding error. In extreme cases, the differences between radii_squared and distance_squared could be small enough to mean a collision on a quad-core Athlon CPU and a miss on a Slot-style PIII.

Note that every time the circles change position, the hit test would need to be recomputed. This is an example of point-in-time collision detection, the simplest to implement flavor. A more advanced algorithm would use something called predicted instance to determine when the objects are expected to collide. No further checking would occur unless the direction of travel changes or the collision time has been reached.

From this example, if a collision has occurred then further testing can be performed on the nature of the collision. If not, then cpu time is conserved and the frame rate takes less of a hit. A fully working C++ example follows.

Full code listing

const double TOUCH_DISTANCE = 0.00000000000001;

enum CollisionResults { NO_COLLISION, TOUCHING, OVERLAPPING };

struct Circle { double x,y; double radius; };

int main( void ) { // These two are all that are needed to start a collision test Circle big_object; Circle small_object;

big_object.x = 100.0; big_object.y = 50.0; big_object.radius = 40.0;

small_object.x = 50.0; small_object.y = 50.0; small_object.radius = 10.0;

// These next variables are for the math work and results CollisionResults colliding; double distance_squared; double radii_squared;

// Note this is just: a² + b² = c² distance_squared = ((big_object.x - small_object.x) * (big_object.x - small_object.x)) + ((big_object.y - small_object.y) * (big_object.y - small_object.y));

// Multiplication is faster than taking a square root radii_squared = (big_object.radius + small_object.radius) * (big_object.radius + small_object.radius);

if ( -TOUCH_DISTANCE < radii_squared - distance_squared && radii_squared - distance_squared < TOUCH_DISTANCE) colliding = TOUCHING; else if (radii_squared > distance_squared) colliding = OVERLAPPING; else colliding = NO_COLLISION;

return colliding; }

Summary

Collision detection using the radius hit test is often cited on the web for good reason; it is simple to implement with accurate results. It can be called several times in a row with cached values to perform a fake capsule test (sometimes called a sweeping circle). The final result can lead into a more complex detection algorithm, and in some cases the final result is all that is necessary to react accordingly.

This tutorial does not cover timing in any way, and therefore does not cover important stuff like velocity, overshooting, and pre-detection. These more advanced topics are usually what developers are looking for. However, a good introduction to hit testing is outlined here. It would take minimal work to turn this into a predicted instance algorithm, and detecting overlap is as easy as calling the method twice; once for the old position and once for the new position.