近似凸包自適應包圍盒碰撞檢測方法

趙迪, 王熊錦, 陳果, 蔡光銳

(湖北工業大學機械工程學院, 武漢 430068)

近年來,虛擬現實技術飛速發展,因其在虛擬環境中對現實場景的高度還原和再現,結合工業產品的結構特點和實際裝配需求,可以將虛擬現實技術與產品制造裝配結合,形成虛擬裝配技術[1]。在零件數量多且復雜的裝配場景中,傳統的碰撞檢測算法存在精度差和檢測效率低的問題,不能滿足用戶的沉浸感和真實感。因此如何提高碰撞檢測精度和碰撞檢測效率是虛擬裝配中需要解決的重要問題。

層次包圍盒法是碰撞檢測最常用的方法。通過構造特定的包圍盒包圍待測對象,對包圍盒間進行相交測試來判斷對象之間是否發生碰撞[2],故包圍盒構造是影響碰撞檢測效果的重要因素。常用的包圍盒主要有球形包圍盒(Sphere)、軸對齊包圍盒(axis-aligned bounding box, AABB)和方向包圍盒(oriented bounding box, OBB)等[3]。它們在構造性、包圍緊密性、相交測試效率等方面都有各自特點,如球形包圍盒構造簡單、相交測試快速,但包圍緊密性差,因此適用于檢測精度不高的場合。AABB包圍盒比球形包圍盒緊密性好,但僅適用于規則幾何對象,當不規則幾何對象發生旋轉時,包圍盒無法相應旋轉,因此會產生冗余空間,降低包圍緊密性[4]。OBB包圍盒相比AABB包圍盒的構造和相交測試復雜,但OBB包圍盒具有方向任意性,能根據幾何對象的形狀特點盡可能緊密的包圍對象,具有很好的適用性、穩定性,在零件多且結構復雜的虛擬裝配場景中應用廣泛。

對傳統OBB包圍盒構造算法進行分析[5-7],發現距離對象中心點較近的點集對OBB包圍盒的方向影響不大,應用于外形存在弧面等不規則對象時,會產生較大的冗余空間,增加冗余計算時間,從而降低碰撞檢測精度和效率。為了解決該問題,現基于改進OBB的近似凸包自適應包圍盒構造算法(approximate convex OBB, ACO),并將該算法應用于本文提出的分層碰撞檢測方法中的精檢測階段,以期通過減少計算包圍盒的頂點數量加快包圍盒的構造時間,構造出更加緊密的包圍盒從而提高碰撞檢測的精度和效率。

1 包圍盒分層碰撞檢測方法

碰撞檢測性能量化指標[8]通常定義為碰撞檢測階段的時間消耗,為了適應接觸過程中的物體干涉,定義碰撞檢測的時間消耗為

T=NuCu+NbCb+NpCp+Cd

(1)

式(1)中:T為碰撞檢測消耗的總時間;Nu為需要重構包圍盒數目;Nb為碰撞檢測的包圍盒數;Np為碰撞檢測的幾何元素對數;Cu為單個包圍盒更新消耗的時間;Cb為每對包圍盒碰撞檢測消耗的時間;Cp為每對幾何元素碰撞檢測消耗的時間;Cd為當對象發生變形的情況下更新包圍盒數目消耗的時間。

從式(1)中可以看出,如果要降低Nu數量,需要盡可能構造緊密性好的包圍盒。若要減小Cu、Cb、Cp,則需要盡可能選擇計算簡捷的包圍盒和高效的相交測試。在物體明顯不相交的情況下,如果采用精細構造方法會造成不必要的計算,因此本文提出一種分層碰撞檢測方法,將整個檢測過程分為粗檢測階段和精檢測階段,如圖1所示。

圖1 分層碰撞檢測方法Fig.1 Layered collision detection method

首先通過基于八叉樹的球形包圍盒對虛擬場景中任意兩個對象Ai、Aj進行粗檢測,判斷兩個包圍盒之間的距離dij與半徑(Ri+Rj)的關系,初步省略明顯不發生碰撞的對象,降低Cu的值。其次通過本文研究的基于改進OBB的近似凸包自適應包圍盒構造算法,對可能發生碰撞的對象進行精確碰撞檢測,盡可能降低Nb和Np。對根節點BTi、BTj進行相交檢測,如果根節點相交,則逐級遍歷包圍盒樹的子節點,并通過分離軸理論[9]判斷是否相交,否則更新虛擬場景退出檢測,最后直接對葉子節點中的幾何元素進行相交檢測。

