射线投射

射线投射是3-D CAD / CAM实体建模和图像渲染的方法学基础。它与计算机图形的光线跟踪（图形）基本相同，在计算机图形中，虚拟光线是在从照相机的焦点到照相机传感器中每个像素的路径上“投射”或“跟踪”，以确定沿摄影机可见的光线。在3D场景中发出光线。1978年至1980年，斯科特·罗斯（Scott Roth）在通用汽车研究实验室（General Motors Research Labs）引入了“射线铸造”一词。他的论文“用于实体建模的射线投射”，使用集合运算符并集（+），交集（＆）和差值（-），通过组合原始实体（例如块和圆柱体）来描述建模的实体对象。使用这些二元运算符进行实体建模的总体思路很大程度上是由于Rochester大学的Voelcker和Requicha的几何建模小组所致。

在进行射线投射（和射线跟踪）之前，计算机图形算法将3D世界中的表面或边缘（例如线条）投影到必须应用可见性逻辑的图像平面上。世界到图像的平面投影是3-D齐次坐标系变换（aka：3D投影，仿射变换或投影变换（Homography）。以这种方式渲染图像很难通过隐藏的表面/边缘去除来实现。另外，必须明确解决曲面的轮廓问题，而曲面轮廓是射线投射的隐​​式副产品，因此无论何时视图发生变化，都无需明确解决。

射线投射极大地简化了3D对象和场景的图像渲染，因为线会转换为线。因此，不是将3D场景中的弯曲边缘和曲面投影到2D图像平面，而是将变换后的线（射线）与场景中的对象相交。齐次坐标变换由4x4矩阵表示。数学技术是计算机图形学和几何建模所共有的。变换包括围绕三个轴的旋转、沿轴的独立缩放，3-D平移甚至倾斜。转换可通过矩阵算术轻松连接。对于4x4矩阵，点由[X，Y，Z，1]表示，方向矢量由[D _x、D _y和D _z、0]。（第四个术语用于翻译，不适用于方向向量。）

在简化数学的同时，射线投射算法非常耗费计算机处理能力。Pixar拥有大型渲染场，这些大楼拥有1000个CPU，可以使用光线跟踪（又称为“光线投射”）作为核心技术来制作动画。

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

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

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

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

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

相反，最坏的情况是：

• 所有原始外壳相互重叠

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

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

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

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

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

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

有关射线投射的历史，请参见射线追踪（图形），因为两者基本上是同一件事。斯科特·罗斯（Scott Roth）在听说“射线追踪”之前就发明了“射线投射”一词。斯科特·罗斯（Scott Roth）在通用汽车研究实验室（GM Research Labs）进行射线投射的开发与特纳·惠特（Turner Whitted）在贝尔实验室的射线追踪工作同时进行。

著名的电子游戏Wolfenstein 3D中的世界是由正方形的，均匀高度的墙与纯色的地板和天花板相交构成的。为了绘制世界，对屏幕像素的每一列都跟踪一条光线，并选择垂直的墙壁纹理切片，并根据光线在世界上的位置以及在行进之前的传播距离进行缩放。

基于网格的级别的目的是双重的-可以更快地发现射线壁碰撞，因为潜在的碰撞变得更加可预测，并且减少了内存开销。但是，对宽阔区域进行编码会占用额外的空间。

由NovaLogic为Comanche游戏开发的Voxel Space引擎通过屏幕像素的每列追踪光线，并针对高度图中的点测试每条光线。然后，它将高度图的每个元素转换为一列像素，确定它们是可见的（也就是说，未被前面绘制的像素所遮挡），然后从纹理图中以相应的颜色绘制它们。

在计算几何中，射线投射问题也称为射线射击问题，可以表述为以下查询问题：给定d维空间中的一组对象，将它们预处理为数据结构，以便对于每个查询射线，可以很快找到被射线击中的初始物体。已经针对各种设置对问题进行了研究：空间尺寸、对象类型、对查询射线的限制等。一种技术是使用稀疏体素八叉树。