包圍體
在計算機圖形學與計算幾何領域，一組物體的包圍體就是將物體組合完全包容起來的一個封閉空間。將複雜物體封裝在簡單的包圍體中，就可以提高幾何運算的效率。通常簡單的物體比較容易檢查相互之間的重疊。
一組物體的包圍體也是包含一個物體及周圍相關環境的封閉空間，因此可以用它來表示一個非空、有限的單一物體。
包圍體的使用
[編輯]包圍體經常用於加速一些特定的檢驗過程。
在光線跟蹤中，包圍體用於光線相交檢驗，在許多渲染算法中，它又用於視體的檢驗。如果光線或者視體與包圍體沒有交叉，那麼就不會與包圍體內的物體相交。通過這樣的相交檢驗，就可以生成需要顯示的物體列表。這裡的顯示表示需要渲染或者柵格化。
在碰撞檢測中，如果兩個包圍體沒有相交，那麼所包含的物體也就不會碰撞。
由於包圍體的幾何形狀較為簡單，而物體通常是多邊形或者簡化為多邊形近似的數據結構所組成，所以對於包圍體的檢驗通常要比對於物體本身的檢驗速度更快。在其中任一種場合下，如果物體不可見的話，那麼根據視體對每個多邊形的檢驗都是無用的計算。不管物體表面是否真的可見，屏幕上的物體必須裁剪到屏幕能夠顯示的區域。
為了得到複雜物體的包圍體，一種常用的方法是用場景圖或者如OBB樹這樣更加專業的包圍體層次工具對物體或者場景進行分解。這種做法的基本思想就是將場景組織成一個樹狀結構，根節點是整個場景，每個葉節點包括一個簡單的局部。
包圍體的常見類型
[編輯]一個應用程序中的包圍體類型的選擇受到不同的因素影響：計算物體包圍體所需的計算開銷、物體移位、形狀或者尺寸發生變化時在程序中更新所需開銷以及相交檢驗所需精度。通常使用幾種類型的組合，例如用來快速、大致檢驗的便宜方法與精確費用較高的方法組合在一起使用。
這裡討論的都是凸包圍體，如果被包圍的物體是凸的，那麼這就不算一個限制；如果需要處理非凸包圍體的話，可以將它們表示為一組凸包圍體的集合然後進行處理。不幸的是，隨着包圍體的複雜性增加，相交檢驗所耗費用也隨之大幅度地增加。
包圍球是一個包容物體的球面。在二維圖形中，這是一個圓，包圍球就用圓心及半徑進行表示。包圍球的碰撞檢測速度非常快：當兩個球心距離不超過半徑之和時就會相交。這樣包圍球就可以用於物體可以向任意方向移動的場合。
包圍柱是包容物體的圓柱，在多數應用程序中圓柱的軸與場景豎直方向相同。圓柱是只能繞着縱向軸旋轉三維物體，而不能繞着其它軸線旋轉，或者只能進行平移。兩個軸線為豎直方向的圓柱只有當它們在豎直軸上的投影（即兩條線段）以及在水平方向的投影（即兩個圓）同時相交的時候，它們才相交。在視頻遊戲中，包圍柱經常作為直立人物的包圍體使用。
包圍盒是一個包容物體的立方體或者二維長方形。在動態仿真中，對於大致是立方體的物體需要相當高的相交檢驗精度時，包圍盒就優於包圍球或者包圍柱。這樣做的效果是很明顯的，例如地面上停放的汽車這種一個物體放在另外一個物體上的場合：用包圍球處理就會得到汽車與地面相交的結果，但是經過更加複雜的對於汽車模型的檢驗就會發現事實並非這樣；包圍盒立即就可以發現汽車與地面不相交，這樣就可以節省花費較大的檢驗。
在許多應用程序中，包圍盒按照坐標系的坐標軸進行排列，這被稱為按坐標軸排列的包圍盒（AABB）。為了將 AABB 與通用的情況進行區分，有時將任意的包圍盒稱為定向包圍盒（OBB）。AABB 檢驗物體的相交要比 OBB 更加簡單，但是它的缺點是當模型旋轉的時候無法隨之旋轉，而必須重新進行計算。
離散定向多面體（DOP）是一般化的 AABB。DOP 是一個包含物體的二維空間的凸多邊形或者三維空間的凸多面體，它是一組無限遠的定向平面移動到與物體相交而得到，於是 DOP 就是這些平面相交平面所生成的凸多面體。三維圖形中構建 DOP 的流行方法有從 6 個按照坐標軸排列的平面得到的按坐標軸排列的包圍盒，以及 10 （豎直邊上取斜面）、18（所有邊取斜面）或者 26 個平面（所有邊及定點上取斜面）得到的斜面包圍盒。從 k 個平面構建的 DOP 稱為 k-DOP；但是由於一些表面可能會縮減到一條邊或者一個定點，所以實際的表面數目可能會少於 k。 凸包是包容物體的最小凸體。如果物體是有限個點的集合，那麼凸包就是一個多面體，實際上它是包容多面體的最小立體。
基本的相交檢驗
[編輯]對於一些包圍體來說，如 OBB 以及凸多面體，一個有效的檢驗方法是 分離軸定理。其思路是如果存在一個與物體不重疊的軸，那麼物體就不相交。通常檢驗的軸 是包圍體的基本軸（AABB 中的單位軸或者 OBB 中的三個基軸）。並且經常要隨後檢查這些軸的外積.
在 AABB 中，這個檢驗過程變成了一組簡單的單位軸的重疊檢驗。一個 M、N 定義的 AABB 與另外一個 O、P 定義的 AABB 滿足下面的條件時二者不相交： (Mx>Px) 或者 (Ox>Nx) 或者 (My>Py) 或者 (Oy>Ny) 或者 (Mz>Pz) 或者 (Oz>Nz)。
AABB 也可以投影到一個坐標軸，如果邊長為 L 以 C 為中心，那麼沿 N 軸投影之後得到：
r=0.5Lx|Nx|+0.5Ly|Ny|+0.5Lz|Nz|, 並且 b=C*N 或者 b=CxNx+CyNy+CzNz, 並且 m=b-r, n=b+r
其中 m 與 n 分別是最小與最大值。
在這方面 OBB 與之類似，但是 OBB 較為複雜。對於有如上 L 與 C 以及基軸 I、J、K 的 OBB 來說，有：
r=0.5Lx|N*I|+0.5Ly|N*J|+0.5Lz|N*K|
m=C*N-r且n=C*N+r
對於範圍 m、n 以及 o、p 來說，如果 m > p 或者 o > n 那麼它們就不相交。這樣，通過將兩個 OBB 的範圍沿着每個 OBB 的 I、J、K 軸進行投影並且檢驗相交性，就可以得到物體的相交性。另外通過檢驗這些坐標軸的叉積 I0×I1、 I0×J1 等，就可確定物體並不相交。
這種通過坐標軸投影確定相交性的方法也可以用於凸多面體，但是要用多面體的法向量代替基軸、用每個頂點點積的最大值與最小值取代坐標軸。需要注意的是這個描述表示的是在世界坐標系中進行檢驗。
