用于降低计算次数的区间算法在射线跟踪问题中的应用

具体实施方式

以下详细描述涉及附图。在不同的附图中，相同的参考标号可用于表示相同或相似的要素。在以下描述中，为了解释而非限制的目的，阐述了诸如特定结构、体系结构、接口、技术等具体细节，以提供对所要求的发明的各个方面的充分理解。然而，对从本公开获益的本领域技术人员来说，很显然，所要求的发明的各个方面可以在脱离这些具体细节的其它示例中实现。在某些实例中，省略了对公知设备、电路和方法的描述以免不必要的细节使本发明的描述变得不清晰。

实施例提供了依靠应用的所选几何性质的射线跟踪遍历，以降低在各个遍历步骤期间要求的浮点(或其它的数据类型操作诸如：整数、定点)操作的数量。区间遍历算法不依赖于组中的射线数目。多级遍历方案可以实现，这开始于在组中的大量射线并然后按需要减少它以维持组相干性。在遍历期间可以产生附加的射线来改进高几何复杂度的区域中产生的图象的反锯齿性质。区间遍历算法组并行几何查询，提取所选的与整个组相关的公共几何特性，然后仅使用这些特性(而不是整个组)来执行查询。射线跟踪整体上基于并行几何查询，所述查询针对某种空间排序的几何数据库来执行。区间遍历算法可被扩展以覆盖其它类型的应用，其中可能针对专用数据库发现并跟踪某些组性质。本领域的技术人员会认识到本发明的实施例不限于浮点实现方式。而是，本发明的实施例发明可以用各种数据类型来实现，所述数据类型包括但不限于整数、定点等。

图1说明了用于遍历二进制树的从公共起点106出发通过单元104的所跟踪的多条射线102的示例100。一个单元104由分割平面P0分割为包括最近单元C0 108和最远单元C1 110的两个子空间。射线102可被发射通过屏幕上的像素而进入表示某个场景内的所有对象的数据库中。这些(适当细分的)对象和数据可以表示空的空间，并且可按分级空间划分结构来存储。发射射线102包括：对射线102通过该结构可采用的路径进行跟踪。并行的可能性存在但有限，因为各条射线可以采用不同的路径来通过该数据库，并且由于数据结构是分级的，因此在射线从一级进入下一级时，存在顺序依赖性。

数据库可以将对象的分布和空的空间表示为轴对准空间区间的集合。射线的集合可以针对数据库分级结构的任意级别(即没有必要从顶部开始)来直接测试。从该结构向下行进的射线束可被细分。

这引发了数值保真度的改进并简化了跟踪射线的过程。特别是，降低了每条射线所要求的操作的数量，从而引发总体应用性能的改进。此外，硬件可以设计成直接实现这种区间算法，从而允许附加的性能改进。射线的发射不是图形学特有的，类似的技术同样可以用来跟踪各种类型的波的传播，从而为军事目的来计算雷达截面，等等。

在射线跟踪环境中，可能要求发射许多条射线。完成该操作的一种方式是确定所有射线与定义场景中的所有几何对象的所有多边形的交点。

完成该操作另一种方式是将所有的这些多边形划分成轴对准的划分结构。这种方式的一个实现方式是将整个场景分割成均一立方体格，同时复制跨立方体边界的多边形。射线可被发射并且该射线通过的立方体可被预测。该射线仅针对这些立方体的每一个的内容来测试，而忽略其余的因素。由于使用这样的表示相对于对每个多边形测试每条射线的相对功效，术语“加速结构”可用于描述设计用来降低射线-多边形交点测试的总数量的任何这样的数据结构。

上述的均一立方格具有以下优点：可以容易地计算射线通过立方体的轨线，以及可以直接访问相关的数据。但是该场景中的细节可能不是均匀分布的。例如，大量的多边形可能在一个立方体中结束，而非常少的细节在其它立方体中结束。

另一个加速结构构造一般被称作kd-树。在这种加速结构中，一些成本函数可以用于通过轴-对准的平面来递归地分割场景。最初，该场景可以由这样的平面分割成两个，然后每一半又可以沿着某个其它平面分割，等等。这产生了该结构的分级组织。加速结构的各个级别可以被递归地遍历以确定在哪里可以发现该结构的下一个级别。在这些结构的构造阶段中仔细地选择成本函数以达到最优的性能，同时当发射可视化需要的各种射线时稍后遍历这些树。

