分离轴定理用于判断两个凸多边形是否碰撞.原理的理解如下:
有两个凸多边形,在一个方向上,用一束光照射,得到两个凸多边形的投影.如果投影有间隙,说明这两个凸多边形没有碰撞.如果没有间隙,可能
是碰撞的.再换一个方向,用光照射,如果还没有间隙,则可能是碰撞的.再换方向...如此反复,直到所有方向照射的投影都没有间隙,则是碰撞的.
只要在一个方向上有间隙,就能说明没有碰撞.
只能用于凸多边形,即内角小于180度的多边形.例如正五边形.五角星不是凸多边形,不适用此法.
凸多边形有个判断方法,如果连接所有定点的线段都在多边形内,则是凸多边形,否则不是.
从一个方向,光束照射在凸多边形上,得到的投影.下图假设从上往下,从左往右,两个方向照射,得到的投影用多边形的颜色区分.
观看投影,发现两个方向的投影都有重叠.可是事实上,这两个物体并没有碰撞.
按照定义,两个物体没有碰撞,那么一定能够找到有间隙的投影.
下图黄色线就是这个间隙
如上图,阴影所在的线称为"投影轴".如上上图,投影轴就是画布的下边界和右边界.
这条轴是怎么确定的呢?由图可见,这投影轴并不一定要在图中所示位置,是可以靠前或者靠后,只要与轴平行.其实,投影轴有无数条
由图可见,投影轴与投射光线垂直.所以,投影轴其实由投射光线决定.
那么,投射光线的方向怎么决定?应该说是,从哪个方向做投影.事实上,可以从360度的全部方位进行投影.
上图就是所有360度方位中的一个方位,此方位的投影找到了间隙,说明了那两个物体没有碰撞.
SAT定理可以这样看,对于上图的两个物体,拿电灯(点光源)照射,看阴影是否有间隙.将电灯围着两个物体转一圈(360度),如果阴影始终是
有重叠的,那说明碰撞了.如果在任何一个角度上,阴影有间隙,那就说明没有碰撞.
程序上不用检测360度全方位,只需要检测一些特定的角度就可以.
凸多边形的每一条边就是一个投射光线的方向.如上图,两个物体一共有7条边,那么只要检测这7个方向就能判断是否碰撞
而且,只要有一个方向发现阴影有间隙,就说明没有碰撞.剩下的方向就不用检测了
实现第一个方法,给定一个多边形,检测它的投影.按边的顺时针方向,求出凸多边形在所有边的投影轴上的投影.
此方法的关键点是要计算出投影轴的合适位置和投影点的位置.每一条投影轴上有n-1个顶点的投影(投影光线(边)所在的两点重合了)
下图按方向 ab - bc - cd - da ...分别画出投影轴和投影点,这两个凸多边形有9条边,所以有9条投影轴
在绘画时,使用坐标系变换.例如,ab边为投影光线,那么,将canvas坐标系平移到a点,再旋转ab线段的斜率对应的角度,
(即以ab线段所在的直线为X轴,a是原点,b是正方向上一点).这时,投影轴在变换后的坐标系中,是一条与Y轴平行的直线.
此时再计算出其它顶点在新坐标系的坐标值,这些点的Y值的最大值和最小值就是投影轴的Y值端点范围.而X值中的最大值加上
合适的距离(如20px)就是投影轴的X值.这样,投影轴就画出来了.投影轴上各顶点的投影点,它们的X值就是投影轴的X值,而Y值
就是这些点的Y值.
蓝色多边形
橄榄色多边形
上图,投影点有重合的投影轴,是青绿色的.
实现上面的投影检测后,就已经可以判断碰撞了.判断投影点是否有空隙,只要判断两个凸多边形的投影点坐标是否有交集
举例说明,在一个投影轴上,多边形1的投影点的Y坐标(排序后)为[1,3,6,9],多边形2的Y坐标为[10,12,13],那么显然是没有交集的
所以不碰撞.如果是[1,2,5]和[4,8,9]那么是有交集的,多边形2的第一个点[4],在多边形1的第2个点和第3个点之间[2,5],此时要
判断下一个投影轴,按照SAT定义,如果所有投影轴都有交集,那么两个多边形是碰撞的
为什么只检查Y(或者X,投影轴水平时)坐标就能判断交集呢?因为点都在同一条线上(投影轴,投影点).可以当作数轴看待.
两个圆形碰撞检测,只需要判断两个圆的圆心距离是否小于两个半径之和
下图r1,r2半径之和小于r1r2圆心的距离,所以不碰撞.r3,r4圆心距离小于半径之和,所以碰撞了
圆可以从0~360度方向投影,和多边形不同,圆的边可以是无数条,没法用边做投影光线方向.
选取半径为投影光线方向,从与X轴重合的半径开始,顺时针每120度,取一条半径做一个投影
圆的投影点总是两个,距离就是圆的直径.
在圆与多边形碰撞检测中,多边形的投影轴仍然由边来定.而圆的投影轴,则由圆心与多边形顶点的连线来定
而且只需要一条连线,就是最短的那一条.所以要确定投影轴,要计算出与圆心最近的顶点.
<<H5核心技术图形动画与游戏开发(David Geary)>> 355 圆与多边形
圆与多边形碰撞检测,一共有N+1条轴,N边形,N条,圆1条(下图绿色的线段)
圆
多边形
实现方法1,传入两个多边形顶点坐标数组,返回是否碰撞
实现方法2,传入1个多边形顶点坐标数组和一个圆的圆心和半径,返回是否碰撞
satCheck.polyons()
satCheck.polyonCircle()
多边形的每条边就是投影光线,从一点起,顺时针走一圈,得到所有投影光线方向
如果是圆与多边形,圆的投影轴只需要一条,就是圆心与多边形最近的顶点的连线.投影光线则是与这投影轴垂直的线,从圆心点开始,到与圆的交点
计算投影点坐标的方法,可以利用坐标系变换.先平移再旋转.以投影光线的起点为新原点做平移变换,再以投影光线的斜率对应角度做旋转变换
然后在这个新坐标系上,计算出所有点的新坐标.对于多边形,除了投影光线起点无需计算(为新坐标系0,0点),其它顶点需要计算.对于圆,有两个点 ,
与投影光线垂直的那条圆的直径,在圆周上的两个点.
投影轴在新坐标系中,实际上是N条与Y轴平行的线(也能是Y轴).因为投影轴与投影光线垂直,而坐标系变换办法,使得X轴与投影光线重合.
投影点在投影轴上的坐标,其X值都是一样的.而其Y值就是多边形或圆在新坐标系中的Y值.这时,投影点就像一条数轴,可以用判断集合是否有交集的
办法.集合的边界就是多边形或圆的投影点Y值的最大值和最小值.判断如果有交集,则说明多边形和多边形(或圆)可能碰撞,如果没有则说明没有碰撞.
根据SAT,程序只要检测到没有交集就可以退出.而判定为碰撞,程序要检测所有投影轴都存在投影点交集.