碰撞檢測技術

1、碰撞檢測技術碰撞檢測技術碰撞檢測技術2011-05-0623：00技術一引擎2008-09-0519：50：55閱讀25110.3碰撞檢測技術到目前為止，構造的各種對象都是相互獨立的，在場景中漫游各種物體，墻壁、樹木對玩家（視點）好像是虛設，可以任意從其中穿越。為了使場景人物更加完善，還需要使用碰撞檢測技術。10.3.1碰撞檢測技術簡介無論是PC游戲，還是移動應用，碰撞檢測始終是程序開發(fā)的難點，甚至可以用碰撞檢測作為衡量游戲引擎是否完善的標準。好的碰撞檢測要求人物在場景中可以平滑移動，遇到一定高度的臺階可以自動上去，而過高的臺階則把人物擋住，遇到斜率較小的斜坡可以上去，斜率過大則會把人物擋住，

2、在各種前進方向被擋住的情況下都要盡可能地讓人物沿合理的方向滑動而不是被迫停下。在滿足這些要求的同時還要做到足夠精確和穩(wěn)定，防止人物在特殊情況下穿墻而掉出場景。做碰撞檢測時，該技術的重要性容易被人忽視，因為這符合日常生活中的常識。如果出現(xiàn)Bug,很容易被人發(fā)現(xiàn)，例如人物無緣無故被卡住不能前進或者人物穿越了障礙。所以，碰撞檢測是讓很多程序員頭疼的算法，算法復雜,容易出錯。17/42對于移動終端有限的運算能力，幾乎不可能檢測每個物體的多邊形和頂點的穿透，那樣的運算量對手機等設備來講是不可完成的，所以移動游戲上使用的碰撞檢測不可能使用太精確的檢測，而且對于3D碰撞檢測問題，還沒有幾乎完美的解決方案。目

3、前只能根據需要來取舍運算速度和精確性。目前成功商業(yè)3D游戲普遍采用的碰撞檢測是BSP樹及AABB（axiallyalignedboundingbox）包裝盒（球）方式。簡單地講，AABB檢測法就是采用一個描述用的立方體或者球形體包裹住3D物體對象的整體（或者是主要部分），之后根據包裝盒的距離、位置等信息來計算是否發(fā)生碰撞，如圖10-24所示。除了球體和正方體以外，其他形狀也可以作包裝盒，但是相比計算量和方便性來講還是立方體和球體更方便些，所以其他形狀的包裝只用在一些特殊場合使用。BSP樹是用來控制檢測順序和方向的數(shù)據描述。在一個游戲場景中可能存在很多物體，它們之間大多屬于較遠位置或者相對無關的

4、狀態(tài)，一個物體的碰撞運算沒必要遍歷這些物體，同時還可以節(jié)省重要的時間。如果使用單步碰撞檢測，需要注意當時間步長較大時會發(fā)生兩個物體完全穿透而算法卻未檢測出來的問題，如圖10-25所示。其解決方案是產生一個4D空間，在物體運動的開始和結束時間之間產生一個4D超多面體，用于穿透測試。圖10-24AABB包裝盒圖10-25碰撞檢測的單步失控和4D測試讀者在程序開發(fā)初期有必要對碰撞檢測有一個初步的估計，以免最后把大量精力消耗在碰撞檢測問題上，從而降低了在基礎的圖形編程之上的注意力。10.3.2球體碰撞檢測真實的物理模擬系統(tǒng)需要非常精確的碰撞檢測算法，但是游戲中常常只需要較為簡單的碰撞檢測，因為只需要知

5、道物體什么時候發(fā)生碰撞，而不用知道模型的哪個多邊形發(fā)生了碰撞，因此可以將不規(guī)則的物體投影成較規(guī)則的物體進行碰撞檢測。球體只有一個自由度，其碰撞檢測是最簡單的數(shù)學模型，我們只需要知道兩個球體的球心和半徑就能進行檢測。那么球體碰撞是如何工作的?主要過程如下。n計算兩個物體中心之間的距離，并且將其與兩個球體的半徑和進行比較。n如果距離大于半徑和，則沒有發(fā)生碰撞。n否則，如果距離小于半徑和，則發(fā)生了物體碰撞?？紤]由球心cl、c2和半徑rl、r2定義的兩個球，如圖10-26所示。設d為球心間的距離。很明顯，當drl+r2時相交，在實踐中通過比較d2<(rl+r2)2,可以避免包括計算d在內的平方根

