顾及自适应多细节层次的八叉树点云管理算法

张俊峰， 许德合， 王小东

（1．华北水利水电大学资源与环境学院，河南郑州450045；2．成都理工大学国土资源部地学空间信息技术重点实验室，四川成都610059）

顾及自适应多细节层次的八叉树点云管理算法

张俊峰1，2， 许德合1， 王小东1

（1．华北水利水电大学资源与环境学院，河南郑州450045；2．成都理工大学国土资源部地学空间信息技术重点实验室，四川成都610059）

为了解决大规模点云不易有效组织、动态可视化时冗余度大，且较难实现自适应显示的问题，提出顾及细节层次（levels of detail，LOD）的八叉树点云管理算法．该算法基于八叉树索引将扫描点限定在每个结点范围内，利用自上而下空间分割和自下而上参数计算相结合的预处理策略，减少实时阶段计算量，通过构建保守性模拟误差，使场景各处均可自动满足可视要求，并辅之以高效加速方法，实现了点云的有效组织和自适应流畅显示．实验研究表明，在优化的预处理和辅助加速策略支持下，与经典R树算法相比，该算法实时阶段计算量小，每帧自适应漫游平均时间在0．04 s以内．

点云；八叉树；模拟误差；可见性裁剪；细节层次

最新的激光扫描仪可动态获取厘米级精度的点云数据，前所未有的数据采集速度和精度对激光点云数据的有效组织和可视化提出了严峻考验［1］．在计算机图形学领域，针对大数据量，发展了多种相关的数据组织和快速调度技术，但多关注于单目标点云，不易进行复杂场景的有效管理和可视化．基于点云数据的海量性、栅格性、原始性和高精度性等特点，一种有效的处理策略是顾及细节层次（levels of detail，LOD）的数据组织和多分辨率显示［2-4］，但费时的预处理过程和不平衡的树深严重影响了其使用感受和细节查询效率．

在空间信息科学领域，目前适用于大规模点云的空间索引方法主要有规则格网、二叉树、四叉树、八叉树、R树等及其变种［5-9］，这些方法多基于单个点对象和空间目标的最小包围盒展开，其索引粒度较小，同样不适用于海量点云三维模型．另外，传统的点云LOD算法多采用静态模型，在实时显示时根据视距动态调用不同层次［10-11］，尽管简单，但切换过程中会出现明显视觉跳跃感以及模型分辨率在单一时刻处处相同，冗余度较大．

作者采用八叉树模型，提出一种顾及细节层次的点云管理算法．该算法对所有站点的点云数据进行自上而下的八叉树孤立分割，通过设定阈值将每个点约束在各个叶结点中，再自下而上重构各级结点，并计算结点误差；实时显示时，依据基于视点的保守性模型误差，可自适应地选择符合精度要求的结点绘制整个场景，并利用各种有针对性的辅助加速算法提高帧速．

1 算法设计

针对地面三维激光扫描仪所获取的多场景点云数据展开，算法总体上分为预处理和实时显示两部分，算法流程如图1所示．1．1节阐述点云数据组织、八叉树空间索引构建、细节层次模型设计和模拟误差计算属于预处理阶段；1．2节阐述实时显示的细节层次选择根据结点精度评价标准展开；1．3节阐述保守可见性判断和增量更新为辅助加速方法．

图1 算法流程Fig．1 Algorithm flow

1．1 细节层次模型构建和模拟误差计算

针对地面三维激光扫描仪获取的多场景点云数据，采用场景内八叉树分割、场景间R树索引根结点机制进行组织，精度判断则采用基于视点的模拟误差．对每个单场景，首先遍历其所有点获取最大和最小坐标（x，y，z），由此构成的最小包围盒作为根结点“0”，然后按照双队列模式进行八叉树自上而下的层次分割，并要求每个结点内的点数目大于或等于阈值ε，分割完成后，每层的最大结点数为8k－1（k＝1，2，…，l，l为当前层深）．为了减少存储量，每个非叶结点不需要存储其父结点和各个子结点指针，结点之间的层次关系可根据编号快速判断．

