基于主成分分析法的碰撞檢測算法

李荀 李孔清 王嘉

摘要：基于主成分分析法，提出了一種新的碰撞檢測算法。該算法利用降維的思想將多個成分轉(zhuǎn)化為少數(shù)幾個成分作為主成分，將研究對象的主成分作為法向量來構(gòu)建K-DOP包圍盒。同時通過對案例進(jìn)行分析，發(fā)現(xiàn)在8-DOP的基礎(chǔ)上增加兩個基于主成分的法向量所構(gòu)建成的12-DOP包圍盒能明顯提高碰撞檢測的精度。

關(guān)鍵詞：碰撞檢測；主成分分析；K-DOP；包圍盒；案例分析

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2019）05-0230-04

Collision Detection Algorithm based on Principal Component Analysis

LI Xun， LI Kong-qing*， WANG Jia

（School of Civil Engineering， Hunan University of Science and Technology， Xiangtan 411201， China）

Abstract： Based on the principal component analysis method， a new collision detection algorithm is proposed. The algorithm uses the thought of dimensionality reduction to transform several components into a few components as the principal component， and constructs the K-DOP bounding box by the principal component of the study object as a normal vector. At the same time， by analyzing the case， it is found that the 12-DOP bounding box，which is constructed by adding two legal vectors based on the principal component on the basis of 8-DOP， can obviously improve the accuracy of the collision detection.

Key words： Collision detection； Principal component analysis； K-DOP； Bounding box； Case analysis

建筑領(lǐng)域由于各專業(yè)之間信息的不對稱性，常常導(dǎo)致發(fā)生管線碰撞的情況[1]。而BIM技術(shù)將建設(shè)、設(shè)計、施工和監(jiān)理單位等項(xiàng)目參與方放到同一平臺上，利用BIM中的碰撞檢測軟件可及早發(fā)現(xiàn)問題，避免潛在的碰撞，從而減少返工，節(jié)省人力物力。BIM技術(shù)的一個重要功能與應(yīng)用就是碰撞檢測[2]。當(dāng)結(jié)構(gòu)、機(jī)電、暖通等專業(yè)完成建模后，將所有模型都導(dǎo)入到碰撞檢測軟件（如Navisworks和Solibri等）中進(jìn)行碰撞檢測，可以提前預(yù)測和避免潛在的碰撞問題。碰撞檢測分為硬碰撞和軟碰撞兩種。硬碰撞指的是實(shí)物之間的碰撞，比如風(fēng)管與水管之間的管線碰撞等；軟碰撞指的是實(shí)體與實(shí)體之間沒有碰撞，但是安裝空間不夠或者管道之間的距離不符合要求等[3]。應(yīng)用該技術(shù)，可以提高設(shè)計的質(zhì)量和加快施工進(jìn)度，并且對于后期的物業(yè)管理也大有益處。綜上所述，BIM中的碰撞檢測算法有重要的研究意義。本論文將針對BIM系統(tǒng)中的碰撞檢測算法進(jìn)行研究，以期提高碰撞檢測的精度。

碰撞檢測算法總的可以分為兩類：一類是靜態(tài)碰撞檢測算法；另一類是動態(tài)碰撞檢測算法[4]。動態(tài)碰撞檢測算法主要分為空間分割法和層次包圍盒法。層次包圍盒法又可分為AABB、包圍球、OBB和K-DOP包圍盒[5]。傳統(tǒng)檢測方法通過層次包圍盒技術(shù)來快速剔除不會發(fā)生碰撞的物體。首先檢測兩包圍盒是否相交，相交后再詳細(xì)檢測包圍盒之間的重疊部分，從而判斷出物體之間是否碰撞[6]。

筆者在選用8-DOP包圍盒來包圍模型，然后用VC++編程來檢測模型間是否碰撞時發(fā)現(xiàn)會出現(xiàn)檢測失效的情況，即兩模型原本不碰撞，卻檢測出碰撞。究其原因是該類算法采用預(yù)先給定的軸方向來構(gòu)造包圍盒。若物體的外形頂點(diǎn)分布方向嚴(yán)重偏離給定的方向，則很容易導(dǎo)致構(gòu)造的包圍盒過大，不夠緊致，容易導(dǎo)致誤判。為了克服固定軸的缺點(diǎn)，本文擬通過對頂點(diǎn)的分布做主成分分析，構(gòu)造出動態(tài)的方向軸，最終固定軸與動態(tài)軸相結(jié)合，從而達(dá)到減少碰撞誤判的可能。

1 新的碰撞檢測算法的提出

1.1 包圍盒類型選擇

通過對包圍盒類型的了解[7～10]，各包圍盒之間碰撞檢測算法的優(yōu)劣性如表1所示。

表1 包圍盒碰撞檢測算法比較

