基于四叉树的大规模点云管理及实时渲染

张东升，李国柱，马 波

（1. 昆明市测绘研究院，云南 昆明 650051；2. 昆明理工大学 国土资源工程学院，云南 昆明 650093）

基于四叉树的大规模点云管理及实时渲染

张东升1,2，李国柱1,2，马 波1

（1. 昆明市测绘研究院，云南 昆明 650051；2. 昆明理工大学 国土资源工程学院，云南 昆明 650093）

三维激光扫描仪能够获取非常详尽的信息，但扫描仪的随机软件多数只能控制设备和数据显示，缺乏足够的点云后处理和空间分析功能。设计了一种基于四叉树的大规模点云管理算法，使用四叉树来对点云进行管理，以期对大规模点云进行高效管理并进行实时渲染。

大规模点云；四叉树；点云渲染；空间数据结构

三维激光扫描仪能够快速地获取测站周围一定距离内的高密度点云数据，现已广泛应用于城市规划、文物保护和测绘工程等领域。高密度点云中所包含的信息非常详尽，但其数据是基于点的，而常规工作中的分析方法大多都是基于面的，且计算机图形学中的可视剔除、背面消隐和光照处理也都是基于面片的。另外，空间点云数据中各点间不存在显式的拓扑关系，所以从对点云进行显示渲染到简单的体积计算，再到复杂的空间分析都需要开发专门的算法。因此，利用传统的数据处理软件对空间点云数据进行处理耗时太长。

本文以大规模点云为研究对象，实现了一种基于四叉树的大规模点云管理算法。在此基础上又特别研究了点云的细节层次（LOD），旨在实现随视点移动点云自动精简显示，以达到对点云进行实时渲染的目的，为之后开发生产和工作中所需的各种分析处理工具作准备。

1 数据结构及LOD计算

对于给定的点云，如果覆盖范围较小，则可将其坐标投影到一个水平面上，不用考虑地球曲率的影响；如果覆盖范围很广，则可以地球椭球为参考对象，对空间球面进行格网剖分，直至每个子格网可视为平面为止。

对于三维激光点云而言，每个点都包含三维坐标。点云的存储管理有多种数据结构可供选择，如KD树、四叉树和八叉树等。KD树是一种二叉树结构，特殊之处在于每一层都有个选择子，在对点云数据执行插入操作时，根据每一层的选择子选择遍历前进的分支，每次只针对一个属性进行比较。使用KD树管理点云数据具有很多优势，但可视剔除和关于LOD的计算会显得比较复杂。四叉树是一种典型的空间划分结构。八叉树在理论上相较于四叉树，对空间的划分更为均匀，因其可充分考虑空间的3个维度。

从扇入扇出的角度来观察，KD树的扇出是最小的，八叉树的扇出最大，四叉树则居中。扇出意味着，树形结构每向下扩充一层，会有更多的子节点产生。从另一个层面上来看，无论采用何种数据结构，都旨在能够实现数据的快速筛选或剔除。以三维可视化中的视景体裁剪为例，这3种数据结构的效率都非常高。当视点距离点云较远时，这些点云会逐渐融合在一起；当远到一定程度时，会在视觉上表现为一个点，这种现象可以使用LOD来模拟。四叉树和八叉树是很容易实现的，而KD树在LOD实现上需要采用很多技巧。在对大规模点云进行实时渲染时，随着当前视点位置的不同，在视点范围内的点云数量或多或少。例如，以俯视角度浏览点云全景时，视点范围包含了全部的点云；当视点位于点云内部时，则只会看到部分点云。实际上，在对点云进行实时渲染显示时，完全没有必要对全部点云进行处理；如果只对点云中的可视部分进行处理，则可极大提高速度。并且当视点以宏观俯视的角度观察点云时，虽然全部点云位于视点范围当中，但由于视点较远，对于场景的细节信息查看得不是很明显。另外，在四叉树的内部节点上可存放子点云的合并信息，所以使用四叉树是非常有利于控制被处理的点云规模和细节信息的。

综合考虑LOD、扇入扇出和空间划分等因素后，选择四叉树为存储激光点云的数据结构，用于存储本文所研究的大规模点云。本文以空间点云所在的空间为对象，对其进行四叉划分，构建四叉树，最终在叶节点中存放该空间中所包含的点云。

图1为一区域的四叉划分及其树形结构，不难看出，四叉树的检索效率较高，实现点的快速定位时，从根节点开始，每次可以剔除约3/4的数据，从而可借助该结构实现数据块的大规模剔除。本文所实现的算法中，点云数据存放在叶节点中，中间节点存放LOD信息。

图1 一个简单的空间四叉划分及其对应的四叉树

图2为使用视景体进行可视剔除的示意图。在构建好四叉树后，使用视景体进行可视剔除其实就是个简单的几何问题，从根节点开始递归向下遍历，判断是否在当前视景体中，如果在，则对子节点进行进一步的遍历；如果不在，则直接返回，直至达到叶节点位置。不难发现，当视点远离点云时，在视觉效果上距离相近的点会逐渐融合在一起，如果能够进一步对该现象进行模拟，则可使每帧中被处理的数据量稳定在一个特定的水平上，这种现象可以通过LOD技术来模拟。

图2 基于视景体的可视剔除

