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