为了实现点云在三维空间中的多尺度表达，算法从分割得到的叶结点出发，向上追溯父结点，并从各子结点中按一定比例抽取部分点汇至父结点，以重构各结点，搭建细节层次模型．具体来说，自适应细节层次八叉树结点构建流程如下：

（1）构建数组L1和L2，将所有叶结点置入L2中．

（2）依次从L2中取出一个结点N，设其层深为c，包含的点数目为m．

（3）根据结点N的编号获取其父结点Np，检查L1中是否包含Np，如果包含，转（4）；否则将Np置入L1中，转（4）．

（4）从N中抽取m（c－1）／c个点作为父结点Np中的点，转（2）．

（5）L2遍历完成后，检查L1中的结点个数，若为1说明已遍历至根结点，退出；否则将L1中的结点置入L2中，清空L1，转（2）．

该过程完成后，每个非叶结点包含的点数目均占其所有子结点中点总数的（c－1）／c，如图2所示．图2中各层结点数目仅为示意，非真实八叉树分割，且层深越大，抽取比例越高，细节表达越详细．后续误差控制下的自适应多细节显示即为基于重构后的结点展开．

实时显示时，模拟误差是判断显示细节的重要指标，因此，当所有结点重构后，再按照自上而下的顺序计算该值以确定当前的表达精度．文中的模拟误差定义为采用当前结点与采用所有叶结点表达场景之间的起伏度差值．每个非叶结点的模拟误差en各不相同．

图2 八叉树结点细节层次构建Fig．2 LOD building of octree nodes

式中：er为原始场景的起伏度；

es为采用当前结点表达场景的起伏度．

式中：Zi为当前结点内的扫描点的高程值；

¯Z为对应叶结点中所有扫描点的平均高程值；

n为当前结点内的点数目．

式中：Zij为当前结点对应的叶结点中扫描点的高程值；

p为对应的叶结点数目；

q为每个叶结点中扫描点的数目．

由于当前结点不一定处于叶结点的上一层次，因此，p≥8，其值由8（s－c）确定，s为树的总深度，c为当前结点层深．

实时漫游时，若利用较高层次结点，因其包含的扫描点较少，模拟误差较大．随着分割层次的加深，（c－1）／c逐渐增大，结点中包含的扫描点也就越多，表达精度相应提高，直到采用叶结点时模拟误差为0，因此，可以看出，模拟误差单调递减，具有保守性．

1．2 结点精度评价标准

场景自适应显示时，需要一个评价标准以确定结点是否需要继续分割，从3个方面进行考虑：

（1）当前结点的模拟误差；

（2）视点到结点中心的距离；

（3）结点所覆盖场景的大小．

通常来说，距离视点越近，表达越精细，场景覆盖范围越大，需要表达的细节越多，同时，可视误差应控制在一定范围内．精度评价标准可由式（4）计算：

式中：l为结点边长平均值；

d为视距；

λ为精度控制因子．

在预处理中获得l和en．据式（4）可知，在λ一定的情况下，当前结点覆盖面积越广，模拟误差越大，距视点越近，越需要继续分割以提高显示细节，同时，λ越小，要求的显示精度越高．

实时显示时，每帧按广度优先原则自上而下逐层判断每个可见结点是否达到显示精度，如满足式（4），将其包含的所有点交给GPU渲染，否则将其8个子结点置于待判断集合，等待下一层次的精度评价，直至叶结点．另外，独立进行每个结点的精度判断，其分割层次不受相邻结点分割情况的影响，因此场景各区域均可自适应地满足可视要求．

1．3 自适应表达的辅助加速算法

点云数据量往往很大，少则数万，多则几百万，甚至上千万，因此，必须考虑海量数据与常规计算机处理能力有限的矛盾．结合八叉树结点构建方法，提出一系列与之相关的辅助加速算法．

（1）八叉树结点的保守可见性判断

在某具体时刻，视点可见区域是有限的，因此不在该范围内的数据不需要调入内存或渲染．文中利用结点外接球和视锥体的空间关系进行可见性判断，且由于八叉树结点具有良好的层次结构，可确保判断的保守性．具体来说，若将某结点外接球和视锥体沿视线方向剖开，二者空间关系如图3所示．

