??????? 對(duì)于2D邊界框的應(yīng)用時(shí)比較廣泛地，它為一個(gè)簡(jiǎn)單匹配建立了很小的計(jì)算規(guī)則，3D模型的boundingbox則比較困難，計(jì)算代價(jià)較大。對(duì)于PCL庫(kù)的使用則降低了計(jì)算難度，三維數(shù)值化降低了建模過(guò)程，可以使用簡(jiǎn)單的邊界框規(guī)則。

??????? 對(duì)于 如何獲取最大最小值過(guò)程：在載入時(shí)去 進(jìn)行一個(gè) 簡(jiǎn)單 一次交換排序，選取最小最大值... 計(jì)算邊界框.

??????? 引自天行健，君子以自強(qiáng)不息的 文章；

??????? 原文鏈接：http://www.cppblog.com/lovedday/archive/2008/02/23/43122.html

矩形邊界框 / 包圍盒

??????? 另一種常見的用來(lái)界定物體的幾何圖元是矩形邊界框，矩形邊界框可以是與軸對(duì)齊的或是任意方向的。軸對(duì)齊矩形邊界框有一個(gè)限制，就是它的邊必須垂直于坐標(biāo)軸。縮寫AABB常用來(lái)表示axially aligned bounding box(軸對(duì)齊矩形邊界框)，OBB用來(lái)表示oriented bounding box(方向矩形邊界框)。軸對(duì)齊矩形邊界框不僅容易創(chuàng)建，而且易于使用。

??????? 一個(gè)3D的AABB就是一個(gè)簡(jiǎn)單的六面體，每一邊都平行于一個(gè)坐標(biāo)平面。矩形邊界框不一定是立方體，它的長(zhǎng)、寬、高可以彼此不同。在圖12.10中，畫出了一些簡(jiǎn)單的3D物體和它們的AABB。

　

AABB的表達(dá)方法

先介紹AABB的一些重要性質(zhì)和引用這些值時(shí)所用到的記法。AABB內(nèi)的點(diǎn)滿足下列等式：

x_min ≤ x ≤ x_max

y_min ≤ y ≤ y_max

z_min ≤ z ≤ z_max

特別重要的兩個(gè)點(diǎn)為：

p_min = [x_min ? y_min???z_min]

p_max = [x_max ? y_max???z_max]

中心點(diǎn)c為：

c = (p_min + p_max) /2

"尺寸向量"s是從p_min指向p_max的向量，包含了矩形邊界的長(zhǎng)、寬、高：

s = p_max - p_min

還可以求出矩形邊界框的"半徑向量"r，它是從中心指向p_max的向量：

r = p_max - c = s/2

明確地定義一個(gè)AABB只需要p_min、p_max、c、s、r這5個(gè)向量中的兩個(gè)（除s和r不能配對(duì)外，它們中的任意兩個(gè)都可配對(duì)）。在一些情況下，某些配對(duì)形式比其他的會(huì)更有用。我們建議用p_min和p_max表示一個(gè)邊界框，因?yàn)閷?shí)際應(yīng)用中，使用它們的頻率遠(yuǎn)高于c、s、r。當(dāng)然，由p_min和p_max計(jì)算其余三個(gè)中的任意一個(gè)都是很容易的。

在我們的C++代碼中，使用下面的類表示AABB，這是一個(gè)縮略的代碼清單。

#ifndef AABB3_H #define AABB3_H #include "vector3.h" class cMatrix4x3;//---------------------------------------------------------------------------// Implement a 3D axially aligned bounding box//---------------------------------------------------------------------------class cAABB3{public:cVector3 min, max;public:// query for dimentionscVector3 size() const { return max - min; }float x_size() { return max.x - min.x; }float y_size() { return max.y - min.y; }float z_size() { return max.z - min.z; }cVector3 center() const { return (min + max) * 0.5f; }// fetch one of the eight corner pointscVector3 corner(int i) const;// "Empty" the box, by setting the values to really large/small numbers.void empty();// add a point to the boxvoid add(const cVector3& p);// add an AABB to the boxvoid add(const cAABB3& box);// return true if the box is emptybool is_empty() const;// return true if the box contains a pointbool contains(const cVector3& p) const;// transform the box and compute the new AABBvoid set_to_transformed_box(const cAABB3& box, const cMatrix4x3& m);// return the clostet point on this box to another pointcVector3 clostet_point_to(const cVector3& p) const;};#endif

