碰撞檢測教程(C++)

簡介本文是闡述如何在2D動作游戲中進行精確而高效的碰撞檢測。這里的碰撞是基于多邊形而不是基于精靈的。這兩者之間在設計上會有不同?；诰`的碰撞檢測是通過精靈之間的重疊的像素來完成的。而多邊形使用向量數(shù)學來精確計算交點，時間和碰撞方向。雖然多邊形僅僅是精靈的一個近似，但是它比精靈系統(tǒng)要高級。 可以精確模擬逼真的簡單物理學，例如反彈，摩擦，斜面的滑行 碰撞檢測可以更精確的用于高速精靈系統(tǒng)。在基于精靈的系統(tǒng)中，如果物體移動過快就會在跳過另一個物體。 基于向量數(shù)學因此可以擴展到3D，然而精靈碰撞系統(tǒng)被嚴格限制在2D的情況下。特性本文使用的算法只適用于凸多邊形，例如三角形，四邊形，六邊形，圓形。對于非凸多邊形，你可以將其分解為多個凸多邊形，例如三角形。算法可以用于快速移動或慢速移動的多邊形。不管物體移動多快，碰撞都不會丟失。它也可以處理重疊的問題，并促使交疊物體分離。演示也支持分割多邊形交叉。這可以用于子彈的建模。同時提供了簡單的物體系統(tǒng)，彈力，一些基本的摩擦和靜摩擦力。用于確保物體不會從斜面上滑落。有一個剛體系統(tǒng)的例子，使用了Chrsi Hecker的物理教程。限制有序碰撞。就是說并不是有序的進行碰撞。這對于快速移動的物體會出現(xiàn)一定的問題。一旦碰撞被檢測到，它就被直接處理了。理想狀態(tài)下你可能需要找到一個碰撞點并處理它，然后尋找更多的碰撞。但是對于2D動作游戲，這通常是不必要的。一、分離坐標軸方法這個方法是碰撞檢測的核心。它的規(guī)則非常簡單并且非常易于實現(xiàn)。這個方法也非?？觳⑶曳浅？煽?，因為計算中沒有使用除法操作，下面給出一個簡單的基于兩個BOX的碰撞檢測的例子。算法試圖在兩個物體之間找到一個合適平面，如果這個平面存在，那么物體就沒有相交。為了測試物體是否是分開的，簡單的方法是投影這個物體到平面的法線上，并比較兩者之間的間距看二者是否重疊。顯然有無數(shù)的平面可以用來分割兩個物體。但是已經(jīng)經(jīng)過證明的是：你只需要使用一部分平面來進行測試，對于BOX從上圖中可以看出平面的法線為BOX B的長軸。對于BOX來說需要測試的分割平面是那些法線等于兩個BOX的軸向的平面。因此對于兩個BOX來說，你只需要測試4個分割平面即可。在這四個平面里，一旦發(fā)現(xiàn)一個分割平面可以分割BOX那么你就可以斷定這兩個BOX是不相交的。如果四個平面都不能分割BOX，那么這兩個BOX一定是相交的，也就是出現(xiàn)了碰撞?？梢詳U展這個算法到普通的多邊形，算法是相同的，只用需要測試的平面的數(shù)量改變了。并且分割平面在每個多邊形邊的垂直方向上又有一個法線。在下圖中，你可以看到兩個分割平面用于測試。在紅色的平面上你可以看到兩個間隔是重疊的。然而，在藍色的平面上間隔是不重疊的，因此，藍色的平面的是分割平面，因此物體是不相交的?，F(xiàn)在，我們有一個算法來檢測兩個多邊形是否是相交的。代碼可以分為三個部分：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 (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 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; 二、用于碰撞響應的擴展分離坐標軸方法檢測多邊形相交是非常有用的方法，但是可以做更多的事情。當多邊形相交時，我想將他們移開以避免他們相交。分離軸的方法可以非常好的用于這種情況，但是還需要作一些額外的工作。必須返回相交的深度，和推開多邊形將它們分離的方向。相交的深度和方向的組合稱為MTD，或者最小平移距離。這是用于將物體分離的的最小向量。為了計算MTD，我們可以使用分離坐標軸。當物體相交時，我們可以計算兩個物體在每一個分離軸上的投影間隔。兩個間隔交疊的部分提供了一個推動向量，你需要將其應用到其中一個物體上以便物體在軸上的投影停止交疊“推動向量”你需要應用于A上將A推開，這樣就可以使A和B分開。顯然，不能沿著一個隨機的軸來推開物體。候選軸是投影在該軸上兩個間隔之間交疊最小的那個。并且這個推動向量提供了最小平移距離。bool Intersect(Polygon A, Polygon B, Vector& MTD) / 電位分離軸。他們被轉換成推動 vectors Vector Axis32; / 每個多邊形最大的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 = B.vertexI - B.vertexJ; AxisiNumAxis+ = Vector(-E.y, E.x); if (AxisSeparatePolygons (N, A, B) 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 = maxa - minb; float d1 = maxb - mina; float depth = (d0 d1)? d0 : d1; / 將分離軸為推力矢量（重新恢復正常的軸乘區(qū)間重疊） float axis_length_squared = Axis dot Axis; Axis *= depth / axis_length_squared; return false; Vector FindMTD(Vector* PushVectors, int iNumVectors) Vector MTD = PushVector0; float 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 +) 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+; / 測試分離軸B for(int j = Bnum-1, i = 0; i Bnum; j = i, i +) Vector E0 = Bj; 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; 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; float d0 = min0 - max1; / 如果重疊, do 0 / 分離，測試動態(tài)間隔 if (d0 0.0f | d1 0.0f) float v = Vel dot N; / 速度很小，所以只能進行重疊測試。 if (fabs(v) t1) float temp = t0; t0 = t1; t1 = temp; / 取最小值 taxis = (t0 0.0f)? t0 : t1; / 交叉時間太晚或時間，沒有碰撞 if (taxis tmax) return true; return false; else / 重疊。得到的區(qū)間，作為最小的|D0|和|D1| / 返回負數(shù)以標記為重疊 taxis = (d0 d1)? d0 : d1; return false; bool FindCollisionPlane (Vector* Axis, float* taxis, int iNumAxes, Vector& Ncoll, float& tcoll) / 先找到碰撞 int mini = -1; tcoll = 0.0f; for(int i = 0; i 0.0f) if (taxisi tcoll) mini = i; tcoll = taxisi; Ncoll = Axisi; Ncoll.Normalise(); / 將軸 / 發(fā)現(xiàn)了碰撞 if (mini != -1) return true; / 不，找到重疊 mini = -1; for(int i = 0; i tcoll) mini = i; tcoll = taxisi; Ncoll = Axisi; return (mini != -1); 現(xiàn)在，你擁有了一個可以檢測未來碰撞的的檢測系統(tǒng)，或者當重疊的時候，返回碰撞平面和碰撞深度/時間四、基本弧碰撞響應下面要作的是用給定的量將兩個物體分離，并添加一點摩擦和一些靜態(tài)摩擦，以便使物體靜止在斜面上。該部分使用簡單的速度影響算法。同樣，為了使碰撞響應更加真實，物體被賦予了質量（更好的是質量的倒數(shù)）。質量的倒數(shù)是比較常用的，該值為零意味著該物體具有無窮大的質量，并因此不能移動。同時速度響應中使用質量的倒數(shù)具有更好的物理精確性。現(xiàn)在我們知道多邊形A在位置PA具有速度VA，與位置PB速度VB的多邊形B發(fā)生碰撞。Ncoll和tcoll定義了碰撞平面。如果碰撞前是交疊的，首先分離兩個物體，如下：if (tcoll 0)if (A.InvMass = 0) PB += Ncoll * tcoll; else if (B.InvMass = 0) PA -= Ncoll * tcoll; else PA -= Ncoll * (tcoll *0.5f); PB += Ncoll * (tcoll *0.5f); 然后可以調用碰撞響應的代碼，為了簡化，我們可以考慮一個粒子碰到一個平面上這里V表示粒子的進入速度，V是粒子發(fā)生碰撞后的速度，N為平面的法向。V = V - (2 * (V . N) * N理想狀態(tài)下，碰撞前后粒子的能量是相同的。但是我們可以給粒子的碰撞加入彈性系數(shù)V = V - (1 + elasticity) * (V . N) * N彈性系數(shù)的范圍為0，1如果為零意味著粒子將沿著平面滑動，如果為1，粒子將沒有能量損耗的彈開。同樣我們可以加入一些摩擦。如果我們沿著碰撞的法線和碰撞平面方向分解速度，我們可以同時計算彈性系數(shù)和摩擦力。這里，速度被沿著平面的法向和平面分解。彈性系數(shù)將影響沿著平面法向的響應(Vn)，摩擦力將影響速度的切向（Vt）。同樣摩擦系數(shù)的范圍為0，1. 0意味著沒有摩擦力，1意味著粒子將突然停止。Vn = (V . N) * N;Vt = V - Vn;V = Vt * (1 - friction) + Vn * -(elasticity);對于靜摩擦力，簡單地在速度Vt小于給定的值時設置Vt為(0,0),或者設置摩擦系數(shù)稍微比1大(1.001f)。現(xiàn)在，計算兩個物體間的碰撞響應。原理是相同的。然而，計算是基于物體的相對速度的，物體將象上述一樣受到影響。結果將添加到每一個物體上?，F(xiàn)在我們需要修改一下系數(shù)，因為現(xiàn)在我們使用了相對的概念Vector V = Va - Vb; / 相對速度Vn = (V . N) * N;Vt = V - Vn;if (Vt.Length() 0.01f) friction =1.01f;/ 響應V = Vt * -(friction) + Vn * -(1 + elasticity);Va += V *0.5f;Vb -= V *0.5f;這里使物體A和物體B具有相同的響應結果。為了使結果更加有趣，A和B可以有不同質量。顯然較輕的物體會受到較大影響，較重的物體被碰撞影響較小。所以我們可以使用質量來確定兩個物體碰撞響應效果。較大的物體具有較小的質量的倒數(shù)，如果質量為無窮大質量的倒數(shù)為零。Va += V * (InvMassA) / (InvMassA + InvMassB);Vb -= V * (InvMassB) / (InvMassA + InvMassB); 五、處理旋轉在許多游戲中都可以發(fā)現(xiàn)一些旋轉的物體。與它們的碰撞會有一點復雜。旋轉精靈的標準做法是通過一個簡單的角度，通常的區(qū)間是0，2*PI?？梢允褂镁仃噥泶尜A三角操作，因此一個角度可以被轉化為2*2的矩陣一個簡單的處理旋轉物體碰撞的方法是保存一個原始多邊形的副本，并將其轉化到當前位置和角度。這是非常簡單的，因此我決定詳細描述并給出一個通用的碰撞檢測系統(tǒng)，這個系統(tǒng)同樣可以用于3D的情況如果你對于矩陣數(shù)學，向量，線形代數(shù)和三角學不是很熟悉，你可以看看下邊的文章。/reference/articles/article1832.asp為了簡化，通常的做法是將一個物體轉化到另一個物體的坐標系中，因此在碰撞檢階段僅僅需要一個轉化過程。轉化到模型空間非常容易使人混淆，但是如果你對于基礎代數(shù)比較熟悉，它會變得非常簡單。進行坐標轉化后還要計算一個物體相對于另一個物體的相對位置和速度，加入方向將使得事情變得稍微復雜一些?？紤]兩個物體A和B，分別位于PA和PB，方向分別為OA和OB，并且位移為DA和DB。轉化物體A到它自己的模型空間中，這里PA=Origin，OA=IdentityMatix，VA=Vector(0,0)，我們需要應用轉化到物體A上，考慮如下的前向轉化，并將其反向，將一個點從局部坐標轉化到世界坐標：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同樣方向Oworld= Olocal* OAOworld* OAT= Olocal* OA * OATOlocal= Oworld* OAT現(xiàn)在我們將物體B的位置轉化到A的局部坐標空間中PB = (PB - PA) * OATDB = (DB - DA) * OATOB = (OB) * OAT同樣，當我們測試分離軸時，需要注意的是我們還在局部坐標中，并且需要將分離軸從B的局部坐標中轉換到A的局部坐標空間中。并且為了計算物體B的局部間隔，使用轉化到物體A的局部坐標空間的軸，我們需要將其反向轉化到B的坐標空間中。這些會使你覺得迷惑，另一個解決方案基本上不會被局部坐標所迷惑，即所有的操作都在全局坐標中完成。這個方法的確定就是你不得不保持一個多邊形的副本，因為每一個多邊形需要分別在世界坐標中計算一次。好處是你不需要再每次處理碰撞的時候重新計算變換。這個對2D游戲來數(shù)是非常好的，但是在3D中，你不會想在每一幀中變換一次物體僅僅為了碰撞檢測的目的，尤其是當物體存儲在樹中并有一個非常復雜的形狀的時候。六、計算觸點為了動態(tài)的移動剛體，我們需要精確計算兩個碰撞多邊形之間的觸點。對于2D來說這并不復雜，但是在3D場景中會變得非常復雜。在2D情況下，可以考慮兩種情況，點和邊的相交或者是邊和邊的相交。這個處理過程幾乎不需要教程，但是它非常適合于一個可視化的演示這里，我只考慮交疊的情況，這個原理也適用于碰撞的情況?，F(xiàn)在給出一個碰撞的法向，在點邊接觸的情況下，如何求得觸點？對于接觸點A，它是直接向前的。我們需要調用一個支撐映射函數(shù)，他將返回多邊形在制定方向上的最低點，非常類似于第一個例子中的CalculateInterval()函數(shù)int FindSupportPoints(const Vector& N, float t,const Vector* A, intAnum,const Vector& PA, const Vector& VA, constMatrix& OA, Vector* S)Vector Norm = N OA; float d32; float dmin; dmin = d0 = A0 * Norm; for(int i = 1; i Anum; i +) di = Ai * Norm; if (di dmin) dmin = di; int Snum = 0; const float threshold = 1.0E-3f; for(int i = 0; i Anum; i +) if (di 0.0f) T += V * t; return T;對于B上的點，你只需要簡單地在反方向找到一個支撐點，在以后的處理中我們需要一對位于兩個物體上的支撐點來做物理模擬推力并使物體旋轉，你可以從上圖中發(fā)現(xiàn)在不同的碰撞情況下你需要得到的一對觸點。現(xiàn)在，調用FindSupportPoint()函數(shù)在每個物體上返回一個或兩個觸點。在一對一觸點的情況下，不需要做任何事情，現(xiàn)在，還不支持一對一的接觸，但是它能夠非常容易的擴展到分離軸算法中。在一對二接觸的情況下，它是一個簡單的點對邊的碰撞，如上圖中的第一個圖在二對一接觸的情況下，可以同樣運用上述情況，除了物體被交換外在二對二接觸的情況下，他是一個邊邊碰撞，你需要找到兩個邊的交疊區(qū)域。首先對于點邊碰撞，在這種情況下，一對碰撞點可以簡單的通過將A上的碰撞點投影到B的邊上來實現(xiàn)，或者說是B的邊上最接近A觸點的點Vector FindClosestPoint(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); if (t 1.0f) t = 1.0f; if (pt) *pt = t; Vector P = A + t * AB; return P;在邊對邊