多分辨率LOD的海量点云显示技术研究

杨振发，万 刚，李 锋，李 滨

（1.信息工程大学，河南 郑州 450000；2. 75711部队，广东 广州 510000）

多分辨率LOD的海量点云显示技术研究

杨振发1，万 刚1，李 锋1，李 滨2

（1.信息工程大学，河南 郑州 450000；2. 75711部队，广东 广州 510000）

利用八叉树数据结构对海量点云进行分块处理，将八叉树叶结点的点云逐层随机采样后保存在外存中构建多分辨率LOD数据结构，设计了一种基于视点的多分辨率点云内外存调度策略，实现了海量点云的流畅显示。通过对一组海量点云数据进行实验，分析了不同八叉树划分深度对八叉树划分、多分辨率数据构建以及显示的影响。

八叉树；多分辨率LOD；海量点云；内外存调度；点云绘制

随着三维激光扫描技术和多角度摄影测量稠密匹配技术的发展，海量点云数据的处理和实时绘制为城市高效建模提出一种新的解决方案。传统的基于三角面的模型绘制需要额外存储点之间的拓扑关系，而基于点的表达是最自然、直接的方式，在大场景中浏览足够密集的点模型时，采样点在屏幕上的投影小于单位像素，可直接用于大区域场景的可视化表达。因此，海量点云数据的实时绘制作为点云数据处理和分析的基础，成为了计算机视觉领域的研究热点。

国内外学者对海量点云的快速显示进行了研究，主要关注点在优化点云数据的存储结构和数据调度方式。Surfels[1]和Qsplat[2,3]都通过树状结构进行数据的存储，并通过多细节层次减少内存消耗，但二者预处理过程比较费时，不平衡的树状结构易导致树深过大进而降低查询效率。文献[4]采用改进四叉树的数据组织方法管理机载激光点云，并采用分段文件映射随机抽取不同细节的点云来实现海量点云的管理和显示，这种二维的数据管理方法难以稳定支持视锥体裁剪的可视化算法。文献[5]采用计算机集群的并行访问技术，将海量点云分配到多个服务器，以提高数据的管理效率。文献[6,7]通过数据分块降低海量数据的复杂性，并建立数据块的多分辨率结构，实现了海量点云在一般配置机器上的轻松浏览，但这种算法仅适用于均匀分布的稠密点云模型。

针对以上问题，本文采用易于实现的八叉树数据结构对海量点云进行分块处理，将八叉树叶结点上的点云进行随机采样建立点云八叉树的多分辨率数据结构，并逐层保存在外存设备中，最后设计了一种基于视点的内外存调度策略实现了海量点云的流畅显示，为海量点云的数据处理和分析奠定基础。本文的算法流程如图1所示。

图1 海量点云实时显示流程图

1 点云的八叉树划分与多分辨率外存组织

八叉树是四叉树在三维空间上的延伸[8]，由于其采用规则的格网剖分，具有较好的可操作性，能满足三维视锥体裁剪算法，因此，本文采用八叉树的数据索引结构，在对海量点云进行数据组织的基础上，以一定的采样率建立各层级的多分辨率点云数据，并以文件映射的方式将海量点云进行外存。

1.1 海量点云的八叉树划分与文件组织

规则的空间八叉树将点云数据所处的正方体包围盒进行规则的八等分，结点的收敛条件一般为点云的数量阈值或者最高深度阈值。经递归划分之后，中间结点仅作为过渡，没有存储点云数据，点云数据实际上保存在叶结点中。

结合数据的外存分块映射组织，本文提出的点云八叉树划分算法步骤如下：

算法描述：点云的八叉树划分及外存文件组织。算法输入：点云集合、八叉树的最大深度DepthMax、外存点云的根目录。

算法输出：基于八叉树的点云外存组织结构。

步骤1：计算点云集合的最小外包围盒大小，以包围盒最大边长为八叉树边长，以包围盒中心为八叉树中心，建立点云八叉树的最小正方体外包围盒，并在外存的根目录下保存外包围盒结构信息。

步骤2：如果八叉树深度小于DepthMax，将空间等分为8个子结点childi（i=0～7），并将该结点的点云分配到子结点中，进入步骤3；如果八叉树深度等于DepthMax，则停止划分，进入步骤4。

步骤3：遍历8个子结点，如果结点为空，则继续下一个子结点；如果不为空，创建新的文件夹，并命名为子结点编号i，保存结点的外包围盒信息，回到步骤2。

