王振文,徐 華

1(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100029)

2(北京石油化工學(xué)院 信息工程學(xué)院,北京 102617)

復(fù)雜場景中基于拓撲空間網(wǎng)格的碰撞檢測算法①

王振文1,徐 華2

1(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100029)

2(北京石油化工學(xué)院 信息工程學(xué)院,北京 102617)

為了提高復(fù)雜場景的碰撞檢測效率,提出一種基于拓撲空間網(wǎng)格的碰撞檢測算法. 由于場景中存在眾多形狀復(fù)雜、尺寸不一且運動狀態(tài)不同的物體,首先采取場景預(yù)處理對空間進行均勻八叉樹網(wǎng)格劃分,建立物體方向包圍盒層次樹與空間網(wǎng)格拓撲結(jié)構(gòu),利用靜態(tài)大尺寸物體分割策略提升定位精確性,然后在實時檢測中利用拓撲空間網(wǎng)格及投影相交測試排除大量不相交物體對,利用層次包圍盒算法對潛在碰撞對進行精確檢測并計算出碰撞點. 實驗結(jié)果表明,本算法有效地提高了實時檢測的效率,適用于復(fù)雜虛擬場景中的碰撞檢測.

碰撞檢測; 拓撲空間網(wǎng)格; 方向包圍盒; 大尺寸物體分割; 層次包圍盒

碰撞檢測在計算機動畫模擬、虛擬仿真、游戲開發(fā)等領(lǐng)域都是關(guān)鍵技術(shù). 隨著虛擬現(xiàn)實的發(fā)展,虛擬場景越為復(fù)雜,物體對象逐步增多,對碰撞檢測算法的實時性提出了更高的要求[1].

基于物體空間的碰撞檢測算法中比較經(jīng)典的兩類碰撞檢測算法是空間剖分法和層次包圍盒[2]. 空間剖分法適用于物體在空間均勻分布的稀疏環(huán)境,簡單地從大量物體中排除不相交的物體[3]. 但對于物體分布密集的場景,則需要進行更深的遞歸分割,空間存儲量大且靈活性差. 經(jīng)典的算法主要有: BSP 樹,八叉樹以及均勻網(wǎng)格剖分法[4]. 層次包圍盒算法是用簡單的包圍盒來包裹整個物體及物體所有的基本單元子集,構(gòu)造起層次樹,通過遍歷兩物體的層次包圍盒來進行逐步求精相交檢測[5]. 比較常用的有包圍球(Bounding sphere),方向包圍盒 (Axis-aligned bounding box,AABB),OBB 包圍盒 (Oriented bounding box,OBB)等[6]. 而對于場景物體數(shù)目較多的情形,若僅使用層次包圍盒算法往往會產(chǎn)生不必要的檢測,影響整體檢測效率. 針對簡單的多物體場景,孫勁光[7]、王巍[8]、Zhao W[9]等人提出了結(jié)合空間剖分及層次包圍盒的混合算法,快速排除不相交物體對,有效地提高檢測效率,但對存在靜態(tài)大尺寸物體的復(fù)雜場景及物體的定位精確性上具有一定局限性,從而影響了排除效率.

因此,本文針對復(fù)雜場景中物體數(shù)目眾多、尺寸不一、形狀不規(guī)則的特性,在方向包圍盒(Oriented bounding box,OBB)層次樹[10]的基礎(chǔ)上提出了一種基于拓撲空間網(wǎng)格的碰撞檢測算法(Topological spatial grid-OBB,TSGO). 通過分割大型物體實現(xiàn)更精確的定位,利用空間網(wǎng)格單元與物體之間的拓撲結(jié)構(gòu)以及投影相交測試排除明顯不相交物體,提升檢測效率,最終計算得到碰撞物體對的精確碰撞點,可為碰撞響應(yīng)服務(wù).

1 算法流程

