基于包圍盒的機床碰撞檢測系統算法研究*

許 榮 張為民②

(①同濟大學機械工程學院，上海 201804;②同濟大學中德學院，上海 200092)

近年來，隨著虛擬現實、計算機仿真等技術的蓬勃發展，對碰撞檢測的實時性和精確性要求逐漸提高。在數控機床進行加工前，刀具與夾具以及工件的碰撞需要運用計算機仿真技術進行在線實時碰撞檢測，防止加工中由于碰撞對機床造成損害［1］。所以實時碰撞檢測技術成為機床在線仿真當中的關鍵技術。隨著機床三維幾何模型形狀越來越復雜，碰撞檢測成為一件很耗時的工作，因此在盡可能保證實時性和場景真實性的前提下，提高碰撞檢測算法的效率，成為研究人員面前一項迫切的任務，從而使得實時碰撞檢測再次成為研究的熱點。本文主要介紹了基于層次包圍盒的碰撞檢測算法在機床碰撞檢測系統中的應用并對算法提出了優化。

1 碰撞檢測算法概述

目前，國內外許多學者對實時碰撞檢測技術進行了廣泛深入的研究和探索，提出了距離跟蹤法、空間分解法、時空包圍盒法和層次包圍盒法等許多檢測算法。其中，主要有空間分解法和層次包圍盒法兩類算法。

空間分解法首先將對整個空間進行體積相等的網格化剖分，然后僅僅對同一網格中的幾何對象進行碰撞檢測［3］。典型的空間分解法有八叉樹法和二叉樹法。

而如今虛擬現實技術中比較通用的是層次包圍盒法，其核心思想是使用體積略大但幾何特性簡單的包圍盒來近似描述復雜的對象，通過構造樹狀層次結構可以不斷逼近真實模型的幾何形狀，最后通過對包圍盒的相交計算來實現幾何物體的碰撞檢測。典型方法有軸向層次包圍盒(Axis－Aligned Bounding Boxes，AABB)、方向層次包圍 盒 (Oriented Bounding Boxes，OBB)、包 圍 球(Sphere)和離散方向多面體(8－Direction Orientation Polytopes，8 －DOP)等［2］，如圖1 所示。

這兩類算法都使用了層次結構模型，其思想都是通過減少需要相交測試的對象或基本幾何元素的數目來提高碰撞檢測的效率。空間分解法由于存儲量大、靈活性差，一般適用于稀疏的環境中較均勻分布的幾何物體之間的碰撞檢測;而層次包圍盒方法則應用比較廣泛，尤其適用于復雜環境中的碰撞檢測。

2 機床碰撞檢測系統中包圍盒算法及其改進

2.1 OBB方向包圍盒的定義及檢測方法

包圍盒OBB被定義為包含該對象且相對于坐標軸方向的任意最小的正六面體。它的最大特點是方向任意性，可以根據被包圍對象的形狀特點盡可能緊密地包圍對象［4］。但是關鍵在于尋找包圍盒的最佳方向，然后確定在該方向上包圍盒的最小尺寸。假設模型中的基本幾何元素是三角形，設第i個三角形的頂點矢量為pi、qi和ri，則均值μ和協方差矩陣C計算式為

式中:n為包圍盒所包圍的三角形面元的數目;μ確定了包圍盒的中心位置;p－i=pi－μ，q－i=qi－ μ 和 r－i=ri－μ是所包圍區域內的向量。協方差矩陣C的三個特征向量是正交的，正規化后可作為一個基底，確定包圍盒的方向軸，最后將所有的頂點投影到這條方向軸上，計算出在軸上的最大值和最小值，以此來確定包圍盒的大小。為了快速地判斷相交性，OBB檢測使用分離軸方法進行檢測。在空間中，若存在一個向量，使兩個OBB在該向量上的投影不相交，那么這個向量即為一條分離軸。若一對OBB間存在一條分離軸，那么可判定這兩個OBB是不相交的。一對OBB包圍盒之間最多有15條潛在的分離軸，分別是每個OBB的3個面方向有3×2=6條潛在分離軸，每個OBB的3條邊方向的兩兩叉乘有3×3=9條潛在分離軸，一共是15條潛在分離軸。對每一條潛在分離軸分別采取區間檢測方法，計算出包圍盒八個頂點的坐標值、每個頂點在分離軸上的投影，比較他們的大小。方法如圖2。

假設兩個OBB分別為A和B，ai和bi表示A、B邊長的一半，Ai和Bi表示A、B軸向的單位向量(i=1，2，3);T是A、B中心點的距離，L是當前的分離軸向量。有如下公式(2):