在包圍盒類型的選擇上，兩個重要的標(biāo)準(zhǔn)是緊密性和簡單性[11]。從表1中可以看出，包圍球和AABB的緊密性均不夠好，緊密性比較好的是K-DOP和OBB。從其他方面來看，K-DOP的簡單性要優(yōu)于OBB，并且占用內(nèi)存也相對較少。因此，本文選用K-DOP包圍盒算法作為研究的基礎(chǔ)和出發(fā)點(diǎn)。為簡單起見，本文的檢測是在二維的條件下實(shí)現(xiàn)的，因此，8-DOP的4個法向量分別為：（1，1，0）、（-1，1，0）、（1，0，0）、（0，1，0）。對三維問題來說，算法依然適用，只是軸向量數(shù)量增加。

1.2 基于主成分分析法的包圍盒算法

基于主成分分析法的包圍盒算法是利用主成分分析法[12]的思想，找到被包圍體的幾個主成分作為法向量，與原有法向量（1，0，0）、（0，1，0）、（1，1，0）、（-1，1，0）相結(jié)合使包圍體更加緊密。

關(guān)于總體主成分有如下結(jié)論：

設(shè)[∑]是[X=（X1，X2，???，Xp）T]的協(xié)方差矩陣，[∑]的特征值為[λ1≥λ2≥???λp≥0]，相應(yīng)的正交單位化特征向量為[e1，e2，???，ep]，則[X]的第i個主成分可寫為：

[Yi=eTiX=ei1X1+ei2X2+???+eipXp，i=1，2，???，p] （1）

其中[ei=（ei1，ei2，???，eip）T]。這時可得到：

[Var（Yi）=eTi∑ei=λieTiei=λi，i=1，2，???，p，Cov（Yi，Yk）=eTi∑ek=λkeTiek=0，i≠k.] （2）

一般地，如果[P=（e1，e2，???，ep）]，則[P]為一正交矩陣，并且[PT∑P=∧=Diag（λ1，λ2，???，λp）]，其中[Diag（λ1，λ2，???，λp）]為對角矩陣。

設(shè)[li=（li1，li2，???，lip）T（i=1，2，???，p）]為[p]個常數(shù)向量，設(shè)[Y1=lT1X]為[X]的第一主成分，其中滿足條件[lT1l1=1]。令：

[z1=（z11，z12，???，z1p）T=PTl1] （3）

則得到：

[Var（Y1）=lT1∑l1=zT1PT∑Pz1=λ1z211+λ2z212+???+λpz21p≤λ1zT1z1=λ1lT1PPTl1=λ1] （4）

并且當(dāng)[z1=（1，0，???，0）T]時，等號成立。這時，

[l1=Pz1=e1] （5）

由此可知，在滿足條件[lT1l1=1]時，當(dāng)[l1=e1]時，[Var（Y1）]達(dá)到最大，且

[maxlT1l1=1Var（Y1）=Var（eT1X）=eT1∑e1=λ1] （6）

如果[Y2=lT2X]為[X]的第二主成分，則有[lT2l2=1]并且[Cov（Y2，Y1）=lT2∑e1=λ1lT2e1=0]。即得到[lT2l2=1]和[lT2e1=0]。

令：

[z2=（z21，z22，???，z2p）T=PTl2] （7）

則可得到：

[lT2e1=zT2PTe1=z21eT1e1+z22eT2e1+???+z2peTpe1=z21=0] （8）

因此

[Var（Y2）=l2T∑l2=z2TPT∑PTz2=z2T∧z2 =λ2z222+???+λPz2p2 ≤λ2z2Tz2=λ2l2Tl2=λ2] （9）

并且當(dāng)[z2=（0，1，0，???，0）T]，也就是[l2=Pz2=e2]時，[Var（Y2）=λ2]。由此可知，當(dāng)[l2=e2]時，滿足條件[lT2l2=1]，[Cov（Y2，Y1）=0]并且使[Var（Y2）=λ2]達(dá)到最大值。

同理可證，對所有的p個主成分，上述結(jié)論均成立。

通過以上結(jié)論可知，若要求出X的各主成分，需要求出其協(xié)方差矩陣[∑]的各特征值及各特征值對應(yīng)的正交單位化后的特征向量。然后按特征值由大到小將特征向量排序，即線性組合[X1，X2，???，Xp]分別稱為X的第一，第二，…，第p個主成分，特征值對應(yīng)各主成分的方差。兩個物體碰撞檢測時，增加的兩個法向量就是兩個物體各自的主成分。

2 碰撞檢測算例與分析