相較于包圍球及軸向包圍盒,OBB包圍盒能夠?qū)π螒B(tài)復(fù)雜的物體模型達到較好的貼合度,一方面能夠更加精確的表征物體模型,增強不相交物體對的排除效果,另一方面在層次樹的構(gòu)造上減少樹的深度,簡化模型二叉樹結(jié)構(gòu). 因此,對于本文研究場景下形態(tài)復(fù)雜、規(guī)模龐大的物體模型,選用OBB層次包圍盒具有更好的適用性. 算法整體流程如圖1所示.

算法共分為場景預(yù)處理以及實時檢測兩大部分,圖2(a)為整體場景示意圖,圖2(b)為局部場景示意圖,以二維場景均勻四叉樹劃分進行說明,三維場景均勻八叉樹劃分同理.

(1) 場景預(yù)處理階段. 首先建立所有物體OBB層次包圍盒,進行均勻八叉樹場景空間劃分,隨后對場景中靜態(tài)大尺寸物體進行分割,將大尺寸物體分解為多個尺寸較小的子物體進行替代,最終建立網(wǎng)格與物體之間的拓撲結(jié)構(gòu). 拓撲建立過程中對物體進行初次定位,利用物體根節(jié)點包圍盒4個體對角線進行定位,提升了定位準確性,大尺寸物體分解為多個尺寸較小的子物體再定位,解決大尺寸物體定位準確性問題. 精確的定位有助于在實時檢測階段有效地排除不相交物體對,減少實時檢測耗時.

圖1 算法流程圖

圖2 場景及網(wǎng)格劃分示意圖

算法對物體建立OBB層次包圍盒,將圖2(b)場景劃分成16個均勻的小正方體空間網(wǎng)格. 由于大尺寸物體B的根節(jié)點包圍盒占據(jù)網(wǎng)格1～16,而實際物體并不占據(jù)網(wǎng)格5、6、9、10、16,為提升網(wǎng)格定位準確度,將B分割為多個子物體,圖中B1為B分割后的小尺寸物體集之一. 最后,對所有物體建立網(wǎng)格的拓撲結(jié)構(gòu),完成物體初次定位.

(2) 實時檢測階段. 利用物體與網(wǎng)格的拓撲關(guān)系排除不在同一網(wǎng)格內(nèi)的物體對,隨后以投影相交測試排除同一網(wǎng)格內(nèi)投影不相交物體對,最終對剩余的潛在碰撞對利用層次包圍盒進行精確測試獲取碰撞物體對并計算碰撞點.

取圖2(b)中物體 S1為例,物體 S1、S2、S3、S4的包圍盒都占據(jù)網(wǎng)格1,因此S1僅與S2、S3、S4進行投影相交測試. 經(jīng)投影相交測試之后排除物體S4,得到潛在碰撞對 (S1,S2)、(S1,S3). 對潛在碰撞對中物體對利用OBB層次包圍盒相交測試算法進行精確檢測,排除物體 S3,確定最終發(fā)生碰撞的物體對為 (S1,S2),得到(S1,S2)相交的三角形對. 最終利用三角形相交算法計算交點作為碰撞點.

2 場景預(yù)處理

2.1 OBB層次包圍盒建立

OBB包圍盒因其方向的任意性,對形態(tài)復(fù)雜,不規(guī)則的物體具有良好的包圍效果. 為改善物體模型三角形面片以及各頂點的非均勻分布導(dǎo)致計算所得包圍盒中心點以及方向矩陣的偏差,采用三角形面積加權(quán)方式減少偏差[11],OBB層次包圍盒建立方法如下:

設(shè)模型共有n個三角形. 第i個三角形的中心點Oi,頂點為pi、qi、ri,面積Si. 構(gòu)成模型的所有三角面片的總面積SumS.

加權(quán)后物體包圍盒中心點u,協(xié)方差矩陣C如下所示[10-12]:

j、k代表點的x、y、z分量并確定矩陣C元素.矩陣C為實對稱矩陣,三個特征向量相互正交,作為包圍盒的方向基底. 物體所有頂點投影到三個方向軸上,得到三個方向上的最大最小值,從而確定包圍盒的尺寸.

層次樹的構(gòu)造采取自頂向下的二叉樹構(gòu)造方式.以整個物體模型對象為根節(jié)點,遞歸劃分模型對象并建立對應(yīng)的OBB包圍盒,直到盒子中的元素僅有一個模型幾何單元(三角形)時終止分裂.

