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.
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.
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.
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 "arms 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.