Polygon Collision

From GPWiki
Jump to: navigation, search

In order to prevent embarrassing situations where game objects move right through each other without even noticing, a lot of games utilize some kind of collision detection system. Often objects are approximated as a circle or ball, or a rectangular axis-aligned box to make it easier to decide whether they are colliding. This is typically insufficient, and in the case of 2d sprites a better approximation would be obtained by comparing individual pixels with each other - if both have a non-transparent pixel at the same location, they are intersecting and something has to be done. This method can quickly become computationally expensive for high-resolution sprites. In two dimensions there is another way to describe shapes: polygons. Testing for intersection on two convex polygons is relatively fast, and the shapes of most objects can be approximated quite well with one or more simple convex polygons.

Separating Axis

To be able to decide whether two convex polygons are intersecting (touching each other) we can use the Separating Axis Theorem. Essentially:

  • If two convex polygons are not intersecting, there exists a line that passes between them.
  • Such a line only exists if one of the sides of one of the polygons forms such a line.

The first statement is easy. Since the polygons are both convex, you'll be able to draw a line with one polygon on one side and the other polygon on the other side unless they are intersecting. The second is slightly less intuitive. Look at figure 1. Unless the closest sided of the polygons are parallel to each other, the point where they get closest to each other is the point where a corner of one polygon gets closest to a side of the other polygon. This side will then form a separating axis between the polygons. If the sides are parallel, they both are separating axes.

Collision dividing.png

Figure 1: Dividing axis

So how does this concretely help us decide whether polygon A and B intersect? Well, we just go over each side of each polygon and check whether it forms a separating axis. To do this we'll be using some basic vector math to squash all the points of both polygons onto a line that is perpendicular to the potential separating line (see figure 2). Now the whole problem is conveniently 1-dimensional. We can determine a region in which the points for each polygon lie, and this line is a separating axis if these regions do not overlap.

Collison projection.png

Figure 2: Projecting polygons onto a line

If, after checking each line from both polygons, no separating axis was found, it has been proven that the polygons intersect and something has to be done about it.

Details

To implement this method of collision checking, you will need to find both the potential separating axes and the lines perpendicular to them, then project points onto those lines. After that you will need to figure out if the regions spanned by these points overlap.

For the purpose of this article, we can treat lines as directions. They always start at (0, 0), and we use an (x, y) vector to indicate in what direction they are going. If our polygons are a list of points, with lines between adjacent points, the n-th line of the polygon is just p_{n+1} - p_n. Getting a line perpendicular to line (x, y) is simple: you can just take line (-y, x).

So now we have a line on which all the points should be projected. The method for projecting a point onto a line is the dot product. If we first normalize our line (give it length 1), then the dot product between the line and a point will be the projection of that point into the 1-dimensional space of the line. So we do this to all points, resulting in a collection of 1-dimensional values for both polygons. To get the area taken up by one polygon, you take the minimum and maximum values of the projections for that polygon. If the polygons do not overlap, either the minimum value for polygon A is bigger than the maximum value for polygon B, or the maximum value for A is smaller than the minimum value for B. Do this check for every line in both polygons, until you find an axis that separates them. If no such axis can be found, they intersect.

Cutting corners

Doing this the hard way is still rather computationally expensive if you have to do it for a large number of polygons. Fortunately, there are some tricks to make it faster.

  • Start with a circle-circle intersection test. Store the center and maximum radius of every polygon, and before you check whether the polygons intersect, you do a quick check for the circles. If the circles do not intersect, the polygons won't either.
  • If you store your polygon corners in a fixed order (clockwise or counter-clockwise), you can compute your projection lines so that they are always facing away from the polygon whose edge you are checking. This allows for some nice tricks. If the line is pointing away from the other polygon (the dot product of the line and the line from this polygon to the other is negative), the edge is on the wrong side of the polygon (facing away from the other polygon) and can not be the separating axis we are searching for. Furthermore, you only have to compare the minimal projected value of the other polygon with the projected value of one of the corners of the current edge. The corners of the edge are automatically the points closest to the other polygon along this line, and since you know the line is pointing from this polygon to the other, the minimum of of this polygon is guaranteed to be smaller than the maximum of the other polygon.
  • If you just want to know whether polygons intersect, it is not necessary to normalize the projection line. If a line has a length that is not 1 and you project onto it with the dot product, all values will be scaled by the line's length. This is not a problem in this case - if X < Y, then X * scale < Y * scale.

Simple Nonconvex Polygons

If you have nonconvex, but still simple polygons, an acceptable method is to iterate over all vertices and perform the Point-in-polygon test[1]. The advantage of this method is that you can compute the exact intersection point and collision normal that you will need to simulate collision. When you have the point that lies inside the other polygon, you just iterate over all edges of the second polygon again and look for edge intersections. Note that this method detects collsion when it already happens. This algorithm is fast enough to perform it hundreds of times per sec.

edge intersection test (assuming Vector2D is a struct carrying the coordinates):

 double determinant(Vector2D vec1, Vector2D vec2){
     return vec1.x * vec2.y - vec1.y * vec2.x;
 }
 
 //one edge is a-b, the other is c-d
 Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){
     double det = determinant(b - a, c - d);
     double t   = determinant(c - a, c - d) / det;
     double u   = determinant(b - a, c - a) / det;
     if ((t < 0) || (u < 0) || (t > 1) || (u > 1)) {
         return NO_INTERSECTION;
     } else {
         return a * (1 - t) + t * b;
     }
 }

Collision Prediction

It is often nice to know two objects are going to collide, before they are actually intersecting. This can be done with pretty much the same method. You calculate the relative speed of the two objects, and after you project both polygons onto a line, you also project this speed onto that line. If they are not intersecting yet, and they are moving towards each other, they will collide (on that axis) in d / s seconds, where d is the distance between the projections of the objects, and s is the projection of the relative speed (in units per second). The axis for which this time is the smallest belongs to the edge against which the collision will actually take place. This can also be used to determine the normal of the collision (the normal of the edge), which can be useful in collision response.