包围体

在计算机图形学与计算几何领域，一组物体的包围体就是将物体组合完全包容起来的一个封闭空间。将复杂物体封装在简单的包围体中，就可以提高几何运算的效率。通常简单的物体比较容易检查相互之间的重叠。

一组物体的包围体也是包含一个物体及周围相关环境的封闭空间，因此可以用它来表示一个非空、有限的单一物体。

包围体的使用

包围体经常用于加速一些特定的检验过程。

在光线跟踪中，包围体用于光线相交检验，在许多渲染算法中，它又用于视体的检验。如果光线或者视体与包围体没有交叉，那么就不会与包围体内的物体相交。通过这样的相交检验，就可以生成需要显示的物体列表。这里的显示表示需要渲染或者栅格化。

在碰撞检测中，如果两个包围体没有相交，那么所包含的物体也就不会碰撞。

由于包围体的几何形状较为简单，而物体通常是多边形或者简化为多边形近似的数据结构所组成，所以对于包围体的检验通常要比对于物体本身的检验速度更快。在其中任一种场合下，如果物体不可见的话，那么根据视体对每个多边形的检验都是无用的计算。不管物体表面是否真的可见，屏幕上的物体必须裁剪到屏幕能够显示的区域。

为了得到复杂物体的包围体，一种常用的方法是用场景图或者如这样更加专业的包围体层次工具对物体或者场景进行分解。这种做法的基本思想就是将场景组织成一个树状结构，根节点是整个场景，每个叶节点包括一个简单的局部。

包围体的常见类型

一个应用程序中的包围体类型的选择受到不同的因素影响：计算物体包围体所需的计算开销、物体移位、形状或者尺寸发生变化时在程序中更新所需开销以及相交检验所需精度。通常使用几种类型的组合，例如用来快速、大致检验的便宜方法与精确费用较高的方法组合在一起使用。

这里讨论的都是凸包围体，如果被包围的物体是凸的，那么这就不算一个限制；如果需要处理非凸包围体的话，可以将它们表示为一组凸包围体的集合然后进行处理。不幸的是，随着包围体的复杂性增加，相交检验所耗费用也随之大幅度地增加。

是一个包容物体的球面。在二维图形中，这是一个圆，包围球就用圆心及半径进行表示。包围球的碰撞检测速度非常快：当两个球心距离不超过半径之和时就会相交。这样包围球就可以用于物体可以向任意方向移动的场合。

是包容物体的圆柱，在多数应用程序中圆柱的轴与场景竖直方向相同。圆柱是只能绕着纵向轴旋转三维物体，而不能绕着其它轴线旋转，或者只能进行平移。两个轴线为竖直方向的圆柱只有当它们在竖直轴上的投影（即两条线段）以及在水平方向的投影（即两个圆）同时相交的时候，它们才相交。在视频游戏中，包围柱经常作为直立人物的包围体使用。

包围盒是一个包容物体的立方体或者二维长方形。在中，对于大致是立方体的物体需要相当高的相交检验精度时，包围盒就优于包围球或者包围柱。这样做的效果是很明显的，例如地面上停放的汽车这种一个物体放在另外一个物体上的场合：用包围球处理就会得到汽车与地面相交的结果，但是经过更加复杂的对于汽车模型的检验就会发现事实并非这样；包围盒立即就可以发现汽车与地面不相交，这样就可以节省花费较大的检验。

在许多应用程序中，包围盒按照坐标系的坐标轴进行排列，这被称为按坐标轴排列的包围盒（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 等，就可确定物体并不相交。

这种通过坐标轴投影确定相交性的方法也可以用于凸多面体，但是要用多面体的法向量代替基轴、用每个顶点点积的最大值与最小值取代坐标轴。需要注意的是这个描述表示的是在世界坐标系中进行检验。

外部链接
Illustration of several DOPs for the same model, from epicgames.com

几何算法
三维计算机图形学