基于八叉树的数据处理方法、装置及计算机可读存储介质

1.本发明涉及数据处理技术领域，尤其涉及一种基于八叉树的数据处理方法、装置及计算机可读存储介质。


背景技术：

2.八叉树(octree)是一种用于描述三维空间的树形数据结构，其原理是把空间的数据按照3d坐标存储到贴图或数组中，能够实现在大型空间数据的快速搜索和查询。
3.在相关技术中，一般采用稀疏八叉树(sparse voxel octree，svo)来实现减小基于八叉树数据结构进行数据存储时内存占用量的效果。而svo是通过对存储在八叉树中的体素表示的几何体进行光线投射来的原理实现的，因此其虽然能一定程度上减小原始的八叉树数据结构的内存占用，但是当svo的存储深度超过16层时，数据的读取或存储速度都会变得非常慢。这导致svo难以适用于大规模的数据处理场景。
4.上述内容仅用于辅助理解本发明的技术方案，并不代表承认上述内容是现有技术。


技术实现要素：

5.本发明的主要目的在于提供一种基于八叉树的数据处理方法，旨在解决如何提升系数八叉树在大规模的数据处理场景下的数据处理效率问题。
6.为实现上述目的，本发明提供的一种基于八叉树的数据处理方法，所述方法包括：
7.获取待存储体数据的最大数据分辨率；
8.基于所述最大数据分辨率，自下而上递减所述待存储体数据中各个层级的数据分辨率，得到lod体数据；
9.将所述lod体数据输入预设八叉树模型，并于所述八叉树模型的根节点处，逐层向下对lod体数据作稀疏化处理至叶子层，得到lod稀疏八叉树，其中，所述lod稀疏八叉树中的各个非空节点带有不同的节点编号；
10.在接收到针对所述lod稀疏八叉树中目标节点的数据处理指令时，获取所述目标节点对应的所述节点编号，并根据所述节点编号跳转至所述目标节点执行数据处理操作。
11.可选地，所述基于所述最大数据分辨率，自下而上递减所述待存储体数据中各个层级的数据分辨率，得到lod体数据的步骤包括：
12.将所述最大数据分辨率作为所述待存储体数据的最下层数据的分辨率，逐层向上递减至所述待存储体数据的最上层，得到所述lod体数据；
13.其中，所述lod体数据中下一层级的数据分辨率为相邻上一层级的数据分辨率的两倍，且各个层级之间的数据量相同，最上层的数据分辨率为所述待存储体数据在存储空间中预设的最小分辨率。
14.可选地，所述将所述lod体数据输入预设八叉树模型，并于所述八叉树模型的根节点处，逐层向下对lod体数据作稀疏化处理至叶子层，得到lod稀疏八叉树的步骤包括：
15.将所述lod体数据输入至所述八叉树模型的根节点；
16.确定所述根节点中的体素稀疏度；
17.基于所述体素稀疏度，逐层向下对lod体数据作稀疏化处理至叶子层，得到所述lod稀疏八叉树。
18.可选地，所述基于所述体素稀疏度，逐层向下对lod体数据作稀疏化处理至叶子层，得到所述lod稀疏八叉树的步骤包括：
19.确定所述根节点的所述体素稀疏度是否大于预设阈值；
20.若是，将所述根节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个所述子节点中；
21.确定各个所述子节点中的所述体素稀疏度是否大于所述预设阈值；
22.若是，再次将所述子节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个所述子节点中，直至当前层级中的各个所述子节点中的lod体数据均小于所述预设阈值，将所述当前层级作为所述叶子层，得到所述lod稀疏八叉树。
23.可选地，所述将所述lod体数据输入至所述八叉树模型的根节点的步骤之后，还包括：
24.于所述根节点处，逐层向下标记所述八叉树模型中各个非空节点，得到所述非空节点的节点编号。
25.可选地，所述于所述根节点处，逐层向下标记所述八叉树模型中各个非空节点的前缀位的步骤包括：
26.获取当前层级的节点中的数据分辨率；
27.根据节点所处层级数和所述数据分辨率，确定所述节点编号；
28.将所述节点编号填充至所述非空节点的所述前缀位；
29.跳转至下一层级，返回执行所述获取当前层级中节点中的数据分辨率的步骤，直至所述八叉树模型中每一非空节点的前缀位均有所述节点编号。
30.可选地，所述根据所述节点编号跳转至所述目标节点执行数据处理操作包括：
31.确定所述节点编号在所述lod稀疏八叉树中是否存在对应的目标节点地址；
32.若存在，根据所述目标节点地址，确定当前节点与目标节点之间的节点偏移量；
33.根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作。
34.可选地，所述根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并读取所述lod体数据的步骤之前，还包括：
35.确定所述节点偏移量是否小于预设偏移量阈值；
36.若是，执行所述根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作；
37.若否，将所述节点偏移量存入预设跳跃偏移块链表。
38.此外，为实现上述目的，本发明还提供一种基于八叉树的数据处理装置，所述基于八叉树的数据处理装置包括：存储器、处理器及存储在所述存储器上并可在所述处理器上运行的基于八叉树的数据处理程序，所述基于八叉树的数据处理程序被所述处理器执行时实现如上所述的基于八叉树的数据处理方法的步骤。
39.此外，为实现上述目的，本发明还提供一种计算机可读存储介质，所述计算机可读存储介质上存储有基于八叉树的数据处理程序，所述基于八叉树的数据处理程序被处理器执行时实现如上所述的基于八叉树的数据处理方法的步骤。
40.本发明实施例提供一种基于八叉树的数据处理方法、装置及计算机可读存储介质，通过构建带有lod结构的稀疏八叉树来存储体数据，使得体数据存储在带有lod结构的稀疏八叉树中，在接收到对lod稀疏八叉树中与当前层级不相邻的目标层级的节点所存储的体数据的数据处理指令时，能够直接跳转去获取另一层级下的节点中的体数据作相应处理，而非一层一层地向上或向下递归至目标层级下作处理。从而使得svo在大规模的数据处理场景下也能够快速读取或存储数据。
附图说明
41.图1为本发明实施例涉及的基于八叉树的数据处理装置的硬件运行环境的架构示意图；
42.图2为本发明基于八叉树的数据处理方法的第一实施例的流程示意图；
43.图3为本发明基于八叉树的数据处理方法的第二实施例的流程示意图；
44.图4为本发明基于八叉树的数据处理方法的第三实施例的流程示意图；
45.图5为本发明基于八叉树的数据处理方法的第四实施例的流程示意图；
46.本发明目的的实现、功能特点及优点将结合实施例，参照附图作进一步说明。
具体实施方式
47.体渲染(physically based rendering)是一种用于生成三维计算机图形的渲染技术，用于模拟三维物体的形状和材质。体渲染技术是基于物理学原理模拟光线在物体表面上的散射、反射、折射等现象来生成图像。因此，体渲染与传统的着色技术不同，传统着色技术是通过手工设置颜色和光照来控制图像的外观，而体渲染则是通过模拟光线在物体上的散射、反射、折射等现象来生成图像。体渲染技术可以生成高质量、真实的三维图像，常用于电影和电视特效、游戏、医疗和科学研究等领域，用来生成人物动画、身体部位分解、疾病模拟等。
48.一般来说，渲染的过程可以分为以下几个步骤：
49.1.模型转换：将三维模型的坐标系转换到观察者的坐标系。
50.2.光栅化：将三维模型的顶点转换为屏幕上的像素点。
51.3.几何处理：对每个像素点进行几何处理，比如剔除、深度测试等。
52.4.着色：使用着色器对每个像素点进行着色，得到最终颜色。
53.5.合成：将所有像素点合成为最终图像。
54.6.显示：将最终图像显示在屏幕上。
55.在传统的建模中，使用诸如多边形网格，nurbs(非均匀有理b样条曲面)面片或细分曲面之类的表面表示来创建3d对象。在传统的建模范式中，表面的视觉属性(例如颜色，粗糙度和反射率)是通过着色算法建模的，该算法可能像phong模型一样简单，也可能像功能齐全的位移变量各向异性brdf一样复杂。由于仅在表面的点上计算光的传播，这些方法通常不能考虑发生在大气中或物体内部的光的相互作用。
56.与表面渲染相反，体渲染描述了用于从三维标量数据生成图像的多种技术。这些技术最初是由通过对自然现象的测量或数值仿真来获取体积数据的科学可视化驱动发展的。典型示例是通过计算机断层扫描(ct)或磁共振成像(mri)获得的人体内部医学数据。其他示例包括计算流体力学(cfd)，地质和地震数据，以及抽象数学数据，例如伪随机数的3d概率分布。
57.而随着高效体绘制技术的发展，体数据在视觉艺术和计算机游戏领域中也变得越来越重要了。体积数据非常适合描述模糊的对象，例如流体，气体和例如云，雾和火等的自然现象。许多艺术家和研究人员已经生成了体数据，以综合补充表面模型，在过程上来说，这对于渲染高质量的特效来说是特别有用的。
58.尽管体积数据比表面更难以可视化，但以真正的三维实体来渲染他们而不退回到2d子集，是很有价值和意义的。
59.体素，是组成体数据的最小单元，一个体素表示体数据中三维空间某部分的值。体素相当于二维空间中像素的概念。如何组织体素元素，加快读取和可视化是一项艰巨的任务。比如说，如果我们有一个模型，设定其分辨率为512x512x512，那么我们将会拥有512x512x512个体素，每个体素代表其在此立方体模型的位置和特性，如：颜色、透光度等。
60.目前，通用的方案是使用八叉树存储，八叉树(octree)是一种树形数据结构，每个内部节点都正好有八个子节点。八叉树常用于分割三维空间，将其递归细分为八个卦限。八叉树是四叉树在三维空间中的对应，在三维图形、三维游戏引擎等领域有很多应用。八叉树的每个节点都可以代表一个空间，对应的八个子节点则将这个空间细分为八个卦限。点域(point region，简称pr)八叉树的节点中都存储着一个三维点，即该节点对应区域的“中心”，也是八个子节点对应区域中的一个角落。矩阵(matrix based，简称mx)八叉树中，节点只记录区域范围，对应的中心点坐标需要从区域范围推算。因此，pr八叉树的根节点可以表示无限大的空间；而mx八叉树的根节点只能表示有限空间，这样才可以得到隐含的中心点。
61.对于一些稀疏的空间结构，已有专家学者提出了一种基于稀疏八叉树结构的高效光线追踪算法和数据结构，其中包含了一种叫voxel data的数据结构，该数据结构由64位的指针构成，前32位用于构建稀疏八叉树，后32位用于提升精度的算法，前32位对于本专利更加有意义，此32位的数据可以分为四个部分，第一个部分是前15位代表指针偏移，接下来的一位代表是否跳跃，该跳跃判断点是用来缓解15位的偏移不足以表示模型的问题，若该跳跃标记被标记为1，则代表需要跳跃才能获得真实的偏移量，接下来的16位用于表征当前和子节点的属性，前8位用于表示当前节点的八个子节点是否存在，后8位用于表示当前节点的八个子节点是否是叶子结点。其光线追踪实现基于八叉树的层次结构遍历，主要有push，advance和pop操作，push处理第一个相交的子节点，压入栈；advance处理当前处理的子节点的姐妹节点；pop处理当前处理子节点的存在的未处理姊妹节点的父节点的姊妹节点。过程如下：
62.1.初始化栈，从根节点开始，push；
63.2.依次遍历八个子节点，若交叉，push；若不交叉，advance；
64.3.若当前无子节点，且不交叉，则pop；
65.尽管稀疏八叉树为大型的体数据存储提供了实现方式，但是随着数据采集技术的快速发展，震波ct、工业ct等三维数据越来越精细，其体数据也越来越大，有的数据体达到
数十gb的大小。给大规模三维数据体快速可视化技术带来了难题，尤其是基于微机的大规模数据场快速可视化。在传统方式下几乎难以实现，因此对数据进行预处理是实现快速可视化的前提。
66.但是上述稀疏八叉树的实现，是将一个整体的体数据集中存储在一棵树上，由此将会带来拓展性和性能的缺陷，比如说：如果体数据过大，存储一整棵树，其深度将超过16层，无论是存储还是读取，都会带来极大的io开销，严重影响可视化的速度，并且这种方式将导致存储的不可拓展，单个文件过大可能导致超过单机文件系统所能容纳的上限。因此在超大规模三维体数据处理过程中，通常会应用八叉树对数据进行分解，按需要分级导入，可以实现对大规模三维数据局部进行快速可视化。并且当需要对全局或者对超过计算机容量的较大局部进行概览和分析时，此方法无法实现，因此还需要应用lod技术。
67.目前，已有专家学者对lod(levels of detail，多细节层次)和八叉树的结合做了一定的研究，如广度八叉树的lod和深度八叉树的lod。
68.优化后的深度八叉树在对大型模型的渲染上，能够有效地使用lod技术来避免一次性读入大量数据，但是其仍未能友好地解决如何将分散的数据节点组织起来的问题，以及如何能够减少不必要的存储开销的问题。
69.总的来说，一方面，传统稀疏八叉树由于将整个模型建立在一棵树上，也就是说存储成了一个文件，未能实现对超大型模型的有效存取。另一方面，深度八叉树虽然解决了如何渲染超大型模型的问题，但他带来一个新的严峻问题，未能实现数据的有效组织，比如：各个节点的分配，只适应于单机文件系统，不能满足日益增长的数据需求；未能有效地减少不必要的存储空间，由于未采用稀疏存储结构，若该模型存在大量空洞，那么实际存储的大小与实际有效的数据大小之比的大小将令人遗憾。
70.因此，本技术通过构建带有lod结构的稀疏八叉树来存储体数据，使得体数据存储在带有lod结构的稀疏八叉树中，在接收到对lod稀疏八叉树中与当前层级不相邻的目标层级的节点所存储的体数据的数据处理指令时，能够直接跳转去获取另一层级下的节点中的体数据作相应处理，而非一层一层地向上或向下递归至目标层级下作处理。从而使得svo在大规模的数据处理场景下也能够快速读取或存储数据。
71.为了更好地理解上述技术方案，下面将参照附图更详细地描述本公开的示例性实施例。虽然附图中显示了本公开的示例性实施例，然而应当理解，可以以各种形式实现本公开而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了能够更透彻地理解本公开，并且能够将本公开的范围完整地传达给本领域的技术人员。
72.作为一种实现方案，图1为本发明实施例方案涉及的基于八叉树的数据处理装置的硬件运行环境的架构示意图。
73.如图1所示，该基于八叉树的数据处理装置可以包括：处理器1001，例如cpu，存储器1005，用户接口1003，网络接口1004，通信总线1002。其中，通信总线1002用于实现这些组件之间的连接通信。用户接口1003可以包括显示屏(display)、输入单元比如键盘(keyboard)，可选用户接口1003还可以包括标准的有线接口、无线接口。网络接口1004可选的可以包括标准的有线接口、无线接口(如wi-fi接口)。存储器1005可以是高速ram存储器，也可以是稳定的存储器(non-volatile memory)，例如磁盘存储器。存储器1005可选的还可以是独立于前述处理器1001的存储装置。
74.本领域技术人员可以理解，图1中示出的基于八叉树的数据处理装置的架构并不构成对基于八叉树的数据处理装置限定，可以包括比图示更多或更少的部件，或者组合某些部件，或者不同的部件布置。
75.如图1所示，作为一种存储介质的存储器1005中可以包括操作系统、网络通信模块、用户接口模块以及基于八叉树的数据处理程序。其中，操作系统是管理和控制基于八叉树的数据处理装置的硬件和软件资源的程序，基于八叉树的数据处理程序以及其他软件或程序的运行。
76.在图1所示的基于八叉树的数据处理装置中，用户接口1003主要用于连接终端，与终端进行数据通信；网络接口1004主要用于后台服务器，与后台服务器进行数据通信；处理器1001可以用于调用存储器1005中存储的基于八叉树的数据处理程序。
77.在本实施例中，基于八叉树的数据处理装置包括：存储器1005、处理器1001及存储在所述存储器上并可在所述处理器上运行的基于八叉树的数据处理程序，其中：
78.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
79.获取待存储体数据的最大数据分辨率；
80.基于所述最大数据分辨率，自下而上递减所述待存储体数据中各个层级的数据分辨率，得到lod体数据；
81.将所述lod体数据输入预设八叉树模型，并于所述八叉树模型的根节点处，逐层向下对lod体数据作稀疏化处理至叶子层，得到lod稀疏八叉树，其中，所述lod稀疏八叉树中的各个非空节点带有不同的节点编号；
82.在接收到针对所述lod稀疏八叉树中目标节点的数据处理指令时，获取所述目标节点对应的所述节点编号，并根据所述节点编号跳转至所述目标节点执行数据处理操作。
83.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
84.将所述最大数据分辨率作为所述待存储体数据的最下层数据的分辨率，逐层向上递减至所述待存储体数据的最上层，得到所述lod体数据；
85.其中，所述lod体数据中下一层级的数据分辨率为相邻上一层级的数据分辨率的两倍，且各个层级之间的数据量相同，最上层的数据分辨率为所述待存储体数据在存储空间中预设的最小分辨率。
86.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
87.将所述lod体数据输入至所述八叉树模型的根节点；
88.确定所述根节点中的体素稀疏度；
89.基于所述体素稀疏度，逐层向下对lod体数据作稀疏化处理至叶子层，得到所述lod稀疏八叉树。
90.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
91.确定所述根节点的所述体素稀疏度是否大于预设阈值；
92.若是，将所述根节点中的lod体数据分配至位于所述八叉树模型的下一层级的八
个所述子节点中；
93.确定各个所述子节点中的所述体素稀疏度是否大于所述预设阈值；
94.若是，再次将所述子节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个所述子节点中，直至当前层级中的各个所述子节点中的lod体数据均小于所述预设阈值，将所述当前层级作为所述叶子层，得到所述lod稀疏八叉树。
95.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
96.于所述根节点处，逐层向下标记所述八叉树模型中各个非空节点，得到所述非空节点的节点编号。
97.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
98.获取当前层级的节点中的数据分辨率；
99.根据节点所处层级数和所述数据分辨率，确定所述节点编号；
100.将所述节点编号填充至所述非空节点的所述前缀位；
101.跳转至下一层级，返回执行所述获取当前层级中节点中的数据分辨率的步骤，直至所述八叉树模型中每一非空节点的前缀位均有所述节点编号。
102.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
103.确定所述节点编号在所述lod稀疏八叉树中是否存在对应的目标节点地址；
104.若存在，根据所述目标节点地址，确定当前节点与目标节点之间的节点偏移量；
105.根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作。
106.处理器1001调用存储器1005中存储的基于八叉树的数据处理程序时，执行以下操作：
107.确定所述节点偏移量是否小于预设偏移量阈值；
108.若是，执行所述根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作；
109.若否，将所述节点偏移量存入预设跳跃偏移块链表。
110.基于上述基于数据处理技术的基于八叉树的数据处理设备的硬件架构，提出本发明基于八叉树的数据处理方法的实施例。
111.参照图2，在第一实施例中，所述基于八叉树的数据处理方法包括以下步骤：
112.步骤s10，获取待存储体数据的最大数据分辨率；
113.在本实施例中，首先获取到输入的待存储体数据的最大数据分辨率，体数据存储在三维数组中。
114.在本实施例中，体数据为一堆体素构成的数据集合，体素为体数据中的最小构成单元，一个体素表示体数据中三维空间某部分的值，体素可以理解为二维空间中的像素。待存储体数据具有一层层的分层，其中，越底层的体素越精细，对应的数据分辨率越大，因此，位于待存储体数据最底层的数据对应的分辨率，为存储所述待存储体数据对应的最大数据分辨率。
115.在本实施例中，数据分辨率是指每个节点所代表的数据的精度或分辨率。每个节点代表的数据范围是由它的区域划分和节点的深度所决定的，深度越深，代表的数据范围和精度就越小，数据分辨率就越高。相反，深度越浅，代表的数据范围和精度就越大，数据分辨率就越低。
116.步骤s20，基于所述最大数据分辨率，自下而上递减所述待存储体数据中各个层级的数据分辨率，得到lod体数据；
117.在本实施例中，在获取到最大数据分辨率之后，对待存储体数据作预处理，具体的，从待存储体数据的最下层开始，将数据分辨率向上逐渐递减，即下一层中的数据分辨率都大于相邻的上一层的数据分辨率。
118.在预处理之后，最下层数据的数据分辨率是待存储体数据中最大的，而最上层数据的数据分辨率是待存储体数据中最小的。即，lod体数据中最上层的数据精度最小，在显示器中显示出来的图像最模糊，而最下层的数据精度最大，在显示器中显示出来的图像最清晰。
119.可以理解的是，当需要调用该lod体数据时，首先调用该lod体数据的最上层数据，即最优先获取数据精度最小的数据，这样能够减小硬件在调用该体数据时的内存占比，当需要去调用其他层次的数据时，再进一步去获取比最上层数据的数据精度更高的，位于最下层之下的其他层数据，从而减小调用该lod体数据时占用的硬件内存。
120.步骤s30，将所述lod体数据输入预设八叉树模型，并于所述八叉树模型的根节点处，逐层向下对lod体数据作稀疏化处理至叶子层，得到lod稀疏八叉树，其中，所述lod稀疏八叉树中的各个节点带有不同的节点编号；
121.在本实施例中，在得到lod体数据之后，将lod体数据输入预设八叉树模型，并于所述八叉树模型的根节点处，逐层向下对lod体数据作稀疏化处理至叶子层，得到lod稀疏八叉树。lod稀疏八叉树表征为具有多细节层次分层且各层均有稀疏存储结构的八叉树。
122.在本实施例中，lod稀疏八叉树的构建原理，是将场景空间分成八个同等大小的子空间，每个子空间可以进一步递归地划分为八个子空间，直到达到某个终止条件，这个过程可以理解为稀疏化。在此过程中，由于数据的子空间划分不会造成数据的压缩，而是在不同的空间层次显示不同精度和细节的场景模型，因此，当lod稀疏八叉树应用在大型场景的绘制下，在提高渲染效率的同时，保证了场景质量和细节。并且，由于lod稀疏八叉树提供了逐级逼近的lod管理，可适应不同的场景大小和细节要求，并且可以高效地支持动态物体和细节变化，还可以应用在空间查询和精细的碰撞检测中。
123.此外，在本实施例中，lod稀疏八叉树中的各个非空节点均带有节点编号，非空节点表征为存在子节点或存在实体的节点，相对的，空节点则表征为没有子节点或不存在实体的节点。示例性地，嘉禾lod稀疏八叉树中的根节点的节点编号为0，该根节点对应的八个子节点我们分别标记为00、01...07。节点编号的作用在步骤s40中具体说明。
124.步骤s40，在接收到针对所述lod稀疏八叉树中目标节点的数据处理指令时，获取所述目标节点对应的所述节点编号，并根据所述节点编号跳转至所述目标节点执行数据处理操作。
125.在本实施例中，在得到lod稀疏八叉树之后，即将待存储体数据以lod稀疏八叉树类型的数据结构进行存储之后，我们得到一个lod稀疏八叉树数据库，该数据库可以供外部
通过相关指令调用其内部的数据。例如，当需要调用lod稀疏八叉树数据库来执行场景渲染操作时，可以通过查询指令进行查询。
126.在本实施例中，节点编号用于快速确定我们所需要的lod稀疏八叉树的区域是否含有值，若有，则跳转至该节点编号对应的目标节点的存储地址。通过节点编号，我们可以根据需要在lod稀疏八叉树中的任一层级来进行跳跃查看。相较于传统的一层一层遍历至该节点所处层级后，再去获取该节点中的数据的方式，能够很大程度上节省索引开销。
127.需要说明的是，数据处理指令中包含的目标节点可以为同一层级下的一个或多个节点，即，在lod稀疏八叉树中可以选取某一层级中的全部区域或部分区域进行查看，例如，某层级中具有8个同一层级的节点a、b、c、d、e、f、g、h，我们可以选取该层级中的一个节点，例如，c节点中的体数据进行查看，也可以选取a、b、c三个节点中的体数据进行查看，也可以选取c、d、e、f四个节点的中的体数据进行查看，或是选取该层级所有节点中的体数据进行查看。
128.在本实施例提供的技术方案中，通过构建带有lod结构的稀疏八叉树来存储体数据，使得体数据存储在带有lod结构的稀疏八叉树中，在接收到对lod稀疏八叉树中与当前层级不相邻的目标层级的节点所存储的体数据的数据处理指令时，能够直接跳转去获取另一层级下的节点中的体数据作相应处理，而非一层一层地向上或向下递归至目标层级下作处理，从而使得svo在大规模的数据处理场景下也能够快速读取或存储数据。
129.进一步的，在本实施例中，所述步骤s20包括：
130.步骤s21，将所述最大数据分辨率作为所述待存储体数据的最下层数据，逐层向上递减至所述待存储体数据的最上层，得到所述lod体数据，其中，所述lod体数据中下一层级的数据分辨率为相邻上一层级的数据分辨率的两倍，且各个层级之间的数据大小相同，最上层的数据分辨率为所述待存储体数据为存储空间中预设的最小分辨率。
131.可选地，在本实施例中，对于待存储体数据的预处理方式，将最大数据分辨率作为待存储体数据最下层数据的分辨率，将上一层的数据分辨率置为该最大分辨率的二分之一，然后再将更上一层的数据分辨率再缩小二分之一，直到最上层数据的分辨率变为该体数据在存储空间中预设的最小分辨率。
132.下面作示例性说明。假设一待存储体数据所需最大数据分辨率为n*n*n，将该分辨率作为待存储体数据最底层第n层的数据分辨率，对于第n-1层的数据分辨率则置为n/2*n/2*n/2，第n-2层的数据分辨率则置为n/4*n/4*n/4，依此类推，直至待存储体数据的第1层的数据分辨率为存储空间中预设的最小分辨率1*1*1，得到具有lod分层的lod体数据。
133.此外，需要说明的是，在本实施例中，虽然将待存储体数据的数据分辨率进行了分层，但每一层的数据量是相同的，即，预处理步骤中不会存在数据的丢失删减，仅仅是数据精细程度的不同。
134.在本实施例提供的技术方案中，采用数据分辨率自下而上递减的预处理策略去构建lod体数据，并且确保每一层的数据量相同，减小调用该lod体数据时占用的硬件内存的同时，避免数据在调用时出现缺损、丢失。
135.参照图3，在第二实施例中，基于任一实施例，所述步骤s30包括：
136.步骤s31，将所述lod体数据输入至所述八叉树模型的根节点；
137.步骤s32，确定所述根节点中的体素稀疏度；
138.步骤s33，基于所述体素稀疏度，逐层向下对lod体数据作稀疏化处理至叶子层，得到所述lod稀疏八叉树。
139.可选地，在本实施例中，对于如何对lod体数据作稀疏化处理构建lod稀疏八叉树，将lod体数据输入至预设的八叉树模型中，lod体数据从根节点开始，获取到根节点中的体素稀疏度，根据体素稀疏度逐层向下去生成该根节点对应的八个子节点，将lod体数据又分配至八个子节点中，然后再分别去确定八个子节点中的体素稀疏度，直至到达八叉树的最底层，即叶子层，得到lod稀疏八叉树。
140.体素稀疏度表征为该节点中实际需要存储的体素数量占总体素数量的比例。
141.下面对如何逐层向下对lod体数据作稀疏化处理至叶子层作示例性说明：
142.1、确定体素的分辨率和边界：首先需要确定体素的分辨率和体素空间的边界大小，以确定八叉树的深度和根节点的边长。
143.2、创建八叉树节点：根据确定的深度，递归地创建八叉树节点，每个节点代表一个固定大小的体素块。
144.3、生成子节点：对于当前节点，根据该体素块中的稀疏度判断其包含的体素块是否需要进一步细分成八个子节点。若需要细分，则创建子节点，并将当前节点和子节点之间建立关系，若不需要细分，则判断当前节点为叶子节点。
145.在本实施例提供的技术方案中，通过体素稀疏度去逐层向下对lod体数据作稀疏化处理至叶子层，得到具有多细节层次分层且各层均有稀疏存储结构的lod稀疏八叉树，在lod体数据的基础上，进一步减少调用原始的待存储体数据占用的硬件内存。
146.进一步的，在本实施例中，所述步骤s33包括：
147.步骤s331，确定所述根节点的所述体素稀疏度是否大于预设阈值；
148.步骤s332，若是，将所述根节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个所述子节点中；
149.步骤s333，确定各个所述子节点中的所述体素稀疏度是否大于所述预设阈值；
150.步骤s334，若是，再次将所述子节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个所述子节点中，直至当前层级中的各个所述子节点中的lod体数据均小于所述预设阈值，将所述当前层级作为所述叶子层，得到所述lod稀疏八叉树。
151.可选地，对于如何根据体素稀疏度去构建lod稀疏八叉树，从根节点开始，判断该节点的体素稀疏度是否大于一预设的阈值，若大于，将根节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个所述子节点中，其中，分配方式可以为随机分配、平均分配和权重分配，根据需要选择，本实施例不作限定。
152.再次判断该子节点中的体素稀疏度是否大于该阈值，若大于，再次将该子节点中的数据分配至下一层级中的八个子节点。递归执行这个步骤，直到一整层中节点的数据稀疏度均小于预设阈值，则将该层作为lod稀疏八叉树的叶子层，叶子层中的节点即为叶子节点，构建完毕。
153.参照图4，在第三实施例中，基于任一实施例，所述步骤s31之后，还包括：
154.步骤s34，于所述根节点处，逐层向下标记所述八叉树模型中各个非空节点，得到所述非空节点的节点编号。
155.可选地，在本实施例中，将lod稀疏八叉树的每个非空节点进行节点编号，节点编
号用于快速确定我们所需要的lod稀疏八叉树的区域是否含有值，若有，则跳转至该节点编号对应的目标节点的存储地址。通过节点编号，我们可以根据需要在lod稀疏八叉树中的任一层级来进行跳跃查看。
156.进一步的，所述步骤s34包括：
157.步骤s341，获取当前层级的节点中的数据分辨率；
158.步骤s342，根据节点所处层级数和所述数据分辨率，确定所述节点编号；
159.步骤s343，将所述节点编号填充至所述非空节点的所述前缀位；
160.步骤s344，跳转至下一层级，返回执行所述获取当前层级中节点中的数据分辨率的步骤，直至所述八叉树模型中每一非空节点的前缀位均有所述节点编号。
161.可选地，为了减少不必要的索引开销，本实施例中采取变长前缀的方法来进行索引，通过节点所处层级数和该节点的数据分辨率来确定具体的节点编号值，并将节点编号值填充至非空节点的前缀位上，从而将lod稀疏八叉树中的每一个节点均设置有编号。
162.示例性地，假设该节点所处层级为第k层，该节点的数据分辨率为i*i*i，采用乘积的方式确定节点编号值n，则确定出的节点编号值n＝ki*ki*ki＝ki3；
163.示例性地，假设该节点所处层级为第k层，该节点的数据分辨率为i*i*i，采用和的方式确定节点编号值n，则确定出的节点编号值n＝k+i*k+i*k+i＝(k+i)3。
164.在本实施例中提供的技术方案中，从根节点开始逐层向下标记所述八叉树模型中各个非空节点中的前缀位，来得到节点编号，从而减少不必要的索引开销，在需要对lod稀疏八叉树中目标节点中的lod体数据调用时，通过节点编号快速索引至该目标节点。
165.参照图5，在第四实施例中，基于任一实施例，所述步骤s40包括：
166.步骤s41，确定所述节点编号在所述lod稀疏八叉树中是否存在对应的目标节点地址；
167.步骤s42，若存在，根据所述目标节点地址，确定当前节点与目标节点之间的节点偏移量；
168.步骤s43，根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作。
169.可选地，在本实施例中，在接收到针对lod稀疏八叉树中目标节点的数据处理指令时，获取目标节点的节点编号，然后确定该节点编号在lod稀疏八叉树中是否存在对应的目标节点地址，根据目标节点地址，确定指针当前所处节点和目标节点之间的节点偏移量。节点偏移量表征为当前节点的地址跳转至目标节点地址之间的数据偏移量。根据节点偏移量，从当前节点跳转至目标节点的所处层级，再从该所处层级中找寻到该目标节点，对该目标节点中的数据执行数据处理指令相应的数据处理操作。
170.具体的，通过设置一个跳跃偏移块链表，我们通过将跳跃偏移块直接插入在当前节点的子节点的索引位置，在读取的过程中，我们需要先判断当前节点是否存在跳跃现象，如有，则跳跃地址应在当前节点的子节点的索引后一个，通过读取该值，我们可以直接跳跃到目标节点。
171.在本实施例提供的技术方案中，通过节点偏移量去实现从当前节点跳转至目标节点的所处层级，并查找到目标节点。从而在实现需要对lod稀疏八叉树中的数据进行获取的时候，能够从当前节点快速跳跃至目标节点。由于不需要一层层的遍历节点，因此即便在
lod稀疏八叉树中的数据量较大，也能够实现数据的快速读取和存储。
172.进一步的，在本实施例中，所述步骤s43之前，还包括：
173.步骤s44，确定所述节点偏移量是否小于预设偏移量阈值；
174.步骤s45，若是，执行所述根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作；
175.步骤s46，若否，将所述节点偏移量存入预设跳跃偏移块链表。
176.可选地，在本实施例中，在节点跳跃过程中，节点偏移量不能够超过设置的节点跳转位数所包含的偏移范围。例如，节点为32位字节，其中15位作为节点的可偏移量数据，则偏移范围为2
15
。
177.当节点偏移量小于预设偏移量阈值时，则代表跳转偏移链表中存储有该目标节点的地址，则执行步骤s43。
178.而倘若节点偏移量大于该预设偏移量阈值，则意味着该节点偏移量对应的节点地址中，在该lod稀疏八叉树中不存在相应的目标节点，则不执行数据处理操作，并且，将该节点偏移量存储至跳跃偏移块链表中，需要说明的是，此处的跳跃偏移块链表与lod稀疏八叉树中设置的跳跃偏移块链表非同一个链表，是用于在节点偏移量超过可偏移范围时记录下贵节点偏移量的链表，以供后续对该异常数据处理指令的查验。
179.在本实施例提供的技术方案中，通过设置偏移量阈值去判断数据处理指令跳转的目标节点是否在lod稀疏八叉树中，当存在则执行该指令，若不存在则将节点偏移量存入跳跃偏移块链表中。通过这种方式，减小了执行错误或异常的数据处理指令对内存占用的开销，进一步的实现了大型渲染场景下lod稀疏八叉树中体数据的快速读取和存储。
180.此外，本领域普通技术人员可以理解的是实现上述实施例的方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成。该计算机程序包括程序指令，计算机程序可以存储于一存储介质中，该存储介质为计算机可读存储介质。该程序指令被基于八叉树的数据处理装置中的至少一个处理器执行，以实现上述方法的实施例的流程步骤。
181.因此，本发明还提供一种计算机可读存储介质，所述计算机可读存储介质存储有基于八叉树的数据处理程序，所述基于八叉树的数据处理程序被处理器执行时实现如上实施例所述的基于八叉树的数据处理方法的各个步骤。
182.其中，所述计算机可读存储介质可以是u盘、移动硬盘、只读存储器(read-only memory，rom)、磁碟或者光盘等各种可以存储程序代码的计算机可读存储介质。
183.需要说明的是，由于本技术实施例提供的存储介质，为实施本技术实施例的方法所采用的存储介质，故而基于本技术实施例所介绍的方法，本领域所属人员能够了解该存储介质的具体结构及变形，故而在此不再赘述。凡是本技术实施例的方法所采用的存储介质都属于本技术所欲保护的范围。
184.本领域内的技术人员应明白，本发明的实施例可提供为方法、系统或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。
185.本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程
图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
186.这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
187.这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
188.应当注意的是，在权利要求中，不应将位于括号之间的任何参考符号构造成对权利要求的限制。单词“包含”不排除存在未列在权利要求中的部件或步骤。位于部件之前的单词“一”或“一个”不排除存在多个这样的部件。本发明可以借助于包括有若干不同部件的硬件以及借助于适当编程的计算机来实现。在列举了若干装置的单元权利要求中，这些装置中的若干个可以是通过同一个硬件项来具体体现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些单词解释为名称。
189.尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。
190.显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

