確定任意形狀物體最小包圍盒的一種方法

陳 華

（西安理工大學理學院，陜西 西安 710048）

物體的包圍盒廣泛應用于碰撞檢測、模具分型設計、產(chǎn)品包裝設計以及圖像處理、模式識別等領域。包圍盒的基本思想是利用某種形狀簡單的幾何體來緊密包裹對象物體。常見的包圍盒類型主要有正六面體（長方體）和球體等。一般來說，由于包圍球的緊密性不夠好，因此在應用中多采用長方體包圍盒。根據(jù)該包圍盒的3個邊與坐標軸的位置關系，長方體包圍盒主要分為沿坐標軸的軸向包圍盒AABB(Axis-Aligned Bounding Boxes)和任意方向的方向包圍盒OBB (Oriented Bounding Box) 及其它改進形式[1-2]。AABB的確定相對而言比較簡單，在現(xiàn)有的CAD軟件中就能直接得到結果，但由于它是平行于坐標軸的定方向的包圍盒，所以不能保證是最小的包圍盒。而OBB最大的特點是其方向的任意性，這使得它可以根據(jù)被包圍對象的形狀特點盡可能緊密地包圍對象，從而做到使包圍盒的體積最小。由于OBB的這一優(yōu)點，近年來在其生成方法研究，特別是在碰撞檢測中的應用方面研究較多。文獻[3]提出了一種多面體模型的最小體積的包圍盒生成算法，用以確定模具的分型方向；文獻[4]將包圍盒技術應用于三維模型的數(shù)據(jù)點配準，以掃描數(shù)據(jù)生成的三角網(wǎng)格模型為對象，應用單純形優(yōu)化算法生成三維模型的最小包圍盒，進而實現(xiàn)數(shù)據(jù)點配準；文獻[5]研究了層次OBB在5軸數(shù)控加工中的應用，提出了刀具OBB與工件八叉樹的干涉檢測方法。

上述文獻表明，OBB的應用范圍相當廣泛，但是由于問題的復雜性和目標對象形狀的任意性，目前的文獻主要是針對平面立體或用三角形面片形式表示的物體，其算法相對都比較復雜，計算量隨物體頂點數(shù)或三角面片個數(shù)的增加而急劇增加。本文提出了一種簡單、實用的確定任意物體最小包圍盒的方法，利用現(xiàn)有的CAD軟件本身具有確定AABB的功能，通過對CAD軟件的二次開發(fā)，利用程序自動確定出任意形狀物體的最小包圍盒。

圖 1 物體旋轉前后的AABB

1 算法思路

1.1 AABB 與OBB

AABB是平行于坐標軸的定方向的最小長方體包圍盒，其體積大小和3個邊長除了與物體本身的形狀和大小有關，還與物體相對于坐標系的角度有關。一個物體在坐標系中的方向確定后，就對應唯一的AABB，在現(xiàn)有的CAD軟件中能直接得到其結果。但是，由于AABB與物體相對于坐標系的角度有關，某一方向下得出的AABB不能保證是物體最小的長方體包圍盒。為了得到最小包圍盒，可以設想將物體在坐標系中分別繞X、Y、Z軸旋轉，每旋轉一個位置，求出其AABB，這些AABB中至少有一個是最小包圍盒。

方向包圍盒OBB的3個邊長大小只與物體的形狀和大小有關，與其在坐標系的擺放角度無關。在一個確定的坐標系中，物體的OBB三個邊相對于坐標系有特定的角度，換句話說，如果將原坐標系旋轉該角度，那么原坐標系中的OBB也就是旋轉變換后新坐標系中的AABB。由此可以設想，不斷地旋轉坐標系并求在該坐標系中的AABB，也能得到物體的最小包圍盒，即在原坐標系下的OBB。圖1給出了物體旋轉前后在同一坐標系下不同的AABB，圖2則是物體不動坐標系旋轉變換前后在兩個坐標系下的AABB。

圖 2 坐標系旋轉前后的AABB

1.2 算法思路

要利用繪圖軟件提取實體在任意方向下的包圍盒，有兩種途徑，一種是將物體作旋轉變換，一種是將坐標系作旋轉變換。兩種方法得到的包圍盒大小是一樣的。相對而言，坐標系旋轉比物體旋轉要簡單得多，在旋轉n3次的情況下，利用后一種途徑，運算速度會大大提高。

圖3是本文方法的程序框圖。程序首先進行初始化，設3個坐標軸的轉角α、β、γ分別為0，并建立一個空文件，用以保存結果數(shù)據(jù)，然后選擇對象，按一定的角度步長，用三重循環(huán)分別使3個坐標軸進行0°～360°的旋轉。在每個旋轉位置，提取對象的物性參數(shù)，從中得到包圍盒的邊界數(shù)據(jù){Xi}和體積Vi，其中{Xi}＝{Xmin，Xmax，Ymin，Ymax，Zmin，Zmax}。比較每個位置的包圍盒體積，可得出最小包圍盒及其對應的轉角α0、β0、γ0，保存在程序開始所建立的文件中。由α0、β0、γ0可直接得出包圍盒的3個邊長相對于初始坐標系的夾角，從而確定出對象的OBB。

