旋转矩形碰撞检测.doc

2D旋转矩形碰撞检测(极力推荐)-支持水平镜像(垂直镜像同理，可以自己编写)数学知识 2010-10-05 14:28:40 阅读734 评论0 字号：大中小订阅 最近在用Flash AS3.0写一个ACT游戏，由于要检测攻击碰撞和被攻击碰撞(没有使用像素级碰撞-没有必要)，遇到矩形碰撞的问题，就是无法全部满足旋转矩形的需求。MovieClip.hitTestObject()对旋转矩形是不适用的，且非常糟糕。在此自己写了一个。对于这种2D动作游戏来说矩形碰撞是绝对满足要求的，不需要使用像素级碰撞来检测碰撞。 一、必知的一些概念1，Separating Axis Theorem(SAT)（分离轴定律）引用:/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.xAxis1.y = A.UR.y - A.UL.yAxis2.x = A.UR.x - A.LR.xAxis2.y = A.UR.y - A.LR.yAxis3.x = B.UL.x - B.LL.xAxis3.y = B.UL.y - B.LL.yAxis4.x = B.UL.x - B.UR.xAxis4.y = B.UL.y - B.UR.y如果发生了水平镜像呢？我们都知道，如果矩形发生了水平镜像，那么对于一个正常的矩形来说，如下图。角的顺序是 ABCD如果发生了水平镜像，那么就变成B和C发生了变换，D和A发生了变换，所以角的顺序是DCBA,所以上面两个矩形的四个轴就变成UR-ULUL-URLR-LLLL-LR所以替换得Axis1.x = A.UL.x - A.RL.xAxis1.y = A.UL.y - A.UR.yAxis2.x = A.UL.x - A.LL.xAxis2.y = A.UL.y - A.LL.yAxis3.x = B.UR.x - B.LR.xAxis3.y = B.UR.y - B.LR.yAxis4.x = B.UR.x - B.UL.xAxis4.y = B.UR.y - B.UL.y那么对于垂直镜像呢？，同理，如下图A和B交换，C和D发生交换，当然这是在没有发生水平镜像的前提下说明的，如果有水平镜像，那么你要仔细考虑了，不过原理是一样的。 那么针对没有水平镜像的情况下垂直镜像我算出4个轴出来。其实和水平镜像一样。UR-LRLR-URUL-LLLL-UL垂直镜像的四个轴,替换为Axis1.x = A.LR.x - A.LL.xAxis1.y = A.LR.y - A.LL.yAxis2.x = A.LR.x - A.UR.xAxis2.y = A.LR.y - A.UR.yAxis3.x = B.LL.x - B.UL.xAxis3.y = B.LL.y - B.UL.yAxis4.x = B.LL.x - B.LR.xAxis4.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的最小标量值时，那么当投射到轴上时，我们的对象就会发生重叠。 图 7.没有重叠=没有碰撞重复在每个轴上重复步骤2和3,4。如果所有的轴都显示重叠就表示碰撞，如果有一个轴没有重叠就表示没有碰撞。 优化下面几件事可以优化算法： 如果你找到一个轴不碰撞那么你应该立刻停止检测碰撞。记住，分离轴定理说，如果两个多边形碰撞所有轴是垂直的多边形的边会出现重叠。这意味着，如果一个轴显示没有重叠，那么碰撞是不会发生的，你应该退出，避免不必要的数学计算。 把矩形B转换为矩形A的本地空间。为了做到这些，你必须在本地空间中操作这些矩形然后转化矩形B为世界空间，在就是矩形A世界空间的逆变换，然后把矩形B添加到矩形A的本地空间中。同样转化两个矩形，把矩形A在X和y轴居中。这意味着四个轴你需要把两个向量投影到单位(x,y)轴上。只要检查两个矩形之间重叠角的x和y值。有了这个方案，你实际上只需要两次任意轴的投影向量，而不是四次。图8.在世界空间的矩形A和BFigure 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*主容器.scaleX3: 指明是否发生了水平镜像，由主容器来决定。主容器.scaleX例如，var cap:Sprite=new Sprite();var s1:DisplayObject=newDisplayObject();var s2:DisplayObject=newDisplayObject();var s3:Sprite=new Sprite();s3.addChild(s1);cap.addChild(s1);cap.addChild(s2);cap.addChild(s3);addChild(cap);cap中的s1s1旋转角度=cap.rotation+s1.rotation*cap.scaleX;s3中的s1s1旋转角度:先算出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 duplicatevar targetClass:Class = Object(target).constructor;var duplicate:DisplayObject = new targetClass();/ duplicate propertiesduplicate.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 assignedrect.x /= 20, rect.y /= 20, rect.width /= 20, rect.height /= 20;duplicate.scale9Grid = rect;/ add to target parents display list/ if autoAdd was provided as trueif (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-(w1),globalPoint.y+(h1),new Point(globalPoint.x-(w1),globalPoint.y-(h1),new Point(globalPoint.x+(w1),globalPoint.y-(h1),new Point(globalPoint.x+(w1),globalPoint.y+(h1);for (var i:int = 0; i 0没有 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, arr10, globalPoint2, arr20) /进行分离轴定理的先决条件/获取第一个矩形的轴， 在这里我全局例举出来，对于效率来说也是很高的/第一个轴var AsisArr:Array = /四条轴 / c-b new Point(arr12.x - arr11.x, arr12.y - arr11.y),/矩形A的轴/c-d new Point(arr12.x - arr13.x, arr12.y - arr13.y),/ b-a new Point(arr21.x - arr20.x, arr21.y - arr20.y),/矩形B的轴/b-c new Point(arr21.x - arr22.x,arr21.y - arr22.y);if (mirror1 0) /矩形A发生水平镜像，那么矩形A的两条轴要发生改变 /b-c(c-b的水平镜像)AsisArr0 = new Point(arr11.x - arr12.x, arr11.y - arr12.y),/矩形A的轴/b-a(c-d的水平镜像)AsisArr1 = new Point(arr11.x - arr10.x, arr11.y - arr10.y)if (mirror2 0) /矩形B发生水平镜像，那么矩形B的两条轴要发生改变 /c-d (b-a)AsisArr2 = new Point(arr22.x - arr21.x, arr22.y - arr21.y),/矩形B的轴/c-b (b-c)AsisArr3 = new Point(arr22.x - arr23.x, arr22.y - arr23.y)/矩形B的轴for (var i:int = 0; i 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的最小标量值时，/那么当投射到轴上时，我们的对象就会发生重叠var rect1MinMax:Array = getScalarValue(rectArr1, Ax);/第一个矩形的最小标量值和最大标量值var rect2MinMax:Array = getScalarValue(rectArr2, Ax);/第二个矩形的最小标量值和最大标量值/开始判断是否重叠if (rect2MinMax0 rect1MinMax1 |rect2MinMax1 rect1MinM