步骤4：将叶结点的点云数据以二进制格式保存。

步骤5：退出算法。

算法的流程如图2所示。

图2 点云的八叉树划分与外存组织

1.2 点云的多分辨率LOD建立

细节分层技术[9]（levels of details，简称LOD）为解决仿真效果与仿真实时性之间的矛盾提供了一种有效的解决方案，已在基于三维网格的实时绘制中得到广泛应用[10]。为解决海量点云数据实时显示的调度问题，在构建八叉树索引的基础上，本文利用随机采样的方法，以叶结点的点云为起点，采用深度遍历的顺序向上逐层采样，得到点云的八叉树多分辨率LOD数据，并保存在上一节所述的文件组织结构下，如图3所示。算法描述如下：

算法描述：点云的八叉树多分辨率LOD生成。

算法输入：点云随机采样率sample。

算法输出：各层次的多分辨率点云数据。

步骤1：将点云的根结点加入八叉树结点链表Vector中，如果链表末结点为空，则退出算法；否则进入步骤2。

步骤2：如果链表的末结点是八叉树结构的非叶子结点，进入步骤3；如果链表的最后结点是八叉树结构的叶子结点，进入步骤4。

步骤3：遍历本结点的8个子结点，将子结点加入链表结构，如果链表末结点不为空，回到步骤2；如果为空结点，将链表末结点删除。

图3 点云的多分辨率LOD建立与外存映射

步骤4：遍历链表中的所有非叶子结点，各层级采样率计算公式为SamoleRatio=samplesize(Vector)-Depthcurrent-1，其中size（Vector）表示链表中结点总数，DepthMax表示该层级的深度值。对叶结点按采样率进行随机采样，得到该层级非叶结点的点云，并将点云保存在该层级八叉树目录下，如果文件已经存在，则对点云进行合并操作。

2 基于视点的点云内外存调度绘制技术

内外存调度技术是指计算机需要处理的数据一部分放在内存中[11]，另一部分放在外部存储设备中，并通过I/O进行调度的技术。该技术是处理数据容量大于计算机内存时的常用技术。在建立八叉树索引结构下的多分辨率LOD点云数据的基础上，本文设计了一种基于视点的多分辨率点云内外存调度策略：将点云的八叉树结构保存在内存中，点云的多分辨率数据存储在外部存储设备中。当观察视点位于某一八叉树父结点外，八叉树外包围盒中心点到视点的距离小于阈值R1时，便从外存中加载该结点对应的多分辨率点云数据；当距离进一步减少且小于阈值R2时，遍历父结点下的子结点，当子结点的包围盒中心到视点的距离小于阈值r时，从外存中加载该子结点，反之则从内存中卸载该结点的点云数据。如图4所示，R表示某一八叉树结点半径大小。将点云根结点的LOD半径阈值设为无穷大，此时，一进入场景便可以观察到三维场景的整体情况。另外在使用OpenGL图形渲染语言绘制点云数据时，通过开辟另一线程来预先判断哪些多分辨率数据需要从外存中加载或者从内存中卸载，便可以在不影响绘制线程的前提下，提高内外存调度的效率，实现海量点云的流畅显示与调度。

图4 基于视点的多分辨率点云调度策略

3 实验与分析

本文的点云数据来源于无人机航拍的影像经过三维重建得到的稠密点云数据，点的数据组成包括三维坐标信息（经度、纬度和高程值）和颜色信息（RGB颜色值）。实验区域为城区中的校园，占地面积为1.25 km2；点的数量为219 367 498，文件大小为3.26 GB。计算机为普通PC，配置为Core i5 2.4 GHz、4 GB内存、750 GB硬盘，软件方面为Windows7 64位操作系统，VS2010 编译环境，OpenGL三维渲染语言。为了比较不同的八叉树深度值对八叉树构建、多分辨率LOD生成以及点云显示效果的影响，设计了两组实验进行比较分析。

实验一：海量点云的八叉树构建和多分辨率外存组织。八叉树深度值分别取3～8，多分辨率点云生成时随机采样率sample设为0.25，数据处理时各主要步骤耗时如表1所示。

表1 不同深度值下点云的八叉树划分与多分辨率点云生成的时间比较/s

可以看出，随着八叉树划分深度的增加，构建八叉树和生成点云的多分辨率数据结构的时间消耗近似呈现指数增长的趋势。

