一种用于光线追踪硬件加速器的栈缓存部件及其应用方法

1.本发明涉及计算机图像渲染的硬件设计领域，具体涉及一种用于光线追踪硬件加速器的栈缓存部件及其应用方法。


背景技术：

2.随着电影、动画、游戏等应用对图像真实感绘制需求的不断增加，人们对计算机渲染图像的真实感要求越来越高，期望渲染的图像能不断接近真实世界环境拍摄的照片。渲染是指通过某种形式将3d场景的描述转换为二维图像的过程。当前渲染方式主要包括光栅化和光线追踪两种。光栅化采用局部光照原理，根据光源照射到物体上直接可见的光照效果，将场景中的几何图元映射到图像的像素点上。光线追踪采用全局光照模型，通过物理原理对光线和物体之间的交互行为进行建模，不仅考虑直接光照效果，也考虑物体间相互光照效果，效果比传统的光栅化渲染效果更加立体，色彩更加柔和。
3.为加速光线追踪中的遍历过程，通常使用加速数据结构(acceleration struceture,as)，主要是将场景中的图元划分到不同的分层空间结构中，在这种结构下，可以快速剔除那些不相关的空间，进而识别出与光线最接近的图元。目前应用最广泛的是一种树形结构，主要包括细分为多个较小空间区域的kd-tree或分解为更小对象几何的包围盒层次结构(bounding volume hierarchy,bvh)。
4.当前主流光线追踪硬件加速器流水线如图1所示，主要包括光线生成渲染器、命中渲染器和未命中渲染器，光线生成渲染器用于遍历加速数据结构以实现光线遍历，并进行三角形相交测试，若三角形相交测试结果为命中，则选择命中渲染器执行渲染，否则选择未命中渲染器执行渲染，最终得到渲染图像。以包围盒层次结构bvh为例，如图2所示，图中分别包含四个三角形，其分别所述的区域a～d的分布关系如右侧树形结构所示。光线迭代地遍历该数据结构，当光线(图2左侧箭头所示)与某个节点的子节点进行遍历测试时，需要根据与子节点是否相交以及光线与子节点的相交距离进行对应的栈操作。如果光线与两个子节点都不相交，将栈中的节点数据弹栈；如果光线与两个子节点都相交，那么将相交距离更近的送到三角形相交测试阶段，将距离更远节点的存入栈中；如果光线与只与一个子节点相交，那么将该节点送到三角形相交测试阶段，无需进行栈操作。
5.在现代cpu或gpu中，在这些硬件中由于有限的寄存器空间，以及栈的编程复杂度高等，所以光线追踪的处理通常是单个线程进行单条光线的处理，这样的处理方式往往导致系统的并行度不高。除此之外，cpu或gpu中通常使用的simd架构也会因为多个线程处理光线的复杂度不同，产生长尾效应，导致整体效率低。因此，在许多光线追踪硬件加速器中，采用栈堆是解决光线追踪并行性的有效方法。但与此同时带来的负面影响是栈的深度过深，在实际应用中，栈的深度较大，这样会导致栈占用的硬件资源过多，无论是嵌入式设备或通用gpu，这样巨大的内存开销是无法接受的。


技术实现要素：

