新建網頁 1
矩形邊界框
另一種常見的用來界定物體的幾何圖元是矩形邊界框，矩形邊界框可以是與軸對齊的或是任意方向的。軸對齊矩形邊界框有一個限制，就是它的邊必須垂直于坐標軸。縮寫AABB常用來表示axially aligned bounding box(軸對齊矩形邊界框)，OBB用來表示oriented bounding box(方向矩形邊界框)。軸對齊矩形邊界框不僅容易創建，而且易于使用。
一個3D的AABB就是一個簡單的六面體，每一邊都平行于一個坐標平面。矩形邊界框不一定是立方體，它的長、寬、高可以彼此不同。在圖12.10中，畫出了一些簡單的3D物體和它們的AABB。
AABB的表達方法
先介紹AABB的一些重要性質和引用這些值時所用到的記法。AABB內的點滿足下列等式：
xmin ≤ x ≤ xmax
ymin ≤ y ≤ ymax
zmin ≤ z ≤ zmax
特別重要的兩個點為：
pmin = [xmin ymin zmin ]
pmax = [xmax ymax zmax ]
中心點c為：
c = (pmin + pmax) /2
"尺寸向量"s是從pmin指向pmax的向量，包含了矩形邊界的長、寬、高：
s = pmax - pmin
還可以求出矩形邊界框的"半徑向量"r，它是從中心指向pmax的向量：
r = pmax - c = s/2
明確地定義一個AABB只需要pmin、pmax、c、s、r這5個向量中的兩個（除s和r不能配對外，它們中的任意兩個都可配對）。在一些情況下，某些配對形式比其他的會更有用。我們建議用pmin和pmax表示一個邊界框，因為實際應用中，使用它們的頻率遠高于c、s、r。當然，由pmin和pmax計算其余三個中的任意一個都是很容易的。
在我們的C++代碼中，使用下面的類表示AABB，這是一個縮略的代碼清單。
#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 dimentions
cVector3 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 points
cVector3 corner(int i) const;
// "Empty" the box, by setting the values to really large/small numbers.
void empty();
// add a point to the box
void add(const cVector3& p);
// add an AABB to the box
void add(const cAABB3& box);
// return true if the box is empty
bool is_empty() const;
// return true if the box contains a point
bool contains(const cVector3& p) const;
// transform the box and compute the new AABB
void set_to_transformed_box(const cAABB3& box, const cMatrix4x3& m);
// return the clostet point on this box to another point
cVector3 clostet_point_to(const cVector3& p) const;
};
#endif
計算AABB
計算一個頂點集合的AABB是非常簡單的，先將最小值和最大值設為"正負無窮大"或任何比實際中用到的數都大或小得多的數。接著，遍歷全部點，并擴展邊界框直到它包含所有點為止。
我們在cAABB類中引入了兩個輔助函數，第一個函數負責"清空"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;
}
第二個函數將單個點"
加"到AABB中，并在必要的時候擴展AABB
以包含每個點：
//---------------------------------------------------------------------------
// Add a point to the box
//---------------------------------------------------------------------------
void cAABB3::add(const cVector3& p)
{
// expand the box as necessary to contain the point
if(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;
}
現在，從一個點集創建矩形邊界框，可以使用下面的代碼：
Listing 12.1: Computing the AABB for a set of points
// Our list of points
const int n;
Vector3 list[n];
// First, empty the box
AABB3 box;
box.empty();
// Add each point into the box
for (int i = 0 ; i < n ; ++i)
box.add(list[i]);
取得AABB的頂點：
//--------------------------------------------------------------------------------------
// 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 range
return cVector3((i & 1) ? max.x : min.x,
(i & 2) ? max.y : min.y,
(i & 4) ? max.z : min.z);
}
其他的相關函數，具體功能詳見注釋：
//---------------------------------------------------------------------------
// Add an AABB to the box
//---------------------------------------------------------------------------
void cAABB3::add(const cAABB3& box)
{
// expand the box as necessary
if(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 axis
return (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 axis
return (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;
else
r.x = p.x;
if(p.y < min.y)
r.y = min.y;
else if(p.y > max.y)
r.y = max.y;
else
r.y = p.y;
if(p.z < min.z)
r.z = min.z;
else if(p.z > max.z)
r.z = max.z;
else
r.z = p.z;
return r;
}
AABB與邊界球
很多情況下，AABB比邊界球更適合于做定界球：
（1）計算一個點集的AABB，在編程上更容易實現，并能在較短的時間內完成。計算邊界球則困難得多。
（2）對實際世界里的許多物體，AABB提供了一種"更緊湊"的邊界。當然，對于某些物體，邊界球更好（設想一個本身就是球形的物體）。在極端情況下，AABB的體積可能僅相當于邊界球體積的1/2，大部分時候邊界球的體積會比矩形框的體積大得多，比較一下電線桿的邊界球和AABB就知道了。圖12.11所示為不同物體的AABB與邊界球的比較。
邊界球的根本問題是它的形狀只有一個自由度----半徑，而AABB卻有三個自由度----長、寬、高。因此，它可以調節這些自由度以適應不同物體。對圖12.11中的大部分物體，除了右上角的星形體外，AABB都比邊界球小。對這顆星，邊界球也僅比AABB略小一些。通過圖12.11，我們可以注意到AABB對物體的方向很敏感。比較下面兩支槍的AABB，圖中槍的大小都是相同的，只是方向不同而已；還應注意到在這一情況下邊界球大小相同，因為邊界球對物體方向不敏感。
變換AABB
當物體在虛擬世界中移動時，它的AABB也需要隨之移動。此時我們有兩個選擇----用變換后的物體來重新計算AABB，或者對AABB做和物體同樣的變換。所得到的結果不一定是軸對齊的（如果物體旋轉），也不一定是盒狀的（如果物體發生了扭曲）。不過，通過"變換后的AABB"進行計算要比通過"經過變換后的物體"計算AABB快得多，因為AABB只有8個頂點。
通過"變換后的AABB"計算不能只是簡單地變換8個頂點，也不能通過轉換原pmin和pmax來得到新的pmin和pmax ----這樣可能會導致xmin > xmax。為了計算新的AABB，必須先變換8個頂點，再從這8個頂點中計算一個新的AABB。
根據變換的不同，這種方法可能使新邊界框比原邊界框大許多。例如，在2D中，45度的旋轉會大大增加邊界框的尺寸，如圖12.12所示：
比較圖12.12中原AABB（灰色框）和新AABB（右邊較大的方框），它是通過旋轉后的AABB計算的，新AABB幾乎是原來的兩倍。注意，如果從旋轉后的物體而不是通過旋轉后的AABB來計算新AABB，它的大小將和原來的AABB相同。
可以利用AABB的結構來加快新的AABB的計算速度，而不必先變換8個頂點，再從這8個頂點中計算新AABB。
讓我們簡單回顧一下3x3矩陣變換一個3D點的過程：
設原邊界框為xmin，xmax，ymin...，新邊界框計算將得到x'min，x'max，y'min...。現在我們的任務就是想辦法加快計算x'min的速度，換句話說，我們希望找到m11x+m21y+m31z的最小值，其中[x, y, z]是原8個頂點中的任意一個，我們所要做的就是找出這些點經過變換后誰的x坐標最小。看第一個乘積：m11x，為了最小化乘積，必須決定是用xmin還是xmax來代換其中的x。顯然，如果m11>0，用xmin能得到最小化乘積；如果m11<0，則用xmax能得到最小化乘積。比較方便的是，不管xmin和xmax中哪個被用來計算xmin，都可以用另外一個來計算xmax。可以對矩陣9個元素中的每個都應用這個計算過程，如下列代碼所示：
//---------------------------------------------------------------------------
// 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 portion
min = 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;
}
}