虛擬吊裝碰撞檢測算法

高越 馬行 周凱

【關鍵詞】虛擬吊裝 AABB包圍盒 汽車起重機設計

在大型吊裝工程中吊裝方案制定是吊裝作業的重要環節。高效、合理的吊裝方案對吊裝工程有著重要的意義。目前有研究采用虛擬現實技術來完成模擬仿真，通過計算機輔助制定吊裝方案。但對吊裝方案制定的研究成果還很有限。

本文通過對虛擬吊裝碰撞檢測算法分析，選擇AABB包圍盒方法對空間中物體包圍并對汽車起重機設計層次包圍盒樹完成虛擬吊裝碰撞檢測。快速有效地制定出吊裝方案，輔助施工人員順利地完成吊裝作業，降低吊裝過程中的作業風險。

1 層次包圍盒碰撞檢測算法

1.1 層次包圍盒算法

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

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

2 虛擬吊裝碰撞檢測

2.1 層次包圍盒度的選擇

根據碰撞檢測特點在汽車起重機虛擬吊裝仿真場景中分析得出，AABB層次包圍盒法適合汽車起重機虛擬吊裝仿真場景碰撞檢測。本文對靜態物體直接采用AABB包圍盒進行包圍，對汽車起重機建立層次包圍盒樹。

樹的節點中最大子節點個數為層次包圍盒樹的度。樹的度比較大，那么樹的高度就比較小，樹度大的情況下檢測每個節點時的計算量較大。當樹的度比較小時樹的高度較大，在樹度小的情況下檢測每個節點時的計算量較小。度為2是汽車起重機虛擬仿真環境中碰撞檢測通常使用的度。因為二叉樹被稱為最簡單的樹狀結構，二叉樹的構造比較快，同時計算復雜度小。

2.2 汽車起重機層次包圍盒樹的構建

自頂向下、自底向上、漸進插入方法是層次包圍盒樹的幾種構建方法。常用自頂向下法構建層次包圍盒樹，它相比自底向上法更容易實現，而漸進插入方法最為復雜。本文對汽車起重機包圍盒數的構建使用自頂向下法。

建立汽車起重機層次包圍盒樹需要根據起重機父子層次結構以及實體形態進行設計。采用自頂而下的方法從根節點逐層為相應的節點構建幾何體進行包圍。再對每一個包含實際幾何元的葉子節點采用AABB包圍盒實現精確碰撞檢測。如圖2所示。

2.3 層次包圍盒的相交測試

假設碰撞檢測的起重機與吊裝環境的層次樹根節點分別為節點N和節點M，按下面步驟判斷兩物體是否相交：

第一步：確定根節點N和M構造的包圍盒是否相交，若判定不相交則沒有碰撞問題發生，否則進行第二步。

第二步：對節點N進行深度優先遍歷，將節點N的子孫節點與節點M做包圍盒相交測試，若包圍盒不相交則跳出此時測試的子樹，繼續測試節點N的剩余子孫節點。如果測試到節點N的葉子節點，設葉子節點為節點Q，則進行第三步，若測試結束則返回沒有碰撞發生。

第三步：對節點M進行深度優先遍歷，將節點M的子孫節點和節點Q做包圍盒相交測試，如包圍盒不相交則跳出當前測試的子樹，繼續測試節點M的剩余子孫節點。如果測試到節點M的葉子節點，設葉子節點為節點P，則進行第四步，若測試結束則返回第二部。

第四步：對葉子節點Q和葉子節點P做相交檢測，若沒有發生碰撞則返回第三步繼續測試，否則返回有碰撞發生，退出遍歷。

3 實驗結果分析

如圖3、圖4所示包圍盒的各條邊用白線框表示。完成各物體的包圍后，當吊裝仿真中運動物體的白色邊框與其他物體的白色邊框相交時，運動物體將在原地進行碰撞檢測而不會穿越物體，這樣能夠較好的體現虛擬吊裝仿真的真實。

4 結束語

本文通過對汽車起重機虛擬吊裝碰撞檢測算法分析，采用AABB包圍盒方法對空間中物體包圍并對汽車起重機設計層次包圍盒樹完成虛擬吊裝碰撞檢測。實驗表明，本文碰撞檢測算法能夠完成汽車起重機虛擬吊裝過程中的碰撞檢測具有設計合理，對汽車起重機虛擬吊裝仿真相關技術的研究有一定價值。

參考文獻

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

[2]劉曉平，翁曉毅，陳皓.運用改進的八叉樹算法實現精確碰撞檢測[J].計算機輔助設計與圖形學學報，2005， 17 （12）：2631-2634.

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

[4]朱元峰，孟軍，謝光華.基于復合層次包圍盒的實時碰撞檢測研究[J].系統仿真學報，2008，20（2）：272-277.