6.本发明要解决的技术问题：针对现有技术的上述问题，提供一种用于光线追踪硬件加速器的栈缓存部件及其应用方法，本发明为光线追踪硬件加速器提供栈缓存并保证光线并行性，具有存储资源开销低、设计逻辑简单以及对光线追踪硬件性能影响很小的优点。
7.为了解决上述技术问题，本发明采用的技术方案为：
8.一种用于光线追踪硬件加速器的栈缓存部件,包括：
9.栈堆，用于保存光线遍历过程中的节点信息；
10.多路选择器，用于匹配查找表中的数据以决定是否需要对栈缓存进行弹栈或压栈操作；
11.查找表，用于保存栈号及其对应栈缓存的序号；
12.栈缓存，由若干栈及其序号组成；
13.所述栈堆、多路选择器、查找表以及栈缓存依次相连呈流水线结构。
14.可选地，所述栈堆中共包含n个用于保存光线遍历过程中的节点信息的栈1～栈n。
15.可选地，所述栈堆中每一个栈均带有一个标记位，所述标记位取值为0或1，用于表示栈堆中对应的栈是否已经存储在栈缓存中。
16.此外，本发明还提供一种光线追踪硬件加速器，包括光线生成渲染器、光线遍历单元、三角形相交测试单元、命中渲染器、未命中渲染器以及前述用于光线追踪硬件加速器的栈缓存部件，所述光线生成渲染器、光线遍历单元、三角形相交测试单元依次相连，所述三角形相交测试单元分别与命中渲染器、未命中渲染器相连，且所述栈缓存部件分别与、光线遍历单元、三角形相交测试单元、命中渲染器以及未命中渲染器相连。
17.此外，本发明还提供一种前述用于光线追踪硬件加速器的栈缓存部件的应用方法,包括响应弹栈请求对栈堆中某一个栈进行弹栈操作，并同时响应弹栈请求对栈缓存执行下述步骤：
18.s101，判断需要进行弹栈操作的栈是否已经存储在栈缓存中，若需要进行弹栈操作的栈尚未存储在栈缓存中，则结束并退出；否则跳转步骤s102；
19.s102，根据进行弹栈操作的栈号，在查找表中查找对应栈缓存的序号；
20.s103，根据找到的栈缓存的序号，在栈缓存找到该需要对应的缓存栈，并将找到的缓存栈中的数据弹栈。
21.可选地，步骤s101中判断需要进行弹栈操作的栈是否已经存储在栈缓存中是指判断需要进行弹栈操作的栈的标记位的取值，若标记位取值为0，则判定需要进行弹栈操作的栈尚未存储在栈缓存中，否则判定需要进行弹栈操作的栈已经存储在栈缓存中。
22.可选地，所述弹栈请求来自光线追踪硬件加速器的光线遍历单元和三角形相交测试单元，且所述光线遍历单元当光线遍历时若判定两个子节点与光线都不相交则向栈堆发送弹栈请求，所述三角形相交测试单元在三角形相交测试结束后向栈堆发送弹栈请求。
23.可选地，包括响应压栈请求时执行下述步骤：
24.s201，判断压栈请求的栈在栈堆中是否已满，若压栈请求的栈在栈堆中未满，则直接将压栈请求对应的数据存入对应的堆栈中，结束并退出；否则，跳转步骤s202；
25.s202，判断压栈请求的栈是否已经存储在栈缓存中，若尚未存储在栈缓存中，则跳转步骤s203；否则跳转步骤s204；
26.s203，通过多路选择器将压栈请求送入查找表中查找有无空闲的栈缓存，若有空闲的栈缓存，则将压栈请求对应的数据存入对应的堆栈中存到栈缓存中序号较小的栈缓存的堆栈中，并在查找表中记录此次在栈缓存中存放的序号和对应的栈号；如果没有空的栈缓存，那么将当前光线的处理暂时阻塞，直到查找表中出现空的栈缓存才将压栈请求对应的数据存入，流水线恢复，并将栈堆中对应栈的标记位置为1；
27.s204，通过多路选择器将压栈请求送入查找表中查找对应的栈号和序号，而后根据序号到栈缓存中将对应的缓存栈的数据进行压栈操作。
28.可选地，步骤s202中判断压栈请求的栈是否已经存储在栈缓存中是指判断压栈请求的栈的标记位的取值，若标记位取值为0，则判定尚未存储在栈缓存中，否则判定已经存储在栈缓存中。
29.可选地，所述压栈请求来自光线追踪硬件加速器的光线遍历单元，所述光线遍历单元在光线遍历结束后判定光线与两个子节点均相交时发送压栈请求以用于将两个子节点中距离较远的子节点信息压入栈堆中。
30.和现有技术相比，本发明主要具有下述优点：
31.1、降低存储资源开销，相比于使用全栈的设计方式，能够有效地将栈的存储资源缩减将近一半。
32.2、设计逻辑简单。栈缓存中的栈与栈堆中的栈设计方式和原理相同，修改的逻辑设计较为简单。
33.3、对光线追踪硬件性能影响很小。该发明通过流水化的设计实现，通过对栈堆的满或非满检测，以及查找表中的数据进行匹配，进而完成栈的相关操作。只有在栈缓存中的栈都被占用时且仍需要进行其他栈的缓存时，才会阻塞当前流水线，这种情况在光线追踪中非常少见，所以对性能的影响很小。
附图说明
34.图1为现有技术中光线追踪硬件加速器的结构示意图。
35.图2为现有技术中光线遍历和三角形相交测试的原理示意图。
36.图3为本发明实施例中栈缓存部件的结构示意图。
具体实施方式
37.如图3所示，本实施例用于光线追踪硬件加速器的栈缓存部件,包括：
38.栈堆，用于保存光线遍历过程中的节点信息；
39.多路选择器，用于匹配查找表中的数据以决定是否需要对栈缓存进行弹栈或压栈操作；
40.查找表，用于保存栈号及其对应栈缓存的序号；
41.栈缓存，由若干栈及其序号组成；
42.所述栈堆、多路选择器、查找表以及栈缓存依次相连呈流水线结构。
43.参见图3，本实施例的栈堆中共包含n个用于保存光线遍历过程中的节点信息的栈1～栈n。基本的光线追踪硬件通常仅设置栈堆用于保存光线遍历过程中的节点信息，本实施例用于光线追踪硬件加速器的栈缓存部件增加一组栈缓存可以有效地对数据进行暂存，
采用流水线的设计可以保持原有的性能。
44.参见图3，本实施例的栈堆中每一个栈均带有一个标记位，所述标记位取值为0或1，用于表示栈堆中对应的栈是否已经存储在栈缓存中。本实施例中，栈堆中的栈1表示当前栈已满，且由于其标记位为1，表明着有数据存放在栈缓存中。栈2表示栈非满，且标记位为0，表明没有数据存放在栈缓存中。栈缓存的设计方式与单个堆栈的设计相同，均采用为全栈深度一半的栈。
45.此外，本实施例还提供一种光线追踪硬件加速器，包括光线生成渲染器、光线遍历单元、三角形相交测试单元、命中渲染器、未命中渲染器以及前述用于光线追踪硬件加速器的栈缓存部件，所述光线生成渲染器、光线遍历单元、三角形相交测试单元依次相连，所述三角形相交测试单元分别与命中渲染器、未命中渲染器相连且所述栈缓存部件分别与、光线遍历单元、三角形相交测试单元、命中渲染器以及未命中渲染器相连。
46.关于栈缓存的操作主要包括两个部分，分别是压栈操作和弹栈操作，现分别就以上两个操作进行介绍。
47.此外，本实施例还提供一种前述用于光线追踪硬件加速器的栈缓存部件的应用方法,包括响应弹栈请求对栈堆中某一个栈进行弹栈操作，并同时响应弹栈请求对栈缓存执行下述步骤：
48.s101，判断需要进行弹栈操作的栈是否已经存储在栈缓存中，若需要进行弹栈操作的栈尚未存储在栈缓存中，则结束并退出；否则跳转步骤s102；
49.s102，根据进行弹栈操作的栈号，在查找表中查找对应栈缓存的序号；
50.s103，根据找到的栈缓存的序号，在栈缓存找到该需要对应的缓存栈，并将找到的缓存栈中的数据弹栈。
51.本实施例中，步骤s101中判断需要进行弹栈操作的栈是否已经存储在栈缓存中是指判断需要进行弹栈操作的栈的标记位的取值，若标记位取值为0，则判定需要进行弹栈操作的栈尚未存储在栈缓存中，否则判定需要进行弹栈操作的栈已经存储在栈缓存中。倘若需要进行弹栈操作，会从栈堆中检测的对应栈进行有无在栈缓存中存数，即图3左侧栈堆中0或1的标记位，如果是1，表明对应栈需要在栈缓存中进行弹栈操作，通过查找表中存储的栈号和序号进行对应操作，最后在栈缓存中查找序号进行对应操作，并将数据弹栈；0则反之，仅需要对栈堆中的对应栈进行弹栈操作。有且仅有弹栈操作，且对应栈在栈缓存中为空时，才会将栈堆中的标记位更改为0。
52.本实施例中，弹栈请求来自光线追踪硬件加速器的光线遍历单元和三角形相交测试单元，且所述光线遍历单元当光线遍历时若判定两个子节点与光线都不相交则向栈堆发送弹栈请求，所述三角形相交测试单元在三角形相交测试结束后向栈堆发送弹栈请求。在一个周期内通常仅能处理一个弹栈请求。当弹栈请求到达时，同样需要根据不同的情况进行判断：1)光线对应的堆栈非满或光线对应的堆栈为满，标记位为0。从堆栈中寻找对应的堆栈进行弹栈处理。2)光线对应的堆栈为满且标记位为1，说明当前堆栈在栈缓存中有缓存的数据，需要通过多路选择器将弹栈请求和对应的栈号发送到查找表中，通过查找表匹配栈号和序号，而后根据匹配的序号到栈缓存中寻找对应的栈缓存进行弹栈操作。
53.本实施例中还包括响应压栈请求时执行下述步骤：
54.s201，判断压栈请求的栈在栈堆中是否已满，若压栈请求的栈在栈堆中未满，则直
接将压栈请求对应的数据存入对应的堆栈中，结束并退出；否则，跳转步骤s202；
55.s202，判断压栈请求的栈是否已经存储在栈缓存中，若尚未存储在栈缓存中，则跳转步骤s203；否则跳转步骤s204；
56.s203，通过多路选择器将压栈请求送入查找表中查找有无空闲的栈缓存，若有空闲的栈缓存，则将压栈请求对应的数据存入对应的堆栈中存到栈缓存中序号较小的栈缓存的堆栈中，并在查找表中记录此次在栈缓存中存放的序号和对应的栈号；如果没有空的栈缓存，那么将当前光线的处理暂时阻塞，直到查找表中出现空的栈缓存才将压栈请求对应的数据存入，流水线恢复，并将栈堆中对应栈的标记位置为1；
57.s204，通过多路选择器将压栈请求送入查找表中查找对应的栈号和序号，而后根据序号到栈缓存中将对应的缓存栈的数据进行压栈操作。
58.本实施例中，步骤s202中判断压栈请求的栈是否已经存储在栈缓存中是指判断压栈请求的栈的标记位的取值，若标记位取值为0，则判定尚未存储在栈缓存中，否则判定已经存储在栈缓存中。
59.本实施例中，压栈请求来自光线追踪硬件加速器的光线遍历单元，所述光线遍历单元在光线遍历结束后判定光线与两个子节点均相交时发送压栈请求以用于将两个子节点中距离较远的子节点信息压入栈堆中。压栈中涉及到以下几种情况，需要分别进行判断：1)需要压栈的栈在栈堆中未满，将对应的数据存入对应的堆栈中即可；2)需要压栈的栈在栈堆中已满，但标记位为0，说明上次压栈将该栈压满，此次需要通过多路选择器将压栈的请求送入查找表中查找有无空闲的栈缓存。如果有空的栈缓存，那么将数据存到栈缓存中序号较小的栈缓存的堆栈中，并在查找表中记录此次在栈缓存中存放的序号和对应的栈号；如果没有空的栈缓存，那么将当前光线的处理暂时阻塞，直到查找表中出现空的栈缓存才会将当前的数据存入，流水线恢复，并将栈堆中的标记位置为1。3)需要压栈的栈在栈堆中已满，且标记位为1，这说明之前在栈缓存中存放有数据，只需要在查找表中查询对应的栈号和序号，而后根据序号到栈缓存中压栈即可。
60.综上所述，面向光线追踪的硬件加速器存在着使用栈堆占用过多硬件资源的问题，本实施例针对使用栈堆的光线追踪硬件加速器设计了一组栈缓存，在一个基本的栈堆设计基础上通过增加一组栈缓存以减少每个栈的深度进而降低栈占用硬件资源，并通过设置一位标记位用于标记有无在栈缓存中存放数据，使得缓存可以实现高效处理。本实施例的栈缓存部件在结构上主要包括三部分，其一为多路选择器，主要用于匹配查找表中的数据，进而决定是否需要对栈缓存进行弹栈或压栈操作；其二是查找表，主要保存栈号和对应栈缓存序号的信息；其三是栈缓存，由若干栈和序号组成，从而可为光线追踪硬件加速器提供栈缓存并保证光线并行性，具有存储资源开销低、设计逻辑简单以及对光线追踪硬件性能影响很小的优点。本实施例的栈缓存部件设计硬件结构简单，可以有效地释放栈堆占据的内存空间，显著降低了硬件开销，同时对性能的影响很小。
61.以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