計(jì)算AABB

?????? 計(jì)算一個(gè)頂點(diǎn)集合的AABB是非常簡(jiǎn)單的，先將最小值和最大值設(shè)為"正負(fù)無(wú)窮大"或任何比實(shí)際中用到的數(shù)都大或小得多的數(shù)。接著，遍歷全部點(diǎn)，并擴(kuò)展邊界框直到它包含所有點(diǎn)為止。

?????? 我們?cè)赾AABB類中引入了兩個(gè)輔助函數(shù)，第一個(gè)函數(shù)負(fù)責(zé)"清空"AABB

//---------------------------------------------------------------------------// "Empty" the box, by setting the values to really large/small numbers.//---------------------------------------------------------------------------void cAABB3::empty() {const float big_number = 1e37f;min.x = min.y = min.z = big_number;max.x = max.y = max.z = -big_number;}

第二個(gè)函數(shù)將單個(gè)點(diǎn)" 加"到AABB中，并在必要的時(shí)候擴(kuò)展AABB 以包含每個(gè)點(diǎn)：
//---------------------------------------------------------------------------// Add a point to the box//---------------------------------------------------------------------------void cAABB3::add(const cVector3& p){// expand the box as necessary to contain the pointif(p.x < min.x) min.x = p.x;if(p.x > max.x) max.x = p.x;if(p.y < min.y) min.y = p.y;if(p.y > max.y) max.y = p.y;if(p.z < min.z) min.z = p.z;if(p.z > max.z) max.z = p.z;}
現(xiàn)在，從一個(gè)點(diǎn)集創(chuàng)建矩形邊界框，可以使用下面的代碼：
Listing 12.1: Computing the AABB for a set of points// Our list of pointsconst int n;Vector3 list[n];// First, empty the boxAABB3 box;box.empty();// Add each point into the boxfor (int i = 0 ; i < n ; ++i) box.add(list[i]);取得AABB的頂點(diǎn)：//--------------------------------------------------------------------------------------// Return one of the 8 corner points. The points are numbered as follows://// 6 7// ------------------------------// /| /|// / | / |// / | / |// / | / |// / | / |// / | / |// / | / |// / | / |// / | / |// 2 / | 3 / |// /----------------------------/ |// | | | |// | | | | +Y// | 4 | | | // | |-----------------|----------| |// | / | / 5 |// | / | / | +Z// | / | / |// | / | / | /// | / | / | /// | / | / | /// | / | / | /// | / | / | /// | / | / |/// |/ |/ ----------------- +X// ------------------------------// 0 1//// Bit 0 selects min.x vs. max.x// Bit 1 selects min.y vs. max.y// Bit 2 selects min.z vs. max.z//--------------------------------------------------------------------------------------cVector3 cAABB3::corner(int i) const{assert(i >= 0 && i <= 7); // make sure index is in rangereturn cVector3((i & 1) ? max.x : min.x,(i & 2) ? max.y : min.y,(i & 4) ? max.z : min.z);}
其他的相關(guān)函數(shù)，具體功能詳見注釋：
//---------------------------------------------------------------------------// Add an AABB to the box//---------------------------------------------------------------------------void cAABB3::add(const cAABB3& box){// expand the box as necessaryif(box.min.x < min.x) min.x = box.min.x;if(box.min.x > max.x) max.x = box.min.x;if(box.min.y < min.y) min.y = box.min.y;if(box.min.y > max.y) max.y = box.min.y;if(box.min.z < min.z) min.z = box.min.z;if(box.min.z > max.z) max.z = box.min.z;}//---------------------------------------------------------------------------// Return true if the box is empty//---------------------------------------------------------------------------bool cAABB3::is_empty() const{// check if we're inverted on any axisreturn (min.x > max.x) || (min.y > max.y) || (min.z > max.z);}//---------------------------------------------------------------------------// Return true if the box contains a point//---------------------------------------------------------------------------bool cAABB3::contains(const cVector3& p) const{// check for overlap on each axisreturn (p.x >= min.x) && (p.x <= max.x) &&(p.y >= min.y) && (p.y <= max.y) &&(p.z >= min.z) && (p.z <= max.z);}//---------------------------------------------------------------------------// return the closest point on this box to another point//---------------------------------------------------------------------------cVector3 cAABB3::clostet_point_to(const cVector3& p) const{// "push" p into the box, on each dimension.cVector3 r;if(p.x < min.x)r.x = min.x;else if(p.x > max.x)r.x = max.x;elser.x = p.x;if(p.y < min.y) r.y = min.y;else if(p.y > max.y) r.y = max.y;elser.y = p.y;if(p.z < min.z)r.z = min.z;else if(p.z > max.z)r.z = max.z;elser.z = p.z;return r;}

