旋转矩形碰撞检测.doc

2D旋转矩形碰撞检测(极力推荐)----支持水平镜像(垂直镜像同理，可以自己编写)
数学知识 2010-10-05 14:28:40 阅读734 评论0   字号：大中小 订阅
最近在用Flash AS3.0写一个ACT游戏，由于要检测攻击碰撞和被攻击碰撞(没有使用像素级碰撞----没有必要)，遇到矩形碰撞的问题，就是无法全部满足旋转矩形的需求。MovieClip.hitTestObject()对旋转矩形是不适用的，且非常糟糕。在此自己写了一个。对于这种2D动作游戏来说矩形碰撞是绝对满足要求的，不需要使用像素级碰撞来检测碰撞。

一、必知的一些概念
1，Separating Axis Theorem(SAT)（分离轴定律）
引用:http://vision.twbbs.org/~jen/?p=78
     什么是STA?
SAT為一種可快速偵測不規則凸多邊是否碰撞的演算法，他的概念如下:給予兩個凸多邊形物體，如果我們能找到一個軸，使得兩個在物體在該軸上的投影互不重疊，則這兩個物體之間沒有碰撞發生，該軸並稱為其Separating Axis。 (紅色軸線)

對於2D的例子來說，可能存在的Separating Axis為垂直於該多邊形各個邊的軸(紅色軸線)。

因此，若我們要檢查兩多邊形是否碰撞，就去檢查兩多邊形在每個所有可能的軸上的投影是否重疊。

如果我們找到一個軸，使得兩多邊形在該軸上的投影互不重疊，則我們就可以知道這兩個多邊沒有碰撞發生。(知道判断不重叠就可以退出了)

如果是3D case的話，則需要考慮的可能的Saparating Axis包括各個面的normal，還有每個面中，兩兩edge之外積所形成的向量。
Metanet Software有一個很棒的互動式SAT教學
David Eberly也有發表一篇比較偏講解SAT理論方面的文章
Intersection of Convex Objects: The Method of Separating Axes

二、旋转碰撞讲解

当我着手学校的项目时,我发现必须对翻转的精灵之间实现碰撞检测,开始想到了包围盒
但因为对每个像素检测是很耗时而且也没必要,经过几天的摸索,我用SAT(separating axis theorem)高效的实现了它,当我把我的方法结实给我的同学和实验室的技术人员时,我意识到游戏开发组织可能通过清晰而彻底解释过程中获益.此而外线性代数,向量数学是很有用的,但不影响对这篇文章的理解.
SAT(Separating Axis Theorem)

Separting Axis Theorem 指出了一对不处于碰撞情况的凸多变形,有且一条相对于多变形一条边的垂直轴,并且两个多边形的投影顶点无重叠.

如果我们投影这个两个多边形顶点(我们正在对每个垂直于每个多边行边的轴进行测试),然后我们检测每个多边形的重叠并且存在碰撞,即使是一个轴没有没有重叠,那么碰撞是不可能的,实质上它到底有什么意义呢.
这种解决方法适用对碰撞检测的可能性,甚至是交叉碰撞.

 图1, 交叉碰撞
我们在深入碰撞算法之前,使用这个方法得有具备一些前提.首先,虽然分离轴理论可以用来在凸多边形之间检测碰撞,但矩形是在2D中通常碰撞方式,所以我们假设你使用几个矩形.此外还得假设你可以把矩形转换为带有四个向量的结构体,他们每个代表一个角,以标记或组织的方式,而知道哪个角是哪个,(具体来说,我们需要去识别哪些角是相临的---如果左上角一直转到它在矩形的低部为止,只要保持边与左上角和右下角标签相联系.
方法
检查两个相互旋转矩形碰撞的确是个问题,什么时候能决定他们不相撞.最简单的交叉检测使用m$的IntersesectRect()函数会检测最大/最小的矩形B的值是否在矩形A的最大和最小的值内.这种对方对
对称轴矩形工作得很好,但在处理旋转矩形时,我们采用更为复杂的方式

图2.标准基于包围的碰撞检测

正如你所见的那样.B的最小值x位于被A的最大和最小x所定义的空间中.此外 ,B的最小值y位于被A的最大和最小y定义的空间中的.使用简单的基于包围的碰撞检测，这将登记为碰撞，反之这不会．

步骤１
这个方法的第一步就是确定我们要往上投影向量的轴．分离轴理论（SAT)指出了,我们必须有一个轴，垂直于我们两个多边形的每个边

     图3.八个垂直轴
