Collision Detection with Polygons

Thank Zeus that we're through all that material. I've about had it with rasterizing and transforming polygons! Let's take a bit of a break and talk about some game-related topics, such as collision detection and how to make such determinations with polygon objects. With that in mind, I'm going to show you three different ways to look at the problem. By using these techniques (or hybrids thereof), you should be able to handle all your polygon collision-detection needs.

Proximity AKA Bounding Sphere/Circle

The first method of testing two polygons for collision is to simply assume that the objects have an average radius and then test if the radii overlap. This can be accomplished with a simple distance calculation, as shown in Figure 8.38.

Of course, you're putting circular bounding boxes around each polygon. When tested by the preceding method, this results in collisions when there are none, as well as missed collisions (depending on how the average radius is computed).

To implement the algorithm, first you must compute a radius value for each polygon. This can be done in a number of ways. You might take the distance from the center of the polygon to each vertex and then average the radius values of each, use the largest value, or some other heuristic. I usually like to use a value that's midway between the average and the farthest vertex. In any case, this computation can be done out of the game loop, so there are no worries about CPU cycles. However, the actual test during runtime is a problem.

Given that you have two polygons—poly1, located at (x1,y1), and poly2, located at (x2,y2), with radius r1 and r2, respectively (calculated in whatever way)—to test if the polygon's radii are overlapping, you can use the following pseudo-code:

// compute the distance between the center of each polygon
dist = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));

