Tricks of the Windows Game Programming Gurus:Vector Rasterization and 2D Transformations

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

### 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.

Figure 8.38 Using bounding circles (spheres in 3D) to detect collisions.

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).

Math To compute the distance between two points, (x1,y1) and (x2,y2), in a 2D space, use the formula d = sqrt((x1-x2)2 + (y1-y2)2). For a 3D space, just add the (z1-z2)2 term within the square root radical.

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:

Math

Taylor/Maclaurin series are mathematical tools used to approximate complex functions by summing up simpler terms based on evaluating the function at constant intervals, along with taking the function’s derivative into consideration. In general, the Maclaurin series expansion of f(x) is

    f(0) + f’(0)*x1/1! + f”(0)*x2/2! + .. + f(n)(0)*xn/n!

where `‘` means derivative and ! means factorial. For example: 3! = 3*2*1.

    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)  (( <) ?  :)

    #define MAX(a, b)  (( >) ?  :)

    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

> Note: Notice that both algorithms are approximations, so be careful if exact accuracy is needed. The 2D version has a maximum error of 3.5 percent, and the 3D version is around 8 percent.

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 1002 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.

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.