一種基于體素八叉樹的碰撞算法研究

朱卓 劉云飛 汪坤 劉森

摘 要：碰撞檢測(cè)算法是虛擬仿真系統(tǒng)中的關(guān)鍵技術(shù)。本文利用OPENGL和CHAI3D庫(kù)實(shí)現(xiàn)對(duì)模型的視覺和觸覺渲染。同時(shí)，針對(duì)復(fù)雜的軟體模型，采用一種多方向體素算法和哈希算法來存儲(chǔ)模型的離散化數(shù)據(jù)。碰撞算法采用包圍盒和空間分解的混合算法，粗略碰撞利用八叉樹判斷兩個(gè)模型是否在同一節(jié)點(diǎn)內(nèi)，精確碰撞是通過基本片元的距離計(jì)算來確定是否發(fā)生碰撞。仿真結(jié)果表明，該算法可以有效實(shí)時(shí)反饋碰撞點(diǎn)的位姿和反饋力。

關(guān)鍵詞：虛擬仿真;體素化;碰撞檢測(cè);八叉樹

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-5168（2019）34-0039-05

A Research about Collision Algorithm Based on Voxel Octree

ZHU Zhuo LIU Yunfei WANG Kun LIU Sen

（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing Jiangsu 210007）

Abstract： Collision detection algorithm is a key technology in virtual simulation system. In this paper， OPENGL and CHAI3D libraries were used to realize visual and tactile rendering of the model. For complex software models， a multidirectional voxel algorithm and hash algorithm were used to store discrete data of the model. The collision algorithm was divided into bounding box and space decomposition， octree was used to judge whether two model were in the same node as rough collision， and whether collision would happen by the distance calculation of the basic elements. The simulation results shows that， the algorithm can feedback the attitude and force of the collision point in real time.

Keywords： virtual simulation;voxelization;collision detection;octree

1 研究背景

在實(shí)時(shí)仿真中，模型間的交互類型有移動(dòng)、觸碰、穿刺、切割、縫合等。其中，碰撞檢測(cè)[1]是這些操作的先決條件，只有判斷碰撞與否，才能計(jì)算產(chǎn)生的碰撞力并刷新變形效果。因此，精確快速的碰撞響應(yīng)是虛擬仿真的重要因素。

碰撞方式按照碰撞主體類型可分為剛體間的碰撞和剛體與軟件間碰撞[2]兩種情況。碰撞檢測(cè)方法主要有層次包圍盒法[3]和空間分解法[4]。常見的包圍盒算法有AABB包圍盒法、Sphere球包圍盒法、方向包圍盒及K-DOP包圍盒法等。包圍盒算法的原理是根據(jù)物體形狀，分別用立方體、圓等多邊體將物體包圍，并自動(dòng)檢測(cè)兩個(gè)物體包圍盒的距離，當(dāng)距離值小于指定閾值時(shí)，則認(rèn)定兩個(gè)物體發(fā)生碰撞。國(guó)內(nèi)外研究包圍盒方法均有一定歷史，國(guó)內(nèi)最具代表性的是國(guó)防科大[5]提出的基于固定方向的凸包包圍盒方法，該方法能適應(yīng)軟組織變形過程中拓?fù)浣Y(jié)構(gòu)的變化。2014年，Sulaiman等人根據(jù)AABB包圍盒，提出一種在虛擬狹窄環(huán)境中進(jìn)行階段性碰撞檢測(cè)的方法;2013年，Emre等人利用多線程提高碰撞檢測(cè)效率;2014年，陳琳等人研究一種混合包圍碰撞樹算法，有效提高了基于三角面片的碰撞檢測(cè)效率;2015年，彭晏飛[6]等人針對(duì)碰撞檢測(cè)的實(shí)時(shí)性和逼真度較差的缺陷，提出一種新的混合碰撞檢測(cè)算法，實(shí)驗(yàn)結(jié)果證明，與經(jīng)典的Rapid算法相比，該算法有效地減少了碰撞檢測(cè)的時(shí)間開銷，提高了碰撞檢測(cè)的實(shí)時(shí)性和真實(shí)感;2016年，孫勁光[7]提出一種基于形狀分類的包圍盒碰撞檢測(cè)優(yōu)化算法，實(shí)驗(yàn)結(jié)果表明，該算法縮短了相交測(cè)試的時(shí)間，提高了碰撞檢測(cè)的效率。

