包围体层次结构的可扩展并行构建的制作方法

包围体层次结构的可扩展并行构建
1.相关申请的交叉引用
2.本技术要求2021年10月18日提交的并且具有序列号63/256,897的标题为“用于可扩展并行包围体层次结构构建的技术(techniques for scalable parallel bounding volume hierarchy construction)”的美国临时专利申请的权益，并且要求2022年2月10日提交的并且具有序列号17/669,293的标题为“包围体层次结构的可扩展并行构建(scalable parallel construction of bounding volume hierarchies)”的美国专利申请的权益。这些相关申请的主题通过引用合并于本文中。
技术领域
3.本公开的实施例总体上涉及计算机科学和计算机图形，并且更具体地涉及包围体层次结构的可扩展并行构建。


背景技术：

4.包围体层次结构(bvh)是用于在空间上组织图形场景或空间的另一表示中的点、三角形、多边形、网格或其他类型的对象的通用层次结构数据结构。bvh通常包括具有多级节点的树结构。树结构中的每个节点表示特定的“包围体(bounding volume)”，其是包含(即，界定)对象中的一些或全部的空间区域。树结构中的根节点表示包含(即，界定)所有对象的单个空间，并且树结构中的给定节点的子节点表示由节点表示的包围体到更小的非重叠包围体的分区。树结构中的叶节点因此表示对象被分组或被组织到其中的最小包围体。每个叶节点另外存储落入对应包围体内的一组对象。
5.在为给定组的对象生成bvh之后，bvh中的树结构可以用于加速与对象相关的各个空间查询。可以在渲染包括该组对象的图形场景、涉及该组对象的模拟、和/或与这些对象相关的其他类型的处理或分析期间执行这些空间查询。例如，可以遍历树结构以确定在光线追踪操作期间首先由光线撞击的点或对象。在另一示例中，由树结构中的节点表示的包围体可以用于检测图形场景或模拟中的虚拟对象之间的碰撞。
6.在生成bvh时，一般采用自上而下的方式构建树结构，从根节点开始，向下递减到叶节点。在树结构中的给定父节点处，由父节点表示的包围体被分割成两个或更多个不相交的包围体。表示不相交的包围体的两个或更多个节点也被创建为父节点的子节点。由父节点表示的包围体还可以“自适应地”被分割为由子节点表示的包围体，其方式为考虑对象在包围体中的空间分布。例如，自上而下bvh构建技术可计算每一对象的代表点作为对象的形心和/或对象的包围盒(bounding box)的形心。自上而下bvh构建技术还可确定包围盒，指派给父节点的所有对象的代表点适合该包围盒。自上而下bvh构建技术可选择沿其分割包围盒的轴线，并且可选择沿该轴线的一个或更多个分割平面，该一个或更多个分割平面将包围盒划分成与子节点相关联的两个或更多个包围体。每个分割平面可以基于轴线的长度、分割平面与对象之间的重叠量、与遍历bvh以执行给定任务相关联的成本、和/或使包围体的分区适应各个参数或因素的其他启发法来选择。自上而下bvh构建技术可继续将bvh中
的不同节点递归地分割成附加子节点，直至与给定节点相关联的对象的数量降至阈值以下和/或直至满足另一条件。
7.上述自适应自上而下方法的一个缺点是与这个方法相关的操作难以并行化。具体地，在bvh的给定级别处执行的分割操作的数量和与计算分区相关联的计算开销随时间而改变，从而使得并行化变得困难。更具体地，自上而下方法开始于与生成少量节点和每个节点的大量对象的分区相关的操作。随着自上而下方法的进展，对增加数量的节点和每个节点的减少数量的对象执行分割操作。因此，大量的线程和/或处理器通常用于分割bvh的根节点附近的各个节点，而单个线程通常用于划分bvh的叶节点附近的各个节点。在根节点与叶节点之间，在给定节点上操作的线程和/或处理器的数量通常基于在bvh的给定级别的节点的数量和与该节点相关联的对象的数量而变化。
8.上述自适应自上而下方法的另一个缺点是树结构中的每个节点通常维护被分组在由该节点所表示的包围体之下的对象的列表。因此，必须为每个列表分配存储器，并且必须将指派给给定父节点的对象列表分割成相应子节点的子列表。随着bvh的建成，存储器分配必须适应列表的数量(例如，靠近根节点的少量列表和靠近叶节点的大量列表)和每个列表的大小(例如，靠近根节点的大列表和靠近叶节点的小列表)的改变。进一步，将列表划分为子列表招致资源开销，资源开销为给定列表的大小和在树结构的给定级别处待分割的列表的数目两者的函数。
9.如前所述，在本领域中所需要的是用于生成包围体层次结构的更有效的技术。


技术实现要素：

