包圍盒

包圍盒

計算方法
包圍盒也叫外接最小矩形,是一種求解離散點集最優包圍空間的算法,基本思想是用體積稍大且特性簡單的幾何體(稱為包圍盒)來近似地代替複雜的幾何對象。[1]被定義為包含該對象且它的所有面的法向量都取自一個固定的方向(k個向量)集合的凸包。FDH比其他包圍體更緊密地包圍原物體,創建的層次樹也就有更少的節點,求交檢測時就會減少更多的冗餘計算,但相互間的求交運算較為複雜。OBB的簡單性要比上面兩種包圍盒差,但它的緊密性是比較好的,可以大大減少參與相交測試的包圍盒的數目,因此總體性能要優于AABB和包圍球。
    中文名:包圍盒 外文名:bounding box 适用領域: 所屬學科: 分類:碰撞檢測、計算機圖形學、計算幾何 類型:求解離散點集最優包圍空間的算法

屬性

碰撞檢測技術中所用的包圍盒有兩個屬性:簡單性和緊密性。簡單性是指包圍盒間進行相交測試時需要的計算量,這不但要求幾何形狀簡單容易計算,而且要求相交測試算法簡單快速;緊密性要求包圍盒盡可能的貼近被包圍的對象,這一屬性直接關系到需要進行相交測試的包圍盒的數目,緊密性越好,參與相交測試的包圍盒數目就越少。

分類

最常見的包圍盒算法有AABB包圍盒(Axis-aligned bounding box),包圍球(Sphere),方向包圍盒OBB(Oriented bounding box)以及固定方向凸包fdh(Fixed directions hulls或k-DOP)。

AABB是應用最早的包圍盒。它被定義為包含該對象,且邊平行于坐标軸的最小六面體。故描述一個AABB,僅需六個标量。AABB構造比較簡單,存儲空間小,但緊密性差,尤其對不規則幾何形體,冗餘空間很大,當對象旋轉時,無法對其進行相應的旋轉。處理對象是剛性并且是凸的,不适合包含軟體變形的複雜的虛拟環境情況。

對象的包圍球被定義為包含該對象的最小的球體。确定包圍球,首先需分别計算組成對象的基本幾何元素集合中所有元素的頂點的x,y,z坐标的均值以确定包圍球的球心,再由球心與三個最大值坐标所确定的點間的距離确定半徑r。包圍球的碰撞檢測主要是比較兩球間半徑和與球心距離的大小。

OBB是較為常用的包圍盒類型。它是包含該對象且相對于坐标軸方向任意的最小的長方體。OBB最大特點是它的方向的任意性,這使得它可以根據被包圍對象的形狀特點盡可能緊密的包圍對象,但同時也使得它的相交測試變得複雜。OBB包圍盒比AABB包圍盒和包圍球更加緊密地逼近物體,能比較顯着地減少包圍體的個數,從而避免了大量包圍體之間的相交檢測。但OBB之間的相交檢測比AABB或包圍球體之間的相交檢測更費時。

FDH(k-DOP)是一種特殊的凸包,繼承了AABB簡單性的特點,但其要具備良好的空間緊密度,必須使用足夠多的固定方向。被定義為包含該對象且它的所有面的法向量都取自一個固定的方向(k個向量)集合的凸包。FDH比其他包圍體更緊密地包圍原物體,創建的層次樹也就有更少的節點,求交檢測時就會減少更多的冗餘計算,但相互間的求交運算較為複雜。

優缺點

AABB也是比較簡單的一類包圍盒。但對于沿斜對角方向放置的瘦長形對象,其緊密性較差。由于AABB相交測試的簡單性及較好的緊密性,因此得到了廣泛的應用,還可以用于軟體對象的碰撞檢測。

包圍球是比較簡單的包圍盒,而且當對象發生旋轉運動時,包圍球不需做任何更新,當幾何對象進行頻繁的旋轉運動時,使用包圍球可能會得到很好的結果;當對象變形時,需要重新計算其包圍球。但它的緊密性是比較差的,因此較少使用。

OBB的簡單性要比上面兩種包圍盒差,但它的緊密性是比較好的,可以大大減少參與相交測試的包圍盒的數目,因此總體性能要優于AABB和包圍球。當幾何對象發生旋轉運動後,隻要對OBB進行同樣的旋轉即可。

因此,對于剛體間的碰撞檢測,OBB不失為一種較好的選擇,但迄今為止,還沒有一種有效的方法能夠較好地解決對象變形後OBB樹的更新問題,而重新計算每個結點的OBB的代價又太大,所以OBB不适用于包含軟體對象的複雜環境中。

FDH相對于上面三種包圍盒其緊密性是最好的,同時其相交測試算法比OBB要簡單的多。可以用于軟體對象的碰撞檢測。

應用

在計算機圖形學與計算幾何領域,一組物體的包圍盒就是将物體組合完全包容起來的一個封閉空間。将複雜物體封裝在簡單的包圍盒中,用簡單的包圍盒形狀來近似代替複雜幾何體的形狀,就可以提高幾何運算的效率。并且通常簡單的物體比較容易檢查相互之間的重疊。

在光線跟蹤中,包圍盒用于光線相交檢驗,在許多渲染算法中,它又用于視體的檢驗。如果光線或者視體與包圍體沒有交叉,那麼就不會與包圍盒内的物體相交。通過這樣的相交檢驗,就可以生成需要顯示的物體列表。這裡的顯示表示需要渲染或者栅格化。

相關詞條

相關搜索

其它詞條