kd-树的叶节点表示小的轴对准的单元，其中有某个数量的多边形。在沿树向上的下一个级别，各个节点表示由叶节点中的两个节点完全填满的轴对准的框(“分割-平面”将较大体积分割成两个叶单元)。在下一个级别，各个节点表示由使用类似的分割-平面等的较低级别的节点中的两个节点完全填满的轴对准的框。不要求树是平衡的，即任何内部节点可以分割成叶节点和另一个内部节点。在任何给定的级别，射线可以与有界框相交以确定是否：(1)该射线完全未命中该框，(2)射线击中该框并通过“左”子节点，即达到分割-平面的“左”边，(3)射线击中该框并通过“右”子框，或(4)射线击中并通过两个子框。在第一种情况(1)下，不再需要进一步处理较低级别的节点，因为射线“未命中”该树的整个较低部分。

本发明的实施例适用于许多加速结构，包括使用分离平面确定哪些对象必须针对特定射线来测试的那些加速结构。这些加速结构包括但不限于格、有界框和kd-树。

参照图1，对于任何给定的射线块，遍历算法确定射线102是否：

(1)通过子空间108到分割-平面104的左边；

(2)通过子空间110到分割-平面104的右边；或

(3)通过子-空间108和110。

在二进制树的整个遍历期间，对各条射线102，单元入口和出口点是已知的。这些是由从先前的计算中已知的oa，ob，oc，od以及oA，oB，oC，oD表示的距离。计算与分割-平面P₀的交点。它们表示为距离oα，oβ，oχ，以及oδ。入口和出口距离与平面交点进行比较。例如，参照图1，射线oa和ob将仅通过左单元108，而射线oc和od通过两个单元108和110。对于射线通过的各个后续单元重复进行该过程。

如果算法要求单元108和110的射线遍历，那么所有关于最远单元(如110)的信息，都存储在类似堆栈的结构中。具体地说，所述信息包括：到入口点oχ和oδ以及出口点oC和oD的距离。首先通过对入口点a，b，c和d以及出口点A，B，χ和δ执行当前过程的所有步骤来递归地遍历最近的单元108。一旦已经遍历了最近的一个单元中的所有单元，就从堆栈中检索最远的单元数据110并且重复整个过程。

如果一些单元包含原始对象(例如三角形)，那么针对这些对象来测试通过这个单元的剩余射线。例如，进行射线/三角形交点测试。

在一些情况下，对于各条射线，已经发现某个原始对象，到该原始对象的距离小于到当前单元的距离。在这种情况下，后续的遍历步骤不是必须的。如果射线跟踪用于渲染的目的，那么若这样的原始对象是不透明的，则可以使用细化。

图2说明了用于二进制树的区间遍历的从公共起点206出发通过单元204的所跟踪的多条射线202的示例200。图2示出了在单元分割后的下一个遍历步骤。特别是，图1示出了一个单元由分割-平面P₀分割成两个子空间C₀ 108和C₁ 110的情况。在图2中，C₀ 208被进一步分割成C₀₀ 210和C₂ 212与C₃ 214的结合。没有射线202与最近的子空间C₀₀ 210相交。

区间遍历算法在对一组射线计算和维持单个区间的基础上建立，其中单个区间包括从所选的点(照相机位置)到特定单元的束中的所有的射线的最小和最大距离。代替将单独射线表示为指向特定方向的3D向量，射线的集合可以表示为近似指向某个特定方向的区间的单个3D向量。通常，这些射线越相干，区间就可能会越紧密。对各个坐标x，y和z，这个区间可以定义为所有射线中的最小和最大坐标值。同样，加速结构的单独单元可以表示为在x，y和z中的区间。在分级加速结构的任何级别上的单元可以表示为这样的区间。在对加速结构进行较深的遍历时，表示一组射线的区间的向量可以针对效率来细分成多组射线。通常在加速结构中的较深处发现较高程度的射线相干性。

图3是流程图，说明了二进制树的区间遍历的过程300。虽然为了便于说明，过程300可针对图2来描述，但是所要求的发明并不限于此。在每个遍历步骤中执行一次图3的动作302、304和306，同时对各个遍历单元执行动作308-316。

在动作302中，产生一组射线并计算该组射线的一些公共特性。对于那些从特定公共起点例如照相机位置o产生，通过具有像素p_xy的屏幕的射线，对各个坐标轴计算以下各项：

