王雪琪，趙文政

（上海理工大學(xué)機(jī)械工程學(xué)院，上海 200093）

0 引言

經(jīng)歷數(shù)十年的高速發(fā)展，汽車工業(yè)已然成為推動國民經(jīng)濟(jì)高質(zhì)量發(fā)展的重要支柱，我國也成為最大的汽車生產(chǎn)國與消費(fèi)國。然而，自主品牌和自有技術(shù)存在的短板阻礙了我國制造業(yè)從“制造”向“智造”轉(zhuǎn)型的步伐。

在汽車行業(yè)，車身制造質(zhì)量不僅影響消費(fèi)者的主觀評價，還對制造過程綜合成本控制、汽車使用性能提升等方面起到?jīng)Q定性作用。我國自主品牌的乘用車制造行業(yè)起步較晚，車身綜合尺寸偏差往往大于5mm，而歐美、日、韓等汽車制造強(qiáng)國的綜合尺寸偏差控制在1.5～3.5mm 之間，明顯優(yōu)于我國自主品牌的車身制造質(zhì)量，導(dǎo)致國產(chǎn)乘用車市場占有率低、產(chǎn)品競爭力弱。

三坐標(biāo)測量機(jī)因其高精度、柔性測量等特點(diǎn)成為白車身、車門系統(tǒng)、底板總成等關(guān)鍵零部件與整車檢測的首選，但由于三坐標(biāo)測量機(jī)在運(yùn)動過程中一旦發(fā)生碰撞時，首先需要進(jìn)行碰撞檢測，并按照之前設(shè)定的避障策略添加空間移動點(diǎn)，以獲取無碰撞的局部檢測路徑。因此，局部檢測路徑的規(guī)劃結(jié)果是影響全局檢測路徑規(guī)劃質(zhì)量的最重要因素，關(guān)鍵在于研究高效、準(zhǔn)確的碰撞檢測算法與通用的避障策略。

目前，碰撞檢測可分為靜態(tài)碰撞檢測和動態(tài)碰撞檢測［1］。其中，靜態(tài)碰撞檢測算法多用于凸多邊形的碰撞檢測，針對凹多邊形可先將其分解成多個凸邊形后，再進(jìn)行碰撞檢測。這種方法主要用于研究靜止?fàn)顟B(tài)下物體是否發(fā)生干涉，檢測精度要求較高。Uchiki 等［2］提出了一種空間占有法的碰撞檢測方法，能夠快速、準(zhǔn)確檢測三維空間中自由物體之間的碰撞。申靜波等［3］基于現(xiàn)有的相交檢測算法提出了基于夾邊邊對的空間平面凸多邊形快速相交檢測方法。然而，現(xiàn)有靜態(tài)碰撞檢測多適用于檢測凸多邊形碰撞，對于凹多邊形的碰撞檢測只能先將其分解為多個凸多邊形后再進(jìn)行碰撞檢測，因此增加了三坐標(biāo)靜態(tài)碰撞檢測算法的計(jì)算時間，效率較低。

動態(tài)碰撞檢測則主要研究物體運(yùn)動過程中是否發(fā)生碰撞，被廣泛運(yùn)用于三維游戲等虛擬現(xiàn)實(shí)中，又可細(xì)分為離散碰撞檢測和連續(xù)碰撞檢測。

離散碰撞檢測是將物體的運(yùn)動軌跡按照一定步長離散化，并分別對每一段進(jìn)行碰撞檢測，代表方法包括層次包圍盒法［4］和空間分割［5］。Alvarez 等［6］基于零件離散化的三角形面片，應(yīng)用空間劃分技術(shù)（K-dimensional tree，Kdtree）減少測頭與零件之間的交叉試驗(yàn)次數(shù)。Dong 等［7］使用軸向包圍盒法（Aixe Align Bounding Box，AABB）進(jìn)行碰撞檢測。Tang等［8］利用非均勻有理B樣條曲面對被測物體進(jìn)行三角劃分，再利用分離軸定理實(shí)現(xiàn)碰撞檢測，提高了檢測效率與準(zhǔn)確度。Han 等［9］基于空間分割法求解測頭運(yùn)動直線軌跡與被測物體所在空間的交集，再利用RE-OP 算法對碰撞路徑進(jìn)行優(yōu)化。上述離散碰撞檢測均能快速進(jìn)行碰撞判別，但會因步長影響無法完全保證檢測準(zhǔn)確性。