技术特征：
1.一种基于八叉树的数据处理方法，其特征在于，所述基于八叉树的数据处理方法包括：获取待存储体数据的最大数据分辨率；基于所述最大数据分辨率，自下而上递减所述待存储体数据中各个层级的数据分辨率，得到lod体数据；将所述lod体数据输入预设八叉树模型，并于所述八叉树模型的根节点处，逐层向下对lod体数据作稀疏化处理至叶子层，得到lod稀疏八叉树，其中，所述lod稀疏八叉树中的各个非空节点带有不同的节点编号；在接收到针对所述lod稀疏八叉树中目标节点的数据处理指令时，获取所述目标节点对应的所述节点编号，并根据所述节点编号跳转至所述目标节点执行数据处理操作。2.如权利要求1所述的基于八叉树的数据处理方法，其特征在于，所述基于所述最大数据分辨率，自下而上递减所述待存储体数据中各个层级的数据分辨率，得到lod体数据的步骤包括：将所述最大数据分辨率作为所述待存储体数据的最下层数据的分辨率，逐层向上递减至所述待存储体数据的最上层，得到所述lod体数据；其中，所述lod体数据中下一层级的数据分辨率为相邻上一层级的数据分辨率的两倍，且各个层级之间的数据量相同，最上层的数据分辨率为所述待存储体数据在存储空间中预设的最小分辨率。3.如权利要求1所述的基于八叉树的数据处理方法，其特征在于，所述将所述lod体数据输入预设八叉树模型，并于所述八叉树模型的根节点处，逐层向下对lod体数据作稀疏化处理至叶子层，得到lod稀疏八叉树的步骤包括：将所述lod体数据输入至所述八叉树模型的根节点；确定所述根节点中的体素稀疏度；基于所述体素稀疏度，逐层向下对lod体数据作稀疏化处理至叶子层，得到所述lod稀疏八叉树。4.如权利要求3所述的基于八叉树的数据处理方法，其特征在于，所述基于所述体素稀疏度，逐层向下对lod体数据作稀疏化处理至叶子层，得到所述lod稀疏八叉树的步骤包括：确定所述根节点的所述体素稀疏度是否大于预设阈值；若是，将所述根节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个子节点中；确定各个所述子节点中的所述体素稀疏度是否大于所述预设阈值；若是，再次将所述子节点中的lod体数据分配至位于所述八叉树模型的下一层级的八个所述子节点中，直至当前层级中的各个所述子节点中的lod体数据均小于所述预设阈值，将所述当前层级作为所述叶子层，得到所述lod稀疏八叉树。5.如权利要求3所述的基于八叉树的数据处理方法，其特征在于，所述将所述lod体数据输入至所述八叉树模型的根节点的步骤之后，还包括：于所述根节点处，逐层向下标记所述八叉树模型中各个非空节点，得到所述非空节点的节点编号。6.如权利要求5所述的基于八叉树的数据处理方法，其特征在于，所述于所述根节点
处，逐层向下标记所述八叉树模型中各个非空节点的前缀位的步骤包括：获取当前层级的节点中的数据分辨率；根据节点所处层级数和所述数据分辨率，确定所述节点编号；将所述节点编号填充至所述非空节点的所述前缀位；跳转至下一层级，返回执行所述获取当前层级中节点中的数据分辨率的步骤，直至所述八叉树模型中每一非空节点的前缀位均有所述节点编号。7.如权利要求1所述的基于八叉树的数据处理方法，其特征在于，所述根据所述节点编号跳转至所述目标节点执行数据处理操作包括：确定所述节点编号在所述lod稀疏八叉树中是否存在对应的目标节点地址；若存在，根据所述目标节点地址，确定当前节点与目标节点之间的节点偏移量；根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作。8.如权利要求7所述的基于八叉树的数据处理方法，其特征在于，所述根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并读取所述lod体数据的步骤之前，还包括：确定所述节点偏移量是否小于预设偏移量阈值；若是，执行所述根据所述节点偏移量，从所述当前节点跳转至所述目标节点的所处层级，并对所述lod体数据执行所述数据处理操作；若否，将所述节点偏移量存入预设跳跃偏移块链表。9.一种基于八叉树的数据处理装置，其特征在于，所述基于八叉树的数据处理装置包括：存储器、处理器及存储在所述存储器上并可在所述处理器上运行的基于八叉树的数据处理程序，所述基于八叉树的数据处理程序被所述处理器执行时实现如权利要求1至8中任一项所述的基于八叉树的数据处理方法的步骤。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有基于八叉树的数据处理程序，所述基于八叉树的数据处理程序被处理器执行时实现如权利要求1至8中任一项所述的基于八叉树的数据处理方法的步骤。

技术总结
本发明涉及数据处理技术领域，尤其涉及一种基于八叉树的数据处理方法、装置及计算机可读存储介质，其中，所述方法包括：获取待存储体数据的最大数据分辨率；基于最大数据分辨率，自下而上递减待存储体数据中各个层级的数据分辨率，得到LOD体数据；将LOD体数据输入预设八叉树模型，并于八叉树模型的根节点处，逐层向下对LOD体数据作稀疏化处理至叶子层，得到LOD稀疏八叉树；在接收到针对LOD稀疏八叉树中目标节点的数据处理指令时，获取目标节点对应的节点编号，并根据节点编号跳转至目标节点执行数据处理操作。解决了如何提升系数八叉树在大规模的数据处理场景下的数据处理效率问题。大规模的数据处理场景下的数据处理效率问题。大规模的数据处理场景下的数据处理效率问题。


技术研发人员：钟权 陈志广 卢宇彤
受保护的技术使用者：中山大学
技术研发日：2023.03.31
技术公布日：2023/7/22