How to find out if two convex polygons are colliding
I'm in the middle of implementing some two-dimensional collision logic, and I thought I'd share how it works.
The solution is based on the separating axis theorem, which for this purpose can be stated as:
If two convex polygons are not colliding, there must be some separating axis such that when the polygons are projected onto the axis, the projections are not colliding.
A more friendly (though not entirely accurate) way of saying this is:
If two convex polygons are not colliding, there must be a way to draw a straight line between them without touching either one.
Therefore, if we want to find out if two convex polygons are colliding, all we need to do is prove that there is no separating axis; i.e., it is impossible to draw a straight line that separates the two.
There are two parts to solving this problem: finding out which lines we should test, and actually testing the lines.
Part 1: which lines should we test?
Obviously, it's prohibitively expensive to try every possible line between the two polygons. What's the smallest set of candidate lines?
If you think about it, a convex polygon is always going to start colliding when one of its faces touches the other polygon. That is, if you were to mash a rectangle into a hexagon, from any angle, the part of the rectangle that will always touch the hexagon first is one of its sides (two if it's a corner). The same is true from the hexagon's perspective, but might not be quite as easy to imagine.
Because the first things to collide between two polygons will always be some set of their faces, the lines we should try are the set of lines which run parallel to each face of each polygon.
Part 2: how do you test a line?
Again, it is obviously too difficult to test every single line that runs parallel to any face of either polygon.
At this point, the metaphor of "drawing a line between the polygons" starts to break down. What we really want is to ask, for each face of each polygon, "is there a gap between the polygons relative to this particular face?"
Recall that at this point all we've decided is that we need to test, for each face of each polygon, whether some line that runs parallel to the face can be drawn without cutting either polygon. There isn't really a clear way to do this. What we need to do at this point is flip the problem ninety degrees and test gaps rather than lines.
To check whether there's a gap between two polygons relative to a particular axis (hold on, we'll get there), we need to use a tool called scalar projection.
Projection (we'll get to the scalar bit in a moment) is basically taking a polygon and throwing it, splat, against a wall. The splat mark is the projection of the polygon.
But what's the wall? That's our axis, or more precisely our axis of separation. What did the separating axis theorem say again?
If two convex polygons are not colliding, there must be some separating axis such that when the polygons are projected onto the axis, the projections are not colliding.
Okay! So what this means is pretty much
If there is any wall at which you can throw two polygons, splat, and the splat marks don't overlap, then the polygons aren't colliding.
This interpretation means we can ask the following two questions, which are much easier to answer than our original query:
How to you throw a polygon against a wall? Splat?
How do you test whether splat marks overlap?
Part 3: How do you project a polygon?
I've tried to keep the descriptions of projection in three dimensions for ease of visualization, but at this point we have to drop down into two dimensions because I haven't the faintest idea how all the math works in three.
If it helps, you can visualize the 2D version of the above by imagining that you're looking top-down at the crazy man hurling polygons at walls.
So, scalar projection. How do you do it?
s = |a|cosθ = (a â
b) / |b|
Isn't mathematics notation great?
Okay, so. You need to understand some things before being able to understand the reasoning behind this equation.
Part 4: Stuff about vectors
The first is the notion of a vector. A vector is an arrow. I don't care what you may have heard in math or physics. For every single useful application of vectors I've seen in game development, thinking of a vector as an arrow is perfectly sufficient. The important properties of a vector are its length and its direction.
Another powerful thing to note about a vector is that you can decompose any vector into components. The components of a vector are basically a bunch of smaller vectors (arrows) that get you to the same place as the original vector. Usually, you keep track of components relative to each axis of your coordinate system, so you can generally expect a two-dimensional vector to be modeled as a structure that has an x component and a y component. This is how we're going to represent our vectors.
So. Vectors have a bunch of operations you can do on them. The ones we need here are the concept of a normal, the magnitude, the unit vector, and the dot product.
The normal of a vector is pretty much another vector with the same magnitude but a perpendicular direction. Each vector has two normals: right-hand and left-hand. You can get the normals of the vector by swapping its components (y, x =Â x, y) and negating either the new x component (left-hand normal) or the new y component (right-hand normal). Usually it doesn't matter which normal you use as long as you're consistent.
The magnitude of a vector is how long the arrow is. There are two interesting things to say about magnitude. The first is that it can be computed like this:Â sqrt(x * x + y * y), where x and y are the components of the vector.
The second interesting thing about magnitude is that vectors with a magnitude of one, usually called unit vectors, are super useful because they represent pure direction. In a traditional 2D coordinate system, the vector will be pointed in a certain direction, meaning it has a certain angle. The x component of a unit vector is the cosine of that angle, and the y component is the sine. If you know any trigonometry at all, you know that these values are really really useful, especially when you don't even need to know the angle to get the unit vector. You can compute a unit vector that points in the same direction as some random vector by taking that vector and dividing all of its components by its magnitude.
The dot product can be kind of difficult to understand. On the face of things, it's pretty arbitrary: you take two vectors, a and b, and sum their element-wise products: a dot b is a.x * b.x + a.y * b.y. Indeed, the only thing that's particularly useful about the dot product of two random vectors is that it's positive when they point in roughly the same direction (the smallest angle between them is less than ninety degrees) and negative otherwise.
But something special happens when b is a unit vector. Somehow, magically, when you take the dot product of some random vector with a unit vector, that turns into throwing the first vector at the second. SPLAT. What you get out is a number that tells you where the splat mark from the first vector ends up on the wall containing the second vector.
This sorcery has pretty much everything to do with trigonometry. Feel free to try and visualize it. The top-down thing helps. But now, I figure it's high time we get back to collision detection.
Part 5: How do you check if two projections overlap?
So, you have your two polygons. You take each vertex of each polygon, and splat it against a unit vector running parallel to some face of one of your two polygons. You end up with two sets of points. What do you do next?
Well, we don't really need the points that are hanging out in the middle of the splat mark. We really only need the smallest and largest point in each set.
Having thrown all the deadwood out, we're left with two line segments. How do you test if two line segments overlap?
See if the left point of the first segment is farther right than the right point of the second segment.
See if the right point of the first segment is farther left than the left point of the second segment.
If neither of the above are true, the segments overlap.
BAM. COLLISION DETECTION.
Part 6: Putting it all together
I think they're going to kick me out of this coffee shop soon, so I'll be brief. We've seen how to describe the collision problem in terms of gaps between faces, and we've learned how to measure the presence of those gaps. What does the actual algorithm look like?
for each face in union(faces in polygon A, faces in polygon B): axis = unit vector running parallel to the face point set A = project polygon A onto axis point set B = project polygon B onto axis left point A = find minimum(point set A) right point A = find maximum(point set A) left point B = find minimum(point set B) right point B = find maximum(point set B) if left point A > right point B or right point A < left point B: return false return true
This describes the general algorithm. Here's the helper functions:
to find a unit vector running parallel to a face: unit vector = new vector unit vector.x = face.x2 - face.x1 unit vector.y = face.y2 - face.y1 unit vector = unit vector / magnitude(unit vector) return unit vector to project a polygon onto an axis: point set = new set for each vertex in the polygon: projected vertex = dot(vertex, axis) append(projected vertex, point set) return point set
Okay, I have to go. I might edit this post later. Hope it was helpful! :D