連續(xù)碰撞檢測算法通過對物體移動過程中掃過的空間進(jìn)行建模，進(jìn)而實(shí)現(xiàn)碰撞判定。代表方法包括基于掃描實(shí)體的算法［10-11］、保守前進(jìn)算法及其改進(jìn)算法［12］、基于GJK 的算法［13-15］、射線追蹤法［16-17］等。Albuquerque 等［18］利用射線跟蹤技術(shù)確定檢測點(diǎn)與目標(biāo)點(diǎn)之間在運(yùn)動過程中是否與三棱柱發(fā)生碰撞。Buchal 等［19］在網(wǎng)格構(gòu)建過程中，基于圖像沖突檢測方法對每一特征進(jìn)行碰撞檢測。Lu等［20］將改進(jìn)的三維射線追蹤法應(yīng)用于坐標(biāo)測量機(jī)所在空間的八叉樹中，以檢測任意兩特征間的障礙物。張應(yīng)中等［15］提出適用于簡單凸體之間的線性連續(xù)碰撞檢測算法。然而，在連續(xù)碰撞檢測中仍存在檢測速度慢的問題［21-23］，且隨著運(yùn)動軌跡復(fù)雜度的增加，環(huán)境空間建模也會隨之變得更加困難。

綜上所述，面對不同應(yīng)用場景，學(xué)者們提出了不同的碰撞檢測算法和改進(jìn)算法以提高檢測效率及準(zhǔn)確度，然而現(xiàn)有碰撞檢測算法仍無法高效解決復(fù)雜環(huán)境下的碰撞檢測問題。例如，面對車身復(fù)雜結(jié)構(gòu)與五軸三坐標(biāo)之間的碰撞檢測，尤其針車身與測頭的連續(xù)運(yùn)動過程的掃掠建模與快速碰撞檢測方面，仍存在碰撞檢測效率低與碰撞檢測精度差等問題。

為了從根本上解決問題，本文提出一種基于GJK（Gilbert Johnson Keerth）的快速連續(xù)碰撞檢測（Fast Continuous Collision Detection）。

1 三坐標(biāo)測量儀碰撞檢測算法

針對現(xiàn)有動態(tài)碰撞檢測算法在車身三坐標(biāo)碰撞檢測應(yīng)用中的不足，對車身進(jìn)行三角面片化，將三坐標(biāo)的測頭、測針、接長桿進(jìn)行層次包圍盒化等處理，實(shí)現(xiàn)對三坐標(biāo)運(yùn)動軌跡所占空間的建模，提出基于OBB 包圍盒（Oriented Bounding Box）和GJK 碰撞檢測相結(jié)合的分級碰撞檢測算法。算法流程如圖1所示。

Fig.1 Dynamic collision detection algorithm flow圖1 動態(tài)碰撞檢測算法流程

由于車身是300～500 個薄板沖壓零件焊接而成的總成件，具有以下特點(diǎn)：①長度和寬度遠(yuǎn)大于厚度；②內(nèi)部存在空腔形態(tài)，且內(nèi)部空腔中存在需要測量的檢測特征；③尺寸較大，曲面結(jié)構(gòu)復(fù)雜。因此，若將車身進(jìn)行包圍處理不僅增加了建模的難度，且建模精度較低。為解決該問題，采用網(wǎng)格化思想，基于曲面曲率變化對車身進(jìn)行三角面片化處理。圖2為三角面片化的車身模型。

Fig.2 Diagram of body in white triangulation圖2 白車身三角面片化示意圖

由于測頭與車身、接長桿與車身之間碰撞檢測是保證CMM 無碰撞路徑最主要的保障，而三坐標(biāo)測量機(jī)是由多個零部件組合而成的實(shí)體，如何合理建模使所構(gòu)造的函數(shù)更簡單、計(jì)算量少、運(yùn)行效率高且模型接近實(shí)體是現(xiàn)階段亟待解決的問題。為此，本文針對三坐標(biāo)測量機(jī)的特點(diǎn)，采用圓柱體及球體對其本體進(jìn)行包絡(luò)，結(jié)合三坐標(biāo)各個關(guān)節(jié)形狀的特點(diǎn)對其進(jìn)行建模，不僅降低了環(huán)境建模的難度，同時提高了模型的精度。圖3 為簡化后三坐標(biāo)機(jī)測頭結(jié)構(gòu)模型。

