基于分离轴定理的碰撞检测算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于分离轴定理的碰撞检测算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：在游戏开发中，为了不使游戏中的物体相互穿越，需要使用碰撞检测技术来约束场景中物体的行动，本文比较了常用的几种碰撞检测算法的优劣，探讨了分离轴定理在碰撞检测中的应用及优势。
关键词：碰撞检测 包围盒 凸多边形 分离轴定理
中图分类号：TH721 文献标识码：A 文章编号：1007-9416(2012)08-0102-01
无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量游戏引擎是否完善的标准。好的碰撞检测要求人物在场景中可以平滑移动，在各种前进方向被挡住的情况下都会尽可能地沿合理的方向滑动而不是被迫停下，不会在特殊情况下穿墙而掉出场景。因为碰撞现象符合日常生活中的常识。如果出现Bug，很容易被人发现，例如人物无缘无故被卡住不能前进或者人物穿越了障碍。所以，碰撞检测的重要性不言而喻。
1、常见的碰撞检测算法
最为精确的碰撞检测算法是像素检测算法，即对物体的每个像素进行测试，当像素出现重叠，即为碰撞，但这种算法的计算量很大，在移动设备上会严重拖慢游戏的运行速度。，所以很少使用。当精确度要求不高时，可以用包围球算法，即用物体轮廓的外接圆把物体包围起来，这样要测试两个物体是否碰撞，只需要计算两个圆之间的距离是否大于两个圆的半径之和，如果大于，则说明没有碰撞，反之则碰撞。由于大多数情况下包围球的紧密型和简单性都不够理想，所以很少单独使用。另外一种AABB（axially aligned bounding box）即沿坐标轴包围盒算法，即把物体抽象成一个边和坐标轴平行的矩形，简单性好，但是紧密型要差。还有OBB（oriented bounding box）即方向包围盒算法，紧密型最好，但是计算量要大一些。一般的精确度完全可以胜任，计算量也在移动设备可承受的范围，所以比较常用。OBB包围盒的碰撞检测算法一般用的是分离轴测试算法。
分离轴定理（Separating Axis Theorem，SAT）提出，如果能找到一条轴，使得两个物体在该轴上的投影互不重叠，那么着两个物体就是不相交的。所以问题的关键如何找到这条轴。
这种算法只适用于凸多边形，所谓凸多边形，就是把一个多边形任意一边向两方无限延长成为一条直线，如果多边形的其他各边均在此直线的同旁，例如三角形，四边形，六边形，圆形等。对于非凸多边形，可以将其分解为多个凸多边形。算法还可以处理重叠的问题，并促使重叠的物体分离。
在2D的情况下，两个多边形每条边的法向量包含了这条轴的所有可能性。所以我们只需要枚举两个多边形的每条边的法向量即可。2D向量的法向量即是垂直于这个向量的一个向量，向量（X,Y）的法向量可以表示为（Y,-X）或（-Y,X），这个算法不需要考虑方向，所以任选一种即可，然后分别计算这两个多边形的所有点在此向量上的投影，并求出最大最小区域，如果没有重合，那么直接确定这两个多边形不重合，如果有重叠，那么就计算出相交的最小深度及其方向（推动向量，称为MTD，用于把两个物体推开）并继续判断下一条边的法向量。步骤为：
(1)计算多边形一条边的法向量。
设这边的两个顶点为（x1，y1）和（x2，y2），那么这条边就可以用向量表示为（x1-x2,y1-y2）,法向量为（y2-y1,x1-x2）。
(2)分别计算每个多边形的每条边在这个法向量上的投影，找出最大值和最小值。
设边的向量为（x1，y1）,法向量为（x2，y2），那么边在法向量上的投影Dot的计算方法为：
Temp1=x2*x2+y2*y2;Temp2=x1*x1+y1*y1;
Dot_x=Temp2*x2/Temp1;Dot_y=Temp2*y2/Temp1;
Dot=Dot_x*x2+ Dot_y*y2;
对多边形的每条边计算出Dot，并找出最大值和最小值。
(3)比较两个多边形的最大值和最小值是否有交集，如果有交集，则转到（1）继续计算下一条边的分离轴，如果没有则说明找到了一条轴，使两个物体在这条轴上的投影不重叠。说明这两个物体没有碰撞，可以结束计算。如果找不到这样的轴，则说明物体重叠，计算出点积值最小的那条分离轴，即推动向量。在碰撞反馈中，让两物体按一定的比例沿推动向量向相反方向分开即可。
3、分离轴碰撞检测算法的优化
由于分离轴算法计算量比较大，所以实际用的时候要和其他算法结合起来来减少计算量。常用优化策略有一下这些：
(1)每两个物体只检测一次。
(2)物体先进行粗略的包围球测试，再进行精确一些的AABB包围盒测试，通过之后再进行分离轴测试，这样可以减少很多不必要的计算量。
(3)对于OBB包围盒来说，多边形的四条边是两两平行的，所以每个多边形只需要测试两条边，两条分离轴。
4、结语
分离轴测试检测算法相对于像素检测算法少了一些精确度，但是省去了很多的计算量；相对于包围球，包围盒算法多了一些计算量，但是提高了很多的精度。经过过滤优化之后，分离轴测试算法完全可以胜任移动设备上的碰撞检测任务。而且这种算法基于向量数学，可以扩展到3D，值得深入研究。
参考文献
[1]陈雷,伊明,陈二雷.基于包围盒的碰撞检测算法研究[J].电脑知识与技术(学术交流),2007.14.
[2]章勤,黄琨,李光明.一种基于OBB的碰撞检测算法的改进[J].华中科技大学学报(自然科学版),2003.1.
[3]董向阳,张佐刚.基于层次包围盒的碰撞检测算法研究[A].2006系统仿真技术及其应用学术交流会论文集[C],2006.
[4]董向阳.基于OBB的碰撞检测算法研究[D].辽宁工程技术大学,2007.
[5]潘振宽,李建波.基于压缩的AABB树的碰撞检测算法.计算机科学,2005.02.
[6]陈尚飞.基于分离轴理论的有向包围盒重叠测试算法[J].广西科学院学报,2005.3.