嚴(yán)以律己,寬以待人. 三思而后行. GMail/GTalk: yanglinbo#google.com; MSN/Email: tx7do#yahoo.com.cn; QQ: 3 0 3 3 9 6 9 2 0 .
碰撞檢測(cè)做得好了是應(yīng)該的，不易被人注意到，因?yàn)檫@符合我們?nèi)粘Ｉ钪械某ＷR(shí)。做得差了卻很容易讓人發(fā)現(xiàn)，人物經(jīng)常被卡住不能前進(jìn)或者人物穿越了障礙。所以大部分人都覺(jué)得寫(xiě)碰撞檢測(cè)代碼是件吃力不討好的事情，算法復(fù)雜、容易出bug、不容易出彩。下面還是回到正題，看看我們?cè)撊绾谓鉀Q這個(gè)難題。
早期3D游戲的碰撞檢測(cè)多數(shù)基于格子或者BSP樹(shù)，基于格子的系統(tǒng)實(shí)現(xiàn)簡(jiǎn)單但精度不夠，不屬于嚴(yán)格意義的3D碰撞檢測(cè)。基于BSP樹(shù)的碰撞檢測(cè)一度十分流行，算法基本已經(jīng)成熟定型，但它的固有缺點(diǎn)卻使它不太適合現(xiàn)在的游戲。BSP樹(shù)需要很長(zhǎng)的預(yù)處理時(shí)間不適合加載時(shí)計(jì)算，BSP劃分經(jīng)常會(huì)產(chǎn)生原多邊形數(shù)三到四倍的多邊形，考慮到不用保存法線、顏色、uv等信息也要增加將近一倍的資源容量，在一個(gè)大的游戲中將模型資源的容量從200M增加到400M相信是大部分人都不愿接受的。目前對(duì)于任意復(fù)雜三角形集合（mesh）的碰撞檢測(cè)多數(shù)基于BVTree（bounding volume tree）,具體可以是aabb tree，obb tree或者K-dop tree，這也是當(dāng)今各種物理引擎和碰撞檢測(cè)引擎流行的做法。
上面是碰撞檢測(cè)按數(shù)據(jù)結(jié)構(gòu)不同的分類，按檢測(cè)方式又可以分為離散點(diǎn)的碰撞檢測(cè)和連續(xù)碰撞檢測(cè)（CCD continuous collision detection）。離散點(diǎn)的碰撞檢測(cè)是指定某一時(shí)刻T的兩個(gè)靜態(tài)碰撞體，看它們之間是否交迭，如果沒(méi)有交迭則返回它們最近點(diǎn)的距離，如果交迭則返回交迭深度，交迭方向等。連續(xù)碰撞檢測(cè)則是分別指定在T1、T2兩個(gè)時(shí)刻兩個(gè)碰撞體的位置，看它們?cè)谟?span>T1運(yùn)動(dòng)到T2時(shí)刻的過(guò)程中是否發(fā)生碰撞，如果碰撞則返回第一碰撞點(diǎn)的位置和法線。連續(xù)碰撞檢測(cè)是最為自然的碰撞檢測(cè)，可以大大方便碰撞響應(yīng)邏輯的編寫(xiě)，可以很容易避免物體發(fā)生交迭或者穿越。離散點(diǎn)的碰撞檢測(cè)則沒(méi)有那么友好，當(dāng)檢測(cè)到碰撞時(shí)兩個(gè)物體已經(jīng)發(fā)生了交迭，如果其中有三角形網(wǎng)格對(duì)象那么已經(jīng)有許多三角形發(fā)生了交迭，如何將兩個(gè)交迭的對(duì)象分開(kāi)并按合理的方式運(yùn)動(dòng)是一個(gè)挑戰(zhàn)。雖然連續(xù)碰撞檢測(cè)是最自然的方式，但它的實(shí)現(xiàn)非常復(fù)雜，運(yùn)算開(kāi)銷(xiāo)也很大，所以目前大部分成熟的物理引擎和碰撞檢測(cè)引擎還是采用了基于離散點(diǎn)的碰撞檢測(cè)，為了避免物體交迭過(guò)深或者彼此穿越，它們都要采用比較小的模擬步長(zhǎng)。
由于碰撞檢測(cè)引擎的復(fù)雜性和對(duì)效率的高要求，我們應(yīng)該盡量使用目前成熟的完整引擎，而不是自己去開(kāi)發(fā)。經(jīng)過(guò)評(píng)估，我決定采用Opcode碰撞檢測(cè)引擎來(lái)做游戲中人物和場(chǎng)景的碰撞檢測(cè)。Opcode的主要功能是用aabb tree管理復(fù)雜三角形集合來(lái)和射線、球體，立方體，另一個(gè)三角形集合等進(jìn)行離散點(diǎn)上的碰撞檢測(cè)，如果檢測(cè)到交迭則返回所有發(fā)生交迭的三角形。Opcode的特點(diǎn)是高度的內(nèi)存使用優(yōu)化和極好的效率，ODE物理引擎底層就采用它來(lái)做復(fù)雜三角形mesh的碰撞檢測(cè)，Opcode的作者也是NovodeX（PhysX前身）物理引擎的核心開(kāi)發(fā)人員，據(jù)說(shuō)NovodeX采用了Opcode的一個(gè)更優(yōu)化版本。由此可見(jiàn)Opcode的成熟與效率。
確定了要使用的引擎，下面要討論的算法就和具體引擎無(wú)關(guān)了，適合于任何離散點(diǎn)的碰撞檢測(cè)引擎。我們用AABB包圍盒來(lái)代表場(chǎng)景中的人物，看看如何實(shí)現(xiàn)文章開(kāi)頭所提出的效果。
首先解釋一下檢測(cè)地面的方式，沿人物包圍盒的四條豎邊向下投四條射線，射線的終點(diǎn)略低于人物的腳底（也就是說(shuō)射線的長(zhǎng)度是有限的），如果與場(chǎng)景發(fā)生碰撞并且碰撞平面的斜率小于某一值則取得碰撞點(diǎn)的高度，否則視為這條射線沒(méi)有檢測(cè)到地面。將所有射線檢測(cè)到的地面高度最大值作為最后的地面高度，如果四條射線都沒(méi)有檢測(cè)到地面則認(rèn)為人物懸空。
上面的算法基本達(dá)到了文章開(kāi)頭所提到的效果，在某些復(fù)雜情況下人物移動(dòng)還有些不流暢，但沒(méi)有發(fā)現(xiàn)人物有穿越障礙物的現(xiàn)象。在大部分情況下人物的新坐標(biāo)都會(huì)由p2點(diǎn)返回，最壞情況是人物被卡住返回p0點(diǎn)。在P4 3.0G的機(jī)器上可以支持120個(gè)人物在最壞情況下保持30幀的游戲幀數(shù)。
posted on 2007-12-29 12:08 楊粼波 閱讀(922) 評(píng)論(0) 編輯 收藏 引用
Powered by: C++博客 Copyright © 楊粼波