图3中，E为当前视点所在位置，AB和CD分别为前后裁剪线，α为垂直视角大小，Ld和Lf为视点E距前后裁剪线的距离，圆O为某结点N外接球的剖面圆，r为半径，β等于视角α的1／2，Le为圆心到视点E的距离，n为视线方向的单位向量．根据空间关系，结点可见的充分必要条件是圆O被梯形ABDC包含或二者相交，可从水平和垂直方向分别考虑二者的关系．

图3 结点外接球和视锥体的空间关系Fig．3 The spatial relationship between node circumscribed sphere and view frustum

从结点N的外接球剖面圆中心到视点E的水平方向考虑．SEO为E到O的矢量，由几何原理知

因此圆O被视锥体包含或二者相交的第1个必要条件是

若不能满足式（5），说明当前结点不可见，其包含的所有子结点也不可见．

从垂直方向考虑，可得

因此圆O被视锥体包含或二者相交的第2个必要条件是

若同时满足式（5）和（6），说明当前结点N可见，若满足但未达到精度要求，还需进一步判断其各个子结点的可见性．

利用结点外接球和视锥体的空间关系进行可见性判断非常简单，且Ld、Lf和r均在预处理中提前计算，不会增加实时阶段工作量．该算法极大减轻了传统方法中根据6个裁剪面进行可见性判断的巨大计算量［12］，且精度较高，可见结点的冗余度很低．另外，该方法也适用于场景自身可见性的判断，从而可在整体上保证场景结构的完整性．

（2）视域拓展的多线程增量更新

实时显示时，内外存将频繁交互数据，因此需要设置合理的调度策略，使预可见数据尽可能地常驻内存，并卸载长期不用或远离视点的数据［13-15］．基于此，提出基于视域拓展的多线程增量更新算法．可视区域和扩展区域如图4所示，设各场景所覆盖范围的长宽平均值为w，E为某时刻视点位置，α为垂直视角，AB为后裁剪面所在位置，则视锥体在平面上的剖面为EAB，将与此相交或在其内的场景定义为可见区域．

为了减少内外存交互，采用“后撤视点，前移裁剪面，扩大视角”的策略，将视点E沿视线反方向移动距离w至E′，并将后裁剪面AB沿视线方向移动距离w至A′B′，同时扩大垂直视角α至β，从而构建一个拓展区域E′A′B′．此时，将与E′A′B′相交或被包含而又不属于可见区域的场景定义为扩展区域，该区域包含当前可见范围的各个方向，因此，无论视点如何移动，通过可见区域和扩展区域的有限切换，均可保证显示的流畅性．

细节层次简化主线程和数据块调度子线程通过视域切换实现同步．在初始阶段，主线程根据视点和可视参数载入所需数据块，然后确定每个结点的可见性，并将符合精度要求的结点交给GPU进行渲染．当视点切换时，主线程还需预测下一帧的可见数据，若不在内存中，将其编号按照优先顺序置入待加载队列．数据调度子线程依据加载队列中的编号依次载入数据，并按照最近最常使用原则卸载无用数据．在整个漫游过程中，可见区域和扩展区域动态切换，相邻帧间的缓慢过渡决定了数据块调度是增量更新的，因此瞬时载入量非常有限．

图4 可视区域和扩展区域Fig．4 The visible area and extended area

2 实验与分析

为了验证算法的有效性，作者在笔记本电脑上采用OpenGL API实现了该算法．算法实现的硬件条件是Inter Core i5-2430U处理器，2 GB内存，NVIDIA NVS 4200M显卡．

实验1 不同精度控制因子下的点云自适应LOD表达

精度控制因子λ决定了三维表达的速度和逼真度，λ越小，精度要求越高，绘制的扫描点越多．作者基于已有的包含77 874个扫描点的单场景，通过设置不同的控制因子，得到对应的自适应表达结果，如图5所示．

表1为运行参数对比．从表1可以看出，随着λ的减小，绘制的点数目越来越多，说明表达精度不断提高，更多区域需要细分到叶结点才能达到精度要求，但自适应LOD可确保每帧绘制的点数据量有限，能够保证场景的流畅漫游，这从单帧运行时间可以看出．

