点云网格重建方法的概述

扫描点云三角网格重建问题最早由Boissonnat在20世纪80年代提出，他对扫描点云网格重建问题做出了开创性的工作。之后，Hoppe利用点到物体表面的距离场构造的零等值面来进行点云网格重建。Hoppe的研究结果促使大批学者开始研究散乱点云的网格重建问题，点云网格三维重建开始成为计算机图形学中一个重要的研究领域。

（1）基于Delaunay三角剖分的网格重建方法

该方法主要应用Delaunay三角剖分对点云进行三角网格化，其主要思想是对每个采样点在各个方向探索所有邻域，寻找可能的邻近点来计算曲面。

1977年，Lawson采用逐点插入法实现对散乱点云的三角网格化，其基本原理为：首先建立一个大的三角形或多边形，把所有数据点包围起来，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，通过交换对角线的方法来保证所形成的三角网是Delaunay三角网。

同时，他在研究中发现凡是符合最大内角最小化原则的三角剖分都是局部均匀的。Sibon证明了基于Delaunay的三角剖分是唯一符合最大内角最小化原则的三角剖分。Green和Sibon实现了二维空间的Voronoi图的计算及Delaunay三角化。

Delaunay三角剖分的结果是一个三角形或四面体的凸包，与原物体表面相比有许多多余的三角形或四面体。Boissonnat采用层层剥离的方法，可视化物体表面的散乱数据点。Edelsbrunner则采用α-shape方法，设置参数α，将包围球或外接圆半径大于α的四面体、三角形和边都删除。后来，Bajaj基于α-shape方法生成了C1连续的散乱数据点的插值曲面。

1998年，Amenta等人提出Crust算法，之后又提出了改进的Power Crust算法，该算法能够不依赖于采样点的浓度和分布输出网格曲面。Dey等人提出了Power Crust的扩展算法，使点位于大Delaunay球内部，点的Delaunay三角形被约束到大Delaunay球的边界。

采用基于Delaunay的三角剖分方法构建的曲面网格拓扑正确，随着采样密度的增大，曲面网格最终收敛于真实的被测曲面，同时克服了人为划分散乱数据区域所带来的操作繁琐和低可靠性。但是该方法计算量大、内存占用高，对于大数据的点云以及存在噪声等特征数据的处理存在一定的局限性。

（2）基于区域增长的方法

该方法的基本原理是：从一个种子三角形开始，遵循一定区域增长规则，选择新点进入区域生成新的三角形并更新边界。遍历所有点，通过初始剖分优化获得被测物体表面的三角网格。其关键是选择新点的约束规则的制定。(www.xing528.com)

Boissonnat以三角形张角最大作为区域增长规则最先应用该方法完成散乱点云的三角剖分。

Choi基于以下假设设置区域增长规则：存在某个三维点C，由该点可看到被测面上所有散乱点，并可定义以C为锥顶的凸锥，使之包含所有散乱点。初始三角剖分后，以最小内角最大化和光顺性原则来优化网格。该算法可直接处理凸封闭曲面和开曲面，但由于受凸锥顶角的角度限制，所建曲面网格可能存在不稳定区域。

Mencl引入图论思想，利用曲面描述图（Surface Description Graph，SDG）来定义曲面轮廓，并用三角形来填充SDG获取网格。此法能根据点的密度变化进行自适应调整，可重建具有边界的曲面，对不连续曲面、采样密度变化剧烈等的重建可靠性较高。

基于区域增长的方法对大数据点云的处理有一定优势，但由于需人为对数据点云预先进行区域划分，降低了自动化程度，并且对于噪声处理的能力比较有限。

（3）隐式曲面拟合的方法

该方法使用隐式函数曲面拟合点云数据，并在零等值面上提取三角形网格。隐式函数通常为径向基函数或多项式函数，而提取三角形网格的方法，主要以Marching Cube和Bloome多边形化这两种方法为代表。

在隐式曲面构造中，使用最多的是径向基函数RBF（Radial Basis Functions），它是几何数据分析、模式识别、神经网络的标准工具。此外二次多项式隐函数也有较多的应用。

Floatef使用分层结构的紧支撑径向基函数，首先使用Delaunay三角剖分计算数据子集的嵌套序列，每层基函数的尺度由来自三角化信息的当前层的点云浓度所决定。这个方法大大提高了传统径向基函数插值逼近散乱点的效率。

隐式曲面拟合的方法具有可自动融合成光滑曲面的重要特性，连续性和变形性好，适于描述具有光滑复杂外形的物体，虽然难以进行实时绘制，但是在降低噪音、过滤离群点、编辑曲面等方面具有较大的优越性。