2.2 空間網(wǎng)格劃分

進行虛擬三維場景均勻八叉樹網(wǎng)格劃分時,需要確定網(wǎng)格單元的尺寸大小. 本文研究場景如圖2(a)所示,其中A、B、C、D為靜態(tài)大尺寸物體,存在多個動態(tài)小尺寸物體呈區(qū)域性非均勻分布,因此網(wǎng)格劃分過大或過小都會對碰撞檢測的效率產(chǎn)生不好的影響[13].此類場景可適用于礦井災(zāi)害模擬仿真、山體隧道坍塌模擬等. 針對此類場景,空間網(wǎng)格劃分算法如下:

(1) 設(shè)總場景空間為立方體,利用場景內(nèi)所有模型頂點集獲取x、y、z三個軸向上的極值點,計算三個軸向極值點差值,取差值結(jié)果中最大值作為總場景空間邊長L,建立起立方體為總場景空間網(wǎng)格;

(2) 對空間網(wǎng)格進行八叉樹網(wǎng)格劃分,將當(dāng)前空間網(wǎng)格劃分成八個尺寸相同的子空間網(wǎng)格;

(3) 若當(dāng)前劃分深度小于k,對當(dāng)前場景內(nèi)所有空間網(wǎng)格執(zhí)行步驟(2),直至劃分深度為k時劃分結(jié)束.

劃分深度k值確定如下:

設(shè)最大動態(tài)小物體尺寸MaxSmallL,網(wǎng)格單元的邊長GridL. 則網(wǎng)格單元總數(shù)為 8k,GridL=L/2k,k的取值 最 大 滿 足L/2kmax+1

圖3 劃分深度與檢測耗時關(guān)系

2.3 大尺寸物體分割

復(fù)雜虛擬場景中存在靜態(tài)大尺寸物體,所包含的三角形單元數(shù)目龐大,導(dǎo)致其層次包圍盒根節(jié)點包圍盒占據(jù)多余空間網(wǎng)格. 為消除冗余網(wǎng)格,提升定位準確性,對其按一定條件進行分割. 以圖2(b)中大尺寸物體B為例,分割過程如下:

(1) 以物體B的層次包圍盒根節(jié)點為當(dāng)前節(jié)點;

(2) 判斷當(dāng)前節(jié)點包圍盒邊長是否滿足:當(dāng)前節(jié)點的包圍盒邊長<網(wǎng)格單元邊長. 若不滿足則將其孩子節(jié)點作為新的當(dāng)前節(jié)點,重復(fù)此步驟; 若滿足或當(dāng)前節(jié)點為葉子節(jié)點,則轉(zhuǎn)到(3);

(3) 抽離當(dāng)前節(jié)點作為分割后的小物體,該小物體包含當(dāng)前節(jié)點的所有三角形集合.

分割形成的子物體如果尺寸過小會導(dǎo)致單一網(wǎng)格內(nèi)子物體數(shù)目眾多,增加后續(xù)潛在碰撞對選取的耗時.因此步驟(2)的終止條件保證了分割后包圍盒尺寸與網(wǎng)格單元大致相同,既能實現(xiàn)較精準的定位又控制了子物體數(shù)目. 分割的實質(zhì)是將大尺寸物體的層次樹分解為若干個符合要求的子樹,每個子樹形成的子物體為大物體的一部分.

2.4 拓撲結(jié)構(gòu)建立

網(wǎng)格單元結(jié)構(gòu)體中包含網(wǎng)格單元ID號Grid_ID;網(wǎng)格頂點的最小點與最大點min,max; 鄰域網(wǎng)格單元ID集合neighbor_ID; 網(wǎng)格內(nèi)包含物體的身份索引Including_Object. 其描述及具體建立過程如下:

2.4.1 網(wǎng)格單元 ID