6、運算。對兩個運動的球進行碰撞檢測要麻煩一些，假設兩個球的運動向量為dl和d2,球與位移向量是一一對應的，它們描述了所討論時間段中的運動方式。事實上，物體的運動是相對的，例如兩列在兩條平行軌道上相向行駛的火車，在其中一列中觀察，對方的速度是兩車速度之和。同樣，也可以從第一個球的角度來簡化問題，假設第一個球是靜止的，另一個是運動的，那么該運動向量等于原向量dl和d2之差，如圖10-27所示。圖10-27動態(tài)球的檢測過程球體碰撞的優(yōu)點是非常適用于需要快速檢測的游戲，因為它不需要精確的碰撞檢測算法。執(zhí)行速度相對較快，不會給CPU帶來過大的計算負擔。球體碰撞的另一個劣勢是只適用于近似球形物體，如果物體非

7、常窄或者非常寬，該碰撞檢測算法將會失效，因為會在物體實際發(fā)生碰撞之前，碰撞檢測系統(tǒng)就發(fā)出碰撞信號，如圖10-28所示是球體碰撞檢測中可能出現(xiàn)的壞情況，其解決方法是縮小檢測半徑，或者使用其他檢測模型，如圖10-29所示。圖10-28球體碰撞的壞情況圖10-29縮小檢測半徑為了解決包容球精確度不高的問題，人們乂提出了球體樹的方法。球體樹實際上是一種表達3D物體的層次結構。對一個形狀復雜的3D物體，先用一個大球體包容整個物體，然后對物體的各個主要部分用小一點的球體來表示，然后對更小的細節(jié)用更小的包容球體，這些球體和它們之間的層次關系就形成了一個球體樹。舉例來說，對一個游戲中的人物角色，可以用一個大球

8、來表示整個人，然后用中等大小的球體來表示四肢和軀干，然后用更小的球體來表示手腳等。這樣在對兩個物體進行碰撞檢測時，先比較兩個最大的球體。如果有重疊，則沿樹結構向下遍歷，對小一點的球體進行比較，直到沒有任何球體重疊，或者到了最小的球體，這個最小的球體所包含的部分就是碰撞的部分，如圖10-30所示。10.3.3AABB立方體邊界框檢測用球體去近似地代表物體運算量很小，但在游戲中的大多數(shù)物體是方的或者長條形的，應該用方盒來代表物體。另一種常見的檢測模型是立方體邊界框，如圖10-31展示了一個AABB檢測盒和它里面的物體。坐標軸平行(Axially-aligned)不僅指盒體與世界坐標軸平行，同時也指

9、盒體的每個面都和一條坐標軸垂直，這樣一個基本信息就能減少轉換盒體時操作的次數(shù)。AABB技術在當今的許多游戲中都得到了應用，開發(fā)者經常用它們作為模型的檢測模型，再次指出，提高精度的同時也會降低速度。因為AABB總是與坐標軸平行，不能在旋轉物體時簡單地旋轉AABB,而是應該在每一幀都重新計算。如果知道每個對象的內容，這個計算就不算困難，也不會降低游戲的速度。然而，還面臨著精度的問題。假如有一個3D的細長剛性直棒，并且要在每一幀動畫中都重建它的AABBo可以看到每一幀中的包裝盒都不一樣而且精度也會隨之改變，如圖10-32所示。圖10-313D模型與AABB檢測盒圖10-32不同方向的AABB可以注意

10、到AABB對物體的方向很敏感，同一物體的不同方向，AABB也可能不同(由于球體只有一個自由度，所以檢測球對物體方向不敏感)。當物體在場景中移動時，它的AABB也需要隨之移動，當物體發(fā)生旋轉時，有兩種選擇：用變換后的物體來重新計算AABB,或者對AABB做和物體同樣的變換。如果物體沒有發(fā)生扭曲，可以通過變換后的AABB重新計算，因為該方法要比通過變換后的物體計算快得多，因為AABB只有8個頂點。變換AABB得出新的AABB要比變換物體的運算量小，但是也會帶來一定的誤差，如圖10-33所示。比較圖中原AABB（灰色部分）和新AABB（右邊比較大的方框），它是通過旋轉后的AABB計算得到的，新AAB

