NEHE的OPENGL中文教程第30課碰撞檢測與

1、NEHE的OPENGL中文教程 第30課 碰撞檢測與2011-06-16 opengl粒子系統(tǒng)轉(zhuǎn)載NEHE的OPENGL中文教程：第30課碰撞檢測與模型運動1opengl粒子系統(tǒng)轉(zhuǎn)載NEHE的OPENGL中文教程：第30課碰撞檢測與模型運動1下面我們要討論的是如何快速有效的檢測物體的碰撞和合乎物理法則的物體運動，先看一下我們要學的：1)碰撞檢測移動的范圍-平面移動的范圍-圓柱移動的范圍-運動的物體2)符合物理規(guī)則的物體運動碰撞后的響應(yīng)在具有重力影響的環(huán)境下應(yīng)用Euler公式運動物體。3)特別的效果使用A Fin-Tree Billboard方法實現(xiàn)爆炸效果使用Windows Multimedi

2、a Library實現(xiàn)聲音(僅限于Windows平臺)4)源代碼的說明源代碼由5個文件組成Lesson31.cpp該實例程序的主程序Image.cpp、Image.h讀入位圖文件Tmatrix.cpp、Tmatrix.h處理旋轉(zhuǎn)Tray.cpp、Tray.h處理光線Tvector.cpp、Tvector.h矢量Vector，Ray和Matrix類是很有用的，我在個人的項目中常使用它們。那么下面就讓我們馬上開始這段學習的歷程吧。31.1、碰撞檢測為了實現(xiàn)碰撞檢測我們將使用一套經(jīng)常在光線跟蹤算法中使用的規(guī)則。先讓我們定義一下什么是光線。一條通過矢量描述的光線，意味著規(guī)定了起點，并且有一個矢量(通常

3、已被歸一化)，描述了該光線通過的方向?；旧显摴饩€從起點出發(fā)并沿著該矢量規(guī)定的方向前進。所以我們的光線可被一下公式所表達：t是一個浮點數(shù)，取值從0到無窮大。t=0時獲得起始點的位置；為其它值時獲得相應(yīng)的位置，當然是在該光線所經(jīng)過的路線上。變量PointOnRay，Raystart和Raydirection都是3D的矢量，取值(x,y,z)?，F(xiàn)在我們可以使用該光線公式計算平面或圓柱的橫截面。Xn與X是矢量而d是一個浮點數(shù)。Xn是它的法線X是它表面的一個點。d是一個浮點數(shù)，描述了從坐標系的原點到法線平面的距離。本質(zhì)上一個平面將空間分成了兩個部分。所以我們要做的就是定義一個平面。由一個點以及一條法線

4、(經(jīng)過該點且垂直于該平面)，這兩個矢量描述了該平面。也就是，如果我們有一個點(0,0,0)和一條法線(0,1,0)，我們實際上就已經(jīng)定義了一個平面，也即x,z平面。因此通過一個點和一個法線已經(jīng)足夠定義一個平面的矢量方程式了。使用平面的矢量方程式，法線被Xn所代替，那個點(也即法線的起點)被X所代替。d是唯一還未知的變量，不過很容易計算出來(通過點乘運算，是基本的矢量運算公式)。注意：這種矢量表示法與通常的參數(shù)表達式方法是等價的，參數(shù)表達式描述一個平面公式如下：Ax+By+Cz+D=0只需簡單的將法線的矢量(x,y,z)代替A,B,C，將D=-d即可。如果一條光線與一個平面相交，那么必定有該光線

5、上的幾個點滿足該平面的公式，也就是：t是從該光線的起點沿著光線的方向到該平面的距離。因此將t代入光線公式即可算出撞擊點。但是還有幾個特殊情況需要考慮：如果Xn dot Raydirection=0，表明光線和平面是平行的，將不會有撞擊點。如果t是負數(shù)，那么表明撞擊點是在光線的起始點的后面，也就是沿著光線后退的方向才能撞到平面，這只能說明光線和平面沒有交點。int TestIntersionPlane(const Plane&plane,const TVector&position,const TVector&direction,double&lamda,TVector&pNormal)doub

