碰撞检测教程C

1、简介本文是阐述如何在2d动作游戏中进行精确而高效的碰撞检测。这里的碰撞是基于多边形而不是基于精灵的。这两者之间在设计上会有不同。基于精灵的碰撞检测是通过精灵之间的重叠的像素来完成的。而多边形使用向量数学来精确计算交点，时间和碰撞方向。虽然多边形仅仅是精灵的一个近似，但是它比精灵系统要高级。· 可以精确模拟逼真的简单物理学，例如反弹，摩擦，斜面的滑行· 碰撞检测可以更精确的用于高速精灵系统。在基于精灵的系统中，如果物体移动过快就会在跳过另一个物体。· 基于向量数学因此可以扩展到3d，然而精灵碰撞系统被严格限制在2d的情况下。特性本文使用的算法只适用于凸多边形，例如三

2、角形，四边形，六边形，圆形。对于非凸多边形，你可以将其分解为多个凸多边形，例如三角形。算法可以用于快速移动或慢速移动的多边形。不管物体移动多快，碰撞都不会丢失。它也可以处理重叠的问题，并促使交叠物体分离。演示也支持分割多边形交叉。这可以用于子弹的建模。同时提供了简单的物体系统，弹力，一些基本的摩擦和静摩擦力。用于确保物体不会从斜面上滑落。有一个刚体系统的例子，使用了chrsi hecker的物理教程。限制有序碰撞。就是说并不是有序的进行碰撞。这对于快速移动的物体会出现一定的问题。一旦碰撞被检测到，它就被直接处理了。理想状态下你可能需要找到一个碰撞点并处理它，然后寻找更多的碰撞。但是对于2d动作

3、游戏，这通常是不必要的。一、分离坐标轴方法这个方法是碰撞检测的核心。它的规则非常简单并且非常易于实现。这个方法也非常快并且非常可靠，因为计算中没有使用除法操作，下面给出一个简单的基于两个box的碰撞检测的例子。算法试图在两个物体之间找到一个合适平面，如果这个平面存在，那么物体就没有相交。为了测试物体是否是分开的，简单的方法是投影这个物体到平面的法线上，并比较两者之间的间距看二者是否重叠。显然有无数的平面可以用来分割两个物体。但是已经经过证明的是：你只需要使用一部分平面来进行测试，对于box从上图中可以看出平面的法线为box b的长轴。对于box来说需要测试的分割平面是那些法线等于两个box的轴

4、向的平面。因此对于两个box来说，你只需要测试4个分割平面即可。在这四个平面里，一旦发现一个分割平面可以分割box那么你就可以断定这两个box是不相交的。如果四个平面都不能分割box，那么这两个box一定是相交的，也就是出现了碰撞。可以扩展这个算法到普通的多边形，算法是相同的，只用需要测试的平面的数量改变了。并且分割平面在每个多边形边的垂直方向上又有一个法线。在下图中，你可以看到两个分割平面用于测试。在红色的平面上你可以看到两个间隔是重叠的。然而，在蓝色的平面上间隔是不重叠的，因此，蓝色的平面的是分割平面，因此物体是不相交的。现在，我们有一个算法来检测两个多边形是否是相交的。代码可以分为三个部