另外，需要注意的是，尽管较小λ可获得更高的表达精度，但这是以运行效率为代价的，因此，选择合适的控制因子也是非常必要的．

实验2 大规模点云的自适应LOD表达

实验采用包含6 672 962个扫描点的多场景点云数据，利用八叉树空间分割和保守可见性判断、增量更新等加速算法，实现了自适应LOD表达，如图6所示．图6中的第1、2和3帧并非漫游时的连续帧，而是为了更好体现算法效果而选择的独立帧．

表2为相关运行参数．在运行初始阶段需要一次性载入当前视点参数下可见的较多数据，因此第1帧等待时间较长，不过，由于连续帧间具有较大重叠，因此后续各帧只需调入少量数据，并适时切换可见区域和扩展区域即可．另外，对每帧来说，视域裁剪不但可以快速确定每一场景的可见性，也可判断场景内每一结点的保守可见性，以最大限度地减少实时绘制量，因此，每帧绘制的点数目仅占原始数据的很少一部分，每帧的自适应漫游平均时间可维持在0．04 s以内．

图5 不同控制因子下的点云自适应表达Fig．5 Adaptive expression of point-cloud data under different control factors

表1 不同控制因子下的点云自适应表达参数Tab．1 Parameters of adaptive expression of point-cloud data under different control factors

图6 大规模点云自适应表达Fig．6 Adaptive expression of large-scale point-cloud data

表2 大规模点云自适应表达参数Tab．2 Parameters of adaptive expression of large-scale point-cloud data

3 结 论

采用八叉树空间索引，结合有针对性的数据组织和加速策略，实现了大规模点云的多细节流畅显示，解决了传统方法中不易管理海量数据，且较难实现自适应表达的问题，得到以下主要结论：

（1）利用八叉树高效的数据索引结构，结合自上而下分割和自下而上计算的预处理策略构建结点的细节层次，可实现点云自适应多分辨率表达．

（2）保守可见性判断和增量更新方法简单高效，使内存占用率很低，且交互量很少，极大压缩了实时阶段绘制量．

（3）结合八叉树结点细节层次模型和辅助加速算法，实时阶段计算量和数据冗余度都很小，能够满足大规模点云的自适应流畅显示，每帧的自适应平均漫游时间可维持在0．04 s以内．

［1］ 李德仁．论地球空间信息的三维可视化：基于图形还是基于影像［J］．测绘学报，2010，39（2）：111-114．LI Deren．3D visualization of geospatial information：graphics based or imagery based［J］．Acta Geodaeticaet Cartographica Sinic，2010，39（2）：111-114．

［2］ 张帆，黄先锋，李德仁．基于球面投影的单站地面激光扫描点云构网方法［J］．测绘学报，2009，38（1）：48-54．ZHANG Fan，HUANG Xianfeng，LI Deren．Spherical projection based triangulation for one station terrestrial laser scanning point cloud［J］．Acta Geodaetica et Cartographica Sinica，2009，38（1）：48-54．

［3］ 张俊峰，姚志宏．基于四叉树孤立分割和屏幕误差的地形LOD算法［J］．西南交通大学学报，2013，48（4）：666-671．ZHANG Junfeng，YAO Zhihong．LOD algorithm of terrain based on conservative screen error and isolated division of quad-tree［J］．Journal of Southwest Jiaotong University，2013，48（4）：666-671．

［4］ MANDOW A，MARTINEZ J L，REINA A，et al．Fast range-independent spherical subsampling of 3D laser scanner points and data reduction performance evaluation for scene registration［J］．Pattern Recognition Letters，2010，31（11）：1239-1250．

［5］ 郑坤，朱良峰，吴信才，等．三维GIS空间索引技术研究［J］．地理与地理信息科学，2006，22（4）：35-39．ZHENG Kun，ZHU Liangfeng，WU Xincai，et al．Study on spatial indexing techniques for 3D GIS［J］．Geography and Geo-information Science，2006，22（4）：35-39．

［6］ 史文中，吴立新，李清泉，等．三维空间信息系统模型与算法［M］．北京：电子工业出版社，2007：216-218．