--在动作304中，计算在任何给定轴上的方向向量op_xy的所有投影中的最小和最大距离值。通过定义，对于该组中的每条射线，op_xy向量的x、y和z坐标将在合适的区间内。在顶部单元遍历开始时(动作304)，确定最小和最大距离oa₁和oA₁。这些可以指定为区间[oa₁，oA₁]。在剩余的遍历过程中维持并可能修改(缩小)这个区间。通过定义，对于该组中的任何射线，到最近单元入口点的距离不小于oa₁且到最远单元出口点的距离小于或等于oA₁。

在动作306中，定义反向区间。

在动作308中，可以使用在动作306中定义的反向区间来计算到分割平面的最小和最大距离od_min和od_max。

如图2所示，由平面P₂分割子单元C₂212和C₃214。确定是否遍历了子单元C₂212和C₃214。具体地说，这通过评估以下两个条件来确定，如果满足所述条件，则导致仅遍历了一个子单元：

--在动作310中，如果到单元(oa₁)的最小距离大于到平面(oA₂)的最大距离，则修改[oa1，oA1]区间并仅遍历右子单元(动作312)。

--在动作314中，如果到单元(oA₁)的最大距离小于到平面(oa₃)的最小距离，则修改[oa1，oA1]区间并仅遍历左子单元(动作316)。

如果这些条件都不满足，则必须遍历两个子单元(动作318)并必须修改适当的区间。如图2中所示的，在C₂遍历的期间，区间将是[oa₁，oA₂]。对单元C₃，区间将是[oa₃，oA₁]。

本领域的技术人员会认识到本文描述的区间遍历实施例可能有不同的实施方式。例如，所描述的实施例可以扩展到没有公共起点的射线组。虽然过程300可以在现代向量或SIMD(单指令多数据)机器上实现，但是所要求的发明不限于此。

当然，区间遍历算法可以有不同的实现方式。上文提供的一个实现方式仅用于陈述的目的，以及在所提供的附图上展示特定的情况。同样有可能将这里略述的思想扩展到射线束的更一般的情况，其中射线束没有公共起点。以下的观察有助于理解在完全和区间遍历算法之间的差异。完全算法基本上实现特定射线组的同时边界框裁剪(clipping)。对在加速结构中到达的任何给定的单元，所有射线的入口和出口点是已知的。图3中所示的区间算法表示懒惰分布的框裁剪，对整个射线组产生确保的最小和最大裁剪距离。

本发明的实施例可以急剧降低在各个遍历步骤中要求的浮点或其它数据类型的操作的数量。与完全遍历算法不同，区间遍历算法不依赖于组中的射线数。可实现多级遍历方案，以组中的大量射线开始并且然后按需要来减少射线量以维持组相干性。区间遍历算法，如果用硬件实现或支持，则可实现由设备消耗的功率的急剧降低，以及提高总体性能。射线跟踪整体上基于并行几何查询，所述查询针对某种空间排序的几何数据库来执行。区间遍历算法包括以下步骤：对这样的查询进行分组，提取与整个组相关的某些公共几何特性，然后仅使用这些特性(而不是整个组)来执行查询。这样，区间遍历方法可被扩展以覆盖其它类型的应用，其中有可能针对专用数据库来发现和跟踪某些组性质。

虽然系统被描述为包括离散部件，但是这些部件可以用硬件、软件/固件或它们的某种结合来实现。当用硬件实现时，系统的一些部件可以结合到某种芯片或设备中。

虽然已经讨论了若干示范性实施方式，但是所要求的发明不应当限于那些明确提到的内容，而是应当包括任何设备或接口，所述设备或接口包括一个以上能够处理、发射、输出或存储信息的处理器。例如，可以用可由本地系统的处理器或另一个部分执行的软件来实现那些过程。

虽然对符合本发明原理的一个或多个实施方式的前面描述提供了说明和描述，但是其目的不是穷举性的或者将本发明的范围限于所公开的精确形式。根据上述教导可能想到一些修改和变化，或可以从本发明的各种实现方式的实施中获得这些修改和变化。

本申请的描述中使用的元件、动作或指令都不应当解释为对本发明是关键的或必要的，除非明确地这样描述。同样，如本文使用的，冠词“一”旨在包括一个或多个项目。可在基本不背离本发明的精神和原理的前提下，对所要求的发明的上述实施方式进行变化和修改。本文中，所有这样的修改和变化都是要包括在本公开的范围内并通过以下权利要求来保护。