Features

Crashing into the New Year:
Collision Detection

The last several years have moved at an incredible pace. It was a year with amazing advances in the visual quality of games. The predictions that 3D hardware would become a major force in the industry have come true.

Consumers can now buy cards for under $100 that deliver 3D graphics performance that would have cost thousands only a few years ago. This added processing power leaves game developers more and more time to dedicate to exploring other areas in computer simulation.

I’m continually amazed that learning a simple trick or technique can open the door to so many different effects and applications. In this article, I’m going to investigate the problem of collision detection. Collision detection is a huge issue in graphics simulation. In fact, it’s an active area of research, so SIGGRAPH and professional journals are a great source of information.

Let me start off by looking at some common problems that can be important to a variety of game applications. These routines, though fairly simple, are very handy to have in your library. The first issue is how to determine whether a point is inside an arbitrary area. Detecting whether a point is inside a convex polygon can be determined very easily. Figure 1 shows a point inside a simple four-sided polygon. Our first step is to create perpendicular vectors for each of the polygon edges and a vector from the test point to the first vertex of each edge. The perpendicular of a 2D vector can be created by simply creating the vector, swap the X and Y components, and then negate the X. As you may recall from previous columns, the dot product of two vectors defines the cosine of the angle between those vectors. If the dot product for each of the edges is positive, all the angles are less than 90 degrees and the point is inside the polygon. This is exactly analogous to a 2D version of backface culling for 3D polygons.

Figure 1. Inside a convex polygon.

That rule is pretty useful for some things. However, it only works when the boundary that you’re checking is convex. Many spaces that we’re interested in are actually concave (Figure 2).

Figure 2. Inside a concave polygon.

This polygon looks like a character in a Duke Nukem level. And in fact, Duke is a pretty good application for this kind of test. Each "sector" of a Duke level is a polygonal boundary defining a region with a specific floor and ceiling height. Knowing whether I’m inside or outside of a particular sector is important information. Unfortunately, the aforementioned dot product test won’t work on these concave polygons. I could divide this region into smaller convex polygons, but that wouldn’t be very efficient. Luckily, this problem is the classic "point in polygon" test that’s commonly described in computational geometry books. There are many approaches to solving this problem, but I want to look at just two of them.

Here We Go Round the Vertex List

One method for determining if the test point is inside the concave polygon comes from the idea that a circle is 360 degrees. Calculate the angle between each vertex and the test point (at the test point itself) and then add up all the angles. If the total is equal to 360, then you are inside. You can see what this looks like in Figure 3.

Figure 3. Angles around the test point.

This actually works very well, however, it is not very efficient. Calculating each angle requires a dot product and an arccosine operation. Those will add up quickly.

A better strategy is to divide the polygon into quadrants centered on the test point, as in Figure 4. Start at the first vertex in the polygon and set a counter to 0. Anytime an edge crosses from one quadrant to the next, add one to the counter if it crosses clockwise around the test point and subtract one if it crosses counter-clockwise. If the edge crosses diagonally across two quadrants, you need to determine which side of the test point it crossed, and then either add or subtract 2. Try it yourself on Figure 4. Start at vertex 1. Add 1 when edge 3-4 crosses from quadrant I to II, and subtract it again with edge 4-5. When you reach the last edge (11-1), you should have 4. When using the routine, if the counter is equal to 4 or –4, the test point is inside the polygon. You can see the code for this routine in Listing 1.

Figure 4. Dividing the polygon into quadrants.

________________________________________________________

Don't Cross That Line

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service