10.本发明的一个实施例阐述了一种用于生成包围体层次结构(bvh)的技术。所述技术包括确定与第一节点相关联的第一组对象。所述技术还包括生成与第一节点相关联的第一多个子节点。该技术还包括：对于第一组对象中包括的每个对象，基于与第一组对象相关联的第一组分区将第一多个子节点中包括的对应子节点的标识符存储在对象内。
11.相对于现有技术，所公开的技术的一个技术优点是，通过所公开的技术，相同的内核用于处理bvh内的各个节点和对象，而不管这些节点和对象驻留在bvh内的层级如何。因此，相对于必须将用于处理各个节点的线程或处理器的数量适配于在bvh的给定级别处执行的分割操作的数量和复杂度的常规方法，可以更容易地实现所公开的技术。所公开的技术的另一技术优势在于，通过简单地改变存储在对象中的节点标识符，对象被“移动”到bvh内的不同节点。因此，所公开的技术比现有技术方法计算效率更高，在现有技术方法中，必须维护指派给bvh中的各个节点的不同对象的各个列表。这些技术优点提供了优于现有技术方法的一个或更多个技术改进。
附图说明
12.为了更详细地理解上述各种实施例的相关特征，可以通过参考各种实施例(其中一些已在附图中说明)对上述简要概括的本发明概念进行更具体的描述。但是，需要注意的是，所附的附图只说明发明概念的典型实施例，因此并不是以任何方式限制范围，还存在其他同样有效的实施例。
13.图1示出了被配置成用于实现各个实施例的一个或更多个方面的系统；
14.图2是根据各个实施例的包括在图1的并行处理子系统中的并行处理单元(ppu)的框图；
15.图3是根据各个实施例的图1的构建引擎的更详细的图示。
16.图4a示出了根据各个实施例的构建示例性包围体层次结构(bvh)的阶段。
17.图4b示出了根据各个实施例的构建示例性bvh的另一阶段。
18.图4c示出了根据各个实施例的构建示例性bvh的另一阶段。
19.图4d示出了根据各个实施例的构建示例性bvh的另一阶段。
20.图4e示出了根据各个实施例的构建示例性bvh的另一阶段。
21.图4f示出了根据各个实施例的构建示例性bvh的另一阶段。
22.图4g示出了根据各个实施例的构建示例性bvh的另一阶段。
23.图5阐明了根据各个实施例的用于生成bvh的方法步骤的流程图。
具体实施方式
24.在下面的描述中，阐述了大量的具体细节，以提供对各个实施例的更全面理解。然而，对于本领域技术人员来说，可以在没有一个或更多个这些具体细节的情况下实践这些发明概念。
25.总体概述
26.包围体层次结构(bvh)是用于在空间上组织图形场景或空间的另一表示中的点、三角形、多边形、网格或其他类型的对象的通用层次结构数据结构。bvh通常包括具有多级节点的树结构。树结构中的每个节点表示特定的“包围体”，其是包含(即，界定)对象中的一些或全部的空间区域。树结构中的根节点表示包含(即，界定)所有对象的单个空间，并且树结构中的给定节点的子节点表示由节点表示的包围体到更小的非重叠包围体的分割。树结构中的叶节点因此表示对象被分组或组织到其中的最小包围体。每个叶节点另外存储落入对应包围体内的一组对象。
27.在为给定组的对象生成bvh之后，bvh中的树结构可以用于加速与对象相关的各个空间查询。可以在渲染包括该组对象的图形场景、涉及该组对象的模拟、和/或与这些对象相关的其他类型的处理或分析期间执行这些空间查询。例如，可以遍历树结构以确定在光线追踪操作期间首先与光线相交的点或对象。在另一示例中，由树结构中的节点表示的包围体可以用于检测图形场景或模拟中的虚拟对象之间的冲突。
28.在生成bvh时，树结构通常以自上而下的方式构建，从根节点开始，向下递减到叶节点。在bvh中的给定父节点处，父节点所表示的包围体被划分割成两个或更多个不相交的包围体。表示不相交的包围体的两个或更多个节点被创建为父节点的子节点。由父节点表示的包围体还可以“自适应地”被分割为由子节点表示的包围体，其方式为考虑对象在包围体中的空间分布。例如，自上而下bvh构建技术可计算每一对象的代表点作为对象的形心和/或对象的包围盒的形心。自上而下bvh构建技术还可确定包围盒，指派给父节点的所有对象的代表点适合该包围盒。自上而下bvh构建技术可选择沿其分割包围盒的轴线，并且可选择沿该轴线的一个或更多个分割平面，该一个或更多个分割平面将包围盒划分成与子节点相关联的两个或更多个包围体。每个分割平面可以基于轴线的长度、分割平面与对象之间的重叠量、与遍历bvh以执行给定任务相关联的成本、和/或使包围体的分割适应不同参
数或因素的其他启发法来选择。自上而下bvh构建技术可继续将bvh中的不同节点递归地分割成附加子节点，直至与给定节点相关联的对象的数量降至阈值以下和/或直至满足另一条件。
29.上述自适应自上而下方法的一个缺点是与此方法相关的操作难以并行化。具体地，在bvh的给定级别处执行的分割操作的数量和与计算分区相关联的计算开销随时间而改变，从而使得并行化变得困难。更具体地，自上而下方法开始于与生成少量节点和每个节点的大量对象的分区相关的操作。随着自上而下方法的进展，对增加数量的节点和每节点的减少数量的对象执行分割操作。因此，大量的线程和/或处理器通常用于分割bvh的根节点附近的各个节点，而单个线程通常用于分割bvh的叶节点附近的各个节点。在根节点与叶节点之间，在给定节点上操作的线程和/或处理器的数量通常基于在bvh的给定级别的节点的数量和与该节点相关联的对象的数量而变化。
30.上文所描述的自适应自上而下方法的另一缺点是树结构中的每一节点通常维持被分组在由节点表示的包围体下的对象的列表。因此，必须为每个列表分配存储器，并且必须将指派给给定父节点的对象列表分割成相应子节点的子列表。当建立bvh时，存储器分配必须适应列表的数量(例如，靠近根节点的少量列表和靠近叶节点的大量列表)和每个列表的大小(例如，靠近根节点的大列表和靠近叶节点的小列表)的改变。进一步，将列表分割为子列表招致资源开销，资源开销为给定列表的大小和在树结构的给定级别处待分割的列表的数目两者的函数。
31.为了提高构建多个bvh的效率，bvh中的每个对象存储该对象当前被指派给的节点的标识符。通过在节点更新内核和对象更新内核之间迭代地切换来构建bvh。节点更新内核处理在bvh的给定级别处的一组节点。对于在该级别的每个节点，如果节点满足用于变成叶节点的一个或更多个条件，则节点更新内核将该节点标记为叶节点。如果节点不满足用于变成叶节点的条件，则节点更新内核生成一个或更多个分区，该一个或更多个分区将节点表示的包围体划分成两个或更多个新的包围体。节点更新内核还生成两个或更多个子节点以表示新的包围体。在节点更新内核的给定迭代完成之后，来自由节点更新内核处理的级别的所有节点已经被转换成叶节点或内部节点。
32.对象更新内核基于在节点更新内核期间作出的改变来更新指派给对象的节点。具体地，对象更新内核确定对象被指派到的节点(即，基于存储在对象中的节点的标识符)是否是叶节点。如果对象被指派到的节点被标记为叶节点，则对象更新内核可选地将对象标记为“已完成”以允许对象更新内核的后续迭代跳过对象。如果对象被指派到的节点没有被标记为叶节点，则对象更新内核确定对象所属的新包围体，并且将表示新包围体的子节点的标识符存储在对象中。因此，在不分配或分割与节点相关联的任何对象列表的情况下，将对象“移动”至子节点。在对象更新内核的给定迭代完成之后，每个对象被指派给该对象先前被指派给的节点的叶节点或子节点。
33.重复节点更新内核和对象更新内核的交替执行，直到没有另外的节点被创建并且所有对象已经被指派给叶节点为止。然后，通过创建叶节点的对象列表并重新计算与节点相关联的包围体，从叶节点开始并向上传播直到到达根节点，来完成bvh的构建。
34.因为使用分别更新节点和对象的两个交替的内核来构建bvh，所以可以在不改变并行性的粒度的情况下并行地执行每个内核。此外，通过改变存储在对象中的标识符而不
是执行与为新创建的节点分配新对象列表并且将对象分类到列表中相关联的在计算上低效的操作，来将对象“移动”到不同的节点。结果，与涉及改变并行度的粒度和/或存储被指派给bvh内的不同节点的对象的列表的常规方法相比，bvh能够以在计算上更简单且更高效的方式来构建。
35.系统概述
36.图1是示出了被配置成用于实施各个实施例的一个或更多个方面的计算机系统100的框图。在一些实施例中，计算机系统100是在数据中心、集群或云计算环境中操作的机器或处理节点，其通过网络提供可扩展计算资源(可选地作为服务)。
37.在各个实施例中，计算机系统100包括但不限于中央处理单元(cpu)102以及系统存储器104，它们经由存储器桥105和通信路径113耦合至并行处理子系统112。存储器桥105进一步地经由通信路径106耦合至i/o(输入/输出)桥107，i/o桥107又耦合至交换机116。
38.在一个实施例中，i/o桥107被配置为从可选的输入设备108(诸如键盘或鼠标)接收用户输入信息，并经由通信路径106和存储器桥105将输入信息转发给cpu 102进行处理。在一些实施例中，计算机系统100可以是云计算环境中的服务器机器。在这样的实施例中，计算机系统100可以不具有输入设备108。相反，计算机系统100可通过接收通过网络传输并经由网络适配器118接收的消息形式的命令来接收等效输入信息。在一个实施例中，交换机116被配置为在i/o桥107和计算机系统100的其他组件(如网络适配器118和各种附加卡120和121)之间提供连接。
39.在一个实施例中，i/o桥107耦合至系统盘114，系统盘114可以被配置为存储内容以及应用程序和数据，以供cpu 102和并行处理子系统112使用。在一个实施例中，系统盘114为应用程序和数据提供非易失性存储，可包括固定的或可移除的硬盘驱动器、闪存设备和cd-rom(光盘只读存储器)、dvd-rom(数字多功能盘-rom)、蓝光、hd-dvd(高清dvd)或其他磁、光或固态存储设备。在各个实施例中，其他组件(诸如通用串行总线或其他端口连接、光盘驱动器、数字多功能盘驱动器、胶片录制设备等)也可以连接到i/o桥107。
40.在各个实施例中，存储器桥105可以是北桥芯片(northbridge chip)，i/o桥107可以是南桥芯片(southbridge chip)。此外，可以用任何技术上合适的协议(包括但不限于agp(加速图形端口)、超文本传输(hypertransport)或本领域公知的任何其他总线或点对点通信协议)在计算机系统100内实现通信路径106和113以及其他通信路径。
41.在一些实施例中，并行处理子系统112包括图形子系统，该图形子系统向可选的显示设备110输送像素，该显示设备可以是任何常规的阴极射线管、液晶显示器、发光二极管显示器等。在这种实施例中，并行处理子系统112合并了针对图形和视频处理优化的电路，包括例如视频输出电路。如结合下图2中更详细地描述的，可以跨并行处理子系统112中包括的一个或更多个并行处理单元(ppu)(这里也称为并行处理器)合并此类电路。在其他实施例中，并行处理子系统112合并了针对通用和/或计算处理而优化的电路。同样，可以跨并行处理子系统112中包括的一个或更多个ppu合并此类电路，这些ppu被配置为执行此类通用和/或计算操作。在其他实施例中，并行处理子系统112中包括的一个或更多个ppp可配置为执行图形处理、通用处理和计算处理操作。系统存储器104包括至少一个设备驱动器，该设备驱动器配置为管理并行处理子系统112中的一个或更多个ppu的处理操作。
42.在一个或更多个实施例中，并行处理子系统112包括构建引擎122，所述构建引擎
为一组对象生成包围体层次结构(bvh)124。例如，构建引擎122可为点、三角形、多边形、网格和/或其他类型的几何对象构建bvh 124。bvh 124随后可用于有效地执行与碰撞检测、光线追踪和/或与几何对象相关联的其他任务相关的操作。
43.在各个实施例中，并行处理子系统112可与图1的一个或更多个其他元件集成，以形成单个系统。例如，并行处理子系统112可以与cpu 102和其他连接电路集成在单个芯片上，以形成片上系统(soc)。
44.在一个实施例中，cpu 102是计算机系统100的主处理器，控制和协调其他系统部件的操作。在一个实施例中，cpu 102发出控制ppu的操作的命令。在一些实施例中，通信路径113是pci express链路，其中专用通路被分配给每个ppu，如本领域中已知的。也可以使用其他通信路径。ppu有利地实现高度并行处理架构。ppu可设有任何量的本地并行处理存储器(pp存储器)。
45.应理解，本文所示的系统是说明性的，并且变化和修改是可能的。连接拓扑(包括网桥的数量和布置、cpu 102的数量和并行处理子系统112的数量)可以根据需要进行修改。例如，在一些实施例中，系统存储器104可以直接连接到cpu 102，而不是通过存储器桥105连接到cpu 102，并且其他设备将经由存储器桥105和cpu 102与系统存储器104进行通信。在其他实施例中，并行处理子系统112可以连接到i/o桥107或直接连接到cpu 102，而不是连接到存储器桥105。在其他实施例中，i/o桥107和存储器桥105可以集成到单个芯片中，而不是作为一个或更多个分立器件存在。最后，在某些实施例中，图1所示的一个或更多个组件可以不存在。例如，可以消除交换机116，网络适配器118和附加卡120、121会直接连接到i/o桥107。
46.图2是根据各个实施例的图1的并行处理子系统112中包括的并行处理单元(ppu)202的框图。尽管图2描述了一个ppu 202，如上文所述，但并行处理子系统112可以包括任意数量的ppu 202。如图所示，ppu 202耦合到本地并行处理(pp)存储器204。ppu 202和pp存储器204可采用一个或更多个集成电路器件实现，例如可编程处理器、应用专用集成电路(“asic”)或存储器设备，或者任何其他技术上可行的方式。
47.一些实施例中，ppu 202包括图形处理单元(gpu)，该gpu可配置为实现图形渲染管线，以基于cpu 102和/或系统存储器104提供的图形数据执行与生成像素数据相关的各种操作。在处理图形数据时，pp存储器204可用作存储一个或更多个常规帧缓冲区(如果需要，还可以存储一个或更多个其他渲染目标)的图形存储器。除其他事项外，pp存储器204可用于存储和更新像素数据，并将最终像素数据或显示帧传输至可选的显示设备110以进行显示。在一些实施例中，ppu 202也可以配置为通用处理和计算操作。在一些实施例中，计算机系统100可以是云计算环境中的服务器机器。在这样的实施例中，计算机系统100可以不具有显示设备110。相反，计算机系统100可以通过经由网络适配器118通过网络传输消息形式的命令来生成等效输出信息。
48.如上所示，在计算机系统100中，cpu 102可以作为主处理器操作来控制和协调其他系统组件的操作。在一个实施例中，cpu 102发出控制ppu 202的操作的命令。例如，cpu 102将用于ppu 202的命令流写入数据结构(图1或图2未明确示出)中，该数据结构可以位于系统存储器104、pp存储器204或cpu 102和ppu 202两者可访问的另一个存储位置。指向数据结构的指针被写入命令队列(也称为推送缓冲区(pushbuffer))以启动对数据结构中命
令流的处理。在一个实施例中，ppu 202从命令队列读取命令流，然后相对于cpu 102的操作异步地执行命令。在生成多个推送缓冲区的实施例中，应用程序可以经由设备驱动器为每个推送缓冲区指定执行优先级，以控制不同推送缓冲区的调度。
49.在一个实施例中，ppu 202包括i/o(输入/输出)单元205，其经由通信路径113和存储器桥105与计算机系统100的其余部分进行通信。在一个实施例中，i/o单元205生成数据包(或其他信号)以在通信路径113上传输，并且还从通信路径113接收所有传入数据包(或其他信号)，将传入数据包定向到ppu 202的相应组件。例如，与处理任务相关的命令可定向到主机接口206，而与存储器操作相关的命令(例如，从pp存储器204读取或写入pp存储器204)可以定向到交叉开关单元210。在一个实施例中，主机接口206读取每个命令队列，并将存储在命令队列中的命令流发送到前端212。
50.如上结合图1所述，ppu 202与计算机系统100的其余部分的连接可以变化。在一些实施例中，并行处理子系统112(其包括至少一个ppu 202)作为附加卡实现，附加卡可插入计算机系统100的扩展槽中。在其他实施例中，ppu 202可采用总线桥集成在单个芯片上，诸如存储器桥105或i/o桥107。同样，在其他实施例中，ppu 202的一些或全部元件可与cpu 102一起被包括在单个集成电路或片上系统(soc)中。
51.在一个实施例中，前端212将从主机接口206接收的处理任务发送到任务/工作单元207内的工作指派单元(未示出)。在一个实施例中，工作指派单元接收指向处理任务的指针，这些任务被编码为任务元数据(tmd)并存储在存储器中。指向tmd的指针包括在命令流中，该命令流存储为命令队列，并由前端212从主机接口206接收。可以编码为tmd的处理任务包括与要处理的数据相关联的索引，以及定义如何处理数据的状态参数和命令。例如，状态参数和命令可以定义要对数据执行的程序。同样，tmd可以指定cta集合的数量和配置。通常，每个tmd对应一个任务。任务/工作单元207从前端212接收任务，并确保在启动每个tmd指定的处理任务之前将通用处理集群gpc 208配置为有效状态。可以为每个tmd指定优先级，该优先级用于调度处理任务的执行。处理任务也可以从处理集群阵列230接收。可选地，tmd可以包括控制是否将tmd添加到处理任务列表(或指向处理任务的指针列表)的头部或尾部，从而提供对执行优先级的另一级控制的参数。
52.在一个实施例中，ppu 202基于处理集群阵列230有利地实现了高度并行处理体系架构，处理集群阵列230包括一组c个通用处理集群(gpc)208，其中c≥1。每个gpc 208能够同时执行大量(例如数百或数千个)线程，其中每个线程都是程序的实例。在各种应用中，可以分配不同的gpc 208来处理不同类型的程序或执行不同类型的计算。gpc 208的分配可根据每种类型的程序或计算产生的工作负载而不同。
53.在一个实施例中，存储器接口214包括一组d个分区单元215，其中d≥1。每个分区单元215耦合到驻留在pp存储器204内的一个或更多个动态随机存取存储器(dram)220。在一些实施例中，分区单元215的数量等于dram 220的数量，每个分区单元215耦合到不同的dram 220。在其他实施例中，分区单元215的数量可以与dram 220的数量不同。本领域普通技术人员可以认识到，dram 220可更换为任何其他技术上合适的存储设备。在操作中，各种渲染目标(诸如纹理映射和帧缓冲区)可以跨dram 220存储，允许分区单元215并行写入每个渲染目标的部分，从而有效地使用pp存储器204的可用带宽。
54.在一个实施例中，给定的gpc 208可以处理要写入pp存储器204中的任何dram 220
的数据。在一个实施例中，交叉开关单元210被配置为将每个gpc 208的输出路由到任何分区单元215的输入或任何其他gpc 208以进行进一步处理。gpc 208经由交叉开关单元210与存储器接口214通信，以从各个dram 220读取或写入各个dram 220。在一些实施例中，交叉开关单元210除了经由存储器接口214连接到pp存储器204之外，还连接到i/o单元205，从而使不同gpc 208中的处理核能够与系统存储器104或非ppu 202本地的其他存储器进行通信。在图2的实施例中，交叉开关单元210与i/o单元205直接连接。在各种实施例中，交叉开关单元210可以使用虚拟通道分隔gpc 208和分区单元215之间的业务流。
55.在一个实施例中，gpc 208可以被编程为执行与各种应用相关的处理任务，包括但不限于线性和非线性数据变换、视频和/或音频数据的过滤、建模操作(例如，应用物理定律以确定对象的位置、速度和其他属性)、图像渲染操作(例如，曲面细分着色程序、顶点着色程序、几何着色程序和/或像素/片段着色程序)、通用计算操作等。在操作中，ppu 202被配置为将数据从系统存储器104和/或pp存储器204传输到一个或更多个片上存储器单元，处理该数据，并将结果数据写回系统存储器104和/或pp存储器204。然后，其他系统组件(包括cpu 102、并行处理子系统112中的另一ppu 202或计算机系统100中的另一并行处理子系统112)可以访问该结果数据。
56.在一个实施例中，并行处理子系统112中可包括任意数量的ppu 202。例如，单个附加卡上可提供多个ppu 202，或者多个附加卡可以连接到通信路径113，或者一个或更多个ppu 202可以集成到桥芯片中。多ppu系统中的ppu 202可彼此相同或不同。例如，不同的ppu 202可能具有不同数量的处理核和/或不同数量的pp存储器204。在存在多个ppu 202的实现方式中，这些ppu可以并行操作，以比采用单个ppu 202所可能的吞吐量更高的吞吐量处理数据。包括一个或更多个ppu 202的系统可以以各种配置和形式因素实现，包括但不限于台式机、笔记本电脑、手持式个人计算机或其他手持设备、服务器、工作站、游戏机、嵌入式系统等。
57.如图所示，每个gpc 208访问构建引擎122的对应实例，并且pp存储器204中的每个dram 220存储用于构建bvh 124的bvh数据222的部分或完整副本。例如，每个gpc 208可以与实现构建引擎122的单独的加速器通信以创建和/或更新bvh 124中的节点和/或对象。构建引擎122和bvh数据222在下面参见图3-5更详细地描述。
58.本领域技术人员将认识到，构建引擎122、bvh 124、和bvh数据222可以以多种方式在图1和图2的系统内实现、复制、或分布。首先，代替或除了将bvh 124和/或bvh数据222存储在pp存储器204中的dram 220上之外，bvh 124和/或bvh数据222的一个或更多个部分可存储在每个gpc 208的片上存储器(例如，静态随机存取存储器(sram)、暂时存储器(scratchpad memory)、片上高速缓存等)中。给定gpc 208或构建引擎122的实例可使用直接存储器访问(dma)来在dram 220和片上存储器之间传输bvh 124和/或bvh数据222的部分。第二，代替或除存储在pp存储器204中的dram 220上之外，bvh 124和/或bvh数据222的一个或更多个部分可存储在每个分区单元215中的l2高速缓存中。第三，构建引擎122的一个实例可以针对每个gpc 208来实现，或者构建引擎122的一个或更多个实例可以由多个gpc 208共享。第四，构建引擎122可以由一个或更多个gpc 208、一个或更多个cpu、和/或由处理来自一个或更多个gpc 208的请求的独立加速器来实现。
59.包围体层次结构的可扩展并行构建
60.图3是根据各个实施例的图1的构建引擎122的更详细的图示。如图3所示，构建引擎122处理dram 220(或另一类型的存储器)中的bvh数据222。bvh数据222包括与bvh 124中的节点相关的节点数据306以及与bvh 124中的对象相关的对象数据308。构建引擎122包括初始化模块300、节点更新内核302和对象更新内核304。下文进一步详细描述这些组件中的每一者。
61.初始化模块300执行与构建bvh 124相关的多个初始化操作。这些初始化操作包括与bvh 124的创建相关的节点、对象和/或元数据的存储器分配328。例如，初始化模块300可以分配用于存储与高达2n个节点(假设n个对象，其中n是大于1的整数)相关联的节点数据306的存储器。
62.在一些实施例中，节点数据306包括bvh 124中的节点对之间的节点关系314。例如，给定节点的节点关系314可包括对该节点的子代和/或该节点的父代的偏移。节点数据306还可以包括由节点表示的包围体316，以及用于把由节点表示的包围体划分成由节点的子节点表示的较小包围体的分区320。进一步，节点数据306可包括表示指派给bvh 124中的各个叶节点的对象的列表的位置的对象列表偏移326。最后，节点数据306可以包括不再必须被处理的已完成节点310和尚未被处理的未完成节点312的一个或更多个位、标签和/或其他指示符。节点数据306的这些元素在下面进一步详细描述。
63.在一些实施例中，节点数据306包括跟踪bvh 124中的节点和/或对象的总数的一个或更多个计数器318。计数器318可以包括跟踪已经创建的节点的数量的一个原子计数器和跟踪已经指派给bvh 124中的叶节点的对象的总数的另一个原子计数器。计数器318还可包括用于bvh 124中的每个节点的“对象计数器”，该“对象计数器”跟踪当前指派给节点的对象的数量。
64.在执行存储器分配328之后，初始化模块300执行节点初始化330，该节点初始化创建并初始化bvh 124中的根节点。例如，初始化模块300可以在dram 220中分配的存储器内创建根节点，将跟踪已经创建的节点数量的计数器设置为1，将根节点的包围体设置为空框，以及将根节点的对象计数器设置为0。
65.初始化模块300还用新创建的根节点更新一组已完成节点310和一组未完成节点312。在一个或更多个实施例中，已完成节点310包括具有相关联的子节点、叶节点、或基于对象到那些节点的指派而“处理”的其他类型的节点的内部节点。相反，未完成节点312包括基于对象到那些节点的指派而尚未被处理的节点，诸如(但不限于)不具有子节点并且不是叶节点的节点。由此，在创建根节点之后，初始化模块300可将根节点添加到该组未完成节点312中，且将该组已完成节点310初始化为空集。
66.初始化模块300还执行对象初始化332，该对象初始化对这些对象的对象数据308进行初始化。在对象初始化332期间，初始化模块300分配存储对象的节点标识符(id)332的阵列(或另一类型的结构)。例如，阵列可被分配为具有表示n个对象的n个元素。阵列中的每个元素可表示不同的对象并且存储与节点(对象被指派到的节点)的节点标识符相对应的整数。在创建阵列之后，初始化模块300更新阵列，使得阵列的所有元素存储根节点的节点标识符(例如，0)，从而指示所有对象当前被指派给根节点。
67.在对象初始化期间，初始化模块300还计算对象的代表点324。例如，初始化模块300可以将每个对象的代表点计算为对象的形心、对象的包围盒的形心、和/或表示对象的
位置的另一点。
68.在为给定对象计算代表点之后，初始化模块300执行与根节点相关的附加节点初始化330操作。首先，初始化模块300在根节点处递增计数器，该计数器跟踪指派给根节点的对象的数量。第二，初始化模块300更新与根节点相关联的包围体，使得代表点由包围体界定。
69.在初始化模块300已经完成存储器分配328、节点初始化330、以及对象初始化332之后，根节点包括选择一个或更多个分区320(例如，分割平面)所需的信息，并且每个对象被“标记”为属于根节点。构建引擎122然后在执行节点更新内核302和对象更新内核304之间交替，以按自上而下的方式构建bvh 124的剩余部分。
70.更具体地，在初始化模块300已经完成执行之后，构建引擎122以执行节点更新内核302开始。节点更新内核302的每次迭代处理bvh 124的给定级别的节点。在节点更新内核302的给定迭代已经完成之后，构建引擎122执行对象更新内核304的对应迭代，以基于节点更新内核302的先前完成的迭代的结果来处理对象。
71.在一个或更多个实施例中，节点更新内核302的每次迭代处理一组未完成节点312，这组未完成节点表示bvh 124的相应级别处的节点。换言之，节点更新内核302的第一次迭代处理bvh 124的第一(即，最高)级别的根节点，并且节点更新内核302的第x次迭代处理bvh 124中的第x级别的节点。
72.在给定的一组未完成节点312的处理期间，节点更新内核302执行叶节点创建334，该叶节点创建在验证给定节点满足用于变成叶节点的一个或更多个标准之后将该节点标记为叶节点。例如，节点更新内核302可以(例如，基于存储在对象中的节点标识符)确定指派给节点的对象的数量，并且将该数量与阈值进行比较。如果指派给节点的对象的数目满足或低于阈值，那么节点更新内核302可通过在节点中存储具有负分割维度的分割平面、设定指示所述节点为叶节点的位或标志或以其他方式存储所述节点为叶节点的指示来将所述节点标记为叶节点。
73.在节点被转换成叶节点之后，节点更新内核302基于指派所转换后的节点的对象的数量来更新一个或更多个计数器318。如上所述，计数器318包括存储被指派给给定节点的对象的数量的对象计数器和存储已经被指派给叶节点的对象的总数的原子计数器。节点更新内核302将原子计数器的当前值作为对象列表偏移(例如，对象列表偏移326)存储到指派给转换后的节点的对象列表。节点更新内核302然后将第二计数器递增转换后的节点的对象计数器的值，以生成要转换成叶节点的下一个节点的新对象列表偏移。例如，如果转换后的节点是bvh 124中的第一叶节点，则转换后的节点的对象计数器可存储由m表示的正整数，并且原子计数器可被设置为0。节点更新内核302可以将第一叶节点的对象列表偏移设置为原子计数器中的值0。节点更新内核302然后可以将原子计数器增加第一计数器中的值m。如果要转换成叶节点的下一个节点具有存储由o表示的正整数的对象计数器，则节点更新内核可以将下一个节点的对象列表偏移设置为m并且随后将原子计数器增加到m+o。如下文进一步详细描述的，在已经确定bvh 124的结构之后，构建引擎122使用这些计数器318来创建被指派给bvh 124中的各个叶节点的对象的列表。
74.当节点更新内核302确定节点不满足用于变成叶节点的标准时，节点更新内核302执行分区生成336，所述分区生成336选择用于将节点表示的包围体细分为两个或更多个更
小的包围体的一个或更多个分区320。例如，节点更新内核302可以使用自适应空间中值分割技术来识别由节点表示的包围体中的最长轴线，并且沿着所识别的轴线选择分割平面。节点更新内核302可以将轴线和分割平面存储为与由节点表示的包围体有关的分区(例如，分区320)。
75.在另一示例中，节点更新内核302可以使用经分仓的表面区域启发法来确定与由给定节点表示的包围体有关的分区320。更具体地，节点更新内核302可以生成包围体被划分成的相同大小的“仓”的x(其中x是正整数)。节点更新内核302还可以创建节点的x个子节点，并且通过将对应的包围体316设置为空框并且将跟踪每个子节点中的对象的数量的计数器318设置为0来初始化子节点。
76.在第三示例中，节点更新内核302可以生成多个分区320，这些分区将由给定节点表示的包围体划分成多于两个的包围体。首先，节点更新内核302可以选择将包围体划分成两个包围体的第一分区。接下来，节点更新内核302可以选择将两个包围体中的较大者划分成两个以上的包围体的第二分区。节点更新内核302可以重复该过程，直到创建期望数量的包围体。
77.在为由给定节点表示的包围体生成一组分区320之后，节点更新内核302执行节点分配338，节点分配338创建表示较小包围体的两个或更多个子节点，包围体被细分成所述较小包围体。例如，节点更新内核302可以通过原子地增加跟踪已经创建的节点的数量的一个或更多个计数器318来分配子节点。节点更新内核302可以将节点关系314存储在节点和/或子节点中，指示该节点是子节点的父节点。节点更新内核302可以通过将对应的包围体316设置为空框并且将跟踪子节点中的每一个中的对象数量的计数器318设置为0来进一步初始化子节点。
78.在一个或更多个实施例中，节点更新内核302包括用于管理“退化分割”的功能，其中，指派给给定节点的所有对象也被指派给该节点的单个子节点。当对象全部具有相同的代表点时，或者如果分区320的计算涉及使给定分区对应于由节点表示的包围体的边之一的舍入操作，则这些退化分割可以发生。当节点更新内核302检测到这样的退化分割时，节点更新内核302可以在与节点相关的一个或更多个分区320中存储指示退化分割的一个或更多个值(例如，指示无效分割维度的值)。节点更新内核302还可以创建节点的两个或更多个子节点，并且以循环(或另一个)方式将对象分类到子节点中。节点更新内核302还可以在随后的迭代中重复该过程，直到给定节点中的对象的数量满足用于将该节点转换成叶节点的阈值。
79.节点更新内核302继续处理处于bvh 124的给定级别的节点。例如，节点更新内核302的每次迭代可包括并行执行以针对bvh 124的对应级别的一组未完成节点312执行叶节点创建334、分区生成336和节点分配338的多个线程、处理器核和/或处理器。在节点更新内核302的迭代完成之后，该级别的每个节点已经被转换成叶节点或具有两个或更多个子代的内部节点。
80.对象更新内核304在节点更新内核302的相应迭代已经完成之后开始执行。具体地，对象更新内核304的给定迭代执行节点指派340，节点指派340将一些或所有对象重新指派给在节点更新内核302的对应迭代中创建的节点。在节点指派340期间，对象更新内核304检查每个对象当前被指派到的节点。如果该节点被标记为叶节点，则对象更新内核304不将
该对象重新指派给另一节点。对象更新内核304还任选地用不需要重新指派对象的位、标志或另一指示符标记对象。此指示符允许对象更新内核304的未来调用跳过与对象相关的额外处理。对象更新内核304还可以或替代地维持仍然需要被重新指派的对象的列表，并且当对象被指派给叶节点时从列表中移除对象。
81.如果给定对象未被标记为叶节点的节点，则对象更新内核304基于存储在该节点中的一个或更多个分区320将该对象重新指派给该节点的子节点。例如，对象更新内核304可以从该节点检索分割平面并计算该分割平面的该对象中的代表点落在的侧面。对象更新内核304然后可以将存储在对象中的节点id(例如，节点id 322)更新为对应子节点的节点id，从而将对象“移动”至子节点。
82.在对一个或更多个对象执行节点指派340之后，对象更新内核304使跟踪指派给每个子节点的对象的数量的一个或更多个对应计数器318递增。例如，在对象被重新指派给给定子节点之后，对象更新内核304可以递增表示被指派给该子节点的对象的数量的计数器。
83.对象更新内核304还执行包围体更新342，该包围体更新将子节点所表示的包围体316更新为包括在指派给子节点的对象中的代表点。例如，对象更新内核304可以确定指派给子节点的对象具有位于由该子节点所表示的当前包围体之外的代表点。然后，对象更新内核304可以更新包围体，以包括先前落在包围体外的代表点的一个或更多个维度。
84.与节点更新内核302一样，对象更新内核304的每次迭代可以由多个线程、处理器和/或处理器核并行执行。这些线程、处理器和/或处理器核中的每个可执行节点指派340和对象的不同子集的包围体更新342。
85.在对象更新内核304的给定迭代已处理所有对象之后，构建引擎122将由节点更新内核302的对应迭代处理的节点(即，最近被节点更新内核302转换成叶节点或内部节点的节点)从该组未完成节点312移动到该组已完成节点310。构建引擎122还将由节点更新内核302的相应迭代创建的子节点(即，对象更新内核304的当前迭代将对象重新指派到的节点)添加到该组未完成节点312。
86.构建引擎122继续在节点更新内核302与对象更新内核304之间交替，直到没有创建进一步的节点。此时，每个节点是叶节点或内部节点，该组未完成节点312是空的，并且每个对象已经被指派给叶节点。
87.构建引擎122然后使用bvh数据222完成bvh 124的构建。首先，构建引擎122基于对象数据308中的节点id 322、计数器318和对象列表偏移326，为bvh 124中的每个叶节点创建对象列表。例如，构建引擎122可创建新的元素阵列来存储对象列表。对于每个叶节点，构建引擎122存储指派给叶节点的对象的列表，在对应的对象列表偏移处开始。因此，如果第一叶节点具有m个指派的对象和对象列表偏移0，则构建引擎122以范围从0到m-1的偏移存储指派给第一叶节点的m个对象。如果第二叶节点具有o个指派的对象和m的对象列表偏移，则构建引擎122以从m到m+o-1范围的偏移存储指派给第二叶节点的o个对象。在构建引擎122已将对象写入到给定列表内的对应偏移之后，构建引擎122可递增对应叶节点的对象列表偏移，并将不同对象写入到经递增的偏移。
88.第二，构建引擎122计算bvh 124中的所有节点的最终包围体316。例如，构建引擎122可以将最终包围体316计算为对应叶节点中的对象的边界的包围盒。构建引擎122还可以以从叶节点开始的“自下而上”的方式计算最终包围体316。换言之，在为作为给定父节点
的子节点的所有叶节点计算最终包围体316之后，构建引擎122将这些最终包围体316组合成父节点的最终包围体。构建引擎122可以针对bvh 124中的其他节点重复该过程，直到针对根节点计算最终包围体。
89.在一些实施例中，构建引擎122使用最终包围体316的计算来用相应的包围体“重新装配(refit)”或“重新填充(repopulate)”bvh 124中的节点。更具体地，构建引擎122可以在这些包围体316用于生成分区320之后丢弃与内部节点相关联的包围体316，分区320用于为内部节点的子节点创建新的包围体316。该丢弃的信息可用于在bvh 124的构建期间减少存储器消耗。在所有对象已经被指派给叶节点之后，构建引擎122重新计算叶节点的最终包围体316并且向上传播最终包围体316直到到达根节点。
90.构建引擎122还可以或替代地经由其他技术来降低存储器消耗。例如，构建引擎122可在单个动态存储器分配调用中为所有节点数据306和对象数据308分配临时存储器。在另一示例中，构建引擎122可将包围体316、分区320、和/或用于从节点关系314和/或与节点数据306中的节点拓扑相关的其他数据中选择bvh 124中的分割的其他分割选择信息分开。构建引擎122还可以将bvh 124中的分割选择信息存储在最多ns个条目中。如果存在多于ns个未完成节点312，则构建引擎122可仅分割第一ns个未完成节点312。结果，构建引擎122将仅为拓扑信息分配临时节点阵列，其在大小上显著小于分割选择信息。
91.如上所述，每个对象可以包括或关联于位、标志、列表、或指示符，该位、标志、列表、或指示符可以被对象更新内核304用于跳过已经被指派给叶节点的对象。这个指示符还可以被构建引擎122的一个或更多个部分用于在构建bvh 124期间标记和跳过“无效”对象。例如，初始化模块300可以在对象初始化332期间验证每个对象。该验证可包括(但不限于)校验表示三角形的对象具有三个唯一顶点和/或校验表示给定对象的数据未被损坏。当检测到无效对象时(例如，当表示三角形的对象实际上是线、点或被损坏时)，初始化模块300可以为该对象设置指示符和/或将该对象从要被重新指派的对象列表中移除，从而使得对象更新内核304在bvh 124的构建期间跳过该对象。初始化模块300还可将对象的节点id设置为负值或指示不应将对象指派给bvh 124中的任何非叶节点的某个其他值。在所有“有效”对象已被指派给叶节点之后，构建引擎122可以可选地基于与叶节点相关联的最终包围体316将无效对象添加到指派给叶节点的对象的对应列表。
92.在一个或更多个实施例中，构建引擎122减少原子操作之间的冲突，这些原子操作通过多个线程对节点和/或对象的协作更新来更新节点和/或对象。例如，构建引擎122可以将与多达y个未完成节点312相关的节点数据306和/或对象数据308存储在gpu内的本地或共享存储器中。执行节点更新内核302和/或对象更新内核304(例如，在线程块内)的多个线程可以协作地更新该共享存储器，以防止与将大量对象重新指派给同一节点相关联的原子冲突。在节点更新内核302或对象更新内核304的给定迭代完成之后，可将共享存储器中的经更新的节点数据306和/或对象数据308转储到存储所有bvh数据222的全局存储器。
93.图4a示出了根据各个实施例的构建示例性bvh 124的阶段。如图4a所示，为占用空间400的对象集合402-410和对象集合402-410中的代表点集合412-420构建bvh 124。对象402-410包括二维(2d)或三维(3d)空间中的三角形，并且代表点412-420可以包括三角形的形心和/或三角形的包围盒的形心。对象402的代表点412由p1表示，对象404的代表点414由p2表示，对象406的代表点416由p3表示，对象408的代表点418由p4表示，并且对象410的代
表点420由p5表示。
94.图4a还示出了由初始化模块300基于对象集合402-410执行的节点初始化330的结果。该结果包括在bvh 124中创建根节点442。根节点442包括节点id为0、被设置为空盒的包围体和被设置为0的对象计数器。响应于根节点442的创建，初始化模块300还将跟踪节点数量的原子节点计数器设置为1。
95.图4b示出了根据各个实施例的在构建示例性bvh中的另一阶段。更具体地，图4b示出了由初始化模块300基于对象402-410执行的对象初始化332的结果。
96.如图4b中所示，对象初始化332包括存储了对象402-410的节点id 322的阵列434的创建。阵列434中的每个元素包括为0的节点id，其指示所有对象402-410当前被指派给根节点442。
97.因为所有对象402-410已经被指派给根节点442，所以根节点442被更新为包括与对象402-410相关联的所有代表点412-420的包围体。根节点442也被更新以包括对象计数器5。
98.图4c示出了根据各个实施例的构建示例性bvh的另一阶段。如图4c所示，与对象402-410相关联的bvh数据222已被节点更新内核302的第一次迭代更新。
99.具体地，节点更新内核302的第一次迭代用于为根节点442所表示的包围体选择分割平面。这个分割平面由位置422表示，该位置422由p6表示并且沿着包围体的最长轴线定位。
100.节点更新内核302的第一次迭代还用于创建根节点442的两个子节点444-446。节点444具有为1的节点id、被设置为空盒的包围体、以及被设置为0的对象计数器。节点446具有节点id2、被设置为空盒的包围体、以及被设置为0的对象计数器。在创建节点444-446之后，节点计数器递增至3。
101.图4d示出了根据各实施例的构建示例性bvh的另一阶段。如图4d所示，在节点更新内核302的第一次迭代之后，通过对象更新内核304的第一次迭代已经更新了与对象402-410相关联的bvh数据222。
102.更具体地，对象更新内核304的第一次迭代用于将对象402-410中的每一个重新指派给在节点更新内核302的第一次迭代中创建的两个节点444-446中的一个。对象402-408被指派给节点444，节点444表示在位置422处分割平面左侧的包围体。对象410被指派给节点446，节点446表示位置422处分割平面右侧的包围体。
103.节点444-446也被更新以反映对象402-410的对应指派。节点444包括包围体，该包围体包括对象402-408的代表点412-418和对象计数器4。节点446包括包围体，该包围体包括对象410的代表点420和对象计数器1。
104.图4e示出了根据各实施例的在构建示例性bvh中的另一阶段。具体地，图4e示出通过节点更新内核302的第二次迭代来更新与对象402-410相关联的bvh数据222。
105.如图4e中所示，节点更新内核302的第二次迭代用于将节点446转换成叶节点(例如，因为节点446中的对象的数量满足用于将节点转换成叶节点的阈值)。响应于转换，节点446包括节点“已完成”并且不需要进一步分割的位、标记或另一指示符。
106.节点更新内核302的第二次迭代还用于为由节点444表示的包围体选择分割平面。该分割平面由位置424表示，位置424由p7表示并且沿着由节点444表示的包围体的最长轴
线定位。
107.节点更新内核302的第二次迭代还用于创建节点444的两个子节点448-450。节点448具有3的节点id、被设置为空盒的包围体、以及被设置为0的对象计数器。节点450具有4的节点id、被设置为空盒的包围体、以及被设置为0的对象计数器。在创建节点444-446之后，节点计数器递增到5。
108.图4f示出了根据各个实施例的构建示例性bvh的另一阶段。具体地，图4f示出了在节点更新内核302的第二次迭代之后，通过对象更新内核304的第二次迭代来更新与对象402-410相关联的bvh数据222。
109.对象更新内核304的第二次迭代用于将对象402-408中的每个重新指派给在节点更新内核302的第二次迭代中创建的两个节点448-450中的一个。对象402被指派给节点448，节点448表示位置424处的分割平面上方的包围体。对象404-408被指派给节点450，节点450表示位置424处的分割平面下方的包围体。
110.更新节点448-450以反映对象402-408的对应指派。节点448包括包围体，该包围体包括对象402的代表点412和对象计数器1。节点450包括包围体，其包括对象404-408的代表点414-418和对象计数器3。
111.图4g示出了根据各个实施例的构建示例性bvh的另一阶段。更具体地，图4g示出了通过节点更新内核302的第三次迭代更新与对象402-410相关联的bvh数据222。
112.如图4g中所示，节点更新内核302的第三次迭代用于将节点448和450转换成叶节点(例如，因为节点448和450中的对象计数器满足用于将节点转换成叶节点的阈值)。响应于转换，节点448和450中的每个包括节点“完成”并且不需要进一步分割的位、标记或另一指示符。
113.在节点更新内核302的第三次迭代完成之后，构建引擎122可确定所有对象402-410已被指派给三个叶节点446-450之一。构建引擎122随后可生成被指派给每个叶节点的对象的列表。例如，构建引擎122可分配大小5的新阵列来存储节点446-450的对象列表。第一列表将为第一叶节点446创建，在阵列中的偏移0处开始，并且包括对象410。第二列表将为第二叶节点448创建，在阵列中的偏移1处开始，并且包括对象402。第三列表将为第三叶节点450创建，在阵列中的偏移2处开始，并且包括对象404-408。
114.图5示出了根据各个实施例的用于生成bvh的方法步骤的流程图。虽然结合图1-3的系统来描述方法步骤，但所属领域的技术人员将理解，经配置以按任何次序执行所述方法步骤的任何系统落入本公开的范围内。
115.如图所示，初始化模块300初始化502根节点、一组计数器和一组对象。例如，初始化模块300可以分配存储器来存储与bvh中的节点和/或对象相关的数据。初始化模块300还可以创建根节点，将根节点的包围体设置为空盒，并且将根节点的对象计数器设置为0。初始化模块300可以将跟踪已经创建的节点的数量的第一计数器设置为1，并且将跟踪已经指派给bvh中的叶节点的对象的数量的第二计数器设置为0。初始化模块300可以在每个对象中另外存储根节点的节点id以指示该对象被指派给根节点。在给定对象被指派给根节点之后，初始化模块300可以递增根节点的对象计数器，并更新根节点的包围体，以在对象中包括代表点。
116.接下来，节点更新内核302选择504未完成节点。该未完成节点可以包括没有被分
割或转换成叶节点的节点。例如，节点更新内核302可以在操作502中创建根节点之后选择新创建的根节点。
117.节点更新内核302确定506所选择的节点是否满足成为叶节点的一个或更多个标准。例如，节点更新内核302可以将节点的对象计数器与叶节点中允许的对象的最大数目的阈值进行比较。如果对象计数器超过阈值，则节点更新内核302可以确定该节点不满足用于变成叶节点的标准。如果对象计数器没有超过阈值，则节点更新内核302可以确定该节点满足变成叶节点的标准。
118.当节点更新内核302确定所选择的节点满足成为叶节点的标准时，节点更新内核302将该节点转换514成叶节点。例如，节点更新内核302可以设置将该节点标记为叶节点的位、标志或另一指示符。
119.节点更新内核302还存储516被指派给叶节点的对象列表的偏移。例如，节点更新内核302可以在表示叶节点的结构中存储偏移。偏移可以被设置为表示当前指派给叶节点的对象的数目的计数器的当前值。在节点更新内核302存储偏移之后，节点更新内核302可以将计数器增加指派给叶节点的对象的数目。
120.当节点更新内核302确定所选择的节点不满足用于变成叶节点的标准时，节点更新内核302基于与该节点相关联的包围体和一个或更多个分割标准确定508一组分区。例如，节点更新内核302可以使用与自适应空间中值分割技术、分仓表面区域技术和/或另一个分割技术相关联的分割标准来确定将所选择的节点的包围体细分成多个更小的非重叠的包围体的一个或更多个分区。
121.节点更新内核302还基于该组分区生成与该节点相关联的一组子节点510。继续以上示例，节点更新内核302可以生成不同的子节点以表示每个较小的包围体。在创建每个子节点之后，节点更新内核302可以递增跟踪已经创建的节点的数量的计数器。节点更新内核302还可以初始化子节点以具有被设置为空盒的包围体和被设置为0的对象计数器。
122.对象更新内核304然后在每个对象中存储512基于该组分区的对应子节点的标识符。例如，对象更新内核304可以使用由节点更新内核302生成的分区来识别用于该对象的代表点落入其中的较小的包围体。对象更新内核304可以将存储在对象中的标识符改变为表示较小包围体的子节点的节点标识符。对象更新内核304可以另外更新存储在子节点中的包围体的边界以包括对象的代表点的位置。
123.在处理给定的非叶节点之后，构建引擎122确定518是否继续处理节点。更具体地，构建引擎122确定如果还有附加的未完成节点，则节点的处理将继续。相反，如果所有节点是叶节点或内部节点，则构建引擎122确定对节点的处理将被中断。
124.当构建引擎122确定继续节点的处理时，构建引擎122重复操作504以选择未完成节点。构建引擎122还执行操作506以确定该节点是否满足用于变成叶节点的标准。如果节点满足成为叶节点的标准，则构建引擎122执行操作514-516以将该节点转换成叶节点。如果节点不满足用于变成叶节点的准则，则构建引擎122执行操作508-512以将节点分割成两个或更多个子节点并且将一些或全部对象重新指派给子节点。构建引擎122因此使用操作504-518来继续处理节点，直到所有节点是叶节点或内部节点并且所有对象已被指派给叶节点。
125.构建引擎122的多个实例还可以并行地执行操作504-518以建立bvh。例如，多个线
程、线程块、处理器核和/或处理器核心可执行构建引擎122以迭代地更新bvh中的节点和对象的不同子集。
126.在所有未完成节点都已经被处理之后，构建引擎122完成520bvh的构建。例如，构建引擎122可以生成指派给各个叶节点的对象列表作为到阵列中的连续偏移，其中，在创建叶节点期间，将表示给定叶节点的对象列表的开始的偏移存储在叶节点中。构建引擎122还可以(例如，基于对象的边界而不是对象中的代表点)执行由bvh中的节点表示的包围体的重新装配，从叶节点开始并向上传播直到到达根节点。
127.综上所述，所公开的技术通过在节点更新内核和对象更新内核之间交替来构建bvh。节点更新内核执行与bvh中的节点相关的处理，对象更新内核执行与在节点下组织的对象相关的处理。节点更新内核的每次迭代通过将每个节点转换成叶节点或将节点分割成两个子节点来更新bvh的给定级别中的节点。对象更新内核的每次迭代通过将对象重新指派给由节点更新内核的最近迭代创建的子节点或将指派给叶节点的对象标记为不再需要重新指派来更新在节点下组织的对象。节点更新内核和对象更新内核继续执行，直到所有节点是内部节点或叶节点并且所有对象已经被指派给叶节点为止。
128.所公开的技术相对于现有技术的技术优点是，利用所公开的技术，相同的内核用于处理bvh内的各个节点和对象，而不管这些节点和对象驻留在bvh内的级别如何。因此，相对于必须将用于处理各个节点的线程或处理器的数量适配成在bvh的给定级别处执行的分割操作的数量和复杂度的常规方法，可以更容易地实现所公开的技术。所公开的技术的另一技术优势在于，通过简单地改变存储在对象中的节点标识符，对象被“移动”到bvh内的不同节点。因此，所公开的技术比现有技术方法计算效率更高，在现有技术方法中，必须维护指派给bvh中的各个节点的不同对象的各个列表。这些技术优点提供了优于现有技术方法的一个或更多个技术改进。
129.1.在一些实施例中，一种用于生成包围体层次结构的计算机实现的方法包括：确定与第一节点相关联的第一组对象；生成与所述第一节点相关联的第一多个子节点；以及对于所述第一组对象中包括的每个对象，基于与所述第一组对象相关联的第一组分区将所述第一多个子节点中包括的对应子节点的标识符存储在所述对象内。
130.2.根据条款1所述的计算机实现的方法，还包括：基于与所述第一节点相关联的第一包围体和一个或更多个分区标准来确定所述第一组分区。
131.3.根据条款1-2中任一项所述的计算机实现的方法，还包括：生成与所述第一多个子节点相关联的第二组分区；以及基于所述第二组分区来生成第二多个子节点，其中所述第二多个子节点中包括的每个子节点与所述第一多个子节点中包括的对应父节点相关联。
132.4.根据条款1-3中任一项所述的计算机实现的方法，还包括：生成第二多个子节点，其中所述第二多个子节点中包括的每个子节点与所述第一多个子节点中包括的对应父节点相关联；生成所述第二多个子节点的第一组包围体；以及对于所述第一多个子节点中包括的每个父节点，基于所述父节点的两个或更多个子节点的两个或更多个包围体来生成所述父节点的包围体。
133.5.根据条款1至4中任一项所述的计算机实现的方法，还包括：基于一个或更多个叶节点标准将所述第一多个子节点中包括的第二节点转换成叶节点。
134.6.根据条款1-5中任一项所述的计算机实现的方法，其中所述一个或更多个叶节
点标准包括指派给所述第二节点的对象的数量的阈值。
135.7.根据条款1-6中任一条款所述的计算机实现的方法，还包括：基于存储被指派给所述第二节点的对象的数量的第一计数器和存储已经被指派给叶节点的对象的总数的第二计数器，存储被指派给所述第一多个子节点中包括的第二节点的对象的列表。
136.8.根据条款1至7中任一项所述的计算机实现的方法，其中确定与所述第一节点相关联的所述第一组对象包括：确定所述第一节点的第一标识符被存储在所述第一组对象中包括的每个对象内。
137.9.根据条款1至8中任一项所述的计算机实现的方法，还包括：执行多个并行操作以确定所述第一组分区。
138.10.根据条款1-9中任一项所述的计算机实现的方法，其中所述第一组分区包括分割平面。
139.11.在一些实施例中，一个或更多个非暂时性计算机可读介质，其存储有指令，所述指令在由一个或更多个处理器执行时，使所述一个或更多个处理器执行以下步骤：确定与第一节点相关联的第一组对象；生成与所述第一节点相关联的第一多个子节点；以及对于所述第一组对象中包括的每个对象，基于与所述第一组对象相关联的第一组分区将所述第一多个子节点中包括的对应子节点的标识符存储在所述对象内。
140.12.根据条款11所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：将所述第一节点创建为与包围体层次结构相关联的根节点；以及在确定所述第一组对象与所述第一节点相关联之前，将所述第一节点的第一标识符存储在所述第一组对象内。
141.13.根据条款11-12中任一项所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使得所述一个或更多个处理器执行以下步骤：确定第一对象无效；以及存储所述第一对象不应被指派给所述第一节点的指示符。
142.14.根据条款11-13中任一项所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：执行多个并行操作以生成与所述第一多个子节点相关联的第二组分区；以及基于所述第二组分区生成第二多个子节点，其中所述第二多个子节点中包括的每个子节点与所述第一多个子节点中包括的对应父节点相关联。
143.15.根据条款11-14中任一项所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：基于一个或更多个叶节点标准将所述第一多个子节点中包括的第二节点转换成叶节点。
144.16.根据条款11-15中任一项所述的一个或更多个非暂态计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：确定与所述第二节点相关联的第二组对象；以及对于所述第二组对象中包括的每个对象，存储所述对象不需要被重新指派的指示符。
145.17.根据条款11-16中任一项所述的一个或更多个非暂态计算机可读介质，其中将所述对应子节点的所述标识符存储在所述对象内包括：基于所述对象的代表点和所述对应子节点表示的包围体来确定所述对应子节点。
146.18.根据条款11至17中任一项所述的一个或更多个非暂态计算机可读介质，其中
所述指令进一步使所述一个或更多个处理器执行以下步骤：执行多个并行操作以确定所述第一组分区。
147.19.根据条款11-18中任一条款所述的一个或更多个非暂态计算机可读介质，其中所述第一组对象包括点、线、三角形或多边形中的至少一个。
148.20.在一些实施例中，一种系统包括：一个或更多个存储器，其存储指令；以及一个或更多个处理器，其被耦合至所述一个或更多个存储器，并且当执行所述指令时，所述一个或更多个处理器被配置为：确定与第一节点相关联的第一组对象；生成与所述第一节点相关联的第一多个子节点；以及对于所述第一组对象中包括的每个对象，基于与所述第一组对象相关联的第一组分区将所述第一多个子节点中包括的对应子节点的标识符存储在所述对象内。
149.以任何方式记载在任何权利要求中的任何权利要求元素和/或本技术中描述的任何元素的任何和所有组合均落入所考虑的本发明和保护的范围内。
150.出于说明目的已经呈现了各个实施例的描述，但并不意图穷尽为或限制为所公开的实施例。在不偏离所述实施例的范围和精神的情况下，对于本领技术人员来讲，许多修改和变化将是显而易见的。
151.本实施例的方面可体现为系统、方法或计算机程序产品。因此，本公开的方面可采取完全硬件实施例、完全软件实施例(包括固件、常驻软件、微代码等)或组合软件和硬件方面的实施例的形式，本文中全部统称为“模块”、“系统”或“计算机”。此外，本公开描述的任何硬件和/或软件技术、工艺、功能、组件、引擎、模块或系统都可以作为电路或一组电路实现。此外，本公开的方面可采用一种或更多种计算机可读介质中体现的计算机程序产品的形式，该计算机可读介质上包含计算机可读程序代码。
152.可以使用一种或更多种计算机可读介质的任意组合。计算机可读介质可以是计算机可读信号介质或计算机可读存储介质。例如，计算机可读存储介质包括但不限于电子、磁、光、电磁、红外或半导体系统、装置或设备，或上述任何适当的组合。计算机可读存储介质的更具体的示例(非穷尽列举)可包括：具有一根或更多根电线的电气连接、便携式计算机磁盘、硬盘、随机存取存储器(ram)、只读存储器(rom)、可擦除可编程只读存储器(eprom或闪存)、光纤、便携式光盘只读存储器(cd-rom)、光存储设备、磁存储设备或上述任何合适的组合。在本文档的上下文中，计算机可读存储介质可以是任何有形介质，其可以包括或存储程序，以供指令执行系统、装置或设备使用或与指令执行系统、装置或设备结合使用。
153.本公开的方面参照根据本公开的实施例的方法、装置(系统)和计算机程序产品的流程图和/或框图进行了描述。应理解，流程图和/或框图中的每个框，以及流程图和/或框图中的框的组合，都可以由计算机程序指令实现。这些计算机程序指令可以提供给通用计算机、专用计算机或其他可编程数据处理装置的处理器，以产生机器。该指令在由计算机或其他可编程数据处理装置的处理器执行时，使得能够实现流程图和/或框图的一个或更多个框中指定的功能/动作。此类处理器可以是但不限于通用处理器、专用处理器、特定于应用程序的处理器或现场可编程门阵列。
154.图中的流程图和框图示出了根据本公开的各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这方面，流程图或框图中的每个框可以表示代码的模块、段或部分，代码包括用于实现一个或更多个指定逻辑功能的一个或更多个可执
行指令。还应指出，在一些替代实施例中，框中指出的功能可不按图中指出的顺序发生。例如，连续显示的两个框实际上可以大致同时执行，或者这些框有时可以相反的顺序执行，这取决于所涉及的功能。还应注意，框图和/或流程图中的每个框，以及框图和/或流程图中框的组合，可以由基于专用硬件的系统实现，该基于专用硬件的系统执行指定功能或动作或专用硬件和计算机指令的组合。
155.虽然前述内容是针对本公开的实施例，本公开的其他和进一步实施例可以在不偏离其基本范围的情况下设计，其范围由所附权利要求确定。