正如你看到的,我们以八个轴结束,你也应该马上看到使矩形的优势,首先,每个边有一条对边(Opposite edge),它共享同一个轴,我们可以利用这个来降低本检测数目,这里只需要四个轴.其次，存在矩形上任意两个相临边的角度为90度.本身而言,对于矩形的任何一个边,两个相临边垂直于它.这就说,我们可以这样计算4个轴:
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
如果发生了水平镜像呢？
我们都知道，如果矩形发生了水平镜像，那么对于一个正常的矩形来说，如下图。
角的顺序是  ABCD

如果发生了水平镜像，那么就变成 

 B和C发生了变换，D和A发生了变换，所以角的顺序是DCBA,所以上面两个矩形的四个轴就变成
UR--->UL
UL--->UR
LR--->LL
LL--->LR
所以替换得
Axis1.x = A.UL.x - A.RL.x
Axis1.y = A.UL.y - A.UR.y
Axis2.x = A.UL.x - A.LL.x
Axis2.y = A.UL.y - A.LL.y
Axis3.x = B.UR.x - B.LR.x
Axis3.y = B.UR.y - B.LR.y
Axis4.x = B.UR.x - B.UL.x
Axis4.y = B.UR.y - B.UL.y

那么对于垂直镜像呢？，同理，如下图

 A和B交换，C和D发生交换，当然这是在没有发生水平镜像的前提下说明的，如果有水平镜像，那么你要仔细考虑了，不过原理是一样的。
那么针对没有水平镜像的情况下垂直镜像我算出4个轴出来。其实和水平镜像一样。

UR---->LR
LR---->UR
UL---->LL
LL---->UL
垂直镜像的四个轴,替换为
Axis1.x = A.LR.x - A.LL.x
Axis1.y = A.LR.y - A.LL.y
Axis2.x = A.LR.x - A.UR.x
Axis2.y = A.LR.y - A.UR.y
Axis3.x = B.LL.x - B.UL.x
Axis3.y = B.LL.y - B.UL.y
Axis4.x = B.LL.x - B.LR.x
Axis4.y = B.LL.y - B.LR.y

对于这个只要轴改变就可以，下面都可以正常运行。

Axis 1表示是A的右上角合向量减去左上角的合向量,其他的也是如此.这里给了我们四个轴,每个垂直于一个矩形的两个对边,这表示
对于每个边上,我们都有一个垂直于它的轴.

          图4:4个轴
步骤2
下一步就是把表示每个矩形四个角的向量投影到每个轴上去.如果你知道如何进行矩阵投影,那么你完成这个应该没问题.
如果你望了矩阵而且望了如何投影,这里提供了投影矩形A的右上角到 Asix 1的等式:

 以下是把方程扩展为标量方程,并简化:

必须指出的是,两个方程的唯一区别就是:我们使用Axis 1的x坐标乘在第一个方程尾部,使用Axis 1的y坐标乘在第二方程
尾部 ,这将给你投影到Axis 1上A.UR的x,y坐标.  举个例子,设A.UR为(2,6),Axis 1由向量(3,4)表示:
带入公式:

 所以,在这个例子,A.UR的x坐标投影到Axis 1是3.6,而y坐标为4.8

   图5.投影到Axis1上向量

步骤3
第三步在这个算法中是计算标量值，这将使我们能够确定每个矩形的最大和最小投影向量。虽然可能很自然的使用标准(长度)向量,如果是一个负坐标那么会出错的，那么就返回一个正标量值。最简单最方便的解决方案是用点乘以每个轴的向量。这将给予我们一个毫无意义的标量值，无论怎么样，这个值指出了在轴中向量的位置。使用我们上面的例子：

