碰撞檢測(cè)教程(C++)

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