在许多(如果不是全部的话)图形应用程序中，快速定位特定空间区域中的几何对象的能力非常重要。射线追踪器需要找到与射线相交的物体;在环境中导航的交互式应用程序需要找到从任何给定的视点可见的对象;游戏和物理模拟需要检测物体碰撞的时间和地点。所有这些需求都可以通过各种空间数据结构来支持，这些空间数据结构旨在组织空间中的对象，以便有效地查找它们。
在本节中，我们将讨论三种一般空间数据结构的示例。将对象组合在一起形成层次结构的结构是对象划分方案:对象被划分为不相连的组，但这些组可能最终在空间上重叠。将空间划分为不相交区域的结构是空间划分方案:空间被划分为单独的分区，但一个对象可能必须与多个分区相交。空间划分方案可以是规则的，将空间划分为形状均匀的小块;也可以是不规则的，将空间自适应地划分为不规则的小块，小块的物体更多更小。
在讨论这些结构时，我们将使用光线跟踪作为主要动机，尽管它们也可以用于视图剔除或碰撞检测。在第4章中，所有对象在检查交叉时都被循环遍历。对于N个对象，这是一个O(N)线性搜索，因此对于大型场景来说速度较慢。像大多数搜索问题一样，光线-对象的交集可以用“分治”技术在次线性时间内计算，前提是我们可以创建一个有序的数据结构作为预处理。有很多技术可以做到这一点。
本节将详细讨论其中三种技术:边界体积层次结构(Rubin & Whitted, 1980; Whitted, 1980; Goldsmith & Salmon, 1987)，统一空间细分(Cleary, Wyvill, Birtwistle, & Vatti, 1983; Fujimoto,Tanaka, & Iwata, 1986; Amanatides & Woo, 1987))和二进制空间分区(Glassner, 1984; Jansen, 1986; Havran, 2000)。前两种策略的示例如图12.24所示。
在大多数相交-加速方案中，一个关键操作是计算带有边界框的射线的相交(图12.25)。这与传统的交点测试不同，我们不需要知道光线在哪里击中方框;我们只需要知道它是否击中方框。
为了构建射线盒交点的算法，我们首先考虑一个方向向量具有正x和y分量的2D射线。稍后我们可以将其推广到任意3D射线。二维包围框由两条水平线和两条垂直线定义：
$$ x=x_{min},x=x_{max},y=y_{min},y=y_{max} $$
被这些直线所包围的点可以用区间表示为：
$$ (x,y)\in[x_{min},x_{max}]*[y_{min},y_{max}] $$
如图12.26所示，相交测试可以通过以下几个区间进行。首先，我们计算光线与$x=x_{min}$交点对应的参数t值：
$$ t_{xmin}=\frac{x_{min}-x_e}{x_d} $$
我们同样可以计算出$t_{xmax},t_{ymin},t_{ymax}$。当且仅当区间$[t_{xmin},t_{xmax}]$与$[t_{ymin},t_{ymax}]$区间重叠时，光线与边界盒子相交。伪代码如下所示：
if (xd >= 0) then
txmin = (xmin - xe) / xd
txmax = (xmax - xe) / xd
else
txmin = (xmax - xe) / xd
txmax = (xmin - xe) / xd
对于y的情况，必须进行类似的代码展开。一个主要的问题是水平射线和垂直射线的yd和xd值分别为零。这将导致除零，这可能是一个问题。然而，在直接解决这个问题之前，我们检查IEEE浮点计算是否为我们优雅地处理了这些情况。回想一下第1.5节中被零除的规则:对于任何正实数a,
$$ +a/0=+\infty; $$
$$ -a/0=-\infty; $$