牽著老婆滿街逛

嚴以律己,寬以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

統(tǒng)計

隨筆 - 1513
文章 - 45
評論 - 907
引用 - 0

公告

言論：
1.每日自省；
2.享受人生；
3.盡力而為；
4.堅持不懈；
5.切莫急躁；
6.慎言敏行；
7.動心忍性；
8.上善若水。

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

搜索

積分與排名

積分 - 2533170
排名 - 2

閱讀排行榜

一種3D游戲碰撞檢測解決方案

轉載自:http://www.cnblogs.com/cproom/archive/2007/12/15/608732.html

碰撞檢測在3D游戲中至關重要，好的碰撞檢測要求人物在場景中可以平滑移動，遇到一定高度內(nèi)的臺階可以自動上去，而過高的臺階則把人擋住，遇到斜率較小的斜坡可以上去，斜率過大則把人擋住，在各種前進方向被擋住的情況下都要盡可能地讓人物沿合理的方向滑動而不是被迫停下。在滿足這些要求的同時還要做到足夠精確和穩(wěn)定，防止人物在特殊情況下穿墻而掉出場景。

碰撞檢測做得好了是應該的，不易被人注意到，因為這符合我們?nèi)粘Ｉ钪械某ＷR。做得差了卻很容易讓人發(fā)現(xiàn)，人物經(jīng)常被卡住不能前進或者人物穿越了障礙。所以大部分人都覺得寫碰撞檢測代碼是件吃力不討好的事情，算法復雜、容易出bug、不容易出彩。下面還是回到正題，看看我們該如何解決這個難題。

早期3D游戲的碰撞檢測多數(shù)基于格子或者BSP樹，基于格子的系統(tǒng)實現(xiàn)簡單但精度不夠，不屬于嚴格意義的3D碰撞檢測。基于BSP樹的碰撞檢測一度十分流行，算法基本已經(jīng)成熟定型，但它的固有缺點卻使它不太適合現(xiàn)在的游戲。BSP樹需要很長的預處理時間不適合加載時計算，BSP劃分經(jīng)常會產(chǎn)生原多邊形數(shù)三到四倍的多邊形，考慮到不用保存法線、顏色、uv等信息也要增加將近一倍的資源容量，在一個大的游戲中將模型資源的容量從200M增加到400M相信是大部分人都不愿接受的。目前對于任意復雜三角形集合（mesh）的碰撞檢測多數(shù)基于BVTree（bounding volume tree）,具體可以是aabb tree，obb tree或者K-dop tree，這也是當今各種物理引擎和碰撞檢測引擎流行的做法。

上面是碰撞檢測按數(shù)據(jù)結構不同的分類，按檢測方式又可以分為離散點的碰撞檢測和連續(xù)碰撞檢測（CCD continuous collision detection）。離散點的碰撞檢測是指定某一時刻T的兩個靜態(tài)碰撞體，看它們之間是否交迭，如果沒有交迭則返回它們最近點的距離，如果交迭則返回交迭深度，交迭方向等。連續(xù)碰撞檢測則是分別指定在T1、T2兩個時刻兩個碰撞體的位置，看它們在由T1運動到T2時刻的過程中是否發(fā)生碰撞，如果碰撞則返回第一碰撞點的位置和法線。連續(xù)碰撞檢測是最為自然的碰撞檢測，可以大大方便碰撞響應邏輯的編寫，可以很容易避免物體發(fā)生交迭或者穿越。離散點的碰撞檢測則沒有那么友好，當檢測到碰撞時兩個物體已經(jīng)發(fā)生了交迭，如果其中有三角形網(wǎng)格對象那么已經(jīng)有許多三角形發(fā)生了交迭，如何將兩個交迭的對象分開并按合理的方式運動是一個挑戰(zhàn)。雖然連續(xù)碰撞檢測是最自然的方式，但它的實現(xiàn)非常復雜，運算開銷也很大，所以目前大部分成熟的物理引擎和碰撞檢測引擎還是采用了基于離散點的碰撞檢測，為了避免物體交迭過深或者彼此穿越，它們都要采用比較小的模擬步長。

