《旋转矩形碰撞检测》由会员分享，可在线阅读，更多相关《旋转矩形碰撞检测（20页珍藏版）》请在金锄头文库上搜索。
1、2D 旋转矩形碰撞检测(极力推荐)-支持水平镜像 (垂直镜像同理，可以自己编写)数学知识 2010-10-05 14:28:40 阅读 734 评论 0 字号：大中小 订阅 最近在用 Flash AS3.0 写一个 ACT 游戏，由于要检测攻击碰撞和被攻击碰撞(没有使用像素级碰撞-没有必要) ，遇到矩形碰撞的问题，就是无法全部满足旋转矩形的需求。MovieClip.hitTestObject()对旋转矩形是不适用的，且非常糟糕。在此自己写了一个。对于这种 2D 动作游戏来说矩形碰撞是绝对满足要求的，不需要使用像素级碰撞来检测碰撞。 一、必知的一些概念1， Separating Axis The
2、orem(SAT)（分离轴定律）引用:http:/vision.twbbs.org/jen/?p=78什么是 STA?SAT 為一種可快速偵測不規則凸多邊是否碰撞的演算法，他的概念如下 :給予兩個凸多邊形物體，如果我們能找到一個軸，使得兩個在物體在該軸上的投影互不重疊，則這兩個物體之間沒有碰撞發生，該軸並稱為其 Separating Axis。 (紅色軸線)對於 2D 的例子來說，可能存在的 Separating Axis 為垂直於該多邊形各個邊的軸(紅色軸線)。因此，若我們要檢查兩多邊形是否碰撞，就去檢查兩多邊形在每個所有可能的軸上的投影是否重疊。如果我們找到一個軸，使得兩多邊形在該軸上的投
3、影互不重疊，則我們就可以知道這兩個多邊沒有碰撞發生。(知道判断不重叠就可以退出了)如果是 3D case 的話，則需要考慮的可能的 Saparating Axis 包括各個面的 normal，還有每個面中，兩兩 edge 之外積所形成的向量。Metanet Software 有一個很棒的 互動式 SAT 教學David Eberly 也有發表一篇比較偏講解 SAT 理論方面的文章Intersection of Convex Objects: The Method of Separating Axes二、旋转碰撞讲解当我着手学校的项目时,我发现必须对翻转的精灵之间实现碰撞检测, 开始想到了包围盒
4、但因为对每个像素检测是很耗时而且也没必要,经过几天的摸索, 我用 SAT(separating axis theorem)高效的实现了它,当我把我的方法结实给我的同学和实验室的技术人员时,我意识到游戏开发组织可能通过清晰而彻底解释过程中获益. 此而外线性代数,向量数学是很有用的, 但不影响对这篇文章的理解.SAT(Separating Axis Theorem)Separting Axis Theorem 指出了一对不处于碰撞情况的凸多变形 ,有且一条相对于多变形一条边的垂直轴,并且两个多边形的投影顶点无重叠.如果我们投影这个两个多边形顶点(我们正在对每个垂直于每个多边行边的轴进行测试),然后
5、我们检测每个多边形的重叠并且存在碰撞,即使是一个轴没有没有重叠, 那么碰撞是不可能的,实质上它到底有什么意义呢.这种解决方法适用对碰撞检测的可能性,甚至是交叉碰撞. 图 1, 交叉碰撞我们在深入碰撞算法之前,使用这个方法得有具备一些前提. 首先,虽然分离轴理论可以用来在凸多边形之间检测碰撞,但矩形是在 2D 中通常碰撞方式,所以我们假设你使用几个矩形.此外还得假设你可以把矩形转换为带有四个向量的结构体, 他们每个代表一个角,以标记或组织的方式,而知道哪个角是哪个,( 具体来说, 我们需要去识别哪些角是相临的-如果左上角一直转到它在矩形的低部为止, 只要保持边与左上角和右下角标签相联系.方法检查
6、两个相互旋转矩形碰撞的确是个问题,什么时候能决定他们不相撞. 最简单的交叉检测使用 m$的 IntersesectRect()函数会检测最大/ 最小的矩形 B 的值是否在矩形 A 的最大和最小的值内.这种对方对对称轴矩形工作得很好,但在处理旋转矩形时,我们采用更为复杂的方式图 2.标准基于包围的碰撞检测正如你所见的那样.B 的最小值 x 位于被 A 的最大和最小 x 所定义的空间中.此外 ,B 的最小值 y 位于被 A 的最大和最小 y 定义的空间中的.使用简单的基于包围的碰撞检测，这将登记为碰撞，反之这不会步骤这个方法的第一步就是确定我们要往上投影向量的轴分离轴理论（SAT)指出了, 我们必
7、须有一个轴，垂直于我们两个多边形的每个边 图 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
8、.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.yAxi
9、s2.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垂直镜像的四个轴
10、,替换为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 的右上角合向量减去左上角的合向量, 其他的也是如此.这里给了我们四个轴, 每个垂直于一个矩形的两个对边,这表示对于每个边
11、上,我们都有一个垂直于它的轴. 图 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)表示:带入公式:所以, 在这
12、个例子,A.UR 的 x 坐标投影到 Axis 1 是 3.6,而 y 坐标为 4.8图 5.投影到 Axis1 上向量步骤 3第三步在这个算法中是计算标量值，这将使我们能够确定每个矩形的最大和最小投影向量。虽然可能很自然的使用标准(长度)向量,如果是一个负坐标那么会出错的，那么就返回一个正标量值。最简单最方便的解决方案是用点乘以每个轴的向量。这将给予我们一个毫无意义的标量值，无论怎么样，这个值指出了在轴中向量的位置。使用我们上面的例子： 图 6. 最小和最大标量值步骤 4现在已确定矩形 A 和 B 的最大和最小( 我们已经计算过了)标量值。如果 B 的最小标量值=A 的最小标量值时，那么当投
13、射到轴上时，我们的对象就会发生重叠。 图 7. 没有重叠=没有碰撞重复在每个轴上重复步骤 2 和 3,4。如果所有的轴都显示重叠就表示碰撞，如果有一个轴没有重叠就表示没有碰撞。 优化下面几件事可以优化算法： 如果你找到一个轴不碰撞那么你应该立刻停止检测碰撞。记住，分离轴定理说，如果两个多边形碰撞所有轴是垂直的多边形的边会出现重叠。这意味着，如果一个轴显示没有重叠，那么碰撞是不会发生的，你应该退出，避免不必要的数学计算。 把矩形 B 转换为矩形 A 的本地空间。为了做到这些，你必须在本地空间中操作这些矩形然后转化矩形 B 为世界空间，在就是矩形 A 世界空间的逆变换，然后把矩形 B 添加到矩形
14、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
15、:Sprite = new Rect1();/创建一个矩形private var rect2:Sprite = new Rect1();这两个对象是一个 MovieClip，我使用的是 SWC 文件，里面就是一个 Rect1 类。注意要想正常使用下面类，就必须按照下面几个条件：1: 要碰撞的矩形，在定义元件时必须指定其中点作为其帧原点2: rorationRectCollide 参数给予的旋转角度必须是全局相对于舞台的角度，可由下列公式来获取发生旋转的主容器(也是最大最外面的总容器).rotation+要碰撞的元件.rotation* 主容器.scaleX3: 指明是否发生了水平镜像，由主容器
16、来决定。主容器.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 中的 s1s1 旋转角度=cap.rotation+s1.rotation*cap.scaleX;s3 中的 s1s1 旋转角度:先算出 s3 的实际旋转角度=cap.rotation+s3.rotation*cap.scaleX;在算出 s1 的实际旋转角度=s3.rotation+s1.rotation*s3.s