場景劃分后網(wǎng)格單元總數(shù)為8k個,k為八叉樹劃分迭代次數(shù),因此劃分好的空間網(wǎng)格在x、y、z單一軸向上的網(wǎng)格數(shù)為m=2k,用a、b、c分別表示x、y、z方向的序號,則 (a,b,c)可以唯一地表示網(wǎng)格單元的序號:

2.4.2 最值點

網(wǎng)格單元6個頂點中在x、y、z三個方向皆為最小值的點為min,皆為最大值的點為max.

2.4.3 鄰域網(wǎng)格單元

記錄當(dāng)前網(wǎng)格單元相鄰網(wǎng)格單元ID號及自身ID.一個網(wǎng)格單元的neighbor_ID至多27個,計算方式如下:

如圖4中網(wǎng)格單元6上x、y、z坐標軸所示,其相鄰網(wǎng)格可利用三個軸向以及任意兩個軸向或三個軸向的組合進行計算:

(1) 第i個網(wǎng)格單元的neighbor_ID分別為i,i±1,i±m(xù),i±m(xù)2,i±1±m(xù),i±1±m(xù)2,i±m(xù)±m(xù)2,i±1±m(xù)±m(xù)2;

(2) 上述27個結(jié)果值若小于0或大于網(wǎng)格總數(shù)8k,則此相鄰單元序號無效,舍去該序號;

(3) 計算剩余鄰域網(wǎng)格單元與當(dāng)前網(wǎng)格單元的距離. 若距離大于網(wǎng)格單元體對角線長度|max-min|則舍去此相鄰單元序號.

2.4.4 網(wǎng)格所含物體集身份索引

網(wǎng)格單元包含的物體集身份索引為該網(wǎng)格內(nèi)所有物體的身份信息集合,利用該索引可確定網(wǎng)格內(nèi)包含的所有物體. 要確定某一網(wǎng)格是否包含該物體,需要先確定物體所占據(jù)的網(wǎng)格. 文獻[7]中所采用的方法是: 已知物體包圍盒主對角線上兩頂點,計算兩頂點所在的網(wǎng)格Grid_ID1和Grid_ID2,則物體所占據(jù)的空間網(wǎng)格為Grid_ID1到Grid_ID2之間所有的連續(xù)網(wǎng)格. 如圖4所示,P1P8為某物體包圍盒的主對角線.P1在網(wǎng)格1中,P8在網(wǎng)格5中,則利用上述算法得到物體所占空間網(wǎng)格為1、2、3、4、5,而實際只占據(jù)網(wǎng)格1和網(wǎng)格5,精確性較差.

圖4 鄰域網(wǎng)格及物體網(wǎng)格定位示意圖

為解決上述方法缺陷,本文提出一種基于包圍盒體對角線來定位物體所占空間網(wǎng)格的方法,具體如下:

(1) 以 4 個體對角線 (P1P8,P2P7,P3P6,P4P5)代替整體包圍盒; 選擇一個對角線,如P1P8,轉(zhuǎn)到 (2).

(2) 尋找該對角線所占網(wǎng)格. 以向量形式P=E+tD表示對角線,E為線段的端點(如P1P8的端點為P1),t為參數(shù),D為從E出發(fā)的對角線方向向量,模值為對角線長度. 對某網(wǎng)格最值點min,max解不等式:

若t有解且 0≤tmin≤tmax≤1,則此條對角線占據(jù)該網(wǎng)格,轉(zhuǎn)到步驟 (3).

(3) 判斷剩余3個體對角線是否占據(jù)(2)中所占網(wǎng)格的鄰域網(wǎng)格,最終記錄4個體對角線占據(jù)的所有非重復(fù)網(wǎng)格單元為物體所占據(jù)的網(wǎng)格.

得到物體占據(jù)的網(wǎng)格單元后將其對應(yīng)的物體身份索引信息記錄在Including_Object中,構(gòu)造出物體與網(wǎng)格之間的對應(yīng)關(guān)系,形成最終拓撲結(jié)構(gòu). 拓撲結(jié)構(gòu)如圖5所示.

圖5 網(wǎng)格單元拓撲結(jié)構(gòu)

3 實時檢測