6、le DotProduct=direction.dot(plane._Normal)；/求得平面法線和光線方向的點積/(也即求Xn dot Raydirection)double l2；/判斷光線是否和平面平行if(DotProduct ZERO)&(DotProduct-ZERO)/判斷一個浮點數(shù)是否為0，也即在一個很小的數(shù)的正負區(qū)間內(nèi)即可認為該浮點數(shù)為0 return 0；/求得從光線的起點到撞擊點的距離?l2=(plane._Normal.dot(plane._Position-position)/D otProduct；if(l2-ZERO)/如果l2小于0表明撞擊點在光線的反方向上，

7、/這只能表明兩者沒有相撞return 0；pNormal=plane._Normal；lamda=l2；return 1；上面這段代碼計算并返回光線和平面的撞擊點。如果有撞擊點函數(shù)返回1否則返回0。函數(shù)的參數(shù)依次是平面，光線的起點，光線的方向，一個浮點數(shù)記錄了撞擊點的距離(如果有的話)，最后一個參數(shù)記錄了平面的法線。31.1.2光線-圓柱體相交的檢測計算一條光線和一個無限大的圓柱體的相撞是一件很復(fù)雜的事，所以我在這里沒有解釋它。有太多的過于復(fù)雜的數(shù)學方法以至于不容易解釋，我的目標首先是提供給你一個工具，不需知道過多的細節(jié)你就可以使用它(這并不是一個幾何的類)。如果有人對下面檢測碰撞的代碼感興趣

8、的話，請看Graphic Gems II Book(pp 35,intersection of awith acylinder)。一個圓柱體的描述類似于光線，有一個起點和方向，該方向描述了圓柱體的軸，還有一個半徑。相關(guān)的函數(shù)是：int TestIntersionCylinder(const Cylinder&cylinder,const TVector&position,const TVector&direction,double&lamda,TVector&pNormal,TVector&newposition如果光線和圓柱體相撞則返回1否則返回0。函數(shù)的參數(shù)依次是圓柱體，光線的起點，光線的

9、方向，一個浮點數(shù)記錄了撞擊點的距離(如果有的話)，一個參數(shù)記錄了撞擊點的法線，最后一個參數(shù)記錄了撞擊點。31.1.3球體-球體撞擊的檢測一個球體通過圓心和半徑來描述。判斷兩個球體是否相撞十分簡單，只要算一下這兩個球體的圓心的距離，如果小于這兩個球體半徑的和，即表明該兩個球體已經(jīng)相撞。問題是該如何判斷兩個運動球體的碰撞。兩個球體的運動軌跡相交并不能表明它們會相撞，因為它們可能是在不同的時間經(jīng)過相交點的。以上的檢測碰撞的方法解決的是簡單物體的碰撞問題。當使用復(fù)雜形狀的物體或方程式不可用或不能解決時，要使用一種不同的方法。球體的起始點，終止點，時間片，速度(運動方向+速率)都是已知的，如何計算靜態(tài)物

10、體的相交方法也是已知的。為了計算交叉點，時間片必須被切分成更小的片斷(slice)。然后我們按照物體的速度運動一個slice，檢測一下碰撞，如果有任何點的碰撞被發(fā)現(xiàn)(那意味著物體已經(jīng)互相穿透了)，那么我們就將前一個位置作為相撞點(我們可以更詳細的計算更多的點以便找到相撞點的精確位置，但是大部分情況下那沒有必要)。時間片分的越小，slice切分的越多，用我們的方法得到的結(jié)果就越精確。舉例來說，如果讓時間片為1，而將一個時間片切分成3個slice，那么我們就會在0，0.33，0.66，1這幾個時間點上檢測2個球的碰撞。太簡單了。下面的代碼實現(xiàn)了以上所說的：int FindBallCol(TVect

11、or&point,double&TimePoint,double Time2,int&BallNr1,int&BallNr2)TVector RelativeV；TRay rays；/Time2是時間的步長，Add將一個時間步長分成了150個小片double MyTime=0.0,Add=Time2/150.0,Timedummy=10000,Timedummy2=-1；TVector posi；for(int i=0；i NrOfBalls-1；i+)/將所有的球都和其它球檢測一遍，NrOfBalls是球的總個數(shù)for(int j=i+1；j NrOfBalls；j+)RelativeV=A

12、rrayVeli-ArrayVelj；/計算兩球的距離rays=TRay(OldPosi,TVector：unit(RelativeV)；MyTime=0.0；/如果兩個球心的距離大于兩個球的半徑，/表明沒有相撞，直接返回(球的半徑應(yīng)該是20)/如果有撞擊發(fā)生的話，計算出精確的撞擊點if(rays.dist(OldPosj)40)continue；while(MyTime Time2)/循環(huán)檢測以找到精確的撞擊點MyTime+=Add；/將一個時間片分成150份posi=OldPosi+RelativeV*MyTime；/計算球在每個時間片斷的位置if(posi.dist(OldPosj)=4

13、0)/如果兩個球心的距離小于40，/表明在該時間片斷發(fā)生了碰撞point=posi；/將球的位置更新為撞擊點的位置if(Timedummy(MyTime-Add)Timedummy=MyTime-Add；BallNr1=i；/記錄哪兩個球發(fā)生了碰撞BallNr2=j；break；if(Timedummy！=10000)/如果Timedummy 10000，/表明發(fā)生了碰撞，/記錄下碰撞發(fā)生的時間TimePoint=Timedummy；return 1；return 0；31.1.4如何應(yīng)用我們剛學過的知識現(xiàn)在我們已經(jīng)能夠計算出一條光線和一個平面或者圓柱體的碰撞點了，但我們還不知要如何計算一個物

14、體和以上這些物體的碰撞點。我們目前能作的只是能夠計算出一個粒子和一個平面或圓柱體的碰撞點。光線的起始點是這個粒子的位置，光線的方向是這個粒子的速度(包括速率和方向)。讓它適用于球體是很簡單的?？匆幌率纠龍D2a就會明白它是如何實現(xiàn)的。每個球體都有一個半徑，將球體的球心看成是粒子，將感興趣的平面或圓柱體的表面沿著法線的方向偏移，在示例圖2a中這些新的圖元由點劃線表示出。而原始的圖元由實線表示出。碰撞就發(fā)生在球心與由點劃線表示的新圖元的交點處?；旧衔覀兪窃诎l(fā)生了偏移的表面和半徑更大的圓柱體上執(zhí)行碰撞檢測的。使用這個小技巧如果球的球心發(fā)生了碰?駁幕埃蚓筒換崠矯妗H綣徽庋齙幕埃突嵯袷糾?2b發(fā)生的那樣

15、，球會穿進平面的。之所以會發(fā)生圖2b所示意的情況，是因為我們在球的球心和圖元之間進行碰撞的檢測，那意味著我們忽略了球的大小，而這是不正確的。檢測到碰撞發(fā)生的地點后，我們還得判斷該碰撞是否發(fā)生在當前的時間片內(nèi)。所謂的時間片就是當時間到了某個時刻，我們就把我們的物體從當前位置沿著速度移動單位個步長。如果發(fā)生了碰撞，我們就計算碰撞點和出發(fā)點的距離，就可以很容易的算出碰撞發(fā)生的時間。假設(shè)單位步長是Dst，碰撞點到出發(fā)點的距離為Dsc，時間片為T，那么碰撞發(fā)生的時刻(Tc)為：如果有碰撞發(fā)生，以上這個公式就是我們所需要的全部。Tc是整個時間片的一部分，所以如果時間片是1秒的話，并且我們已經(jīng)正確的找到了碰

16、撞發(fā)生時離出發(fā)點的距離，那么如果經(jīng)過計算求出碰撞是在0.5秒時發(fā)生的，那么這就意味著從該時間片開始后過了0.5秒發(fā)生了一次碰撞?，F(xiàn)在碰撞點就可以簡單的計算出來了：這就是撞擊點的坐標，當然是在已經(jīng)發(fā)生了偏移的表面上的點，為了求出真正平面上的撞擊點，我們將該坐標沿該點的法線(由檢測撞擊的程序求出)的反方向移動球體的半徑那么長的距離。注意圓柱體的撞擊檢測程序已經(jīng)返回了撞擊點，所以它就不需要計算了。31.2、符合物理規(guī)則的物體運動31.2.1碰撞響應(yīng)如果物體撞到了一個靜止的物體，比如說一個平面上，那該如何響應(yīng)呢?圓柱體本身和找到撞擊點一樣重要。通過使用這套規(guī)則和方法，正確的撞擊點和該點的法線以及撞擊發(fā)

17、生的時間都能被正確的求出。要決定如何響應(yīng)一次碰撞，需要應(yīng)用物理法則。當一個物體撞在了一個表面上，它的運動方向會改變，也就是說，它被反彈了。新的運動方向和撞擊點的法線所形成的夾角與入射點和撞擊點的法線所形成的夾角是相等的，也就是說，物體在撞擊點按照撞擊點的法線發(fā)生了鏡面反射。示意圖3顯示了在一個球面上發(fā)生的一次撞擊及其反彈。圖中，R是新運動方向的矢量。I是撞擊發(fā)生前的矢量。N是撞擊點的法線的矢量。那么，矢量R可以這樣求出：有個限制條件是I和N這兩個矢量都必須是單位矢量(歸一化)，速度矢量在我們的例子中被用來描述速率和運動的方向。因此，如果不經(jīng)過轉(zhuǎn)換，它不能被代入方程式中的I。速率要被提取出來，在

18、速度矢量中該速率就是這個速度矢量的長度。一旦求出該長度，這個速度矢量就能夠被歸一化并被代入上面公式中以求出反射后的運動矢量R。矢量R告訴了我們反彈后的運動方向。但是為了描述速度，我們還得加入速率這個分量。因此我們得乘上撞擊前的矢量的長度，這樣最終我們才獲得了正確的反彈后的運動矢量。下面的例子里用來計算撞擊后的反彈問題，如果一個球撞到了一個平面或是一個圓柱體上的話。但是它也適用于任意的表面，它并不在意表面的形狀是怎樣的。只要能得到撞擊點的法線，該程序就能夠適用。下面是程序的代碼：rt2=ArrayVelBallNr.mag()；/求出球的速率ArrayVelBallNr.unit()；/歸一化/

19、計算反彈ArrayVelBallNr=TVector：unit(normal*(2*normal.dot(-ArrayVelBallNr)+ArrayVelBallNr)；ArrayVelBallNr=ArrayVelBallNr*rt2；/乘上速率以求得反彈后的速度31.2.2當球體發(fā)生碰撞當一個球撞到了另一個球上，該如何計算撞擊后的反彈呢?如果兩個球互相撞到了一起是比較麻煩。得用質(zhì)點動力學的復(fù)雜公式來求解。因此我直接給出了最終的解決方案而沒有進行驗證(請在這一點上相信我沒出錯)。當兩個球發(fā)生碰撞時，我們用示例圖4來示意：U1和U2這兩個矢量是兩個球體碰撞時的速度。有一個軸矢量(X_Axis

20、)連接了兩個球體的球心。U1x和U2x是U1和U2沿著X_Axis的分量，而U1y和U2y是U1和U2沿著X_Axis的垂直方向的分量。為了求出這幾個矢量，只需要一點簡單的點積運算即可。M1和M2分別是這兩個球體的質(zhì)量。V1和V2分別是撞擊后兩個球體的新的速度矢量。而V1x,V1y,V2x,V2y分別是這兩個速度矢量在X_Axis上的分量。下面是一些細節(jié)：a)求出X_Axis X_Axis=(center2-center1)；Unify X_Axis,X_Axis.unit()；b)求出兩個球體的速度在X_Axis上的分量U1x=X_Axis*(X_Axis dot U1)U1y=U1-U1x

21、 U2x=-X_Axis*(-X_Axis dot U2)U2y=U2-U2x c)求出新的速度(U1x*M1)+(U2x*M2)-(U1x-U2x)*M2 V1x=-M1+M2(U1x*M1)+(U2x*M2)-(U2x-U1x)*M1 V2x=-M1+M2在我們的例子中我們令M1=M2=1，所以上面的等式可以變得更簡單了。d)求出最終的速度V1y=U1y V2y=U2y V1=V1x+V1y V2=V2x+V2y要得到上面這些方程式，得做很多的運算工作。但是一旦求出來了，它們就能夠很容易的被使用。下面的代碼用來求解碰撞后的反彈：TVector pb1,pb2,xaxis,U1x,U1y,U

22、2x,U2y,V1x,V1y,V2x,V2y；double a,b；pb1=OldPosBallColNr1+ArrayVelBallColNr1*BallTi me；/找到球1的位置pb2=OldPosBallColNr2+ArrayVelBallColNr2*BallTi me；/找到球2的位置xaxis=(pb2-pb1).unit()；/計算出X_Axis的矢量a=xaxis.dot(ArrayVelBallColNr1)；/計算球1的速度在X_Axis上的分量U1x=xaxis*a；U1y=ArrayVelBallColNr1-U1x；xaxis=(pb1-pb2).unit()；/

23、和上面的代碼一樣，計算球2的速度在X_Axis上的分量b=xaxis.dot(ArrayVelBallColNr2)；U2x=xaxis*b；U2y=ArrayVelBallColNr2-U2x；V1x=(U1x+U2x-(U1x-U2x)*0.5；/現(xiàn)在計算新的速度，因為我們令公式中的M1和M2都為1，結(jié)果分母就成了2，也就是0.5，了解吧。V2x=(U1x+U2x-(U2x-U1x)*0.5；V1y=U1y；V2y=U2y；for(j=0；j NrOfBalls；j+)/更新每個球的位置ArrayPosj=OldPosj+ArrayVelj*BallTime；ArrayVelBallCol

24、Nr1=V1x+V1y；/設(shè)置新的速度給那兩個發(fā)生了碰撞的球ArrayVelBallColNr2=V2x+V2y；31.2.3使用歐拉公式在重力影響下移動物體為了模擬真實的撞擊運動，光計算撞擊點和撞擊后的反彈是不夠的，基于物理法則的運動也必須被模擬。為了模擬真實的情況，歐拉公式是被廣泛使用的。在使用時間片的時候，所有的計算都要被提供，那意味著整個仿真是先進的，在整個運動過程中的確定的時間片上，以及在碰撞和反彈時。作為一個例子我們仿真2秒鐘。在每一幀，基于歐拉公式，每一個時間片的速度和位置可以這樣計算：現(xiàn)在這個物體根據(jù)這個新的速度運動并進行碰撞測試。每個物體的加速度(Acceleration)是

25、由累積在這個物體上的力除以該物體的質(zhì)量得到的，根據(jù)的是以下這個公式：希望你還記得初中物理。在我們的例子中，作用在物體上的唯一的力是重力。它作用在物體上的加速度是個常數(shù)，可以立即被一個矢量表達出來。在我們的例子中，Y軸不能為負，例如有個物體的坐標是(0,-0.5,0)，這是不允許出現(xiàn)的。這就意味著，在一個時間片的開始時，我們計算每個物體的新的速度，并移動它們和檢測碰撞。如果在一個時間片內(nèi)發(fā)生了碰撞(例如假設(shè)一個時間片是1秒，而在0.4秒時發(fā)生了碰撞)，我們計算物體在這個時間時的位置，計算反彈后的速度，然后移動這個物體在剩下的時間(根據(jù)上面的假設(shè)是0.6秒)，再次進行碰撞的檢測在這剩下的時間內(nèi)，這

26、個過程不斷的被重復(fù)知道這個時間片完成。當有多個物體同時運動時，每個運動的物體都要根據(jù)靜態(tài)幾何學進行碰撞檢測，只有最近的一次碰撞才被記錄下來。當一個物體對所有其它物體的碰撞檢測都完成后，最近的一次和靜態(tài)物體的碰撞才被返回(這句我不太懂：The returned intersection is compared with the intersection returned by the static objects and the closest one is taken)。全部的仿真工作已經(jīng)在那個點上更新過了。(也就是說，如果最近的一次碰撞發(fā)生在0.5秒后，那么我們可以移動所有的物體0.5秒)，

27、發(fā)生碰撞的物體的反彈后的速度矩陣被計算，然后循環(huán)將繼續(xù)剩余的時間片斷。31.3、特效31.3.1爆炸每次當一個碰撞發(fā)生時，就會在碰撞點觸發(fā)一次爆炸。一個模擬爆炸的好方法是alpha混合。將兩個互相垂直的多邊形以碰撞點為中心進行alpha混合。這些多邊形會隨著時間的流逝而變大并逐漸消失。消失效果是通過改變多邊形各頂點的alpha通道的值，隨著時間的流逝從1變到0，就可實現(xiàn)。因為大量多邊形的alpha混合會導致問題和因為Z緩沖的問題而互相混合(在Red Book in the chapter about transparency and blending章節(jié)中有詳述)。我們借用了粒子系統(tǒng)的技術(shù)，為了得到正確的結(jié)果我們不得不將多邊形按照距離眼睛的遠近從遠及近進行排序，但是同時又禁用深度測試。(同樣在中有介紹)。注意我們限制了爆炸的最大數(shù)量是每幀20個。如果有更多的爆炸發(fā)生的話，緩沖區(qū)