空間分解法是為了保證虛擬空間中不規(guī)則物體碰撞的精度，原理是將物體所在空間分割成若干個(gè)小的立方體，根據(jù)物體是否占據(jù)同一個(gè)空間節(jié)點(diǎn)來判斷是否發(fā)生碰撞。該方法是當(dāng)前研究的熱點(diǎn)。例如，F(xiàn)an[8]采用線性八叉樹結(jié)構(gòu)實(shí)現(xiàn)空間碰撞檢測(cè);李山[9]等人提出了基于八叉樹細(xì)分的并行碰撞檢測(cè)算法;臺(tái)灣大學(xué)的Mei[10]等人利用空間八叉樹結(jié)構(gòu)來檢測(cè)虛擬工具和機(jī)器人的碰撞。近年來，有些學(xué)者利用硬件加速和并行技術(shù)提高算法效率，如浙江工業(yè)大學(xué)Mei K J等人[11]研究利用GPU加速粒子流體動(dòng)力學(xué)模擬流血效果;青島大學(xué)吳世宇等人利用GPU實(shí)現(xiàn)光柵化，有效提高模型的體素化和碰撞檢測(cè)效率?？臻g分解法是一種常用的粗略碰撞測(cè)試方案，這將大大降低組合測(cè)試的數(shù)量，因此有利于提高碰撞效率。

總體來看，包圍盒法檢測(cè)規(guī)則幾何體的實(shí)時(shí)性和精確性較好。對(duì)于復(fù)雜幾何體，雖然可以利用改進(jìn)的包圍盒法來實(shí)現(xiàn)，但精度仍低于實(shí)時(shí)仿真的標(biāo)準(zhǔn)?？臻g分解法的優(yōu)點(diǎn)是精確度高，適用于不規(guī)則物體，缺點(diǎn)是內(nèi)存需求大，計(jì)算復(fù)雜，實(shí)時(shí)性差，因此對(duì)計(jì)算機(jī)硬件性能和算法有一定要求。而利用兩種方法的混合碰撞算法[12]是提高仿真實(shí)時(shí)性和精確性的有效方法。

2 碰撞檢測(cè)

本文提出一種基于哈希八叉樹結(jié)構(gòu)的多方向體素化算法。針對(duì)實(shí)時(shí)仿真中復(fù)雜軟體模型數(shù)據(jù)量多、計(jì)算量大的特點(diǎn)，采用一種基于歐式距離場(chǎng)的多方向快速體素法，并利用哈希表存儲(chǔ)八叉樹節(jié)點(diǎn)及模型離散體素;采用一種結(jié)合包圍盒和空間分解的碰撞檢測(cè)算法，通過粗略碰撞和精確碰撞兩階段實(shí)現(xiàn)碰撞檢測(cè)，同時(shí)實(shí)時(shí)反饋碰撞點(diǎn)位置和力。

2.1 八叉樹結(jié)構(gòu)和存儲(chǔ)

八叉樹是處理3D空間常見的方法和數(shù)據(jù)結(jié)構(gòu)。使用八叉樹存儲(chǔ)體素可以有效減少體素的高內(nèi)存需求，且更易理解離散化模型。一個(gè)優(yōu)秀的八叉樹數(shù)據(jù)結(jié)構(gòu)能高效和方便地搜索相鄰節(jié)點(diǎn)，因此可以有效提高對(duì)象內(nèi)部的體素化和碰撞檢測(cè)速度。

如圖1所示，八叉樹根節(jié)點(diǎn)是一個(gè)軸對(duì)齊的立方體包圍盒，隨后將其沿[x、y、z]軸劃分為8個(gè)子立方體，這8個(gè)子立方體就是子節(jié)點(diǎn)，繼續(xù)按上述方法對(duì)子節(jié)點(diǎn)進(jìn)行遞歸劃分，直至達(dá)到指定深度。在本文中，八叉樹單元中的深度是體素的[2l]倍，[l]為八叉樹單元的深度。