當(dāng)場景中存在大量物體時,若僅用兩兩物體配對檢測,無法達到高效的檢測效率[14]. 因此,本文算法利用拓撲空間網(wǎng)格以及投影相交測試剔除場景中明顯不相交物體,再對剩余潛在碰撞對物體進行OBB層次包圍盒相交測試,以提升檢測過程實時效率.

3.1 潛在碰撞對選取

算法利用網(wǎng)格拓撲結(jié)構(gòu)中的所含物體集身份索引Including_Object進行排除. 確立某物體占據(jù)的網(wǎng)格,僅對該物體和該物體占據(jù)網(wǎng)格內(nèi)包含的所有物體配對進行投影相交測試.

投影相交測試利用包圍盒的各坐標軸投影來排除明顯不相交的物體. 具體內(nèi)容為: 兩物體層次包圍盒的根節(jié)點包圍盒向x、y、z三個坐標軸中的每一條坐標軸做投影,計算在該坐標軸下其包圍盒的投影區(qū)間是否有重疊. 若x、y、z三條軸上存在任意一條軸上的投影區(qū)間不相交,則證明該物體對一定不相交,可排除該物體對. 將剩余物體對作為潛在碰撞對存入潛在碰撞對集合.

潛在碰撞對選取算法偽代碼如下:

輸入: 運動物體集MO; 大物體分裂所得物體集BO;

輸出: 潛在碰撞對集合PCP;

3.2 層次包圍盒相交測試

如圖6所示,潛在碰撞對共三種類型,而真實發(fā)生相交的僅為圖(c)所示類型,因此需要通過遍歷兩物體OBB層次包圍盒樹進行逐步求精的相交檢測,過程如下[15].

利用某潛在碰撞對中Object1的OBB層次包圍盒根節(jié)點去遍歷Object2的OBB層次包圍盒,若能達到Object2的葉子節(jié)點,再利用該葉子節(jié)點去遍歷Object1的層次包圍盒,若也能達到Object1的葉子節(jié)點,則Object1與Object2發(fā)生碰撞,兩葉子節(jié)點中包含的三角形相交. 如果在遍歷過程中,當(dāng)前兩節(jié)點的包圍盒不相交,則它們包含的對象的三角形子集必定不相交,也就不需要對子集中的元素進行進一步的遍歷檢測. 其中,兩節(jié)點包圍盒之間的相交測試利用的是分離軸理論[16]. 一對 OBB 包圍盒,其分離軸有 15 個: 兩盒子共6個面的法向量,盒子三條邊向量與另一盒子三條邊向量的兩兩叉積,共9個. 當(dāng)15條分離軸都無法分離時,兩包圍盒之間相交.

圖6 潛在碰撞對類型圖

層次包圍盒相交測試利用二叉樹遍歷避免了對執(zhí)行該階段的兩物體的所有幾何基元(三角形)進行窮舉碰撞測試. 設(shè)單個物體三角形個數(shù)m,則層次包圍盒遍歷檢測的時間復(fù)雜度為O(mlbm),達到高效的精確檢測效率.

3.3 相交點計算

通過層次包圍盒相交測試得到最終發(fā)生相交的物體及三角形后進行交點計算并作為碰撞點. 三維空間內(nèi)兩三角形的空間分布分為異面與共面兩種,針對兩種情況的相交類型如下.

(1) 異面相交

圖7中(a)、(b)、(c)顯示了異面三角形的三種相交類型及交點. 交點利用射線-三角形相交法[17]計算:

在三角形(V0,V1,V2)上的點T可以用如下方式表示:

射線使用R(t)=O+tD來表示,O為原點,D為射線方向,為三角形線段起始點指向線段終點,模值為線段長度. 可利用下式求交點:

解得:

其中E1=V1-V0,E2=V2-V0,E3=O-V0. 交點為O+tD.若t不在[0,1]區(qū)間內(nèi),則交點超出線段長度,認為無交點; 若 (D×E2)·E1為 0,如圖7 中 (c)所示,三角形一邊與另一三角形重合,也認為線段與平面無交點.

(2) 共面相交