Fig.3 Simplified model of CMM probe structure圖3 三坐標(biāo)測頭結(jié)構(gòu)簡化模型

1.1 基于空間幾何的靜態(tài)碰撞檢測

三坐標(biāo)路徑規(guī)劃的碰撞檢測可分為靜態(tài)碰撞檢測及動態(tài)碰撞檢測。其中，靜態(tài)碰撞主要為三坐標(biāo)與車身之間的碰撞檢測；動態(tài)碰撞檢測包括運(yùn)動過程中三坐標(biāo)與三坐標(biāo)之間碰撞檢測、三坐標(biāo)與車身之間碰撞檢測兩種。首先將詳細(xì)闡述基于空間幾何距離的靜態(tài)碰撞檢測算法及所提出的基于分級連續(xù)碰撞檢測的動態(tài)碰撞檢測算法。

測頭系統(tǒng)中探針與接長桿可簡化為圓柱體結(jié)構(gòu)，旋轉(zhuǎn)中心可簡化為球體結(jié)構(gòu)。因此，測頭與車身結(jié)構(gòu)的靜態(tài)碰撞探測可轉(zhuǎn)化為篩選點(diǎn)云是否存在于測頭系統(tǒng)所占幾何空間中，對于旋轉(zhuǎn)中心而言，靜態(tài)碰撞探測可以表示為：

其中，（Xj，Yj，Zj）為車身離散化節(jié)點(diǎn)的坐標(biāo)值，（Xo，Yo，Zo）為簡化關(guān)節(jié)中心點(diǎn)坐標(biāo)，Δdq為車身點(diǎn)云節(jié)點(diǎn)到測頭中心點(diǎn)的距離和簡化球體半徑的差值，若Δdq＜0則三坐標(biāo)與車身發(fā)生碰撞，否則不發(fā)生碰撞。

對于探針與接長桿而言，先根據(jù)點(diǎn)云節(jié)點(diǎn)與圓柱體表面點(diǎn)之間的矢量夾角的計(jì)算結(jié)果進(jìn)行粗篩選，再計(jì)算點(diǎn)云節(jié)點(diǎn)與圓柱體軸線見的距離，確定是否存在靜態(tài)碰撞，其判斷過程可表示為：

1.2 基于分級檢測的動態(tài)碰撞檢測算法

CMM 采用的是接觸式測量方式，但測頭在移動過程中大多與車身之間存在逼近距離。針對這一規(guī)律，首先采用包圍盒對測頭結(jié)構(gòu)的運(yùn)動軌跡所占空間進(jìn)行簡化，初步判斷其與車身是否發(fā)生碰撞。

圖4（彩圖掃OSID 碼可見，下同）中橙色曲面表示測頭結(jié)構(gòu)從t0時刻到tend時刻的移動軌跡，青色為測頭結(jié)構(gòu)移動軌跡所占空間的包圍盒?？筛鶕?jù)測頭點(diǎn)云信息得到測頭結(jié)構(gòu)從t0時刻到tend時刻在空間中的位置U（iXi，Yi，Zi）、Li（Xi，Yi，Zi）（i=1，2，...，P），最終通過OBB 包圍盒確定各個節(jié)點(diǎn)的坐標(biāo)值，具體步驟如下：

各測頭中心點(diǎn)的均值為：

根據(jù)式（1）可得到協(xié)方差H：

其中，j，k分別表示所采用的坐標(biāo)分量即x、y、z，1≤j，k≤

通過公式（3）可得到3×3 對稱的協(xié)方差矩陣H，將H的3 個特征向量正交化后即為OBB 的3 條軸方向，最后計(jì)算OBB 內(nèi)各頂點(diǎn)在這3 條軸上的投影最大、最小值即可確定OBB 的3條邊長及各交點(diǎn)的坐標(biāo)。

Fig.4 CMM probe motion modeling based on bounding box method圖4 基于包圍盒法的CMM測頭運(yùn)動建模示意圖

