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 foursided 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 counterclockwise. 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 34 crosses from quadrant I to II,
and subtract it again with edge 45. When you reach the last edge (111),
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.