AABB與邊界球

很多情況下，AABB比邊界球更適合于做定界球：

（1）計(jì)算一個(gè)點(diǎn)集的AABB，在編程上更容易實(shí)現(xiàn)，并能在較短的時(shí)間內(nèi)完成。計(jì)算邊界球則困難得多。

（2）對(duì)實(shí)際世界里的許多物體，AABB提供了一種"更緊湊"的邊界。當(dāng)然，對(duì)于某些物體，邊界球更好（設(shè)想一個(gè)本身就是球形的物體）。在極端情況下，AABB的體積可能僅相當(dāng)于邊界球體積的1/2，大部分時(shí)候邊界球的體積會(huì)比矩形框的體積大得多，比較一下電線桿的邊界球和AABB就知道了。圖12.11所示為不同物體的AABB與邊界球的比較。

邊界球的根本問(wèn)題是它的形狀只有一個(gè)自由度----半徑，而AABB卻有三個(gè)自由度----長(zhǎng)、寬、高。因此，它可以調(diào)節(jié)這些自由度以適應(yīng)不同物體。對(duì)圖12.11中的大部分物體，除了右上角的星形體外，AABB都比邊界球小。對(duì)這顆星，邊界球也僅比AABB略小一些。通過(guò)圖12.11，我們可以注意到AABB對(duì)物體的方向很敏感。比較下面兩支槍的AABB，圖中槍的大小都是相同的，只是方向不同而已；還應(yīng)注意到在這一情況下邊界球大小相同，因?yàn)檫吔缜驅(qū)ξ矬w方向不敏感。

　

變換AABB

?????? 當(dāng)物體在虛擬世界中移動(dòng)時(shí)，它的AABB也需要隨之移動(dòng)。此時(shí)我們有兩個(gè)選擇----用變換后的物體來(lái)重新計(jì)算AABB，或者對(duì)AABB做和物體同樣的變換。所得到的結(jié)果不一定是軸對(duì)齊的（如果物體旋轉(zhuǎn)），也不一定是盒狀的（如果物體發(fā)生了扭曲）。不過(guò)，通過(guò)"變換后的AABB"進(jìn)行計(jì)算要比通過(guò)"經(jīng)過(guò)變換后的物體"計(jì)算AABB快得多，因?yàn)锳ABB只有8個(gè)頂點(diǎn)。

?????? 通過(guò)"變換后的AABB"計(jì)算不能只是簡(jiǎn)單地變換8個(gè)頂點(diǎn)，也不能通過(guò)轉(zhuǎn)換原p_min和p_max來(lái)得到新的p_min和p_max ----這樣可能會(huì)導(dǎo)致x_min > x_max。為了計(jì)算新的AABB，必須先變換8個(gè)頂點(diǎn)，再?gòu)倪@8個(gè)頂點(diǎn)中計(jì)算一個(gè)新的AABB。

?????? 根據(jù)變換的不同，這種方法可能使新邊界框比原邊界框大許多。例如，在2D中，45度的旋轉(zhuǎn)會(huì)大大增加邊界框的尺寸，如圖12.12所示：

?????? 比較圖12.12中原AABB（灰色框）和新AABB（右邊較大的方框），它是通過(guò)旋轉(zhuǎn)后的AABB計(jì)算的，新AABB幾乎是原來(lái)的兩倍。注意，如果從旋轉(zhuǎn)后的物體而不是通過(guò)旋轉(zhuǎn)后的AABB來(lái)計(jì)算新AABB，它的大小將和原來(lái)的AABB相同。