圖7中(d)、(e)、(f)、(g)顯示了共面三角形相交的四種類型以及交點. 首先判斷一個三角形的頂點是否在另一三角形內(nèi),若在內(nèi)部則記錄該點. 然后利用線段相交求交點,該類型交點計算分解為線段的相交判斷.

圖7 異面/共面三角形相交類型

線段上的點用P=E+tD表示,E為線段的端點,D為E點出發(fā)的方向向量,其值為線段長度,t為參數(shù),則線段相交有:E1+t1D1=E2+t2D2. 解得若t1,t2∈[0,1]則線段相交且交點為E1+t1D1. 若發(fā)生線段重合,該式無解,也判定線段不相交.

4 實驗分析

為測試本文算法在復(fù)雜虛擬場景中的碰撞檢測效率,以河北省張家口某礦區(qū)模型為虛擬地礦實驗場景.場景中有6個復(fù)雜的靜態(tài)大尺寸模型: 包含5個地層模型及1個巷道模型,三角面片數(shù)目共93079個; 采掘區(qū)域內(nèi)存在大量不規(guī)則運動巖體碎塊,進行碎塊與碎塊,碎塊與巷道及碎塊與地層之間的碰撞檢測. 本文算法在CPU主頻為3.2GHz,內(nèi)存4G的PC機上進行實驗并用OpenGL進行顯示. 圖8(a)為整體虛擬場景,圖8(b)為場景中巷道及碎塊模型.

圖8 實驗場景與碰撞點結(jié)果

實驗分別設(shè)定50、100、200、300、400、500、600個運動巖體碎塊進行檢測,空間劃分深度取2. 針對上述場景,分別選用基于OBB層次包圍盒算法的經(jīng)典碰撞檢測算法RAPID[10]、基于空間剖分與層次包圍盒的混合算法[7-9]以及本文提出的TSGO算法執(zhí)行100次測試實驗. 三種算法執(zhí)行碰撞檢測并得出碰撞點的平均耗時如表1所示,圖8(c)、8(d)為最終的碰撞點.

通過圖9及表1中的實驗結(jié)果可以看出,隨著運動物體數(shù)目增多,相較于RAPID算法,混合算法與TSGO算法利用空間網(wǎng)格排除明顯不相交物體使總體檢測耗時減小; 相較于混合算法,TSGO算法利用空間網(wǎng)格拓撲、大物體分割及投影相交測試使得算法耗時進一步減小,且隨著碎塊數(shù)目的增長,TSGO算法的檢測效率優(yōu)勢越為明顯.

表1 實驗結(jié)果對比

圖9 算法耗時對比圖

5 結(jié)束語

針對復(fù)雜虛擬場景物體數(shù)目多、形狀復(fù)雜、尺寸不一的特性,本文提出一種基于拓撲空間網(wǎng)格的碰撞檢測算法. 算法以大尺寸物體分割及包圍盒體對角線替代有效改善了物體定位準確性,利用均勻八叉樹拓撲網(wǎng)格及投影相交測試排除不相交物體對,提升了檢測效率,最終分析了空間三角形的相交類型并通過計算得到精確的碰撞點. 實驗結(jié)果表明: 相比較RAPID算法及單純的空間剖分與層次包圍盒的混合算法,本文算法可有效地減少檢測耗時,對存在大尺寸物體的復(fù)雜場景中多物體的碰撞檢測有良好的適用性和檢測效率. 所得碰撞點可為碰撞響應(yīng)提供可靠支持.

1劉秀玲,王冬雨,陳棟,等. 復(fù)雜場景中快速碰撞檢測算法及 GPU 加速. 計算機工程與設(shè)計,2012,33(5): 1847–1851.

2沈?qū)W利,吳瓊. 基于包圍盒和空間分割的混合碰撞檢測算法. 計算機工程,2012,38(6): 256–258.

3馮立穎. 碰撞檢測技術(shù)研究綜述. 計算機時代,2014,(8):7–10.

4Ericson C. 實時碰撞檢測算法技術(shù). 劉天慧,譯. 北京: 清華大學(xué)出版社,2010.

5Chang JW,Wang WP,Kim MS. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy. Computer-Aided Design,2010,42(1): 50–57. [doi: 10.1016/j.cad.2009.04.010]

