2D旋转矩形碰撞检测(极力推荐)----支持水平镜像(垂直镜像同理，可以自己编写)
数学知识 2010-10-05 14:28:40 阅读734 评论0 字号：大中小 订阅
最近在用Flash AS3.0写一个ACT游戏，由于要检测攻击碰撞和被攻击碰撞(没有使用像素级碰撞----没有必要)，遇到矩形碰撞的问题，就是无法全部满足旋转矩形的需求。MovieClip.hitTestObject()对旋转矩形是不适用的，且非常糟糕。在此自己写了一个。对于这种2D动作游戏来说矩形碰撞是绝对满足要求的，不需要使用像素级碰撞来检测碰撞。
一、必知的一些概念
1，Separating Axis Theorem(SAT)（分离轴定律）
引用:vision.twbbs/~jen/?p=78
什么是STA?
SAT為一種可快速偵測不規則凸多邊是否碰撞的演算法，他的概念如下:給予兩個凸多邊形物體，如果我們能找到一個軸，使得兩個在物體在該軸上的投影互不重疊，則這兩個物體之間
沒有碰撞發生，該軸並稱為其Separating Axis。 (紅色軸線)
對於2D的例子來說，可能存在的Separating Axis為垂直於該多邊形各個邊的軸(紅色軸線)。
因此，若我們要檢查兩多邊形是否碰撞，就去檢查兩多邊形在每個所有可能的軸上的投影是否重疊。
如果我們找到一個軸，使得兩多邊形在該軸上的投影互不重疊，則我們就可以知道這兩個多邊沒有碰撞發生。(知道判断不重叠就可以退出了)
如果是3D ca的話，則需要考慮的可能的Saparating Axis包括各個面的normal，還有每個面中，兩兩edge之外積所形成的向量。
Metanet Software有一個很棒的互動式SAT教學
David Eberly也有發表一篇比較偏講解SAT理論方面的文章
Interction of Convex Objects: The Method of Separating Axes
reply二、旋转碰撞讲解
当我着手学校的项目时,我发现必须对翻转的精灵之间实现碰撞检测,开始想到了包围盒
但因为对每个像素检测是很耗时而且也没必要,经过几天的摸索,我用SAT(parating axis theorem)高效的实现了它,当我把我的方法结实给我的同学和实验室的技术人员时,我意识到游戏开发组织可能通过清晰而彻底解释过程中获益.此而外线性代数,向量数学是很有用的,但不影响对这篇文章的理解.
SAT(Separating Axis Theorem)
Separting Axis Theorem 指出了一对不处于碰撞情况的凸多变形,有且一条相对于多变形一条边的垂直轴,并且两个多边形的投影顶点无重叠.
contactus如果我们投影这个两个多边形顶点(我们正在对每个垂直于每个多边行边的轴进行测试),然后我们检测每个多边形的重叠并且存在碰撞,即使是一个轴没有没有重叠,那么碰撞是不可能的,实质上它到底有什么意义呢.
这种解决方法适用对碰撞检测的可能性,甚至是交叉碰撞.
图1, 交叉碰撞
experiment怎么读
我们在深入碰撞算法之前,使用这个方法得有具备一些前提.首先,虽然分离轴理论可以用来在凸多边形之间检测碰撞,但矩形是在2D中通常碰撞方式,所以我们假设你使用几个矩形.此外还得假设你可以把矩形转换为带有四个向量的结构体,他们每个代表一个角,以标记或组织的方式,而知道哪个角是哪个,(具体来说,我们需要去识别哪些角是相临的---如果左上角一直转到它在矩形的低部为止,只要保持边与左上角和右下角标签相联系.
方法
检查两个相互旋转矩形碰撞的确是个问题,什么时候能决定他们不相撞.最简单的交叉检测使用m$的InterctRect()函数会检测最大/最小的矩形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个轴出来。其实和水平镜像一样。
requirement
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
business week 图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: 要碰撞的矩形，在定义元件时必须指定其中点作为其帧原点