技术特征：
1.一种用于光线追踪硬件加速器的栈缓存部件,其特征在于，包括：栈堆，用于保存光线遍历过程中的节点信息；多路选择器，用于匹配查找表中的数据以决定是否需要对栈缓存进行弹栈或压栈操作；查找表，用于保存栈号及其对应栈缓存的序号；栈缓存，由若干栈及其序号组成；所述栈堆、多路选择器、查找表以及栈缓存依次相连呈流水线结构。2.根据权利要求1所述的用于光线追踪硬件加速器的栈缓存部件,其特征在于，所述栈堆中共包含n个用于保存光线遍历过程中的节点信息的栈1～栈n。3.根据权利要求2所述的用于光线追踪硬件加速器的栈缓存部件,其特征在于，所述栈堆中每一个栈均带有一个标记位，所述标记位取值为0或1，用于表示栈堆中对应的栈是否已经存储在栈缓存中。4.一种光线追踪硬件加速器，其特征在于，包括光线生成渲染器、光线遍历单元、三角形相交测试单元、命中渲染器、未命中渲染器以及栈缓存部件，所述光线生成渲染器、光线遍历单元、三角形相交测试单元依次相连，所述三角形相交测试单元分别与命中渲染器、未命中渲染器相连，所述栈缓存部件为权利要求1～3中任意一项所述的用于光线追踪硬件加速器的栈缓存部件，且所述栈缓存部件分别与、光线遍历单元、三角形相交测试单元、命中渲染器以及未命中渲染器相连。5.一种权利要求1～3中任意一项所述的用于光线追踪硬件加速器的栈缓存部件的应用方法,其特征在于，包括响应弹栈请求对栈堆中某一个栈进行弹栈操作，并同时响应弹栈请求对栈缓存执行下述步骤：s101，判断需要进行弹栈操作的栈是否已经存储在栈缓存中，若需要进行弹栈操作的栈尚未存储在栈缓存中，则结束并退出；否则跳转步骤s102；s102，根据进行弹栈操作的栈号，在查找表中查找对应栈缓存的序号；s103，根据找到的栈缓存的序号，在栈缓存找到该需要对应的缓存栈，并将找到的缓存栈中的数据弹栈。6.根据权利要求5所述的用于光线追踪硬件加速器的栈缓存部件的应用方法,其特征在于，步骤s101中判断需要进行弹栈操作的栈是否已经存储在栈缓存中是指判断需要进行弹栈操作的栈的标记位的取值，若标记位取值为0，则判定需要进行弹栈操作的栈尚未存储在栈缓存中，否则判定需要进行弹栈操作的栈已经存储在栈缓存中。7.根据权利要求5所述的用于光线追踪硬件加速器的栈缓存部件的应用方法,其特征在于，所述弹栈请求来自光线追踪硬件加速器的光线遍历单元和三角形相交测试单元，且所述光线遍历单元当光线遍历时若判定两个子节点与光线都不相交则向栈堆发送弹栈请求，所述三角形相交测试单元在三角形相交测试结束后向栈堆发送弹栈请求。8.根据权利要求5所述的用于光线追踪硬件加速器的栈缓存部件的应用方法,其特征在于，包括响应压栈请求时执行下述步骤：s201，判断压栈请求的栈在栈堆中是否已满，若压栈请求的栈在栈堆中未满，则直接将压栈请求对应的数据存入对应的堆栈中，结束并退出；否则，跳转步骤s202；s202，判断压栈请求的栈是否已经存储在栈缓存中，若尚未存储在栈缓存中，则跳转步
骤s203；否则跳转步骤s204；s203，通过多路选择器将压栈请求送入查找表中查找有无空闲的栈缓存，若有空闲的栈缓存，则将压栈请求对应的数据存入对应的堆栈中存到栈缓存中序号较小的栈缓存的堆栈中，并在查找表中记录此次在栈缓存中存放的序号和对应的栈号；如果没有空的栈缓存，那么将当前光线的处理暂时阻塞，直到查找表中出现空的栈缓存才将压栈请求对应的数据存入，流水线恢复，并将栈堆中对应栈的标记位置为1；s204，通过多路选择器将压栈请求送入查找表中查找对应的栈号和序号，而后根据序号到栈缓存中将对应的缓存栈的数据进行压栈操作。9.根据权利要求8所述的用于光线追踪硬件加速器的栈缓存部件的应用方法,其特征在于，步骤s202中判断压栈请求的栈是否已经存储在栈缓存中是指判断压栈请求的栈的标记位的取值，若标记位取值为0，则判定尚未存储在栈缓存中，否则判定已经存储在栈缓存中。10.根据权利要求9所述的用于光线追踪硬件加速器的栈缓存部件的应用方法,其特征在于，所述压栈请求来自光线追踪硬件加速器的光线遍历单元，所述光线遍历单元在光线遍历结束后判定光线与两个子节点均相交时发送压栈请求以用于将两个子节点中距离较远的子节点信息压入栈堆中。

技术总结
本发明公开了一种用于光线追踪硬件加速器的栈缓存及其应用方法，本发明的栈缓存部件包括：栈堆，用于保存光线遍历过程中的节点信息；多路选择器，用于匹配查找表中的数据以决定是否需要对栈缓存进行弹栈或压栈操作；查找表，用于保存栈号及其对应栈缓存的序号；栈缓存，由若干栈及其序号组成；所述栈堆、多路选择器、查找表以及栈缓存依次相连呈流水线结构。本发明为光线追踪硬件加速器提供栈缓存并保证光线并行性，具有存储资源开销低、设计逻辑简单以及对光线追踪硬件性能影响很小的优点。简单以及对光线追踪硬件性能影响很小的优点。简单以及对光线追踪硬件性能影响很小的优点。


技术研发人员：黄立波 闫润 苏垠 郭辉 郑重 邓全 郭维 雷国庆 王俊辉 隋兵才 孙彩霞 王永文 倪晓强
受保护的技术使用者：中国人民解放军国防科技大学
技术研发日：2023.04.13
技术公布日：2023/7/7