一些碰撞算法

92 阅读 0 评论 61 点赞

我是靠谱客的博主老迟到人生，最近开发中收集的这篇文章主要介绍一些碰撞算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前段时间，项目中需要改进一下碰撞算法。我查了很多资料。。最后完成了http://hi.baidu.com/jrsnail/blog/item/007e9c7faf1ba90328388a8d.html这个对我影响很大。。

我们以前的算法是用的凸包算法。就是检测点是否在一个矩形中。算法分析：http://kevinew.blog.sohu.com/14735858.html有详细介绍，通过左转判定公式，只需判断 x1*y2-x2*y1 的正负值,为正说明 p1 到 p2 为左转. 其实就是判断一个向量到另一个向量是逆时针转还是顺时针转，如果点d在矩形边四条边的左边或都在四条边的右边，说明这个点在矩形内。。。

这个是我们以前的算法，后来，我把算法改成了分离轴算法，

这一系列的文章并不是我的原创,如果有同仁需要查看英文的原文的话,地址我曾经给出过，英文水平是有限的,如果有什么地方没有翻译清楚,可以向发邮件或者直接留言.
需要说明的是这里的范例都是基于OPENGL的代码。
2D多边形碰撞检测和反馈
介绍
这是一篇论证如何在2D动作游戏中执行碰撞检测的文章（Mario,宇宙入侵者等），为了保证它的高效性和精确性，碰撞检测是以多边形为基础的，而不是以sprite为基础。这是两种不同的设计途径。
基于sprite的检测执行的是检测sprites的像素的交叉，以这种方式来检测碰撞。多边形是使用向量数学来精确的计算点，时间和碰撞的方向。当多边形只是一种近似sprite自身的时候，它就超越了sprite系统。
表现出了更精确的物理现象，例如弹性，摩擦，在一个随机的形状中来处理斜坡。
碰撞检测相对一个高速的sprite来讲是更加的精确的。在一个基于sprite的系统中，对象有可以在一个强力的跳跃中因为速度太快而相互穿越。
这是一个基于向量数学的系统，所以可以扩展到3D，但是一个sprite碰撞系统被完全的限制到了2D中。
特色：
因为运算法则的限制，系统只能操作凸多边形，例如三角形，矩形，五边形，圆形。在一个非凸多边形中，你可以将这些多边形分成三角形来处理。
无论是快速或者慢速的多边形，他的处理方式都是一样的。不管对象的移动有多快，碰撞也不会丢失的。他也可以来处理交叠，分开已经交叉的对象。
里面的范例也有线段的交叉。这可以用来模拟子弹。
它也提供了一些简单的物理系统，模拟弹力，一些基本的摩擦力和静摩擦力。在斜坡上的一些特性它也可以模拟。
这里也有一个刚体系统的例子，引用的是Chrsi Hecker的物理文章。
局限性：
碰撞的种类，我的意思是它不能顺序的处理碰撞。在一个快速的对象中这可能会有问题。一旦一个碰撞被检测了，它便会直线的离开。你可以检测到第一个碰撞并处理它，然后再找到其他的碰撞。但是在一个2D的动作游戏中，这是很具有杀伤力的。
必要条件：
一些普通的原料，一个编译器，范例是基于GLUT（GL开发包）的框架，所以需要下载一个小的GLUT SDK和一个兼容opengl的显卡。
你还需要对向量数学有一个基本的了解。这里的文章不准备对点乘进行讲解，但是它可以帮助你对向量的操作有更好的了解。
对于刚体，你需要对Chris Hecker的文章仔细的阅读一下。它需要你付出更多，但是它是值得的，并不是多么的困难。
内容列表：
文章1：分离轴的方法
文章2：扩展应用于碰撞反馈的分离轴的方法。
文章3：对快速移动的对象来检测他的碰撞。
文章4：基本的Arcade碰撞反馈
文章5：处理旋转
文章6：计算碰撞点
文章7：刚体动力学。
分离轴的方法：
这是碰撞检测的核心，原理是非常简单的，也非常的容易实现。它也是快速和稳定的，因为没有除法在运算中被使用。我将会带给大家一个简单的两个BOX碰撞测试的例子。

该运算法则试着来确定两个对象中的一个合适的面。如果有这样的一个面存在，如果有这样的面存在，说明对象是分离的，没有交叉。
为了确定对象是否是分离的。只要将这个对象投影到这个平面的法线上，然后比较它们之间的间隔看他们是否交叉。
所以，很明显有无数个边能够适合这两个分离的对象，但是已经证明你只要测试少数的几个面就可以了，对于上面图形中的两个BOX，你可以看到边的法线是形状B的边。
从上面的这些形状中可以发现，那些即将被测试的分离面是两个BOX的边的法线。对于这两个BOX而言，你只需要测试4个分离的面。在这4个面中，一旦你发现一个分离面分隔了这两个BOX。你就可以知道了这两个BOX是分离的。然后返回一个没有碰撞的标记。
如果这4个面没有分隔这两个BOX，那么这两个BOX肯定是交叉的，说明他们有一个碰撞。
扩展到一般的多边形，该运算法则仍然是适用的。只不过是测试的边变化了。那些分离的面的法线是和每个多边形的边的垂直方向是平行的。在下面的图形中，你可以看到有两个分离面被测试。在红色的面被测试的时候，你可以看到那两个间隔是交叉的，但是在蓝色的被测试的时候，间隔并没有交叉。所有蓝色的面是分离面，对象因此是没有交叉的。

现在，我们已经有一个检测他们是否碰撞的法则了。这些代码也能够被扩展为3D。
所有的分隔轴都需要被测试
计算的是每一个多边形所在的轴的间隔（分离面的法线）
测试这些间隔是否交叉。

bool Intersect(Polygon A, Polygon B)
{
for(I = 0; I < A.num_edges; I ++)
{
Vector N = Vector(-A.EdgeDir[I].y, A.EdgeDir[I].x);
if (AxisSeparatePolygons(N, A, B))
return false;
}
for(I = 0; I < B.num_edges; I ++)
{
Vector N = Vector(-B.EdgeDir[i].y, B.EdgeDir[I].x);
if (AxisSeparatePolygons (N, A, B))
return false;
}
return true;
}

void CalculateInterval(Vector Axis, Polygon P, float& min, float& max)
{
float d = Axis dot P.vertex[0];
min = max = d;
for(I = 0; I < P.num_vertices; I ++)
{
float d = P.vertex[I] dot Axis;
if (d < min)
min = d;
else
if(d > max)
max = d;
}
}

到这里，这个计算两个2D多边形碰撞的运算法则是非常快和稳定的。边的方向不一定是单位化的，所以你可以避免将边的方向都存储起来，你可以直接根据多边形的顶点来构建这些边的方向。
for(J = A.num_vertices-1, I = 0; I < A.num_vertices; J = I, I ++)
{
Vector E = A.vertex[I] – A.vertex[J];
Vector N = Vector(-E.y, E.x);

if (AxisSeparatePolygons(N, A, B))
return false;
}

最先看到是英文版的算法。。后来进一步了解算法时，发现了这个文章。。觉得讲的挺详细，，就记了下来。。英文网站是：

http://www.gamedev.net/page/resources/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604