5、分：a)生成需要测试的分离轴b)计算每一个多边形在分离轴法线上的投影c)检测这些投影是否相交bool intersect(polygon a, polygon b) for(i = 0; i < a.num_edges; i +) vector n = vector(-a.edgediri.y, a.edgediri.x);if (axisseparatepolygons(n, a, b) return false; for(i = 0; i < b.num_edges; i +) vector n = vector(-b.edgediri.y, b.edgediri.x); if

6、 (axisseparatepolygons (n, a, b) return false; return true; void calculateinterval(vector axis, polygon p, float& min, float& max) float d = axis dot p.vertex0; /从坐标原点开始计算向量 min = max = d; for(i = 0; i < p.num_vertices; i +) float d = p.vertexi dot axis; if (d < min) min = d; else if(d

7、 > max) max = d; 算法检测2d多边形之间的碰撞，这个算法非常的快速和适用。边的方向不需要单位化，因此你可以避免存贮边的方向，并通过多边形的顶点直接得到边的方向。for(j = a.num_vertices-1, i = 0; i < a.num_vertices; j = i, i +) vector e = a.vertexi - a.vertexj; vector n = vector(-e.y, e.x); if (axisseparatepolygons(n, a, b) return false; 二、用于碰撞响应的扩展分离坐标轴方法检测多边形相交是非常有

8、用的方法，但是可以做更多的事情。当多边形相交时，我想将他们移开以避免他们相交。分离轴的方法可以非常好的用于这种情况，但是还需要作一些额外的工作。必须返回相交的深度，和推开多边形将它们分离的方向。相交的深度和方向的组合称为mtd，或者最小平移距离。这是用于将物体分离的的最小向量。为了计算mtd，我们可以使用分离坐标轴。 当物体相交时，我们可以计算两个物体在每一个分离轴上的投影间隔。两个间隔交叠的部分提供了一个推动向量，你需要将其应用到其中一个物体上以便物体在轴上的投影停止交叠“推动向量”你需要应用于a上将a推开，这样就可以使a和b分开。显然，不能沿着一个随机的轴来推开物体。候选轴是投影

9、在该轴上两个间隔之间交叠最小的那个。并且这个推动向量提供了最小平移距离。bool intersect(polygon a, polygon b, vector& mtd)  / 电位分离轴。他们被转换成推动      vectors vector axis32;      / 每个多边形最大的16个顶点的      int inumaxis = 0;      for(j = a.num_vertices - 1, i

10、 = 0; i < a. num_vertices; j = i, i +)                vector e = a.vertexi - a.vertexj;          axisinumaxis+ = vector(-e.y, e.x);           if (axisseparatepolygons(

11、n, a, b)              return false;            for(j = b. num_vertices - 1, i = 0; i < b.num_vertices; j = i, i +)                vector e = b.vertexi -

12、 b.vertexj;          axisinumaxis+ = vector(-e.y, e.x);               if (axisseparatepolygons (n, a, b)              return false;     

13、60;          / 找到所有的分离向量之间的mtd      mtd = findmtd(axis, inumaxis);      / 确保将向量a推动远离b      vector d = a.position - b.position;      if (d dot mtd < 0.0f)     

14、60;   mtd = -mtd;      return true;    bool axisseparatepolygons(vector& axis, polygon a, polygon b)        float mina, maxa;      float minb, maxb;      calculateinterval(axis, a, mina, maxa

15、);      calculateinterval(axis, b, minb, maxb);      if (mina > maxb | minb > maxa)          return true;      / 查找间隔重叠      float d0 = maxa - minb;      float

16、 d1 = maxb - mina;      float depth = (d0 < d1)? d0 : d1;      / 将分离轴为推力矢量（重新恢复正常的轴乘区间重叠）      float axis_length_squared = axis dot axis;      axis *= depth / axis_length_squared;      return false

17、;    vector findmtd(vector* pushvectors, int inumvectors)        vector mtd = pushvector0;      float mind2 = pushvector0 dot pushvector0;      for(int i = 1; i < inumvectors; i +)         

18、60;      float d2 = pushvectori * pushvectori;          if (d2 < mind2)                        mind2 = d2;           

19、   mtd = pushvectori;                      return mtd;   一旦得到了mtd向量，可以使用如下的方式将他们分开。 a.postion += mtd * 0.5f; b.position -= mtd * 0.5f;显然，如果物体a是静态的，那么b将被完全的mtd推开（b.position-=mtd）而a将不会被推开。三、对快速移动的物体做进一步

20、扩展上述方法处理慢速移动物体时会取得非常好的效果。但是当物体移动的非常快时，碰撞系统将失去准确性，丢失碰撞，或者允许物体之间相互穿越，这可不是我们所期望的。 这里我们还是使用分离坐标轴的方法，并进一步扩展，并使用该算法检测未来某时刻的碰撞和交叠。 原理还是相同的，可以使用下面的图片解释：现在需要使用投影数学。如果投影间隔没有相交，将速度投影到分离轴上，并计算两个间隔的碰撞时间。 相对于静态分离轴算法，我们需要测试一个扩展的轴。显然这个是速度矢量轴。 那么我们现在有3个选择：1 间隔交叠2 间隔不相交，但是将在未来某个时刻发生碰撞3&#

21、160;间隔不相交，并且不会在未来发生碰撞第三种可能性意味着物体不会在该帧处发生碰撞，而且分离轴真正分离了物体。因此物体不会发生碰撞。 axisseparatepolygons()函数将反映这种现象，并返回重叠量或者碰撞时间。为了区别两者，当检测到交叠时，将返回一个负值。如果检测到未来的碰撞，将返回一个正值。该函数看起来如下： bool axisseparatepolygons(vector axis, polygon a, polygon b, vector offset, vector vel, float& t, float tmax);这里offset是多边

22、形a和多边形b之间的相对距离，并且vel是多边形a相对于多边形b的相对速度。 求解碰撞平面的算法与mtd非常相似。只是碰撞将优于交叠，如果检测到未来的碰撞，将选择最新的一个。 如果没有发现碰撞并且只检测到了交叠，那么就像以前一样，选择交叠最小的那个轴。 碰撞检测函数将返回碰撞的法向，还有碰撞的深度（负值）和碰撞时间（正值）之一。最后的伪代码如下bool collide(const vector* a, int anum,const vector* b, int bnum,const vector& xoffset, const vector& xv

23、el,vector& n, float& t)        if (!a | !b) return false;              / all the separation axes      / note : a maximum of 32 vertices per poly is supported      vector xaxis64

24、;float taxis64;      int inumaxes=0;      xaxisinumaxes = vector(-xvel.y, xvel.x);      float fvel2 = xvel * xvel;      if (fvel2 > 0.00001f)                if (!

25、intervalintersect( a, anum, b, bnum, xaxisinumaxes, xoffset, xvel, taxisinumaxes, t)              return false;          inumaxes+;            / 测试分离轴a    

26、  for(int j = anum-1, i = 0; i < anum; j = i, i +)                vector e0 = aj;          vector e1 = ai;          vector e = e1 - e0;       

27、   xaxisinumaxes = vector(-e.y, e.x);                   if (!intervalintersect( a, anum, b, bnum, xaxisinumaxes, xoffset, xvel, taxisinumaxes, t)              return fals

28、e;         inumaxes+;            / 测试分离轴b      for(int j = bnum-1, i = 0; i < bnum; j = i, i +)                vector e0 = bj;     

29、    vector e1 = bi;          vector e = e1 - e0;          xaxisinumaxes = vector(-e.y, e.x);          if (!intervalintersect( a, anum, b, bnum, xaxisinumaxes, xoffset, xvel, taxisi

30、numaxes, t)              return false;         inumaxes+;              if (!findmtd(xaxis, taxis, inumaxes, n, t)          return false

31、;      / 确保多边形被彼此推开。      if (n * xoffset < 0.0f)         n = -n;      return true;  bool axisseparatepolygons ( vector n, polygon a, polygon b, vector offset, vector vel, float &t, float tmax)

32、        float min0, max0;      float min1, max1;      calculateinterval(n, a, min0, max0);      calculateinterval(n, b, min1, max1);           float h = offset dot n;  &#

33、160;   min0 += h;      max0 += h;      float d0 = min0 - max1; / 如果重叠, do < 0      float d1 = min1 - max0; / 如果重叠, d1 > 0      / 分离，测试动态间隔      if (d0 > 0.0f | d1 > 0.0f)  &

34、#160;             float v = vel dot n;          / 速度很小，所以只能进行重叠测试。         if (fabs(v) < 0.0000001f)              return false; 

35、60;       float t0 =-d0 / v; / 时间影响d0达到0          float t1 = d1 / v; / 时间影响d0达到1          / 排序时间。          if (t0 > t1)         

36、60;             float temp = t0;              t0 = t1;              t1 = temp;                 

37、  / 取最小值          taxis = (t0 > 0.0f)? t0 : t1;          / 交叉时间太晚或时间，没有碰撞          if (taxis < 0.0f | taxis > tmax)            

38、0; return true;          return false;            else                / 重叠。得到的区间，作为最小的|d0|和|d1|        / 返回负数以标记为重叠     

39、     taxis = (d0 > d1)? d0 : d1;          return false;        bool findcollisionplane (vector* axis, float* taxis, int inumaxes, vector& ncoll, float& tcoll)        / 先找到碰撞   

40、60;  int mini = -1;      tcoll = 0.0f;      for(int i = 0; i < inumaxes; i +)                if (taxisi > 0.0f)          if (taxisi > tcoll)   

41、60;                            mini = i;                  tcoll = taxisi;             

42、;     ncoll = axisi;                  ncoll.normalise(); / 将轴                              / 发现了碰撞   

43、;   if (mini != -1)          return true;      / 不，找到重叠      mini = -1;      for(int i = 0; i < inumaxes; i +)                float n = a

44、xisi.normalise(); / 轴线长度          taxisi /= n; / 正常区间重叠太          / 记住，这些数字是负的，所以采取最接近0          if (mini = -1 | taxisi > tcoll)              

45、          mini = i;              tcoll = taxisi;              ncoll = axisi;                    

46、;       return (mini != -1);  现在，你拥有了一个可以检测未来碰撞的的检测系统，或者当重叠的时候，返回碰撞平面和碰撞深度/时间四、 基本弧碰撞响应下面要作的是用给定的量将两个物体分离，并添加一点摩擦和一些静态摩擦，以便使物体静止在斜面上。该部分使用简单的速度影响算法。同样，为了使碰撞响应更加真实，物体被赋予了质量（更好的是质量的倒数）。质量的倒数是比较常用的，该值为零意味着该物体具有无穷大的质量，并因此不能移动。同时速度响应中使用质量的倒数具有更好的物理精确性。现在我们知道多边形a在位置pa具有速

47、度va，与位置pb速度vb的多边形b发生碰撞。ncoll和tcoll定义了碰撞平面。如果碰撞前是交叠的，首先分离两个物体，如下：if (tcoll < 0)  if (a.invmass = 0)         pb += ncoll * tcoll;     else if (b.invmass = 0)         pa -= ncoll * tcoll;  &

48、#160;  else              pa -= ncoll * (tcoll * 0.5f);         pb += ncoll * (tcoll * 0.5f);      然后可以调用碰撞响应的代码，为了简化，我们可以考虑一个粒子碰到一个平面上这里v表示粒子的进入速度，v是粒子发生碰撞后的速度，n为平面的法向。v

49、= v - (2 * (v . n) * n理想状态下，碰撞前后粒子的能量是相同的。但是我们可以给粒子的碰撞加入弹性系数v = v - (1 + elasticity) * (v . n) * n弹性系数的范围为0，1如果为零意味着粒子将沿着平面滑动，如果为1，粒子将没有能量损耗的弹开。同样我们可以加入一些摩擦。如果我们沿着碰撞的法线和碰撞平面方向分解速度，我们可以同时计算弹性系数和摩擦力。这里，速度被沿着平面的法向和平面分解。弹性系数将影响沿着平面法向的响应(vn)，摩擦力将影响速度的切向（vt）。同样摩擦系数的范围为0，1. 0意味着没有摩擦力，1意味着粒子将突然停止。vn = (v .

50、n) * n;vt = v - vn;v = vt * (1 - friction) + vn  * -(elasticity);对于静摩擦力，简单地在速度vt小于给定的值时设置vt为(0,0), 或者设置摩擦系数稍微比1大(1.001f)。现在，计算两个物体间的碰撞响应。原理是相同的。然而，计算是基于物体的相对速度的，物体将象上述一样受到影响。结果将添加到每一个物体上。 现在我们需要修改一下系数，因为现在我们使用了相对的概念vector v = va - vb; / 相对速度vn = (v . n) * n;vt = v - vn;if (vt.length()

51、 < 0.01f) friction = 1.01f;/ 响应v = vt * -(friction) + vn  * -(1 + elasticity);va += v * 0.5f;vb -= v * 0.5f;这里使物体a和物体b具有相同的响应结果。为了使结果更加有趣，a和b可以有不同质量。显然较轻的物体会受到较大影响，较重的物体被碰撞影响较小。所以我们可以使用质量来确定两个物体碰撞响应效果。较大的物体具有较小的质量的倒数，如果质量为无穷大质量的倒数为零。va += v * (invmassa) / (invmassa + invm

52、assb);vb -= v * (invmassb) / (invmassa + invmassb); 五、处理旋转在许多游戏中都可以发现一些旋转的物体。与它们的碰撞会有一点复杂。旋转精灵的标准做法是通过一个简单的角度，通常的区间是0，2*pi。可以使用矩阵来存贮三角操作，因此一个角度可以被转化为2*2的矩阵 一个简单的处理旋转物体碰撞的方法是保存一个原始多边形的副本，并将其转化到当前位置和角度。这是非常简单的，因此我决定详细描述并给出一个通用的碰撞检测系统，这个系统同样可以用于3d的情况 如果你对于矩阵数学，向量，线形代数和三角学不是很熟悉，你可以看看下边的文章。

53、0;为了简化，通常的做法是将一个物体转化到另一个物体的坐标系中，因此在碰撞检阶段仅仅需要一个转化过程。转化到模型空间非常容易使人混淆，但是如果你对于基础代数比较熟悉，它会变得非常简单。 进行坐标转化后还要计算一个物体相对于另一个物体的相对位置和速度，加入方向将使得事情变得稍微复杂一些。 考虑两个物体a和b，分别位于pa和pb，方向分别为oa和ob，并且位移为da和db。转化物体a到它自己的模型空间中，这里pa=origin，oa=identitymatix，va=vector(0,0)，我们需要应用转化到物体a上，考虑如下的前向转化，并将其反向，将一个点从局部坐标转化到世界

54、坐标：pworld = plocal * oa + pa(pworld  - pa) = plocal * oa(pworld  - pa) * oat = plocal * oa * oatplocal = (pworld  - pa) * oat同样使用，前向变换来转换方向向量dworld = dlocal * oadworld * oat = dlocal * oa * oatdlocal = dworld * oat同样方向ow

55、orld = olocal * oaoworld * oat= olocal * oa * oatolocal = oworld * oat现在我们将物体b的位置转化到a的局部坐标空间中pb = (pb - pa) * oat db = (db - da) * oat ob = (ob) * oat同样，当我们测试分离轴时，需要注意的是我们还在局部坐标中，并且需要将分离轴从b的局部坐标中转换到a的局部坐标空间中。并且为了计算物体b的局部间隔，使用转化到物体a的局部坐标空间的轴，我们需要将其反向转化到b的坐标空间中。

56、 这些会使你觉得迷惑，另一个解决方案基本上不会被局部坐标所迷惑，即所有的操作都在全局坐标中完成。这个方法的确定就是你不得不保持一个多边形的副本，因为每一个多边形需要分别在世界坐标中计算一次。好处是你不需要再每次处理碰撞的时候重新计算变换。这个对2d游戏来数是非常好的，但是在3d中，你不会想在每一帧中变换一次物体仅仅为了碰撞检测的目的，尤其是当物体存储在树中并有一个非常复杂的形状的时候。六、计算触点为了动态的移动刚体，我们需要精确计算两个碰撞多边形之间的触点。对于2d来说这并不复杂，但是在3d场景中会变得非常复杂。在2d情况下，可以考虑两种情况，点和边的相交或者是边和边的相交。

57、0;这个处理过程几乎不需要教程，但是它非常适合于一个可视化的演示这里，我只考虑交叠的情况，这个原理也适用于碰撞的情况。现在给出一个碰撞的法向，在点边接触的情况下，如何求得触点？对于接触点a，它是直接向前的。我们需要调用一个支撑映射函数，他将返回多边形在制定方向上的最低点，非常类似于第一个例子中的calculateinterval()函数int findsupportpoints(const vector& n, float t, const vector* a, intanum, const vector& pa, const vector& va,

58、  constmatrix& oa, vector* s) vector norm = n oa;     float d32;     float dmin;     dmin = d0 = a0 * norm;     for(int i = 1; i < anum; i +)            

59、  di = ai * norm;         if (di < dmin)                      dmin = di;                   int sn

60、um = 0;     const float threshold = 1.0e-3f;     for(int i = 0; i < anum; i +)              if (di < dmin + threshold)                

61、      ssnum+ = transform(ai, pa, va, oa, t);                  if (snum = 2)                 return snum;       

62、0;           return snum; 这里，函数的第一部分找到多边形的最小值。第二部分简单的找到接近最小值的所有点，因此如果碰撞法线垂直于一条边，将返回两个点。这两个点将以世界坐标存贮，变换函数将确保多边形的触点被转化为世界坐标，并且如果是一个未来的碰撞，这个点将被转化为碰撞时刻的vector transform(const vector& vertex, const vector& p, const vector& v, constmatrix& xorient, float t)