本技术涉及图像处理，具体而言，本技术涉及一种构建层次包围盒树的方法、处理引擎及芯片。
背景技术：
1、在图像处理领域，光线寻迹(raytracing)是应用较为广泛的一种场景。光线寻迹本质上是光线和物体之间的求交过程，一个场景中如果物体比较多，光线需要与所有物体进行求交运算，这会消耗大量的芯片算力。从而引入层次包围盒(bounding volumehierarchies，bvh)的概念，bvh是对一个空间内的物体建立层次化的包围盒，首先求光线和处于顶层的包围盒是否相交，如果不相交，则无需求光线与其子树中的包围盒是否相交了，这样可以大大节省算力消耗。
2、bvh的引入虽然大大减轻了光线和包围盒求交的计算负载，但bvh树的建立同样会消耗一定的算力，并且建树的时间复杂度较高，如何高效实现层次化包围盒的构建，是提升光线寻迹等应用场景性能的关键。
技术实现思路
1、本技术实施例提供了一种构建层次包围盒树的方法、处理引擎及芯片，可以解决现有技术的上述问题。所述技术方案如下：
2、根据本技术实施例的第一个方面，提供了一种构建层次包围盒树的方法，应用于处理引擎序列中的任意一个处理引擎，处理引擎序列与数据总线连接，每个处理引擎包括寄存器，寄存器用于存储一个莫顿编码以及莫顿编码本轮迭代所在的bvh子树的状态信息，状态信息至少包括左边界序号和右边界序号，方法包括：
3、根据预先构建的莫顿编码序列，在寄存器中存储莫顿编码以及初始的状态信息，莫顿编码在莫顿编码序列中的序号为处理引擎自身在处理引擎序列中的序号，左边界序号为莫顿编码序列的首位莫顿编码的序号，右边界序号为莫顿编码序列的末位莫顿编码的序号；
4、与处理引擎序列中的其他处理引擎并行迭代操作，直至本轮迭代所在的bvh子树的左边界和右边界均为处理引擎自身存储的莫顿编码的序号；
5、每轮迭代操作包括：
6、在本轮迭代的每个阶段，通过数据总线与其他处理引擎交互各自寄存器存储的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息；
7、其中，对于本轮迭代的起始阶段，参考信息为处理引擎自身存储的莫顿编码，对于本轮迭代的非起始阶段，参考信息为上一阶段更新的状态信息，本轮迭代的末尾阶段更新的状态信息为左边界序号或右边界序号。
8、作为一种可选的实施方式，状态信息还包括首位不同位、目标子编码以及切分点标识中的至少一种；
9、首位不同位是指本轮迭代所在的bvh子树中左边界和右边界的莫顿编码之间的首个子编码不同的子编码位置；
10、目标子编码是指处理引擎自身存储的莫顿编码中位于首位不同位的子编码；
11、切分点标识用于表示处理引擎自身存储的莫顿编码是否为本轮迭代所在的bvh子树的切分点。
12、作为一种可选的实施方式，每轮迭代还包括切分点确定阶段，切分点确定阶段更新的状态信息为切分点标识；
13、通过数据总线与其他处理引擎交互各自寄存器的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息，包括：
14、在本轮迭代的末尾阶段，通过数据总线与其他处理引擎交互各自在切分点确定阶段更新的切分点标识，以确定本轮迭代所在的bvh子树对应的参考处理引擎，参考处理引擎的切分点标识用于表示参考处理引擎自身存储的莫顿编码为本轮迭代所在的bvh子树的切分点；
15、根据处理引擎自身和参考处理引擎的先后顺序，确定处理引擎自身存储的莫顿编码在下轮迭代所在的bvh子树的左边界和右边界，以更新寄存器中的左边界序号或右边界序号。
16、作为一种可选的实施方式，每轮迭代还包括首位不同位广播阶段和切分点确定阶段，首位不同位广播阶段更新的状态信息为目标子编码：切分点确定阶段更新的状态信息为切分点标识；
17、通过数据总线与其他处理引擎交互各自寄存器的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息，包括：
18、在本轮迭代的切分点确定阶段，通过数据总线获得后一个处理引擎在首位不同位广播阶段更新的目标子编码；
19、若处理引擎自身的目标子编码与后一个处理引擎的目标子编码不一致，则更新寄存器中的切分点标识赋值为真，以表示处理引擎自身为本轮迭代所在的bvh子树的切分点；
20、若处理引擎自身的目标子编码与后一个处理引擎的目标子编码一致，则更新寄存器中切分点标识赋值为假，以表示处理引擎自身不为本轮迭代所在的bvh子树的切分点。
21、作为一种可选的实施方式，状态信息还包括：左边界有效标识，左边界有效标识用于表示处理引擎自身存储的莫顿编码是否为本轮迭代所在的bvh子树中的左边界；
22、每轮迭代还包括首位计算阶段和首位不同位广播阶段，首位计算阶段更新的状态信息为首位不同位；首位不同位广播阶段更新的状态信息为目标子编码：
23、通过数据总线与其他处理引擎交互各自寄存器的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息，包括：
24、在本轮迭代的首位不同位广播阶段，若处理引擎自身的左边界有效标识为假，则通过数据总线获得左边界对应的处理引擎在首位计算阶段更新的首位不同位，若处理引擎自身的左边界有效标识为真，则通过数据总线将在首位计算阶段确定的首位不同位发送其他处理引擎；
25、从处理引擎自身存储的莫顿编码中确定首位不同位的目标子编码，并更新处理引擎自身的寄存器中的目标子编码。
26、作为一种可选的实施方式，首位计算阶段为本轮迭代的起始阶段，通过数据总线与其他处理引擎交互各自寄存器的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息，包括：
27、在本轮迭代的首位计算阶段，通过数据总线发送处理引擎自身存储的莫顿编码；
28、若处理引擎自身的左边界有效标识为真，则通过数据总线获得右边界的莫顿编码；
29、对处理引擎自身存储的莫顿编码和右边界的莫顿编码进行异或操作，对异或操作的结果进行领先一次lod操作，获得首位不同位，并更新处理引擎自身的寄存器中的首位不同位。
30、作为一种可选的实施方式，根据处理引擎自身和参考处理引擎的先后顺序，确定处理引擎自身存储的莫顿编码在下轮迭代所在的bvh子树的左边界和右边界，包括：
31、若参考处理引擎为处理引擎自身，则确定下轮迭代所在的bvh子树的左边界保持不变，右边界为处理引擎自身存储的莫顿编码；
32、若参考处理引擎位于处理引擎自身之前，则确定下轮迭代所在的bvh子树的左边界为参考处理引擎的后一个处理引擎存储的莫顿编码，右边界保持不变；
33、若参考处理引擎位于处理引擎自身之后，则确定下轮迭代所在的bvh子树的右边界为参考处理引擎存储的莫顿编码，左边界保持不变。
34、作为一种可选的实施方式，在本轮迭代的末尾阶段，更新寄存器中的左边界序号或右边界序号，之后还包括：
35、将寄存器中除左边界序号和右边界序号以外的状态信息更新为空值。
36、作为一种可选的实施方式，处理引擎序列还与状态机连接，状态机用于向各个处理引擎周期性发送对应各阶段的阶段信号；
37、在本轮迭代的每个阶段，通过数据总线与其他处理引擎交互各自寄存器的参考信息，之前还包括：
38、获得状态机发送的阶段信号，根据阶段信号确定当前所处的阶段。
39、根据本技术实施例的第二个方面，提供了一种处理引擎序列中的处理引擎，处理引擎序列与数据总线连接，每个处理引擎包括寄存器，寄存器用于存储一个莫顿编码以及莫顿编码本轮迭代所在的bvh子树的状态信息，状态信息至少包括左边界序号和右边界序号，处理引擎包括：
40、初始化模块，用于根据预先构建的莫顿编码序列，在寄存器中存储莫顿编码以及初始的状态信息，莫顿编码在莫顿编码序列中的序号为处理引擎自身在处理引擎序列中的序号，左边界序号为莫顿编码序列的首位莫顿编码的序号，右边界序号为莫顿编码序列的末位莫顿编码的序号；
41、并行迭代模块，用于与处理引擎序列中的其他处理引擎并行迭代操作，直至本轮迭代所在的bvh子树的左边界和右边界均为处理引擎自身存储的莫顿编码的序号；
42、每轮迭代操作包括：
43、在本轮迭代的每个阶段，通过数据总线与其他处理引擎交互各自寄存器存储的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息；
44、其中，对于本轮迭代的起始阶段，参考信息为处理引擎自身存储的莫顿编码，对于本轮迭代的非起始阶段，参考信息为上一阶段更新的状态信息，本轮迭代的末尾阶段更新的状态信息为左边界序号或右边界序号。
45、作为一种可选的实施方式，状态信息还包括首位不同位、目标子编码以及切分点标识中的至少一种；
46、首位不同位是指本轮迭代所在的bvh子树中左边界和右边界的莫顿编码之间的首个子编码不同的子编码位置；
47、目标子编码是指处理引擎自身存储的莫顿编码中位于首位不同位的子编码；
48、切分点标识用于表示处理引擎自身存储的莫顿编码是否为本轮迭代所在的bvh子树的切分点。
49、作为一种可选的实施方式，每轮迭代还包括切分点确定阶段，切分点确定阶段更新的状态信息为切分点标识；
50、并行迭代模块包括：
51、参考引擎确定单元，用于在本轮迭代的末尾阶段，通过数据总线与其他处理引擎交互各自在切分点确定阶段更新的切分点标识，以确定本轮迭代所在的bvh子树对应的参考处理引擎，参考处理引擎的切分点标识用于表示参考处理引擎自身存储的莫顿编码为本轮迭代所在的bvh子树的切分点；
52、边界更新单元，用于根据处理引擎自身和参考处理引擎的先后顺序，确定处理引擎自身存储的莫顿编码在下轮迭代所在的bvh子树的左边界和右边界，以更新寄存器中的左边界序号或右边界序号。
53、作为一种可选的实施方式，每轮迭代还包括首位不同位广播阶段和切分点确定阶段，首位不同位广播阶段更新的状态信息为目标子编码：切分点确定阶段更新的状态信息为切分点标识；
54、并行迭代模块包括：
55、目标子编码获得单元，用于在本轮迭代的切分点确定阶段，通过数据总线获得后一个处理引擎在首位不同位广播阶段更新的目标子编码；
56、切分点确定单元，用于若处理引擎自身的目标子编码与后一个处理引擎的目标子编码不一致，则更新寄存器中的切分点标识赋值为真，以表示处理引擎自身为本轮迭代所在的bvh子树的切分点；若处理引擎自身的目标子编码与后一个处理引擎的目标子编码一致，则更新寄存器中切分点标识赋值为假，以表示处理引擎自身不为本轮迭代所在的bvh子树的切分点。
57、作为一种可选的实施方式，状态信息还包括：左边界有效标识，左边界有效标识用于表示处理引擎自身存储的莫顿编码是否为本轮迭代所在的bvh子树中的左边界；
58、每轮迭代还包括首位计算阶段和首位不同位广播阶段，首位计算阶段更新的状态信息为首位不同位；首位不同位广播阶段更新的状态信息为目标子编码：
59、并行迭代模块包括：
60、广播单元，用于在本轮迭代的首位不同位广播阶段，若处理引擎自身的左边界有效标识为假，则通过数据总线获得左边界对应的处理引擎在首位计算阶段更新的首位不同位，若处理引擎自身的左边界有效标识为真，则通过数据总线将在首位计算阶段确定的首位不同位发送其他处理引擎；
61、目标子编码更新单元，用于从处理引擎自身存储的莫顿编码中确定首位不同位的目标子编码，并更新处理引擎自身的寄存器中的目标子编码。
62、作为一种可选的实施方式，首位计算阶段为本轮迭代的起始阶段，并行迭代模块包括：
63、编码发送单元，用于在本轮迭代的首位计算阶段，通过数据总线发送处理引擎自身存储的莫顿编码；
64、右编码获得单元，用于若处理引擎自身的左边界有效标识为真，则通过数据总线获得右边界的莫顿编码；
65、首位不同位确定单元，用于对处理引擎自身存储的莫顿编码和右边界的莫顿编码进行异或操作，对异或操作的结果进行领先一次lod操作，获得首位不同位，并更新处理引擎自身的寄存器中的首位不同位。
66、作为一种可选的实施方式，边界更新单元具体用于：
67、若参考处理引擎为处理引擎自身，则确定下轮迭代所在的bvh子树的左边界保持不变，右边界为处理引擎自身存储的莫顿编码；
68、若参考处理引擎位于处理引擎自身之前，则确定下轮迭代所在的bvh子树的左边界为参考处理引擎的后一个处理引擎存储的莫顿编码，右边界保持不变；
69、若参考处理引擎位于处理引擎自身之后，则确定下轮迭代所在的bvh子树的右边界为参考处理引擎存储的莫顿编码，左边界保持不变。
70、作为一种可选的实施方式，在本轮迭代的末尾阶段，边界更新单元还用于：
71、将寄存器中除左边界序号和右边界序号以外的状态信息更新为空值。
72、作为一种可选的实施方式，处理引擎序列还与状态机连接，状态机用于向各个处理引擎周期性发送对应各阶段的阶段信号；
73、处理引擎还包括：
74、阶段确定模块，用于获得状态机发送的阶段信号，根据阶段信号确定当前所处的阶段。
75、根据本技术的第三个方面，提供一种芯片，包括处理引擎序列，处理引擎序列包括至少两个如上述第二方面的处理引擎。
76、作为一种可选的实施方式，芯片还包括与处理引擎序列连接的数据总线和状态机。
77、根据本技术实施例的第四个方面，提供了一种电子设备，该电子设备包括存储器、处理器及存储在存储器上的计算机程序，处理器执行计算机程序以实现上述构建bvh树的方法的步骤。
78、本技术实施例提供的技术方案带来的有益效果是：
79、通过具有新的处理架构的装实现，该装置包括处理引擎序列，该方法应用于处理引擎序列中的任意一个处理引擎，处理引擎序列和数据总线连接，为各处理引擎序列进行数据传输以及并行迭代奠定基础，处理引擎包括寄存器，寄存器用于存储一个霍顿编码以及该霍顿编码本轮迭代所在的bvh子树的状态信息，通过在寄存器中存储霍顿编码以及初始的状态信息，所有处理引擎并行迭代操作，在迭代的每个阶段，通过数据总线与其他处理引擎交互各自寄存器存储的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息，读取方便，不存在大量访存，性能得到明显提升。本技术构建bvh树产生的各类信息，从l1/l2缓存读入到最终bvh树构建完成的过程中，全部进行硬件在线处理，无需将中间结果写入l1/l2缓存中，大大提升了处理效率；每轮迭代，各处理引擎并行计算，只需几个时钟周期即可完成当前轮迭代中所有子树的切分，效率很高，时间复杂度只有o(log(n))。
1.一种构建层次包围盒bvh树的方法，其特征在于，应用于处理引擎序列中的任意一个处理引擎，所述处理引擎序列与数据总线连接，每个处理引擎包括寄存器，所述寄存器用于存储一个莫顿编码以及所述莫顿编码本轮迭代所在的bvh子树的状态信息，所述状态信息至少包括左边界序号和右边界序号，所述方法包括：
2.根据权利要求1所述的方法，其特征在于，所述状态信息还包括首位不同位、目标子编码以及切分点标识中的至少一种；
3.根据权利要求2所述的方法，其特征在于，每轮迭代还包括切分点确定阶段，所述切分点确定阶段更新的状态信息为所述切分点标识；
4.根据权利要求2所述的方法，其特征在于，每轮迭代还包括首位不同位广播阶段和切分点确定阶段，所述首位不同位广播阶段更新的状态信息为所述目标子编码：所述切分点确定阶段更新的状态信息为所述切分点标识；
5.根据权利要求2所述的方法，其特征在于，所述状态信息还包括：左边界有效标识，所述左边界有效标识用于表示处理引擎自身存储的莫顿编码是否为本轮迭代所在的bvh子树中的左边界；
6.根据权利要求5所述的方法，其特征在于，所述首位计算阶段为本轮迭代的起始阶段，所述通过所述数据总线与所述其他处理引擎交互各自寄存器的参考信息，以更新处理引擎自身的寄存器在本阶段的状态信息，包括：
7.根据权利要求3所述的方法，其特征在于，所述根据处理引擎自身和所述参考处理引擎的先后顺序，确定处理引擎自身存储的莫顿编码在下轮迭代所在的bvh子树的左边界和右边界，包括：
8.根据权利要求3或7所述的方法，其特征在于，在本轮迭代的末尾阶段，所述更新所述寄存器中的左边界序号或右边界序号，之后还包括：
9.根据权利要求1-8任意一项所述的方法，其特征在于，所述处理引擎序列还与状态机连接，所述状态机用于向各个处理引擎周期性发送对应各阶段的阶段信号；
10.一种处理引擎序列中的处理引擎，其特征在于，所述处理引擎序列与数据总线连接，每个处理引擎包括寄存器，所述寄存器用于存储一个莫顿编码以及所述莫顿编码本轮迭代所在的bvh子树的状态信息，所述状态信息至少包括左边界序号和右边界序号，所述处理引擎包括：
11.根据权利要求10所述的处理引擎，其特征在于，所述状态信息还包括首位不同位、目标子编码以及切分点标识中的至少一种；
12.根据权利要求11所述的处理引擎，其特征在于，每轮迭代还包括切分点确定阶段，所述切分点确定阶段更新的状态信息为所述切分点标识；
13.根据权利要求11所述的处理引擎，其特征在于，每轮迭代还包括首位不同位广播阶段和切分点确定阶段，所述首位不同位广播阶段更新的状态信息为所述目标子编码：所述切分点确定阶段更新的状态信息为所述切分点标识；
14.根据权利要求所述的处理引擎，其特征在于，状态信息还包括：左边界有效标识，所述左边界有效标识用于表示处理引擎自身存储的莫顿编码是否为本轮迭代所在的bvh子树中的左边界；
15.根据权利要求14所述的处理引擎，其特征在于，首位计算阶段为本轮迭代的起始阶段，所述并行迭代模块包括：
16.根据权利要求12所述的处理引擎，其特征在于，所述边界更新单元具体用于：
17.根据权利要求12或16所述的处理引擎，其特征在于，在本轮迭代的末尾阶段，所述边界更新单元还用于：
18.根据权利要求10-17任意一项所述的处理引擎，其特征在于，所述处理引擎序列还与状态机连接，所述状态机用于向各个处理引擎周期性发送对应各阶段的阶段信号；
19.一种芯片，其特征在于，包括处理引擎序列，所述处理引擎序列包括至少两个如权利要求10-18任意一项所述的处理引擎。
20.根据权利要求19所述的芯片，其特征在于，还包括与所述处理引擎序列连接的数据总线和状态机。
