虛擬裝配系統中一種快速碰撞檢測方法

李秀莉，張樹仁

(長春理工大學，長春130022)

在虛擬裝配環境中，碰撞檢測用于判定一對或多對物體在給定時間域內的同一時刻是否占有相同區域。它是虛擬裝配的關鍵技術之一。在虛擬的環境中零部件的裝配必須能夠針對碰撞檢測的結果如實、快速做出合理的響應，反映真實動態效果[1]。目前，機電系統越來越復雜，由三維幾何模型構成的虛擬場景規模越來越大，對虛擬裝配實時性和真實性要求越來越高，故快速碰撞檢測技術成為研究熱點。

碰撞檢測方法總體上可分為兩類:靜態干涉檢測算法和動態碰撞檢測算法，動態碰撞檢測算法又分為離散碰撞檢測算法和連續碰撞檢測算法。其基本原理是基于圖形和基于圖像的碰撞檢測。這兩類算法的主要區別在于是利用物體三維幾何特性進行求交計算，還是利用物體二維投影的圖像及深度信息來進行相交分析[2]。其中在基于圖形的碰撞檢測上，研究人員已經做了大量的工作，形成了層次包圍盒法和空間分割法等成熟算法[3-5]。

在三維環境中尋找碰撞是非常苛刻的任務。尋找碰撞時間占總運行時間的50%。對于復雜機電系統，三維虛擬原型是非常復雜的，含有成千上萬的元素。為此，本文提出了一種能夠快速、準確檢測碰撞的交迭軸包圍盒碰撞檢測算法。

1 表面碰撞檢測算法原理

交迭軸包圍盒是包圍盒碰撞檢測方法的擴展和延伸，該方法中將一個三維的模型定義為一種表面的集合，每個表面又被單獨描繪成一個三角形的合集，采用每個面的軸對齊包圍盒和重疊軸對齊，即交迭軸包圍盒的方法，篩選出相交的表面。表面碰撞檢測算法的體系結構如圖1所示。

圖1 表面碰撞檢測算法體系結構Fig.1 Surface collision detection architecture for solving the narrow phase

兩個實體A和B，定義MAB為實體B與實體A的交迭處的變換矩陣。

圖2中每個實體被定義為AABB，判斷兩個實體A和B是否相交，如果這對軸對齊包圍盒不重疊，則A與B不相交；如果相應的軸對齊包圍盒重疊，則A和B是兩個碰撞的候選對象。在這種情況下，重疊軸對齊包圍盒OAABB(A，B)被確定，如圖2所示。

圖2 二維中OAABB概念Fig.2 The OAABB concept shown in 2D

2 碰撞表面判定

為了提高表面碰撞檢測算法的性能和檢測速度，使用每個面的軸對齊包圍盒和重疊軸對齊包圍盒，即交迭軸包圍盒方法，篩選碰撞表面，如圖3所示。

圖3 交迭軸包圍盒碰撞表面篩選Fig.3 The surface filter process shown

考慮OAABB(A，B)由兩個相交候選對象，與AABBs表面不相交的OAABB被篩選掉。對每個對象的剩余m表面，分別判定與表面AABBs是否相交。這一步復雜度為O(m2)。實施這一步驟程序結構如下：

3 多邊形相交管理程序

確定了可能碰撞的表面，需要從這一對表面找出需要檢查的每一對多邊形碰撞。兩個多邊形相交是一個費時的運算操作。應該放棄AABBS不能重疊相交的多邊形，在這一點上，該算法采用重迭軸對齊包圍盒，如圖4所示。

圖4 重迭軸對齊包圍盒篩選過程Fig.4 Polygon filtering using AABBs and OAABB

當且僅當AABBS與OAABBA相交，兩個多邊形才可能碰撞。如果沒有相交，那么相應的多邊形過濾出來。循環的最后，篩選出相交的多邊形，即得到了最終的碰撞檢測結果，實施這一步驟程序結構如下：

4 實例分析

對如圖5所示的結構，采用傳統包圍盒算法和交迭軸包圍盒算法進行比較分析。

從圖5所示的信息化模型中提取表面信息和細化相互獨立的表面，將獨立的表面和與它們相對應的多邊形數據存儲在一個結構環境中。

圖5 典型實例Fig.5 The key case study scenario

表1是在執行實例的裝配過程中，通過程序反饋給出的各項監測數據。表1表明交迭軸包圍盒算法比傳統包圍盒算法更快速，相差一個數量級。其根本原因在于交迭軸包圍盒算法比傳統包圍盒算法減少軸對齊包圍盒和三角形測試的數目。

表1 交迭軸包圍盒算法與傳統包圍盒算法結果對比Tab.1 Results for the surface collision detection algorithm supported by the OAABBs compared to the“Brute Force” approach

5 結論

交迭軸包圍盒算法是一種快速碰撞檢測算法，確定在虛擬裝配環境中三維裝配模型表面的精確碰撞。該方法OAABBs過濾掉那些不會相交的元素，具有高度的并行性、快捷性，提高了虛擬裝配的仿真性能。尤其對復雜機電系統而言，提高其仿真運行的速度，具有非常重要的意義。

[1]潘振寬，崔樹娟.基于層次包圍盒的碰撞檢測方法[J].青島大學學報，2005，18(1)：71-76.

[2]鄒益勝，丁國富.實時碰撞檢測算法綜述[J].計算機應用研究，2008，25(1)：8-12.

[3]王志強，洪嘉振，楊輝.碰撞檢測問題研究綜述[J].軟件學報，1999，10(5)：545-551.

[4]陳學文，丑武勝，劉靜華，等.基于包圍盒的碰撞檢測算法研究[J].計算機工程與應用，2005，41(5)：46-50.

[5]李芙玲，張瑾.碰撞檢測技術研究[J].華北科技學院學報，2006，2(1)：71-73.