11、B兒乎是原來AABB的兩倍，注意，如果從旋轉后的物體而不是旋轉后的AABB來計算新AABB,它的大小將和原來的AABB相同。先介紹AABB的表達方法，AABB內的點滿足以下條件：xminWxWxmaxyminWyWymaxzniinWzWzniax因此只需要知道兩個特別重要的頂點(xmin,ymin,zmin)、(xmax,ymax»zmax)9記作：floatmin=newfloat0.Of,0.Of,0.Of)；f1oatmax=newf1oat0.Of,0.Of,0.Of)；中心點是兩個頂點的中點，代表了包裝盒的質點。floatcenter=newfloat0.Of,0.Of,

12、0.Of)；中心點的計算方法如下：floatcenter()center0=(min0+max0)*0.5f；center1=(minl+maxl)*0.5f；center2=(min2+max2)*0.5f；returncenter；通過這兩個頂點可以知道以下屬性。floatxSizeOreturn(max0-min0)；floatySizeOreturn(max1-min1)；floatzSize()return(max2-min2)；floatsize()return(maxEO-min0)*(maxEl-min1)*(max21一min2)；當添加一個頂點到包裝盒時，需要先與這兩個頂點

13、進行比較。voidadd(floatp)if(p0min0)min0=p0；if(p0max0)max0=p0；if(plminl)minl=pl；if(plmaxl)maxl=pl；if(p2min2)min2=p2；if(p2max2)max2=p2；檢測包裝盒是否為空，可以將這兩個頂點進行比較。booleanisEmpty()return(min0max0)ii(minlmaxll)ii(min2max2)；檢測某個點是否屬于AABB范圍之內的代碼如下：booleancontains(floatp)return(p0=min0)&&(p0=max0)&&(

14、pl=minl)&&(pl=maxl)&&(p2=min2)&&(p2=max2)；AABB的靜態(tài)檢測比較簡單，檢測兩個靜止包裝盒是否相交，它是一種布爾測試，測試結果只有相交或者不相交。這里我們還提供了獲取相交范圍信息的方法，一般來說，這種測試的目的是為了返回一個布爾值。碰撞的示意如圖10-34所示。圖10-34包裝盒的碰撞檢測靜態(tài)AABB碰撞的方法如下：booleanintersectAABBs(AABBbox2,AABBboxIntersect)floatbox2_min=box2.getMinO；floatbox2_max=box2.get

15、Max()；if(min0box2_max0)returnfalse；if(maxE0box2_min0)returnfalse；if(min1box2_max1)returnfalse；if(max1box2_min1)returnfalse；if(min2box2_max2)returnfalse；if(max2box2_min2)returnfalse；if(boxlntersect!=null)floatbox_intersect_min=newfloat3；floatbox_intersect_max=newfloat3；box_intersect_min0=Math.max(min

16、0,box2_min0)；box_intersect_max0=Math.min(max0,box2_max0)；box_intersect_minl=:Math.max(min1,box2_minl)；box_intersect_maxl:Math.min(max1,box2_maxl)；box_intersect.min2=Math.max(min2,box2_min2)；box_intersect_max2=Math.min(max2,box2_max2)；returntrue；可以利用AABB的結構來加快新的AABB的計算速度，而不用變換8個頂點，再從這8個頂點中計算新AABB。下面簡

17、單地回顧4X4矩陣變換一個3D點的過程。通過原邊界框(xmin,ymin,zmin,xmax,ymax,zmax)計算新邊界框現(xiàn)在的任務是計算的速度。換句話說，希望找到mllx+ml2y+ml3z+ml4的最小值。其中x,y,z是原8個頂點中的任意一個。變換的目的是找出這些點經過變換后哪一個的x坐標最小?？吹谝粋€乘積mllx,為了最小化乘積，必須決定是用xmin還是xmax來替換其中的X。顯然，如果1nli>0,用xmin能得到最小化的乘積;如果mllXO,則用xmax能得到最小化乘積。比較方便的是，不管xmin還是xmax中哪一個被用來計算，都可以用另外一個來計算?？梢詫仃囍械?個元

18、素中的每一個都應用這個計算過程(其他元素不影響大小)。根據變換矩陣和原有的AABB包裝盒計算新的AABB包裝盒的代碼如下：voidsetToTransformedBox(Transformt)if(isEmpty。)判斷包裝盒是否為空return；floatm=newfloat16；t.get(m)；將變換矩陣存入數(shù)組floatminx=O,miny=0,minz=0；floatmaxx=0,maxy=O,maxz=O；minx+=m3；/x方向上平移maxx+=m3；/x方向上平移miny+=m7；/y方向上平移maxy+=m7；y方向上平移minz+=mll；/z方向上平移maxz+=ml

