李荀 李孔清 王嘉

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

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

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

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

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

1 新的碰撞檢測(cè)算法的提出

1.1 包圍盒類型選擇

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

表1 包圍盒碰撞檢測(cè)算法比較

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

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

基于主成分分析法的包圍盒算法是利用主成分分析法[12]的思想，找到被包圍體的幾個(gè)主成分作為法向量，與原有法向量（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個(gè)主成分可寫(xiě)為：

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

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

[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）]為對(duì)角矩陣。

設(shè)[li=（li1，li2，???，lip）T（i=1，2，???，p）]為[p]個(gè)常數(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]時(shí)，等號(hào)成立。這時(shí)，

[l1=Pz1=e1] （5）

由此可知，在滿足條件[lT1l1=1]時(shí)，當(dāng)[l1=e1]時(shí)，[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]時(shí)，[Var（Y2）=λ2]。由此可知，當(dāng)[l2=e2]時(shí)，滿足條件[lT2l2=1]，[Cov（Y2，Y1）=0]并且使[Var（Y2）=λ2]達(dá)到最大值。

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

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

2 碰撞檢測(cè)算例與分析

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

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

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

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

3 結(jié)論

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7] 宋城虎，閔林，朱琳，等.基于包圍盒和空間分解的碰撞檢測(cè)算法[J].計(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é)報(bào)（自然科學(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)境中碰撞檢測(cè)問(wèn)題的研究[D].長(zhǎng)沙：中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué)， 2000.

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

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