基于改进的八叉树索引与分层渲染的海量激光点云可视化技术

王磊　郭清菊　姜晗

摘要：近年来利用三维激光扫描技术进行的国内各地城市数字化发展迅速，随着硬件技术的升级和扫描范围的逐渐扩大，获得的相应的三维数据可达TB级。因此，如何合理的建立点云索引管理机制，是解决海量点云数据组织和管理的关键问题。本文首先对传统八叉树数据结构的索引方法进行了优化，然后对三维点云分块，建立八叉树索引数据文件，同时用LOD方法对其进行分层抽稀操作，通过建立改进的八叉树与LOD方法相结合的索引，来降低内存的消耗、提高查询的效率，最后根据屏幕显示范围与视角变化实时读取释放点云索引数据，从而实现海量点云数据的可视化。

关键词：海量点云；八叉树索引；细节层次模型；可视化

中图分类号：000000 文献标识码：A DOI：10.3969/j.issn.1003-6970.2016.04.026

0 引言

近年来，城市数字化工作在国内各线城市中开展，在对城市的三维空间信息的采样获取过程中，逐渐实践和总结出了多种快速有效的手段。其中，使用三维扫描技术对被测目标采集真实空间坐标数据的方法被广泛采用并应用到采集工作中，三维激光扫描技术所依托的软件硬件在近些年来得到了迅速的发展，扫描目标场景的不断增大和场景复杂度的不断升高，都对扫描设备的存储量和扫描算法的运算效率提出了挑战。例如，广泛装备于汽车的激光扫描设备，其工作原理就是使用数个激光扫描器对三维点云数据进行采集，最终获取的扫描数据量接近TB级，由此看来，处理数据的算法亟待优化和改进。为了更好的将采集到的海量点云数据应用到三维重建与快速辅助生成地形图等实际应用中来，需要对海量点云数据的管理算法进行不断的优化。在管理海量点云数据时，最为常用的管理方法是利用索引管理点云数据，索引的好坏直接关系到点云数据处理的效率，因此如何完善现有的索引算法，建立更高效的海量点云索引，是近几年相关方向的研究重点之一。

目前，实现海量点云数据快速显示的有效方法是构建索引树，常用的索引树主要包括R树、K-D树、四叉树和八叉树等。其中，R树具有较强的灵活性和调节性，但由于中间节点允许重叠，在查找速度、动态操作性能方面仍存在一些不足；四叉树和八叉树结构简单，对于精确匹配点的查找性能较高，但树的动态性较差，树的平衡性不好，以至于影响点云显示的交互性。针对上述问题，国内外研究者相继提出了一系列改进的方法。Beckmmann等在R树的基础上提出了R*树，相比于R树，R*树的优越性体现在查找方式和节点操作的多样性，并且它同时支持点和空间数据的索引，但是R*树的索引构建时间比R树略高。支晓栋等提出的一种改进四叉树算法可以快速完成索引树的构建，但是该算法构建的索引树的树高减小，降低了数据的查询速度。

相较于传统方法在处理点云数据时，内存占用率高，执行效率低等问题，本文提出了一种新的方法，该方法以优化后的八叉树数据结构为基础，对可视化过程中需要的海量点云数据进行有效的组织。由于本文对海量点云数据同时进行八叉树结构的索引创建操作和LOD抽稀采样操作，并对传统的八叉树数据结构经过了优化，所以，在索引创建与检索过程中，可以实时降低内存的消耗、提高查询效率。最终根据显示范围查找索引读取对应数据块，从而实现海量的点云数据更加高效的可视化浏览。

1 改进的八叉树索引算法与LOD技术

1.1 改进的八叉树索引算法

八叉树结构是一种用来描述三维空间的数据结构，八叉树中任一节点的子节点均为八个，各节点分别指向下一个八叉树节点。对一定的三维空间做基于三维坐标轴方向的分割，可以得到相应的八个小立方体，各小立方体被称为体元，每个体元中存储相应的属性数据，这就是八叉树结构。通过对经典八叉树算法分析可知，如果将经典八叉树数据结构直接应用于海量点云数据的管理，其各节点在存储结构上存在冗余，比如，为提高检索速度，相邻指针和父指针会被存储在节点之间，但是相应的内存空间会增大。如图1.1所示，指向父节点的指针我们在这里使用m parent命名，相应的，定义孩子节点指针为m_child，使用m_pointsNum保存数据块ID，另外，m_points表示当前指针。

虽然在设计时对八叉树的结构考虑的各方面都非常细致，但是在点云数据管理的应用中其中的某些属性信息并没有保存的必要。为了降低程序在运行时的内存占用率，本文分以下几步对八叉树数据结构进行优化：首先对以上的存储结构中的非必需字段进行删除，以释放内存容量，降低存储冗余。比如可以将节点的父指针入栈，使用基于栈的相关操作方法来完成对其父节点指针的查找操作，因此各节点不需要为父节点指针作单独的存储。其次，优化结构以节省存储空间。由于点云一般都是采集现实区域中的数据，比如学校、村庄、高速公路等，因其地理位置的不定性，在采集空间数据时，只有一部分区域会生成点云，相应在进行存储时就会有很大的空闲空间。在存储八叉树的线性链表中，各节点是否有子节点直接决定了该节点是否需要进行下一步分割处理。基于此，可以定义一个指针指向所有的子树。1个字节有8个比特，恰好对应八个子节点，即可以用每个比特作为标识，来表示当前节点的子节点是否存在。