19、l；/z方向上平移if(m00.Of)minx+=m0*niin0；elseminx+=m0*max0；if(ml0.Of)minx+=m1*min1；elseminx+=m1*max1；if(m20.Of)minx+=m2*min2；elseminx+=m2*max2；maxx+=m0*max0；maxx+=m0*min0；maxx+=m2*max2；maxx+=m2*min2；if(m40.Of)miny+=m4*min0；maxy+=m4*max0；elseminy+=m4*max0；maxy+=m4*min0；if(m50.Of)miny+=m5*min1；maxy+=m5*max1；

20、elseminy+=m5*max1；if(m60.Of)miny+=m6*min2；elseminy+=m6*max2；if(m80.Of)minz+=m8*min0；elseminz+=m8*max0；if(m90.Of)minz+=m9*niinl；elseminz+=m9*max1；maxy+=m5*min1；maxy+=m6*max2；maxy+=m6*min2；maxz+=m8*max0；maxz+=m8*min0；maxz+=m9*max1；maxz+=m9*min1；minz+=m10*min2；maxz+=m10*max2；elseminz+=m10*max2；maxz+=m1

21、0*min2；min0=minx；minl=miny；min2=minz；/用新的AABB坐標替換原有坐標maxEOl=maxx；maxl=maxy；max2=maxz；用新的AABB坐標替換原有坐標為了使用AABB包裝盒進行碰撞檢測，將這些方法和屬性封裝為AABB類,代碼如下：importjava.lang.Math；importjavax.microedition.m3g.Transform：c1assAABBpublicAABB()floatgetMinOreturnmin；floatgetMaxOreturnmax；)voidsetMin(floatx,floaty,floatz)mi

22、n0=x；minl=y；min2=z；voidsetMax(floatx,floaty,floatz)max0=x；maxl=y；max2=z；voidreset()for(inti=0；i3；i+)mini=0；maxi=0；其他方法同上為了檢驗碰撞檢測的使用構造了兩個立方體，并各自綁定了一個包裝盒。/*立方體1*/meshl=createCube()；創(chuàng)建立方體Imeshl.setTranslation(l.Of,0.Of,0.Of)；平移meshl.setOrientation(90,0.Of,1.Of,0.Of)；旋轉meshl.setScale(0.5f,0.5f,0.5f)；縮放b

23、oxl=newAABB()；包裝盒boxl.setMin(-1.0f,-l.Of,-1.Of)；設置包裝盒1的最小頂點boxl.setMax(l.Of,1.Of,1.Of)；設置包裝盒1的最大頂點meshl.getCompositeTransform(cubeTransform)：/獲取立方體1的混合矩陣boxl.setToTransformedBox(cubeTransform)；將變換矩陣應用到包裝盒中world.addChild(meshl)；將立方體1添加到場景中/*立方體2*/mesh2=createCube()；創(chuàng)建立方體2mesh2.setTranslation(-0.5f,0.

24、Of,0.Of)；/平移mesh2.setScale(0.5f,0.5f,0.5f)；縮放box2二newAABB()；包裝盒box2.setMin(-1.0f,-l.Of,-1.Of)；/設置包裝盒2的最小頂點box2.setMax(l.Of,1.Of,1.Of)；設置包裝盒2的最大頂點mesh2.getCompositeTransform(cubeTransform)；/獲取立方體2的混合矩陣box2.setToTransformedBox(cubeTransform)；將變換矩陣應用到包裝盒2中world.addChiId(mesh2)；將立方體2添加到場景中檢測包裝盒1和包裝盒2是否碰

25、撞的代碼如下：isCollided=ersectAABBs(box2,null)；檢測兩個AABB包裝盒是否碰撞編譯運行程序，設置兩個立方體不同的位置和角度，可以比較精確地檢測出它們的碰撞情況，如圖10-35所示。檢測兩個靜止AABB的碰撞情況比較簡單，只需要在每一維上單獨檢查它們的重合程度即可。如果在所有維上都沒有重合，那么這兩個AABB就不會相交。AABB間的動態(tài)檢測稍微復雜一些，考慮一個由頂點smin和smax指定的靜態(tài)包裝盒和一個由頂點mmin和mmax指定的動態(tài)包裝盒(如果兩個都是動態(tài)的，可以根據相對運動視作如此)。運動的速度由向量s給出，運動時間t假定為01。圖10