// test the distance
if (dist <= (r1+r2)
    {
     // collision!
    } // end if

This works just as you'd expect, but there's one problem…it's freakin' slow! The square root function takes about a month in CPU cycles, so you know you need to get rid of that. But let's start with the simpler optimizations just to warm up. First, there's no need to compute the difference twice, (x1-x2) and (y1-y2). You can compute it once and then use the result in the computation, like this:

float dx = (x1-x2);
float dy = (y1-y2);

dist = sqrt(dx*dx + dy*dy);

That helps a bit, but the sqrt() function takes about 70 times longer than a floating-point multiply. That is, an FMUL takes about 1-3 cycles on a standard Pentium, and the FSQRT takes about 70 cycles. In either case, it's unacceptable. Let's see what you can do. One trick is to compute the distance using a mathematical trick based on a Taylor/Maclaurin series expansion.

After working through the math, you can write a function that approximates the distance between two points, p1 and p2, in 2D space (or 3D) with only a few tests and additions. Here are algorithms for both the 2D and 3D cases:

// used to compute the min and max of two expressions
#define MIN(a, b)   ((a < b) ? a : b)
#define MAX(a, b)   ((a > b) ? a : b)

#define SWAP(a,b,t) {t=a; a=b; b=t;}

int Fast_Distance_2D(int x, int y)
{
// this function computes the distance from 0,0 to x,y with 3.5% error

// first compute the absolute value of x,y
x = abs(x);
y = abs(y);

// compute the minimum of x,y
int mn = MIN(x,y);

// return the distance
return(x+y-(mn>>1)-(mn>>2)+(mn>>4));

} // end Fast_Distance_2D

/////////////////////////////////////////////////////////////////////////

float Fast_Distance_3D(float fx, float fy, float fz)
{
// this function computes the distance from the origin to x,y,z

int temp;  // used for swaping
int x,y,z; // used for algorithm

// make sure values are all positive
x = fabs(fx) * 1024;
y = fabs(fy) * 1024;
z = fabs(fz) * 1024;

// sort values
if (y < x) SWAP(x,y,temp);
if (z < y) SWAP(y,z,temp);
if (y < x) SWAP(x,y,temp);

int dist = (z + 11*(y >> 5) + (x >> 2) );

// compute distance with 8% error
return((float)(dist >> 10));

} // end Fast_Distance_3D

The parameters to each function are simply the deltas. For example, to use Fast_Distance_2D() in the context of your previous algorithm, you would do the following:

dist = Fast_Distance_2D(x1-x2, y1-y2);

This new technique, based on the function call, uses only three shifts, four additions, a few compares, and a couple of absolute values—much faster!

One last thing… Astute readers may notice that there's yet another optimization to take advantage of—and that's not finding the square root at all! Here's what I mean: Let's say that you want to detect if one object is within 100 units of another. You know that the distance is dist = sqrt(x*x + y*y), but if you were to square both sides of the equation, you'd get

dist2 = (x*x + y*y)

And dist in this case was 100, so 100² is 10,000. Thus, if you test the RHS and it's < 10,000, that's equivalent to testing if it's < 100 if you take the square root! Cool, huh? The only problem with this technique is overflowing, but there is no reason whatsoever to compute the actual distance. Just do all your comparisons in terms of the square of the distance.

Bounding Box

Although the mathematics of the bounding sphere/circle algorithm are very straightforward, the obvious problem in your case is that the object (polygon) is being approximated with a circular object. This may or may not be appropriate. For example, take a look at Figure 8.39. It depicts a polygonal object that has general rectangular geometry. Approximating this object with a bounding sphere would induce a lot of errors, so it's better to use a geometrical entity that's more like the object itself. In these cases, you can use a bounding box (square or rectangle) to make the collision detection easier.

Creating a bounding rectangle for a polygon is done in the same manner as for a bounding sphere, except that you must find four edges rather than a radius. I usually like to call them (max_x, min_x, max_y, min_y) and they're relative to the center of the polygon. Figure 8.40 shows the setup graphically.

To find the values for (max_x, min_x, max_y, min_y), you can use the following simple algorithm:

And here's the algorithm coded to work for your standard POLYGON2D structure:

int Find_Bounding_Box_Poly2D(POLYGON2D_PTR poly,
                             float &min_x, float &max_x,
                             float &min_y, float &max_y)
{
// this function finds the bounding box of a 2D polygon
// and returns the values in the sent vars

// is this poly valid?
if (poly->num_verts == 0)
    return(0);

// initialize output vars (note they are pointers)
// also note that the algorithm assumes local coordinates
// that is, the poly verts are relative to 0,0
max_x = max_y = min_x = min_y = 0;

// process each vertex
for (int index=0; index < poly->num_verts; index++)
    {
    // update vars – run min/max seek
    if (poly->vlist[index].x > max_x)
       max_x = poly->vlist[index].x;

    if (poly->vlist[index].x < min_x)
       min_x = poly->vlist[index].x;

    if (poly->vlist[index].y > max_y)
       max_y = poly->vlist[index].y;

    if (poly->vlist[index].y < min_y)
       min_y = poly->vlist[index].y;

} // end for index

// return success
return(1);

} // end Find_Bounding_Box_Poly2D

You would call the function like this:

POLYGON2D poly; // assume this is initialized

float min_x, min_y, max_x, max_y; // used to hold results
// make call
Find_Bounding_Box_Poly2D(&poly, min_x, max_x, min_y, max_y);

After the call, the min/max rectangle will be built and stored in (min_x, max_x, min_y, max_y). With these values, along with the position of the polygon (x0,y0), you can then perform a bounding box collision test by testing two different bounding boxes against each other. Of course, you can accomplish this in a number of ways, including by testing if any of the four corner points of one box are contained within the other box, or by using more clever techniques.

Point Containment

In light of my last statement about testing if a point is contained within a rectangle, I thought it might be a good idea to show you how to figure out if a point is contained within a general convex polygon. What do you think? Obviously, figuring out if a point is within a rectangle is no more than the following:

Given rectangle (x1,y1) to (x2,y2) and that you want to test (x0,y0) for containment:

if (x0 >= x1 && x0 <= x2) // x-axis containment
   if (y0 >= y1 && y0 <= y2) // y-axis containment
      { /* point is contained */ }

Let's see if you can figure out if a point is contained within a convex polygon, as shown in Figure 8.41. At first, you might think that it's an easy problem, but I assure you that it's not. There are a number of ways to approach the problem, but one of the most straightforward is the half-space test. Basically, if the polygon you're testing is convex (which it is in this case), you can think of each side as a segment that is colinear with an infinite plane. Each plane divides space into two half-spaces, as shown in Figure 8.42.

If the point you're testing is on the interior side of each half-space, the point must be within the polygon because of the convex property of the polygon. Thus, all you need to do is figure out a way to test if a point in a 2D space is on one side of a line or the other.

This isn't too bad, assuming that you label the lines in some order and convert them to vectors. Then you'll think of each of the line segments as a plane. Using the dot product operator, you can determine if a point is on either side of each plane or on the plane itself. This is the basis of the algorithm.

You may not be up to speed on vectors, dot products, and so on, so I'm going to hold off for this test and the accompanying algorithm until we cover 3D math—no need to confuse you here. However, I wanted you to at least understand the geometry of the solution. The details are just math, and any high-level organic or inorganic organism can perform math if taught properly…right?