6潘仁宇,孫長樂,熊偉,等. 虛擬裝配環(huán)境中碰撞檢測算法的研究綜述與展望. 計算機科學(xué),2016,43(11A): 136–139.

7孫勁光,吳素紅. 基于空間分割與橢球包圍盒的碰撞檢測算法. 計算機工程與應(yīng)用,2016,52(4): 217–222.

8王崴,周誠,楊云,等. 面向虛擬維修的碰撞檢測算法. 計算機應(yīng)用與軟件,2016,33(4): 235–238.

9Zhao W,Ye LM. A collision detection algorithm based on spatial partitioning and bounding volume. Applied Mechanics and Materials,2013,433-435: 932–935. [doi: 10.4028/www.scientific.net/AMM.433-435]

10Gottschalk S,Lin MC,Manocha D. OBBTree: A hierarchical structure for rapid interference detection. Proc. of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York,NY,USA. 1996. 171–180.

11李苗. 實時碰撞檢測算法分析與比較. 計算機與現(xiàn)代化,2011,(6): 88–90.

12田瑜,關(guān)正西,許平,等. 3D 關(guān)節(jié)角色基于 OBB 的實時動態(tài)碰撞檢測. 計算機工程與應(yīng)用,2006,42(33): 91–93. [doi:10.3321/j.issn:1002-8331.2006.33.029]

13鮑義東,吳冬梅. 自適應(yīng)細分及優(yōu)化編碼八叉樹碰撞檢測算法. 上海交通大學(xué)學(xué)報,2015,49(8): 1114–1122.

14王磊,王毅剛. 基于GPU加速的多物體碰撞檢測方法. 計算機工程與科學(xué),2009,31(12): 52–55. [doi: 10.3969/j.issn.1007-130X.2009.12.015]

15彭晏飛,盧真真. 基于空間剖分和包圍盒的快速碰撞檢測算法. 計算機應(yīng)用與軟件,2015,32(8): 150–153,165.

16孔中武,石林鎖,王濤. 導(dǎo)彈飛行視景仿真中的碰撞檢測算法. 計算機系統(tǒng)應(yīng)用,2015,24(1): 176–179.

17Havel J,Herout A. Yet faster ray-triangle intersection (using SSE4). IEEE Trans. on Visualization and Computer Graphics,2010,16(3): 434–438. [doi: 10.1109/TVCG.2009.73]

Collision Detection Algorithm in Complex Scenes Based on the Topological Spatial Grid

WANG Zhen-Wen1,XU Hua2

1(College of Information Science & Technology,Beijing University of Chemical Technology,Beijing 100029,China)
2(College of Information Engineering,Beijing Institute of Petrochemical Technology,Beijing 102617,China)

To improve the efficiency of collision detection in complex scenes,a collision detection algorithm based on topological spatial grid is proposed in this paper. Because there are numerous objects with complex shapes,different scales and motion states in the scene,the algorithm firstly partitions the scene with uniform octree,builds oriented bounding box hierarchal tree,sets up the topology of spatial grids and conducts static large-scale object decomposition for accurate positioning in preprocess stage. Then,the algorithm excludes plenty of non-intersect objects with topological spatial grid and projection intersection test,by using bounding volume hierarchy to conduct accurate detection of potential collision pairs and calculates collision points in real-time detection process. Experimental results show that this algorithm improves the real-time detection efficiency,which is suitable for collision detection in complex virtual scenes.

collision detection; topological spatial grid; oriented bounding box; large-scale object decomposition; bounding volume hierarchy

王振文,徐華.復(fù)雜場景中基于拓撲空間網(wǎng)格的碰撞檢測算法.計算機系統(tǒng)應(yīng)用,2017,26(12):116–123. http://www.c-s-a.org.cn/1003-3254/6031.html

國家重點研發(fā)計劃項目(2016YFC0801801); 國家自然科學(xué)基金(41430318); 北京市自然科學(xué)基金(4142015)

2017-02-11; 修改時間: 2017-02-23; 采用時間: 2017-03-02