图6. 最小和最大标量值
步骤4
现在已确定矩形A和B的最大和最小(我们已经计算过了)标量值。如果B的最小标量值<=A的最大标量值且B的最大标量值>=A的最小标量值时，那么当投射到轴上时，我们的对象就会发生重叠。

图 7. 没有重叠=没有碰撞
重复
在每个轴上重复步骤2和3,4。如果所有的轴都显示重叠就表示碰撞，如果有一个轴没有重叠就表示没有碰撞。

优化
下面几件事可以优化算法：
· 如果你找到一个轴不碰撞那么你应该立刻停止检测碰撞。记住，分离轴定理说，如果两个多边形碰撞所有轴是垂直的多边形的边会出现重叠。这意味着，如果一个轴显示没有重叠，那么碰撞是不会发生的，你应该退出，避免不必要的数学计算。
· 把矩形B转换为矩形A的本地空间。为了做到这些，你必须在本地空间中操作这些矩形然后转化矩形B为世界空间，在就是矩形A世界空间的逆变换，然后把矩形B添加到矩形A的本地空间中。 同样转化两个矩形，把矩形A在X和y轴居中。这意味着四个轴你需要把两个向量投影到单位(x,y)轴上。只要检查两个矩形之间重叠角的x和y值。有了这个方案，你实际上只需要两次任意轴的投影向量，而不是四次。

图8. 在世界空间的矩形A和B

Figure 9. 在A的本地空间中已转化的矩形A和B
· 用半径完全包含了矩形是非常明智的。 如果矩形A和B之间的中心距离>A+B的半径，那是不可能发生碰撞的，这是不必使用分离轴定理。

代码编写：
下面就是代码了，我用AS3.0写的，使用FlashDevlop编写，要注意
private var rect1:Sprite = new Rect1();//创建一个矩形
private var rect2:Sprite = new Rect1();
这两个对象是一个MovieClip，我使用的是SWC文件，里面就是一个Rect1类。

注意要想正常使用下面类，就必须按照下面几个条件：

1: 要碰撞的矩形，在定义元件时必须指定其中点作为其帧原点
2: rorationRectCollide参数给予的旋转角度必须是全局相对于舞台的角度，可由下列公式来获取
    发生旋转的主容器(也是最大最外面的总容器).rotation+要碰撞的元件.rotation*主容器.scaleX
3: 指明是否发生了水平镜像，由主容器来决定。主容器.scaleX

例如，
var cap:Sprite=new Sprite();
var s1:DisplayObject=new DisplayObject();
var s2:DisplayObject=new DisplayObject();
var s3:Sprite=new Sprite();
s3.addChild(s1);

cap.addChild(s1);
cap.addChild(s2);
cap.addChild(s3);
addChild(cap);

cap中的s1
s1旋转角度=cap.rotation+s1.rotation*cap.scaleX;

s3中的s1
s1旋转角度:
先算出s3的实际旋转角度=cap.rotation+s3.rotation*cap.scaleX;
在算出s1的实际旋转角度=s3.rotation+s1.rotation*s3.scaleX;

//看上面的例子就是自己要一级一级算出其实际旋转角度，所以为了方便，自己最好只有两级容器。