?????? 可以利用AABB的結(jié)構(gòu)來(lái)加快新的AABB的計(jì)算速度，而不必先變換8個(gè)頂點(diǎn)，再?gòu)倪@8個(gè)頂點(diǎn)中計(jì)算新AABB。

讓我們簡(jiǎn)單回顧一下3x3矩陣變換一個(gè)3D點(diǎn)的過(guò)程：

?????? 設(shè)原邊界框?yàn)?/span>x_min，x_max，y_min...，新邊界框計(jì)算將得到x^'_min，x^'_max，y^'_min...。現(xiàn)在我們的任務(wù)就是想辦法加快計(jì)算x^'_min的速度，換句話說(shuō)，我們希望找到m₁₁x+m₂₁y+m₃₁z的最小值，其中[x, y, z]是原8個(gè)頂點(diǎn)中的任意一個(gè)，我們所要做的就是找出這些點(diǎn)經(jīng)過(guò)變換后誰(shuí)的x坐標(biāo)最小。看第一個(gè)乘積：m₁₁x，為了最小化乘積，必須決定是用x_min還是x_max來(lái)代換其中的x。顯然，如果m₁₁>0，用x_min能得到最小化乘積；如果m₁₁<0，則用x_max能得到最小化乘積。比較方便的是，不管x_min和x_max中哪個(gè)被用來(lái)計(jì)算x_min，都可以用另外一個(gè)來(lái)計(jì)算x_max。可以對(duì)矩陣9個(gè)元素中的每個(gè)都應(yīng)用這個(gè)計(jì)算過(guò)程，

如下列代碼所示：

//---------------------------------------------------------------------------// Transform the box and compute the new AABB. Remember, this always// results in an AABB that is at least as big as the origin, and may be// considerably bigger.//---------------------------------------------------------------------------void cAABB3::set_to_transformed_box(const cAABB3& box, const cMatrix4x3& m){// if we're empty, then bail.if(box.is_empty()){empty();return;} // start with the translation portionmin = max = get_translation(m); // examine each of the 9 matrix elements and compute the new AABB if(m.m11 > 0.0f){min.x += m.m11 * box.min.x;max.x += m.m11 * box.max.x;}else{min.x += m.m11 * box.max.x;max.x += m.m11 * box.min.x;}if(m.m21 > 0.0f){min.x += m.m21 * box.min.y; max.x += m.m21 * box.max.y;}else{min.x += m.m21 * box.max.y; max.x += m.m21 * box.min.y;}if(m.m31 > 0.0f){min.x += m.m31 * box.min.z; max.x += m.m31 * box.max.z;}else{min.x += m.m31 * box.max.z; max.x += m.m31 * box.min.z;}if(m.m12 > 0.0f) {min.y += m.m12 * box.min.x; max.y += m.m12 * box.max.x;}else{min.y += m.m12 * box.max.x; max.y += m.m12 * box.min.x;}if(m.m22 > 0.0f){min.y += m.m22 * box.min.y; max.y += m.m22 * box.max.y;}else{min.y += m.m22 * box.max.y; max.y += m.m22 * box.min.y;}if(m.m32 > 0.0f){min.y += m.m32 * box.min.z; max.y += m.m32 * box.max.z;}else{min.y += m.m32 * box.max.z; max.y += m.m32 * box.min.z;}if(m.m13 > 0.0f) {min.z += m.m13 * box.min.x; max.z += m.m13 * box.max.x;}else{min.z += m.m13 * box.max.x; max.z += m.m13 * box.min.x;}if(m.m23 > 0.0f){min.z += m.m23 * box.min.y; max.z += m.m23 * box.max.y;}else{min.z += m.m23 * box.max.y; max.z += m.m23 * box.min.y;}if(m.m33 > 0.0f){min.z += m.m33 * box.min.z; max.z += m.m33 * box.max.z;}else{min.z += m.m33 * box.max.z; max.z += m.m33 * box.min.z;}}

后記：

???????? 包圍盒作為一種約束，和坐標(biāo)系有關(guān)系，世界坐標(biāo)系標(biāo)定了包圍盒的精度。

總結(jié)

以上是生活随笔為你收集整理的3D集合图元：最小边界框/包围盒（boundingbox）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。