碰撞檢測在3D遊戲中至關重要，好的碰撞檢測要求人物在場景中可以平滑移動，遇到一定高度内的台階可以自動上去，而過高的台階則把人擋住，遇到斜率較小的斜坡可以上去，斜率過大則把人擋住，在各種前進方向被擋住的情況下都要盡可能地讓人物沿合理的方向滑動而不是被迫停下。在滿足這些要求的同時還要做到足夠精确和穩定，防止人物在特殊情況下穿牆而掉出場景。
碰撞檢測做得好了是應該的，不易被人注意到，因為這符合我們日常生活中的常識。做得差了卻很容易讓人發現，人物經常被卡住不能前進或者人物穿越了障礙。是以大部分人都覺得寫碰撞檢測代碼是件吃力不讨好的事情，算法複雜、容易出bug、不容易出彩。下面還是回到正題，看看我們該如何解決這個難題。
早期3D遊戲的碰撞檢測多數基于格子或者BSP樹，基于格子的系統實作簡單但精度不夠，不屬于嚴格意義的3D碰撞檢測。基于BSP樹的碰撞檢測一度十分流行，算法基本已經成熟定型，但它的固有缺點卻使它不太适合現在的遊戲。BSP樹需要很長的預處理時間不适合加載時計算，BSP劃分經常會産生原多邊形數三到四倍的多邊形，考慮到不用儲存法線、顔色、uv等資訊也要增加将近一倍的資源容量，在一個大的遊戲中将模型資源的容量從200M增加到400M相信是大部分人都不願接受的。目前對于任意複雜三角形集合（mesh）的碰撞檢測多數基于BVTree（bounding volume tree）,具體可以是aabb tree，obb tree或者K-dop tree，這也是當今各種實體引擎和碰撞檢測引擎流行的做法。
上面是碰撞檢測按資料結構不同的分類，按檢測方式又可以分為離散點的碰撞檢測和連續碰撞檢測（CCD continuous collisiondetection）。離散點的碰撞檢測是指定某一時刻T的兩個靜态碰撞體，看它們之間是否交疊，如果沒有交疊則傳回它們最近點的距離，如果交疊則傳回交疊深度，交疊方向等。連續碰撞檢測則是分别指定在T1、T2兩個時刻兩個碰撞體的位置，看它們在由T1運動到T2時刻的過程中是否發生碰撞，如果碰撞則傳回第一碰撞點的位置和法線。連續碰撞檢測是最為自然的碰撞檢測，可以大大友善碰撞響應邏輯的編寫，可以很容易避免物體發生交疊或者穿越。離散點的碰撞檢測則沒有那麼友好，當檢測到碰撞時兩個物體已經發生了交疊，如果其中有三角形網格對象那麼已經有許多三角形發生了交疊，如何将兩個交疊的對象分開并按合理的方式運動是一個挑戰。雖然連續碰撞檢測是最自然的方式，但它的實作非常複雜，運算開銷也很大，是以目前大部分成熟的實體引擎和碰撞檢測引擎還是采用了基于離散點的碰撞檢測，為了避免物體交疊過深或者彼此穿越，它們都要采用比較小的模拟步長。
由于碰撞檢測引擎的複雜性和對效率的高要求，我們應該盡量使用目前成熟的完整引擎，而不是自己去開發。經過評估，我決定采用Opcode碰撞檢測引擎來做遊戲中人物和場景的碰撞檢測。Opcode的主要功能是用aabb tree管理複雜三角形集合來和射線、球體，立方體，另一個三角形集合等進行離散點上的碰撞檢測，如果檢測到交疊則傳回所有發生交疊的三角形。Opcode的特點是高度的記憶體使用優化和極好的效率，ODE實體引擎底層就采用它來做複雜三角形mesh的碰撞檢測，Opcode的作者也是NovodeX（PhysX前身）實體引擎的核心開發人員，據說NovodeX采用了Opcode的一個更優化版本。由此可見Opcode的成熟與效率。
确定了要使用的引擎，下面要讨論的算法就和具體引擎無關了，适合于任何離散點的碰撞檢測引擎。我們用AABB包圍盒來代表場景中的人物，看看如何實作文章開頭所提出的效果。
首先解釋一下檢測地面的方式，沿人物包圍盒的四條豎邊向下投四條射線，射線的終點略低于人物的腳底（也就是說射線的長度是有限的），如果與場景發生碰撞并且碰撞平面的斜率小于某一值則取得碰撞點的高度，否則視為這條射線沒有檢測到地面。将所有射線檢測到的地面高度最大值作為最後的地面高度，如果四條射線都沒有檢測到地面則認為人物懸空。
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( 交疊 )
{
// 無法得到合理的移動位置，人物位置保持不變
// 等待下一幀玩家調整前進方向再做測試
将p0作為人物的新位置
bOnGround = true;
return;
}
else
{
将p1作為人物的新位置
bOnGround = bOnGroundP1;
return;
}
}
Else
{
将p4作為人物的新位置
bOnGround = bOnGroundP3;
return;
}
}
else
{
将p2作為人物的新位置
bOnGround = bOnGroundP1;
return;
}
上面的算法基本達到了文章開頭所提到的效果，在某些複雜情況下人物移動還有些不流暢，但沒有發現人物有穿越障礙物的現象。在大部分情況下人物的新坐标都會由p2點傳回，最壞情況是人物被卡住傳回p0點。在P4 3.0G的機器上可以支援120個人物在最壞情況下保持30幀的遊戲幀數。
在使用廣義碰撞階段迅速排除了大量物體以後，将會使用精确到多邊形級别的精确碰撞，比如兩個凸包之間的碰撞，凸包和面片之間的碰撞，以及2次曲面和多邊形面片的碰撞，在遊戲中常用的兩次曲面有，橢圓體，圓柱體，膠囊，球體等等。對于兩個凸包之間的碰撞算法目前比較流行的是SAT，分離軸測試算法可以靜态和動态的計算出兩個凸包之間的碰撞時間法向量等等。但是對于面數較多的凸包以及2次曲面卻不大适合，此時一般使用GJK算法但是GJK算法本身強壯性的實作問題一直是一個較難的問題。在我的一項使用BSP進行碰撞檢測的實驗中，人物以膠囊來模拟，房屋内部通過非SOLID 的LEAFY BSP來構造，在使用BSP剔除了大量面片以後，遇到這樣一個問題：如何在最後篩選下的三角形面片進行碰撞測試，以确定碰撞發生的時間，法向量等。
本文提出一種簡單，易懂，準确的方法用來确定一個以速度v前進的膠囊和一個凸多邊形第一次發生碰撞的時間。
首先一個膠囊是所有到某根線段的距離等于某個值r的點的集合：
如圖：虛線表示該線段這裡以ab表示，r代表所有點到該線段的長度：
首先觀察靜态情況下的碰撞情況。當一個多邊形面片和膠囊碰撞的時候，實際上是該多邊形面片中存在一些點，這些點到線段ab的距離小于了r，這是因為在膠囊外部的點到線段ab的距離均大于r（膠囊是所有到某根線段的距離等于某個輸r的點的集合）。是以在兩個物體都靜止的情況下相交測試實際上是測試線段ab到多邊形的最短距離，如果該距離<R那麼存在碰撞，否則不存在碰撞：
如圖這裡以一個三角形為例子，左圖中該三角形的所有點到線段ab的距離均大于r是以和該膠囊不相交，而右圖中三角形的黑色區域中的點到線段ab的距離小于r是以該三角形和膠囊相交。
是以實際上隻要計算一條線段到某個多邊形的距離，然後和r作比較就可以知道是否發生碰撞。而一條線段和一個多邊形的距離計算，需要分以下幾個步驟（以三角形為例）
A将線段ab的2個端點投影到三角形所在平面，并檢查投影點是否落在三角形内部，如果是的話将該投影距離作為一個候選值
B分别計算線段ab和三角形的三條邊的最短距離點對，并檢查該點對中的點是否落線上段中（ab線段和三角形的邊線段中）如果是的話将該點對的距離作為一個候選值。
C分别計算線段ab的兩個端點到三角形每條邊的投影（實際上是計算最近點對），并檢查該投影是否落在邊的線段中如果是的話作為一個候選值儲存。
D分别計算三角形的3個頂點到線段ab上的投影，并檢查該投影是否落線上段ab中。如果是的話作為一個候選值儲存。
E 分别計算三角形的3個頂點到線段ab的兩個頂點，把距離作為候選值儲存。
這樣一來碰撞檢測就歸結為，點和線段，線段和線段，以及點和面的最短點對的計算了，
最後将上述的候選值進行比較，結果最小的那個就是三角形中到線段ab的距離。
上述方法非常容易推廣到動态的情況也就是：當膠囊以速度v運動時第一次和三角形發生碰撞的時間。問題歸結為在哪個時間T線段ab到三角形的距離等于半徑r，而這又歸結為上述A,B,C,D,E 5個子問題。如果能夠分别求出這5個子問題的時間，t1,t2,t3,t4,t5那麼取這5個時間中的最小值就是膠囊和三角形發生碰撞的确切時間了。
下面以兩條直線，一條靜止，另外一條以速度v移動作為例子，來說明求得時間的過程。問題等同于:
給定一條靜止，另外一條以速度v移動的直線，求出在哪個時間T這兩條直線的距離等于半徑r。
對于兩條直線，假設直線的方程分别為：
L1:P1+r1*t;
L2:P2+r2*t;
現在架設直線L2以速度v={vx,vy,vz}移動；
根據兩條直線的距離公式
d=|P1P2 .（r1Xr2）| /|（r1Xr2）|
其中P1P2是向量代表 P2-P1，X代表叉積，.代表點積
由于r1,r2是常量不會随着直線的移動而改變，這裡令（r1Xr2）=r={x*,y*,z*}
P1={x1,y1,z1}不變，P2={x2+vx*t, y2+vy*t, z2+vz*t}其中t代表時間是個變量
帶入公式d=|P1P2 .（r1Xr2）| /|（r1Xr2）|可得
d(t)=x*(x2-x1)+y*(y2-y1)+z*(z2-z1)+(x*vx+y*vy+z*vz)t
令(x*vx+y*vy+z*vz)=a; x*(x2-x1)+y*(y2-y1)+z*(z2-z1)=b;
那麼d(t) = at+b -----------------------------(1)
公式1就是兩條直線之間的距離随着時間t變化的函數，這是一個帶符号的距離，兩邊平方可得 d^2(t)= (at+b)^2
這是一個兩次方程，假設膠囊半徑為r 那麼隻要求解方程(at+b)^2=r^2這個方程就可以求出子問題B的時間了，同時注意計算出時間t之後還需要計算出該時間兩條直線的線最近點對是否都處在兩條對應的線段上，如果是的話才是一個合理的時間否則就抛棄該時間。
通過同樣的推導可以分别求出其他子問題的時間取這些時間，取這些時間的最小值就是碰撞第一次發生的時間，當然在求解2次方程過程中要考慮到delta<或者=0的情況這些情況都有自己的實體意義，以上面兩條線段距離為例d^2(t)= (at+b)^2中如果a=0
那麼方程恒等于b^2，考察a=0的實體意義，a=0也就是(x*vx+y*vy+z*vz)=0；其中x*,y*,z*是這兩條直線所組成的面的法向量
這表面移動速度平行于這兩條直線所組成的面。顯然距離是恒定不變的。
結論：
以上方法很容易推廣到凸多邊形，以及求出碰撞的法向量（根據最短時間是由上述A,BCDE中那種情況所引起的）。
在一般網遊的室内環境檢測中，使用膠囊模拟人物已經足夠了，結合BSP的漂亮剪枝能力，可以做出比較滿意和快速的碰撞檢測，人物和其他物件的碰撞可以采用凸包比較或者GJK方法等。
周末一天沒事寫個遊戲,好簡單的,裡面的亮點是碰撞檢測代碼,是我在國外論壇上看到的一個算法,算是很強的了.下面我貼出來,然後講一下大緻思路,關于遊戲的代碼就不貼了,一大串的看了也心煩 ^^"
點選浏覽該檔案
這個函數就是碰撞檢測的關鍵,我給它啟名叫 "描邊"
首先裡面兩個參數,第一個pmc就是要描邊的mc,第二個num是要描的級數(等下會解釋到),我們先可以先看下裡面的逐句解釋
| function doFigure(pmc, num) { // 為 pmc 建立一個數組 , 數組的大小是 num*2; pmc.point = new Array(num*2); // 從 pmc 的長和寬中取大的 , 然後除以 2 var mx = Math.max(pmc._width, pmc._height)/2; // 把 360 ℃ num 等分 var inc = 360/num; // 定義兩個變量等下用 var n = 0; var i = 0; // while循環的次數為 i<num*2;while (i<(num*2)) {//從下面n+=inc知道 xs和ys就是每一個等分上x和y的所指的方向var xs = Math.cos((n*Math.PI)/180);var ys = Math.sin((n*Math.PI)/180);//以pmc的(x,y)點為定點,半徑為mx的一個圓的軌迹var x = pmc._x+(mx*xs);var y = pmc._y+(mx*ys);//如果x,y沒有接觸到pmc上,不斷循環while (!pmc.hitTest(x, y, true)) {// x,y分别減x -= xs;y -= ys;//如果都小于0,就break跳出循環if (x<0 && y<0) {break;}}//把此時的x和y,分别計入point數組中pmc.point[i] = x-pmc._x;pmc.point[i+1] = y-pmc._y;n += inc;i += 2;}} |
他這麼做到底什麼意思呢?
其實point裡面就是記錄了,一個圖形的邊緣的坐标.他是怎麼做到的?
我們抛開所有從最裡面的while循環講起吧.
while的條件是,當(x,y)點沒有接觸到pmc的時候,就不斷循環,循環的内容是 x-=xs,y-=ys;
如果我們前面什麼也沒看,應該可以想象,一開始(x,y)點一定在pmc的右邊,然後不斷的減一個數值xs,ys,直到減到x,y碰到pmc為止,這樣,x,y就是pmc上的一點坐标了.
但是我們目前還不知道x和y是怎麼定義的,還有就是xs和ys怎麼來的
往上看
var xs = Math.cos((n*Math.PI)/180);
var ys = Math.sin((n*Math.PI)/180);
var x = pmc._x+(mx*xs);
var y = pmc._y+(mx*ys);
數學好的,一看就看出來了,這是圓的極坐标公式,就是以pmc的(x,y)為定點,mx為半徑的圓的軌迹.
看到這裡,應該可以猜到,一定是讓一些點以圓的方式出現在mc的周圍,然後每個點往mc靠攏,知道每個點都靠到mc上面.
這樣我們隻要解決這個圓的大小問題了,也就是mx的大小,實際上,你把mx定義成一個很大的數也沒問題,但是這樣做,會浪費很多,對于寫程式的來說,不必要的浪費是不行的^^
那麼看上面的
var mx = Math.max(pmc._width, pmc._height)/2;
這裡就定下了 mx的大小,也就是從mc的長和寬中找一個較大的出來,這樣可以保證畫出來的圓把整個mc都抱在了裡面,大家看到除以2了吧,是以一定能想到 mc 的注冊點一定是在中心哦(這也是關鍵之一^^)
接着,和定義半徑大小一樣,我們做個360度每一度檢測一下,也是可以的,但是這樣做會很費資源,而且也沒有必要那麼精細.
是以才會有一個描邊級數num,這個級數就是規定了,分num個等次來描,來記錄num個點的坐标.然後就是運用了
随便畫個形狀,在這個mc中寫下面的代碼,場景上再建立一個mc,命名為mc2
你可以看到,你的描邊級數越高,每次檢測的就越多,是以盡量減少就可以了,像我遊戲裡面隻定義了10.
其實這隻是一個大概的資料,并不是百分百的描邊,不過這樣已經夠用了^^"
| onClipEvent (load) { numb = 100; _root.doFigure(_name, numb); } onClipEvent (enterFrame) { _root.hit = false; i = 0; while (i < (numb * 2)) { x = points[i] + _x; y = points[i + 1] + _y; if (_root.mc2.hitTest(x, y, true)) { _root.hit = true; break; } i = i + 2; } } onClipEvent (mouseDown) { if (this.hitTest(_root._xmouse, _root._ymouse, true)) { this.startDrag(); } } onClipEvent (mouseUp) { this.stopDrag(); } |
數學不好,解釋的不太清楚,大家不懂的再發貼問,我盡量解釋,當然也請高手幫忙完善^^!
轉】MSDN中關于OnDrawItem的說明
afx_msgvoidOnDrawItem(intnIDCtl,LPDRAWITEMSTRUCTlpDrawItemStruct);
Parameters
nIDCtl
存儲發送WM_DRAWITEM消息的控件ID，如果是菜單發送的，nIDCtl的值為0。
lpDrawItemStruct
一個指向DRAWITEMSTRUCT結構體的指針，該結構體儲存有關要被繪制的項目與繪制所需要的類型等星系。
Remarks
當自繪按鈕(owner-draw button)，下拉清單框(combo box)，清單框(list box)視覺屬性，或者菜單發生變化時，架構為他們的owner調用該函數。
DRAWITEMSTRUCT結構的itemAction成員定義了要進行的繪制操作行為。該值确定了所需的繪制動作。
在處理完此消息之前，應用程式應當確定由DRAWITEMSTRUCT結構的成員hDC辨別的裝置上下文還原到預設狀态。
如果上面結構的成員hwndItem指向CButton，CMenu，CListBox或者CComboBox對象，那麼就調用相應類的DrawItem虛函數。重載相應類的DrawItem成員函數來繪制各個項。
其他的一些說明：
OnPaint()這個函數是在已經有形的控件上進行畫圖的
OnPaint()
{
在這裡隻是畫原控件沒有的圖形
}
OnDrawItem()這個函數是自已去繪畫一個控件，根據你想要的形狀，圖案.它是建立一個控件的外表而用到的
可以這樣了解，OnDrawItem是畫視窗中的子控件的，因為它的入口參數LPDRAWITEMSTRUCT帶入不同子控件的相關參數，而且，你得把字控件設定成“自畫”類型，才會調用到OnDrawItem，順便說一下自畫，不是所有設定成自畫類型的控件都會調用父視窗的OnDrawItem，例如ListBox的自畫，你就必須重載CListBox的DrawItem方法和MeasureItem方法才可以，但象菜單，按鈕等的自畫則會調用OnDrawItem。OnPaint和OnDrawItem不在一個範疇内，他是WM_PAINT的響應函數，凡是基于CWnd的類都有OnPaint事件發生，就是說凡是視窗都有WM_PAINT事件發生。（不知道我了解的對不對）
2009産品創新數字化峰會征文：基于CAD的碰撞檢測技術及其在虛拟裝配拆卸系統中的應用
1 引言
幾何形體間的碰撞檢測在虛拟裝配和拆卸過程中幾乎無處不在，碰撞檢測的精度決定了虛拟裝配和拆卸的精度，對于目前的商用VR開發平台而言，普遍采用多邊形（通常是三角形）描述場景中的任意幾何形體，并通過紋理映射、光照模型來模型物體在真實世界的視覺效果。而多邊形模型首先是面模型，面模型不包括物體的内部資訊，無法計算由面所組成的體之間的空間幹涉情況，隻能計算面面之間的相交情況；其次多邊形模型隻是對形體幾何的逼近形式，對形體的逼近程度決定了三角形面片數量的多少，逼近程度越高，三角形網格數量越多，渲染和碰撞檢測的時間開銷越大；對形體的描述形式決定了基于多邊形網格的碰撞檢測算法難以實作物體間的精确碰撞檢測。
精确的碰撞檢測首先要保證模型是精确的，其次要保證碰撞檢測算法要基于精确模型之間的空間相交求解。在目前一些大型的商用CAD軟體中，如UG、Pro/E等，不僅采用初等解析曲面和樣條曲面定義幾何物體的外形輪廓曲面，而且采用的是體模型，能夠準确定義幾何物體的内外部空間，同時其提供的靜态幹涉檢查功能和算法是成熟的，分析時間是高效的，本文通過把商用CAD系統提供的幹涉檢查功能無縫內建到定制開發的虛拟裝配和拆卸系統中，一方面能夠實作形體間的精确碰撞檢測，同時能夠快速地繪制場景以實作互動，并進一步通過采用諸如包圍盒等方式構造合适的精确碰撞檢測加速政策，快速排除大量不會發生碰撞的物體對，降低複雜場景中進行精确碰撞檢測的開銷，提高虛拟裝配/拆卸系統的實時性。
2 總體技術方案
目前商用的VR開發平台均不提供基于CAD幾何模型的精确碰撞檢測功能，而隻提供基于多邊形相交測試的碰撞檢測功能，不僅碰撞檢測精度難以提高，而且由于難以判别包容幹涉、接觸幹涉、硬幹涉三種之間的差別，對于虛拟裝配和拆卸過程中廣泛存在的對齊、貼合、相切等情況難以得到正确的碰撞檢測結果，進而影響系統對這類情況做出正确的反應。
通過深入的研究和程式開發，本文在VR環境中實作了基于CAD幾何模型的快速精确碰撞檢測功能，圖1是系統結構框圖。
從圖中可以看出，CAD模型是聯系前台的場景展示和背景的碰撞檢測計算的紐帶，一方面，基于CAD的精确碰撞檢測平台在背景對CAD模型進行空間幹涉計算，另一方面，前台根據CAD模型動态生成場景圖并進行繪制以用于使用者互動，進而将仿真的三維顯示和仿真計算分離。當場景中的幾何對象發生運動時，通過在二者之間建立的通訊技術同步更新運動的幾何對象在場景中的幾何方位并保持一緻。幾何對象運動過程中的幹涉計算采用離散時間步的方法進行計算，即：幾何對象運動時，在場景中以一定的時間間隔步進，同時把該物體運動後的空間方位通過通訊傳遞給背景用于計算的CAD碰撞檢測平台，在背景同步更新運動部件的空間方位後，與其它部件在該時刻進行靜态的碰撞幹涉計算，然後得到并分析計算結果，并把計算結果通過通訊計算傳遞到前台VR環境控制端，如果部件間沒有發生幹涉，則繼續進行下一個步進動作，否則在場景中發出幹涉信号并做出相應的反應。這樣隻要步進的距離或角度足夠合理，可以獲得幾何對象運動過程中可能發生的任何幹涉情況。
圖1系統結構框圖
3 關鍵技術
3.1基于CAD的精确碰撞檢測算法及其程式實作
CAD互動界面下的幹涉檢查功能無法實作批量自動化處理，顯然無法內建到定制開發的VR系統中去，為此，必須找到脫離CAD互動運作界面的程式自動化計算方法。通常而言，高端商用CAD系統提供有二次開發包，在其開發包上進行二次開發有望實作幹涉檢測的程式自動化處理。
UG NX是高端CAD系統，其提供的二次開發工具NX/Open功能強大，在NX/Open的基礎上能夠開發實作任意幾何對象之間的精确碰撞檢測的自動計算。
使用NX/Open的進行幹涉檢查分析的步驟如下：
1)建立一個間隙分析資料集，配置設定空間并設定相關屬性
2)設定間隙分析模式，允許采用實體模型或多邊形網格模型進行幹涉檢查。
3)設定間隙分析規則，設定需要排除的幹涉檢查對。
4)設定間隙分析中用于分析的幾何對象。
5)進行間隙分析，對上面的設定進行幹涉分析。
6)對計算結果進行分析。從計算結果中找到發生硬幹涉的物體對以及幹涉區域。
使用NX/Open進行幹涉檢查的計算結果的幹涉類型分為如下4類：
1)不幹涉：幾何對象間沒有發生幹涉；
2)包容幹涉：一個幾何對象在另一個幾何對象内部；
3)硬幹涉：兩個幾何物體在三維空間存在空間位置重疊并且存在相交的空間曲面；
4)接觸幹涉：兩個幾何物體在三維空間存在點或空間曲面接觸，但不存在公共的實體空間；
通過對幹涉計算結果進行分析，可以得到任意兩個幾何對象間的準确的空間幹涉情況。
3.2基于CAD的VR場景圖動态生成技術
商用VR開發平台不能識别并繪制CAD模型，商用的VR開發平台通常隻支援多邊形網格模型，而CAD模型是由參數曲面組成的三維實體模型，為了在VR開發平台下渲染CAD模型，必須根據CAD模型的層次結構動态生成VR場景圖對象。
根據CAD模型動态建立VR場景圖的關鍵在于把CAD參數曲面轉換為某張逼近程度的多邊形網格模型，并按照規定的層次和結構組合成一顆場景樹。
對于一個UG裝配檔案，采用如下方式組織VR場景圖（VR開發平台采用Vega Prime）：
1)在Vega Prime場景圖根節點上建立一個vpObject組節點，UG裝配檔案根節點對應于該組節點。
2)對于UG裝配中的每一個部件，在Vega Prime場景圖中建立一個vpTransform節點，并把該節點作為第一步建立的vpObject節點的子節點。根據該部件在裝配中的空間方位矩陣定義一個vpTransform節點中的方位矩陣，如果該部件是零件模型，則建立一個vsGeometry節點，并把該節點作為vpTransform的子節點；如果該部件仍然是一個裝配模型，則再建立一個vpTransform節點，并把該節點作為上一級vpTransform的子節點，把該vpTransform節點作為父節點遞歸調用步驟2；
通過如上步驟，建立了與CAD模型層次結構類似的Vega Prime場景圖結構。
CAD幾何模型到多邊形網格模型的轉換需要借助于具體的參數曲面離散和多邊形網格剖分算法，對于不同類型的的參數曲面，曲面離散和多邊形網格剖分算法複雜程度不同，文獻[1]對此有詳細的描述。
3.3 可視化前端與背景計算端的幾何對象空間方位同步機制
由于用于使用者互動的可視化前端繪制的是由參數曲面離散生成的多邊形網格，而背景碰撞檢測計算采用的是最初的CAD模型，為了保證碰撞檢測結果的正确性，必須保證這兩個環境中的部件在任意時刻的空間相對方位保持一緻。基于CAD的VR場景圖動态生成技術保證了在初始時刻二者在空間方位上的一緻性，同步機制需要保證在任意時刻運動部件在二者當中具有同樣的運動特性。采用如下步驟保證二者中的幾何對象空間方位的一緻性：
1)在Vega Prime場景圖節點對象和CAD中的幾何對象之間建立一一映射關系，隻有建立了一一映射關系，才有可能當使用者在互動界面中選擇并移動或旋轉了某個幾何對象時，系統才能指導該幾何對象對應于CAD中的哪一個幾何對象，并進行相應的平移或旋轉。
2)定義一個結構，該結構用于描述平移或旋轉的類型及所有參數以及碰撞檢測結果，變換的類型及參數用于在CAD計算端進行同樣的變換操作，碰撞檢測結果用于訓示可視化前端進行相應的響應。該結構定義如下：
Struct CommunicationData{
Tag_t motionprt; //目前運動的幾何對象
Unsigned int motiontype; //0代表平移，1、2、3分别繞xyz軸旋轉
Double translate[3]; //代表進行平移的坐标值
Double angle; //代表旋轉的角度值
BOOL bIsCollision; //代表是否發生空間幹涉 }
3)當可視化前端選中某個幾何對象并進行相應的運動後，填充CommunicationData中的資料并傳遞到CAD計算端，CAD計算端根據旋轉或平移的大小重新計算運動部件在CAD場景中的方位矩陣，最後采用UF_ASSEM_reposition_part_occurrence或者UF_ASSEM_reposition_instance函數把運動部件放置在新的位置。
4)CAD端計算運動部件在新的方位處與其它部件之間的空間幹涉情況，如果幹涉計算結果為硬幹涉，則發生空間幹涉，填充CommunicationData結構中的bIsCollision域并通知可視化前端，可視化前端擷取該值并做出相應的反應。
3.4 碰撞檢測加速政策
層次包圍盒方法的基本思想是用體積略大而幾何特性簡單的包圍盒來近似描述複雜的幾何對象，進而通過構造樹狀層次結構來逼近對象的幾何模型，直到幾乎完全獲得對象的幾何特性，進而隻需對包圍盒重疊的部分進行進一步的相交測試。層次包圍盒最重要的特點是能夠應用于任意形狀的幾何對象的物體的碰撞檢測，是以也是目前應用最廣泛的一種碰撞檢測方法。
層次包圍盒樹根據包圍盒類型的不同又可分為包圍球、AABB、OBB、k-Dop等等，對應于每一類的包圍盒都有一個代表性的碰撞檢測算法，包圍盒的示意圖如圖6所示：
表1是對幾種基本包圍盒的碰撞檢測算法的性能比較，沿坐标軸的包圍盒AABB（axis-aligned bounding boxes）是使用的最久也是最廣的包圍盒類型，一個給定對象的AABB被定義為包含該對象且各邊平行于坐标軸的最小的六面體。其計算十分簡單，隻需分别計算組成對象的基本幾何元素集合中各個元素的頂點的X、Y、Z坐标的最大值和最小值即可；兩個AABB相交當且僅當它們在三個坐标軸上的投影區間均重疊，AABB間的相交測試最多隻需要6次比較運算。AABB也是衆多VR開發平台廣泛支援的包圍盒類型，為此，本文采用AABB作為標明的包圍盒類型。
本文采用AABB層次包圍盒加基于CAD模型的精确碰撞檢測算法實作碰撞檢測，其中層次包圍盒算法用于快速排除場景中沒有發生幹涉的物體對，對于采用層次包圍盒算法計算後仍然幹涉的物體對，用采用基于CAD模型的精确碰撞檢測算法進行準确的碰撞檢測，這樣一方面保證了碰撞檢測結果的正确性，另一方面能夠大大降低碰撞檢測的時間開銷。
表1基本包圍盒碰撞檢測算法比較
4 應用執行個體及結論
圖3是在Vega Prime中開發的原型系統的程式運作界面，在該原型系統中，通過選擇運動部件并設定運動路徑（平移和旋轉），程式通過計算運動部件運動過程中與其它部件的空間幹涉情況來判斷該運動過程是否存在幹涉，空間幹涉的結果根據在運動過程中運動部件和非運動部件的UG CAD模型的空間幹涉情況得出。
圖3原型系統運作界面
圖4用于碰撞檢測測試的模型
圖4是用于虛拟安裝測試的模型，需要把紅色部件插入到另一個部件的中心圓孔中（圓孔直徑與紅色物體外徑相同），實際上，在插入圓孔的過程中，它們之間隻存在接觸幹涉,而不存在空間硬幹涉，對此，基于CAD模型的精确碰撞檢測算法可以正确識别，而基于多邊形相交測試的碰撞檢測算法隻能把這類情況作為發生幹涉進行處理。
表2顯示了在p4 3.4GCPU，4G記憶體和Nvidia Quadro Fx1400顯示卡微機上進行測試時（紅色物體逐漸插入圓孔中心，采樣100幀的平均值）不同碰撞檢測算法和時間開銷比較表。
表2幾種碰撞檢測算法計算的平均時間開銷
從試驗結果可以看出，基于CAD模型的精确碰撞檢測算法可以區分接觸幹涉和硬幹涉以及包容幹涉之間的差別，同時可以在很快的時間開銷下完成幾何物體間的精确碰撞檢測，采用層次包圍盒可以進一步降低碰撞檢測的時間開銷，而采用基于多邊形一一相交測試的碰撞檢測算法的時間開銷随着用于碰撞檢測的多邊形數目的增加而急劇增加。
實踐證明，本文提出的技術方案切實可行，不僅解決了商用VR開發系統中碰撞檢測精度難以提高的技術問題，而且用于精确碰撞檢測的時間開銷能夠滿足工程實際需要。
[參考文獻]
[1] 趙瑛峰，NX Openflight資料交換輸出接口開發技術研究[J]，産品數字化實踐論文集，電子工業出版社，2008.5
// 球體－球體的碰撞 Sphere-Sphere Collision bool IsCollidingSphereToSphere() { // 兩個小球的相對速度 relative_vel = Sphere2_Vel - Sphere1_Vel; r = Sphere1_Radius + Sphere2_Radius; relative_position = Sphere2_Center – Sphere1_Center; // 檢查兩個小球是否已經碰撞 if ((Sqr_relative_position - (r*r)) <= 0) // 提前跳過測試：如果兩個小球朝向遠離對方的方向移動，則傳回false //這裡我們需要檢測兩次update之間是否存在碰撞 if (rel_distance < (sqrt(Sqr_relative_vel)*update_interval)) { time_fract = rel_distance/sqrt(Sqr_relative_vel); time_remain = update_interval – time_fract; if ((Sqr_relative_pos - (r*r)) <= 0) { return true; } } return ((relative_movement * relative_movement - ((Sqr_relative_pos - r*r) - Sqr_relative_vel)) > 0); // 球體－平面的碰撞 Sphere-Plane Collision bool IsCollidingSphereToPlane() { // 提前跳過測試：檢查小球是否可以在沒有碰撞的情況下移動， // 如果可以，則傳回false； // 如果不可以則檢測球體與平面之間的距離是否為 for (int i=0; i<6; i++) { // 小球的速度與平面法向量的點積 // 如果點積為，則速度矢量平行與平面，是以不可能碰撞 float unit_normal_vel_dot = normal . velocity; if (unit_normal_vel_dot < 0.0f) { // 計算平面公式 float D1 = normal * point_on_plane; float normal_pos_dot = normal . center_S; // 計算球心到平面的距離 float distance = (D1-normal_pos_dot)/unit_normal_vel_dot; // 這裡處理球體已經接觸到盒子的情況 if (distance <= radius1) { collide = true; // 存儲這個面的法向量 } break; } else { float Projected = velocity * update_interval; // 這裡處理球體在update_interval時間移動距離x， // 但是x小于球與平面的距離的情況 if (Projected > distance) { collide = true; time_fract = (distance–radius)/velocity; time_remain = update_interval - time_fract; } break; } } return collide; 物移動控制是單機和網遊中比較重要的部分，但前單機遊戲使用動力學以及IK動畫等已經達到了非常逼真的地步，在大型網絡遊戲中這樣的實體模拟同步是很實作的，是以在目前多數網遊中仍舊是采取使用一個包圍體（盒子或者膠囊）來模拟人物。一個好的移動系統是很重要的，平滑的貼牆滑動以及下滑，跳躍等會帶給玩家順暢的手感否則則會有種奇怪的感覺，本文具體介紹了一下碰撞反應，包括貼牆滑動等的具體實作細節。包括一個demo執行個體 。
目前實體引擎裡面大多自帶獨立于剛體的人物角色控制，但是實體引擎需要特定的實體模型命名以及比較大的實體模拟開銷度。如果需要定制自己的特别功能或者需要簡化計算（同時模拟多個延遲或者玩家的反應）。就必須自己完成人物碰撞反應控制的代碼。
要完成人物發生碰撞以後的行為控制，需要碰撞檢測系統提供以下的碰撞資訊，對于每一個碰撞：
1． 碰撞發生的時間
2． 碰撞的法向量
3． 碰撞點
對于基本的人物碰撞控制反應來說，以上3點是必須的，有時還需要提供和包圍體發生碰撞的具體三角形資訊。
對于場景上的物體首先使用膠囊所在的包圍盒AABB或者OBB和場景中的碰撞體包圍盒作層次碰撞裁減，至于具體怎麼組織可以任意，比如可以采用AABB或者OBB樹，也可以采用簡單的球樹。但碰撞進行到樹的葉子節點後開始檢測人物的AABB盒和該AABB盒所包圍的OBJECT的碰撞情況。如果發現這2個AABB（OBB）盒将會發生碰撞，那麼開始使用人物的膠囊體和景物所帶的三角面片進行精确到polygon soup級别的比較。這時候仍舊可以優化，比如說我還做了一步把一個Object中的三角形面片打成BSP樹的形式存儲起來，這樣可以大大減少膠囊和三角形碰撞檢測的次數，因為這種動态檢測是十分耗時的。有關膠囊和三角形面片的比較可以參考：http://dev.gameres.com/Program/Abstract/Arithmetic/capsule.mht中的方法。 對于BSP的劃分以及AABB碰撞檢測就不用多說了~到處都可以找到文章。
對于地形而言，也是采用同樣的方法，隻不過對于地形而言三角形資訊不用額外存儲，隻需要使用和渲染相同的三角形（對于景物來說一般不會使用渲染用的三角形而會使用更加簡化數量更少的簡化網格碰撞模型）。這裡可以有很多優化的技巧，因為地形本身是規則的cell一個地形是由若幹個patch(一般是16X16)組成的，而每個patch是由若幹cell(一般是16X16)組成的。對于patch來說一般已經組織到了一顆QUADTREE中了因為視棱錐裁減也需要這種結構，是以碰撞檢測中的AABB-AABB階段使用這顆已經存在的QUADTREE就可以快速的完成層次碰撞檢測了。但發現某個patch中的AABB和人物的AABB發生碰撞後需要檢測每一個CELL所在的AABB和人物AABB盒的碰撞，這裡可以使用點小技巧比如說首先将AABB盒投影到CELL所在的XY平面上，找出被投影覆寫的那些CELL然後再檢測這些CELL的AABB盒是否和人物的發生碰撞。一但确定了某個CELL和人物發生碰撞那麼就可以将該CELL中的三角形取出（一般為2個）依次和人物所在的膠囊進行三角形-膠囊的碰撞檢測。
這樣當碰撞檢測系統完成任務以後我們将會獲得一個碰撞資訊的數組：
class CollideInFo{
public:
GFVECTOR_3D m_worldcdnorm;//碰撞法向量
GFPOINT_3D m_worldpoint;//碰撞點
float m_cdtime;//碰撞時間
};
CollideInFo collidearray[]；
然後使用這個數組就可以進行碰撞後的處理了包括，沿牆滑動下滑等等。在具體說明整個人物移動控制算法之前，首先說下動态碰撞檢測和靜态碰撞檢測的差別，動态碰撞檢測是指物體A以速度V前進了T時間，在這期間第一次和物體B發生碰撞的時間。這樣的碰撞檢測必須傳回第一次2個物體發生碰撞的時間。而靜态檢測是指2個不動的物體是否互相相交對于這種檢測是不需要傳回時間的。動态檢測算法比靜态的複雜而且也耗用更多的時間。一個完善的碰撞系統需要解決以上2種碰撞檢測，如果你不想自己寫檢測代碼，目前比較流行的有OPCODE，SOLID庫等檢測庫 。你可以直接使用他們提供的功能，這裡我采用的是自己寫檢測代碼的方法，目前隻用到三角形-膠囊，AABB-AABB，OBB-OBB的碰撞檢測。 [Page]
完成了包圍體（用的是膠囊）和三角形的碰撞，膠囊和BSP，地形的碰撞檢測之後，擁有了碰撞的資訊 1。碰撞時間。2。碰撞法向量。3。碰撞點。接着就可以處理人物在碰撞後的反應了。
首先人物的一次移動分2個階段，第一個是初始階段，使用靜态碰撞檢測獲得該階段的速度（具體做法在後面說）。第2階段使用該速度去做動态碰撞檢測得到碰撞資訊，根據這些碰撞資訊去處理碰撞後的反應。
先來看第一階段，過程對于一個膠囊我們需要擷取他周圍的臨近面片的資訊，以決定這個膠囊目前所處平面的傾斜度，是否貼着不可通過的牆等等。我采用的方法是将膠囊體略為膨脹一些，然後調用靜态碰撞檢測的代碼擷取和該膨脹後的膠囊體相交的三角形面片碰撞資訊如圖：
棕色的是原始的膠囊體，紅色的表示将膠囊半徑略為增加以後的膠囊體，藍色的2個地形是将膠囊膨脹以後所發生相交的2個三角形，而如果不采用膨脹的話該膠囊是不和任何三角形相交的，具體膨脹數值可以設為膠囊下落的最小高度，比如你設定膠囊離底部物體超過0.6機關屬于騰空狀态的話你就将膨脹數值設為0.6。在這個例子中我們将會檢測到2個碰撞（藍色部分）這2個碰撞法向量正好是這2個三角面的法向量（在很多情況下也可能不是這個看你的碰撞代碼中法向量是如何計算的了）。其中底部的那個是可行走平面，另外一個是不可行走平面，有了這2個碰撞平面就很簡單了，如果使用者輸入的速度和那個不可行走的平面相反（也就是撞向那個不可行走平面），那麼那個不可行走平面是有效的，這樣他和底部那個可行走的平面所組成的交線就是人物的初始速度，如果使用者輸入的速度和那個不可行走的平面法向量相同，那麼這個不可行走平面沒有作用人物最終的速度就是把使用者速度投影到該可行走平面上的速度。
0頂一下
具體計算是否能夠水準移動以及移動速度的算法：當給出M個不可行走平面和N個可行走平面時：
1首先将速度在N個可行走平面上分解，檢查這些分解的速度是否有效（如何判斷速度有效下面會說道）
2如果在1的時候存在一個有效的速度直接傳回該速度
3沒有有效速度，這時檢查NXM個平面的交線，将速度在上面分解同時檢查是否存在有效速度
4如果存在有效速度傳回該速度
5否則檢查MXM條交線的，将速度在上面分解同時檢查是否存在有效速度
6如果存在有效速度傳回該速度
7否則傳回0速度
那麼如何判定速度是否有效呢，首先我們知道了所有碰撞的資訊，給定一個速度，如果該速度和所有碰撞的法向量的夾角都是小于90度那麼這就是個有效速度，（說明該分解後速度不會引起和這些碰撞面的在一次碰撞，因為該速度是将物體拉下遠離該平面的方向的）。如果隻要有一個夾角大于90度那麼該速度就是非有效速度，同時在移動時還要判斷該速度的傾斜角是否大于最大下滑傾斜角。注意 5是很重要的因為2個不可行走的平面所形成的交線仍舊可能是可以行走的，甚至是水準的。
以上的部分是檢查是否能夠水準移動的，如果不能水準移動那麼該物體會下滑，1如果沒有檢測到碰撞平面說明物體處于騰空狀态，這時候給物體加上重力加速度，産生一個往下的速度和原來的水準速度結合起來（如果存在）。
如圖棕色是原始狀态膠囊經過上一幀移動後到達藍色的位置這時通過上訴算法可以檢測到膠囊騰空，這時他的速度為水準速度（紅色）+下滑速度（綠色）。
2如果檢測到碰撞平面但是平面以及它們的交線都是不可行走的（傾斜角大于可行走角度）那麼依次将目前速度在碰撞平面分解，以及檢測每一條可能下滑的交線。得出速度後檢測是否是有效速度具體過程和前面檢查水準速度時的方法一樣，隻是将速度投影到平面上的方法不一樣具體方法可以根據程式需要，我這裡采用首先去掉原始速度在碰撞平面法線的分量，然後将速度分解為2個速度一個是貼着平面水準移動的速度另外一個是貼着平面下滑的速度。注意如果上一幀更新後物體處于下滑狀态那麼目前速度就因該是該下滑速度，否則則是使用者輸入的速度。
如果使用者輸入的速度是跳躍也就是帶Z分量的速度那麼，計算初始速度這一步需要略過直接輸入給下一階段使用者起跳的速度。
階段2計算初始速度引起的碰撞
對于多數情況來說，計算完初始速度就不會再發生碰撞了，一旦發生，那麼我們依舊傳入碰撞面的那些法向量，碰撞點的資訊，同樣采用前面計算初始速度時所采用的方法，計算出碰撞後的調整速度。 [Page]
整個處理過程基本上就是這樣的，其中可能還會出現一些小問題比如說誤差控制等。總結一條就是人物行走要麼研着平面分解速度要麼沿着2個平面的交線行走或者下滑。這個是Demo示例畫面（由于沒有人幫我做動畫。。是以demo中目前隻有行走動畫，沒有起跳，下落等動畫。。）