26、-35靜態(tài)物體碰撞檢測示意移動檢測的目標是計算運動AABB碰撞到靜態(tài)AABB的時刻，因此需要計算出兩個AABB在所有維上的第一個點。為了簡化起見，可以把上述問題先歸結到某一維，然后再將三維結合到一起。假設把問題投影到x軸，如圖10-36所示。圖10-36AABB的動態(tài)檢測黑色矩形代表沿坐標軸滑動的AABB,廿0時，運動AABB完全位于靜止AABB的左邊。當時，運動AABB完全位于靜止AABB的右邊。當t=tenter時，兩個AABB剛剛相交，當廿tleave時，兩個AABB脫離碰撞。對照上圖，可以推導出兩個AABB接觸和離開的時間：AABB的動態(tài)檢測有3個要點。n如果速度為0,兩個包裝盒要么一

27、直相交，要么一直分離。n不管物體從哪個方向運動，碰撞過程中，肯定是先入后出，所以有tenter<tleaveon如果tenter和11eave超出運動時間范圍，那么在此范圍內它們是不相交的。檢測出某一維的碰撞還不夠，還需要進行其他兩維的檢測，然后取結果的交集。如果交集為空，那么兩AABB包裝盒沒有相交，如果區(qū)間范圍在時間段0,1之外，那么在此區(qū)間也不相交。對AABB進行動態(tài)檢測的方法定義如下：floatintersectMovingAABB(AABBstationaryBox,AABBmovingBox,floats)floatNoIntersection=le30f；沒有碰撞則返回大數(shù)

28、floattEnter=0.Of；初始化碰撞時間floattLeave=l.Of；初始化離開時間floatSwap=0.Of；交換操作中間變量floatsBoxmin=stationaryBox.getMinO；靜止包裝盒的最小值頂點floatsBoxmax=stationaryBox.getMax()；靜止包裝盒的最大值頂點floatmBoxmin=movingBox.getMinO;運動包裝盒的最小值頂點floatmBoxmax=movingBox.getMax()；運動包裝盒的最大值頂點if(sO=O.Of)如果x方向速度為Oif(sBoxmin0=mBoxmax0)I.(sBoxmax

29、0=mBoxmin0)returnNoIntersection；進行靜態(tài)檢測elsefloatxEnter=(sBoxmin0-mBoxmax0)/s0；計算碰撞時間floatxLeave=(sBoxmax0-mBoxmin0)/s0；計算離開時間if(xEnterxLeave)檢查順序Swap=xEnter；xEnter=xLeave；xLeave=Swap；if(xEntertEnter)tEnter=xEnter；更新區(qū)間if(xLeavetLeave)tLeave=xLeave；if(tEntertLeave)是否導致空重疊區(qū)returnNoIntersection；沒有碰撞if(sl

30、=0.Of)/y軸速度為0if(sBoxmin1=mBoxmax1)I.(sBoxmax1=mBoxmin1)returnNoIntersection；沒有相交elsefloatyEnter=(sBoxmin1-mBoxmaxl)/sl；floatyLeave=(sBoxmax1-mBoxminl)/sl；if(yEnteryLeave)Swap=yEnter；yEnter=yLeave；yLeave=Swap；if(yEntertEnter)tEnter=yEnter；更新區(qū)間if(yLeavetLeave)tLeave=yLeave；if(tEntertLeave)returnNoInte

31、rsection；if(s2=0.Of)/z方向速度為Oif(sBoxmin2=mBoxmax2)I.(sBoxmax2=mBoxmin2)returnNoIntersection；elsef1oatoneOverD=1.Of/s2；floatzEnter=(sBoxmin2-mBoxmax2)/s2；floatzLeave=(sBoxmax2-mBoxmin2)/s2；if(zEnterzLeave)Swap=zEnter；zEnter=zLeave；zLeave=Swap；if(zEntertEnter)tEnter=zEnter；更新區(qū)間if(zLeavetLeave)tLeave=zL

32、eave；if(tEntertLeave)returnNoIntersection；returntEnter；返回碰撞時間為了對移動AABB進行檢測，創(chuàng)建兩個AABB如圖10-37所示。兩個包裝盒距離Q5,速度為3。圖10-37移動AABB檢測檢測代碼如下：floatspeed=newfloat3,Of,0.Of,0.Of；floattEnter=intersectMovingAABB（boxl,box2,speed）；輸出結果為0.16667,完全符合預期的猜測。10.3.40BB樹碰撞檢測前面提到了長條物體在旋轉時AABB盒的變化，那么是否有能夠在任意方向都更為精確的檢測方式，答案是肯定的

