用于非相干射线跟踪的遍历设备的制作方法

1.本发明一般涉及非相干射线跟踪，更具体地，涉及一种用于在计算装置中为渲染实时三维(three-dimension，3d)图形而执行非相干射线跟踪的遍历设备。


背景技术：

2.随着虚拟图形成为当今虚拟生活的一部分，人们一直在努力使三维(three-dimension，3d)图形在设备上看起来更逼真。为了给人一种逼真的感觉，在图像中描绘光线和阴影很重要。光栅化技术是一项获取以矢量图形格式(即形状)描述的图像并将该图像转换为渲染目标(例如，一系列像素、点或线等，当这些像素、点或线一起显示时，产生通过形状表示的图像)的任务。射线跟踪是一种用于通过将光线的路径作为图像平面中的像素进行跟踪来生成图像并模拟光线与虚拟物体相遇的效果的渲染技术。这种渲染技术相比于光栅化技术，能够产生更高的视觉真实感。这些技术不适合于交互式3d应用，因为计算所需数量的光子需要很长时间，而且计算成本也更高。此外，用于交互式3d渲染的已知方法中需要各种硬优化。例如，高相干光子处理可以使用光栅化技术来优化。光子分布的近似和缓存可能需要使用球面谐波、光图和其他算法等技术来优化。此外，通过体素网格、二维(two dimension，2d)纹理、符号距离函数、屏幕空间算法族和海面渲染，实现了对场景的函数表示的射线跟踪的优化。光子数的减少和硬优化计算使开发人员可以实现可接受的帧渲染时间(即以毫秒为单位)并可以显示场景中渲染的交互性。但是，这些优化和减少方法阻碍了在现代移动硬件上实现电影质量的交互式3d图形。此外，这些方法具有局限性，例如引擎的开发极其复杂、照片仿真质量差、不准确、模糊。此外，相干性太高的已知方法阻碍了物理上正确的漫射效果的渲染。因此，电影质量的实时渲染的要求与计算装置(特别是移动设备)的可用性能之间存在着显著差距。
3.已知的实时射线跟踪方法使用以下步骤：构建包围体层次结构(bounding volume hierarchy，bvh)、光栅化、射线投射、遍历、三角形相交、使用相交结果和后处理步骤。遍历迭代bvh中的所有节点，而每个节点通常有自己的轴对齐包围盒(axis-aligned bounding box，aabb)，每个叶子包括三角形数组。每条射线可以从随机内存中读取几个aabb，并与之相交，例如每条射线相交20～40次(平均30次)。aabb与射线的每次相交需要更多浮点运算，例如，6次乘法、6次加法和12～14次比较。这需要更强的计算能力，约40～60次flop。基于标准“浮点”类型的每个aabb使用192位或24个字节。因此，最后，一条射线可能会提供约1800(60*30)次flop，并使用720个字节(24*30)的带宽。要进行非相干射线跟踪以渲染简单的实时交互式漫射和镜面全局照明、非平面和非球面物体的平滑反射以及渲染3d场景中的一些其他效果的最小有用射线数量可以估计为每秒1,200,000,000条射线。具体地，每帧至少要跟踪1,000,000条射线，每秒至少有60帧，而且射线跟踪处理需要占用整个帧渲染时间的5％左右，从而估计出每秒1,200,000,000条射线(1,000,000*60/5％)。因此，遍历的总计算能力可以估计为约每秒2万亿次flop(tflop/s)，遍历的带宽可以估计为约每秒1万亿个字节(tbyte/s)。
4.此外，场景可以包括500,000个三角形。bvh遍历和其他优化根据场景的复杂度将三角形的数量减少到2～30个，因此每条射线可能与30个三角形相交。三角形的大小为40个字节。三角形-射线相交比aabb相交复杂，但平均复杂度通常可能为60次flop。因此，一条射线可能会提供1800(60*30)次flop，并使用1200个字节(40*30)的带宽进行三角形-射线相交。使用已知方法，用于三角形相交的最小有用实时射线跟踪的总计算能力为约2tflop/s，用于三角形相交的带宽为约1.5tbyte/s。即使是最小有用版本(例如1.2千兆条射线每秒)也需要极大性能(例如至少4tflop/s)和带宽(例如至少2.5tbyte/s)。
5.广泛使用的计算装置(例如移动设备)由于功率有限，对于实时射线跟踪来说太慢，并且性能低。在现代移动平台(例如snapdragon、mali、powervr)上，只有有限数量的计算单元可用。因此，一些流行的现代射线跟踪技术方案使用基于包围体层次结构(bounding volume hierarchy，bvh)的加速结构。非相干射线跟踪通常需要随机访问。因此，内存读取是不可预测的，并且不能高效地缓存，因为(a)现有计算装置中的内存的大小只有一半或几个兆字节(而bvh可能会占用兆字节)，(b)普通3d数据可能需要当前缓存，例如临时缓冲区、纹理、着色器等，或者(c)由于对小数据块进行随机访问，不可能预取内存。此外，数百个计算单元同时访问bvh可能会导致内存冲突和巨大的功耗。非相干射线在高质量渲染中占主导地位，并为gpu射线投射带来了最繁重的工作负载。
[0006]“体素锥跟踪”是一种游戏引擎技术，其速度足够快，可以在上一代台式机和笔记本电脑的图形处理单元(graphics processing unit，gpu)上实时工作。然而，体素锥跟踪不是很准确，占用了大量内存，而且对于移动平台来说太昂贵。已知的硬件技术方案使用硬件支持的射线跟踪，这比其他方法更快。但是，此硬件技术方案需要的物理尺寸很大，功耗很大。已知技术方案将屏幕空间环境光遮挡/屏幕空间反射方法实现为像素着色器。然而，这种方法非常不准确、噪声大，并且在计算装置上占用了大量带宽。
[0007]
球面谐波(spherical harmonic，sh)照明是一系列实时渲染技术，用于以相对较小的开销产生逼真的着色和阴影。但是，对于场景中的动画几何形状，这种技术的效率低下。另一种已知方法使用光能传递技术，这是有限元法的应用，用于求解具有漫反射光线的表面的场景的渲染方程。然而，这种方法速度很快，甚至可以在移动平台上使用。此外，光能传递技术不是很准确，图像的质量也有限。已知方法使用辐照度缓存，这是一种基于射线跟踪的技术，用于计算漫射表面上的全局照明。然而，辐照度缓存是一种复杂且不稳定(有噪声)的方法。另一种已知方法使用射线行进技术，该技术使用3d场景的函数表示，其中，3d场景被呈现为数学公式。然而，对于创建游戏的动态场景，这种方法非常复杂。
[0008]
上述用于在现有计算装置上渲染3d图形的已知方法需要复杂的计算、大容量内存(可选地是硬件)，但提供的图像质量有限，或者在内存有限的现有计算装置中无法有效地应用于3d图形渲染。此外，现有计算装置包括计算单元，这些计算单元不能每秒提供足够的射线来使用非相干射线跟踪进行实时3d图形渲染。计算单元可能需要每秒提供1千兆条以上射线，如果计算单元用于每秒提供1千兆条以上射线，则计算单元需要巨大的功耗。
[0009]
因此，需要解决上述现有技术中的技术缺陷，以确保现有计算装置中的实时3d图形，而不使用大容量内存，并且在场景中渲染出良好的图像质量。