［7］ ZHU Qing，GONG Jun，ZHANG Yeting．An efficient 3D R-tree spatial index method for virtual geographic environment［J］．ISPRS Journal of Photogrammetry＆Remote Sensing，2007，62（3）：217-224．

［8］ 龚俊，朱庆，张叶廷，等．顾及多细节层次的三维R-索引扩展方法［J］．测绘学报，2014，40（2）：249-255．GONG Jun，ZHU Qing，ZHANG Yeting，et al．An efficient 3D R-tree extension method concerned with levels of detail［J］．Acta Geodaetica et Cartographica Sinica，2011，40（2）：249-255．

［9］ 龚俊，朱庆，章汉武，等．基于R树索引的三维场景细节层次自适应控制方法［J］．测绘学报，2011，40（4）：531-534．GONG Jun，ZHU Qing，ZHANG Hanwu，et al．An adaptive control method of LODs for 3D scene based on R-tree index［J］．Acta Geodaetica et Cartographica Sinica，2011，40（4）：531-534．

［10］ PFFIFFR N．A subdivision algorithm for smooth 3D terrain models［J］．ISPRS Journal of Photogrammetry＆Remote Sensing，2005，59（3）：115-127．

［11］ RENATO P．Fastmesh：efficient view-dependent meshing［C］∥Proceedings of 2001 International Conference on Computer Graphics＆Applications．Washington D C：IEEE Computer Society，2001：22-30．

［12］ 李清泉，杨必胜，史文中，等．三维空间数据的实时获取、建模与可视化［M］．武汉：武汉大学出版社，2003：198-204．

［13］ LIU R，PFISTER H，ZWICKER M．Object space EWA surface splatting：a hardware accelerated approach to high quality point rendering［J］．Computer Graphics Forum，2002，21（3）：461-470．

［14］ MA Hongchao，WANG Zongyue．Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds［J］．Computers＆Geosciences，2011，37（2）：193-201．

［15］ WAND M，BERNER A，BOKELOH M，et al．Processing and interactive editing of huge point clouds from 3D scanners［J］．Computers＆Graphics，2008，32（2）：204-220．

（中文编辑：秦萍玲 英文编辑：兰俊思）

Management Algorithm of Point-Cloud Data Based on Octree Concerned with Adaptive Levels of Detail

ZHANG Junfeng1，2， XU Dehe1， WANG Xiaodong1
（1．School of Resource and Environment，North China University of Water Resources and Electric Power，Zhengzhou 450045，China；2．Key Laboratory of Geo-special Information Technology，Ministry of Land and Resources，Chengdu University of Technology，Chengdu 610059，China）

Large-scale point-cloud data are not easy to organize effectively and have great redundancy at dynamic visualization，and it is hard to realize the adaptive display．Aiming at these problems，a new algorithm concerned with the levels of detail（LOD）of point-cloud expression on the basis of octree structure was proposed．The algorithm assigned every scanning point into an octree node，and integrated top-down division with down-top calculation as the pretreatment strategy to reduce the amount of real-time calculation．Then it made any region meet the accuracy requirement and display speed automatically by building conservative simulation-error evaluation criteria．Furthermore，with the help of acceleration methods，large-scale point-cloud data could be organized effectively and expressed smoothly with little data redundancy．Preliminary experiments show that the algorithm has abilities to overcome the shortcoming of the classical R-tree methods；meanwhile，with the support of optimized pretreatment and assistant acceleration methods，the amount of real-time calculation is small and the time of each frame can hold within 0．04 s easily．

point cloud；octree；simulation error；visibility culling；levels of detail

P208

A

0258-2724（2016）01-0078-07

10．3969／j．issn．0258-2724．2016．01．012

2014-08-19

国土资源部地学空间信息技术重点实验室开放基金（KLGSIT2014-02）；河南省教育厅科学技术研究重点项目（14A420001）；地理信息工程国家测绘地理信息局重点实验室开放基金（201318）

张俊峰（1982—），男，讲师，博士，研究方向为地理信息智能化处理与可视化，电话：13673355837，E-mail：zh-junfeng＠163．com

张俊峰，许德合，王小东．顾及自适应多细节层次的八叉树点云管理算法［J］．西南交通大学学报，2016，51（1）：78-84．