在該方法中只要改變比較條件，就可求出滿足不同要求的最小包圍盒，如最小表面積的包圍盒（產(chǎn)品的包裝盒生產(chǎn)時）、某一邊長最大/最小的包圍盒（模具分型方向確定）等。

2 應用舉例

圖 3 程序框圖

上述算法可以在任何具有物性提取功能的三維CAD軟件中實現(xiàn)。這里以國內(nèi)外廣泛使用的AutoCAD軟件為平臺，采用嵌套在其內(nèi)部的AutoLisp語言編程予以實現(xiàn)。程序的核心是 AutoCAD的“MASSPROP”命令和“UCS”命令的調(diào)用。使用“MASSPROP”命令將生成一個物性文件，存儲對象的體積、質(zhì)心坐標、AABB的3個邊長邊界坐標、對象的慣性矩、慣性積等物性數(shù)據(jù)。而“UCS”命令則用以新建一個坐標系，有多種創(chuàng)建方法。本文利用的是繞原坐標系的某個軸旋轉一定角度，建立新坐標系的方法，在具體編程時，調(diào)用“MASSPROP”命令的語句放在三重循環(huán)的最內(nèi)層，而三重循環(huán)的每一層均要調(diào)用“UCS”命令，分別實現(xiàn)使坐標系繞X、Y、Z旋轉。

圖4 是某物體的三維模型，物體體積為2526148mm3，表面積為114273mm2。在初始位置下的AABB包圍盒的體積是10369845mm3，平行于X、Y、Z軸的3個邊長分別是182.618mm，198.512mm，286.050mm。

利用本文所編制的程序，確定出其最小體積包圍盒的體積是7121911mm3，3個邊長分別是307.790 mm，180.271mm，128.356mm，包圍盒表面積是236262 mm2，它是將原坐標系分別繞X軸旋轉α=144°、繞Y軸旋轉β=72°、繞Z軸旋轉γ=18°建立的新坐標系下的AABB，也就是物體在原坐標系下的OBB，如圖5所示。如果追求包圍盒表面積最小，則可得出最小表面積的包圍盒體積為7121956mm3，包圍盒表面積是235926 mm2，3 個邊長分別是305.776mm，180.754mm，128.857mm，此結果是將原坐標系分別繞X軸旋轉α=126°、繞Y軸旋轉β=72°、繞Z軸旋轉γ=36°得出的。不同的包圍盒的參數(shù)對比如表1所示。由此可見，最小體積的包圍盒與最小表面積的包圍盒有可能是不同的，對于不同的應用場合，應根據(jù)需要確定合適的包圍盒類型，再確定包圍盒的參數(shù)。

圖 4 物體模型及其AABB

圖 5 物體的最小體積包圍盒

表 1 同一物體不同要求包圍盒的參數(shù)對比

3 結 論

對物體包圍盒的研究目前主要集中于虛擬現(xiàn)實技術中的碰撞檢測方面，在企業(yè)生產(chǎn)中的模具分型設計和產(chǎn)品包裝設計等方面也有一定應用。方向包圍盒OBB由于其對物體的包裹緊密性強的特點，是目前應用最多的一種包圍盒。但現(xiàn)有文獻中OBB的確定主要是針對平面立體或用三角形面片形式表示的物體，其計算量隨物體頂點數(shù)或三角面片個數(shù)的增加而急劇增加。本文提出的確定任意形狀物體最小包圍盒的方法，基于現(xiàn)有軟件確定AABB的功能，通過二次開發(fā)，可自動確定出任意形狀物體的最小體積包圍盒或最小表面積包圍盒。這種確定OBB的方法只要求有物體的三維實體模型，對其形狀沒有限制，也不需要復雜的計算，因而簡單、實用，具有廣闊的應用前景。

[1] 馬登武, 葉 文, 李 瑛. 基于包圍盒的碰撞檢測算法綜述[J]. 系統(tǒng)仿真學報, 2006, 18(4)： 1058-1061.

[2] 譚同德, 吳 強, 趙紅領, 等. OBB層次包圍盒構造方法的改進[J]. 計算機工程與應用, 2008, 44(5)： 79-81.

[3] 郭九生, 初紅艷, 盧秉恒. 多面體最小體積的包圍盒生成算法研究[J]. 計算機應用, 2001, 21(1)： 38-40.

[4] 張開興, 張樹生, 白曉亮. 基于最小包圍盒的三維模型的配準技術[J]. 機床與液壓, 2008, 36(4)： 5-7.

[5] Ding S, Mannan M A, Poo A N. Oriented bounding box and octree based global interference detection in 5-axis machining of free-form surfaces [J]. Computer-Aided Design, 2004, 36(13)： 1281-1294.