Don’t Cross that Line

The quadrant method is pretty efficient. However, there’s a completely different approach. An interesting feature of this problem can be found if you draw a line from the test point to a point definitely outside the polygon. Now count how many polygon edges crossed that line. If that number is odd, the point is inside the polygon. If the number of edge crossings is even, the point is on the outside. Try it out.

I saw a pretty fast way to implement this in Graphic Gems IV. This method projects a line from the hit position along the x axis. Only testing line segments that are on either side of this position lets you avoid some calculations. Segments that could cross this line require an x intercept calculation to be sure. However, this can be simplified to eliminate a divide because of the unique needs of the test. The code for this routine is in Listing 2. Whether or not this method is faster than the quadrant method depends greatly on the polygon being testing. The routines are so easy to implement that you should try both in your application if speed is a real issue.

Listing 2. The X Intercept Calculation.

// Procedure: PointInPoly (EDGE 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;
tPoint2D *pnt1,*pnt2;
BOOL inside = FALSE; // INITIAL TEST CONDITION
BOOL flag1,flag2;

edge = first = sector->edge; // SET UP INITIAL CONDITIONS
pnt1 = &m_edgelist[edge].pos;
flag1 = ( hitPos->y >= pnt1->y ) ; // IS THE FIRST VERTEX OVER OR UNDER THE LINE

/* LOOP THROUGH THE VERTICES IN A SECTOR */
do {
next = m_edgelist[edge].nextedge; // CHECK THE NEXT VERTEX
pnt2 = &m_edgelist[next].pos;
flag2 = ( hitPos->y >= pnt2->y ); // IS IT OVER OR UNDER
if (flag1 != flag2) // MAKE SURE THE EDGE ACTUALLY // CROSSES THE TEST X AXIS
{
// CALCULATE WHETHER THE SEGMENT ACTUALLY CROSSES THE X TEST AXIS
// A TRICK FROM GRAPHIC GEMS IV TO GET RID OF THE X INTERCEPT DIVIDE
if (((pnt2->y - hitPos->y) * (pnt1->x - pnt2->x) >=
(pnt2->x - hitPos->x) * (pnt1->y - pnt2->y)) == flag2 )
inside = !inside; // IF IT CROSSES TOGGLE THE INSIDE // FLAG (ODD IS IN, EVEN OUT)
}
pnt1 = pnt2; // RESET FOR NEXT STEP
edge = next;
flag1 = flag2;
} while (edge != first);
return inside;
}

Standing at Arm’s Length

The above routines are enough to let your player navigate around in a Doom-style level. You would just need to make sure that the player is always inside a sector. If the player leaves one sector and does not enter any other, a "collision" has happened. This works very well. However, using the inside polygon test for collision by itself has a drawback. The player can get very close to the wall of a sector and still be considered "inside." Logically, this works fine. However, in a 3D rendered game engine, being too close to a wall is a bad thing. Textures will look blocky, they can distort badly, and walls may clip out.

What you really want to do is keep the walls at "arm’s length" from the player. You can simply make the logical collision walls closer in than the visual walls; however, this can lead to other problems. So how do I keep the character away from the wall? Turn once again to our dear old friend, the dot product. Take a look at Figure 5.

Figure 5. Checking the distance.

What I want to know is, how far away is the test point, t, from line segment A. An easy solution would be to find the nearest point, n, to the test point on the line segment and measure the distance to it. First, I create a vector, B, from the test point, t, to vertex p1. I can dot this vector with the line segment A. This will give me the cosine of the interior angle. If this angle is 90 degrees or greater, the nearest point is the vertex itself and I’m done. But let’s say that the dot product gives me 0.7, or the cosine of about 45 degrees. I will then do the same thing on the other side. I create a vector C and dot it with the segment A. If it had returned an angle greater than or equal to 90 degrees, point p2 would be the closest and I would be done again. In this case, the dot product returns 0.75, or the cosine of about 40 degrees. Now that I have the two dot products, a linear ratio will solve the problem.

You can see the code that determines the nearest point on a line segment to an input point in Listing 3. The squared distance from t to n can be used to make sure the player cannot get too close to the wall. When I combine this with the inside-polygon tests, I have the pieces I need to create a Doom-style collision model. In these days of Quake III and Unreal, it may seem a bit retro to talk about Doom-style collision detection. However, the ability to build simple collision boundaries that you can use and modify in real-time is a very attractive feature. Rules in game development are meant to be broken. Just because these days you are displaying a world made of 3D polygons, your collision boundaries don’t have to be 3D polygons. Many of the environments we wish to interact with have boundaries that can easily be defined as 2D concave-polygonal-line-segments. Sometimes the best results can be achieved with simple solutions. If you didn’t have these routines already in your math library, add them and you will be surprised by how often you use them.

Listing 3. Finding the Nearest
Point on a Line Segment.

// Procedure: GetNearestPoint
// Purpose: Find the nearest point on a line segment
// Arguments: Two endpoints to a line segment a and b,
// and a test point c
// Returns: Sets the nearest point on the segment in nearest

void CFateView::GetNearestPoint(tPoint2D *a, tPoint2D *b,tPoint2D *c,tPoint2D *nearest)
{
/// Local Variables ///////////////////////
long dot_ta,dot_tb;

// SEE IF a IS THE NEAREST POINT - ANGLE IS OBTUSE
dot_ta = (c->x - a->x)*(b->x - a->x) + (c->y - a->y)*(b->y - a->y);
if (dot_ta <= 0) // IT IS OFF THE AVERTEX
{
nearest->x = a->x;
nearest->y = a->y;
return;
}
dot_tb = (c->x - b->x)*(a->x - b->x) + (c->y - b->y)*(a->y - b->y);
// SEE IF b IS THE NEAREST POINT - ANGLE IS OBTUSE
if (dot_tb <= 0)
{
nearest->x = b->x;
nearest->y = b->y;
return;
}
// FIND THE REAL NEAREST POINT ON THE LINE SEGMENT - BASED ON RATIO
nearest->x = a->x + ((b->x - a->x) * dot_ta)/(dot_ta + dot_tb);
nearest->y = a->y + ((b->y - a->y) * dot_ta)/(dot_ta + dot_tb);
}