若粗檢測過程中三坐標(biāo)測頭結(jié)構(gòu)與車身發(fā)生碰撞，則進(jìn)一步基于GJK 碰撞檢測算法確定車身與三坐標(biāo)各個關(guān)節(jié)是否發(fā)生碰撞。GJK 模型是一種用來確定兩個凸集之間最短距離是否小于零，從而確定兩物體是否發(fā)生碰撞的方法，相關(guān)基本概念如下：

（1）Q表示三維空間的一個點(diǎn)集，則包含Q的所有凸集的交集稱為Q的凸包（Convex Hull，CH），記為CH（Q）。

（2）如果有A，B兩個點(diǎn)集，令a和b為分別為A和B中的頂點(diǎn)位置，則2 個點(diǎn)集A和B的Minkowski 差可定義為C=A?B=｛a-b：a∈A，b∈B｝，當(dāng)且僅當(dāng)CH（C）包含原點(diǎn)時，則表示凸包A和凸包B發(fā)生碰撞。

（3）對于凸集C內(nèi)沿給定方向v且距離凸集最遠(yuǎn)的點(diǎn)被稱為支撐點(diǎn)，這一過程被稱作支撐映射，可記作Sc（v）。如圖5所示，P點(diǎn)為凸集C沿v方向的支撐點(diǎn)。

Fig.5 Support point P of convex body C on direction v圖5 凸體C在方向v上的支撐點(diǎn)P

設(shè)三坐標(biāo)測頭從t0時刻到tend時刻所形成凸體，記為CTU，即測頭結(jié)構(gòu)在［t0，tend］時間區(qū)間內(nèi)所形成凸體的凸集可由各個邊的節(jié)點(diǎn)表示。車身某處三角面片記為BIW，用D（Cmm，BIW）表示兩凸體之間的距離，則兩者之間的距離可表示為：

設(shè)兩凸體Cmm、BIW之間的Minkowski 差C所構(gòu)成的凸包CSO 與原點(diǎn)之間的最短距離設(shè)置為d，則存在有d(C) ∈C且||d(C)||=min{||x||：x∈C}，CSO中所有頂點(diǎn)集合為W，GJK 算法通過迭代方式計(jì)算CSO 中距離原點(diǎn)最近的點(diǎn)，并保證每次生成的單形體節(jié)點(diǎn)W更接近于原點(diǎn)，記第k次迭代產(chǎn)生形體的頂點(diǎn)集合為Wk。

對于［t0，tend］時間區(qū)間內(nèi)測頭結(jié)構(gòu)所形成的凸體TUT與車身三角面片BIW之間的GJK 算法的碰撞檢測過程：

步驟1：給定初始方向，輸入兩凸體CTU、BIW 之間的Minkowski 差C所形成凸包CSO，其中CSO 中初始頂點(diǎn)集合為W0=?。

步驟2：計(jì)算凸包CSO 與原點(diǎn)之間的最短距離為dk，該點(diǎn)記為vk。

步驟3：若dk為0，則三坐標(biāo)包圍盒與車身發(fā)生碰撞算法結(jié)束；若不為0，則轉(zhuǎn)到步驟3。

步驟4：對于Wk中不包含vk的子單形體，將其頂點(diǎn)從Wk中剔除。

步驟5：沿初始方向負(fù)方向即計(jì)算凸包CSO 沿-vk所在方向的支撐點(diǎn)wk。

步驟6：若‖vk‖2-vkwk≤ε2，則結(jié)束迭代過程，并輸出三坐標(biāo)與車身不相交。若k＞K，則三坐標(biāo)與車身不碰撞；否則k=k+1，將wk加到Wk中并返回步驟1。

步驟7：輸出三坐標(biāo)測頭結(jié)構(gòu)與車身狀態(tài)。

2 實(shí)驗(yàn)及分析

為驗(yàn)證本文算法的有效性和實(shí)時性，建立三維場景復(fù)雜度不同的場景進(jìn)行測試。選取具有兩個大小不同的正方體作為實(shí)驗(yàn)對象，正方體由程序生成，并且每個正方體的移動方向和速度隨機(jī)生成，當(dāng)兩個正方體發(fā)生碰撞時，會顯示碰撞信息，如圖6所示。