依据上文中的分析，优化后的八叉树数据结构如图1.2所示：

其中m_child指向了第一个孩子。m_allChilds表示孩子的状态，即依次标示每个节点的8个孩子是否存在。显而易见，相较于经典的八叉树，这样的编码方式在运行时的内存占用率有了很大降低。尤其在程序运行时，相应索引的建立和检索操作大大降低了内存占用率，提高了执行效率。

1.2 LOD可视化技术

这里提到的LOD技术，其英文全称为level ofdetails，简称LOD，字面意思可以理解为“多层次（展现）细节”技术，在该技术的作用下，渲染资源会依据模型各区域的重要程度进行重分配，从而对提高渲染效率。例如，视角靠近物体的时候，就选择精细的、高分辨率的模型来进行实时渲染，而当视角远离的时候，就选择低分辨率的、粗糙的模型来进行渲染；根据视角的变化来实时地进行显示模型的切换，从而快速绘制显示图形、实现海量数据的实时交互。

经典的基于规则格网构建LOD模型的方法是Lindstrom等人提出的，基于视点的连续细节层次（Continuous LOD，简称CLOD）算法。将一个正方体的点云区域均等分割成八个小正方体点云区域，而被分割出来的正方体均为要构造的八叉树的一个节点，在这些节点中存有对应区域的点云数据，依据所扫描的区域的具体情况，越复杂的点云所分割的精细度就更大，从而得到的精确度就更高。本文基于该方法，自顶向下递归地对点云数据进行划分，并建立了对应的数据结构，同时，根据屏幕显示的覆盖范围，决定什么时候、加载哪些节点存储的点云数据，来进行LOD模型的动态更新。

本文根据LOD算法的基本思想，使用八叉树数据结构对该模型分层重构。首先根据原始点云数据量的大小，得到原始数据的范围，即Xmin，Xmax，Ymin，Ymax，Zmin，Zmax，根据总体数据的Zmax、Zmin与实际需要来确定分割深度N。然后，依据本文提出的改进的八叉树方法对获得的数据进行点云分块，这种分块操作的顺序是自顶向下的。如，首先对第N层深度的点云进行等间距抽稀，每隔2N个点进行采样，生成的数据使用八叉树结构存储，作为第N层的节点，存储到八叉树结构中去；然后继续对N-l层的点云数据采用相同处理，此时抽稀间距为2N-l，并排除掉已经在八叉树中存储的（即抽稀间距为2N的点云数据），这些作为八叉树的第N-1层的节点，存储到八叉树结构中去，持续分割，直到N=1，当N=1时，不再需要抽稀，直接将该区域范围内未存储到八叉树结构中的点存储到该层对应节点即可。

至此，数据索引构建完成。在浏览的过程中，根据当前视角的坐标来计算需要显示的点云块的范围，根据视角远近比例来计算显示深度，即可在保证运行效率的前提下实现动态的点云渲染。

2 实验与分析

本文利用c++与vtk实现了海量点云数据的索引快速建立与动态调度，并实现了渲染与绘制，实验数据为某地区的点云扫描数据，实验环境为intel corei7处理器，8G内存。

如图2.1与图2.2中所示为实验过程中海量激光点云数据的实现效果。表2.1将本文方法与传统构建八叉树索引处理方式进行了比较。对于两种方法对同一组点云数据，在海量数据索引的构建、内存占用情况、节点存储文件大小等数据信息做了对比与分析。

经过对表2.1中的数据进行分析我们可以得到，使用本文中的算法对点云数据进行处理时，所消耗的时间和点云的体积是有着类似线性相关性的。传统方法对点云数据的处理步骤为：先对原始点云做八叉树分块处理，再进行LOD抽稀，即分层抽稀操作需要等到前一步（分块处理）完成后再进行，而本文中提到的算法思想为：对点云数据的分块操作与LOD抽稀同时进行，所以本方法在生成索引文件的过程中所消耗的时间与传统方法相比要短得多，并且，为了降低八叉树索引操作在运行时的内存消耗，本文还对传统的八叉树数据结构进行了优化。另外，本文方法的最大优势，就是在创建索引时，就通过抽稀分层实现了LOD算法，因此在实时浏览时，直接调用八叉树，即实现了LOD算法，不需要在显示时二次构建渲染分层模型，节省了大量内存。

实验数据表明：本文方法较传统方法相比更适合应用于海量点云数据的实时呈现。本文对传统的八叉树的数据结构进行了优化，使其在对点云数据的处理中有着更高的运行效率。改进后的方法首先对点云数据进行索引分块，在对数据进行LOD抽稀的同时，使用优化后的八叉树数据结构对数据进行存储管理，节省了存储空间，降低了内存占用率。

3 结语

综上，本文提出的对点云数据的处理方法相较于经典算法在执行渲染操作时，显示效率更高，更能满足实际海量点云数据可视化的需求。通过对比数据表明，本文的算法是值得进一步研究与应用的。此外，为了提高点云渲染效率，需要进一步研究如何与GPU渲染方法相结合，从而取得更好的显示效果。