虛擬實驗教學中并行空間雙調排序碰撞檢測算法研究

劉佳祎， 楊呈永

（桂林理工大學網(wǎng)絡與信息中心，廣西 桂林 541004）

0 引言

作為教學應用值得研究的重要領域—虛擬仿真現(xiàn)實技術，已隨著計算機技術的發(fā)展廣泛運用于教學。在實踐教學課上虛擬化仿真對學生的動手能力、實踐能力提升有很重要的意義［1-2］。精準、高效地碰撞檢測使虛擬環(huán)境更加真實，虛擬環(huán)境本身的復雜性和實時性對碰撞檢測提出了更高的要求。如何快速、高效地完成檢測成為虛擬仿真現(xiàn)實技術中的一大難題。

1 并行空間劃分優(yōu)化算法

并行計算具有強大的數(shù)據(jù)計算和處理能力，是計算機領域的研究熱點之一，在空間劃分方面也尤為適用。利用并行空間劃分來描述實體的運動情況，提升單元網(wǎng)格大小以減少兩個物體之間的碰撞次數(shù)。

1.1 并行計算

并行計算［3-5］（Parallel Computing）是指同時使用多個處理器、多種計算資源在單位時間內完成多指令流和多數(shù)據(jù)流解決同一計算問題的過程，用來加快解題速度提高處理能力。并行算法，是一種通過每次可計算多個指令來解決大量數(shù)據(jù)且復雜度高的算法。并行算法目前主要分為兩種，一種是通過運用代數(shù)模式進行計算的如矩陣運算、處理數(shù)字信號等數(shù)值并行算法（Numeric Parallel Algorithm），另一種是在比較關系中進行運算包括在數(shù)據(jù)庫操作及優(yōu)化過程中一些符號處理的非數(shù)值并行算法（Non-numeric Parallel Algorithm）。

1.2 空間劃分原理

空間劃分［6］在某種方面上比起排序和搜索算法更容易實現(xiàn)且效果尚佳，比較合適并行算法。用相同大小的網(wǎng)格（從3D的角度來說就是立方體）將整個空間劃分開，并且每個網(wǎng)格的大小要大于最大物體的體積，保證每個網(wǎng)格單元中都有相應的鏈表，存在網(wǎng)格中的物體（包括質心在網(wǎng)格內），將會發(fā)生碰撞。

1.3 并行空間劃分原理及算法

因會涉及并行算法等問題，比起傳統(tǒng)的空間劃分，并行空間劃分更加復雜。當一個物體與多個網(wǎng)格存在接觸，如按照傳統(tǒng)空間劃分每個網(wǎng)格都會對存儲在自己鏈表的物體進行處理，這樣容易導致同一個物體在同一時間進行多次修改。為解決這個問題，同時減少發(fā)生物體之間碰撞次數(shù)，需要對傳統(tǒng)的空間算法進行優(yōu)化，如圖1所示。

圖1 并行空間劃分

1.3.1 劃分規(guī)則單元格

將物體存儲網(wǎng)格ID的方式，改變成主單元ID加相交單元ID的方法。簡單地說，主單元ID就是物體質心所在的單元，其接觸的單元ID為次單元ID或者成為幻影單元。

1.3.2 確定物體占有的空間單元

為保證每次計算時處理的每個單元和其他單體之間至少隔一個單元，將網(wǎng)格單元的大小提高至最大物體邊界框的倍，確保每次僅有存在某個物體的單元，可以對物體進行修改。

1.3.3 進行相交測試

只對占據(jù)同一單元格或相鄰單元格的實體進行相交測試，即具有相同標示的單元網(wǎng)格可以進行并行處理。

2 碰撞檢測算法

碰撞檢測算法在時間域可以劃分為連續(xù)、離散和靜態(tài)3種基本形態(tài)；在空間域則有物體和圖像2種空間分類。

在物體空間中比較常見的檢測技術主要有：進行層次性組織，剔除分支，加快碰撞空間剖分法；逼近對象，進行代替，快速排除層次包圍盒方法。上述算法均利用三維特性進行相交計算，通過投影的圖像及深度信息進行相交運算的碰撞檢測方法［7］。

2.1 空間碰撞檢測定義

將三維空間以及時間結合形成四維空間，通過對物體的空間進行劃分來描述物體的運動狀況［8］。通過使用點集來描述這個在四維空間中的物體，即：

式中：q為物體；t為時間；M為物體的三維空間點集；T（t，M）則為三維空間點集中每個點在t時間的位置。如果兩個物體M1和M2的運動情況可以用四維空間中的點集和表示（*為區(qū)分三維和四維空間的點集），在何時某兩個物體占用空間位置的關系可表示：在（q，t）集合中，有（q1，t1）∈和（q2，t2）∈，當且僅當≠Φ時，發(fā)生碰撞［9］。具體四維空間的碰撞算法如下：