如果滿足前者大于后者，那么兩個物體不相交;否則按此公式繼續計算A、B在其他14條分離軸上的投影。在最多進行15次計算之后如果還不能把兩個OBB分開，可以判定這兩個物體是相交的。由此可見，創建階段和比較階段都很復雜，過程包括了大量的運算。

2.2 基于OBB包圍盒算法的機床碰撞檢測系統

采用基于層次包圍盒樹的碰撞檢測算法，在機床上建立有效的碰撞檢測系統，實現實時加工碰撞的檢測。

首先是機床、刀具和工件的實體建模階段。即準確描述機床、工件和刀具的運動狀態，在OpenGL軟件環境下建立模型，實現機床模型和工件模型的三角面片化，為后面層次包圍盒二叉樹建模做準備，另外實現G代碼的解析工作，將G代碼解析后生成指令來驅動模型運動。

其次在機床幾何模型基礎上建立OBB包圍盒樹模型，實現碰撞檢測。結合機床的結構，銑刀頭運動方式(轉角范圍、刀具尺寸及形狀等)以及工件的建模來確定可能發生碰撞的系統部件，對其進行包圍盒樹的構建，運用分離軸理論，實現基于包圍盒樹算法的碰撞檢測。另外，應用西門子的OEM開發包，實現碰撞檢測系統與機床數控系統的嵌入集成。圖3為虛擬環境中應用OpenGL建立的機床三維幾何模型;圖4為機床碰撞檢測系統的顯示界面。

2.3 包圍盒算法優化

由于OBB包圍盒的中心位置是各三角形面片頂點簡單的平均，當模型存在弧度或凹凸時，構成模型表面的三角形面片尺寸就會不均勻，有的尺寸大而分散，有的尺寸小且密集，這樣計算出來的包圍盒整體就會向著三角形尺寸小且密集的部分偏移。這種情況對最后碰撞檢測的結果存在不利影響，可能會出現誤判。因為有一部分三角形面片在包圍盒的外面，同時包圍盒有一個與包圍盒平行的較小的長方體空隙，這樣就使得包圍盒緊密性變差，而且會使構造的包圍盒樹不平衡，影響到碰撞檢測的效率。尤為嚴重的是存在某些情況，即那些在包圍盒外面的三角形已經與其他物體接觸了，但包圍盒檢測時沒有檢測出接觸，于是錯誤地斷定所包圍的三角形不接觸，導致錯誤的檢測結果。此外，這對協方差矩陣也有影響，導致包圍盒方向向量的計算不準確，對包圍盒的緊密性造成影響。這樣就需要對傳統的OBB包圍盒算法提出優化的解決方法。

優化方法是給每一個三角形加權，選擇三角形的面積作為權值。設第i個三角形的面積用Si表示，包圍盒所包圍的物體表面積用S表示，第i個三角形的中心用ni表示，包圍盒所包圍的三角形帶權中心用n表示，則公式如下:

協方差矩陣C的元素為

3 實驗測試

實驗環境是在西門子840D數控系統的機床碰撞檢測系統中，實現了本文優化的OBB碰撞檢測算法。分別測試了兩個場景的碰撞檢測的時間，兩個場景中機床模型分別在不同G代碼的驅動下，完成碰撞檢測。場景1中為圓柱面刀具與長方體刀架的碰撞，場景2為圓環面刀具與機床尾架的碰撞。圖5為碰撞發生時機床的響應結果，圖6為兩種算法的耗時結果對比。

由實驗結果可以看出，采用優化的碰撞檢測算法較之原始算法有大約20%的性能上的改進，并且當場景的規模越大時，算法改進的效率也越高。

4 結語

OBB層次包圍盒廣泛應用于數控機床的碰撞檢測中，且緊密性較好，但存在一些誤檢測情況。本文根據OBB的算法特點，提出并實現了優化的OBB碰撞檢測算法。實驗結果證明，本文的優化算法能較大幅度地提高碰撞檢測的實時性能，且效果明顯。

［1］許瑋，張為民，金致富.基于西門子840D數控系統的防碰撞技術研究［J］.制造技術與機床，2010(11):33－36.

［2］何偉，李勇，蘇虎.碰撞檢測中的包圍盒方法［J］.重慶工學院學報，2007(12).

［3］龍春國，史耀耀，程剛，等.基于OpenGL五軸聯動數控仿真系統碰撞干涉檢驗實時仿真技術及算法研究［J］.機床與液壓，2006(2).

［4］Christer Ericson.Real－ time collision detection［M］.Elsevier Science Ltd.，2005.