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

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

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

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

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

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

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

T=NuCu+NbCb+NpCp+Cd

(1)

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

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

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

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

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

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

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

2 基于改進OBB的近似凸包自適應(yīng)包圍盒構(gòu)造

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

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

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

(3)

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

基于改進OBB的近似凸包自適應(yīng)包圍盒構(gòu)造流程如圖4所示。

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

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

OjOk

(4)

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

(5)

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

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

(6)

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

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

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

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

3 近似凸包自適應(yīng)包圍盒碰撞檢測

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

3.1 簡化包圍盒樹的存儲結(jié)構(gòu)

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

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

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

3.2 近似凸包自適應(yīng)包圍盒碰撞檢測

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

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

(7)

(8)

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

L≤RA+RB

(9)

(10)

(11)

聯(lián)立式(9)～式(11)可得

(12)

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

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

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

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

4 虛擬裝配實例驗證

4.1 交互場景設(shè)計

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

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

4.2 抓取規(guī)則設(shè)計

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

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

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

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

4.3 包圍盒碰撞檢測設(shè)計

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

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

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

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

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

4.4 實驗對比分析

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

表3 實驗數(shù)據(jù)對比結(jié)果Table 3 Experimental data comparison results

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

5 結(jié)論

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

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

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

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

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