技术实现要素：

[0010]
本发明的目的是提供一种用于在计算装置中为渲染实时三维(three-dimension，3d)图形而执行射线跟踪的遍历设备，同时避免现有技术方法的一个或多个缺点。
[0011]
这个目的是通过独立权利要求的特征来实现的。其它实现形式在从属权利要求、说明书和附图中是显而易见的。
[0012]
本发明提供了一种用于在计算装置中为渲染实时3d图形而执行射线跟踪的遍历设备。
[0013]
根据第一方面，提供了一种用于在计算装置中执行非相干射线跟踪的遍历设备。不相干射线投射在三维(three-dimension，3d)场景中。所述3d场景包括在包围体层次结构(bounding volume hierarchy，bvh)中排序的物体，所述bvh包括节点，每个节点具有两个分支，每个分支包括轴对齐包围盒(axis-aligned bounding box，aabb)和指向下一个节点或(如果所述节点是叶子节点)指向三角形的数据的索引。所述遍历设备包括用于遍历所述bvh的多个遍历模块。每个遍历模块具有用于以压缩的低位形式存储所述bvh中的节点的高速缓存内存。每个遍历模块用于从所述计算装置中的图形处理单元(graphical processing unit，gpu)接收追踪距离范围以及射线的使用量化压缩为低位形式的原点和方向。每个遍历模块用于通过检查所述射线和所述存储节点中的aabb在所述追踪距离范围内的射线-aabb交点，遍历所述bvh中的所述存储节点。每个遍历模块用于：如果到达叶子节点，请求所述射线和三角形的射线-三角形交点。所述遍历设备包括用于将射线与三角形相交的多个三角形模块。每个三角形模块具有用于以压缩的低位形式存储三角形的数据的寄存器。每个三角形模块用于根据任一所述遍历模块的请求，根据所述叶子中包括的所述索引接收所述叶子节点的三角形的数据。每个三角形模块用于检查所述射线和所述叶子的三角形在所述跟踪距离范围内的射线-与三角形交点。每个三角形模块用于输出指示所述射线-三角形交点的存在和距离的交点数据。每个遍历模块用于通过本机低位整数算术计算来检查射线-aabb交点，其中，所述低位整数算术计算提供小于0.01％的漏报交点。每个三角形模块用于通过本机低位整数算术计算来检查射线-三角形交点，其中，所述低位整数算术计算提供小于0.01％的漏报交点。
[0014]
遍历设备实现多个遍历模块，这些遍历模块使得遍历设备以内存有限的计算装置(例如移动平台)可接受的低功耗，跟踪先前无法获得的非相干射线。非相干(例如多向)射线导致对bvh进行随机遍历，因此导致对计算装置中的内存进行随机访问。遍历设备能够实现计算装置的随机负载平衡。发生射线与aabb相交的遍历模块独立地处理非相干射线，并且对计算装置中的内存进行单独的内存访问。
[0015]
遍历设备是一种专用硬件，其将bvh的大小减小到足以将数据放入计算装置中的快速内存中。考虑到bvh的遍历需要大量的小随机内存请求，该遍历设备显著加速了非相干射线跟踪，并由于简化了计算装置的内存访问而降低了功耗。每个遍历模块有aabb和索引等2种数据，并针对遍历的各种过程(例如，遍历bvh和遍历存储节点)进行了优化。此外，对遍历设备进行优化，以实现一次对多个节点(例如4个节点)进行高效并行处理，每个节点仅使用很少gpu时钟。遍历设备将遍历的带宽减少4倍，因此，由于计算装置中的内存足以进行实时3d图形渲染，功率成本显著降低。遍历设备使计算装置的内存使用率提高到4～5倍，每条非相干射线的功耗可以降低40～100倍。
[0016]
每个三角形模块可以用于：如果表示射线的方向和三角形表面法线的向量的内积为正或零，确定不存在射线-三角形交点。
[0017]
可选地，所述遍历设备还包括用于接收所述gpu的跟踪请求的遍历调度器。所述跟踪请求可以包括所述射线的原点和方向、所述跟踪距离范围和遍历模块标识符(identifier，id)。所述遍历调度器用于根据所述遍历模块id分配遍历模块，并将所述射线的原点和方向以及所述跟踪距离范围发送到所述分配的遍历模块。所述遍历调度器还可以用从所述三角形模块接收所述交点数据，并将所述交点数据返回给所述gpu。
[0018]
这解决了现有技术中的技术问题。这些所述技术问题涉及现有计算装置在创建高质量3d图形时的限制，例如高内存要求、高计算成本和差的质量。
[0019]
因此，相比之下，根据本发明提供的遍历设备，硬件的特殊格式(即遍历设备)被实现成为计算装置中的图形处理单元(graphics processing unit，gpu)和中央处理单元(central processing unit，cpu)的扩展。遍历设备实现多个遍历模块，这些遍历模块使得遍历设备以内存有限的计算装置(例如移动平台)可接受的低功耗，跟踪先前无法获得的非相干射线。遍历设备是一种专用硬件，其将bvh的大小减小到足以将数据放入计算装置中的快速内存中。遍历设备可以使用计算装置的有限射线跟踪能力来渲染具有互补优化的实时3d图形，该补充优化可以在计算装置中的现有模块上实现。
[0020]
本发明的这些和其他方面在下面描述的一种或多种实现方式中是显而易见的。
附图说明
[0021]
下面参考附图，仅通过举例来描述本发明的实现方式，在附图中：
[0022]
图1为本发明一种实现方式提供的用于在计算装置中执行非相干射线跟踪的遍历设备的框图；
[0023]
图2为本发明一种实现方式提供的用于在计算装置中执行非相干射线跟踪的遍历设备的框图；
[0024]
图3为本发明一种实现方式提供的遍历模块的框图；
[0025]
图4为本发明一种实现方式提供的三角形模块的框图；
[0026]
图5为本发明一种实现方式提供的生成包围体层次结构(bounding volume hierarchy，bvh)的框图；
[0027]
图6为本发明一种实现方式提供的包围体层次结构(bounding volume hierarchy，bvh)的框图；
[0028]
图7为本发明一种实现方式提供的输出指示射线-三角形交点的存在和距离的交点数据的方法的流程图；
[0029]
图8为本发明一种实现方式提供的压缩多个三角形模块的过程的框图；
[0030]
图9为本发明一种实现方式提供的使用遍历设备执行射线跟踪的方法的流程图；
[0031]
图10为本发明一种实现方式提供的使用包围体层次结构(bounding volume hierarchy，bvh)在遍历设备上实现非相干射线跟踪的方法的流程图。
具体实施方式
[0032]
本发明实现方式提供了一种用于执行非相干射线跟踪以在计算装置上渲染实时
三维(three-dimension，3d)图形的遍历设备。所述遍历设备通过提供多个遍历模块和多个三角形模块在3d场景中执行非相干射线跟踪，来优化计算装置中的内存。
[0033]
为了使本领域技术人员更容易理解本发明的技术方案，结合附图描述本发明的以下实现方式。
[0034]
本发明的发明内容、权利要求书及附图中的“第一”、“第二”、“第三”和“第四”(如果有)等术语用于区分相似对象，而不一定用于描述特定的顺序或次序。应当理解，如此使用的术语在适当的情况下是可互换的，使得本文中描述的本发明实现方式，例如，能够以本文所示或所描述的顺序以外的顺序来实现。此外，术语“包括”和“具有”及其任何变体旨在涵盖非排他性包括。例如，包括一系列步骤或单元的过程、方法、系统、产品或设备不一定限于明确列出的步骤或单元，而是可以包括未明确列出的或此类过程、方法、产品或设备固有的其它步骤或单元。
[0035]
定义：
[0036]
渲染目标是随机存取内存(random-access memory，ram)的一部分，包括用于存储数据帧的位图。
[0037]
相干射线跟踪是射线跟踪性能的关键，它将射线束分组在相干数据包中，并根据三维场景测试这些数据包，而不是单独测试每条射线。相干射线是指具有相似性的射线。
[0038]
三维(three-dimension，3d)模型使用3d空间中的点集合表示物理主体，这些点组装成三角形或其他几何实体。每个三角形与某种像素处理函数(材质)相匹配。
[0039]
场景是世界空间中的3d模型、光源和其他类型的物体的集合，相机可以放置在其中用于描述3d渲染的场景。
[0040]
图形处理单元(graphics processing unit，gpu)是一种专用电子电路，旨在快速操作和更改内存，以加速在渲染目标中创建图像，从而将图像输出给显示设备。市场上几乎所有的gpu都针对光栅化进行了优化。
[0041]
带宽是数据传输速率、比特率或吞吐量，以比特/秒为单位。通过降低带宽要求，移动设备的性能及其可用时间增加。
[0042]
计算着色器或着色器是在gpu上执行的程序。它利用图形处理单元(graphics processing unit，gpu)中的大量并行处理器，以高性能执行通用计算任务。
[0043]
开放图形库(open graphics library，opengl)是一种用于渲染二维(two-dimension，2d)和3d矢量图形的框架。应用编程接口(application programming interface，api)通常用于与用于控制硬件加速渲染的图形处理单元(graphics processing unit，gpu)进行交互。
[0044]
vulkan是一种低开销、跨平台3d图形和计算框架。vulkan面向高性能实时3d图形应用，例如视频游戏和所有平台上的交互式媒体。
[0045]
加速结构是一个子例程，用于尽快决定特定射线、平截头体或其他图元可能会与场景中的哪些物体相交，并拒绝确定图元永远不会触及的大群物体。
[0046]
包围体层次结构(bounding volume hierarchy，bvh)是一组几何物体上的树形结构。所有几何物体都包裹在形成树中叶子节点的边界体积中。然后，这些节点被分组为小集合，并被封闭在较大的边界体积中。
[0047]
全局照明(global illumination，gi)是一种模拟光如何从表面反弹到其他表面
(即间接光)上的系统，而不是仅限于直接从光源照射到表面的光(即直接光)。模拟间接照明使虚拟世界看起来更加逼真和更加紧密，因为物体会影响彼此的外观。物理上正确的全局照明具有极大的计算成本，而且提出了很多近似方法。
[0048]
环境光遮挡(ambient occlusion，ao)是一种着色和渲染技术，用于计算场景中每个点暴露于环境光的程度。例如，管的内部通常比暴露的外表面更闭塞(因此更暗)，并且管的内部越深就越暗。环境光遮挡可以看作是为每个表面点计算的可访问性值。在开阔天空的场景中，这是通过估计每个点的可见天空范围来完成的，而在室内环境中，仅考虑一定半径内的物体，并假定环境光源自墙壁。结果是漫射、非定向的着色效果，不会投射清晰的阴影，但会使封闭和遮挡区域变暗，并可能影响渲染图像的整体色调。
[0049]
图1为本发明一种实现方式提供的在计算装置100中执行非相干射线跟踪的遍历设备102的框图。计算装置100包括图形处理单元(graphic processing unit，gpu)108，gpu 108将与射线跟踪有关的数据发送到遍历设备102。非相干射线通过gpu等在三维(three-dimension，3d)场景中投射。3d场景包括在具有节点的包围体层次结构(bounding volume hierarchy，bvh)中排序的物体。每个节点具有两个分支，每个分支包括轴对齐包围盒(axis-aligned bounding box，aabb)和指向下一个节点或(如果节点是叶子节点)指向三角形的数据的索引。遍历设备102包括多个遍历模块104a至104n和用于3d场景中的射线跟踪的多个三角形模块106a至106n。多个遍历模块104a至104n用于遍历bvh。每个遍历模块(例如104a)具有用于以压缩的低位形式存储bvh中的节点的高速缓存内存。每个遍历模块用于接收跟踪距离范围以及射线的使用量化压缩为低位形式的原点和方向。每个遍历模块用于通过检查射线和存储节点中的aabb在追踪距离范围内的射线-aabb交点，遍历bvh中的存储节点。每个遍历模块用于：如果到达叶子节点，请求射线和三角形的射线-三角形交点。
[0050]
多个三角形模块106a至106n用于将射线与三角形相交。每个三角形模块(例如106a)具有用于以压缩的低位形式存储三角形的数据的寄存器。每个三角形模块用于根据叶子中包括的索引接收叶子节点的三角形的数据。每个三角形模块用于检查射线和叶子的三角形在跟踪距离范围内的射线-三角形交点，并将指示射线-三角形交点的存在和距离的交点数据输出给gpu 108。每个遍历模块用于通过本机低位整数算术计算来检查射线-aabb交点，其中，该低位整数算术计算提供小于0.01％的漏报交点。每个三角形模块用于通过本机低位整数算术计算来检查射线-三角形交点，其中，该低位整数算术计算提供小于0.01％的漏报交点。
[0051]
遍历设备102包括多个遍历模块104a至104n，每个遍历模块具有单独的用于以压缩的低位形式存储bvh中的节点的高速缓存(快速)内存，多个遍历模块使得遍历设备102以内存有限的计算装置100(例如移动平台)可接受的低功耗，跟踪先前无法获得的非相干射线。非相干射线投射即从随机原点向随机方向的投射射线，导致对bvh进行随机遍历，因此导致对计算装置100中的内存进行随机访问。遍历设备102能够实现计算装置100的随机负载平衡。发生射线与aabb相交的多个遍历模块104a至104n独立地处理非相干射线，并且对计算装置100中的内存进行单独的内存访问。遍历设备102是一种专用硬件，其使用压缩的bvh，其尺寸减小到足以将数据放入遍历模块104a至104n中的快速内存中。考虑到bvh的遍历需要大量的小随机内存请求，遍历设备102显著加速了非相干射线跟踪，并由于简化了计算装置100的内存访问而降低了功耗。每个遍历模块有aabb和索引等2种数据，并针对遍历
bvh和检查射线-aabb交点等遍历过程进行了优化。此外，对遍历设备102进行优化，以实现一次对多个节点(例如4个节点)进行高效并行处理，每个节点仅使用很少gpu时钟。遍历设备102将遍历的带宽减少4倍，因此，由于计算装置100中的内存足以进行实时3d图形渲染，功率成本显著降低。遍历设备102使计算装置100中的内存使用率提高到4～5倍，每条非相干射线的功耗可以降低40～100倍。
[0052]
每个三角形模块可以用于：如果表示射线的方向和三角形表面法线的向量的内积为正或零，确定不存在射线-三角形交点。遍历设备102可以包括50个或更多遍历模块104a至104n，或者包括200个或更多遍历模块104a至104n。每个遍历模块可以具有4096～16384个字节的高速缓存内存。每个遍历模块可以用于以压缩的低位形式存储bvh中的128个或更多节点。可选地，遍历设备102是片上系统(system on a chip，soc)单元。遍历设备102可以用于每秒跟踪至少12亿条非相干射线。遍历设备102用于与计算装置100中的gpu 108的纹理映射单元(texture mapping unit，tmu)共享遍历模块104a至104n中的高速缓存内存。
[0053]
通常，3d游戏和其他交互式3d应用中的相干射线跟踪是通过高级光栅化方法实现的。非相干射线跟踪任务发生在光栅化之后。因此，在光栅化之后，对非相干射线进行投射，显示出不同的、随机的原点和方向。对所述非相干射线进行跟踪，以使3d图形的电影质量更好。遍历设备102是具有单独的遍历模块的专用硬件，每个遍历模块具有存储压缩的低位bvh的单独高速缓存内存，遍历设备102可以在计算装置100中每秒有效跟踪许多非相干射线，无需大容量、高速的内存存储(例如移动设备)。bvh是一组几何物体上的树形结构。所有几何物体都包裹在形成树中叶子节点的边界体积中。
[0054]
由于非相干射线在多个遍历模块104a至104n中进行独立处理，而每个遍历模块具有用于以压缩的低位形式存储bvh中的节点的高速缓存内存，因此计算装置100的内存使用率得到优化。可选地，每个遍历模块用于通过近似低位整数算术计算来检查射线-aabb交点，其中，该低位整数算术计算提供小于10％的漏报交点。
[0055]
图2为本发明一种实现方式提供的在计算装置202中执行非相干射线跟踪的遍历设备200的框图。计算装置200包括图形处理单元(graphic processing unit，gpu)208。遍历设备202包括多个遍历模块204a至204n和用于在计算装置200中执行非相干射线跟踪的多个三角形模块206a至206n。遍历设备202还可以包括用于与计算装置200中的gpu 208连接的输入/输出(input/output，i/o)总线210。遍历设备202还可以包括遍历调度器212、只写(write-only，wo)总线218、距离保持器216和只读(read-only，ro)总线220。距离保持器216存储每条射线的发送到遍历设备202的跟踪距离范围。i/o总线210将遍历设备202与计算装置200中的图形处理单元208连接起来。
[0056]
遍历设备202可以包括遍历调度器212，遍历调度器212用于接收gpu 208的跟踪请求。跟踪请求可以包括射线的原点和方向、跟踪距离范围和遍历模块标识符(identifier，id)。某个遍历模块id可以由gpu 208根据射线的原点和方向以及bvh中的节点在遍历模块之间的分布来确定。遍历调度器212用于根据遍历模块id分配一个遍历模块(例如204a)，并用于将跟踪距离范围以及射线的原点和方向发送到分配的遍历模块。遍历调度器212还可以用于从多个三角形模块206a至206n接收交点数据，并将交点数据返回给gpu 208。
[0057]
遍历设备202可以包括三角形调度器214，三角形调度器214用于根据遍历模块204a至204n中的任一个遍历模块的请求，根据叶子中包括的索引接收三角形的数据，并用
于分配可用的三角形模块(例如206a)，并将三角形数据发送到该三角形模块。三角形调度器214用于将跟踪距离范围以及射线的原点和方向发送到分配的三角形模块。三角形调度器214还用于从三角形模块206a至206n接收交点数据，并将交点数据发送到遍历调度器212。
[0058]
每个遍历模块(例如204a)可以用于接收压缩到15～24位的射线原点和压缩到每轴8～24位的射线方向。每个遍历模块中的高速缓存内存可以用于存储包围体层次结构(bounding volume hierarchy，bvh)中的节点，其中，每个aabb可以压缩到24～48位。每个三角形模块(例如206a)可以用于接收三角形的数据，包括每个三角形的三角形几何形状和三角形id。每个三角形的三角形几何形状压缩到36～90位。
[0059]
遍历设备202可以保存15～24位的射线原点，保存8～12位的射线方向，并可以提供
±
0.22-0.013度的非相干射线跟踪精度。对于通常的3d图形渲染要求，这种非相干射线跟踪精度可以提供良好的3d场景质量。由于原始射线和压缩射线之间的差异对于非相干射线跟踪不重要(非相干射线的原点和方向是随机的)，因此压缩射线(即低位射线)由于使用了低位整数，可以将射线处理的复杂度降低2～10倍。因此，与原始未压缩射线相比，压缩射线跟踪的计算成本要低得多。非相干射线(即随机的多方向射线)可能导致对bvh进行随机遍历，因此导致对计算装置200中的内存进行随机访问。多个遍历模块204a至204n对计算装置200中的内存执行随机平衡，这样可以简化用于在计算装置200上渲染交互式3d场景的可用内存的管理。
[0060]
遍历设备202可以迭代与射线相交的所有bvh节点和叶子。遍历设备202使用具有堆栈、无堆栈、排序等的算法以及射线-aabb交点和射线-三角形交点的数据来迭代bvh节点和叶子。如上所述的bvh压缩可以使bvh的内存大小减少5倍。以低位形式压缩的bvh可以减小bvh的总大小，使得所有bvh树的数据都可以放入遍历设备202的遍历模块204a至204h中的高速缓存内存中。考虑到遍历bvh需要大量的小随机内存请求，上述优化避免了使用内存管理单元(memory management unit，mmu)，显著加速了非相干射线跟踪，而且由于简化了计算装置200的内存访问而降低了功耗。例如，64位的一条内存总线可能足以在一个时钟期间读取两个aabb。此外，遍历(例如遍历bvh和遍历存储节点)的所有过程都可以针对一个数据块大小进行优化，因为每个遍历模块具有aabb和索引等2种数据此外，遍历设备202可选地实现一次对4个节点进行高效并行处理，每个节点仅使用很少gpu时钟，而不是传统方法中的数百个时钟。此外，遍历的带宽可以减少4倍或25％，并且该带宽的功率成本可以显著降低，因为遍历设备202仅与高速缓存内存一起工作，而不是与计算装置200中的内存一起工作。
[0061]
bvh的分层树形结构具有大小与叶子的大小相匹配的大多数三角形。因此，三角形可以相对于叶子指定，可以使用多个三角形模块206a至206n将每个轴的位数减少到4～8个，而不是通常技术方案中的32个。压缩三角形重用遍历压缩bvh的结果。压缩三角形是压缩bvh的延伸。射线是在节点的坐标中计算的。压缩射线的坐标可以用于与压缩三角形相交。由于使用压缩射线、压缩三角形和具有硬件优化功能的遍历设备202，重用射线坐标使三角形数据的处理速度加快到10～100倍。此外，遍历的带宽可以减少4～6倍。三角形可以不需要存储在计算装置200中的内存中。
[0062]
叶子的最大数量和三角形的数量可以是固定的。例如可允许128,000个叶子与
400,000～800,000个三角形一起使用。对于计算装置200中的大多数3d游戏来说，所述有限的最大叶子数量是足够的，因为这个固定数量的叶子可能仅适用于3d场景的背景效果，其中，非相干射线跟踪是更好的3d图形电影质量所必需的。压缩bvh和有限叶子数可以将bvh所需的快速内存限于一定量。bvh的内存可能是1～2兆字节(megabyte，mb)。由于bvh压缩，带宽可能会从每秒1太字节减少到每秒250千兆字节。使用以下公式，可以估计足够射线跟踪性能所需的计算单元数量。
[0063]nunits
＝[rays*(avnodes*cyclespernode+avleaves*(cyclesread+cyclescheck)]/gpufreq
[0064]
最佳处理器频率可以是700mhz。
[0065]
一个遍历步骤(读取并检查4个aabb)和同步需要约5个周期。
[0066]
读取三角形需要20个周期。
[0067]
每4个三角形和同步需要约5个周期。
[0068]
每条射线的平均检查节点有8个
[0069]
每条射线的平均检查三角形有8个(或3个叶子)
[0070]
为了提供1.2g ray/s，n_单元必须等于约200。
[0071]
bvh内存可以划分为子bvh树，其中，小树的数量等于计算单元的数量。每个计算单元可以与小的高速缓存内存集成。计算单元可以独占访问高速缓存内存。这种方法消除了访问内存的冲突。计算单元可以设置通过遍历调度器212到多个遍历模块204a至204n或多个三角形模块206a至206n的射线。多个遍历模块204a至204n可以具有连接到只写(write only，wo)总线的单独高速缓存内存。多个三角形模块206a至206n可以具有连接到只读(read only，ro)总线的单独寄存器。
[0072]
遍历设备202可以包括用于与计算装置200中以压缩的低位形式存储bvh中的节点的内存连接的只写总线218。遍历设备202可以包括用于与计算装置200中以压缩的低位形式存储三角形的数据的内存连接只读总线220。
[0073]
遍历设备202可以实现多个遍历模块204a至204n，多个遍历模块204a至204n使得遍历设备202以计算装置200可接受的低功耗跟踪先前无法获得的射线。计算装置200可能需要场景中的25,000,000～50,000,000个三角形和计算装置200中的50～100mb内存。射线跟踪中有两个关键作用：检查射线和aabb之间的交点，检查射线和三角形之间的交点。这两个作用是通过提供非常小的非可编程遍历模块204a至204n和多个三角形模块206a至206n来实现的，这些模块具有低功耗并且在遍历设备202中的芯片上的大小很小，该芯片可以连接到计算装置200中的gpu 208。放置在遍历设备202中的多个遍历模块204a至204n和多个三角形模块206a至206n可以对射线进行尽可能粗略的处理。多个遍历模块204a至204n和多个三角形模块206a至206n放置在芯片上，并且可以提供足够多的射线，以在计算装置200上提供电影3d场景质量，即使在一个时刻只有几十个计算单元可用于渲染的移动设备上也是如此。
[0074]
每个遍历模块可以具有自己的高速缓存内存，用于bvh的小树。缓存的每个1千字节(kilobyte，kb)可以包括bvh中的(1024/12)＝85个节点。高速缓存内存大小可能取决于支持的bvh大小。移动设备大概可以使用每个遍历模块1mb高速缓存内存。台式机大概可以使用每个遍历模块100mb高速缓存内存。使用一定数量的计算单元，例如，移动设备使用256
个或台式机使用10240个，可以在不同的遍历模块204a至204n和三角形模块206a至206n之间共享一些内存块。每个遍历模块的平均高速缓存内存可能为4096～16384个字节。多个遍历模块204a至204n有可能将小树加载到计算装置200中的内存中。小树的管理可以在驱动器侧实施。
[0075]
固定内存大小和计算单元＝数量可以实现gpu 208的soc架构的硬件模块。由于内存大小和计算单元是固定的，实时计算单元电路的内存使用率、带宽和复杂度显著降低。这样可以在连接到计算装置200中的gpu 208的芯片上开发具有可接受大小的低位遍历设备。由于射线跟踪的所有阶段都进行了简化，可以在计算装置200上实现可接受的每条射线功耗。
[0076]
图3为本发明一种实现方式提供的遍历模块300的框图。遍历模块300包括命令总线302、距离总线304、三角形总线306、高速缓存内存308、只写总线310、射线-aabb相交单元312a和312、遍历处理器314和堆栈寄存器316。命令总线302将遍历模块300与遍历设备的遍历调度器连接起来。距离总线304用于从距离保持器接收跟踪距离范围。每个遍历模块300包括用于以压缩的低位形式存储bvh中的节点的高速缓存内存308。遍历模块300用于通过只写(write only，wo)总线310从计算装置中的图形处理单元(graphical processing unit，gpu)接收射线的使用量化压缩为低位形式的原点和方向以及通过距离总线304接收跟踪距离范围。遍历模块300用于通过检查射线和存储节点中的aabb在追踪距离范围内的射线-aabb交点，遍历bvh中的存储节点。遍历模块300还用于：如果到达叶子节点，通过三角形总线306请求射线和三角形的射线-三角形交点。射线-aabb交点的结果可以移动到堆栈寄存器316。
[0077]
可选地，遍历模块300包括2个或更多用于检查射线-aabb交点的射线-aabb相交单元312a、312b和遍历处理器314。每个遍历模块300可以用于通过不同的射线并行地遍历bvh。可选地，遍历处理器314控制2个或更多射线-aabb相交单元312a、312b的操作以检查射线-aabb交点，并向这些单元提供射线-aabb的数据以处理结果。遍历处理器314可以控制遍历模块300的整个操作。可选地，遍历处理器314用于指示遍历模块300中的组件来执行以下操作：(i)从计算装置中的图形处理单元(graphical processing unit，gpu)接收跟踪距离范围以及射线的使用量化压缩为低位形式的原点和方向，(ii)通过检查射线和存储节点中的aabb在跟踪距离范围内的射线-aabb交点，遍历bvh中的存储节点，(iii)如果到达叶子节点，请求射线和三角形的射线-三角形交点。
[0078]
图4为本发明一种实现方式提供的三角形模块400的框图。每个三角形模块400包括命令总线402、距离总线404、只读(read only，ro)总线406、寄存器408、三角形相交单元410a至410d和相交处理器412。命令总线402将三角形模块400与遍历设备的三角形调度器连接起来。三角形模块400用于根据任一遍历模块的请求，根据叶子中包括的索引，以压缩的低位形式接收叶子节点的三角形的数据。寄存器408用于以压缩的低位形式存储三角形的数据。三角形模块400可以通过命令总线402接收射线的参数，并通过距离总线404接收跟踪距离范围。三角形相交单元410a至410d可以检查射线与叶子的每个三角形的射线-三角形交点。射线和叶子的三角形在跟踪距离范围内的射线-三角形交点被提供给相交处理器412，相交处理器412通过ro总线406将指示射线-三角形交点的存在和距离的交点数据输出给计算装置中的gpu。
[0079]
寄存器408可选地存储三角形的数据，包括每个三角形的三角形几何形状和三角形id。每个三角形的三角形几何形状压缩到36～90位。每个三角形模块400可以用于每次操作接收2个或更多三角形的数据，或用于每次操作接收4个或更多三角形的数据。每个三角形模块400可以包括4个或更多用于检查射线-三角形交点的射线-三角形相交单元410a至410d和相交处理器412。每个三角形模块400可以用于并行地将不同的射线与三角形相交。
[0080]
可选地，相交处理器412控制4个或更多射线-三角形相交单元410a至410d的操作以检查射线-三角形交点，并向这些单元提供射线-aabb的数据以处理结果。相交处理器412可以控制三角形模块400的整个操作。可选地，相交处理器412用于指示三角形模块400中的组件来执行以下操作：(i)根据任一遍历模块的请求，根据叶子中包括的索引接收叶子节点的三角形的数据，(ii)检查射线和叶子的三角形在跟踪距离范围内的射线-三角形交点，(iii)输出指示射线-三角形交点的存在和距离的交点数据。
[0081]
图5为本发明一种实现方式提供的生成包围体层次结构(bounding volume hierarchy，bvh)的框图。该框图包括bvh根502，其可以分支为顶层加速结构(top level of acceleration structure，tlas)504a和504b以及底层加速结构(bottom level of acceleration structure，blas)508a至508d。底层加速结构(bottom layer of acceleration structure，blas)508a至508d可以实现为bvh，并用于物体的内部几何形状。顶层加速结构(top level of acceleration structure，tlas)504a和504b用于场景中的物体。bvh根502能够为完全动画物体更新底层加速结构(bottom level of acceleration structure，blas)508a至50d。顶层加速结构(top level of acceleration structure，tlas)504a和504b可以按帧更新。顶层加速结构(top level of acceleration structure，tlas)504a和504b在结构上可以较小。例如，场景中的叶子(物体)通常多达100～1000个，而某个blas中的三角形可以多达100,000～1,000,000个，从而提高了tlas的更新速度。具有仿射动画的物体可以更快地变换物体的局部坐标506a和506b中的射线，而不是重建底层加速结构(bottom level of acceleration structure，blas)508a至508d。为了支持仿射动画，顶层加速结构(bottom level of acceleration structure，tlas)504a和504b与底层加速结构(bottom level of acceleration structure，blas)508a至508d之间存在特殊“变换”。
[0082]
图6为本发明一种实现方式提供的包围体层次结构(bounding volume hierarchy，bvh)的框图。包围体层次结构(bounding volume hierarchy，bvh)包括存在分支的树。每个分支包括一个父节点，每个父节点分支为两个节点。bvh中的每个节点可以包括分支或子节点的描述。每个分支或子节点包括轴对齐包围盒(axis aligned bounding box，aabb)的描述和指向下一个节点或叶子节点的索引。aabb限定物体在3d场景中的坐标。第一父节点包括索引602a和轴对齐包围盒(axis aligned bounding box，aabb)602b，第二父节点包括索引604a和aabb 604b。第一父节点包括第一子级，该第一子级包括具有索引606a和aabb 608a的第一子节点和具有索引606b和aabb 608b的第二子节点。第二父节点包括第二子级，该第二子级包括具有索引610a和aabb 612a的第三子节点和具有索引610b和aabb 612b的第四子节点。
[0083]
子级的bvh可以基于fp32、fp24或fp16格式的值。通过量化每个节点的子级aabb，可以优化bvh。子级的大小与父节点的大小相匹配。
[0084]
图7为本发明一种实现方式提供的输出指示射线-三角形交点的存在和距离的交点数据的方法的流程图。在步骤702中，计算单元设置射线。计算装置中的图形处理单元(graphical processing unit，gpu)可以包括多个计算单元。在步骤704中，遍历调度器选择潜在的三角形。在步骤706中，遍历模块检查射线和存储节点中的aabb的射线-aabb交点是否在跟踪距离范围内。每个遍历模块用于通过本机低位整数算术计算来检查射线-aabb交点，其中，该低位整数算术计算方法提供小于0.01％的漏报交点。在步骤708中，多个三角形模块输出射线和叶子的三角形在跟踪距离范围内检查到的射线-三角形交点以及指示射线-三角形交点的存在和距离的交点数据。
[0085]
图8为本发明一种实现方式提供的非相干射线跟踪的通信的框图。该框图包括图形处理单元(graphical processing unit，gpu)800、gpu寄存器802、与遍历设备816中的遍历总线806进行通信的多个着色器核心804a至804d。遍历设备816包括遍历调度器808、多个遍历模块810a至810n、三角形内存访问总线812和多个三角形模块814a至814n。计算装置中的图形处理单元(graphical processing unit，gpu)800提供跟踪请求，该跟踪请求可以包括射线的原点和方向、跟踪距离范围以及遍历模块标识符(identifier，id)。遍历调度器808用于通过与遍历总线806进行通信的多个着色器核心804a至804d从图形处理单元(graphical processing unit，gpu)800接收跟踪请求。遍历调度器808用于根据遍历模块id分配多个遍历模块810a至810n中的一个遍历模块，并将跟踪距离范围以及射线的原点和方向发送到分配的遍历模块。遍历调度器808还可以用于从多个三角形模块814a至814n接收交点数据，并将交点数据返回给gpu 800。多个遍历模块810a至810n用于遍历bvh，其中，每个遍历模块包括用于以压缩的低位形式存储包围体层次结构(bounding volume hierarchy，bvh)中的节点的高速缓存内存，并用于执行以下操作：(i)从图形处理单元(graphical processing unit，gpu)800接收跟踪距离范围以及射线的使用量化压缩到低位形式的原点和方向，(ii)通过检查射线和存储节点中的aabb在跟踪距离范围内的射线-aabb交点，遍历bvh中的存储节点，(iii)如果到达叶子节点，请求射线和三角形的射线-三角形交点。
[0086]
多个三角形模块814a至814n用于将射线与三角形相交。要相交的三角形的数据由遍历设备816通过三角形内访问总线812以压缩的低位形式获得。每个三角形模块包括用于以压缩的低位形式存储三角形数据的寄存器，并用于执行以下操作：(i)根据任一遍历模块的请求，根据叶子中包括的索引接收叶子节点的三角形的数据，(ii)检查射线和叶子的三角形在跟踪距离范围内的射线-三角形交点，(iii)输出指示射线-三角形交点的存在和距离的交点数据。每个遍历模块用于通过本机低位整数算术计算来检查射线-aabb交点，其中，该低位整数算术计算方法提供小于0.01％的漏报交点。每个三角形模块用于通过本机低位整数算术计算来检查射线-三角形交点，其中，该低位整数算术计算提供少于0.01％的漏报交点。
[0087]
每个遍历模块具有自己的缓存，用于bvh的小树。缓存中的每个1kb可以包括bvh中的(1024/12)＝85个节点。平均缓存大小取决于支持的bvh大小(例如手机使用1mb，台式机使用100mb)、单元数量(例如手机使用256个，台式机使用10240个)、不同遍历模块之间共享一些内存块的可能性。单元数量可以是4096～16384个字节。
[0088]
遍历设备816利用多个遍历模块810a至810n和用于执行非相干射线跟踪以实现3d
场景中细节的多个三角形模块814a至814n，并能够将物体的更精细的细节包括在3d场景中。可选地，三角形可以使用量化来压缩。可选地，每个三角形的大小与节点或叶子节点的大小相匹配。
[0089]
图9为本发明一种实现方式提供的使用遍历设备执行射线跟踪的方法的流程图。在步骤902中，在计算或片段着色器中启动射线跟踪。在步骤904中，计算或片段着色器投射射线。在步骤906中，使用任何固有着色器函数遍历基于浮点的顶层加速结构(top level of acceleration structure，tlas)和自定义节点。在步骤908中，对于每个tlas的指向底层加速结构(bottom level of acceleration structure，blas)的叶子，可以使用对应的变换方式对射线进行变换，并转换为低位格式。所有所述步骤902至908都可以在计算装置中执行，但在遍历设备之外执行。在步骤910中，将射线寄存在遍历设备的遍历调度器中。在步骤912中，遍历调度器分配对应的遍历模块并初始化遍历。遍历调度器可以匹配计算或片段着色器、射线id和射线距离，以控制分布式过程。在步骤914中，将blas中的检查节点和三角形发送到每个blas的叶子的三角形模块。在步骤916中，如果三角形模块识别出交点，并且交点比存储在遍历调度器中的距离更近，则三角形模块测试低位三角形以将交点数据推送到调度器。三角形模块可以访问gpu内存总线，并可以一次下载几个压缩三角形。在步骤918中，从遍历调度器获取交点数据，并将交点数据与遍历tlas和自定义节点的数据组合。在步骤920中，可选地，测试fp32三角形，即测试使用单精度浮点格式fp32的非压缩变量的射线-三角形交点。tlas遍历完成后，计算或片段着色器向遍历调度器请求最接近的点。在所有遍历模块和三角形模块(根据射线id)完成射线处理之后，遍历调度器将距离和点交点返回到着色器中，之后在步骤922中完成射线遍历。
[0090]
图10为本发明一种实现方式提供的使用包围体层次结构(bounding volume hierarchy，bvh)在遍历设备上实现非相干射线跟踪的方法的流程图。在步骤1002中，在遍历设备中启动当前节点。在步骤1004中，通过检查射线-轴对齐包围盒(axis-aligned bounding box，aabb)交点来检查与节点的子级的交点。在步骤1006中，根据距离对子节点进行排序。在步骤1008中，检查子节点是否为叶子节点。如果是，则在步骤1010中请求三角形相交测试。否则，进入步骤1012。在步骤1012中，检查两个子级是否都是节点。如果是，则在步骤1014中将一个子节点推送到堆栈寄存器。否则，进入步骤1016。在步骤1016中，检查是否没有子是叶子节点。如果是，则从堆栈寄存器中获取一个子节点，或者在步骤1018中退出该过程。否则，进入步骤1004。
[0091]
计算装置可以包括至少一个处理器，其中，计算装置可以使用以下任何合适的协议来实现：例如，外围组件互连(peripheral component interconnect，pci)、pci-express、加速图形端口(accelerated graphics port，agp)、hypertransport或任何其他总线或一个或多个点对点通信协议。计算装置还包括数据存储器。
[0092]
控制逻辑(软件)和数据存储在存储器中，存储器可以是随机存取存储器(random-access memory，ram)。在描述中，单个半导体平台可以指单独的基于单一半导体的集成电路或芯片。需要说明的是，术语“单个半导体平台”还可以指连接性增强的多芯片模块，这些多芯片模块模拟连接性增强的片上模块，这些片上模块模拟片上操作，并在使用传统的中央处理器(central processing unit，cpu)和总线实现方式的基础上进行实质性改进。当然，根据用户的需要，各种模块也可以位于单独的位置或者位于半导体平台的各种组合中。
[0093]
计算装置还可以包括辅助存储器。辅助存储器包括硬盘驱动器、可移动存储驱动器、表示软盘驱动器、磁带驱动器、光盘驱动器、数字多功能磁盘(digital versatile disk，dvd)驱动器、记录设备、通用串行总线(universal serial bus，usb)闪存等。可移动存储驱动器以众所周知的方式从可移动存储单元中读取和写入可移动存储单元中的至少一个。
[0094]
计算机程序或计算机控制逻辑算法可以存储在存储器和/或辅助存储器中。这类计算机程序在执行时，使系统能够执行各种功能。存储器、辅助存储器和/或任何其他存储器是计算机可读介质的可能示例。
[0095]
在一种实现方式中，前面各种附图的架构和功能可以在处理器、耦合到通信接口的图形处理器单元(graphics processor unit，gpu)、能够具有处理器和gpu两者的至少一部分能力的集成电路、芯片组(即，一组集成电路，用于作为一个单元来工作和出售，以执行相关的功能等)，和/或任何其他集成电路的环境中实现。此外，前面各种附图的架构和功能可以在通用计算机系统、电路板系统、专用于娱乐目的的游戏控制台系统、特定应用系统，和/或任何其他所需系统的环境中实现。例如，计算装置可以是移动设备、台式机、笔记本电脑、服务器、工作站、游戏机、嵌入式系统，和/或任何其他类型的逻辑等形式。
[0096]
此外，计算装置可以采取各种其他设备的形式，包括但不限于个人数字助理(personal digital assistant，pda)设备、移动电话设备、电视等。此外，尽管未示出，但计算装置可以耦合到网络(例如，电信网络、局域网(local area network，lan)、无线网络、广域网(wide area network，wan)，例如互联网、点对点网络、电缆网络等)以通过i/o接口实现通信。
[0097]
应当理解，在所描述的附图中示出的组件的布置是示例性的，并且其他布置也是可能的。还应理解，由权利要求书界定的、下文描述的并在各种框图中示出的各种系统组件(和构件)表示根据本文中公开的主题配置的一些系统中的组件。例如，这些系统组件(和构件)中的一个或多个可以全部或部分地通过所描述的至少一些组件(即在附图中示出的布置展现出的组件)来实现。
[0098]
此外，虽然这些组件中的至少一个至少部分地实现为电子硬件组件，并因此构成机器，但其它组件可以在软件中实现，当该软件包括在执行环境中时，构成机器、硬件或软件和硬件的组合。计算机程序可以存储/分布在适当的介质上，例如与其他硬件一起提供或作为其他硬件的一部分提供的光存储介质或固态介质，但也可以以其他形式分布，例如通过互联网或其他有线或无线通信系统分布。
[0099]
尽管已详细描述了本发明及其优点，但是应当理解，在不脱离所附权利要求书界定的本发明的精神和范围的情况下，可以作出各种改变、替代和更改。

技术特征：
1.一种用于在计算装置(100、200)中执行非相干射线跟踪的遍历设备(102、202、816)，其特征在于，非相干射线投射在三维(three-dimension，3d)场景中，所述3d场景包括在包围体层次结构(bounding volume hierarchy，bvh)中排序的物体，所述bvh包括节点，每个节点具有两个分支，每个分支包括轴对齐包围盒(axis-aligned bounding box，aabb)和指向下一个节点或(如果所述节点是叶子节点)指向三角形的数据的索引，所述遍历设备包括：用于遍历所述bvh的多个遍历模块(104a至104n、204a至204n、300、810a至810n)，其中，每个遍历模块具有用于以压缩的低位形式存储所述bvh中的节点的高速缓存内存，并用于：从所述计算装置中的图形处理单元(graphical processing unit，gpu)(108、208、800)接收跟踪距离范围以及射线的使用量化压缩为低位形式的原点和方向；通过检查所述射线和所述存储节点中的aabb在所述跟踪距离范围内的射线-aabb交点，遍历所述bvh中的所述存储节点；如果到达叶子节点，请求所述射线和三角形的射线-三角形交点；用于将射线与三角形相交的多个三角形模块(106a至106n、206a至206n、400、814a至814n)，其中，每个三角形模块具有用于以压缩的低位形式存储三角形的数据的寄存器(408、802)，并用于：根据任一所述遍历模块的请求，根据所述叶子包括的所述索引接收所述叶子节点的三角形的数据；检查所述射线和所述叶子的三角形在所述跟踪距离范围内的射线-三角形交点；输出指示所述射线-三角形交点的存在和距离的交点数据，其中，每个遍历模块用于通过本机低位整数算术计算来检查射线-aabb交点，其中，所述本机低位整数算术计算提供小于0.01％的漏报交点。每个三角形模块用于通过本机低位整数算术计算来检查射线-三角形交点，其中，所述低位整数算术计算提供小于0.01％的漏报交点。2.根据权利要求1所述的遍历设备，其特征在于，每个三角形模块用于：如果表示射线的方向和三角形表面法线的向量的内积为正或零，确定不存在射线-三角形交点。3.根据权利要求1或2所述的遍历设备，其特征在于，所述遍历设备还包括：遍历调度器(212、808)，用于：接收所述gpu的跟踪请求，其中，所述跟踪请求包括所述射线的原点和方向、所述跟踪距离范围以及遍历模块标识符(identifier，id)；根据所述遍历模块id分配遍历模块；将所述跟踪距离范围以及所述射线的原点和方向发送到所述分配的遍历模块，其中，所述遍历调度器还用于从所述三角形模块接收所述交点数据，并将所述交点数据返回给所述gpu。4.根据权利要求3所述的遍历设备，其特征在于，所述遍历设备还包括：三角形调度器(214)，用于：根据任一所述遍历模块的请求，根据所述叶子中包括的所述索引接收所述三角形的数据；分配可用的三角形模块，并将所述三角形的数据发送给所述三角形模块；
将所述跟踪距离范围以及所述射线的原点和方向发送到所述分配的三角形模块，其中，所述三角形调度器还用于从所述三角形模块接收所述交点数据，并将所述交点数据发送到所述遍历调度器。5.根据权利要求1至4中任一项所述的遍历设备，其特征在于，每个遍历模块用于接收压缩到15～24位的射线原点和压缩到每轴8～24位的射线方向。6.根据权利要求1至5中任一项所述的遍历设备，其特征在于，每个遍历模块中的高速缓存内存(308)用于存储所述bvh中的节点，其中，每个aabb压缩到24～48位。7.根据权利要求1至6中任一项所述的遍历设备，其特征在于，每个三角形模块用于接收包括每个所述三角形的三角形几何形状和三角形id的三角形数据，每个所述三角形的三角形几何形状压缩到36～90位。8.根据权利要求7所述的遍历设备，其特征在于，每个三角形模块用于每次操作接收2个或更多三角形的数据，或者用于每次操作接收4个或更多三角形的数据。9.根据权利要求1至8中任一项所述的遍历设备，其特征在于，所述遍历设备包括50个或更多遍历模块，或者包括200个或更多遍历模块。10.根据权利要求1至9中任一项所述的遍历设备，其特征在于，每个遍历模块具有4096～16384个字节的高速缓存内存。11.根据权利要求1至10中任一项所述的遍历设备，其特征在于，每个遍历模块用于以压缩的低位形式存储所述bvh中的128个或更多节点。12.根据权利要求1至11中任一项所述的遍历设备，其特征在于，所述遍历设备还包括用于与所述计算装置中的所述gpu连接的输入/输出(input/output，i/o)总线(210)。13.根据权利要求1至12中任一项所述的遍历设备，其特征在于，所述遍历设备还包括用于与所述计算装置中以压缩的低位形式存储所述bvh中的节点的内存连接的只写总线(218、310)。14.根据权利要求1至13中任一项所述的遍历设备，其特征在于，所述遍历设备还包括用于与所述计算装置中以压缩的低位形式存储所述三角形的数据的内存连接的只读总线(220、406)。15.根据权利要求1至14中任一项所述的遍历设备，其特征在于，每个遍历模块包括2个或更多用于检查射线-aabb交点的射线-aabb相交单元(312a和312b)和遍历处理器(314)。16.根据权利要求1至15中任一项所述的遍历设备，其特征在于，每个遍历模块用于通过不同的射线并行地遍历所述bvh。17.根据权利要求1至16中任一项所述的遍历设备，其特征在于，每个三角形模块包括4个或更多用于检查射线-三角形交点的射线-三角形相交单元(410a至410d)和相交处理器(412)。18.根据权利要求1至17中任一项所述的遍历设备，其特征在于，每个三角形模块用于并行地将不同的射线与所述三角形相交。19.根据权利要求1至18中任一项所述的遍历设备，其特征在于，所述遍历设备为片上系统(system on a chip，soc)单元。20.根据权利要求1至19中任一项所述的遍历设备，其特征在于，所述遍历设备用于每秒跟踪至少12亿条非相干射线。
21.根据权利要求1至20中任一项所述的遍历设备，其特征在于，所述遍历设备用于与所述计算装置中的所述gpu的纹理映射单元(texture mapping unit，tmu)共享所述遍历模块中的所述高速缓存内存。

技术总结
本发明提供了一种用于在计算装置(100、200)中执行实时非相干射线跟踪的遍历设备(102、202、816)。非相干射线投射在三维(three-dimension，3D)场景中。所述3D场景包括在包围体层次结构(bounding volume hierarchy，BVH)中排序的物体。所述遍历设备包括用于遍历所述BVH的多个遍历模块(104A至104N、204A至204N、300、810A至810N)。每个遍历模块具有用于以压缩的低位形式存储所述BVH中的节点的高速缓存内存。所述遍历设备包括用于将射线与三角形相交的多个三角形模块(106A至106N、206A至206N、400、814A至814N)。每个三角形模块具有用于以压缩的低位形式存储三角形的数据的寄存器。每个遍历模块用于检查射线-AABB交点，每个三角形模块用于通过本机低位整数算术计算来检查射线-三角形交点，其中，所述本机低位整数算术计算提供小于0.01％的漏报交点。计算提供小于0.01％的漏报交点。计算提供小于0.01％的漏报交点。


技术研发人员：尼基塔
受保护的技术使用者：华为技术有限公司
技术研发日：2021.02.08
技术公布日：2023/10/6