包围体层次的形成的制作方法

包围体层次的形成
1.本技术要求2023年3月31日提交的英国专利申请gb2204657.7、gb2204658.5和gb2204664.3；以及2023年2月8日提交的gb2301775.9的优先权，这些专利申请以全文以引用方式并入本文中。
技术领域
2.本发明涉及包围体层次的形成。


背景技术：

3.处理器是用于执行机器代码指令集的设备，该机器代码指令集包括各种通用指令，诸如加法、乘法等。诸如图形处理单元(gpu)的专用处理器可以通过在固定功能硬件电路中包括用于执行一种或多种特定类型操作的一个或多个专用硬件模块来适应特定的应用。取决于处理器的设计，这种硬件可以例如由处理器的指令集中的一个或多个专用指令类型来调用，或者通过写入专用寄存器或写入专用存储器区中的缓冲器等来调用。
4.光线跟踪是图形处理器可用于以软件或专用硬件或者更典型地以组合来执行的一个任务。光线跟踪是指一种图形处理技术，其用于通过跟踪光线穿过建模环境的路径并且模拟光线与沿途物体相遇的效果来生成图像。建模的光线从建模光源被跟踪到建模视点(前向光线跟踪)，或反之从建模视点向后被跟踪到建模光源(即，反向光线跟踪，其通常更有效率，因为前向光线跟踪通常导致对轨迹最终从未命中视点的光线进行处理)。可以通过光线的起点的坐标、指定光线方向的矢量、沿着该矢量的光线的最大和最小范围以及任选地光线颜色来描述光线。在反向光线跟踪的情况下，光线跟踪始于从图像中的每个像素将光线投射到建模环境中。光线可以在建模环境中与之相互作用的对象被分成几何图元，例如三角形小面。对于每个光线，光线跟踪包括寻找与光线相互作用的最接近的几何图元(如果有的话)。在一些图形处理器中，这种搜索在固定功能硬件中执行。当入射光线相交时，它接着可终止、反射或折射。反射或折射引入相对于入射光线具有新方向的一个或多个二次光线，该入射光线被终止(即，反射或折射光线被建模为新光线)。二次光线也可以将相对于入射光线的新值(颜色)进行累加。
5.光线跟踪可以在使用通用指令的软件中执行，或者在专用硬件中执行，或者在它们的组合中执行。例如，在一个gpu设计中，在gpu上运行的驱动软件形成“包围体层次”(bvh，稍后将更详细地讨论)，该包围体层次是将建模环境划分成用于搜索目的的层次区的数据结构。驱动软件将此数据结构写入存储器中的专用缓冲器。在硬件中实现的专用“遍历单元”被布置成随后使用bvh来检测各种建模的光线(源自应用软件，并且被写入被称为光线缓冲器的另一专用存储器区)是否会与建模环境中的几何图元相交。
6.确定光线与几何图元的相互作用的效果通常在软件中进行解析解决。进行此操作的程序被称为着色器程序。通常存在运行以处理不同交互场景的不同着色器程序。
7.例如，不同着色器程序可以包括：错过着色器程序、最近命中着色器程序、任何命中着色器程序和相交着色器程序。当光线未命中任何东西时，运行错过着色器程序。当光线
命中几何形状时，运行最近命中着色器程序，其中已知将保持此命中并且需要所述程序计算光在命中点处的效果。当光线命中几何形状时，运行任何命中着色器程序，但还需要该程序决定是否保持该命中。如果保持该命中，则随后将运行最近命中着色器程序。当光线命中其中具有用户定义的几何形状的框时，运行相交着色器程序，并且需要该程序程序性地生成或从存储器加载该几何形状，检查这些几何形状中哪一个被光线命中，然后决定是否保持该命中。如果保持该命中，则随后将运行最近命中程序。以上是从光线跟踪api标准导出的分类。在一个具体实现中，任何命中着色器和相交着色器可以一起被分组到遍历着色器中。
8.更一般来说，为支持光线跟踪而进行的操作可以包括：光线生成(产生光线)、光线相交(针对图元或含有图元的框来测试光线)、光线遍历(搜索上述框的树或其他这样的场景加速结构，并且沿树的行踪对相交进行调度)。
9.包围体层次(bvh)是用于光线遍历的数据结构类型。bvh的数据结构采用树结构的形式，其中节点表示建模环境中的空间区(通常是框)，并且从父节点到子节点的边缘表示由子节点表示的区嵌套在由父节点表示的区内。因此，这些节点从根节点下至处于每个分支的最低层级的叶节点以分层层级排列。由每个叶节点表示的空间区含有相应的一个或多个几何图元或者几何图元的至少部分。在光线遍历机制中使用bvh来搜索与建模的光线相交的几何图元。该搜索包括首先确定光线将在从根向下的第一层级处遍历哪个节点，以及随后确定光线将与该节点的子节点中的哪个子节点相交等，直到该搜索以找到光线所遍历的叶节点，并且确定光线是否与该叶节点内所含有的图元或者图元中的任何图元相交而结束。
10.形成bvh的一种简单方式是将建模环境对半划分，并且随后再将每一半对半划分，等等。因此在根下方的第一层级处，根具有两个子节点，每个子节点表示不同的一半空间；随后，这些节点中的每个节点(除非其为叶)在向下的下一层级处具有其自身的两个相应的子代(根的孙代)，每个子代将其相应父代的包围框再对半划分，以此类推。在每一层级处，该空间可以被对半划分，例如通过距离，或通过体素的数量，或通过图元质心的中间坐标(根据图元质心到由一个轴上的中间坐标给定的平面的位置，每“一半”被大小设定成使得其含有由其父代包围的几何图元的一半)。
11.然而，搜索bvh树的效率取决于建模空间区在树的不同节点之间被分割的方式。上文描述的简单方法不一定会产生平均来说为了确定光线是否与图元相交而需要搜索的计算次数最少的树。存在用于估计搜索bvh的预期计算成本的已知度量。一种这样的度量被称为表面积启发式(sah)，其对确定随机光线是否与给定bvh的图元相交的预期计算成本进行测量。
[0012]“并行再插入包围体层次优化”(梅斯特(meister)和比特纳(bittner)，2018年)描述了一种方法，其用于对将建模空间分割成二进制bvh中的不同大小的包围框的方式进行优化。该方法以某个起始树开始，随后迭代地考虑不同的可能的“再插入”。每种可能的再插入包括取一个“输入节点”(现有bvh中的子节点中的一个子节点)，以及考虑将该输入节点移动到树的不同部分。受影响节点的边界将收缩或增长以适应输入节点的移动。如果输入节点将被移动，则由于该树是二叉树，因而输入节点的旧兄弟(sibling)将变为“独子”或“唯一子代”，从而使旧父代冗余。因此，这将意味着移除旧父代，并且使旧兄弟成为旧父代
的父代(输入节点的旧祖代)的子代。并且在将再插入输入节点的地方，创建新节点以孕育输入节点和其新兄弟(“目标节点”)，从而维持树的二叉结构。
[0013]
梅斯特的方法经历了几次迭代。每次迭代包括考虑多个可能的候选再插入，根据sah度量对每个候选再插入进行评分以确定哪个再插入将是有益的(即，将减少预期计算成本)，并且随后选择执行这些再插入中的至少一些再插入(即，使用所选再插入来更新bvh)。一旦已经执行当前迭代的所选再插入，该方法便循环到另一次迭代，在该迭代中，该方法从新更新的bvh的新起始点考虑进一步可能的再插入，以此类推。


技术实现要素：

