面向車身數字化工藝開發的三坐標碰撞算法研究

王雪琪，趙文政

（上海理工大學機械工程學院，上海 200093）

0 引言

經歷數十年的高速發展，汽車工業已然成為推動國民經濟高質量發展的重要支柱，我國也成為最大的汽車生產國與消費國。然而，自主品牌和自有技術存在的短板阻礙了我國制造業從“制造”向“智造”轉型的步伐。

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

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

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

動態碰撞檢測則主要研究物體運動過程中是否發生碰撞，被廣泛運用于三維游戲等虛擬現實中，又可細分為離散碰撞檢測和連續碰撞檢測。

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

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

綜上所述，面對不同應用場景，學者們提出了不同的碰撞檢測算法和改進算法以提高檢測效率及準確度，然而現有碰撞檢測算法仍無法高效解決復雜環境下的碰撞檢測問題。例如，面對車身復雜結構與五軸三坐標之間的碰撞檢測，尤其針車身與測頭的連續運動過程的掃掠建模與快速碰撞檢測方面，仍存在碰撞檢測效率低與碰撞檢測精度差等問題。

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

1 三坐標測量儀碰撞檢測算法

針對現有動態碰撞檢測算法在車身三坐標碰撞檢測應用中的不足，對車身進行三角面片化，將三坐標的測頭、測針、接長桿進行層次包圍盒化等處理，實現對三坐標運動軌跡所占空間的建模，提出基于OBB 包圍盒（Oriented Bounding Box）和GJK 碰撞檢測相結合的分級碰撞檢測算法。算法流程如圖1所示。

Fig.1 Dynamic collision detection algorithm flow圖1 動態碰撞檢測算法流程

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

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

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

Fig.3 Simplified model of CMM probe structure圖3 三坐標測頭結構簡化模型

1.1 基于空間幾何的靜態碰撞檢測

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

測頭系統中探針與接長桿可簡化為圓柱體結構，旋轉中心可簡化為球體結構。因此，測頭與車身結構的靜態碰撞探測可轉化為篩選點云是否存在于測頭系統所占幾何空間中，對于旋轉中心而言，靜態碰撞探測可以表示為：

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

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

1.2 基于分級檢測的動態碰撞檢測算法

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

圖4（彩圖掃OSID 碼可見，下同）中橙色曲面表示測頭結構從t0時刻到tend時刻的移動軌跡，青色為測頭結構移動軌跡所占空間的包圍盒。可根據測頭點云信息得到測頭結構從t0時刻到tend時刻在空間中的位置U（iXi，Yi，Zi）、Li（Xi，Yi，Zi）（i=1，2，...，P），最終通過OBB 包圍盒確定各個節點的坐標值，具體步驟如下：

各測頭中心點的均值為：

根據式（1）可得到協方差H：

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

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

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

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

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

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

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

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

設三坐標測頭從t0時刻到tend時刻所形成凸體，記為CTU，即測頭結構在［t0，tend］時間區間內所形成凸體的凸集可由各個邊的節點表示。車身某處三角面片記為BIW，用D（Cmm，BIW）表示兩凸體之間的距離，則兩者之間的距離可表示為：

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

對于［t0，tend］時間區間內測頭結構所形成的凸體TUT與車身三角面片BIW之間的GJK 算法的碰撞檢測過程：

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

步驟2：計算凸包CSO 與原點之間的最短距離為dk，該點記為vk。

步驟3：若dk為0，則三坐標包圍盒與車身發生碰撞算法結束；若不為0，則轉到步驟3。

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

步驟5：沿初始方向負方向即計算凸包CSO 沿-vk所在方向的支撐點wk。

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

步驟7：輸出三坐標測頭結構與車身狀態。

2 實驗及分析

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

Fig.6 Collision detection in the following experimental scenario圖6 實驗場景下的碰撞檢測

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

由于側圍外板的CAD 數模結構由側圍外板薄板件、眾多加強件、功能件等多種零件連接而成。因此，在對側圍外板進行測量時，首先將其放置在固定支架小車上并利用夾具進行固定，然后將支架小車及側圍外板件放置于先前設定好的測量機的檢測區域，最后進行測量機校準、坐標系重建及對側圍外板關鍵尺寸特征進行檢測。

利用有限元軟件對側圍外板及固定支架進行網格劃分，選用四邊形與三角形結合的劃分模式，對劃分網格的節點進行提取，共獲得1 728 995 個車身離散化點云坐標。如圖7 所示，藍色的為車身點云，紅色的為車身測點，共689個。

Fig.7 Point cloud diagram of side outer plate and fixed support圖7 側圍外板及固定支架點云圖

圖8 為基于OBB 粗略檢測下三坐標測頭結構與車身發生沖突的情況。其中，綠色點代表車身點云，藍色線條代表包圍盒，可見三坐標測頭結構在運動過程中與障礙物之間發生沖突。隨后，本文將三坐標運動軌跡進行離散化處理，表1為三坐標離散軌跡點。

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

Table 1 Trace points of three-dimensional probe structure in discrete space表1 三坐標測頭結構離散空間軌跡點

圖9 為構造三坐標測頭結構運動軌跡包絡體。將車身點云轉換為凸多面體形式，采用GJK 精細化進行碰撞檢測。

由圖9 可見，三坐標測頭結構在運動過程中與障礙物之間發生了沖突，從而驗證本文碰撞檢測算法的有效性。

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

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

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

3 結語

本文提出了一種基于分級連續碰撞檢測算法，該算法針對靜態碰撞檢測算法中存在的“隧道效應”和計算效率低的問題，根據三坐標測頭結構的特征進行簡化，利用分級碰撞檢測算法在有限的步驟內檢測是否發生碰撞。

仿真結果表明，提出的算法具有較快的響應速度和較高的檢測速度。下一步將以提高動態碰撞檢測的效率為方向進行深入研究。