常用的傳統(tǒng)八叉樹數(shù)據(jù)結(jié)構(gòu)如圖2所示，原理如圖3所示。*NextNode指向子節(jié)點(diǎn)的下一節(jié)點(diǎn)地址;*FirstChild由子節(jié)點(diǎn)指向下個(gè)葉子節(jié)點(diǎn)的首地址;*object為模型指針;center是節(jié)點(diǎn)中心點(diǎn)，是int整型變量;m_size是采樣空間中的實(shí)際坐標(biāo)，原本是double型變量，在這里為了方便計(jì)算和哈希存儲(chǔ)，擴(kuò)大1 000倍后存為整型量。

為了快速查詢節(jié)點(diǎn)，本文采用基于索引的哈希算法來存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)，如圖4所示。哈希算法本質(zhì)上是一種散列表，是一種以“空間換時(shí)間”的算法，是關(guān)鍵碼值（Key value）而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)（見圖5）。也就是說，其通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。而當(dāng)使用哈希表進(jìn)行查詢時(shí)，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位。圖4中的數(shù)據(jù)結(jié)構(gòu)省去兩個(gè)單鏈表指針，只新增一個(gè)int型的value值，大大節(jié)約內(nèi)存。

本文哈希函數(shù)使用乘法哈希：

[Hash（key）=floor（m?（K?A-floor（K?A）））]? ? ? ? ? ? （1）

式中，[floor（）]表示小數(shù)向下取整;[K]取黃金比例0.618;[m]為210，哈希表使用STL容器中的hasp_map;[A]由center中的[x、y、z]確定，即體素點(diǎn)的相對(duì)空間位置，公式為：

[A=n2（z-1）+n（x-1）+y]? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

式中：[n=8l]。

2.2 體素化

體素化可以理解為二維像素化到三維空間的推廣，就是以三維采樣的方式將模型離散化，以數(shù)個(gè)正立方體的形式來表現(xiàn)模型，當(dāng)立方體越小時(shí)，模型精度越高，同時(shí)計(jì)算量也越大。

本文采用一種基于八叉樹的體素化算法。該方法分為兩個(gè)階段：一是根據(jù)八叉樹理論采用遞歸的方法細(xì)分空間，直到指定深度;二是提取軟組織所占空間網(wǎng)格，即體素化。首先輸入3DS格式的體網(wǎng)格模型，再歸一化到指定空間，然后對(duì)空間進(jìn)行八叉樹細(xì)分，再根據(jù)歐式距離法判定模型表面體素點(diǎn)，并計(jì)算投影向量與三角面片法向量關(guān)系來標(biāo)記模型體素點(diǎn)，最后將體素點(diǎn)鑲嵌于八叉樹節(jié)點(diǎn)中。

為了方便描述，將3D空間簡(jiǎn)化為2D空間。對(duì)于一個(gè)二維物體，由于已知模型邊界信息，因此考慮從四個(gè)方向逐行掃描模型包圍盒空間，掃描示意圖如圖6所示。在掃描過程中，將模型外部體素標(biāo)記為0，當(dāng)遇到第一個(gè)非0體素點(diǎn)時(shí)，則進(jìn)入下一行，直至完成這一方向。在經(jīng)過4個(gè)方向掃描后，可取得模型外部體素點(diǎn)的集合。對(duì)于整個(gè)包圍盒數(shù)據(jù)，除去外部體素，剩余則為模型表面和內(nèi)部體素，經(jīng)過渲染則實(shí)現(xiàn)了物體的體素化。

另外，判斷每一掃描行單個(gè)體素點(diǎn)是否為模型邊界，需要進(jìn)行基于歐式法的距離判定和三角形投影判定，具體步驟如下：第一步：預(yù)計(jì)算模型表面三角片所在平面、法向量等信息并存儲(chǔ);第二步：根據(jù)歐式距離法，計(jì)算體素點(diǎn)與三角片距離，當(dāng)該距離小于指定閾值時(shí)，表示體素點(diǎn)在模型表面，進(jìn)入第三步，否則循環(huán)判斷下一個(gè)體素點(diǎn);第三步：計(jì)算體素中心點(diǎn)在三角片上的投影向量，通過計(jì)算投影向量與三角片法向量的乘積，判斷該點(diǎn)是否在三角片內(nèi)，如果為真，表示該點(diǎn)是第一個(gè)模型邊界點(diǎn)，循環(huán)進(jìn)入下一行。

2.3 碰撞算法