為提高粗檢測階段的效率,采用基于八叉樹的球形模型進行包圍盒的構造和碰撞檢測,結合八叉樹快速剖分空間結構[10]和球形包圍盒兩種方法的優勢,構建基于八叉樹的球形模型結構。球形包圍盒沿八叉樹結構不斷劃分成8個子球體,可加快空間剖分速度并減少計算量[11],基于八叉樹的球形模型如圖2所示。

圖2 基于八叉樹的球形模型Fig.2 Spherical model based on octree

基于上述八叉樹的球形模型計算出待測對象的子節點,根據兩子節點間球心距和兩子節點半徑和的大小來判斷子節點是否相交完成,此外還需對當下葉子節點中所含幾何元素構造緊密性更好的包圍盒,以便作進一步精確檢測。

2 基于改進OBB的近似凸包自適應包圍盒構造

如上所述,在粗檢測中若兩個對象的子節點相交則會進入精檢測階段,本節主要針對精檢測階段采用傳統OBB包圍盒存在冗余空間大、檢測效率低的問題進行改進。

虛擬環境中的三維模型是由很多個三角面片構成的,其中一級圓柱齒輪減速器上蓋的三角面片模型如圖3所示。

傳統OBB包圍盒不考慮凸包模型的影響,計算的中心位置是所有幾何元素三角形面片各頂點的平均值。若模型表面存在弧面時,會導致每個三角形面片的尺寸不均勻,所構成的包圍盒會向尺寸小而緊密的部位偏移,產生較大的冗余空間,增加不必要的計算時間,從而降低碰撞檢測精度及效率。為了減少因三角形面片的尺寸不均勻對于構造包圍盒方向的影響,采用材料力學中的形心計算方法,基于三角形面積加權法確定包圍盒中心點O,由此來確定頂點集的協方差矩陣,使得包圍盒更加緊密地包圍在凸面模型上,即

(3)

式(3)中:οi、Si為第i個三角面片的中心點和表面積。

基于改進OBB的近似凸包自適應包圍盒構造流程如圖4所示。

圖4 基于改進OBB的近似凸包自適應包圍盒構造流程Fig.4 Construction process of approximate convex hull adaptive bounding box based on improved OBB

設待測物體由n個基本幾何元素三角形構成,根據式(4)計算頂點集S′的協方差矩陣C。

OjOk

(4)

協方差矩陣C是3×3的對稱矩陣,其3個特征向量β1、β2、β3是正交的,進行歸一化如下:

(5)

式(5)中:η1、η2、η3為包圍盒的3個軸向量,用來確定方向。

包圍盒的大小根據式(6)計算投影長度l1、l2、l3的最大值,所有元素在xyz坐標軸方向上投影的最大值和最小值分別為Fxmax、Fxmin、Fymax、Fymin、Fzmax、Fzmin。

(6)

只需要15個浮點數來確定OBB包圍盒的大小和方向,其中9個浮點數確定方向,6個浮點數確定大小。

以一級圓柱齒輪減速器上蓋模型為例,使用本文方法計算的體積為11 260.653 cm3,傳統OBB法計算的體積為13 372.025 cm3。采用基于改進OBB的近似凸包自適應包圍盒更加緊密,補償了傳統OBB包圍盒引起的方向偏差和冗余空間,傳統與改進后的OBB包圍盒如圖5所示。

圖5 傳統與改進后的OBB包圍盒Fig.5 Traditional and improved OBB bounding boxes

分析上述兩種包圍盒算法構造時間,如表1所示。從表1可以看出,采用基于改進OBB的近似凸包自適應包圍盒構造算法,構造時間縮短約66%,有效降低Nu的值。

3 近似凸包自適應包圍盒碰撞檢測

