虛擬吊裝碰撞檢測(cè)算法

高越 馬行 周凱

【關(guān)鍵詞】虛擬吊裝 AABB包圍盒 汽車起重機(jī)設(shè)計(jì)

在大型吊裝工程中吊裝方案制定是吊裝作業(yè)的重要環(huán)節(jié)。高效、合理的吊裝方案對(duì)吊裝工程有著重要的意義。目前有研究采用虛擬現(xiàn)實(shí)技術(shù)來(lái)完成模擬仿真，通過(guò)計(jì)算機(jī)輔助制定吊裝方案。但對(duì)吊裝方案制定的研究成果還很有限。

本文通過(guò)對(duì)虛擬吊裝碰撞檢測(cè)算法分析，選擇AABB包圍盒方法對(duì)空間中物體包圍并對(duì)汽車起重機(jī)設(shè)計(jì)層次包圍盒樹(shù)完成虛擬吊裝碰撞檢測(cè)。快速有效地制定出吊裝方案，輔助施工人員順利地完成吊裝作業(yè)，降低吊裝過(guò)程中的作業(yè)風(fēng)險(xiǎn)。

1 層次包圍盒碰撞檢測(cè)算法

1.1 層次包圍盒算法

目前，典型的層次包圍盒有軸向包圍盒（AABB）、包圍球（Sphere）、k-dop包圍盒、方向包圍盒（OBB）。我們分別對(duì)各類包圍盒進(jìn)行討論，深入研究他們的優(yōu)缺點(diǎn)。如圖1所示各種包圍盒在二維平面的示例。

包圍球是四種包圍盒中最簡(jiǎn)單的包圍體，它的計(jì)算非常簡(jiǎn)單，同時(shí)相比于其他包圍盒做相交測(cè)試和節(jié)點(diǎn)修改更加簡(jiǎn)單。但它與物體的逼近程度不夠好，緊密性差。軸向包圍盒也是比較簡(jiǎn)單的包圍盒算法且具有相對(duì)較好的緊密性，AABB包圍盒樹(shù)的構(gòu)建和更新都比較快，同時(shí)相互間的相交測(cè)試也很快，所以軸向包圍盒得到廣泛的應(yīng)用。方向包圍盒相互之間的相交測(cè)試相對(duì)復(fù)雜，相交測(cè)試的時(shí)間復(fù)雜度比AABB要高出很多。雖然它的時(shí)間復(fù)雜度高，但它緊密性比較好，可以降低相交測(cè)試包圍盒的數(shù)目。k-dop對(duì)包圍物體的逼近程度比包圍球和AABB要好很多，但它的耗費(fèi)相比包圍球和AABB也提高了很多，構(gòu)建這樣的包圍盒有一定的困難，如表1所示。

2 虛擬吊裝碰撞檢測(cè)

2.1 層次包圍盒度的選擇

根據(jù)碰撞檢測(cè)特點(diǎn)在汽車起重機(jī)虛擬吊裝仿真場(chǎng)景中分析得出，AABB層次包圍盒法適合汽車起重機(jī)虛擬吊裝仿真場(chǎng)景碰撞檢測(cè)。本文對(duì)靜態(tài)物體直接采用AABB包圍盒進(jìn)行包圍，對(duì)汽車起重機(jī)建立層次包圍盒樹(shù)。

樹(shù)的節(jié)點(diǎn)中最大子節(jié)點(diǎn)個(gè)數(shù)為層次包圍盒樹(shù)的度。樹(shù)的度比較大，那么樹(shù)的高度就比較小，樹(shù)度大的情況下檢測(cè)每個(gè)節(jié)點(diǎn)時(shí)的計(jì)算量較大。當(dāng)樹(shù)的度比較小時(shí)樹(shù)的高度較大，在樹(shù)度小的情況下檢測(cè)每個(gè)節(jié)點(diǎn)時(shí)的計(jì)算量較小。度為2是汽車起重機(jī)虛擬仿真環(huán)境中碰撞檢測(cè)通常使用的度。因?yàn)槎鏄?shù)被稱為最簡(jiǎn)單的樹(shù)狀結(jié)構(gòu)，二叉樹(shù)的構(gòu)造比較快，同時(shí)計(jì)算復(fù)雜度小。

2.2 汽車起重機(jī)層次包圍盒樹(shù)的構(gòu)建

自頂向下、自底向上、漸進(jìn)插入方法是層次包圍盒樹(shù)的幾種構(gòu)建方法。常用自頂向下法構(gòu)建層次包圍盒樹(shù)，它相比自底向上法更容易實(shí)現(xiàn)，而漸進(jìn)插入方法最為復(fù)雜。本文對(duì)汽車起重機(jī)包圍盒數(shù)的構(gòu)建使用自頂向下法。