本文的碰撞算法是結(jié)合基于空間分解法的粗略碰撞和基本圖元法的精確碰撞[13]。粗略碰撞通過計(jì)算剛體與節(jié)點(diǎn)中心點(diǎn)距離判斷剛體末端與軟體是否在同一節(jié)點(diǎn)內(nèi);精確碰撞通過計(jì)算剛體末端與軟體表面三角形單元距離判斷是否產(chǎn)生碰撞。

2.3.1 粗略碰撞檢測(cè)。該階段使用已構(gòu)造的空間Hash表，每個(gè)八叉樹節(jié)點(diǎn)存在對(duì)應(yīng)的Hash表中。由于八叉樹節(jié)點(diǎn)數(shù)量遠(yuǎn)低于體素點(diǎn)和模型點(diǎn)的數(shù)量，因此，在粗略碰撞階段，可以快速剔除遠(yuǎn)離潛在碰撞點(diǎn)的八叉樹節(jié)點(diǎn)，從而有效加快碰撞檢測(cè)速度。

為了方便描述粗略碰撞的原理，這里用2D圖表示3D場(chǎng)景（見圖7）。設(shè)點(diǎn)[A（x0，y0，z0）]為虛擬工具末端初始點(diǎn)，點(diǎn)[B（x1，y1，z1）]為虛擬工具末端移動(dòng)終點(diǎn)。圖中黑色正方形為八叉樹節(jié)點(diǎn)，邊長(zhǎng)[l=12d]，[d]為八叉樹深度，點(diǎn)[O（x2，y2，z2）]為其中心點(diǎn)，灰色為模型體素點(diǎn)。當(dāng)虛擬工具在點(diǎn)[A]時(shí)，與點(diǎn)[O]的距離為：

[distAO=（x0-x1）2+（y0-y1）2+（z0-z1）2]? ? ? ? ? （3）

此時(shí)，[distAO>22l]，則判定不存在粗略碰撞。

當(dāng)虛擬工具末端點(diǎn)在[B]時(shí)，與點(diǎn)[O]距離為：

[distBO=（x2-x1）2+（y2-y1）2+（z2-z1）2]? ? ? ? ? ?（4）

此時(shí)，[distBO<22l]，則判定存在粗略碰撞，進(jìn)入精確碰撞檢測(cè)階段。

2.3.2 精確碰撞檢測(cè)。精確碰撞檢測(cè)是當(dāng)粗略碰撞檢測(cè)發(fā)生后，如果虛擬工具末端點(diǎn)與軟組織在同一節(jié)點(diǎn)內(nèi)，則進(jìn)行基本圖元檢測(cè)，稱為點(diǎn)與三角形的相交測(cè)試，具體是判斷虛擬工具與軟組織表面是否產(chǎn)生碰撞。點(diǎn)與三角形測(cè)試使用較多的方法是未預(yù)處理三角形的計(jì)算質(zhì)心法和經(jīng)過預(yù)計(jì)算的三角形法兩種。

本文使用另外一種方法：針對(duì)三角形[ABC]和一點(diǎn)[P]，先進(jìn)行平移操作，使得[P]點(diǎn)位于原點(diǎn)，然后測(cè)試原點(diǎn)是否位于平移后的三角形內(nèi)部。當(dāng)且僅當(dāng)三角形[PAB]、[PBC]、[PCA]同為順時(shí)針或逆時(shí)針排列時(shí)，頂點(diǎn)[P]位于三角形[ABC]內(nèi)部（見圖8）。

經(jīng)過平移后，頂點(diǎn)[P]即為原點(diǎn)[O]，當(dāng)發(fā)生碰撞時(shí)，由于[O]在三角形內(nèi)部，所以該方法等價(jià)于計(jì)算式（5）的三個(gè)公式是否指向同一方向，即測(cè)試[u·v]是否大于等于0和[u·w]是否大于等于0。該方法的代碼如圖9所示。

[u=B×Cv=C×Aw=A×B]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

由于叉積成本較大，根據(jù)拉格朗日恒等式記為5點(diǎn)積形式，該方法代碼如圖10所示。

3 實(shí)驗(yàn)結(jié)果