精檢測階段構造出更加緊密的近似凸包自適應包圍盒。為了縮短精確碰撞檢測階段計算的時間,可以通過簡化包圍盒樹的存儲結構加快幾何元素間的相交測試速率,并采用分離軸方法進行包圍盒之間的相交測試,完成碰撞檢測。

3.1 簡化包圍盒樹的存儲結構

大量的三角形面片參數在計算過程中會占用存儲空間[11]。為減少重疊的測試,通過去除葉子節點的包圍盒,將葉子節點的三角形信息存儲在父節點中,直接進行幾何元素三角形之間的相交測試,包圍盒樹存儲結構簡化前后對比如圖6所示,最大程度地減少層次包圍盒樹(BVH Tree)的節點數,提高相交測試的速率,降低Np值。

圖6 包圍盒樹存儲結構簡化前后對比Fig.6 Compare the bounding box tree storage structure before and after simplification

從以上分析可以看出,利用二叉樹建立的具有N個葉子節點的包圍盒樹,其存儲的節點數為 (2N-1)。當刪除葉子節點時,只需要存儲(N-1)個節點,減少了將近一半節點,不僅改善了包圍盒的存儲結構,而且大大減少了待測節點的數量。

3.2 近似凸包自適應包圍盒碰撞檢測

在精確檢測階段中,對任意兩個物體進行精確檢測時,分別遍歷其OBB樹,采用分離軸方法進行包圍盒之間的相交測試。

圖7 分離軸碰撞測試Fig.7 Separating axis crash tests

(7)

(8)

判斷兩個包圍盒是否發生碰撞,只需要比較正交邊投影長的一半與兩個中心點連線投影的長度。如果滿足式(9),則表示兩個包圍盒發生碰撞,不滿足則不發生碰撞。

L≤RA+RB

(9)

(10)

(11)

聯立式(9)～式(11)可得

(12)

事實上,只需要測試包圍盒A的3根方向軸、包圍盒B的3根方向軸、9根與A、B包圍盒的軸向相垂直的軸,即15根可作為分離軸的軸。如果15根分離軸不能將這兩個包圍盒分開,則它們是相交的。

選取不同數量三角面數為測定模型進行碰撞檢測,通過坐標定位保證每次碰撞檢測為相同位置,分別用基于改進OBB的近似凸包自適應包圍盒算法和傳統OBB包圍盒算法進行碰撞檢測,碰撞檢測時間如圖8所示。

圖8 兩種包圍盒碰撞檢測方法時間對比Fig.8 Time comparison of two bounding box collision detection methods

從圖8可以看出,采用基于改進OBB近似凸包自適應包圍盒碰撞檢測時間更短,較傳統OBB包圍盒碰撞檢測時間縮短約37%,有效降低Cb、Cp的值,隨著三角面片數不斷增加,兩種包圍盒碰撞檢測所用的時間差不斷增大,在這種情況下采用改進OBB近似凸包自適應包圍盒算法更具有優勢。

4 虛擬裝配實例驗證

4.1 交互場景設計

交互場景框架設計如圖9所示,設計應用虛擬裝配的改進OBB近似凸包自適應包圍盒碰撞檢測算法,對比傳統OBB包圍盒算法的構造包圍盒時間和碰撞檢測時間。使用體感交互設備Leap Motion獲取操作者的手部動作,映射虛擬手抓取零件進行虛擬裝配,在Unity3D虛擬現實開發引擎中構建液壓調平舉升平臺各部件虛擬裝配場景,設計實例驗證算法的可行性。

圖9 交互場景框圖Fig.9 Interactive scene diagram

4.2 抓取規則設計

抓取物體時至少需要兩根手指才能完成,通常是用食指和大拇指,Leap Motion識別食指手勢較穩定[12]。虛擬手在抓取和釋放物體的不同狀態可以通過觸發手指的根數來指定,虛擬手抓取過程如圖10所示。

圖10 虛擬手抓取過程Fig.10 Virtual hand grasp process

定義集合表示虛擬手抓取物體時的交互狀態,G={grabbing,grabbed,releasing,released},各狀態需要滿足的部分條件如表2所示。

表2 各狀態需滿足的部分條件Table 2 Partial conditions to be met by each state

4.3 包圍盒碰撞檢測設計

