面向地形构建的点云孔洞修补

武警工程大学研究生管理大队 柳方明 张洪彪 李俊利

面向地形构建的点云孔洞修补

武警工程大学研究生管理大队 柳方明 张洪彪 李俊利

由于三维激光扫描仪在获取点云数据时，受设备自身、环境、目标物表面结构等复杂因素影响，其获取的点云数据往往存在局部孔洞，这对精确重建地形带来了巨大的挑战。本文针对真实地形点云数据存在的孔洞，结合Delaunay三角剖分与Loop细分算法，解决了地形孔洞难以修补这一难题。该算法首先连接距离最近的两点，根据Delaunay三角形外接圆特性，以外接圆半径增长的方式搜索三角形第3点，构建种子三角形。随后对新生成边重复采用外接圆半径增长的方式构建新三角形，从而对所有散乱点云建立三角网拓扑结构，再以Loop细分的方式实现点云孔洞的修补，经算例验证，本文算法可用于实际地形孔洞修补。

三角剖分；Loop细分；孔洞修补

三维建模是计算机研究的热点之一，随着三维激光扫描仪的更新换代，三维激光扫描技术已经可以全天候、高效率、高精度的获取实体重建所需要的原始点云数据[1,2]。近年来，随着国内外学者对点云三维建模研究的不断深入，在取得不少科研成果的同时，点云三维建模技术也开始广泛应用于逆向工程、医疗、古文物重建、工业锻造、城市主体三维场景建模、地形侵蚀监测等多个领域[3-5]。在逆向工程中，高精度的三维建模可以缩短生产周期，并提高产品生产效率；在医疗领域里，高精度扫描的点云数据经建模后可进行脸部、牙齿、耳朵等的畸形矫正；在文物保护领域，对具有上千年历史的古文物的原型数字存储、复原中，三维激光扫描仪也有非接触、高精度等不可替代的优势。中华文化博大精深，古文物数不胜数，无数奇珍异宝，直接暴露在空气中展览，难免会对文物造成不可修复的损伤。实物重建后，利用3D打印技术，既起到保护文物的作用，亦可为游客展现中华瑰宝；而在城市规划中，三维激光扫描技术可以提供良好的数据保证。在对实际地形进行三维建模时，由于三维激光扫描仪在获取点云数据时，受设备自身、环境、目标物表面结构等复杂因素影响，其获取的点云数据往往存在局部孔洞。目前，由于点云数据处理难度大，技术门槛高，加之地形的不规则性，导致国内对地形孔洞修补的进程极度缓慢。而孔洞的存在严重影响了地形重建精度，本文结合Delaunay三角剖分与Loop细分，成功的的解决了这一难题，恢复了局部缺失的地形数据。

1 三角剖分算法

散乱点云的分布反映地形表面整体形态，对其三角剖分是构建数据点拓扑关系，实现地形重建，揭示地形表面形态特征的一个关键环节。三角剖分后，每个三角形单元都代表地形很小的一个部分，相互邻接的三角形网则整体反映地形表面模型。本文对Delaunay三角剖分算法研究，通过改进一种原有的三角形生长算法[6]，利用三角形外接圆半径增长的方式重新构建三角网格。

在Delaunay三角剖分一般有以下几个特点：

（1）建立的三角网格具有唯一性，散乱点集中任意四点不可能共圆；

（2）任意一个三角形的外接圆不包含其他任何顶点，且尽量保证形成的三角形周长最小；

（3）任何一个三角形的内角尽量保持均衡，接近等边三角形。

根据特点2，本文利用外接圆半径增长的方式搜索第3点。该算法的具体思路如下：在散乱点集中，任取一点S，在其余点中搜索距离S最近的一点R，连接SR，确定SR的中垂线EF，交SR于点P。由数学原理可知，SR的外接圆圆心必位于SR的中垂线上，随着圆心位置的变化，半径的增加，必然存在第3点A满足共圆条件且圆内部无其他顶点，即点A满足Delaunay三角形条件。

2 Loop细分

细分的方法适应于任意拓扑结构的曲面，并且不影响原始曲面形态。在对散乱点云三角剖分形成三角网格后，对部分大于三角形平均周长的三角形（下文称之为大三角形）进行Loop细分，细分后大三角形的每条边产生一个内部点，原本的大三角形的顶点也会生成新顶点而有微小的位移[7]。Loop细分的主要思想如下：

图1 新顶点生成规则

Loop细分完毕后，每个新生成的点与周围的点互相连接，形成新边，完成大三角形细分。大三角形Loop细分算法具体步骤如下：

STEP1：计算三角网格中三角形的平均周长，遍历三角网格，根据三角形周长与平均周长的相比结果，一般孔洞区域越大则选取的比例略大，本文选择的是对相比结果超过1.2倍的三角形进行细分；

STEP2：对需要细分的三角形，计算三角形每条边的新生成点，计算三角形三个顶点的新生成点；

STEP3：互相连接新生成点，组成新的三角网格，算法结束。

3 试验结果

以西安理工大学径流冲刷实验所获取的细沟点云数据为孔洞修补算例。如图2所示，地形中原有数据7000个点，孔洞修补后共12684个点，新增5684个点。为了便于观察孔洞修补效果，在Arcgis10.2软件中将地形数据中的孔洞标记出来。（a）为细沟的原始点云数据图，（b）为孔洞修补后导出的点云数据图。

图2 细沟孔洞修补

[1]贺岩,雷琳君,臧华国等．地基全视景三维成像激光扫描仪[J]．红外,2012(02):13-16．

[2]代世威．地面三维激光点云数据质量分析与评价[D]．西安:长安大学,2013．

[3]OHTAKE Y,BELYAEV A,SEIDEL H-P．A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions[C]．Shape Modeling International,2003．IEEE,2003:153-161．

[4]王茹．古建筑数字化及三维建模关键技术研究[D]．西安:西北大学,2010．

[5]张栋．基于LIDAR数据和航空影像的城市房屋三维重建[D]．武汉:武汉大学,2005．

[6]蒋红斐,涂鹏,李国忠．基于生长算法构建Delaunay三角网的研究[J]．公路交通科技,2004(12):38-41．

[7]LOOP C．Smooth subdivision surfaces based on triangles[D]．Utah:University of Utah,1987．