Fig.6 Collision detection in the following experimental scenario圖6 實(shí)驗(yàn)場景下的碰撞檢測

在上述研究基礎(chǔ)上，以白車身為例，闡明本文所提出的分級碰撞檢測的有效性，對某型號白車身單一車次內(nèi)所需檢測的關(guān)鍵尺寸特征進(jìn)行碰撞檢測，并與現(xiàn)有方法進(jìn)行比較。

由于側(cè)圍外板的CAD 數(shù)模結(jié)構(gòu)由側(cè)圍外板薄板件、眾多加強(qiáng)件、功能件等多種零件連接而成。因此，在對側(cè)圍外板進(jìn)行測量時，首先將其放置在固定支架小車上并利用夾具進(jìn)行固定，然后將支架小車及側(cè)圍外板件放置于先前設(shè)定好的測量機(jī)的檢測區(qū)域，最后進(jìn)行測量機(jī)校準(zhǔn)、坐標(biāo)系重建及對側(cè)圍外板關(guān)鍵尺寸特征進(jìn)行檢測。

利用有限元軟件對側(cè)圍外板及固定支架進(jìn)行網(wǎng)格劃分，選用四邊形與三角形結(jié)合的劃分模式，對劃分網(wǎng)格的節(jié)點(diǎn)進(jìn)行提取，共獲得1 728 995 個車身離散化點(diǎn)云坐標(biāo)。如圖7 所示，藍(lán)色的為車身點(diǎn)云，紅色的為車身測點(diǎn)，共689個。

Fig.7 Point cloud diagram of side outer plate and fixed support圖7 側(cè)圍外板及固定支架點(diǎn)云圖

圖8 為基于OBB 粗略檢測下三坐標(biāo)測頭結(jié)構(gòu)與車身發(fā)生沖突的情況。其中，綠色點(diǎn)代表車身點(diǎn)云，藍(lán)色線條代表包圍盒，可見三坐標(biāo)測頭結(jié)構(gòu)在運(yùn)動過程中與障礙物之間發(fā)生沖突。隨后，本文將三坐標(biāo)運(yùn)動軌跡進(jìn)行離散化處理，表1為三坐標(biāo)離散軌跡點(diǎn)。

Fig.8 Results of the bracketing box-based detection圖8 基于包圍盒的檢測結(jié)果

Table 1 Trace points of three-dimensional probe structure in discrete space表1 三坐標(biāo)測頭結(jié)構(gòu)離散空間軌跡點(diǎn)

圖9 為構(gòu)造三坐標(biāo)測頭結(jié)構(gòu)運(yùn)動軌跡包絡(luò)體。將車身點(diǎn)云轉(zhuǎn)換為凸多面體形式，采用GJK 精細(xì)化進(jìn)行碰撞檢測。

由圖9 可見，三坐標(biāo)測頭結(jié)構(gòu)在運(yùn)動過程中與障礙物之間發(fā)生了沖突，從而驗(yàn)證本文碰撞檢測算法的有效性。

Fig.9 Graded collision detection results圖9 分級碰撞檢測結(jié)果

通過在車身場景下的測試，對本文提出的分級碰撞檢測算法和僅有包圍盒的碰撞檢測效率進(jìn)行了比較實(shí)驗(yàn)，共記錄50 個測點(diǎn)的平均檢測時間，仿真實(shí)驗(yàn)結(jié)果如圖10所示。

通過測試數(shù)據(jù)可知，在同一場景下本文提出的碰撞檢測效率相較于僅有包圍盒的碰撞檢測，在實(shí)時性方面提升顯著，能夠基本滿足虛擬場景中對碰撞檢測的實(shí)時性要求。

3 結(jié)語

本文提出了一種基于分級連續(xù)碰撞檢測算法，該算法針對靜態(tài)碰撞檢測算法中存在的“隧道效應(yīng)”和計(jì)算效率低的問題，根據(jù)三坐標(biāo)測頭結(jié)構(gòu)的特征進(jìn)行簡化，利用分級碰撞檢測算法在有限的步驟內(nèi)檢測是否發(fā)生碰撞。

仿真結(jié)果表明，提出的算法具有較快的響應(yīng)速度和較高的檢測速度。下一步將以提高動態(tài)碰撞檢測的效率為方向進(jìn)行深入研究。