技术特征：
1.一种用于生成包围体层次结构的计算机实现的方法，所述方法包括：确定与第一节点相关联的第一组对象；生成与所述第一节点相关联的第一多个子节点；以及对于所述第一组对象中包括的每个对象，基于与所述第一组对象相关联的第一组分区将所述第一多个子节点中包括的对应子节点的标识符存储在所述对象内。2.根据权利要求1所述的计算机实现的方法，还包括：基于与所述第一节点相关联的第一包围体和一个或更多个分区标准来确定所述第一组分区。3.根据权利要求1所述的计算机实现的方法，还包括：生成与所述第一多个子节点相关联的第二组分区；以及基于所述第二组分区来生成第二多个子节点，其中所述第二多个子节点中包括的每个子节点与所述第一多个子节点中包括的对应父节点相关联。4.根据权利要求1所述的计算机实现的方法，还包括：生成第二多个子节点，其中所述第二多个子节点中包括的每个子节点与所述第一多个子节点中包括的对应父节点相关联；生成所述第二多个子节点的第一组包围体；以及对于所述第一多个子节点中包括的每个父节点，基于所述父节点的两个或更多个子节点的两个或更多个包围体来生成所述父节点的包围体。5.根据权利要求1所述的计算机实现的方法，还包括：基于一个或更多个叶节点标准将所述第一多个子节点中包括的第二节点转换成叶节点。6.根据权利要求5所述的计算机实现的方法，其中所述一个或更多个叶节点标准包括指派给所述第二节点的对象的数量的阈值。7.根据权利要求1所述的计算机实现的方法，还包括：基于存储被指派给所述第二节点的对象的数量的第一计数器和存储已经被指派给叶节点的对象的总数的第二计数器，存储被指派给所述第一多个子节点中包括的第二节点的对象的列表。8.根据权利要求1所述的计算机实现的方法，其中确定与所述第一节点相关联的所述第一组对象包括：确定所述第一节点的第一标识符被存储在所述第一组对象中包括的每个对象内。9.根据权利要求1所述的计算机实现的方法，还包括：执行多个并行操作以确定所述第一组分区。10.根据权利要求1所述的计算机实现的方法，其中所述第一组分区包括分割平面。11.一个或更多个非暂时性计算机可读介质，其存储有指令，所述指令在由一个或更多个处理器执行时，使所述一个或更多个处理器执行以下步骤：确定与第一节点相关联的第一组对象；生成与所述第一节点相关联的第一多个子节点；以及对于所述第一组对象中包括的每个对象，基于与所述第一组对象相关联的第一组分区将所述第一多个子节点中包括的对应子节点的标识符存储在所述对象内。12.根据权利要求11所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：将所述第一节点创建为与包围体层次结构相关联的根节点；以及
在确定所述第一组对象与所述第一节点相关联之前，将所述第一节点的第一标识符存储在所述第一组对象内。13.根据权利要求11所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：确定第一对象无效；以及存储所述第一对象不应被指派给所述第一节点的指示符。14.根据权利要求11所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：执行多个并行操作以生成与所述第一多个子节点相关联的第二组分区；以及基于所述第二组分区生成第二多个子节点，其中所述第二多个子节点中包括的每个子节点与所述第一多个子节点中包括的对应父节点相关联。15.根据权利要求11所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：基于一个或更多个叶节点标准将所述第一多个子节点中包括的第二节点转换成叶节点。16.根据权利要求15所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：确定与所述第二节点相关联的第二组对象；以及对于所述第二组对象中包括的每个对象，存储所述对象不需要被重新指派的指示符。17.根据权利要求11所述的一个或更多个非暂时性计算机可读介质，其中将所述对应子节点的所述标识符存储在所述对象内包括：基于所述对象的代表点和所述对应子节点表示的包围体来确定所述对应子节点。18.根据权利要求11所述的一个或更多个非暂时性计算机可读介质，其中所述指令进一步使所述一个或更多个处理器执行以下步骤：执行多个并行操作以确定所述第一组分区。19.根据权利要求11所述的一个或更多个非暂时性计算机可读介质，其中所述第一组对象包括点、线、三角形或多边形中的至少一个。20.一种系统，包括：一个或更多个存储器，其存储指令，以及一个或更多个处理器，其被耦合至所述一个或更多个存储器，并且当执行所述指令时，所述一个或更多个处理器被配置为：确定与第一节点相关联的第一组对象；生成与所述第一节点相关联的第一多个子节点；以及对于所述第一组对象中包括的每个对象，基于与所述第一组对象相关联的第一组分区将所述第一多个子节点中包括的对应子节点的标识符存储在所述对象内。

技术总结
本发明的一个实施例阐述了一种用于生成包围体层次结构的技术。该技术包括确定与第一节点相关联的第一组对象。该技术还包括生成与第一节点相关联的第一多个子节点。该技术还包括：对于第一组对象中包括的每个对象，基于与第一组对象相关联的第一组分区将第一多个子节点中包括的对应子节点的标识符存储在对象内。内。内。


技术研发人员：I
受保护的技术使用者：辉达公司
技术研发日：2022.10.17
技术公布日：2023/10/6