本文對(duì)上述算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)使用的PC機(jī)是Win7、4.0GB的64位操作系統(tǒng)，利用雙線程實(shí)現(xiàn)基于CHAI3D和OPENGL開源庫(kù)的力覺和視覺渲染。

針對(duì)不同模型進(jìn)行不同分辨率下的體素化，得到仿真效果圖如圖11所示，體素化算法測(cè)試結(jié)果如表1所示。由圖11可知，該算法可以實(shí)現(xiàn)正常的視覺效果;由表1可知，在128和256體素率下，模型均可以較好地實(shí)現(xiàn)體素化。

碰撞檢測(cè)實(shí)驗(yàn)過程：用戶操作力反饋設(shè)備末端執(zhí)行器（見圖12），位姿映射到虛擬場(chǎng)景中剛體模型位姿，控制剛體模型觸碰軟體模型并進(jìn)行按壓操作，界面實(shí)時(shí)顯示剛體的相對(duì)位姿、反饋力及刷新頻率。

圖13為碰撞檢測(cè)效果圖，表2是碰撞檢測(cè)結(jié)果。通過表2可知，不斷移動(dòng)虛擬工具，刷新頻率平均在600Hz以上，可以滿足視覺要求，檢測(cè)時(shí)間在毫秒級(jí)，可以滿足實(shí)時(shí)性要求，同時(shí)可以實(shí)時(shí)反饋碰撞點(diǎn)的位置和產(chǎn)生的力。

4 結(jié)語

在實(shí)時(shí)仿真中，體素化算法處理復(fù)雜曲面軟體模型和高分辨率模型時(shí)預(yù)加載時(shí)間過長(zhǎng)，后期需要進(jìn)一步優(yōu)化算法和利用硬件GPU提升算法性能。另外，在剛體模型移動(dòng)過程中，需要遍歷整個(gè)軟體模型，耗時(shí)較長(zhǎng)，可以利用領(lǐng)域查找等方法進(jìn)一步提高實(shí)時(shí)性。

參考文獻(xiàn)：

[1]王文杰，劉國(guó)兵，陶磊.一種基于多傳感器的客車防碰撞預(yù)警系統(tǒng)[J].河南科技，2018（9）：115-117.

[2]沈華，陳金良，周志靖.混合空域中無人機(jī)飛行防相撞技術(shù)[J].指揮信息系統(tǒng)與技術(shù)，2016（6）：24-29.

[3]左軍濤，朱恩成，黃四牛.基于GPU胡航跡快速計(jì)算方法[J].指揮信息系統(tǒng)與技術(shù)，2011（4）：55-59.

[4]王杰，田宏安.無人機(jī)融入非隔離空域感知與規(guī)避技術(shù)[J].指揮信息系統(tǒng)與技術(shù)，2017（1）：27-32.

[5]龔隨，侯進(jìn)，鐘李濤.基于橢球擬合胡人體一服裝碰撞檢測(cè)方法[J].計(jì)算機(jī)應(yīng)用2，2019（1）：274-283.

[6]彭晏飛，盧真真.基于空間剖分和包圍盒的快速碰撞檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2015（8）：150-153，165.

[7]孫勁光，吳素紅，周積林.基于形狀分類的包圍盒碰撞檢測(cè)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件，2016（2）：242-245.

[8] Fan W S， Wang B， Paul J C， et al. An octree-based proxy for collision detection in large-scale particle systems[J]. Science China-Information Sciences，2013（1）：1-10.

[9]李山，趙偉，李菲.一種基于八叉樹與流水線技術(shù)的快速碰撞檢測(cè)算法[J].計(jì)算機(jī)與現(xiàn)代化，2011（1）：20-24.

[10]張璐鵬.適用于柔性體切割仿真的八叉樹體模型生成算法[D].青島：青島大學(xué)，2018.

[11] Mei K J， Rong S. Collision detection for virtual machine tools and virtual robot arms using the Shared Triangles Extended Octrees method[J]. International Journal of Computer Integrated Manufacturing，2016（4）：355-373.

[12]鮑義東，吳冬梅.粘彈性軟組織建模和切割及虛擬仿真實(shí)驗(yàn)研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2016.

[13]朱卓，李宏勝.虛擬手術(shù)中人體軟組織超粘彈性建模及穿刺仿真[J].應(yīng)用力學(xué)學(xué)報(bào)，2019（2）：304-309.