33、，這是一種基于0BB即定向包容盒子（OrientedBoundingBox,OBB）的技術，它已經廣泛用于光線追蹤和碰撞檢測中。OBB這種方法是根據物體本身的幾何形狀來決定盒子的大小和方向，盒子無須和坐標軸垂直。這樣就可以選擇最合適的最緊湊的包容盒子。0BB盒子的生成比較復雜。一般是考慮物體所有的頂點在空間的分布，通過一定的算法找到最好的方向（OBB盒子的幾個軸）o一個2D示意圖如圖10-38所示。這種技術比AABB技術更精確而且更健壯，但OBB實現(xiàn)起來比較困難，執(zhí)行速度慢，并且不太適合動態(tài)的或柔性的物體。特別注意的是，當把一個物體分得越來越小的時候，事實上是在創(chuàng)建一棵有層次的樹，如圖10-3

34、9所示。圖10-390BB樹的生成（曲折線為物體）為任意的網格模型創(chuàng)建0BB樹可能是算法里最難的一個部分，而且它還要調整以適合特定的引擎或游戲類型。從圖中可以看出，不得不找出包圍給定模型的最近似的包裝盒（或者其他3D體）?，F(xiàn)在得到了所有的包裝盒，下一步將構造一棵樹。從最初的AABB包裝盒開始從上至下地反復分割它。另外，還可以用從下至上的方式，逐步地合并小包裝盒從而得到最大的包裝盒。把大的包裝盒分割成小的包裝盒，應該遵守以下兒條原則。（1）用一個面（這個面垂直于包裝盒中的一條坐標軸）來分割包裝盒上最長的軸，然后根據多邊形處在分割軸的哪一邊把多邊形分離開來（如圖10-38所示）。（2）如果不能沿著

35、最長的軸進行分割，那就沿第二長的邊分割。持續(xù)地分割直到包裝盒不能再分割為止。（3）依據需要的精度（比如，是否真的要判斷單個三角形的碰撞），可以按選擇的方式（是按樹的深度或是按包裝盒中多邊形的數(shù)目）以任意的條件停止分割。正如讀者所看到的，創(chuàng)建階段相當復雜，其中包括了大量的運算，很明顯不能實時地創(chuàng)建樹，只能是事先創(chuàng)建。事先創(chuàng)建可以免去實時改變多邊形的可能。另一個缺點是OBB要求進行大量的矩陣運算，不得不把它們定位在適當?shù)牡胤?，并且每棵子樹必須與矩陣相乘?，F(xiàn)在假設已經有了OBB或者AABB樹。那么該怎么進行碰撞檢測呢？首先檢測最大的包裝盒是否相交（AABB級別），如果相交了，它們可能（注意，只是可能

36、）發(fā)生了碰撞，接下來將進一步地遞歸處理它們（OBB級別，不斷地遞歸用下一級進行處理）。如果沿著下一級，發(fā)現(xiàn)子樹并沒有發(fā)生相交，這時就可以停止，并得出結論沒有發(fā)生碰撞。如果發(fā)現(xiàn)子樹相交，那么要進一步處理它的子樹直到到達葉子節(jié)點，并最終得出結論。碰撞檢測最直觀的想法是把一個OBB盒子的每個邊都和另一個盒子的所有面來比較，如果這個邊穿過了另一個OBB盒子的一個面，則兩個OBB盒子發(fā)生了碰撞。顯然這種方法的計算量是比較大的，因為要進行12X6X2=144次邊和面的比較。但是，在考察兩個沒有碰撞的OBB盒子時，人們發(fā)現(xiàn)一些規(guī)律來簡化比較。(1)如果兩個OBB盒子不互相接觸，則應該可以找到一個盒子上的一個面，這個面所在的平面可以把3D空間分為兩部分，兩個OBB盒子各在兩邊。(2)如果沒有這樣的表面存在，則一定可以在兩個OBB盒子上各找出一條邊，這兩條邊所在的平面可以把兩個OBB盒子分在兩邊。有了這個平面，就可以找到垂直于它的分割軸(separatingaxis)，如圖10-40所示。(3)進行相交測試時，可以把包裝盒投影到分割軸上，并檢查它們是否線性相交。兩個0BB盒子在這個分割軸上的投影將是分離的。如上所述，要判斷兩個0BB盒子是否碰撞，只需要看兩個0BB盒子之間是否有這樣的平面和分割軸存在。如果存在，則沒有碰撞。如果不存在