分离轴定理解决矩形碰撞问题
引自http://www.gamedev.net/reference/programming/features/2dRotatedRectCollision/
?
Separating Axis Theorem
The separating axis theorem states thatfor a pair of convex polygons that are not in a state of collision there existsan axis perpendicular to an edge of one of the polygons that has no overlapbetween the projected vertices of the two polygons. Essentially, what thismeans is that if we project the vertices of the two polygons that we aretesting onto each axis that is perpendicular to the edges of each polygon andwe detect an overlap on each polygon there is a collision, if even one axisshows no overlap then a collision is impossible. This solution works for anycollision possibility, even the dreaded cross collision.
Figure 1. CrossCollision
Setting Up
Figure 2.Standard Bounds-based Collision Check
As you can see, the minimum x value of B lies within thespace defined by the minimum and maximum x values of A. Additionally, theminimum y value of B lies within the space defined by the minimum and maximum yvalues of A. With simple bounds based collision detection this would registeras a collision, when it clearly is not.
Step 1
Figure 3. TheEight Perpendicular Axes
As you can see, we end up with eight axes. You should alsoimmediately see the benefits of using rectangles. Firstly, each edge has anopposite edge which shares an identical axis, we can take advantage of this tolower the number of axes that need checked to four. Secondly, the angle thatexists between any two adjacent edges on a rectangle is 90 degrees. As such, forany edge of a rectangle, both of the adjacent edges are perpendicular to it.This means that we can calculate our four axes to be as such:
Axis1.x = A.UR.x - A.UL.x
Axis1.y = A.UR.y - A.UL.y
Axis2.x = A.UR.x - A.LR.x
Axis2.y = A.UR.y - A.LR.y
Axis3.x = B.UL.x - B.LL.x
Axis3.y = B.UL.y - B.LL.y
Axis4.x = B.UL.x - B.UR.x
Axis4.y = B.UL.y - B.UR.y
Meaning that Axis 1 is the resultant vector of theupper-right corner of A minus the upper-left corner of A and so on. This givesus four axes, each of which is perpendicular to two opposite edges of one ofthe rectangles, meaning that for each edge we have an axis that isperpendicular to it.
Figure 4. OurFour Axes
Here is the equation expanded out into scalar math andsimplified:
It is important to note that the only difference betweenthese two equations is that we’re multiplying by Axis 1’s x coordinate at the end of the first equation andwe’re multiplying by Axis 1’s ycoordinate at the end of the second equation. That will give you the x and ycoordinates of A.UR projected onto Axis 1. As an example, let’s pretend thatA.UR is at location (2, 6) and Axis 1 is represented by the vector (3, 4):
Therefore, in this example, the x coordinate of A.URprojected onto Axis 1 is 3.6 and the y coordinate is 4.8.
Figure 5.Vectors Projected Onto Axis 1
Figure 6. Theminimum and maximum scalar values
Figure 7. NoOverlap = No Collision
??????You can and should stop checking forcollision the instant you find an axis where the rectangles don’t overlap.Remember, the separating axis theorem says that if two polygons are colliding allaxes that are perpendicular to the edges of the polygons will show an overlap.Meaning that, if one axis shows no overlap, then collision is not possible andyou should opt out to prevent unnecessary math.
??????It can really pay off to transform rectangle Binto rectangle A’s local space. In order to do this, you should maintain theserectangles in local space and then transform rectangle B into world space andthen by the inverse of rectangle A’s world space transform to put rectangle Binto rectangle A’s local space. Then, translate both rectangles equally so thatrectangle A is centered about the x and y axes. This means that two of the fouraxes that you need to project vectors onto are the unit (x and y) axes. Simplycheck for overlap between the x values of the corners of both rectangles andbetween the y values of the corners of both rectangles. With this solution youonly have to actually project the vectors onto arbitrary axes twice, instead offour times.
Figure 8.Rectangles A and B in world space
Figure 9.Rectangles A and B Transformed Into A's Local Space
??????It can be wise to utilize a radius thatcompletely encompasses the rectangle. If the distance between the centers ofrectangles A and B is greater than the radius of A and B added together thenthere cannot possibly be a collision and it is unnecessary to use theseparating axis theorem.
?
?
?
?
?
