劉佳祎， 楊呈永

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

0 引言

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

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

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

1.1 并行計(jì)算

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

1.2 空間劃分原理

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

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

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

圖1 并行空間劃分

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

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

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

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

1.3.3 進(jìn)行相交測試

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

2 碰撞檢測算法

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

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

2.1 空間碰撞檢測定義

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

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

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

2.2 空間排序碰撞檢測算法

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

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

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

2.3 雙調(diào)排序算法

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

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

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

3 并行空間雙調(diào)排序碰撞檢測算法

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

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

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

3.1.1 網(wǎng)格初始化

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

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

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

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

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

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

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

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

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

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

3.2 并行空間的雙調(diào)排序算法（Bitonic Sorter）

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

圖3 排序結(jié)果

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

假設(shè)給定雙調(diào)序列（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｝。由此可得出如下結(jié)論：

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

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

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

步驟1每2個元素進(jìn)行升序和降序排序。

步驟2先對每4個元素進(jìn)行升降，再對每2個元素進(jìn)行升降。

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

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

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

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

圖4 4個線程排序

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

圖6 配件安裝界面

5 結(jié)語

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