虛擬裝配系統(tǒng)中一種快速碰撞檢測方法

李秀莉，張樹仁

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

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

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

在三維環(huán)境中尋找碰撞是非?？量痰娜蝿铡ふ遗鲎矔r間占總運行時間的50%。對于復雜機電系統(tǒng)，三維虛擬原型是非常復雜的，含有成千上萬的元素。為此，本文提出了一種能夠快速、準確檢測碰撞的交迭軸包圍盒碰撞檢測算法。

1 表面碰撞檢測算法原理

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

圖1 表面碰撞檢測算法體系結(jié)構(gòu)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)。實施這一步驟程序結(jié)構(gòu)如下：

3 多邊形相交管理程序

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

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

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

4 實例分析

對如圖5所示的結(jié)構(gòu)，采用傳統(tǒng)包圍盒算法和交迭軸包圍盒算法進行比較分析。

從圖5所示的信息化模型中提取表面信息和細化相互獨立的表面，將獨立的表面和與它們相對應的多邊形數(shù)據(jù)存儲在一個結(jié)構(gòu)環(huán)境中。

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

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

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

5 結(jié)論

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

[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]李芙玲，張瑾.碰撞檢測技術(shù)研究[J].華北科技學院學報，2006，2(1)：71-73.