外壳和效率

射线投射符合解决问题的蛮力方法。最小算法很简单，特别是考虑到它的许多应用程序和易用性，但是应用程序通常会投射很多光线。可以投射数百万条光线以渲染动画电影的单个帧。计算机处理时间随着屏幕分辨率和合成物中原始实体/表面数量的增加而增加。

通过在构图树中的实体周围使用最小边界框，对射线-固体相交的穷举搜索类似于有效的二分搜索。蛮力算法会进行详尽的搜索，因为它始终会访问树中的所有节点（将射线转换为图元的局部坐标系，测试射线与曲面的交点并组合分类），即使射线明显错过了实体也是如此。为了检测“明显遗漏”，一种更快的算法使用二进制合成树作为实体合成所占空间的层次表示。但是所有位置，形状和大小信息都存储在原始实体所在的树的叶子处。树中的顶部和中间节点仅指定合并运算符。

用外壳表征所有实体填充的空间，从而为树中的所有节点提供位置和尺寸信息的抽象摘要。然后，快速的“射线相交外壳”测试将指导分层中的搜索。当测试在树中的中间节点失败时，可以确保将射线分类为复合射线，因此无需递归向下子树进行进一步研究。

准确评估使用外壳的成本节省是困难的，因为它取决于基元的空间分布（复杂性分布）和组成树的组织。最佳条件是：

• 没有原始的外壳在空间上重叠
• 构图树是平衡且有组织的，因此空间中附近的子实体也位于树中

相反，最坏的情况是：

• 所有原始外壳相互重叠

以下是Roth关于射线投射的论文中进行的其他性能改进，但随后其他人也进行了相当大的改进。

• 早期出局。如果树中某个复合节点处的运算符为–或＆且光线被分类为该复合物体的左子实体之外的光线，则该光线将被分类为该复合物之外的物体，而与该光线相对于右子实体的分类无关。固体。因此，没有必要针对正确的子实体对射线进行分类，因此应避免效率。

• 转变。通过最初将屏幕到场景变换与图元的场景到局部变换结合起来，并将结果的屏幕到局部变换存储在图元的数据结构中，可以消除每个射线表面交点的一个射线变换。

• 递归。给定一棵深层的合成树，结合分配和释放内存，递归可能会很昂贵。可以使用静态数组作为堆栈来模拟递归。

• 动态边界。如果仅显示实体的可见边缘，则射线投射算法可以动态绑定射线以切断搜索。也就是说，在发现光线与子实体相交之后，该算法可以使用最接近屏幕的交点来收紧“光线交点箱”测试的深度范围。从顶部开始，这仅适用于树的+部分。使用–和＆，射线的附近“内”部分可能稍后变为“外”。

• 连贯性。相干原理是在两个相邻像素处可见的表面更可能是相同的而不是不同的。计算机图形和视觉系统的开发人员已将此经验性事实应用于效率和性能。对于线条图，包含边缘的图像区域通常比总图像区域小得多，因此射线投射应集中在边缘周围，而不是在开放区域中。通过用射线稀疏地采样屏幕，然后在相邻的射线标识不同的可见表面时，通过二进制搜索来定位边缘，可以有效地实现这一点。