碰撞检测教程(C++)

《碰撞检测教程(C++)》由会员分享，可在线阅读，更多相关《碰撞检测教程(C++)（44页珍藏版）》请在装配图网上搜索。

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

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

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

4、于BOX从上图中可以看出平面的法线为BOX B的长轴。3 / 42如果您需要使用本文档，请点击下载按钮下载!对于BOX来说需要测试的分割平面是那些法线等于两个BOX的轴向的平面。因此对于两个BOX来说，你只需要测试4个分割平面即可。在这四个平面里，一旦发现一个分割平面可以分割BOX那么你就可以断定这两个BOX是不相交的。如果四个平面都不能分割BOX，那么这两个BOX一定是相交的，也就是出现了碰撞。可以扩展这个算法到普通的多边形，算法是相同的，只用需要测试的平面的数量改变了。并且分割平面在每个多边形边的垂直方向上又有一个法线。在下图中，你可以看到两个分割平面用于测试。在红色的平面上你可以看到两个

5、间隔是重叠的。然而，在蓝色的平面上间隔是不重叠的，因此，蓝色的平面的是分割平面，因此物体是不相交的。4 / 42如果您需要使用本文档，请点击下载按钮下载!现在，我们有一个算法来检测两个多边形是否是相交的。代码可以分为三个部分：a)生成需要测试的分离轴b)计算每一个多边形在分离轴法线上的投影c)检测这些投影是否相交bool Intersect(Polygon A, Polygon B) 5 / 42如果您需要使用本文档，请点击下载按钮下载! for(I = 0; I A.num_edges; I +) Vector N = Vector(-A.EdgeDirI.y, A.EdgeDirI.x);