叶节点中包含了具体的点云数据，同时叶节点和中间节点中也设置了相应的域用于存放该范围内点集所对应的LOD信息。本算法所采用的方法是对于叶节点而言，设该叶节点中包含n个点，其中第i个点的信息为（xi，yi，hi，ri，gi，bi）。（xi，yi，hi）为点的坐标信息；（ri，gi，bi）为该点的色彩属性，对于某些类型的设备或通过算法处理的点云数据，还可能包括法线矢量属性。LOD（xleaf，yleaf，hleaf，rleaf，gleaf，bleaf）各分量的计算公式为：

中间节点的LOD（xmid，ymid，hmid，rmid，gmid，bmid）则取子节点LOD信息的数学均值，即

需要特别说明的是，只有在理想情况下，中间点节才包含4个子节点，很多情况下都不一定包括4个子节点。在这种情况时，m为实际的子节点数目。这些LOD信息可在数据插入四叉树之后，通过递归逆向计算得到。

图3为某一子区域中点的LOD计算示意图，其中红色点为其余点通过上述公式所计算出的虚拟点。当该子区域在视平面上的投影小于一定阀值时，便可直接使用该虚拟点代表该区域中的点集，而不影响视觉效果。通过这种方法可更进一步减少数据量。

图3 LOD计算示意图

2 算法实现

算法实现的基础是四叉树节点的数据结构，本文所采用的基础结构如表1、2所示，其中表1为单个点的信息结构，表2为四叉树节点的结构。在此结构体基础上，实现了相应的操作函数，如表3所示。

表1 PC_POINT结构

表2 QUAD_TREE_NODE结构

表3 四叉树的操作函数

表1中结构的信息域是自解释的，其中除了包含点的三维坐标外，还包括点的法线和颜色信息。表2中包含了丰富的信息，其中flag为标记变量，用来标识当前节点是叶子节点还是中间节点；cur_node_info变量是PC_POINT类型的变量，在四叉树的插入完成后，通过遍历四叉树，逆向计算每个节点的LOD信息，用于显示时实现数据的快速渲染；pt_list是指针，指向一 个动态申请的数组，用于存放该叶子节点包含的具体点云数据。其余的坐标范围数据只是用于标识每个矩形区域的范围，在视景体进行可视测试时，辅助实现数据的快速剔除。

3 实例分析

图4为笔者于2014年在昆明理工大学1号楼国土资源工程学院前侧扫描得到的一站激光点云数据，使用了Leica的三维激光扫描仪，其中包含点数近200万。图5和图6为笔者使用立体相对处理算法对云南某山区的无人机航片进行处理得到的点云数据，点云数量也是百万级。

本文利用图4、图5和图6的数据对算法进行了验证，在系统中漫游时，频率可达60帧/s以上。在实时计算机图形学中，渲染是按帧数进行的，即每秒显示器刷新的次数。由于视点位置不同，处理的点云规模可大可小，在规模较小时需处理的数据量较少；反之，需要处理的数据量则较大。因此，视点不同会导致交互漫游时出现忽快忽慢的闪烁效果。为了能够使系统在处理不同级别的数据时保持稳定，算法对帧频进行了锁定，稳定在60帧/s的水平上（与现今主流液晶显示器的刷新频率保持一致）。

图4 针对建筑物扫描的点云数据

图5 某山区的点云

图6 某农村区域的点云渲染效果

4 结 语

本文主要研究了使用四叉树实现大规模点云数据的管理，并建立了相应的LOD，用以辅助减少渲染时的数据量。在完成四叉树的建树及数据的载入后，通过视景体对不可见数据进行快速剔除，根据视点的远近，进一步利用LOD技术实现数据量的控制，将渲染的数据稳定在了一定的水平线上。最后采用实例对文中的算法进行了测试，效果达到了预期目标，下一步可研究具体的建模算法和分析工具，以便于解决生产实践中的具体问题。

[1] 惠文华,郭新城．三维GIS中的八叉树空间索引研究[J]．测绘通报,2003(1)∶25-27

[2] 黄先锋,陶闯,江万寿,等．机载激光雷达点云数据的实时渲染[J]．武汉大学学报(信息科学版),2005,30(11)∶975-978

[3] 徐景中,万幼川,张圣望．LiDAR地面点云的简化方法研究[J]．测绘信息与工程,2008,33(1)∶32-34

[4] 程效军,李伟英,张小虎．基于自适应八叉树的点云数据压缩方法研究[J]．河南科学,2010,28(10)∶1 300-1 305

[5] 李娜,马一薇,杨洋,等．利用RANSAC算法对建筑物立面进行点云分割[J]．测绘科学,2011,36(5)∶144-145

[6] 李必军,方志祥,任娟．从激光扫描数据中进行建筑物特征提取研究[J]．武汉大学学报(信息科学版),2003,28(1)∶65-70

[7] 郑顺义,苏国中,张祖勋．三维点集的自动表面重构算法[J]．武汉大学学报(信息科学版),2005,30(2)∶154-157

[8] 李长春,何荣,王宝山．LOD在大范围复杂场景简化中的应用[J]．河南理工大学学报(自然科学版),2007,26(2)∶181-184

P228

B

1672-4623（2016）09-0032-03

10.3969/j.issn.1672-4623.2016.09.010

张东升，硕士，工程师，研究方向为三维激光扫描。

2015-06-01。

项目来源：住房和城乡建设部科技示范资助项目（S52014016）。