基于上述研究方法,操作者在搭建好的虛擬環境中進行裝配應用實驗,首先給零件添加基于改進OBB的近似凸包自適應包圍盒,當抓取不同類型的零件時,系統通過Leap Motion獲取操作者手勢信息,映射虛擬手且滿足虛擬手抓取規則即可穩定抓取零件。在Unity3D虛擬場景中定義錨定(Anchor)機制將零件安裝到與之匹配的位置,提前將待裝配零件與錨定點建立關聯。裝配過程中,當零件包圍盒觸碰到錨定點發生碰撞檢測,如果是不匹配的零件,錨點位置不會出現高亮顯示的零件提示,若釋放零部件,也不會自動吸附到該位置。如果確實為這一步待裝配的零件,會出現文字提示且零件表面會變為高亮色,虛擬手即可直觀地實現抓取和裝配零件操作,裝配操作示例如圖11所示。

圖11 裝配操作示例Fig.11 Example of assembly operation

分別采用傳統OBB包圍盒和基于改進OBB的近似凸包自適應包圍盒進行碰撞檢測如圖12所示。

圖12 傳統OBB與近似凸包包圍盒碰撞檢測Fig.12 Collision detection between traditional OBB and approximate convex hull bounding box

可以看出當采用傳統OBB包圍盒,零件明顯還未碰到裝配錨點,就觸發碰撞檢測。而采用本文提出的基于改進OBB的近似凸包自適應包圍盒,零件精確地碰到裝配位置才會觸發碰撞檢測,同時錨點位置顯示高亮,符合使用者實時的自然交互習慣。

4.4 實驗對比分析

為了驗證本文采用的基于改進OBB的近似凸包自適應包圍盒算法(ACO)在虛擬裝配中的應用優勢,分別將本文算法(ACO)、基于傳統OBB包圍盒算法、基于AABB包圍盒算法應用到液壓調平舉升平臺和一級圓柱齒輪減速器裝配實驗中。即采用3種不同的算法完成兩組復雜度不同的裝配實驗,每次實驗所用的時間記為實驗執行時間如表3所示。

表3 實驗數據對比結果Table 3 Experimental data comparison results

由表3可以看出,本文采用的基于改進OBB近似凸包自適應包圍盒算法進行同一復雜度的裝配實驗耗時最短,在實驗執行時間上比傳統OBB包圍盒算法加快了22.2%,比常用的AABB包圍盒算法加快了17.4%。簡化包圍盒的層次結構和改進OBB包圍盒的構造可以加快相交測試的速度,兩種優化操作結合起來使得在存儲空間和碰撞檢測效率上達到了平衡,提高了虛擬裝配的效率。

5 結論

針對虛擬裝配應用中,基于包圍盒碰撞檢測算法存在的準確性差和檢測效率低的問題,設計了粗精結合的分層檢測方法,重點研究了基于改進OBB近似凸包自適應包圍盒構造算法,最后進行了實例驗證。得出如下結論。

(1)設計了分層碰撞檢測方法。將整個檢測階段分為粗檢測和精檢測階段。通過基于八叉樹的球形包圍盒進行粗檢測,初步省略明顯不發生碰撞的對象,減少不必要的相交測試計算。

(2)改進了傳統OBB包圍盒因三角形面片的尺寸不均勻導致構造包圍盒方向偏移的問題,提出一種基于改進OBB近似凸包自適應包圍盒構造算法,并應用于分層碰撞法中的精檢測階段,補償了傳統OBB包圍盒因方向偏差產生的冗余空間。改進的OBB包圍盒與傳統的OBB包圍盒算法相比,構造時間縮短約66%,碰撞檢測時間縮短約37%。

(3)設計虛擬裝配交互實驗并進行實例驗證。實驗表明采用的改進OBB近似凸包自適應包圍盒算法在效率上較傳統OBB包圍盒碰撞檢測算法加快了22.2%,較常用的AABB包圍盒碰撞檢測算法加快了17.4%,且三角面片數越多效果越明顯。

本文提出的算法可以滿足虛擬裝配中多物體碰撞檢測效率高的要求,對于設計虛擬裝配的包圍盒算法應用具有參考價值。