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.

Listing 1. The Quadrant Approach
to the Bounding Box Test

// FIGURE OUT WHICH QUADRANT THE VERTEX IS RELATIVE TO
// THE HIT POINT

#define WHICH_QUAD(vertex,hitPos) \
( (vertex.x > hitPos->x) ? ((vertex.y > hitPos->y)
? 1 : 4) :( (vertex.y > hitPos->y) ? 2 : 3) )

// GET THE X INTERCEPT OF THE LINE FROM THE CURRENT VERTEX TO
// THE NEXT

#define X_INTERCEPT(point1, point2, hitY) \
(point2.x - ( ((point2.y - hitY) * (point1.x - point2.x))
/ (point1.y - point2.y) ) )

/////////////////////////////////////////////////////////////
// Procedure: PointInPoly (SUM OF ANGLES CROSSING VERSION)
// Purpose: Check if a point is inside a polygon
// Returns: TRUE if Point is inside polygon, else FALSE
/////////////////////////////////////////////////////////////

BOOL CFateView::PointInPoly(tSector *sector, tPoint2D *hitPos)
{

/// Local Variables /////////////////////////////////////////
short edge, first, next;
short quad, next_quad, delta, total;

/////////////////////////////////////////////////////////////
edge = first = sector->edge;
quad = WHICH_QUAD(m_edgelist[edge].pos, hitPos);
total = 0; // COUNT OF ABSOLUTE SECTORS CROSSED
/* LOOP THROUGH THE VERTICES IN A SECTOR */
do {
next = m_edgelist[edge].nextedge;
next_quad = WHICH_QUAD(m_edgelist[next].pos, hitPos);
delta = next_quad - quad; // HOW MANY QUADS HAVE I MOVED

// SPECIAL CASES TO HANDLE CROSSINGS OF MORE THEN ONE
//QUAD

switch (delta) {
case 2: // IF WE CROSSED THE MIDDLE, FIGURE OUT IF IT
//WAS CLOCKWISE OR COUNTER
case -2: // US THE X POSITION AT THE HIT POINT TO
// DETERMINE WHICH WAY AROUND
if (X_INTERCEPT(m_edgelist[edge].pos,
m_edgelist[next].pos, hitPos->y) > hitPos->x)
delta = - (delta);
break;
case 3: // MOVING 3 QUADS IS LIKE MOVING BACK 1
delta = -1;
break;
case -3: // MOVING BACK 3 IS LIKE MOVING FORWARD 1
delta = 1;
break;
}
/* ADD IN THE DELTA */
total += delta;
quad = next_quad; // RESET FOR NEXT STEP
edge = next;
} while (edge != first);

/* AFTER ALL IS DONE IF THE TOTAL IS 4 THEN WE ARE INSIDE */
if ((total == +4) || (total == -4)) return TRUE; else return FALSE;
}

Figure 4. Dividing the polygon into quadrants.