輸出：檢測結果（True為相交，F(xiàn)alse為不相交）

2.2 空間排序碰撞檢測算法

空間剖分法［9］能依層次、快速靈活地將物體場景中的空間分割為相應的子空間對，在檢測過程中，大大減少各空間對物體的相交概率，快速刪除多余的檢測，降低檢測時間，是一種分而治之思想，空間排序和各種叉樹剖分算法在許多場景空間較為常用。一般情況下當物體運動時空間剖分算法僅計算運動對象所占用的空間單元即可。這種算法對于在離散環(huán)境中分布較為均勻的集合之間的碰撞檢測效果最為明顯。Clark提出用來逼近幾何對象的如球包圍盒（Sphere）、軸對齊包圍盒（AABB）［10］、k-Dops［11］、方向包圍盒（OBB）［12］等常見的層次包圍盒，以根節(jié)點為母體進行劃分，通過不斷地對上一節(jié)點物體的拆分來完成物體的幾何替代，選擇較原物體略大且結構簡單、緊密性較好的包圍盒，排除不相交的元素對，能快速準確地進行碰撞檢測。

為能高效處理多運動物體場景，靳雁霞等［13］將軸對稱包圍盒與具有二分類功能的深度神經(jīng)網(wǎng)絡相結合提出了圓形包圍盒樹結構。該算法測試速度快，不僅可提高自碰撞檢測高層剔除率，還可降低模擬整體耗時。

蔣健勛等［14］在此算法上運用OBB層次包圍盒進行精確檢測，在通過Sphere包圍盒迅速把空間內不相交的物體排除在外，提出OBB-sphere混合層檢測的算法，使包圍盒的精密性和單一性之間的沖突得以有效解決。趙吉［15］將Sphere包圍球和k-Dops包圍相結合，構造了一種新的混合層次包圍盒算法，有效證明了混合層次包圍盒比單一層次包圍盒的實時性更高。

2.3 雙調排序算法

雙調排序是最早采用反復歸并2個雙調序列的方式來實現(xiàn)排序的并行排序算法，在一段時間內曾被認為是最實用的并行排序算法之一。雙調序列是一個先單調增后單調減的序列，它是通過循環(huán)移位后滿足上述條件的序列。設（a1，a2，…，a2n）為一個長為2n的雙調序列，對于所有的i（1≤i≤n），將ai與ai+n比較交換，得到：bi=min（ai，ai+n）和ci=max（ai，ai+n），則2個子序列（b1，b2，…，bn）和（c1，c2，…，cn）也均是雙調序列。當n為2的方冪時，雙調排序算法的原理可描述如下：

近年來，仍然有相當多的文章討論雙調排序算法在并行環(huán)境下的實現(xiàn)［16-18］，由此可見，雙調排序算法在目前并行排序算法的研究中仍具有影響力。

本文算法先用并行算法對空間劃分進行優(yōu)化，使發(fā)生在2物體之間的碰撞檢查次數(shù)減少，再用雙調排序算法對碰撞的物體進行詳細檢查?？臻g劃分技術僅對同一子空間內的部分物體做相交測試，采用運動對象時空的局限性，按照一定準則將空間劃分為多個子空間，減少碰撞檢測運算中不必要的開銷。

3 并行空間雙調排序碰撞檢測算法

并行空間劃分較傳統(tǒng)的空間劃分更為復雜，需進一步優(yōu)化，這里給出優(yōu)化步驟，再結合雙調排序算法對空間排序檢測技術作出系統(tǒng)改進，實現(xiàn)運算開銷的減少。

3.1 并行空間劃分實現(xiàn)步驟

并行空間劃分過程主要是由2個步驟實現(xiàn)。①利用網(wǎng)格的初始化過程建立對象屬性；②單元ID數(shù)組的建設，用來對相關數(shù)據(jù)儲存分析。

3.1.1 網(wǎng)格初始化

針對所需的數(shù)據(jù)，對每個物體和單元網(wǎng)格建立相關對象屬性。對每個物體來說，都需要一個ID屬性，一個控制屬性（存儲單元類型，如主單元還是次單元），一組物體所有接觸網(wǎng)格的單元ID信息（至多2n個，n為所在空間維度）。簡單說明如下：

（1）單元ID數(shù)組，存儲網(wǎng)格中所有接觸的物體ID。

（2）物體ID數(shù)組，存儲物體的ID號及物體的控制屬性。

3.1.2 建立單元ID數(shù)組

在進行碰撞檢測之前，要給單元ID數(shù)組賦值。對每個物體，很可能會存在多個與物體相互接觸的網(wǎng)格單元。其質心所在單元成為主單元（home cell）或稱為H單元，其他則稱為次單元（Phantom Cell）或者幻影單元、P單元。

