朱卓 劉云飛 汪坤 劉森

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

關鍵詞：虛擬仿真;體素化;碰撞檢測;八叉樹

中圖分類號：TP391 文獻標識碼：A 文章編號：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 研究背景

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

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

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

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

2 碰撞檢測

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

2.1 八叉樹結構和存儲

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

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

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

為了快速查詢節(jié)點，本文采用基于索引的哈希算法來存儲數(shù)據(jù)結構，如圖4所示。哈希算法本質上是一種散列表，是一種以“空間換時間”的算法，是關鍵碼值（Key value）而直接進行訪問的數(shù)據(jù)結構（見圖5）。也就是說，其通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。而當使用哈希表進行查詢時，就是再次使用哈希函數(shù)將key轉換為對應的數(shù)組下標，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進行數(shù)據(jù)定位。圖4中的數(shù)據(jù)結構省去兩個單鏈表指針，只新增一個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]確定，即體素點的相對空間位置，公式為：

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

式中：[n=8l]。

2.2 體素化

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

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

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

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

2.3 碰撞算法

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

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

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

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

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

當虛擬工具末端點在[B]時，與點[O]距離為：

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

此時，[distBO<22l]，則判定存在粗略碰撞，進入精確碰撞檢測階段。

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

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

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

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

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

3 實驗結果

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

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

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

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

4 結語

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

參考文獻：

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

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

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

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

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

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

[7]孫勁光，吳素紅，周積林.基于形狀分類的包圍盒碰撞檢測優(yōu)化算法[J].計算機應用與軟件，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]李山，趙偉，李菲.一種基于八叉樹與流水線技術的快速碰撞檢測算法[J].計算機與現(xiàn)代化，2011（1）：20-24.

[10]張璐鵬.適用于柔性體切割仿真的八叉樹體模型生成算法[D].青島：青島大學，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]鮑義東，吳冬梅.粘彈性軟組織建模和切割及虛擬仿真實驗研究[D].哈爾濱：哈爾濱工業(yè)大學，2016.

[13]朱卓，李宏勝.虛擬手術中人體軟組織超粘彈性建模及穿刺仿真[J].應用力學學報，2019（2）：304-309.