实验二： 基于视点的点云多分辨率内外存调度绘制。以实验一得到的不同八叉树深度值（选取深度值为3～6）的多分辨点云数据为显示实验的数据，视点调度的阈值R1设为4R，R2设为2R，r设为R（其中R为某一父结点的外包围盒半径值）。使用OpenGL三维渲染引擎的点图元为绘制单元，分别赋予其点的坐标信息和颜色信息。图5为4种不同数据在点云加载和视点漫游阶段，内存和硬盘读写随时间变化的情况，从左到右分别为八叉树深度值3到6的4种点云数据。

从4个图可以看出，点云在显示时，首先从硬盘上读取根结点层级上的多分辨率点云数据，当视点逐渐拉近时，从硬盘上加载或者卸载相应的多分辨率点云数据，导致内存使用产生波动；当八叉树最大深度较小时，各深度上的多分辨率点云数据相对较大，因此在内外存调度时内存波动幅度较大；反之，则内外存调度的波动幅度较小；另外，由于点云在显示时，需从外存的八叉树结构的文件中读取各层级的多分辨率数据结构，因此随着深度的增加，显示用时明显增加。图6为4种不同八叉树最大深度数据的显示效果图。当最大深度值小时，被加载的子结点点云较大，内存消耗相应增加；深度大时，需要加载的多分辨率结点较多，增加了CPU的调度负担。在三维点云中漫游时，4种测试数据均可以保证帧率在20～40之间，符合流畅显示的要求。

图5 不同深度值多分辨率点云显示的内存使用和内外存调度情况

图6 不同八叉树最大深度值下的海量点云显示效果

4 结 语

在普通计算机上，海量点云数据的流畅显示受到硬件设备的制约。本文将点云数据按照深度值进行八叉树划分，并将得到的数据结构组织在外存中，然后通过随机采样的方法由子结点向根结点构建多分辨率的点云数据，保存在相应的外存文件中，最后设计了一种基于视点的点云多分辨率调度策略，实现了海量点云的流畅显示。通过实验验证了不同的八叉树深度值对点云多分辨率结构生成的效率、内存调度和显示的影响，并在普通计算机上实现了数亿点云的流畅显示。

[1] PFISTER H, ZWICKER M, VAN BAAR J, et al. Surfels: Surface Elements as Rendering Primitives [C] //Proceedings of ACM SIGGRAPH 2000. New York: ACM Press, 2000

[2] RUSINKIEWICZ S, LEVOY M. QSplat: A Multiresolution Point Rending System for Large Meshes [C] //Proceeding of ACM SIGGRAPH 2000. New York: ACM Press,2000

[3] BOTSCH M, HORNUN A,ZWICKER M, et al. High-quality Surface Splatting on Today's Gpus [C] //Proceedings of the 2nd Eurographics / IEEE VGTC Symp. Point-Based Graphics, 2005

[4] 支晓栋, 林宗坚, 苏国中, 等. 基于改进四叉树的LiDAR点云数据组织研究[J]. 计算机工程与应用, 2010, 46(9): 71-74

[5] MA H, WANG Z. Distributed Data Organization and Parallel Data Retrieval Methods for Huge Scanner Point Clouds [J]. Computer&Geoscience, 2011, 37(1): 193-201

[6] 孟放, 査红彬. 基于LOD控制与内外存调度的大型三维点云数据绘制[J].计算机辅助设计与图形学学报, 2006, 18(1): 1-7

[7] 张毅, 吕秀琴. 大规模点云内外存调度绘制技术[J].计算机工程, 2014, 40(1): 49-54

[8] 邵正伟, 席平. 基于八叉树编码的点云数据精简方法[J].工程图学学报, 2010(4): 73-76

[9] HOPPE H. Smooth View-dependent Level-of-detail Control and Its Application to Terrain Rendering [C] // Proceedings of IEEE Visualization, Research Triangle Park, North Carolina, 1998

[10] 吴小东, 许捍卫. 基于OSGEarth的城市三维场景构建[J].地理空间信息, 2013, 11(2): 107-110

[11] CHIANG Y, El-SANA J, LINDSTROM P, et al. Out-of-core Algorithms for Scientific Visualization and Computer Graphic [C] //Proceedings of IEEE Visualization, Boston, 2002

P208

B

1672-4623（2016）10-0022-04

10.3969/j.issn.1672-4623.2016.10.006

杨振发，硕士研究生，主要研究方向为战场环境仿真。

2015-09-30。

项目来源：国家自然科学基金资助项目（41371384、41401465）；地理信息工程国家重点实验室资助项目（SKLGIE2014-2-4-1）。