6、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 (AxisSeparatePolygons (N, A, B) return false; return true; void CalculateInterval(Vector Axis, Polygon P, float& min, float& max) float d = Axis dot P.vertex0; /从坐标原点开始计算

7、向量 min = max = d; 6 / 42如果您需要使用本文档，请点击下载按钮下载!for(I = 0; I P.num_vertices; I +) float d = P.vertexI dot Axis; if (d 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; Vec

8、tor N = Vector(-E.y, E.x); if (AxisSeparatePolygons(N, A, B) return false; 二、用于碰撞响应的扩展分离坐标轴方法7 / 42如果您需要使用本文档，请点击下载按钮下载!检测多边形相交是非常有用的方法，但是可以做更多的事情。当多边形相交时，我想将他们移开以避免他们相交。分离轴的方法可以非常好的用于这种情况，但是还需要作一些额外的工作。必须返回相交的深度，和推开多边形将它们分离的方向。相交的深度和方向的组合称为MTD，或者最小平移距离。这是用于将物体分离的的最小向量。为了计算MTD，我们可以使用分离坐标轴。当物体相交时，我们可

9、以计算两个物体在每一个分离轴上的投影间隔。两个间隔交叠的部分提供了一个推动向量，你需要将其应用到其中一个物体上以便物体在轴上的投影停止交叠8 / 42如果您需要使用本文档，请点击下载按钮下载!“推动向量”你需要应用于A上将A推开，这样就可以使A和B分开。显然，不能沿着一个随机的轴来推开物体。候选轴是投影在该轴上两个间隔之间交叠最小的那个。并且这个推动向量提供了最小平移距离。bool Intersect(Polygon A, Polygon B, Vector& MTD) 9 / 42如果您需要使用本文档，请点击下载按钮下载!/ 电位分离轴。他们被转换成推动 vectors Vector Axi

10、s32; / 每个多边形最大的16个顶点的 int iNumAxis = 0; for(J = A.num_vertices - 1, I = 0; I A. num_vertices; J = I, I +) Vector E = A.vertexI - A.vertexJ; AxisiNumAxis+ = Vector(-E.y, E.x); if (AxisSeparatePolygons(N, A, B) return false; for(J = B. num_vertices - 1, I = 0; I B.num_vertices; J = I, I +) Vector E =

11、B.vertexI - B.vertexJ; AxisiNumAxis+ = Vector(-E.y, E.x); if (AxisSeparatePolygons (N, A, B) 10 / 42如果您需要使用本文档，请点击下载按钮下载!return false; / 找到所有的分离向量之间的MTD MTD = FindMTD(Axis, iNumAxis); / 确保将向量a推动远离b Vector D = A.Position - B.Position; if (D dot MTD maxb | minb maxa) return true; / 查找间隔重叠 float d0 = m

12、axa - minb; 11 / 42如果您需要使用本文档，请点击下载按钮下载!float d1 = maxb - mina; float depth = (d0 d1)? d0 : d1; / 将分离轴为推力矢量（重新恢复正常的轴乘区间重叠） float axis_length_squared = Axis dot Axis; Axis *= depth / axis_length_squared; return false; Vector FindMTD(Vector* PushVectors, int iNumVectors) Vector MTD = PushVector0; floa

13、t mind2 = PushVector0 dot PushVector0; for(int I = 1; I iNumVectors; I +) float d2 = PushVectorI * PushVectorI; if (d2 0.00001f) if (!IntervalIntersect( A, Anum, B, Bnum, xAxisiNumAxes, xOffset, xVel, taxisiNumAxes, t) return false; iNumAxes+; / 测试分离轴A for(int j = Anum-1, i = 0; i Anum; j = i, i +)

14、Vector E0 = Aj; Vector E1 = Ai; Vector E = E1 - E0; xAxisiNumAxes = Vector(-E.y, E.x); if (!IntervalIntersect( A, Anum, B, Bnum, xAxisiNumAxes, xOffset, xVel, taxisiNumAxes, t) return false; iNumAxes+; 17 / 42如果您需要使用本文档，请点击下载按钮下载!/ 测试分离轴B for(int j = Bnum-1, i = 0; i Bnum; j = i, i +) Vector E0 = Bj

15、; Vector E1 = Bi; Vector E = E1 - E0; xAxisiNumAxes = Vector(-E.y, E.x); if (!IntervalIntersect( A, Anum, B, Bnum, xAxisiNumAxes, xOffset, xVel, taxisiNumAxes, t) return false; iNumAxes+; if (!FindMTD(xAxis, taxis, iNumAxes, N, t) return false; / 确保多边形被彼此推开。 if (N * xOffset 0.0f) N = -N; return true

16、; 18 / 42如果您需要使用本文档，请点击下载按钮下载! bool AxisSeparatePolygons ( Vector N, Polygon A, Polygon B, Vector Offset, Vector Vel, float &t, float tmax) float min0, max0; float min1, max1; CalculateInterval(N, A, min0, max0); CalculateInterval(N, B, min1, max1); float h = Offset dot N; min0 += h; max0 += h; floa

17、t d0 = min0 - max1; / 如果重叠, do 0 / 分离，测试动态间隔 if (d0 0.0f | d1 0.0f) 19 / 42如果您需要使用本文档，请点击下载按钮下载!float v = Vel dot N; / 速度很小，所以只能进行重叠测试。 if (fabs(v) t1) float temp = t0; t0 = t1; t1 = temp; / 取最小值 taxis = (t0 0.0f)? t0 : t1; / 交叉时间太晚或时间，没有碰撞 20 / 42如果您需要使用本文档，请点击下载按钮下载!if (taxis tmax) return true; re

18、turn false; else / 重叠。得到的区间，作为最小的|D0|和|D1| / 返回负数以标记为重叠 taxis = (d0 d1)? d0 : d1; return false; bool FindCollisionPlane (Vector* Axis, float* taxis, int iNumAxes, Vector& Ncoll, float& tcoll) / 先找到碰撞 int mini = -1; 21 / 42如果您需要使用本文档，请点击下载按钮下载!tcoll = 0.0f; for(int i = 0; i 0.0f) if (taxisi tcoll) mi

19、ni = i; tcoll = taxisi; Ncoll = Axisi; Ncoll.Normalise(); / 将轴 / 发现了碰撞 if (mini != -1) return true; 22 / 42如果您需要使用本文档，请点击下载按钮下载!/ 不，找到重叠 mini = -1; for(int i = 0; i tcoll) mini = i; tcoll = taxisi; Ncoll = Axisi; return (mini != -1); 23 / 42如果您需要使用本文档，请点击下载按钮下载!现在，你拥有了一个可以检测未来碰撞的的检测系统，或者当重叠的时候，返回碰撞平

20、面和碰撞深度/时间四、基本弧碰撞响应下面要作的是用给定的量将两个物体分离，并添加一点摩擦和一些静态摩擦，以便使物体静止在斜面上。该部分使用简单的速度影响算法。同样，为了使碰撞响应更加真实，物体被赋予了质量（更好的是质量的倒数）。质量的倒数是比较常用的，该值为零意味着该物体具有无穷大的质量，并因此不能移动。同时速度响应中使用质量的倒数具有更好的物理精确性。现在我们知道多边形A在位置PA具有速度VA，与位置PB速度VB的多边形B发生碰撞。Ncoll和tcoll定义了碰撞平面。如果碰撞前是交叠的，首先分离两个物体，如下：if (tcoll 0)if (A.InvMass = 0)24 / 42如果您

21、需要使用本文档，请点击下载按钮下载! PB += Ncoll * tcoll; else if (B.InvMass = 0) PA -= Ncoll * tcoll; else PA -= Ncoll * (tcoll *0.5f); PB += Ncoll * (tcoll *0.5f); 然后可以调用碰撞响应的代码，为了简化，我们可以考虑一个粒子碰到一个平面上25 / 42如果您需要使用本文档，请点击下载按钮下载!这里V表示粒子的进入速度，V是粒子发生碰撞后的速度，N为平面的法向。V = V - (2 * (V . N) * N理想状态下，碰撞前后粒子的能量是相同的。但是我们可以给粒子的

22、碰撞加入弹性系数V = V - (1 + elasticity) * (V . N) * N弹性系数的范围为0，1如果为零意味着粒子将沿着平面滑动，如果为1，粒子将没有能量损耗的弹开。同样我们可以加入一些摩擦。如果我们沿着碰撞的法线和碰撞平面方向分解速度，我们可以同时计算弹性系数和摩擦力。26 / 42如果您需要使用本文档，请点击下载按钮下载!这里，速度被沿着平面的法向和平面分解。弹性系数将影响沿着平面法向的响应(Vn)，摩擦力将影响速度的切向（Vt）。同样摩擦系数的范围为0，1. 0意味着没有摩擦力，1意味着粒子将突然停止。Vn = (V . N) * N;Vt = V - Vn;V = V

23、t * (1 - friction) + Vn * -(elasticity);对于静摩擦力，简单地在速度Vt小于给定的值时设置Vt为(0,0),或者设置摩擦系数稍微比1大(1.001f)。27 / 42如果您需要使用本文档，请点击下载按钮下载!现在，计算两个物体间的碰撞响应。原理是相同的。然而，计算是基于物体的相对速度的，物体将象上述一样受到影响。结果将添加到每一个物体上。现在我们需要修改一下系数，因为现在我们使用了相对的概念Vector V = Va - Vb; / 相对速度Vn = (V . N) * N;Vt = V - Vn;if (Vt.Length() 0.01f) fricti

24、on =1.01f;/ 响应V = Vt * -(friction) + Vn * -(1 + elasticity);Va += V *0.5f;Vb -= V *0.5f;这里使物体A和物体B具有相同的响应结果。为了使结果更加有趣，A和B可以有不同质量。显然较轻的物体会受到较大影响，较重的物体被碰撞影响较小。所以我们可以使用质量来确定两个物体碰撞响应效果。较大的物体具有较小的质量的倒数，如果质量为无穷大质量的倒数为零。28 / 42如果您需要使用本文档，请点击下载按钮下载!Va += V * (InvMassA) / (InvMassA + InvMassB);Vb -= V * (Inv

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

26、做法是将一个物体转化到另一个物体的坐标系中，因此在碰撞检阶段仅仅需要一个转化过程。转化到模型空间非常容易使人混淆，但是如果你对于基础代数比较熟悉，它会变得非常简单。进行坐标转化后还要计算一个物体相对于另一个物体的相对位置和速度，加入方向将使得事情变得稍微复杂一些。考虑两个物体A和B，分别位于PA和PB，方向分别为OA和OB，并且位移为DA和DB。转化物体A到它自己的模型空间中，这里PA=Origin，OA=IdentityMatix，VA=Vector(0,0)，我们需要应用转化到物体A上，考虑如下的前向转化，并将其反向，将一个点从局部坐标转化到世界坐标：Pworld= Plocal* OA

27、+ PA(Pworld - PA) = Plocal* OA30 / 42如果您需要使用本文档，请点击下载按钮下载!(Pworld - PA) * OAT= Plocal* OA * OATPlocal= (Pworld - PA) * OAT同样使用，前向变换来转换方向向量Dworld= Dlocal* OADworld* OAT= Dlocal* OA * OATDlocal= Dworld* OAT同样方向Oworld= Olocal* OAOworld* OAT= Olocal* OA * OATOlocal= Oworld* OAT现在我们将物体B的位置转化到A的局部坐标空间中PB

28、= (PB - PA) * OATDB = (DB - DA) * OATOB = (OB) * OAT31 / 42如果您需要使用本文档，请点击下载按钮下载!同样，当我们测试分离轴时，需要注意的是我们还在局部坐标中，并且需要将分离轴从B的局部坐标中转换到A的局部坐标空间中。并且为了计算物体B的局部间隔，使用转化到物体A的局部坐标空间的轴，我们需要将其反向转化到B的坐标空间中。这些会使你觉得迷惑，另一个解决方案基本上不会被局部坐标所迷惑，即所有的操作都在全局坐标中完成。这个方法的确定就是你不得不保持一个多边形的副本，因为每一个多边形需要分别在世界坐标中计算一次。好处是你不需要再每次处理碰撞的时

29、候重新计算变换。这个对2D游戏来数是非常好的，但是在3D中，你不会想在每一帧中变换一次物体仅仅为了碰撞检测的目的，尤其是当物体存储在树中并有一个非常复杂的形状的时候。六、计算触点为了动态的移动刚体，我们需要精确计算两个碰撞多边形之间的触点。对于2D来说这并不复杂，但是在3D场景中会变得非常复杂。在2D情况下，可以考虑两种情况，点和边的相交或者是边和边的相交。32 / 42如果您需要使用本文档，请点击下载按钮下载!这个处理过程几乎不需要教程，但是它非常适合于一个可视化的演示这里，我只考虑交叠的情况，这个原理也适用于碰撞的情况。现在给出一个碰撞的法向，在点边接触的情况下，如何求得触点？对于接触点A

30、，它是直接向前的。我们需要调用一个支撑映射函数，他将返回多边形在制定方向上的最低点，非常类似于第一个例子中的CalculateInterval()函数int FindSupportPoints(const Vector& N, float t,const Vector* A, intAnum,const Vector& PA, const Vector& VA,33 / 42如果您需要使用本文档，请点击下载按钮下载! constMatrix& OA, Vector* S)Vector Norm = N OA; float d32; float dmin; dmin = d0 = A0 * No

31、rm; for(int i = 1; i Anum; i +) di = Ai * Norm; if (di dmin) dmin = di; int Snum = 0; const float threshold = 1.0E-3f;34 / 42如果您需要使用本文档，请点击下载按钮下载! for(int i = 0; i Anum; i +) if (di 0.0f) T += V * t; return T;对于B上的点，你只需要简单地在反方向找到一个支撑点，在以后的处理中我们需要一对位于两个物体上的支撑点来做物理模拟推力并使物体旋转，你可以从上图中发现在不同的碰撞情况下你需要得到的一对

32、触点。现在，调用FindSupportPoint()函数在每个物体上返回一个或两个触点。在一对一触点的情况下，不需要做任何事情，现在，还不支持一对一的接触，但是它能够非常容易的扩展到分离轴算法中。36 / 42如果您需要使用本文档，请点击下载按钮下载!在一对二接触的情况下，它是一个简单的点对边的碰撞，如上图中的第一个图在二对一接触的情况下，可以同样运用上述情况，除了物体被交换外在二对二接触的情况下，他是一个边边碰撞，你需要找到两个边的交叠区域。首先对于点边碰撞，在这种情况下，一对碰撞点可以简单的通过将A上的碰撞点投影到B的边上来实现，或者说是B的边上最接近A触点的点Vector FindClo

33、sestPoint(const Vector& V, const Vector& A, const Vector& B, float* pt) Vector AV = V - A; Vector AB = B - A; float t = (AV * AB) / (AB * AB);37 / 42如果您需要使用本文档，请点击下载按钮下载! if (t 1.0f) t = 1.0f; if (pt) *pt = t; Vector P = A + t * AB; return P;在边对边碰撞的情况下，处理过程非常类似。只是你需要沿着沿着碰撞法线的垂直方向排序点，并得到两个中间点。然后，将它们投

34、影到另外的边上以便得到一对触点。38 / 42如果您需要使用本文档，请点击下载按钮下载!有了这些触点，你就可以编写一个基本的刚体系统，物体将比以前更真实的相互碰撞并响应碰撞。七、动态刚体为了不浪费时间介绍动态刚体，可以直接参参见下面的连接：这里，展示了如何在2D游戏中实施真实的物理。39 / 42如果您需要使用本文档，请点击下载按钮下载!我将介绍一些我所做的扩展，首先，计算给定凸多边形的惯量是有技巧的。需要提醒你的是，惯量适用于角度变化，质量适用于线形变化。较高的惯量对应于较大的质量，在这种情况下物体将很难旋转。相反，较小的惯量使得物体的角速度更易改变。质量和惯量是有联系的，因为它们都依赖于体

35、积，密度和物体的平衡，下面的连接给出了一些参考一句话，计算惯量的公式为：这里：M是质量，N是顶点数，Pn是多边形的一个顶点，|.|表示求模运算。在2D中表示向量的长度。可以使用下面的公式根据组成多边形材质的密度来计算惯量40 / 42如果您需要使用本文档，请点击下载按钮下载!这里：P是密度，N是顶点数, Pn是多边形的顶点, |.|表示求模，从上述方程中，你可以推理出计算质量的等式。该系统的其它模式是处理交叠。这可以避免一个物体陷入另一个物体，因为使用推力计算在低速的时候是非常不精确的。为了解决交叠问题，即简单的方法是沿着碰撞法线根据碰撞深度将物体推开。当然只有在检测到交叠的时候才使用它。为了

36、使它更为精确，物体的移动应该依赖于它们质量的比率，因此较轻的物体应该移动更多，而较重的物体移动较少，当然具有无穷大质量的物体是不会移动的。至于摩擦力，基本的是动态摩擦力，它将沿着物体速度的反向添加一个力，大小为|u*Jn|其中u是动摩擦系数Jn是压力。41 / 42如果您需要使用本文档，请点击下载按钮下载!静态摩擦力总是比较简单的模型。我选则的静态摩擦力的模型是将物体与一个不可见的物体在碰撞平面上发生碰撞。正碰撞的计算是非常简单的。碰撞力的方向是速度的反向，触点的速度会被抵消（基本上，恢复系数稍微比1大）好了，剩下的部分就按照Chris Hecke的教程。物体翻转，碰撞，做一系列疯狂的事情，并且看起来非常的真实。 （注：可编辑下载，若有不当之处，请指正，谢谢!） 42 / 42