建立汽車起重機(jī)層次包圍盒樹(shù)需要根據(jù)起重機(jī)父子層次結(jié)構(gòu)以及實(shí)體形態(tài)進(jìn)行設(shè)計(jì)。采用自頂而下的方法從根節(jié)點(diǎn)逐層為相應(yīng)的節(jié)點(diǎn)構(gòu)建幾何體進(jìn)行包圍。再對(duì)每一個(gè)包含實(shí)際幾何元的葉子節(jié)點(diǎn)采用AABB包圍盒實(shí)現(xiàn)精確碰撞檢測(cè)。如圖2所示。

2.3 層次包圍盒的相交測(cè)試

假設(shè)碰撞檢測(cè)的起重機(jī)與吊裝環(huán)境的層次樹(shù)根節(jié)點(diǎn)分別為節(jié)點(diǎn)N和節(jié)點(diǎn)M，按下面步驟判斷兩物體是否相交：

第一步：確定根節(jié)點(diǎn)N和M構(gòu)造的包圍盒是否相交，若判定不相交則沒(méi)有碰撞問(wèn)題發(fā)生，否則進(jìn)行第二步。

第二步：對(duì)節(jié)點(diǎn)N進(jìn)行深度優(yōu)先遍歷，將節(jié)點(diǎn)N的子孫節(jié)點(diǎn)與節(jié)點(diǎn)M做包圍盒相交測(cè)試，若包圍盒不相交則跳出此時(shí)測(cè)試的子樹(shù)，繼續(xù)測(cè)試節(jié)點(diǎn)N的剩余子孫節(jié)點(diǎn)。如果測(cè)試到節(jié)點(diǎn)N的葉子節(jié)點(diǎn)，設(shè)葉子節(jié)點(diǎn)為節(jié)點(diǎn)Q，則進(jìn)行第三步，若測(cè)試結(jié)束則返回沒(méi)有碰撞發(fā)生。

第三步：對(duì)節(jié)點(diǎn)M進(jìn)行深度優(yōu)先遍歷，將節(jié)點(diǎn)M的子孫節(jié)點(diǎn)和節(jié)點(diǎn)Q做包圍盒相交測(cè)試，如包圍盒不相交則跳出當(dāng)前測(cè)試的子樹(shù)，繼續(xù)測(cè)試節(jié)點(diǎn)M的剩余子孫節(jié)點(diǎn)。如果測(cè)試到節(jié)點(diǎn)M的葉子節(jié)點(diǎn)，設(shè)葉子節(jié)點(diǎn)為節(jié)點(diǎn)P，則進(jìn)行第四步，若測(cè)試結(jié)束則返回第二部。

第四步：對(duì)葉子節(jié)點(diǎn)Q和葉子節(jié)點(diǎn)P做相交檢測(cè)，若沒(méi)有發(fā)生碰撞則返回第三步繼續(xù)測(cè)試，否則返回有碰撞發(fā)生，退出遍歷。

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

如圖3、圖4所示包圍盒的各條邊用白線框表示。完成各物體的包圍后，當(dāng)?shù)跹b仿真中運(yùn)動(dòng)物體的白色邊框與其他物體的白色邊框相交時(shí)，運(yùn)動(dòng)物體將在原地進(jìn)行碰撞檢測(cè)而不會(huì)穿越物體，這樣能夠較好的體現(xiàn)虛擬吊裝仿真的真實(shí)。

4 結(jié)束語(yǔ)

本文通過(guò)對(duì)汽車起重機(jī)虛擬吊裝碰撞檢測(cè)算法分析，采用AABB包圍盒方法對(duì)空間中物體包圍并對(duì)汽車起重機(jī)設(shè)計(jì)層次包圍盒樹(shù)完成虛擬吊裝碰撞檢測(cè)。實(shí)驗(yàn)表明，本文碰撞檢測(cè)算法能夠完成汽車起重機(jī)虛擬吊裝過(guò)程中的碰撞檢測(cè)具有設(shè)計(jì)合理，對(duì)汽車起重機(jī)虛擬吊裝仿真相關(guān)技術(shù)的研究有一定價(jià)值。

參考文獻(xiàn)

[1]S.Melax.Dynamic plane shifting BSP traversal[C].Proceedings graphics interface 2000，213-220.

[2]劉曉平，翁曉毅，陳皓.運(yùn)用改進(jìn)的八叉樹(shù)算法實(shí)現(xiàn)精確碰撞檢測(cè)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005， 17 （12）：2631-2634.

[3]張國(guó)飚，張華，劉滿祿，余慧.基于空間剖分的碰撞檢測(cè)算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（7）：46-55.

[4]朱元峰，孟軍，謝光華.基于復(fù)合層次包圍盒的實(shí)時(shí)碰撞檢測(cè)研究[J].系統(tǒng)仿真學(xué)報(bào)，2008，20（2）：272-277.