對于每個物體的H單元ID，根據(jù)其質心所在網(wǎng)格單元建立的哈希值

式中：pos值為物體的坐標；CellSize為空間維度；Shift為預定義常量，用來確定分配的位數(shù)。一般將坐標以32 bit uint型存儲，讓其中8 bit為空，其他位用來存儲坐標XYZ。為確定是主單元還是次單元，利用控制位來標示單元對象類型。

確定其物體除主單元之外的其他單元。在受限于網(wǎng)格大小的情況下，一個物體最多存在2n-1個次單元，如果數(shù)量少于2n-1個，則其余單元ID標記為0xFFFFFFFF，為無效單位。用圖2說明建立結果。

圖2 序列化單元ID數(shù)組

在所有單元ID建立完成后，需對其進行存儲。利用并行計算方法，將每個物體中單元ID的數(shù)字快速存儲在專門的單元數(shù)組里，縮減多余的空單元ID，并根據(jù)單元哈希值和單元類型進行排序。

3.2 并行空間的雙調排序算法（Bitonic Sorter）

通過雙調排序算法，對劃分過程中并行空間內所產(chǎn)生的單元ID進行排序。一個單元ID的哈希值可能在不同物體中存在，而且不同類型沒有先后（H或者P），為了之后方便對數(shù)據(jù)進行計算，須將相同哈希值的單元ID，根據(jù)單元類型按順序排列，主單元排在同組的最前面，并選擇一種穩(wěn)定性較好的排序算法。具體如圖3所示。

圖3 排序結果

雙調歸并排序是一個并行排序算法，它常被用來建立排序網(wǎng)絡以及并行處理系統(tǒng)。雙調歸并網(wǎng)絡是基于Batcher定理，因此也受定理約束。

假設給定雙調序列（x0，x1，…，xn-1），對于所有的0≤i≤n/2-1，執(zhí)行xi和xi+n/2的比較交換得到si=min｛xi，xi+n/2｝和li=max｛xi，xi+n/2｝。由此可得出如下結論：

（1）小序列（s0，s1，…，sn-1）和大序列（l0，l1，…，ln-1）仍是雙調序列；

（2）對于所有的0≤i，j≤n/2-1，均滿足si≤lj。

在一般情況下，該算法時間復雜度為O［nlg（n）］，通過并行方法來實現(xiàn)后，變?yōu)镺（lg（n）），而且最好和最差的情況是一樣的，這也就確保了其優(yōu)秀的穩(wěn)定性。使用4個線程對如下線程組的數(shù)據(jù)進行排序，過程如下：初始為排序數(shù)據(jù)。

步驟1每2個元素進行升序和降序排序。

步驟2先對每4個元素進行升降，再對每2個元素進行升降。

步驟3執(zhí)行一個2×4的數(shù)據(jù)集轉置。

步驟4現(xiàn)在8個元素可以使用共享內存進行排序。

步驟5數(shù)據(jù)轉置回來。

步驟6執(zhí)行剩余的排序。

圖4 4個線程排序

4 實驗結果與分析

在計算機組裝實驗中用鼠標拖動配件進行定位組裝，采用并行空間雙調排序碰撞檢測算法和串行碰撞檢測算法進行測試對比。實驗中隨機選取3個組裝配件定位采用2種算法進行實驗。算法采用C#語言在多處理器上實現(xiàn)，以64 bit處理器為平臺，在1024×768分辨率下測試不同算法相同時間內配件碰撞檢測次數(shù)，數(shù)據(jù)記錄如圖5所示。

圖5 不同算法相同時間內各配件碰撞檢測次數(shù)

通過結果比較，采用并行雙調排序算法比傳統(tǒng)串行碰撞檢測算法，配件組裝碰撞次數(shù)有明顯減少。

除此之外，還測試了不同配件在不同檢測算法下檢測次數(shù)和所用時間，數(shù)據(jù)記錄見表1。

表1 不同算法配件安裝成功碰撞次數(shù)和所用時間

不同算法配件安裝界面效果如圖6所示。

圖6 配件安裝界面

5 結語

本文對傳統(tǒng)的空間排序檢測技術進行改進，運用雙調歸并排序算法對網(wǎng)格進行排序，以減小系統(tǒng)的時間復雜度。通過對串行和并行空間雙調排序劃分方法的實驗數(shù)據(jù)比較驗證了本算法的有效性。本檢測法滿足虛擬實驗組裝教學需求，在碰撞對象較多的虛擬場景中無論是碰撞次數(shù)還是檢測速度均有明顯效果，非常適合在計算機組裝與維護虛擬實驗教學系統(tǒng)配件檢測定位中應用本優(yōu)化碰撞檢測算法，值得在虛擬實驗中的推廣。