由于K-DOP的緊密性隨著K值的增大而愈緊密，因此針對傳統(tǒng)檢測方法中出現(xiàn)的實(shí)際不碰撞，檢測結(jié)果卻碰撞的檢測失效情況，采用增加2個法向量的方法來優(yōu)化8-DOP。增加的這兩個法向量確定如下：首先是利用主成分分析法，分別計算得到兩個對象的主成分作為法向量來構(gòu)建12-DOP；其次是增加（1，0.57735，0）和（1，-1.73205，0）這兩個確定的法向量，即30°與-60°坐標(biāo)軸來構(gòu)建12-DOP。

2.1 兩種優(yōu)化方法檢測比較

對于兩種增加法向量所構(gòu)建的12-DOP包圍盒算法來進(jìn)行檢測比較，通過下面五個算例來進(jìn)行說明，如圖1所示，其中包圍對象的坐標(biāo)已在圖中列出，黑色實(shí)線代表包圍對象，紅色虛線代表增加了主成分法向量的12-DOP包圍盒，黑色虛線代表增加了固定法向量的12-DOP包圍盒。

通過VC++編程來檢測兩個對象碰撞與否，最終得到16-DOP算法的分析結(jié)果見表4所示。發(fā)現(xiàn)16-DOP與增加了兩個基于主成分的法向量的12-DOP檢測結(jié)果一致。從而驗(yàn)證得到在8-DOP的基礎(chǔ)上增加兩個基于主成分的法向量所構(gòu)建成的12-DOP包圍盒能明顯提高檢測的精度。

3 結(jié)論

1） 針對傳統(tǒng)的K-DOP包圍盒出現(xiàn)檢測失效的情況，提出了基于主成分分析法的碰撞檢測算法。將主成分分析法與碰撞檢測技術(shù)相結(jié)合，能夠使包圍盒更加均勻且緊密地包圍物體，提高檢測精度。

2） 通過分析比較基于主成分分析法的12-DOP包圍盒和基于固定法向量的12-DOP包圍盒，發(fā)現(xiàn)前者所構(gòu)建的包圍盒比后者更加均勻，檢測精度大大提高。

3） 既增加固定法向量又增加基于主成分的法向量所構(gòu)建成16-DOP，通過碰撞檢測算例驗(yàn)證，發(fā)現(xiàn)與單獨(dú)增加兩個主成分的法向量所構(gòu)建的12-DOP包圍盒碰撞檢測結(jié)果一致，從而驗(yàn)證得到在8-DOP的基礎(chǔ)上增加兩個基于主成分的法向量所構(gòu)建成的12-DOP包圍盒能明顯提高檢測的精度。

參考文獻(xiàn)：

[1] 李煜一.基于BIM的綜合管線碰撞檢測研究[D].蘭州：蘭州交通大學(xué)， 2014.

[2] 王咸鋒，黃妙燕.基于BlM技術(shù)的碰撞檢測在地鐵工程中的應(yīng)用研究[J].廣東技術(shù)師范學(xué)院學(xué)報， 2016， 37（11）：33-39.

[3] 劉卡丁，張永成，陳麗娟.基于BIM技術(shù)的地鐵車站管線綜合安裝碰撞分析研究[J].土木工程與管理學(xué)報， 2015（1）：53-58.

[4] 王嘉，李孔清.碰撞檢測算法研究綜述[J].電腦知識與技術(shù)， 2017，13（20）：202-205.

[5] 何水艷.虛擬校園的碰撞檢測研究[D].武漢：華中師范大學(xué)，2006.

[6] 李建波，潘振寬，孫志軍.基于包圍盒與空間分解的碰撞檢測算法[J].計算機(jī)科學(xué)， 2005， 32（6）：155-157.

[7] 宋城虎，閔林，朱琳，等.基于包圍盒和空間分解的碰撞檢測算法[J].計算機(jī)技術(shù)與發(fā)展， 2014， （1）：57-60.

[8] Xing Y S， Liu X P， Xu S P. Efficient collision detection based on AABB trees and sort algorithm[A]. In：IEEE. International Conference on Control and Automation[C]. Xiamen：IEEE ， 2010. 328-332.

[9] 章勤，黃棍，李光明.一種基于OBB的碰撞檢側(cè)算法的改進(jìn)[J].華中科技大學(xué)學(xué)報（自然科學(xué)版）， 2003， 31（l）： 46-48.

[10] Klosowski J T， Held M， Mitchell J S B， et al. Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs[J]. IEEE Transactions on Visualization & Computer Graphics， 1998， 4（1）：21-36.

[11] 魏迎梅.虛擬環(huán)境中碰撞檢測問題的研究[D].長沙：中國人民解放軍國防科學(xué)技術(shù)大學(xué)， 2000.

[12] 張祥國，丁瑞，蔣幸幸.基于主成分分析與熵值法結(jié)合的多元評價模型的研究[J].新教育時代電子雜志：教師版，2017（18）：181.

【通聯(lián)編輯：梁書】