[0014]
梅斯特的方法的一个问题是，在多次迭代内对候选再插入进行搜索、评分和执行的过程本身会招致处理资源。因此，在优化搜索过程本身的复杂性与可能实现的sah(等)的可能节省之间进行权衡将是有益的。
[0015]
最有益的sah节省可能是从更接近树顶端的候选再插入中找到的。因此，通过将该方法限制在某个搜索下限之上的输入节点，这有利地限制了该方法的处理负担，而不会过度损失光线遍历中可能的计算节省。另外，候选再插入的目标节点也可以被限制在此搜索下限之上。这也有利地限制了搜索的处理负担，而不会过度损失可能的节省。
[0016]
另外，最有益的sah节省可能是从在输入节点的特定距离内的候选再插入中找到的。因此，通过将搜索限制到输入节点之上的特定搜索上限，这再次有利地限制了搜索的处理负担，而不会过度损失可能的节省。
[0017]
根据本文中公开的一个方面，提供了一种由图形处理器执行的方法。所述方法包括：获得起始bvh包围体层次，所述包围体层次是包括表示建模环境中的不同3d空间区的节点的数据结构，所述数据结构包括树，在所述树中，所述节点从根节点下至多个叶节点分层排列，其中由每个叶节点建模的区涵盖至少一个图元或图元的部分。所述方法还包括以第一次迭代开始，执行一次或多次迭代，所述第一次迭代以作为当前bvh的所述起始bvh开始。每次迭代包括：对于所述当前bvh的所述树中的多个输入节点中的每个相应输入节点，搜索至少一个相应候选再插入，所述至少一个相应候选再插入将在所述树中将所述相应输入节点从旧父代移动到新父代，并且与所述当前bvh相比，所述至少一个相应候选再插入将减少搜索所述树以确定建模的光线是否与所述图元中的一个图元相交的预期计算成本(根据用于估计所述计算成本的度量)；以及执行至少第一次更新以使用从所述候选再插入当中选择的一个或多个所选再插入来更新所述当前bvh。在对候选再插入的该搜索中，以下中的任一者或两者：a)该新父代被限制为通过不超过该当前bvh的该树中在该旧父代之上预定数量的分层层级的祖先而与该旧父代相关，以及/或者b)该输入节点被限制为处于或高于该当前bvh的该树中在根节点之下预定数量的分层层级的分层层级。
[0018]
在实施方案中，所述新父代也可以被限制为处于或高于所述当前bvh的所述树中在根之下预定数量的分层层级的分层层级。
[0019]
给定的再插入可以被定义为仅再插入单个相应输入节点(没有树的其他节点)的操作。因此，候选再插入中的一个、多个或所有候选再插入中的每个候选再插入将仅再插入其一个相应输入节点(并且不插入树的其他节点)。也就是说，每个这种再插入将仅把其一个相应输入节点移动到树的另一分支(移动到目标节点旁边的位置，与例如将输入节点与
目标节点交换相反)。
[0020]
这意味着在候选再插入中的一个、一些或所有候选再插入中的每个候选再插入中，候选再插入i)增加新父代处的子节点的数量(例如，如在诸如图7中的非二叉再插入的情况下，稍后更详细地讨论)；或者ii)将新节点作为新父代添加到数据结构中(例如，如在诸如图6中所示出的二叉再插入的情况下，也在稍后更详细地讨论)。
[0021]
从候选当中选择用于执行的所选再插入中的任何或所有所选再插入也可以是满足上述定义的再插入。
[0022]
在实施方案中，所述方法可以包括根据所述度量来确定起始分数，所述起始分数是起始bvh的分数，其中第一次迭代以作为当前bvh的当前分数的起始分数开始。每次迭代(或其中的至少一些迭代)随后可以包括更新当前分数以考虑第一次更新。当前分数是当前bvh的总分数的运行值。这可以用于例如确定当前bvh是否收敛，并且因此确定是执行所述迭代中的下一次迭代还是终止所述方法。作为另一示例，bvh的当前总分数可用于确定下一次迭代中的搜索的稀疏度参数。可替代地，不必每次迭代都更新分数。
[0023]
在实施方案中，bvh的每次更新包括重新计算具有受bvh更新影响的边界的任何节点进行建模的包围体的边界。可替代地，不必每次更新都更新包围体。
[0024]
梅斯特的方法的另一个问题是，其假设树必须在每次再插入时总是保持为二叉树，该问题可以在本文中公开的实施方案中得到所解决。本文中应认识到，这不适当地限制了减少sah(或类似情况)的机会。有时，对于给定输入节点，不采用二叉树的候选再插入——诸如通过允许给定父代的三个子代——可以比相同输入节点的可能二叉再插入给出更好的sah节省。因此，至少在评分阶段中，至少考虑一个或多个可能的再插入将是有益的，该一个或多个可能的再插入没有在整个树中保持严格的二叉结构。
[0025]
因此，在实施方案中，在迭代中的至少一次迭代的搜索步骤中，一个或多个候选再插入可以被允许包括至少一个候选再插入，该至少一个候选再插入将为旧父代留下多于一个子代，并且/或者向新父代给出多于两个子代。在实施方案中，在迭代中的至少一次迭代的更新步骤中，所选再插入中的至少一个所选再插入可以为相应旧父代留下多于一个子代，并且/或者给出相应新父代多于两个子代。
[0026]
在实施方案中，该方法允许评估两种再插入类型：二叉再插入(例如，如在梅斯特的现有方法中所见)和非二叉再插入(在现有子列表中插入节点)。
[0027]
在实施方案中，处理器可以包括缓冲器，该缓冲器包括多个槽，树中的节点中的每个相应节点被表示为多个槽中相应一个槽中的条目。在这类实施方案中，当在所述迭代中的一次迭代中移除旧父代时，相应槽被释放用于存储新条目，该新条目表示由在所述迭代的同一或后一迭代中的所选再插入中的另一所选再插入创建的新创建的节点。所述多个槽可以是固定数量的槽。
[0028]
在另外的实施方案中，图形处理器可以被配置成运行多个再插入进程，其中每个再插入进程被配置成用于相应输入节点，并且每个再插入进程由相应进程id来标识。再插入进程或这类进程的部分可以彼此并行执行。在这类实施方案中，用于相应输入节点的再插入进程可以包括：对相应输入节点的候选再插入执行搜索；根据所述度量执行相应输入节点的候选再插入的评分；以及如果相应输入节点的候选再插入中的任何一个候选再插入被选择作为所选再插入中的相应所选再插入，则通过使用相应的所选再插入执行当前bvh
的更新来执行对所选再插入的执行。
[0029]
在实施方案中，另一所选再插入(其使用空闲槽)可以为其相应的旧父代留下至少两个子代，并且创建新创建的节点作为相应的新父代，以便适应作为树中的另一目标节点的兄弟的输入节点。
[0030]
允许非二叉再插入的一个问题是它可能使进程不确定。例如，考虑一种场景，其中不同的输入节点由以循环方式等调度的不同线程进行处理。如果一个线程可以通过从树中移除节点来释放槽，并且另一线程可以重用该槽来创建新节点，则程序的确切行为将取决于哪个线程碰巧首先被调度。使用严格的二叉树，这不是一个问题，因为从其旧位置移除输入节点总是恰好移除一个节点，并且在其新位置处插入输入节点总是恰好创建一个新节点，因此处理该再插入的进程将仅针对同一再插入的新创建的节点重用所删除节点的槽。然而，如果允许非二叉行为，则这不一定将发生在每个可能的再插入中。虽然不是必要的，但程序允许非二叉树同时仍然保持确定性将是有益的——即如果重新运行程序(例如在测试等中)，对于同一场景的同一帧或同一时间点，将总是得到完全相同的结果。
[0031]
因此，在实施方案中，在所选再插入中的任何所选再插入的执行中，除了由与在同一迭代或前一迭代中释放槽的进程具有相同进程id的进程所创建的新创建的节点之外，没有一个空闲槽可以被允许用于存储表示任何节点的条目。
[0032]
也就是说，处理器包括缓冲器，该缓冲器包括多个槽，树中的节点中的每个相应节点被表示为多个槽中相应一个槽中的条目。此外，不同的输入节点可以由不同的再插入进程(例如线程或着色器调用)来处理，每个再插入进程由进程id来标识，并且再插入进程中的至少一些再插入进程(至少部分地)彼此并行地执行。在此情况下，当再插入进程中的第一再插入进程通过从树中移除节点来释放槽时，该方法可以包括仅允许与第一再插入进程具有相同进程id的再插入进程重用空闲槽，以便创建新节点。重用该槽的再插入进程可以是第一再插入进程本身或者具有相同进程id的另一再插入进程。优选地，除了由与释放相应槽的再插入进程具有相同进程id的再插入进程中的一个再插入进程创建的新创建的节点之外，不允许使用空闲槽来存储表示任何节点的条目。
[0033]
换句话说，所述处理器包括缓冲器，所述缓冲器包括多个槽，树中的节点中的每个相应节点被表示为多个槽中的相应一个槽中的条目；其中所述图形处理器被配置成运行多个进程，包括彼此并行的至少一些进程，其中每个进程被配置成处理所述输入节点中的相应一个或多个输入节点，每个进程由相应进程id来标识；其中在迭代中的至少一次迭代(一次或多次释放迭代)的更新步骤中，从树中移除旧父代，并且释放旧父代的相应槽，以用于存储表示由所选再插入中的另一所选再插入创建的新创建的节点的新条目；并且其中没有一个空闲槽(没有空闲槽，即没有从所述释放迭代中的任何释放迭代中释放的任何槽)被允许用于存储表示除了新创建的节点之外的任何节点的条目，所述新创建的节点是由与在同一迭代或前一迭代中释放所述槽的进程具有相同进程id的进程创建的。
[0034]
这有利地在节点缓冲器的操作范围内提供新节点的确定性分配方案。
[0035]
该方法可以通过针对每个进程id维持由具有相应进程id的进程释放的空闲槽的列表来实现；其中如果在与相应进程id相关联的列表上存在来自同一迭代或前一迭代的空闲槽，则仅允许每个进程搜索将使用前一迭代中空闲的槽的候选再插入。
[0036]
在实施方案中，由第一再插入进程处理的所选再插入可以包括为相应旧父代留下
仅一个剩余子代的再插入，使得相应旧父代从树中被移除，并且剩余子代成为旧父代的父代的子代。
[0037]
在实施方案中，另一所选再插入可以为其相应的旧父代留下至少两个子代，并且创建新创建的节点作为相应的新父代，以便适应作为树中的另一目标节点的兄弟的输入节点。
[0038]
在实施方案中，在所选再插入中的任何所选再插入的执行中，空闲槽可用于存储表示由与在同一迭代或前一迭代中释放槽的进程具有相同进程id的进程所创建的新创建的节点的条目。
[0039]
在实施方案中，所述方法可以包括仅当所述槽由在前一迭代中与进程中的所述一个进程具有相同的相应进程id的进程释放时，才搜索将使用在前一迭代中释放的槽的候选再插入的所述进程中的一个进程。
[0040]
此外，本文中公开的实施方案的替代或额外特征中，根据冲突检查来选择被选择用于包括在所述第一次更新中的一个或多个所选再插入，以确定所述候选再插入的任何组是否会影响所述当前bvh的所述树的彼此相同的部分，并且如果是，则仅选择所述组中的一个候选再插入以包括在所述第一次更新中。在一些这类实施方案中，其中所述迭代中的至少一次迭代还可以包括在所述第一次更新之后，在同一迭代内执行第二次更新，以使用所述组中的另一候选再插入来更新所述当前bvh。
[0041]
重试先前冲突的再插入(导致每次迭代有多个再插入集)有利地允许进一步减少sah(或其他这种度量)的机会，而不需要重复搜索候选再插入。所述方法可以包括在重试先前冲突的再插入之前验证这些再插入。
[0042]
本文中公开的任何实施方案的方法可以由逻辑来执行，该逻辑在存储器中所存储的软件中实现，或者被配置成在一个或多个上运行；或者在固定功能硬件电路中实现，或者在诸如pga或fpga的可配置或可重新配置的硬件电路中实现；或者在硬件与软件的任何组合中实现。
[0043]
在任何实施方案中，逻辑可以在集成电路上的硬件中体现。可以提供一种在集成电路制造系统处制造包括所述逻辑的处理器的方法。可以提供一种集成电路定义数据集，所述集成电路定义数据集当在集成电路制造系统中被处理时配置所述系统以制造该逻辑或处理器。可以提供一种非暂态计算机可读存储介质，该非暂态计算机可读存储介质上存储有逻辑或处理器的计算机可读描述，该计算机可读描述当在集成电路制造系统中被处理时使集成电路制造系统制造包含该逻辑或处理器的集成电路。
[0044]
可以提供一种集成电路制造系统，包括：非暂态计算机可读存储介质，其上存储有逻辑或处理器的计算机可读描述；布局处理系统，其被配置成处理所述计算机可读描述，以便生成包含所述逻辑或处理器的集成电路的电路布局描述；以及集成电路生成系统，其被配置成根据所述电路布局描述制造所述逻辑或处理器。
[0045]
可以提供一种用于执行本文中描述的任一方法的计算机程序代码。可提供非暂态计算机可读存储介质，其上存储有计算机可读指令，当在计算机系统处执行时，所述计算机可读指令促使所述计算机系统执行本文中所描述的方法中的任一种方法。
[0046]
如对本领域的技术人员显而易见的，上述特征可以适当地组合，并且可以与本文所述的示例的任何方面组合。
[0047]
提供此发明内容仅仅是为了说明本文公开的一些概念及其可能的实施方式。发明内容部分所述的并非全部内容都是为了限制本公开的范围。相反，本公开的范围仅受权利要求的限制。
附图说明
[0048]
现在将参考附图详细描述示例，在附图中：
[0049]
图1是用于在图形处理器上的软件和/或硬件中执行光线跟踪的一些逻辑的示意框图，
[0050]
图2是包围体层次(bvh)的示意图，
[0051]
图3a和图3b给出了bvh中的包围几何图元的一些示例叶节点的示意图，
[0052]
图4a和图4b给出了bvh中的包围几何图元的叶节点的一些其他示例的示意图，
[0053]
图5是示意性地示出形成bvh的方法的流程图，
[0054]
图6给出了在bvh的形成中进行再插入的方法的示例的示意图，
[0055]
图7给出了根据本文中公开的实施方案的考虑可能的二叉和非二叉再插入的示例的示意图，
[0056]
图8是在其中实现图形处理系统的计算机系统的示意性框图，
[0057]
图9是用于生成体现图形处理系统的集成电路的集成电路制造系统的示意性框图，
[0058]
图10给出了根据本文中公开的实施方案的可借以重试再插入中的一个再插入的冲突候选再插入的示例的示意图，
[0059]
图11给出了根据本文中公开的实施方案的可借以在后一迭代中重试再插入中的一个再插入的冲突候选再插入的另一示例的示意图，
[0060]
图12给出了根据本文中公开的实施方案的在搜索再插入时限制搜索上限的示意图，
[0061]
图13是根据本文中公开的实施方案的通过允许不同冲突重试次数的方案而实现的sah减少的模拟结果的曲线图，
[0062]
图14a是根据本文中公开的实施方案的通过施加搜索下限而实现的sah减少的模拟结果的曲线图，并且
[0063]
图14b是根据本文中公开的实施方案的通过施加搜索上限而实现的sah减少的模拟结果的曲线图。
[0064]
附图示出了各种示例。技术人员将了解，附图中所示出的元件边界(例如框、框的组，或其他形状)表示边界的一个示例。在一些示例中，情况可能是一个元件可以被设计为多个元件，或者多个元件可以被设计为一个元件。在适当的情况下，贯穿各附图使用共同的附图标记来指示类似的特征。
具体实施方式
[0065]
借助于示例呈现以下描述，以使得本领域的技术人员能够制造和使用本发明。本发明不限于本文中所描述的实施方案，并且对所公开实施方案的各种修改对于本领域的技术人员将显而易见。现在将仅借助于示例来描述实施方案。
[0066]
本公开提供了针对光线跟踪优化包围体层次(bvh)的方法。在使用计算着色器以在gpu上执行的实施方案中，在为了快速执行而被并行化的后处理中，现有层次的质量得到改善。
[0067]
根据本文中公开的实施方案，并行再插入方法(诸如梅斯特的方法)可以通过以下优化中的任何一个、多个或全部优化来扩展。
[0068]
i.非二叉层次的优化。非二叉bvh可以提高跟踪性能并且减小带宽，因此能够优化考虑到这一点的现有bvh并且输出具有这些益处的bvh是有用的特质。
[0069]
ii.冲突再插入的重试。不是由于与较高评分再插入的冲突而舍弃对层次的建议更新，而是可以在之后重试这些再插入。这增加了每次搜索对bvh的有用更新的数量(每次迭代最昂贵的阶段)。使用这些重试，每次迭代可以执行多组再插入。
[0070]
iii.仅优化层次中的前2k个节点(以广度优先顺序)，从而减少计算时间，对最终层次质量的影响最小。
[0071]
iv.限制层次中新位置(
‘
目标’)的搜索范围，从而减少计算时间，对最终层次质量的影响最小。
[0072]
bvh概述
[0073]
图1示意性地示出了逻辑100，该逻辑可以实现根据本文中公开的实施方案的所公开的方法中的任何一个或多个方法。逻辑100包括包围体层次(bvh)形成模块102、bvh存储装置104、光线遍历单元106和光线缓冲器108。bvh形成模块102和光线遍历单元106中的每一者操作性地耦合到bvh存储装置104。遍历单元106也可以操作性地耦合到光线缓冲器108。在操作中，bvh形成模块通过稍后将更详细讨论的迭代进程来形成bvh，并且将所得bvh存储在bvh存储装置104中。建模的光线可以源自运行在图形处理器或主处理器上的应用软件，并且被存储在光线缓冲器108中。光线遍历单元106(也可称为光线相交单元等)从bvh存储装置104中读取所存储的bvh，并且从光线缓冲器108中读取光线，并且使用bvh来确定建模的光线中的每个建模的光线是否与bvh的叶所包围的一个或多个几何图元相交。
[0074]
逻辑100可以使用被存储在一个或多个存储器单元中的软件来实现，并且被布置成在图形处理器的一个或多个执行单元上运行。可替代地，逻辑100可以在图形处理器的固定功能硬件中实现，或者在诸如可编程门阵列(pga)或现场可编程门阵列(fpga)的可配置或可重新配置的电路中实现。作为另一替代方案，逻辑100可以用硬件与软件的组合来实现。在一个示例具体实现中，bvh形成模块102在图形处理器的驱动软件中实现，并且光线遍历单元106被实现为图形处理器中的固定功能硬件单元。bvh存储装置104可以在专用存储器或专用存储器区(诸如ram)中实现，或者在专用寄存器中实现。类似地，光线缓冲器108可以在专用存储器或专用存储器区(例如ram)中实现，或者在专用寄存器中实现。
[0075]
图2借助于示例示出了包围体层次(bvh)200的概念。bvh包括被布置为树的数据结构，其中节点被布置在分层层级或分层中，从多个叶节点206，通过内部节点(204)的一个或多个层级，直到根节点(202)。根节点202和每个内部节点204(即除了叶节点206之外的每个节点)各自是相应的一个或多个子节点的父代，相应子节点是其他内部节点204或叶节点206。根节点202仅为父代，而不是子代；并且叶节点206仅为子代，而不是父代。在二叉树中，根节点202和每个内部节点204(除了叶之外的每个节点)各自恰好具有两个子代。
[0076]
注意：在本文中提及树以层级或层排列并非暗示所有的叶节点206必须处于树中
的相同深度。在实践中，bvh通常将是不平衡的，并且具有处于不同深度的叶206。
[0077]
每个节点202、204、206表示(模型化)建模环境中不同的相应空间体——即所谓的包围体，即3d空间区。由每个叶节点206表示的体积涵盖至少一个相应几何图元或相应几何图元的部分。根202通常表示整个环境。从子代到父代的边缘表示由子代表示的空间体包含(嵌套)在由父代表示的区内。沿着树从根到叶，每个内部节点204表示嵌套在其父节点内的较小空间区，直到树在叶节点处到达包围体的最小层级。
[0078]
bvh提供了一种针对光线与几何图元之间的相交搜索建模环境中的空间体的方式。几何图元是几何单元(例如三角形小平面)，根据这些几何单元，可以在建模环境内形成较大对象。例如，曲面的近似可以由多个较小三角形小平面构成。几何图元有时简称为图元。光线遍历的目的是确定哪些光线与建模环境内的哪些图元相交。
[0079]
注意：如本文中提及的几何图元不限于简单的三角形或多边形图元，并且该术语还可以涵盖进程图元的可能性。这些是编程定义的形状，例如具有相关联包围框的数学定义的球体，对于这些形状，一旦着色器已经确定光线是否与该框相交，就可以使用着色器来确定光线是否命中该形状。
[0080]
根据bvh，建模环境的3d空间被划分成越来越细的子部分(通常是框)，这些子部分被描述为树(传统上是二叉树)中的节点，一直到表示层次中子部分的最小层级的树的叶。一般来说，取决于所使用的特定方案和所建模的特定几何形状，由给定叶节点206表示的包围体可以恰好涵盖一个几何图元、超过一个几何图元或几何图元的一部分(分数)。例如，特定方案可以对叶节点206可含有的图元数量具有阈值。
[0081]
应注意，虽然图元可以仅为单个点，但图元更通常将是2d或3d形状，并且因此图元不一定总是完全适配到一个包围框或另一包围框中。包围体可以彼此重叠，并且给定图元(或其部分)有时可以在除了在bvh中引导到该图元的包围框之外的包围体内被找到。此外，可以构建出具有孕育单个图元的多个体积的bvh。
[0082]
图3a和图3b给出了一些示例。在图3a中，两个叶节点206的包围框重叠，但各自仅指向它们在层次中的单个对应图元301(在此情况下是三角形)。在图3b中，对于三角形图元301，具有两个较小的包围框而不是具有一个较大的包围框来将该图元包围得更紧可能是有益的。因此，在层次中将有两个叶节点206孕育同一图元301。
[0083]
节点202、204、206中的每一者可以由保存在节点缓冲器110的相应槽中的数据来表示，其中每个节点一个槽。节点缓冲器110由bvh模块102维持，并且取决于具体实现，该节点缓冲器可以在通用存储器、专用存储器或专用存储器区或者专用寄存器中实现。
[0084]
为了讨论起见，个别包围体在本文中可以被称为框，但这不是限制性的，并且更一般来说，包围体可以采取任何形状。本文中对包围框的任何引用可以更一般地用术语包围框或空间区来代替。
[0085]
为了确定给定光线与哪些图元相交，光线遍历单元106首先确定光线与树的顶层级处的哪个(些)包围框相交，随后在那个/那些框内确定光线与下一层级处的哪个(些)框相交，以此类推。这比仅仅将每个图元与光线进行比较更有效。应注意，该过程不一定只在与光线相交的第一框处停止(即不假设一个框被另一框遮挡)，因为光线可能命中框，但仍然未命中该框内的所有图元。
[0086]
为了确定由bvh 200中的不同节点204、206表示的包围框，一种用于划分空间的简
单方式便是对半划分，随后再将每一半对半划分，以此类推；例如，通过沿某个轴(诸如x轴)按距离将空间对半划分，或者通过使用图元质心的x坐标沿某个轴(诸如x轴)划分中间坐标的任一侧(换句话说，划分空间以使得图元质心的一半落在划分的一侧，并且图元质心的另一半落在另一侧)。给定图元的质心可以是图元本身(例如三角形)的质心，或者是图元周围的包围框的质心。
[0087]
为了处理图元可能不是单个点，并且因此图元并不总是完全适配到一个包围框或另一包围框中的事实，该简单方法的基本具体实现可以使用图元的包围框的质心来确定它应该去往分割的哪一侧——图元可能不完全是一侧或另一侧，并且这是框之间可能被引入重叠的地方。图4a示出了针对每个叶206保留完整图元301的此基本“对象分割”方法的示例。这里，点表示质心。稍微更复杂的具体实现可能会决定“切穿”图元，并且将框一分为二，从而形成如图4b中所示出的情形。
[0088]
sah(表面区域启发式)是一种用于对建模空间在bvh的节点之间的分割方式进行评分的度量。对于给定的树或子树，该度量测量确定随机光线是否与树或子树中的图元相交所需的预期计算操作数量。为了对树或子树(例如整个bvh或其一部分)进行评分，对所讨论的树或子树中的每个层级处的每个节点进行单独评分，并且随后树或子树作为整体的分数是个别节点的分数的总和。
[0089]
sah是基于相对于根包围体的表面积的包围体的表面积乘以其子代计数。也存在可以以相同方式使用的其他度量。例如，可以仅使用两个框的表面积，而不是表面积乘以子代计数。在以下描述中，可以借助于示例来引用sah，但是这不是限制性的，并且更一般来说，这可以由用于估计确定光线是否与给定bvh的图元相交的预期计算成本的任何度量来代替。
[0090]
通常，当查询bvh时，希望找到光线首先与哪个图元相交——即与光线原点
‘
最近’的相交。该度量并不假设图元将被命中——查询的结果可能是光线未命中所有图元。但是如果光线确实相交，则(至少在实施方案中)由该度量测量的成本是找到最近的相交的预期计算成本。因此，该度量测量预期操作数量以确定结果——命中或未命中——并且如果命中多个图元，则使用
‘
最近的’。例如，这就是sah工作的方式。
[0091]
为避免疑问，应注意，光线遍历可能不一定首先找到最近的相交。例如，如果发现光线与叶节点相交，并且该叶节点含有多个图元，则光线遍历算法可以测试所有那些图元以确定哪些图元被命中，并且随后确定哪个图元是最近的；或者该光线遍历算法可以找到相交的不同叶节点，并且将再次从不同节点中识别出任何相交的图元，并且随后确定最近的图元。
[0092]
bvh形成模块102可被布置成找到使sah(或等效地优化任何这种度量)的bvh树，即，使当搜索树以确定光线是否与图元相交时在光线遍历中将招致的平均计算成本最小化。应注意，如本文中使用的术语“最小化”或“优化”不一定限于找到绝对完美的解决方案，而是更一来说，也可以意味着迭代地趋向于改进的解决方案，该改进的解决方案可能不是所有理论上可能的解决方案中的绝对最小值或最优解决方案，但它至少是精修sah分数(等)的迭代进程的累积。
[0093]
特别地，迭代地修改bvh以试图降低分数的过程本身会招致处理资源，因此将在用于bvh优化的处理资源与这将在光线遍历中实现的可能节省之间进行权衡。
[0094]
优化工作通过以某个初始bvh树开始(例如以上述的简单方式确定)，随后考虑可能的候选再插入——将节点从树中的一个父代移动到另一父代。只有当移动(单独*)减少了整体sah时，该优化工作才将通过对树进行实际更新来执行。(*可能存在以下情形：其中当执行两个特定的再插入时，其中一个再插入使另一再插入实际上增加了sah，但这考虑起来较复杂，因此再插入是在假设多次再插入的平均值通常将得到净减少的基础上单独评估的)。
[0095]
测试候选再插入随后执行再插入的此进程可以以迭代方式执行多于一次。
[0096]
再插入是其中输入节点i(以及其后代中的任何后代)被移除并且被再插入到bvh的树中的目标节点t旁边的情况。图6中示出了示例。本文中的“输入节点”仅为意指当前bvh中于再插入中被移动(或者被考虑在候选再插入中被移动)的节点，即再插入操作的输入。当移动输入节点i时，受移动影响的任何上游节点的包围体可以相应地收缩或增长。例如，在所示出的示例中，p'的父代的边界将增长以适应i的边界。
[0097]
另外，应注意左图中的父代p是如何消失的，因为在此示例中，该树是二叉树，并且父代不能只具有一个子代。当输入节点i被移除时，父代p只具有一个子代，即输入的兄弟节点s。为了维持二叉结构，父代p被移除并且由树中的兄弟s替换。节点缓冲器110中的此空闲节点的槽随后可以被回收，以存储输入节点i和目标节点t(新的兄弟)两者的新父代p'。此过程假设并维持二叉树。
[0098]
在输入节点的唯一兄弟被留下，并且输入节点的旧父代被移除的场景中，这可以被称为“单独移除”。在技术上，被移除的是旧父代，而不是单独者本身(如果剩下的唯一旧兄弟被称为“单独者”)，但这等效于移除单独者，并且更新父代的特性以进行匹配。在实践中,“单独移除”是通过移除父代而不是单独者来完成的，因为单独者已经含有所需的大部分数据(边界、子指针、子计数等)，因此这避免了需要通过简单地移除父代来将此信息复制到父代中。因此术语“单独移除”可以仅意味着对树进行编辑来移除单个子案例。
[0099]
通过在层次中搜索使给定输入节点的预期sah减少最大化的目标节点来识别再插入：
[0100]
■
移除该节点可以使树中该该节点上面的节点的边界收缩，从而减少sah(节点也可能不影响树中该节点上面的节点的边界，例如，如果该节点不接触旧父代框的边中的任何边，则移除该节点对父代将没有影响)；
[0101]
■
再插入节点可能会增加上面节点的边界，从而增加sah(同样也可能将没有效果)；并且
[0102]
■
如果减少的量超过了增加的量，则sah就有净益处。
[0103]
此预期sah减少定义了再插入的分数。尝试具有正分数(即，其将减少sah)的再插入。
[0104]
图5示出了bvh优化的方法。在步骤510处，bvh形成模块102形成初始bvh。可选地，bvh形成模块还可以确定整个bvh的总sah分数(或者根据用于测量在光线遍历中搜索bvh将招致的估计计算成本的某个其他度量的总分数)。然而，确定整个bvh的总分数并不是必要的，如稍后将变得显而易见。
[0105]
在步骤515处，bvh形成模块搜索将对bvh有益的候选再插入，即，将减少其sah(或其他这种分数，即减少通过在光线遍历中搜索bvh而招致的估计计算成本的分数)。
[0106]
搜索步骤515可以被描述为包括三个子步骤。在子步骤520中，bvh形成模块102在当前bvh的树中搜索可能的候选再插入。对候选再插入的搜索可以考虑树中所有可能的输入节点，或者仅考虑子集。在后一种情况下，子集可以由稀疏度参数确定。对于每个所考虑的输入节点，搜索可以选择该节点的一个或多个可能的再插入作为用于评分的初始或初步候选。在子步骤530中，bvh形成模块102根据在被执行时将产生的sah的变化对初始候选再插入中的每个初始候选再插入进行评分。如果再插入会提高分数(会减少sah，即减少光线遍历的预期计算成本)，则在步骤540中，可以将该再插入添加到有益的候选再插入列表中。否则，如果该再插入会使分数恶化，则潜在的再插入将被忽略。应注意，当对潜在或候选再插入进行评分时，没有必要计算整个bvh的sah。相反，有可能仅计算将与候选再插入相关联的sah(或类似度量)的增量，即候选再插入在被执行时将带来的度量的变化或差异。正是此增量决定了候选再输入的潜在潜在益处(或坏处)。如果sah的增量是负的(或者更一般来说，该度量表示与光线遍历相关联的估计计算成本的减少)，则所讨论的候选再插入将是有益的，但如果sah的增量是正的(或者更一般来说，该度量表示估计计算成本的增加)，则所讨论的候选再插入将不是有益的。更大的sah减少表示候选再插入更有益，并且这可以在确定将哪些再插入作为后续步骤的候选时发挥作用。该增量还可以确定选择哪些候选项来执行，如稍后将更详细地讨论(见步骤550)。
[0107]
还应注意，图5在一定程度上是示意性的，并且在实践中，子步骤520至540可以在时间上相互缠结。即，在对候选项执行评分或将候选项添加到有益的再插入列表中的任一者之前，不必等待首先确定可能的候选再插入的整个集合，而是可以随着搜索的进行对可能的候选再插入进行评分。
[0108]
特别地，搜索520和评分530可以彼此协同地执行。例如，在实施方案中，搜索515窄化到每个输入节点仅一个候选再插入，以在步骤550处进行冲突检查。为此，随后对于搜索中考虑的每个潜在输入节点，搜索可以通过取得输入节点的第一可能的再插入并且对此第一可能的再插入进行评分(即确定其增量)来开始，随后对同一输入节点的第二可能的再插入进行评分，并且如果该再插入产生sah的更大减少，则第二可能的再插入代替第一可能的再插入作为所讨论的输入节点的当前候选项，否则第一再插入保持不变。随后，该搜索对第三次再插入进行评分，并且如果这击败了当前候选项，则该搜索将第一候选项或第二候选项替换为当前候选项，依此类推。搜索可以在所有可能的再插入中进行；或者仅是根据某个定义的搜索标准的可能再插入的子集，并且/或者直到满足某个定义的sah减少的标准。
[0109]
在搜索和评分的这种具体实现中，步骤540简单地确定每个输入节点的最佳候选项是否确实给出了sah减少(即确实减少了计算成本)，并且如果是，则将该最佳候选项包括在有益候选项的列表上。这可以在搜索每个单独输入节点的最佳再插入之后完成，而不是等到搜索全部所考虑的输入节点的再插入结束。
[0110]
在实施方案中，对给定输入节点的可能再插入的搜索可以在输入节点(可能被移动的节点)的层级处开始，随后沿树向上移动。因此，第一搜索层级将在输入节点的父代下面的节点上进行。随后，搜索向上移动一个层级，以包括输入节点的祖代下面的节点，依此类推。应注意，搜索中不包括输入节点下面的节点，因为考虑将节点移动到它自己下面是没有意义的。搜索可以在每个层级处尝试可能的移动中的所有移动或子集。该搜索可以仅跟踪sah的变化，直到受移动影响的最高节点。如果移动减少了sah，则该移动将被添加到候选
列表中。到目前为止，每个节点都将具有在搜索中找到的
‘
最佳移动’。如果移动减少的sah比当前最佳移动更多，则该移动将替换当前移动作为最佳移动。随后，搜索向上移动到层次中的下一层级，并且重复此过程，以此类推，直到一路穷尽该层次。
[0111]
在步骤550处，bvh形成模块102确定实际执行有益候选列表上的再插入中的哪个再插入，即更新当前bvh以实际包括在树中(到目前为止，候选再插入仅由bvh形成模块102视为出于评分目的的可能或假设的移动)。这可以简单地包括从列表中选择所有的再插入，或者进行随机选择，或者执行最有益的前m个再插入等。然而，在实施方案中，步骤550可以包括冲突管理步骤。
[0112]
如果列表上的两个(或更多)不同的候选再插入将试图修改树的相同部分，即如果存在两个再插入都需要修改的任何节点，则发生冲突。示例将是具有相同目标节点的两个候选再插入。因此，在实施方案中，可以包括冲突管理进程，以确保如果列表上有候选再插入会在候选列表上彼此冲突，则只有这些候选再插入中的一个候选再插入被执行。
[0113]
如果将并行执行再插入，则冲突管理可能特别重要。当执行再插入时，希望能够并行地(同时或并发地)执行多个这些再插入，每个再插入通过不同的并行进程，诸如线程或着色器调用来执行。例如，进程中的不同进程可以在不同的并行执行单元上运行，或者在桶线程执行单元中的不同时隙上运行。
[0114]
潜在的再插入可能会彼此冲突——也就是说，在执行期间尝试修改相同的节点。当并行执行时，这会引入竞争条件。例如，两个再插入可能共享同一目标，并且都将尝试相应地修改目标节点。
[0115]
可以使用锁定策略来防止执行中的冲突。据此，每个候选再插入由相应再插入进程或者能够代表相应再插入进行“投标”的其他这种代码部分来表示(例如这可以通过由多个线程形成的再插入进程的特定投标线程来完成)。一旦已经定义了候选再插入，bvh形成模块102就知道它将具有的效果(它影响的节点和它实现的sah分数的变化)。有益再插入列表上的每个候选再插入必须对受该再插入影响的节点的所有权(或者更确切地说，表示代表候选再插入的再插入投标的再插入进程)进行“投标”。如果两个不同的候选再插入会冲突(即在相同的受影响节点中的一个或多个受影响节点上投标)，具有最佳sah改进的一个再插入获胜，并且另一再插入必须被舍弃。如果两个候选再插入具有相同的sah改进，则存在平局决胜标准，例如具有最大输入节点索引的候选再插入获胜。
[0116]
再插入必须在其影响的节点上赢得所有投标，以便被视为安全的以并行执行。例如，投标可以是64位无符号整数：32个最高有效位取自浮点分数，并且32个最低有效位是输入节点的索引。节点的当前投标可以通过对提议的投标执行原子最大值来更新。这意味着具有较高分数的再插入赢得受影响节点的所有权。输入指数用于确定性地解决具有相同分数的再插入的平局决胜。在投标进程之后，检查投标，并且从当前迭代中舍弃未能赢得所有所需节点的再插入。
[0117]
在冲突管理中的投标的上下文中，可以采用不同的策略来定义节点可以如何被称为受到再插入的“影响”。例如，一种策略可以考虑再插入是否会改变连接到或来自所讨论节点的树的拓扑(因此改变其父代、兄弟或子代)。另一种策略可以替代地或另外地考虑再插入是否会改变所讨论的节点的边界。
[0118]
在实施方案中，可以采用“稀疏”策略来减少冲突再插入的数量。这意味着在搜索
阶段515处，只考虑节点的子集作为给定迭代的输入节点。其思想是，随后减少的所选再插入集合不太可能彼此冲突。稀疏度可以例如通过仅考虑以存储在存储器中的顺序的每第n个节点(例如每第三节点)来实现，或者通过在树中索引的顺序来实现(存储器中的位置不一定映射到树中的位置，但优选地，作为可能的输入被包括的节点应分散在树周围，并且节点通常以广度优先或深度优先的方式进行存储)。另一示例将是使用随机选择的节点。
[0119]
在实施方案中，子集可以由稀疏度参数来确定。稀疏度参数可以是可设置的。
[0120]
在一个特定的示例具体实现中，可以使用稀疏度参数μ来实现稀疏度。不是处理层次中的每个节点，而是处理每第μ个节点。循环偏移用于每次迭代处理不同的节点集。例如，如果μ＝3，(并且应注意，根节点通常存储在索引0处，并且从不作为输入被处理)，每次迭代将处理索引处的节点：
[0121]
■
1,4,7,10,...
[0122]
■
2,5,8,11,...
[0123]
■
3,6,9,12,...
[0124]
■
1,4,7,10,...
[0125]
更少的再插入意味着更低的冲突几率，但也意味着对层次更少的潜在改进。在实施方案中，稀疏度参数μ可以在优化期间减小(见下文)，并且最佳起始值可以是场景依赖性的。
[0126]
在一些实施方案中，稀疏度参数可以从一次迭代到下一次迭代是可变的。例如，在实施方案中，稀疏度参数可以基于当前迭代中bvh的当前总sah来设置，例如基于总bvh从一次迭代到下一次迭代收敛的良好程度来设置。
[0127]
在步骤560处，该方法执行在步骤550处从列表中选择的任何候选再插入(例如通过冲突检查)。这意味着使用所选再插入来更新临时存储装置(例如在节点缓冲器110中)中的当前bvh的结构，即以实际上将所选再插入包括在树中(与如在前一步骤中仅仅将它们视为候选项相反)。这可以包括重新计算当前树的总sah。
[0128]
步骤520至560形成一次迭代。概括地说，在实施方案中，每次迭代可以包括以下操作：
[0129]
对于每个输入节点，搜索最佳目标节点以定义再插入；
[0130]
对于每次再插入，在受影响的节点上投标；
[0131]
对于每次再插入，已经赢得对受影响的节点的检查投标；
[0132]
对于每个(成功的)再插入，通过更新bvh拓扑来执行再插入；
[0133]
重新适配层次中所有节点的包围体；以及
[0134]
计算层次的新sah
[0135]
在步骤570处，bvh形成模块102确定刚刚在步骤520至560处执行的迭代是否是最后一次迭代。如果不是，则该方法循环回到步骤520，并且从那里使用当前最新更新的bvh作为当前bvh进行重复。在利用bvh的总体总sah的实施方案中(不是必需的)，随后可以在此点处重新计算图形的总sah(或者作为变体，这可以仅在一些迭代处完成)。
[0136]
另一方面，如果在步骤570处确定已经到达最后一次迭代，则该方法进行到步骤580，其中bvh形成模块102将最终bvh写入bvh存储装置104，并且触发光线遍历单元106基于当前存储在bvh存储装置104中的bvh的最新版本来继续执行光线遍历。
[0137]
在实施方案中，在步骤570处关于是否已经达到最终迭代的确定可以简单地包括确定是否已经执行了预定次数的迭代，或者已经过了阈值时间等。即，在已经执行预定次数的迭代之后，或者已经过了预定时间，则在步骤570处，该方法将确定这是最后一次迭代，并且前进到步骤580。
[0138]
然而，作为另一示例，基于是否已经达到收敛阈值来进行确定。每次迭代都有递减的回报，因此一旦sah减少收敛到低于某个预定阈值水平，则在步骤570处，该方法便可以停止迭代并且前进到步骤580，以便继续进行光线遍历。换句话说，重复上述步骤，直到优化收敛到某个预定程度。可以通过将从当前迭代中的最新一轮执行中得到的bvh的总sah与从前一迭代中得到的总sah进行比较来确定收敛。可替代地，可以通过对来自当前迭代的全部所执行的再插入的所有单独的sah分数(单独的增量)进行求和来确定该收敛。
[0139]
在实施方案中，第二参数(分数阈值)可用于确定优化是否进展良好。在此情况下，如果迭代之间的sah减少低于此阈值(或者甚至是负的——即sah已增加)，则稀疏度参数μ将减小。重复此操作，直到μ＝0，此时优化终止。
[0140]
示例软件具体实现
[0141]
由并行处理器执行的计算工作可被布置到所谓的“工作组”和“线程”中。工作组可以包括一个或多个线程，其中一般来说，多个线程可以被串行或并行处理(例如在图形处理单元的单个核芯上)。可彼此独立地处理工作组(例如在不同的图形处理单元核芯处，或者在图形处理单元的单个核芯处连续地处理)。同一工作组内的线程可以能够在处理期间彼此同步，并且还可以能够在它们的处理期间共享对专用于处理这些线程的gpu核芯的存储器(例如专用于处理这些线程的gpu核芯的片上存储器)的访问。相比之下，不同的工作组可能并不能够在处理期间彼此同步，并且可能并不能够在它们的处理期间共享对专用于特定gpu核芯的存储器的访问。在工作组由多个线程形成的情况下，则这可以被布置为线程阵列(例如一维、二维或三维线程阵列)。工作组所包括的线程数量可能是有限的。对工作组所包括的线程数量的限制可能是硬件限制(例如对可以在可用处理硬件上并行处理多少线程的限制)。在常见示例中，工作组可包括多达1024个线程。在此示例中，如果多于1024个线程将根据同一计算程序(例如着色器程序)来处理，则多于一个工作组将与该计算程序相关联。例如，如果将根据同一计算程序处理3000个线程，则三个工作组可与该计算程序相关联(例如其中两个可被完全打包，第三个被部分打包)。应理解，本文中使用的“工作组”和“线程”术语并不旨在为限制性的，并且也可使用其他术语来描述相同概念。例如，如本文中描述的“线程”可替代地被称为“着色器调用”、“调用”或“工作项目”，而如本文中描述的“工作组”可替代地被称为“线程块”或“线程组”。
[0142]
在本上下文中，针对给定输入节点执行的再插入进程(或更简单地称为“进程”)可以包括一系列阶段，每个阶段具有单独的线程。通过使用同一id来链接再插入进程内的线程。由此，再插入进程可以被描述为包括一个或多个线程的“线程集”或“程序流”。来自不同节点的再插入进程但涉及相同步骤(即关于不同节点)的线程可以一起被分组到工作组中。线程与再插入进程之间的关系将在下文更详细地解释。
[0143]
在实施方案中，可能是再插入的主体的每个输入节点i通过给定再插入进程的几个
‘
步骤’由针对每个步骤的相应线程来处理。给定步骤的线程也可以称为着色器调用。实现bvh形成模块102的软件可以包括着色器代码块——每个着色器代码块定义了再插入进
程的
‘
步骤’——这些着色器代码块可以运行多次以在不同的输入节点上执行其步骤。对于给定步骤，每个线程(着色器调用)将具有唯一的id，该id可用于标识将针对所讨论的输入节点处理的数据部分(例如使用id来导出该线程的输入节点索引)。针对给定步骤的不同输入节点的线程中的一些或所有线程可以作为一个工作组彼此并行执行。在实施方案中，程序员通过指定待运行步骤的顺序以及每个步骤需要多少个工作组来运行n个再插入进程，其中针对步骤的线程总数(根据每个工作组的线程数以及每个步骤的工作组数)至少为n。应注意，不同的步骤可能具有不同的工作组大小。低级调度器硬件或软件根据程序员定义的工作组组成和步骤，确定线程的确切排序和并行执行。
[0144]
在实施方案中，为以下步骤提供着色器代码：
[0145]-搜索：找到给定输入节点的最佳再插入
[0146]-投标：对给定再插入设置投标
[0147]-检查：对于给定再插入，检查是否已赢得投标
[0148]-执行：执行再插入——改变层次拓扑
[0149]-重新适配：更新包围体(例如框)以反映层次的变化
[0150]-sah：对层次的sah进行评分
[0151]
给定输入节点的再插入进程包括调用搜索、投标、检查以及执行共享公共id的着色器中的每一者。即，每个输入节点调用搜索、投标、检查和执行着色器，并且通过使用公共id来链接针对同一节点调用的不同着色器。在已针对迭代执行再插入进程之后调用的重新适配和sah着色器不针对每个输入节点进行调用。相反，重新适配着色器以每个叶节点一个线程开始。重新适配着色器的所有线程都将尝试更新其父代的框——其中只允许最后一个线程更新给定节点(即如果两个线程试图更新节点，则只有第二线程将实际如此进行)。这些成功的线程随后将尝试更新下一层级的后一父代，依此类推，直到最后一个线程到达根为止。对于sah着色器，针对所有节点运行线程，而不仅仅是可能具有稀疏选择的输入节点。
[0152]
因此，将有多个线程针对它们相应的输入节点运行搜索着色器，而不是使持久线程在整个迭代中处理每个输入节点。然后，另外的线程针对那些相应输入节点的所选再插入运行投标着色器，等等。
[0153]
例如，假设有3000个输入节点需要考虑，并且希望针对这些输入节点处理(目前没有任何稀疏节点选择)再插入。如果工作组有1024个线程，则搜索、投标、检查和执行着色器都将运行3个工作组，其中每个输入节点一个线程。(在此情况下，由于线程比输入节点更多，因而一些线程可能没有任何工作要做。)
[0154]
如果采用稀疏度，则这只改变了从线程id到节点缓冲器中输入节点的索引的映射。因此，如果稀疏度为3，则id为0的线程将处理缓冲器中的节点1，线程1将处理节点4，线程2将处理节点7，以此类推。在下一次迭代中，这些映射被偏移一，以得到所处理的不同节点集：线程0处理节点2，线程1处理节点5，以此类推。
[0155]
在实施方案中，一个着色器的所有工作组必须在下一着色器的任何开始之前完成。
[0156]
i.搜索着色器将进行全面搜索，以在缓冲器中找到节点x的再插入(其中x是从线程id中导出的)。搜索着色器将通过写入到两个其他缓冲槽：targets[x]和scores[x]来存储再插入。其他着色器随后可以读取这些缓冲器。
[0157]
ii.投标着色器将对投标缓冲器进行更新。例如，如果节点x的再插入影响节点y，则用于节点x的再插入的相应线程将试图将bids[y]更新为其当前值和提议投标的最大值。因为多个线程可能试图更新bids[y]，所以此操作是原子地完成的(即依序更新到同一个槽)。
[0158]
iii.类似地，检查着色器随后遍历所有受影响的节点，以确保已针对节点x的再插入赢得投标。如果没有(即检查着色器输掉了冲突)，则检查着色器设置scores[x]＝0。
[0159]
iv.如果scores[x]》0，则执行着色器随后进行节点x的实际再插入。
[0160]
对于每个输入节点，迭代的每个步骤都有一个线程。并且可以有对应于每个节点的各种缓冲器来一起工作。输入节点是在每线程id基础上被处理的。每个相应输入节点的每个步骤由单独的线程来完成。每个搜索着色器线程对其自身的输入节点的所有候选再插入进行评分，并且具有相同线程id的对应投标线程将代表其相应节点的任何有益候选再插入设置投标，并且具有相同线程id的对应执行线程将针对相应输入节点的任何获胜投标更新bvh。
[0161]
不必有任何集中式协调器来将输入节点分配给线程。相反，每个线程可以从其自身的id中导出其本身正在处理的输入节点。在实施方案中，任何集中式工作只检查优化的进度，并且是在cpu侧处理的。示例cpu伪代码可以如下所示。
[0162]
while(！finished){
[0163]
runsearchshaderongpu(num_workgroups)
[0164]
while(retries《3){
[0165]
runbidsshaderongpu(num_workgroups)
[0166]
runcheckshaderongpu(num_workgroups)
[0167]
runexecuteshaderongpu(num_workgroups)
[0168]
retries++
[0169]
}
[0170]
runrefitshaderongpu(num_workgroups)
[0171]
runsahshaderongpu(num_workgroups)
[0172]
}
[0173]
注意：循环“while(retries《3){
…
}”是指稍后描述的冲突重试特征的示例。
[0174]
将了解，上文仅仅是本文中公开的技术可以如何在软件中实现的示例。更一般来说，软件可以被描述为包括多个进程(或代码流)，其中每个进程执行给定相应输入节点的处理的至少部分，并且进程中的至少一些进程或流的至少部分可以彼此并行运行。仍然更一般来说，软件可以以任何串行或并行形式或其组合来实现。还应注意，本文中提及的“并行”执行可以被理解为涵盖通过不同的复制并行硬件资源的执行，或者在桶形线程执行单元的不同时隙中的并发执行，或者这些技术的组合。
[0175]
非二叉再插入
[0176]
梅斯特假设的上述优化算法的约束条件是输入二叉树，并且在整个优化过程中维持该二叉树。然而，本文中认识到，至少在为了被评分的目的而进行的搜索(步骤515)中，将希望考虑可能的候选再插入，其不假设必须总是维持二叉树，因为这将提供更多的机会来减少sah。取决于分数，这类再插入随后可以被包括在考虑选择的有益再插入列表当中(步
骤550)，或者实际上被执行的那些列表中(步骤560)，例如在这些列表清除了冲突管理(步骤550)的情况下。然而，将再插入的概念扩展到非二叉树的bvh可能引起整个bvh中节点数量的变化，这不是梅斯特算法所考虑的事情，也不是梅斯特论文所考虑的事情，并且因此也不是他建议如何处理的事情。
[0177]
不假设二叉树必须总是被维持的这类再插入可以包括其中bvh的树在再插入之前和/或之后包括非二叉部分的再插入。再插入可能给旧父代留下多于一个子代，并且/或者给出新父代多于两个子代。在实施方案中，候选再插入或所执行的再插入可以将树的二叉部分改变为非二叉部分。并且/或者，候选或所执行的再插入可以将树的非二叉部分改变为二叉部分。
[0178]
在实施方案中，也可以包括二叉再插入，无论是作为评分或冲突检查的候选项，还是作为待执行的实际再插入。由此，再插入中的一些再插入可能仍然涉及目标节点和输入节点的对应新父代的单独移除和插入，如先前关于图6所描述。
[0179]
因此，本文中公开的实施方案现在允许两种类型的再插入，二叉和非二叉。允许非二叉再插入为减少sah开辟了更多的机会。搜索(515)现在可以系统地考虑二叉和非二叉可能性。
[0180]
非二叉bvh对于跟踪性能和带宽减小具有益处，因此允许非二叉输入(已在考虑了这些益处的情况下进行构建)并且产生具有这些益处的非二叉层次是有用的。因此，可以使用两种类型的再插入。二叉再插入可以如先前所讨论那样来实现，其中创建新节点以孕育目标节点和输入节点。非二叉再插入看到被添加到目标的子列表中的输入节点。在对每个候选目标的目标搜索期间，可以评估这两种再插入类型。
[0181]
图7示出了非二叉再插入的可能性。图7中的左图示出了当允许非二叉树时可能遇到的当前树(或其部分)的示例。这可能是起始bvh或当前迭代轮次处的bvh。无论哪种方式，在所示出的示例中，输入节点i是一组三个兄弟中的一个兄弟，即当前相应父代的三个子代(其在考虑再插入的情况下将成为旧父代)。中间的图示出了如先前参照图6所讨论的二叉再插入的可能性。这里唯一的区别是，当输入节点i留下两个旧兄弟时，没有“单独者”被留下，如先前参照图6所讨论，并且因此旧父代保留在原处(尽管具有收缩的边界)。因此，在此情况下，即使输入节点以及其父节点和兄弟节点的子树本质上不是二叉的，再插入也是二叉的。右图示出了替代非二叉再插入。这里，不是成为目标节点t的兄弟并且创建目标节点和再插入的输入节点的新父代(+)(如在二叉再插入情况下)，而是将输入节点i作为目标节点t的子代进行再插入，在树的目的地分支中形成当前三个(或更多)兄弟的组，即预先存在的父代或目标节点t的多于两个子代。
[0182]
然而，放宽二叉要求可能会引入额外的问题，如上文简要提及的。先前保证了输入的父节点被释放(由于单独移除)，并且此节点被“回收”作为输入节点i和目标节点t的父代。换句话说，节点缓冲器110中先前用于旧父代的槽可以重新用于新父代。然而，如果允许非二叉树，则此单独移除可能不会发生。实际上，可能需要在不移除旧节点的情况下创建新节点。如果通过移除旧节点而没有在节点缓冲器中释放槽，则将需要节点缓冲器110中的新槽来表示新节点(+)。
[0183]
例如，参见图7右图，其中输入节点i位于非二叉子列表中，并且因此旧父代仍然存在。同样，在非二叉再插入的情况下，不总是需要新节点。如所示出，如果输入节点i从给定
父代的三个子代的组中移动，从而仍然留下旧父代的两个子代的组，则旧父代必须被保留在bvh中。但移动可能涉及针对移动节点创建新父代。例如，在所示出的示例中，不是如图7的右图中那样仅仅在同一现有层级处将i作为t的另一子节点添加，而是可以针对i和t创建新父节点(+)，从而有效地执行二叉再插入，如图7的中间的图所示出。原因是，就sah而言，创建此新节点可能更好。子代计数是sah的一个因素，因此具有带有大量子代的节点可能是昂贵的。这是一个权衡的问题，在遍历的这一点上，更好的做法将是：a)明确地进行3次框测试(t的子代和i)，或者b)明确地进行2次框测试(t和i)，并且随后在t命中的情况下可能对t的子代再做2次框测试。因此，如果命中t并且进行那额外2次测试的几率小于50％，则新节点是值得的，因为预期的测试将是比如2+(2*25％)＝2.5《3。
[0184]
然而，节点缓冲器110中的槽数量是有限资源，并且因此可能不一定随意添加新节点。为了适应新节点的可能创建，希望提供一种方案来跟踪并分配由再插入创建和使用的空闲节点槽。在实施方案中，优化在节点缓冲器110中的节点槽的特定操作范围上操作，优选地在固定范围(例如索引0至n)上操作。在此操作范围中包括新节点有助于减少sah，因为新节点可以用作输入节点，或者在未来的迭代中被选为目标节点。
[0185]
根据本文中公开的实施方案，操作范围中的空闲节点槽将被分配给需要它们的再插入。这优选地是确定性地完成的；因为否则，允许在不同的索引处创建新节点可能例如改变该新节点是否在下一次迭代中被处理(因此允许在多次迭代之后不同的可能所得bvh，这将引起在渲染同一场景时的可能性能不同，这是不希望的)。
[0186]
如先前所讨论，在实施方案中，每个输入节点由包括一个或多个线程的相应再插入进程来处理，其中不同进程中的至少一些进程的至少部分可以彼此并行运行。例如，每个进程可以被配置成代表其相应的输入节点执行搜索、投标、检查和执行-再插入步骤。例如，每个进程可以包括多个线程，其中多个线程中的每个线程包括对以下着色器集中不同的相应一个着色器的调用：搜索着色器、投标着色器、检查着色器和执行-再插入着色器。每个再插入进程由相应进程id来标识。在进程包括多个线程的实施方案中，则该进程的线程可以各自通过相应进程id而被标识为同一进程的部分。
[0187]
所实现的方案看到针对每个进程id维持的列表，每个列表指示通过与该id相关联的线程进行的单独移除而创建的空闲节点槽。与特定id相关联的线程能够回收列表中针对该id指示的节点，以用于未来的二叉再插入。这些每id空闲列表确保了节点到再插入的确定性分配。二叉再插入将仅在空闲节点槽可用于再插入进程的情况下(例如在使用相同id的前一再插入进程创建了空闲节点槽的情况下)被评估，或者将由执行单独移除的该进程立即创建。虽然在此方案的情况下，空闲节点槽将并不总是可用的(即与一个id相关联的空闲节点槽将并不可用于与不同id相关联的再插入进程)，但该方案仍然足以以确定性方式产生良好的sah减少(通过允许在操作范围内创建节点)。
[0188]
详细来讲，原则上有可能在需要的时候创建和销毁存储器中的槽，但优选地不这样操作。这将需要全局分配方案，其中如果并行再插入进程需要任何空闲槽/当它们需要空闲槽时，可以在存储器中给出这些并行再插入进程任何空闲槽。这有两个问题。首先是速度。多个并行进程将想要同时被分配有空闲槽，但这些槽处于何处的全局记录必须被自动更新(即一次一个)。因此，每个进程必须等待轮到它获得下一空闲槽，这样做是浪费时间的。第二个原因是确定性。再插入进程被分配节点的顺序将是不固定的。因此，在优化的不
同轮次中，节点可以被写入缓冲器110中的不同位置处。由于先前描述的稀疏度特征，这可能导致在下一次迭代中选择不同的节点，并且将对层次进行不同的改变。
[0189]
因此，实际上，在实施方案中，在开始(步骤510)时，该方法以在存储器(节点缓冲器110)中分配的特定数量的槽(例如64000个)开始，每个槽被映射到现有节点(或者可替代地，这可以被放宽以包括一些未映射的槽来考虑)。随后，随着该方法进行完搜索和执行循环的一次或多次迭代(步骤520至560)，可能发生节点被销毁而无需创建新节点的情况。例如，输入节点是仅一个其他节点的兄弟，因此其旧兄弟变为单独者，并且因此旧父代被移除；但被移动的节点作为现有兄弟组的兄弟被添加。如果节点的槽在一次迭代中以此方式被释放，则该槽会使节点槽在同一迭代或后一迭代中由具有相同id的进程用于新节点。因此，新节点槽可被用于扩展可以考虑的可能移动的集合。因此，在下一次迭代的搜索期间，现在可能考虑将创建新节点的候选项移动/再插入，而那些可能性在前一迭代中被排除。或者空闲节点槽可以在当前迭代中被回收。例如，如果输入节点是两个子代中的一个子代，则可以知道移除该输入节点将导致此单独移除。这样，可以知道空闲节点将变为可用，并且因此在搜索期间也可以考虑二叉再插入。因为针对每个进程id跟踪空闲节点，所以在这类实施方案中，空闲节点槽只可以由具有与移除对应节点的进程相同的id的再插入进程使用，而不可以由任何其他再插入进程使用。
[0190]
在实施方案中，在给定迭代内，每个输入节点有一个再插入进程(每个进程包括线程或着色器调用，或者具有相同id的线程或着色器调用的序列，如先前所讨论)，并且许多这些再插入进程(关于不同的输入节点)可以并行运行。在后续迭代中，进程id被重新用于另一再插入进程，例如以在树中其新位置处处理相同输入节点，或者处理完全不同的节点。优选地，给定再插入进程只可以重用已由其自身或与相同id相关联的另一进程释放的节点槽。否则，该方法将不是确定性的，因为它将依赖于线程调度器。即，对于相同场景的相同帧或时间点，希望(例如为了测试目的)总是得到相同的结果。但如果槽可以在并行进程之间重用，则结果将取决于线程1或2(例如)是否碰巧首先从进程开始的任何点被调度，并且因此得到对回收槽的第一“投标”。
[0191]
注意：此问题不取决于哪个sah投标更高，因为这与现有节点的投标是分开的，以避免冲突。一旦并行进程被确认为
‘
赢得’了其所有投标，这些并行进程便试图得到空闲节点。想象存在所有空闲槽的全局列表，并且需要空闲槽的每个线程都必须移除列表中的下一个槽来声明它。不能知道是线程1还是线程2先读取并更新该列表，因此哪个线程得到哪个节点将不是确定的。
[0192]
冲突重试
[0193]
在梅斯特的算法中，如果候选再插入在冲突管理中输掉投标，则该候选再插入便被简单地舍弃。但这是潜在的浪费，因为这并不一定意味着候选再插入是无用的，仅为因为它不可以与在给定迭代内赢得再插入的另一候选再插入并行执行。
[0194]
就计算成本而言，搜索和评分是昂贵的。搜索和评分一起构成了迭代的最长阶段，因此可以减少达到给定的sah减少所需的搜索次数以及/或者使每次搜索的改进最大化的任何操作都是需要的。
[0195]
在梅斯特的方法中，在冲突解决之后，未能赢得其所需的所有节点的所有权的任何再插入都被简单地抛弃(不使用)。本文中认识到这是低效的，特别是鉴于找到这些再插
入的成本。即使使用稀疏输入，冲突仍然是常见的，并且限制了迭代的sah减少。
[0196]
冲突会阻止再插入的并发执行，但可能不会使它们无效。因此，根据本文中公开的实施方案，该方法可以包括用于冲突重试的方案，以重试这些另外被舍弃的再插入。换句话说，该方法可以在获胜者执行之后但仍在同一迭代内重试输掉的再插入。这增加了从每个搜索阶段执行的再插入的数量，并且因此提高了对层次的改进。
[0197]
为了计算效率，在实施方案中，重试再插入不被重新评分；但在其他具体实现中可以这样做，即重新计算sah中的增量或与将有可能重试的每个候选再插入相关联的其他这种度量(因为自从上次评分以来，层级已经改变)。
[0198]
无论哪种方式，优选地，应检查所讨论的再插入是否仍然有效(新的层次可能使其变得无意义)。另外，重试再插入优选地仍然应再次针对试图影响树的相同部分的任何其他重试再插入进行冲突检查。
[0199]
由于以下原因中的一个或多个原因，当在同一迭代内执行前一再插入集时，冲突的再插入可能因对层次的改变而无效：
[0200]
■
在单独移除期间，输入节点或目标节点已被释放；
[0201]
■
节点缓冲器中的输入节点或目标节点槽已在单独移除期间被释放，并且随后在二叉再插入中作为新父代被回收，因此该槽现在表示完全不同的节点；
[0202]
■
目标节点现在是输入的后代(节点不能在其自身的子树内移动)；以及/或者
[0203]
■
再插入是二叉的，并且需要从单独移除中创建空闲节点槽，但在移除输入时将不再创建空闲节点槽。
[0204]
因此，在实施方案中，在执行第一再插入集之后，可以在同一迭代内再次尝试先前输掉冲突检查的一个或多个第二再插入的集合。在实施方案中，这可以包括：
[0205]
■
根据上述标准来验证冲突的再插入，舍弃失败的再插入；
[0206]
■
所有节点上的投标被重置为零；
[0207]
■
剩余再插入可以在其所影响的节点上重新投标；
[0208]
■
检查投标，以避免冲突；以及
[0209]
■
执行剩余再插入。
[0210]
如所提及，在给定迭代内，不需要在重试之间重新计算各个sah中的增量。替代地，可以假设每次重试再插入的增量值保持近似相同。对于这些重试再插入，有时会发生此近似实际上不是这种情况，并且特定的个别重试再插入实际上可能增加sah；但尽管如此，因为再插入的分数往往不会有太大的变化，所以通过不重新评分所做的假设仍然将导致在一次迭代内多次重试的平均sah的总体减少。然而，可替代地，在其他实施方案中，可以在同一迭代内的各轮重试之间针对潜在重试候选项重新计算个别sah分数(或其他这种度量)的增量。在此情况下，仅重试仍然将给出sah减少(或另一种这样的度量的改进)或者大于阈值减少或改进的那些候选再插入。
[0211]
在实施方案中，在所有更新之后，而不是在每组更新之后，每次迭代更新一次bvh的总sah分数。然而，也有可能在第一组更新之后(即在执行第一次获胜者再插入之后)更新bvh的sah分数，并且随后在第二组更新之后再次更新bvh的分数(执行在一轮重试中获胜的再插入)。另一种可能性是不在每次迭代之后更新sah分数，或者甚至完全不计算bvh的总体总分数。换句话说，例如出于计算效率的原因，当决定是否继续进一步的迭代(在图5中的
570处)或者如先前所讨论那样评估减小稀疏度参数时，可以不考虑bvh的当前分数。因此，在诸如这样的情况下，不需要计算更新后的sah分数。例如，在极端情况下，可以决定执行固定次数的迭代，并且因此不再需要bvh的sah分数来决定是迭代还是结束优化。通过减少计算并且因此减少执行这些迭代的处理，省略每次迭代之间的重新评分可能是有利的。所有这类方法都是有效的。
[0212]
类似的选择适用于包围框的重新适配，这可以在每组更新之后或者在每次迭代之后执行。应注意，在一组更新之后(无论是在迭代之间，还是在迭代内的重试之前)更新bvh的sah分数将优选地要求包围体是最新的。如果希望更新bvh的sah分数，则将需要最新的边界。然而，如果将不考虑包围体(例如只对子代计数进行评分)的不同度量用于分数，则包围体不需要重新适配。另外，应注意，在冲突重试的情况下，拓扑可以在多个再插入集内被更新，包括重试。然后，在迭代中的所有重试之后，该方法可以扫描bvh以重新适配包围体来反映那些拓扑变化。因此，如果在重试之间重新评估再插入，则包围体将不一定是最新的。如果希望针对重试之间的再插入更新sah增量，则将需要最新的边界。
[0213]
在实施方案中，重试可以被重复几次，以从单个搜索步骤中提取对层次的更多更新。在所有的重试之后，迭代像之前那样使用包围框重新适配和sah重新评分步骤进行包裹。虽然层次在识别与执行再插入之间可能已经改变，但这些重试有净益处。如图13中所示出，重试优化可以更快地提高sah，并且可以收敛到更低的最终分数。
[0214]
在一些实施方案中，待(潜在地)重试的再插入可以在其投标被重新提交之前被重新存储。即，在已执行当前迭代中的先前获胜者之后，并且优选地在已经在更新后的bvh中重新计算了包围体之后，重新计算这些再插入的sah减少。在此情况下，只有在已重新计算其分数之后仍然有益的那些再插入才会进入重新投标阶段。然而，可替代地，在其他实施方案中，为了节省计算，不对将重试的再插入的分数进行重新存储，而是仍然有效的任何再插入可以前进到重新投标阶段。
[0215]
还应注意：虽然稀疏度没有消除冲突，仅为减少了冲突的数量，但实施方案仍然可以采用稀疏度以及冲突重试。可替代地，不需要采用稀疏度，而是在搜索中可以考虑所有可能的输入节点。
[0216]
图10示出了可被重试的冲突再插入的示例。再次假设每个输入节点的候选再插入由不同的再插入进程(各自包括一个或多个线程)来表示。
[0217]
比如进程1想要执行再插入，以将其输入节点i从p移动到t作为其新父代，进程2想要执行不同的再插入，以将另一输入节点从树中的其他位置——比如节点j——移动到t作为其新父代。即使在其中t可以具有灵活数量的子代的非二叉示例中，这优选地也应当不被并行完成，否则效果将是随机的——进程2可能使覆写进程1的结果终止，并且反之亦然。
[0218]
冲突管理解决了这一问题——进程1和进程2都可以获取t(以及其拓扑结构将受到所提议的再插入影响的其他附近的节点)的所有权。然而，传统上，输掉的进程(例如在进程1赢得投标的情况下为为2)将不得不抛弃其候选再插入，这浪费了搜索该再插入所做的工作，即使失败的再插入可能仍然有效并且有益，即使在已执行获胜的再插入之后。
[0219]
另一方面，通过允许冲突重试，两次再插入仍有可能被使用。比如进程1赢得了对t的初始投标。因为(在非二叉情况下)，这并不排除线程2也进行其添加，所以可以重试进程2的再插入。
[0220]
具有获胜的再插入的所有再插入进程执行它们的再插入，并且存在等待它们全部完成的障碍，随后具有输掉的再插入的线程可以再次重试。这比没有障碍地进行所有再插入更慢，但由于冲突，因而这不是优选的。
[0221]
上述冲突重试方案不限于允许非二叉树的非二叉再插入或bvh。图11示出了可以在纯二叉场景中重试再插入的示例。除了i和j都在二叉再插入中被移动之外，此示例类似于图10中的示例。在第一次再插入i之后，t仍然是有效目标，因此j可以在第二次再插入时与t配对。
[0222]
减小搜索范围
[0223]
原则上，节点可以被再插入到任何地方，但如果输入节点的目的地接近它在树中的旧位置，则再插入更有可能给出良好分数。因此，本文中认识到，通过限制搜索的范围(步骤515)，有可能减少搜索候选再插入的计算成本，而不太可能对所实现的sah的减少具有不当的影响(如果存在)。
[0224]
sah的大部分改进都是通过更接近bvh根节点的改变来进行的。因此，在实施方案中，该方法可以被限制为仅试图移动层次中高于特定深度的节点(即仅考虑可能的输入节点)，即更接近根的那些节点。这可以被认为是树中的“搜索下限”。或者作为此方法的变体，该方法可以在更靠近根部处采用比在叶处更低的稀疏度。更一般来说，该限制可以描述为：输入节点被限制为来自靠近根的子集，并且这可以通过例如对深度的限制，或者使用广度优先排序以得到某个数量的节点来实现(下文的2^k方法就是这样的示例)。
[0225]
越靠近根，节点便与越大的包围体相关联，并且因此与越大的表面积相关联，并且因此潜在的节省越大。这提供了减小优化范围(即搜索范围)的机会，对最终的层次质量影响有限。
[0226]
在实施方案中，对此限制可能有两个组成规则。第一组成规则是从节点的靠近根的子集中选择输入节点(例如不低于深度d，或者呈广度第一顺序的前n个节点)。这减少了整个迭代的工作量，因为待处理的再插入更少。第二规则是目标节点也可以被限制到此子集。这减小了搜索空间。第二规则需要第一规则，因为如果输入节点远离树的底部处，则将目标限制到树的顶部将是不利的。
[0227]
在实施方案中，层次被广度优先读入节点缓冲器110中，这意味着节点根据它们离根的距离被筛选。缓冲器中的前2k个节点定义优化的范围——输入节点和/或目标节点必须在该
‘
操作范围’内。减少此节点计数会导致每次迭代处理的节点更少，并且还会在寻找目标节点时减小搜索空间。层次的重新适配和重新评分也是有益的，因为在此范围之外的节点将具有固定的界限和sah分数，所以在迭代之间不需要被考虑。
[0228]
k的选择引入了时间与质量的权衡，其中减小范围节省了优化时间，但可能影响最终的层次质量。该方法相对于输入的节点数量选择k。例如，如果层次具有2
17
个节点(向上舍入到二的幂)，则前2
14
个节点可能是已处理的——k值相差3。图14a示出了这个差dk对无约束方法的影响。
[0229]
在层次质量方面，可以用很少的成本节省大量的运行时间。借助于示例，可以选择dk＝3来实现两者之间的良好平衡。
[0230]
在k≤16的此情况下，还设置了固定的上限，以防止运行时间过长。因此，对于具有n个节点并且dk＝3的输入层次：
[0231][0232]
这仅为示例。更一般来说，可以使用处于某个定义根深度内的任何数量m的节点，而不一定是2^k。使用m仍然将具有相同的效果和时间质量的权衡。
[0233]
此外，作为对搜索范围的替代或额外限制，通过改为设置“搜索上限”，即在候选输入节点之上的树中可能受到影响的最大高度，可以剔除一些不太可能的可能性，而不显式地对这些可能性进行评分。例如，如果上限为3，则仅可以考虑向曾祖代之下的其他位置的移动。
[0234]
这窄化了在寻找目标节点时的搜索空间。与无约束搜索的范围相比，发现大多数最优目标节点相对靠近输入。
[0235]
在实施方案中，搜索如下进行。在跟踪搜索期间到达最高节点，其中当前搜索空间是以此节点为根的子树(减去输入节点和其后代)。一旦已搜索完当前范围(深度优先)，最高节点便向上移动到其父代，从而扩展搜索空间。在梅斯特的论文中，此操作持续直到最高节点是根为止。参见图12。
[0236]
通过限制输入节点与最高节点之间的距离，可以较容易地限制搜索的范围。图14b示出了在选择此高度限制时运行时间与层次质量之间的权衡。借助于示例，大约4或5的最大高度以很少的成本得到了良好的运行时间节省。
[0237]
搜索上限可以独立于搜索下限使用，或者组合使用。
[0238]
示例系统具体实现
[0239]
图8示出了可以在其中实现本文中所描述的图形处理系统的计算机系统。计算机系统包括cpu 802、gpu 804、存储器806和其他设备814，诸如显示器816、扬声器818和相机819。处理块810(对应于图1的逻辑100)在gpu 804上实现。在其他示例中，处理块810可以在cpu 802上实施。计算机系统的部件可通过通信总线820彼此通信。存储库812(其可以至少部分地对应于图1中的存储器104)被实现为存储器806的部分。
[0240]
图1至图7的逻辑示出为包括许多功能块。这仅是示意性的，并不旨在限定此类实体的不同逻辑元件之间的严格划分。每个功能块可以任何合适的方式提供。应当理解，在本文中被描述为由逻辑形成的中间值不需要由逻辑在任何点处物理地生成，并且可以仅表示方便地描述由逻辑在其输入与输出之间执行的处理的逻辑值。
[0241]
本文中所描述的逻辑可以包含在集成电路上的硬件中。本文中所描述的逻辑可以被配置成执行本文中所描述的任一种方法。一般来说，上文所描述的功能、方法、技术或部件中的任一者可以在软件、固件、硬件(例如固定逻辑电路)或其任何组合中实现。本文中可以使用术语“模块”、“功能性”、“部件”、“元件”、“单元”、“块”和“逻辑”来概括地表示软件、固件、硬件或它们的任何组合。在软件实施方式的情况下，模块、功能性、部件、元件、单元、块或逻辑表示程序代码，当在处理器上被执行时，所述程序代码执行指定任务。本文中所描述的算法和方法可由执行代码的一个或多个处理器执行，所述代码促使处理器执行算法/方法。计算机可读存储介质的示例包括随机访问存储器(ram)、只读存储器(rom)、光盘、闪存存储器、硬盘存储器，以及可使用磁性、光学和其他技术来存储指令或其他数据并且可由机器访问的其他存储器设备。
[0242]
如本文中所使用的术语计算机程序代码和计算机可读指令是指用于处理器的任何种类的可执行代码，包括以机器语言、解译语言或脚本语言表达的代码。可执行代码包括
二进制代码、机器代码、字节代码、定义集成电路的代码(诸如硬件描述语言或网表)，以及用诸如c、java或opencl等编程语言代码表达的代码。可执行代码可以是例如任何种类的软件、固件、脚本、模块或库，当在虚拟机或其他软件环境中被适当地执行、处理、解译、编译、运行时，这些软件、固件、脚本、模块或库使得支持可执行代码的计算机系统的处理器执行由所述代码指定的任务。
[0243]
处理器、计算机或计算机系统可以是任何种类的装置、机器或专用电路，或其集合或一部分，它具有处理能力使得可以执行指令。处理器可以是任何种类的通用或专用处理器，诸如cpu、gpu、片上系统、状态机、媒体处理器、专用集成电路(asic)、可编程逻辑阵列、现场可编程门阵列(fpga)等。计算机或计算机系统可以包括一个或多个处理器。
[0244]
本发明还意图涵盖限定如本文中所描述的硬件的配置的软件，诸如hdl(硬件描述语言)软件，如用于设计集成电路，或者用于配置可编程芯片以实施所需功能。也就是说，可以提供一种计算机可读存储介质，其上编码有呈集成电路定义数据集形式的计算机可读程序代码，当在集成电路制造系统中被处理(即运行)时，该集成电路定义数据集将系统配置成制造被配置成执行本文中所描述的方法中的任何方法的逻辑，或者制造包括本文中所描述的任何装置的逻辑。集成电路定义数据集可以是例如集成电路描述。
[0245]
因此，可以提供一种在集成电路制造系统处制造如本文中所描述的逻辑的方法。此外，可以提供一种集成电路定义数据集，该集成电路定义数据集当在集成电路制造系统中处理时，使制造逻辑的方法被执行。
[0246]
集成电路定义数据集可以呈计算机代码的形式，例如作为网表，用于配置可编程芯片的代码，作为定义适合于在集成电路中以任何级别制造的硬件描述语言，包括作为寄存器传输级(rtl)代码，作为高级电路表示法(诸如verilog或vhdl)，以及作为低级电路表示法(诸如oasis(rtm)和gdsii)。在逻辑上定义适合于在集成电路中制造的硬件的更高级表示法(诸如rtl)可在计算机系统处进行处理，所述计算机系统被配置成用于在软件环境的上下文中产生集成电路的制造定义，所述软件环境包括电路元件的定义以及用于组合这些元件以便产生由所述表示法如此定义的集成电路的制造定义的规则。如通常软件在计算机系统处执行以便定义机器的情况一样，可能需要一个或多个中间用户步骤(例如提供命令、变量等)，以便将计算机系统配置成用于生成集成电路的制造定义，以执行定义集成电路以便生成该集成电路的制造定义的代码。
[0247]
现在将参考图9描述在集成电路制造系统处处理集成电路定义数据集以便将该系统配置为制造逻辑的示例。
[0248]
图9示出了被配置成制造如本文中的示例中的任何示例中所描述的逻辑的集成电路(ic)制造系统902的示例。具体而言，ic制造系统902包括布局处理系统904和集成电路生成系统906。ic制造系统902被配置成接收ic定义数据集(例如定义如本文中的示例中的任何示例中所描述的逻辑)，处理ic定义数据集，并且根据ic定义数据集来生成ic(例如其体现如本文中的示例中的任何示例中所描述的逻辑)。ic定义数据集的处理将ic制造系统902配置为制造包含如本文的任一示例中描述的逻辑的集成电路。
[0249]
布局处理系统904配置成接收并处理ic定义数据集以确定电路布局。根据ic定义数据集确定电路布局的方法在本领域中是已知的，并且例如可以涉及合成rtl代码以确定待产生电路的门级表示，例如就逻辑部件(例如nand、nor、and、or、mux和flip-flop部件)而
言。通过确定逻辑部件的位置信息，可以根据电路的门级表示来确定电路布局。这可以自动完成或者在用户参与下完成，以便优化电路布局。当布局处理系统904已确定电路布局，布局处理系统可以将电路布局定义输出到ic生成系统1006。电路布局定义可以是例如电路布局描述。
[0250]
如本领域中已知，ic生成系统906根据电路布局定义来生成ic。例如，ic产生系统906可实施用以产生ic的半导体设备制造工艺，所述半导体设备制造工艺可涉及光刻和化学处理步骤的多步骤序列，在此期间，在由半导体材料制成的晶片上逐渐形成电子电路。电路布局定义可呈掩码的形式，其可以在光刻工艺中用于根据电路定义来产生ic。可替代地，提供给ic产生系统906的电路布局定义可呈计算机可读代码的形式，ic产生系统906可使用所述计算机可读代码来形成用于产生ic的合适掩码。
[0251]
由ic制造系统902执行的不同工艺可全部在一个位置中例如由一方来实施。可替代地，ic制造系统902可以是分布式系统，使得一些过程可在不同位置处执行，并且可由不同方来执行。例如，以下阶段中的一些可以在不同位置和/或由不同方来执行：(i)合成表示ic定义数据集的rtl代码，以形成待生成的电路的门级表示；(ii)基于门级表示来生成电路布局；(iii)根据电路布局来形成掩模；以及(iv)使用掩模来制造集成电路。
[0252]
在其它示例中，在集成电路制造系统处对集成电路定义数据集的处理可将系统配置成制造逻辑，而无需对ic定义数据集进行处理以确定电路布局。例如，集成电路定义数据集可以定义可重新配置的处理器(诸如fpga)的配置，并且对该数据集的处理可以将ic制造系统配置成(例如通过将配置数据加载到fpga)生成具有该定义配置的可重新配置的处理器。
[0253]
在一些实施方案中，当在集成电路制造系统中被处理时，集成电路制造定义数据集可以使集成电路制造系统产生如本文中所描述的设备。例如，由集成电路制造定义数据集以上文参考图9所描述的方式对集成电路制造系统进行的配置可促使如本文中所描述的设备得以制造。
[0254]
在一些示例中，集成电路定义数据集可包括在于数据集处定义的硬件上运行的软件，或与在数据集处定义的硬件组合运行的软件。在图9中所展示的示例中，ic产生系统还可由集成电路定义数据集配置成在制造集成电路时根据在集成电路定义数据集处定义的程序代码将固件加载到所述集成电路上，或另外向集成电路提供用于与集成电路一起使用的程序代码。
[0255]
当与已知的具体实施相比时，本技术中所阐述的概念在设备、装置、模块和/或系统中(以及在本文中实施的方法中)的具体实施可引起性能改进。性能改进可包括计算性能提高、等待时间减少、吞吐量增大和/或功耗减小中的一者或多者。在制造这类设备、装置、模块和系统(例如在集成电路中)期间，可在性能提高与物理具体实现之间进行权衡，从而改进制造方法。例如，可在性能改进与布局面积之间进行权衡，从而匹配已知实施方式的性能，但使用更少的硅。例如，这可以通过以串行方式重复使用功能块或在设备、装置、模块和/或系统的元件之间共享功能块来完成。相反，本技术中所阐述的带来设备、装置、模块和系统的物理具体实现的改进(诸如硅面积减小)的概念可与性能提高进行权衡。这可以例如通过在预定义面积预算内制造模块的多个实例来完成。
[0256]
进一步说明
[0257]
申请人据此独立地公开了本文中所描述的每个单独的特征以及两个或更多个此类特征的任意组合，到达的程度使得此类特征或组合能够根据本领域的技术人员的普通常识基于本说明书整体来实行，而不管此类特征或特征的组合是否解决本文中所公开的任何问题。鉴于前文描述，本领域的技术人员将清楚，可以在本发明的范围内进行各种修改。
[0258]
根据本文公开的一个方面，提供了如发明内容章节中阐述的方法。
[0259]
在实施方案中，在候选再插入中的一个、一些或所有候选再插入中的每个候选再插入中，候选再插入将仅把其一个相应的输入节点再插入到树的另一分支。
[0260]
在实施方案中，在所述候选再插入中的一个、一些或所有候选再插入中的每个候选再插入中，所述候选再插入增加所述新父代处的子节点的数量，或者向所述数据结构添加新节点作为所述新父代。
[0261]
在实施方案中，所述输入节点被限制为处于或高于所述当前bvh的所述树中在所述根节点之下预定数量的分层层级的分层层级。
[0262]
在实施方案中，所述新父代可以被限制为处于或高于所述当前bvh的所述树中在根之下预定数量的分层层级的分层层级。
[0263]
在实施方案中，所述多个输入节点可以仅为所述树中的节点的总数的子集，所述子集不包括所述根节点以及一个或多个内部节点和/或叶节点。
[0264]
在实施方案中，在所述当前bvh的所述树中的至少一个层处，所述子集可以仅包括所述层内的每第n节点，其中n是大于二的整数。
[0265]
在实施方案中，对于在所述迭代中的任何给定迭代中的所述多个输入节点中的每个输入节点，对至少一个候选再插入的所述搜索可能或可能并不成功地找到根据所述度量将减少所述预期计算成本的至少一个候选再插入。
[0266]
在实施方案中，对于所述多个输入节点中的每个输入节点，所述搜索到的至少一个候选再插入可以由相应输入节点的多个可能的候选再插入当中的单个最佳候选再插入组成，所述最佳候选再插入根据所述度量将给出所述预期计算成本的最大减少。
[0267]
在实施方案中，对于多个输入节点中的每个相应输入节点，所述搜索所述候选再插入包括：根据所述度量对所述相应输入节点的相应多个可能的再插入中的每个可能的再插入进行评分，以确定所述再插入将实现的估计计算成本的差异；以及从所述相应输入节点的所述多个可能的再插入当中，识别给出最低差异(即最大减少)的再插入，并且如果所述相应输入节点的所述最低差异是所述预期计算成本的减少，则选择所识别的再插入作为所述相应输入节点的所述至少一个搜索到的候选再插入。
[0268]
在实施方案中，所述方法可以包括根据所述度量来确定起始分数，所述起始分数是起始bvh的分数，其中第一次迭代以作为当前bvh的当前分数的起始分数开始。每次迭代可以包括更新当前分数以考虑第一次更新。
[0269]
在实施方案中，所述方法可以包括在所述一次或多次迭代之后，搜索所述当前bvh的所述树，以确定建模的光线是否与所述图元中的任何图元相交。
[0270]
在实施方案中，所述方法可以包括输出图形数据，所述图形数据用于控制屏幕渲染表示建模环境的至少部分的场景，所述场景包括基于所述建模的光线的照明效果。
[0271]
在实施方案中，可以根据冲突检查来选择被选择用于包括在所述第一次更新中的一个或多个所选再插入，以确定所述候选再插入的任何组是否会影响所述当前bvh的所述
树的彼此相同的部分，并且如果是，则仅选择所述组中的一个候选再插入以包括在所述第一次更新中。
[0272]
在实施方案中，根据所述度量，针对所述第一次更新选择的所述组中的所述一个候选再插入可以是基于来自所述组当中的所述候选再插入根据所述度量给出所述预期计算成本的最大减少来选择的。
[0273]
在实施方案中，其中所述迭代中的至少一次迭代还可以包括在所述第一次更新之后，在同一迭代内执行第二次更新，以使用所述组中的另一候选再插入来更新所述当前bvh。
[0274]
在实施方案中，所述第二次更新可以包括在所述第一次更新之后对所述组中剩余的多个重试再插入进行重试，所述重试包括：评估所述重试再插入中的每个重试再插入是否满足一个或多个标准，以及选择所述重试再插入中满足所述一个或多个标准中的所有标准的一个重试再插入作为所述另一再插入以包括在所述第二次更新中。
[0275]
在实施方案中，一个或多个标准可以包括以下中的一者、多者或全部：
[0276]-重试再插入在第一次更新之后仍然有效，
[0277]-重试再插入仍然不与重试再插入中的另一个更有益的重试再插入冲突，以及/或者
[0278]-根据所述度量，重试再插入仍然会降低预期计算成本。
[0279]
在实施方案中，针对所述第二次更新选择的所述再插入中的所述另一再插入可以是基于来自满足所述一个或多个标准的所述重试再插入当中的所述再插入根据所述度量给出所述预期计算成本的所述最大减少来选择的。
[0280]
在实施方案中，每次迭代可以包括更新当前分数以考虑第一次更新和第二次更新。
[0281]
在实施方案中，处理器可以包括缓冲器，该缓冲器包括多个槽，树中的节点中的每个相应节点被表示为多个槽中相应一个槽中的条目。所述多个槽可以是固定数量的槽。
[0282]
不同的输入节点可以由不同的再插入进程来处理，所述再插入进程中的至少一些再插入进程至少部分地彼此并行执行。每个再插入进程可以由相应进程id来标识。
[0283]
在这类实施方案中，当再插入进程中的一个再插入进程通过从树中移除节点来释放槽时，所述方法可以包括仅允许与第一再插入进程具有相同进程id的再插入进程中的一个再插入进程重用空闲槽以创建新节点。
[0284]
也就是说，当处理所选再插入中的一个所选再插入的再插入进程中的第一再插入进程通过从树中移除相应旧父代来释放槽时，相应槽可以被重新用于存储新条目，所述新条目表示(在所述迭代中的同一或后一迭代中)由所选再插入中的另一所选再插入新创建的新节点；并且所述方法可以包括仅允许与第一再插入进程具有相同进程id的再插入进程中的一个再插入进程重用空闲槽以创建新节点。
[0285]
在实施方案中，除了由与释放相应槽的再插入进程具有相同进程id的再插入进程中的一个再插入进程创建的新创建的节点之外，所述方法可以不允许使用空闲槽来存储表示任何节点的条目。
[0286]
在实施方案中，由第一再插入进程处理的所选再插入中的所述一个所选再插入可以包括为相应旧父代留下仅一个剩余子代的再插入，使得相应旧父代从树中被移除，并且
剩余子代成为旧父代的父代的子代。
[0287]
在实施方案中，另一所选再插入可以为其相应的旧父代留下至少两个子代，并且创建新创建的节点作为相应的新父代，以便适应作为树中的另一目标节点的兄弟的输入节点。
[0288]
在实施方案中，所述处理器包括缓冲器，所述缓冲器包括多个槽，树中的节点中的每个相应节点被表示为多个槽中的相应一个槽中的条目；其中所述图形处理器被配置成运行多个进程，包括彼此并行的至少一些进程，其中每个进程被配置成处理所述输入节点中的相应一个或多个输入节点，每个进程由相应进程id来标识；其中在迭代中的至少一次迭代的更新步骤中，从树中移除旧父代，并且释放旧父代的相应槽，以用于存储表示由所选再插入中的另一所选再插入创建的新创建的节点的新条目；并且没有一个空闲槽被允许用于存储表示除了新创建的节点之外的任何节点的条目，所述新创建的节点是由与在同一迭代或前一迭代中释放所述槽的进程具有相同进程id的进程创建的。
[0289]
在实施方案中，相应再插入进程对每个相应输入节点的处理可以包括：
[0290]-对所述相应输入节点的所述候选再插入执行所述搜索，
[0291]-对所述相应输入节点的所述候选再插入执行所述评分，以确定计算成本的预期减少，以及
[0292]-如果所述相应输入节点的所述候选再插入中的任何一个候选再插入被选择作为所选再插入中的相应一个所选再插入，则通过使用相应的所选再插入执行所述当前bvh的所述更新来执行所选再插入的执行。
[0293]
根据本文中公开的另一方面，可以提供一种处理器，其包括逻辑，所述逻辑被配置成执行本文中公开的方法中的任何方法。
[0294]
在实施方案中，处理器可以在集成电路上的硬件中体现。
[0295]
根据另一方面，提供了一种使用集成电路制造系统制造本文中公开的任何实施方案的处理器的方法。
[0296]
根据另一方面，提供了一种集成电路定义数据集，当在集成电路制造系统中被处理时，该集成电路定义数据集将集成电路制造系统配置成制造本文中公开的任何实施方案的处理器。
[0297]
根据另一方面，提供了一种集成电路制造系统，其被配置成制造本文中公开的任何实施方案的处理器。
[0298]
在实施方案中，该方法可以包括对应于本文中公开的任何实施方案的操作的步骤。
[0299]
根据另一方面，可以提供一种被配置成执行该方法的图形处理系统。
[0300]
根据另一方面，提供了一种计算机可读代码，其被配置成当运行该代码时使得该方法得以执行。
[0301]
根据另一方面，提供了一种其上编码有上述计算机可读代码的计算机可读存储介质。
[0302]
根据本文公开的其它方面，可以提供一种操作处理器的对应方法以及一种被配置成操作处理器的对应计算机程序。根据其它方面，可以提供一种制造处理器的对应方法、一种布置成制造处理器的对应制造设施，以及一种包含在计算机可读存储装置上的对应电路
设计数据集。
[0303]
例如，根据一个方面，可以提供一种非暂态计算机可读存储介质，其上存储有本文中的任何实施方案的处理器的计算机可读描述，当在集成电路制造系统中被处理时，所述计算机可读描述使得集成电路制造系统：使用布局处理系统对逻辑或处理器的计算机可读描述进行处理，以便生成体现所述逻辑或处理器的集成电路的电路布局描述；以及使用集成电路生成系统根据电路布局描述来制造所述逻辑或处理器。
[0304]
根据另一方面，可以提供一种集成电路制造系统，其包括：非暂态计算机可读存储介质，其上存储有本文中公开的任何实施方案的处理器的计算机可读描述；布局处理系统，其被配置成处理计算机可读描述，以便生成体现所述逻辑或处理器的集成电路的电路布局描述；以及集成电路生成系统，其被配置成根据所述电路布局描述来制造所述逻辑或处理器。
[0305]
根据另一方面，可以提供一种使用集成电路制造系统制造本文中公开的任何实施方案的处理器的方法，所述方法包括：使用布局处理系统对所述电路的计算机可读描述进行处理，以便生成体现所述逻辑或处理器的集成电路的电路布局描述；以及使用集成电路生成系统根据电路布局描述来制造所述逻辑或处理器。
[0306]
根据另一方面，可以提供一种布局处理系统，其被配置成确定从集成电路描述中导出的电路的逻辑部件的位置信息，以便生成体现本文中公开的任何实施方案的处理器的集成电路的电路布局描述。
[0307]
一旦本文给出本公开，所公开的技术的其它变体、实施方式和/或应用对于本领域技术人员就可能变得显而易见。本公开的范围不受上述实施方案限制，而是仅受权利要求书限制。