package  
{
import adobe.utils.CustomActions;
import flash.display.DisplayObject;
import flash.display.InterpolationMethod;
import flash.display.PixelSnapping;
import flash.display.SpreadMethod;
import flash.display.Sprite;
import flash.geom.*;
import flash.utils.*;
import .registerClassAlias;

/**
* ...
* @author 戢晶晶
* 此类用来检测两个矩形的碰撞（包括旋转的矩形），使用分离轴定理来完成，坐标投影
*   分离轴定理---这么说的:SAT為一種可快速偵測不規則凸多邊是否碰撞的演算法，他的概念如下:給予兩個凸多邊形物體，
*   如果我們能找到一個軸，使得兩個在物體在該軸上的投影互不重疊，則這兩個物體之間沒有碰撞發生，該軸並稱為其Separating Axis。
*   
*/
public class RectCollide {
public function RectCollide() {
}

   /*   
*   深度拷贝，最好用于普通对象上，不要用于自定义类上
*   obj: 要拷贝的对象
*   return ：返回obj的深度拷贝
*/
public static function clone(object:Object):DisplayObject{  
var qClassName:String = getQualifiedClassName(object);  
var objectType:Class = getDefinitionByName(qClassName) as Class;  
registerClassAlias(qClassName, objectType);  
var copier : ByteArray = new ByteArray();  
copier.writeObject(object);  
copier.position = 0;  
return copier.readObject() as DisplayObject;  
        } 
/*
*   获取一个点旋转一定角度后的新坐标
*   origin: 原点，就是p点环绕其转动的点
*   p: 要旋转的点
*   ro:  旋转角度
*   公式是 :
*   x0=(x-b)*cos(a)-(y-c)*sin(a);  (x,y) ----P点     (b,c)----origin点    a----角度
* 
             y0=(y-c)*cos(a)+(x-b)*sin(a);
             x1=x0+b;
             y1=y0+c;
(x1,y1)----旋转后的点
*   
   */
private static function getRectPoint(origin:Point, p:Point, ro:Number):Point {
var radian:Number = ro * Math.PI / 180;
var x0:Number = (p.x - origin.x) * Math.cos(radian) - (p.y - origin.y) * Math.sin(radian);
var y0:Number = (p.y - origin.y) * Math.cos(radian) + (p.x - origin.x) * Math.sin(radian);
return new Point(x0+origin.x,y0+origin.y);
}

/*
*    影片剪辑的复制，只要是DisplayObject都可以
*    target ：要复制的影片剪辑
*    autoAdd: 如果为true就表示重复的天骄显示列表中
*    
*/
public static function duplicateDisplayObject(target:DisplayObject, autoAdd:Boolean = false):DisplayObject {
// create duplicate
var targetClass:Class = Object(target).constructor;
var duplicate:DisplayObject = new targetClass();

// duplicate properties
duplicate.transform = target.transform;
duplicate.filters = target.filters;
duplicate.cacheAsBitmap = target.cacheAsBitmap;
duplicate.opaqueBackground = target.opaqueBackground;
if (target.scale9Grid) {
var rect:Rectangle = target.scale9Grid;
// Flash 9 bug where returned scale9Grid is 20x larger than assigned
rect.x /= 20, rect.y /= 20, rect.width /= 20, rect.height /= 20;
duplicate.scale9Grid = rect;
}

// add to target parent's display list
// if autoAdd was provided as true
if (autoAdd && target.parent) {
target.parent.addChild(duplicate);
}
   return duplicate;
}
/*
*   获取矩形的每个点，保存在Array中并返回
*   dis:显示对象，获取其矩形坐标
*   globalPoint :以将dis坐标转化为舞台全局坐标了
*/
private static function getRectEachPoint(dis:DisplayObject, globalPoint:Point, ra:Number):Array {

var s:DisplayObject = duplicateDisplayObject(dis);//复制dis一个副本
s.rotation = 0;
/*  b                      c
*   |---------------------|
*   |                     |
*   |                     |
    |                     | 
    |---------------------|
a                     d
保存的坐标要按abcd的形式保存
*/
var w:Number = s.width;
var h:Number = s.height;

var fourPointArr:Array = [//保存四个正常顶点坐标，且都是全局的
   new Point(globalPoint.x-(w>>1),globalPoint.y+(h>>1)),
new Point(globalPoint.x-(w>>1),globalPoint.y-(h>>1)),
new Point(globalPoint.x+(w>>1),globalPoint.y-(h>>1)),
new Point(globalPoint.x+(w>>1),globalPoint.y+(h>>1))
];
for (var i:int = 0; i < 4;++i) {//循环找到各个顶点旋转ra角度后的新坐标，并还是保存在fourPointArr中
   fourPointArr[i] = getRectPoint(globalPoint, fourPointArr[i],ra);
}
s = null;
return fourPointArr;//返回新的坐标
}

/*
*    用来判断两个矩形是否碰撞
*    rect1： 第一个矩形（这里用可显示对象来代替）
*    ra1 ： 第一个矩形的全局旋转角度
*    mirror1:矩形1是否发生了水平镜像  >0没有  <0发生了x方向上的水平镜像
*    rect2:  第二个矩形
*    ra2   :第二个矩形的全局旋转角度
*     mirror1:矩形2是否发生了水平镜像  >0没有  <0发生了x方向上的水平镜像
*    return 返回碰撞的结果
*/
public static function rorationRectCollide(rect1:DisplayObject,ra1:Number,mirror1:Number,rect2:DisplayObject,ra2:Number,mirror2:Number):Boolean {
    //先算出两个矩形的四个顶点保存在数组中，供后面使用
var globalPoint1:Point = rect1.localToGlobal(new Point(0, 0));//把rect1显示对象的坐标转换为全局舞台坐标
var globalPoint2:Point = rect2.localToGlobal(new Point(0, 0));;//获取rect2的全局坐标
//trace("globalPoint1="+globalPoint1.x);
var arr1:Array = getRectEachPoint(rect1, globalPoint1,ra1);//获取四个顶点的坐标
var arr2:Array = getRectEachPoint(rect2, globalPoint2,ra2);//获取顶点坐标
if (maybeCollide(globalPoint1, arr1[0], globalPoint2, arr2[0])) {//进行分离轴定理的先决条件
//获取第一个矩形的轴， 在这里我全局例举出来，对于效率来说也是很高的
//第一个轴
var AsisArr:Array = [//四条轴
    // c-b
    new Point(arr1[2].x - arr1[1].x, arr1[2].y - arr1[1].y),//矩形A的轴
 //c-d
    new Point(arr1[2].x - arr1[3].x, arr1[2].y - arr1[3].y),
// b-a
    new Point(arr2[1].x -  arr2[0].x, arr2[1].y - arr2[0].y),//矩形B的轴
//b-c
    new Point(arr2[1].x -  arr2[2].x,arr2[1].y - arr2[2].y)
];
if (mirror1 < 0) {//矩形A发生水平镜像，那么矩形A的两条轴要发生改变
   //b-c(c-b的水平镜像)
AsisArr[0] = new Point(arr1[1].x - arr1[2].x, arr1[1].y - arr1[2].y),//矩形A的轴
//b-a(c-d的水平镜像)
AsisArr[1] = new Point(arr1[1].x -  arr1[0].x, arr1[1].y - arr1[0].y)
}
if (mirror2 < 0) { //矩形B发生水平镜像，那么矩形B的两条轴要发生改变
   //c-d (b-a)
AsisArr[2] = new Point(arr2[2].x - arr2[1].x, arr2[2].y - arr2[1].y),//矩形B的轴
//c-b (b-c)
AsisArr[3] = new Point(arr2[2].x - arr2[3].x, arr2[2].y - arr2[3].y)//矩形B的轴
}
for (var i:int = 0; i < 4;++i) {//四个轴依次判断
     if (projectOverlap(AsisArr[i], arr1, arr2)) {//只要为true就表示有一个没有重叠，那么就没有碰撞
 return false;
 }
}
return true;
}
return false;//发生了碰撞
/*************************/
}

/*
*   用来判断是否两个矩形碰撞，这是个先决条件，如果这个条件都没有，那么就绝对不发生碰撞，那么就不执行分离轴定理了
*   
*   这个条件是---如果矩形A和B之间的中心距离>A+B的半径，那是不可能发生碰撞的，这是不必使用分离轴定理。
*   A和B的半径是 其顶点到其原点的距离
*   
*   返回碰撞的可能性，如果为false，就一定不碰撞，如果为true，就有可能碰撞，但不一定
*    p00： 第一个矩形的中点坐标，也是原点，这个项目中就是其x，y坐标，要全局的
*    p01： 其中一个顶点的坐标，通常用左边角那个(正常情况下的)
*    
*    后面的参数一样的
*/
private static function maybeCollide(p00:Point,p01:Point,p10:Point,p11:Point):Boolean {
var r1:Number = getTowPointDistance(p00, p01);//算出第一个矩形的半径
var r2:Number = getTowPointDistance(p10, p11);//第二个矩形的半径
var abDistance:Number = getTowPointDistance(p00,p10);//第一个矩形和第一个矩形原点的距离
if (abDistance > r1 + r2) {//如果矩形A和B之间的中心距离>A+B的半径，那是不可能发生碰撞的
return false;
}
return true;//有可能发生碰撞
}

/*
*   获取两个点的距离
*/
private static function getTowPointDistance(p1:Point, p2:Point):Number {
var ax:Number = (p1.x - p2.x) * (p1.x - p2.x);
var ay:Number = (p1.y - p2.y) * (p1.y - p2.y);
return Math.sqrt(ax+ay);
}

/*
*   用来判断是否两个矩形的顶点在轴上有重叠的情况
*   Ax: 轴向量
*   rectArr1:第一个矩形的顶点坐标
*   rectArr2: 第二个矩形的顶点坐标
* 
*   投影公式：  例如  矩形的一个顶点为(rx,ry),轴点向量为(Ax,Ay)
*   
*   这个点的投影是：  x0=(rx*AX+ry*Ay)/((Ax)^+(Ay)^)*Ax;
*                     y0=(rx*AX+ry*Ay)/((Ax)^+(Ay)^)*Ay;
*   算出投影后，每个点在向量的位置公式是：
*   d=x0*Ax+y0*Ay;//其实就是坐标相乘
*   
*/
private static function projectOverlap(Ax:Point, rectArr1:Array, rectArr2:Array):Boolean {
//算出每个顶点到轴的投影，公式在上面
//检测两个矩形的投影的是否重叠，判断依据是 : 如果B的最小标量值<=A的最大标量值且B的最大标量值>=A的最小标量值时，
//那么当投射到轴上时，我们的对象就会发生重叠
var rect1MinMax:Array = getScalarValue(rectArr1, Ax);//第一个矩形的最小标量值和最大标量值
var rect2MinMax:Array = getScalarValue(rectArr2, Ax);//第二个矩形的最小标量值和最大标量值
//开始判断是否重叠
if (rect2MinMax[0] > rect1MinMax[1] ||rect2MinMax[1] < rect1MinMax[0]) {//没有发生重叠
return true;
}
return false;//有可能发生重叠
}

/*
*   获取一个顶点到轴的投影
*   axsi ：轴
*   p:   矩形其中一个顶点
*/
private static function getProjectPoint(axsi:Point, p:Point):Point {
var x0:Number = (p.x * axsi.x + p.y * axsi.y) / (axsi.x * axsi.x + axsi.y * axsi.y) * axsi.x;
var y0:Number = (p.x * axsi.x + p.y * axsi.y) / (axsi.x * axsi.x + axsi.y * axsi.y) * axsi.y;
return new Point(x0,y0);
}

/*
*   获取一个矩形的投影到轴上的最小值和最大标量
*   arr:  顶点数组
*   axsi ：原点坐标
*   
*/
private static function getScalarValue(arr:Array, axsi:Point):Array {
var minMaxArr:Array = new Array(2);//第一个存最小值，第二个存最大值
var tempArray:Array = new Array(4);//保存四个投影坐标的
var len:int = arr.length;
for (var i:int = 0; i < 4;++i) {
tempArray[i] = getProjectPoint(axsi,arr[i]);//找到投影点
tempArray[i] = tempArray[i].x * axsi.x + tempArray[i].y * axsi.y;
//trace("tempArray[i]="+tempArray[i]);
}
tempArray.sort();//开始排序
tempArray.sort(Array.NUMERIC);//数字排序
   //trace("tempArray="+tempArray);
//计算出最小标量值和最大标量值
//公式是 d=x0*Ax+y0*Ay;//其实就是坐标相乘
minMaxArr[0] = tempArray[0];
minMaxArr[1] = tempArray[3];
tempArray = null;
return minMaxArr;
}
}

}
上面这个类可以检测任何DisplayObject之间的碰撞，不管他怎么旋转都可以检测碰撞。里面主要的知识点就是：
(1)投影矩阵
(2)点旋转
(3)向量，怎么通过两个点确定垂直于这两个点连线的轴

PS：差点忘记提了，制作元件时一定要确保其帧原点在中点上还有就是碰撞矩形一定要填充的，否则会出现问题的。
缺陷在于无法对即使放大和缩小的两个矩形进行正常的检测。