由于碰撞檢測引擎的復雜性和對效率的高要求，我們應該盡量使用目前成熟的完整引擎，而不是自己去開發(fā)。經(jīng)過評估，我決定采用Opcode碰撞檢測引擎來做游戲中人物和場景的碰撞檢測。Opcode的主要功能是用aabb tree管理復雜三角形集合來和射線、球體，立方體，另一個三角形集合等進行離散點上的碰撞檢測，如果檢測到交迭則返回所有發(fā)生交迭的三角形。Opcode的特點是高度的內(nèi)存使用優(yōu)化和極好的效率，ODE物理引擎底層就采用它來做復雜三角形mesh的碰撞檢測，Opcode的作者也是NovodeX（PhysX前身）物理引擎的核心開發(fā)人員，據(jù)說NovodeX采用了Opcode的一個更優(yōu)化版本。由此可見Opcode的成熟與效率。

確定了要使用的引擎，下面要討論的算法就和具體引擎無關了，適合于任何離散點的碰撞檢測引擎。我們用AABB包圍盒來代表場景中的人物，看看如何實現(xiàn)文章開頭所提出的效果。

首先解釋一下檢測地面的方式，沿人物包圍盒的四條豎邊向下投四條射線，射線的終點略低于人物的腳底（也就是說射線的長度是有限的），如果與場景發(fā)生碰撞并且碰撞平面的斜率小于某一值則取得碰撞點的高度，否則視為這條射線沒有檢測到地面。將所有射線檢測到的地面高度最大值作為最后的地面高度，如果四條射線都沒有檢測到地面則認為人物懸空。

vD = 當前幀人物位移

p0 = 人物包圍盒中心當前位置

bOnGroundP1; // 人物是否站在地面

bOnGroundP3; // 人物是否站在地面

bOnGround; // 人物是否站在地面

p1 = p0 + vD

在p1位置檢測地面

if( 檢測到地面 )

{

將包圍盒下放到地面得到位置p2

bOnGroundP1 = true;

}

else

{

p2 = p1;

bOnGroundP1 = false;

}

測試p2點的包圍盒是否與場景交迭

if( 交迭 )

{

取得所有交迭三角形的法線，將它們相加后取平均值，得到法線normal

將法線與向上的向量叉乘得到切線方向tangent

// 計算人物沿切線滑動后的位置，注意這里用p0做計算。

// 如果要使滑動更平滑可以把p0向法線方向推出一些

// p3 = p0 + normal * 0.1f + vD.Dot(tangent);

p3 = p0 + vD.Dot(tangent);

在p3位置檢測地面

if( 檢測到地面 )

{

將包圍盒下放到地面得到位置p4

bOnGroundP3 = true;

}

Else

{

p4 = p3;

bOnGroundP3 = false;

}

測試p4點的包圍盒是否與場景交迭

if( 交迭 )

{

測試p1點的包圍盒是否與場景交迭

if( 交迭 )

{

// 無法得到合理的移動位置，人物位置保持不變

// 等待下一幀玩家調(diào)整前進方向再做測試

將p0作為人物的新位置

bOnGround = true;

return;

}

else

{

將p1作為人物的新位置

bOnGround = bOnGroundP1;

return;

}

Else

{

將p4作為人物的新位置

bOnGround = bOnGroundP3;

return;

}

else

{

將p2作為人物的新位置

bOnGround = bOnGroundP1;

return;

}

上面的算法基本達到了文章開頭所提到的效果，在某些復雜情況下人物移動還有些不流暢，但沒有發(fā)現(xiàn)人物有穿越障礙物的現(xiàn)象。在大部分情況下人物的新坐標都會由p2點返回，最壞情況是人物被卡住返回p0點。在P4 3.0G的機器上可以支持120個人物在最壞情況下保持30幀的游戲幀數(shù)。

posted on 2007-12-29 12:08 楊粼波閱讀(930) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

牽著老婆滿街逛

導航

統(tǒng)計

公告

常用鏈接

留言簿(11)

隨筆分類(466)

隨筆檔案(1513)

文章分類(46)

文章檔案(45)

相冊

收藏夾(39)

工具官網(wǎng)

技術網(wǎng)站

開源網(wǎng)站

其他窩點

收藏網(wǎng)站

銀行官網(wǎng)

友情鏈接

資源共享

搜索

積分與排名

最新評論

閱讀排行榜

一種3D游戲碰撞檢測解決方案