技术特征：
1.一种由图形处理器执行的方法，所述方法包括：获得起始bvh包围体层次，所述包围体层次是包括表示建模环境中的不同3d空间区的节点的数据结构，所述数据结构包括树，在所述树中，所述节点从根节点下至多个叶节点分层排列，其中由每个叶节点建模的区涵盖至少一个图元或图元的部分；以第一次迭代开始，执行一次或多次迭代，所述第一次迭代以作为当前bvh的所述起始bvh开始，每次迭代包括：-对于所述当前bvh的所述树中的多个输入节点中的每个相应输入节点，搜索至少一个相应候选再插入，所述至少一个相应候选再插入将在所述树中将所述相应输入节点从旧父代移动到新父代，并且与所述当前bvh相比将根据用于估计预期计算成本的度量减少搜索所述树以确定建模的光线是否将与所述图元中的一个图元相交的所述预期计算成本；以及-执行至少第一次更新，以使用从所述候选再插入当中选择的一个或多个所选再插入来更新所述当前bvh；其中，在搜索候选再插入时，以下中的一者或两者：-所述新父代被限制为通过在所述当前bvh的所述树中不超过所述旧父代的预定数量的分层层级的祖先而与所述旧父代相关，以及/或者-所述输入节点被限制为处于或高于所述当前bvh的所述树中在所述根节点之下预定数量的分层层级的分层层级。2.如权利要求1所述的方法，其中所述新父代被限制为通过不超过所述旧父代之上所述预定数量的分层层级的祖先而与所述旧父代相关。3.如权利要求1或2所述的方法，其中所述输入节点被限制为处于或高于所述当前bvh的所述树中在所述根节点之下预定数量的分层层级的分层层级。4.如权利要求3所述的方法，其中所述新父代被限制为处于或高于所述当前bvh的所述树中在所述节点之下预定数量的分层层级的分层层级。5.如任一前述权利要求所述的方法，其中在所述候选再插入中的一个、一些或所有候选再插入中的每个候选再插入中，所述候选再插入增加所述新父代处的子节点的数量，或者向所述数据结构添加新节点作为所述新父代。6.如任一前述权利要求所述的方法，其中所述多个输入节点仅为所述树中的节点的总数的子集，所述子集不包括所述根节点以及一个或多个内部节点和/或叶节点。7.如权利要求6所述的方法，其中在所述当前bvh的所述树中的至少一个层处，所述子集仅包括所述层内的每第n节点，其中n是大于二的整数。8.如任一前述权利要求所述的方法，其中对于在所述迭代中的任何给定迭代中的所述多个输入节点中的每个输入节点，对至少一个候选再插入的所述搜索可能或可能并不成功地找到根据所述度量将减少所述预期计算成本的至少一个候选再插入。9.如任一前述权利要求所述的方法，其中对于所述多个输入节点中的每个输入节点，所述搜索到的至少一个候选再插入由相应输入节点的多个可能的候选再插入当中的单个最佳候选再插入组成，所述最佳候选再插入根据所述度量将给出所述预期计算成本的最大减少。10.如任一前述权利要求所述的方法，其中所述搜索所述候选再插入包括对于所述多个输入节点中的每个相应输入节点：
根据所述度量对所述相应输入节点的相应多个可能的再插入中的每个可能的再插入进行评分，以确定所述再插入将实现的估计计算成本的差异；以及从所述相应输入节点的所述多个可能的再插入当中，识别给出最低差异的再插入，并且如果所述相应输入节点的所述最低差异是所述预期计算成本的减少，则选择所识别的再插入作为所述相应输入节点的所述至少一个搜索到的候选再插入。11.如任一前述权利要求所述的方法，其中所述方法包括根据所述度量来确定起始分数，所述起始分数是所述起始bvh的分数，其中所述第一次迭代以作为所述当前bvh的当前分数的所述起始分数开始；并且其中每次迭代包括更新所述当前分数以考虑所述第一次更新。12.如任一前述权利要求所述的方法，其包括在所述一次或多次迭代之后，搜索所述当前bvh的所述树，以确定建模的光线是否与所述图元中的任何图元相交。13.如权利要求12所述的方法，其包括输出图形数据，所述图形数据用于控制屏幕渲染表示建模环境的至少部分的场景，所述场景包括基于所述建模的光线的照明效果。14.如任一前述权利要求所述的方法，其中在所述迭代中的至少一次迭代的搜索步骤中，一个或多个候选再插入包括至少一个候选再插入，所述至少一个候选再插入将为所述旧父代留下多于一个子代，并且/或者向所述新父代给出多于两个子代。15.如任一前述权利要求所述的方法，其中在所述迭代中的至少一次迭代的更新步骤中，所选再插入中的至少一个所选再插入为相应旧父代留下多于一个子代，并且/或者向相应新父代给出多于两个子代。16.如任一前述权利要求所述的方法，其中根据冲突检查来选择被选择用于包括在所述第一次更新中的一个或多个所选再插入，以确定所述候选再插入的任何组是否会影响所述当前bvh的所述树的彼此相同的部分，并且如果是，则仅选择所述组中的一个候选再插入以包括在所述第一次更新中。17.如权利要求16所述的方法，其中针对所述第一次更新选择的所述组中的所述一个候选再插入是基于来自所述组当中的所述候选再插入根据所述度量给出所述预期计算成本的最大减少来选择的。18.如权利要求16或17所述的方法，其中所述迭代中的至少一次迭代还包括在所述第一次更新之后，在同一迭代内执行第二次更新，以使用所述组中的另一候选再插入来更新所述当前bvh。19.一种在计算机可读存储装置上体现的计算机程序，所述计算机程序包括代码，所述代码被配置成当在图形处理器上运行时，执行任一前述权利要求所述的方法。20.一种图形处理器，其包括：存储器，其包括一个或多个存储器单元，以及处理装置，其包括一个或多个执行单元；其中所述存储器存储被布置成在所述处理装置上运行的代码，所述代码被配置成在运行时执行如权利要求1至18中任一项所述的方法。

技术总结
本发明涉及包围体层次的形成。一种方法，其包括在一次或多次迭代中的每次迭代中：i)对于当前包围体层次(BVH)中的多个输入节点中的每个输入节点，搜索候选再插入，该候选再插入将把相应输入节点从旧父代移动到新父代，并且将减少针对光线相交搜索所述BVH的预期计算成本；以及ii)使用从候选项当中选择的一个或多个所选再插入更新到该当前BVH。在对候选再插入的该搜索中，以下中的任一者或两者：a)该新父代被限制为通过不超过该旧父代之上预定数量的分层层级的祖先而与该旧父代相关，以及/或者b)该输入节点被限制为处于或高于根节点之下预定数量的分层层级的分层层级。之下预定数量的分层层级的分层层级。之下预定数量的分层层级的分层层级。


技术研发人员：J
受保护的技术使用者：想象技术有限公司
技术研发日：2023.03.28
技术公布日：2023/10/19