1、基于点云的几何表面重构方法研究摘 要三维扫描技术与获取技术的不断发展，使得三维几何造型技术广泛地应用在计算机辅助设计，计算机辅助制造，逆向工程等多个领域。获取海量的三维点云数据信息成为了现实，但拥有大规模点云信息的三维几何模型的构造和处理给计算机的处理能力带来了极大地挑战，于是如何快速、有效、可靠地实现对点云数据的几何表面重构成为了计算机图形学研究的重点和热点问题之一。本文针对传统的三角网格生长法进行点云数据表面模型重构时，搜索第三点耗时太长，导致重构效率很低的问题，采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域，在每个子域内进行三角网格重构，避免了网格拼接的过程；采用最大角最小化原则
2、进行三角网格优化；并运用三角面片定向的方法进行网格法向量一致化处理。该方法很大地（几十倍，上百倍）提高了表面模型重构的效率，形成的网格能够较好地体现模型的细节特征。本研究主要采用空间划分算法和三角网格生长算法探讨表面模型重构的关键技术，主要完成以下工作：（1）采用基于径向基函数的隐式曲面重构方法对点云模型进行曲面重构。采用八叉树分割算法法对给定点云数据进行空间划分，针对每个分割形成的子区域内的点，构建一个基于径向基函数的隐式函数对其进行拟合重构。（2）采用了自适应八叉树空间划分算法，依据点云数据密度的不同，将点云数据分割成均匀的相互有覆盖的较小的子区域。在每个子区域内对点云数据进行分别处理，大
3、大提高了计算效率。（3）采用了三角网格生长算法对点云模型进行表面重构，分析研究了三角网格剖分的三种算法（逐点插入算法、分治算法和三角网格生长算法）的优缺点，最后确定了三角网生长法进行模型重构，通过设定一些限定条件，构成正则度较高的三角网格。采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域，在每个子域内进行三角网格剖分。实验结果表明，该方法几十倍甚至上百倍的提高了表面模型重构的效率，形成的网格质量也很好，能够较好地体现模型的细节特征，鲁棒性较好。关键词：表面重构；三角网格生长算法；隐式曲面；空间划分；点云 目 录第一章 绪论.11.1 研究背景与意义.11.2 国内外研究现状.11.2.1
4、 基于 Delaunay 的三角网格剖分 .21.2.2 基于隐式曲面的模型重构方法 .41.2.3 基于学习的曲面重构 .51.2.4 网格孔洞修补算法 .61.3 研究内容.71.4 论文结构组织.8第二章 基于径向基函数的隐式曲面重构技术.92.1 隐式曲面模型的描述.92.2 空间划分.102.3 局部形状函数估计.102.4 实验结果与分析.112.5 本章小结.13第三章 三角网格剖分算法.143.1 Delaunay 三角剖分 .143.1.1 Delaunay 三角剖分定义 .143.1.2 局部最优化处理 .153.2 逐点插入法.163.3 分治方法.173.4 三角网格生
5、长法.183.5 本章小结.20第四章 自适应八叉树空间划分方法.214.1 八叉树.214.1.1 八叉树定义 .214.1.2 八叉树实现原理 .214.1.3 八叉树的存储结构 .224.2 空间划分.224.3 自适应八叉树分割求 k 近邻结果 .244.3.1 k 近邻 .244.3.2 八叉树分割法求 k 近邻 .244.4 网格优化方法.274.5 本章小结.29第五章 实验结果与分析.305.1 实验结果.305.2 本章小结.37第六章 总结与展望.386.1 总结.386.2 展望.38参考文献.39致 谢.43作者简介.44第一章 绪论 1第一章 绪论1.1 研究背景与意
6、义所谓点云，就是指大量的数据点聚集在一起形成的一个集合，这些数据点可以由三维扫描获取，也可以通过计算机随机生成，通常这些点会包含坐标、法向量等信息。点云几何表面重构，是指通过对散乱点云数据进行拓扑连接形成一定的几何网格形状（如三角形网格、四面体网格等）来表示点云数据的原始模型。表面重构是几何造型中的一个重要问题。近年来，由于激光扫描技术的发展和在工程设计，产品设计，医疗家电设计和考古学等领域的广泛应用，表面重构技术受到越来越多的关注。随着科学技术的飞速发展，逆向工程技术也有着越来越广泛的应用，如汽车制造、医疗保健、考古研究等领域。通常，逆向工程可以分为数据点采样，数据点预处理，三维模型重构，以
7、及模型的后处理等几个方面。数据点采样，就是指采用三维扫描、计算机随机生成等方法，获得采样点数据（即点云）的过程；数据点预处理，是指在对采样点数据进行模型重构之前，对采样的数据点进行排序、归一化等一系列处理的过程；三维模型重构，是指运用隐式曲面重构、几何表面重构等三维重构算法对采样点进行拟合、逼近，还原采样点的原始形状；后处理，则是对重构形成的模型进行一系列的优化处理，使重构结果更加完善。在整个处理流程中，三维模型重构对整个逆向工程系统起着至关重要的作用，因此也是研究的重点和热点。计算机图形学技术的迅速发展和三维扫描设备的不断更新，使得获取复杂物体表面模型海量的点云数据成为现实。然而，海量的点云
8、数据（几十万，上百万甚至更大）给三维模型重构技术带来了新的难题。首先是点云数据的空间存储问题，海量的数据给空间的有效存储带来了巨大困难；其次是噪声点的问题，在点云数据采集的过程中，不可避免地会带有一定的误差（操作失误，仪器本身问题等），因此海量的数据也就意味着相对大量的噪声点数据，同时还有可能产生因为数据点的采集缺失而造成点云数据的漏洞问题。上述这些难题，都给三维模型重构技术带来了极大的困难。针对上述的这些问题，诸多图形学等领域的学者提出了各种解决问题的方案，但是，迄今为止，大多数对扫描点云进行三维模型重构的方法，都存在不同形式的不足。鉴于以上所述的各种情况，本文研究并总结了众多学者的模型重构
9、方法，采用了基于自适应八叉树空间划分的方法对点云数据进行分割，然后采用三角网格生长算法对点云数据进行几何表面重构，解决了大规模点云数据处理耗时过长的问题。基于点云的几何表面重构方法研究21.2 国内外研究现状随着计算机图形学与虚拟现实科技的飞速发展以及汽车、飞机等制造技能的进步，逆向工程技术的应用日趋广泛化，成为计算机辅助制造（CAM）、工程产品设计、考古学研究、计算机辅助设计（CAD）等领域研究的焦点（Guskov et al.2001;Hoppe et al. 1992;Kobbelt et al.2004）。逆向工程技术研究的理想目标是在不加入人工干预的条件下自动生成计算机辅助设计模型，
10、但是就目前的研究现状来看，实现这个目标还需要很大的努力。根据重构曲面的表示形式不同可将曲面重构方法（武剑洁等 2004）分为以下四种:1.2.1 基于 Delaunay 的三角网格剖分基于Delaunay 的三角网格剖分算法的主要思想是通过一定的剖分算法（如基于Voronoi图的三角网格剖分算法、三角网格生长算法等）对点云数据进行几何形状连接表示，连接形成的几何形状是Delaunay三角网格的形式。Lawson（1972 ）提出了最大化最小内角的局部优化准则，使剖分形成的三角网格质量更加优化。Amenta等人（1998）提出了基于Voronoi图和Delaunay三角剖分的全新曲面重构算法，称
11、为Crust算法。该算法可以有效地对点云数据进行Delaunay三角网格剖分，但是采样点的密度和分布对算法的有效性影响较大，因而制约了概算法的应用范围。为了解决上述问题，Amenta等人（1999）又提出了Power Crust算法，该算法克服了Crust 算法对采样点密度和分布的依赖性，并且剖分形成的三角网格可以更好地体现模型的细节特征。之后，Amenta等人（2002）在Crust算法的基础上提出了Cocone算法，节省了计算时间和内存消耗。Tight Cocone （ 2003）则在Cocone的基础上，改进了Coeone算法引入额外点的不足，并且能够从Delaunay三角剖分中寻找三角
12、形填补孔洞。随后，Mederos等人（2005 ）以及Dey 等人（2006）分别对 Power Cruse算法进行了简化和扩展，获得了较好的重构结果。Lee和Schachter（1980）对Delaunay三角剖分算法做了一定的研究，并分别采用了分治算法和迭代算法进行了实验，最后对两种算法的时间复杂度进行了分析比较。Crossno和Angel（1999）提出了基于螺旋边的三角网格剖分算法，该算法在速度上比传统算法快了三个数量级。通过构建某个点与其邻域的一个星状三角网格剖分对曲面进行一个局部拟合。然后以这个星状三角网格为基础，向四周扩展，直至完成对整个点云数据的剖分重构。Mencl （1995
13、）基于图论的思想提出了一种空间散乱点集表面重构的新算法。该算法的基本思想是计算给定点云数据的欧几里得最小生成树，然后对欧几里得最小生成树进行宽展生成表面描述图，最后用三角网格填充由表面描述图定义的框架以完成对整个点集的曲面重构。Gopi等人（2000）提出了一种基于低维局部Delaunay三角网格重构算法，快速有效地实现了散乱点云数据集的流形三角网格重构。该算法克服了采样点对于几何形状、拓扑结构以及边界等条件的限制，但要求采样点第一章 绪论 3的模型必须是一个流形结构。Yin等人（2011）提出了一种基于容量约束的Delaunay三角剖分算法用于计算点云的分布，根据给定的简单多面体P和所需点的
14、数目n，计算三角剖分，并通过不断更新迭代三角形的几何拓扑连接进行处理，使得生成的三角网格尽可能的均匀分布。徐青等人（2000）针对传统的分治算法和三角网格生长算法分别存在的问题，提出一种两种办法融合的方法。该方法通过将分块中的点云数目设定一个阈值而自适应地调整分块的大小，然后在各个分块中采用三角网格生长算法对块中数据进行三角剖分，实验结果表明该算法可以快速、有效地完成对点云数据的三角网格剖分。胡金星等人（2004）针对数字地形模型，以分治算法为基础提出了一种基于格网划分的三角网格剖分算法。董洪伟（2005）在基于增量扩散法的思想提出了一种三角网格重构算法，在进行第三点搜索时采用了探测邻域规则，
15、提高了搜索效率。邓曙光、刘刚（2006）采用了直线分割式正负区的原理搜索第三点，每次只搜索点集中的部分点，在一定程度上提高了构网效率。邹徐文等人（2007）在分割-合并的思想的基础上，提出了一种基于AVL树的三角剖分算法，该算法通过与传统的三角网格生长算法和基于四叉树的分治算法做了对比，表明该算法具有鲁棒性好、效率高等优点。刘少华等人（2007）针对逐点插入算法定位点与三角形位置效率低下的缺点，研究分析基于点边关系以及基于边边关系的方向定位算法，采用了一种基于这两种算法的一个改进算法，有效地提高了三角网格重构的效率。刑建业等人（2007）针对数字高程模型中快速定位点所在三角形的需求，提出了一种
16、快速的定位算法。陈伟，刘肖琳（2009）提出了一种基于栅格化分的三角网格生长算法。该算法针对传统的三角网格剖分算法效率低下的缺点，采用空间栅格对散乱点云进行空间分割，然后对每个栅格内的数据进行分别处理。与传统的三角网格生长算法相比，该算法在重构效率方面有了极大的提高，实验结果方面也有所改善。张霞等人（2011）介绍了一种新的基于三角网格生长算法的方法对含噪点云数据进行曲面重构。文中使用手动的方法对噪声点进行消除，然后采用空间栅格方法对点云数据进行划分，在每个分割的区域中采用三角网格生长算法对点云数据进行三角剖分，最终完成对整个点云数据集的曲面重构。聂建辉等人（2012）针对大规模散乱点云数据提
17、出了一种快速的三维重构算法。该算法类似与三角网格生长算法，首先建立一个三角网格闭环（六边形），然后对其进行扩展构建初始的近似网格曲面，之后在对其进行细分割，并采用了B样条曲线对生成的点云数据进行层次优化。梁群仙（2013）针对三维扫描得到的规则的采样点数据，提出了一种基于扫描线的三角剖分算法。该算法利用了扫描得到的点云数据之间的内在关系对其进行网格剖分，极大地提高了模型重构效率。综上所述，以上算法都是通过一定的方法确定点云数据之间的拓扑连接，然后将这些点云数据连接成三角网格形式来表示点云模型。这些算法的优点就是重构曲面网格的复杂性和输入采样点的复杂性成正比，而且在采样浓度未知情况下，也能够界定
18、基于点云的几何表面重构方法研究4重构质量。但是，这些算法也存在一些缺点和不足，所需时间复杂度或空间复杂度可能较大，在大规模数据领域的应用收到了限制。1.2.2 基于隐式曲面的模型重构方法基于隐式曲面的模型重构是指根据给定的点云数据，构建一个隐式函数（二次多项式函数、径向基函数等）对其进行曲面拟合重构。Lorensan和Cline （1987）提出了MC （Marching Cube）算法，将给定数据集分割成立方体体素，通过构建等值面对每个体素中的数据进行逼近拟合。所谓等值面，是指一个集合，该集合中的所有数据的函数值都是相同的常数。比如，三维空间中一曲面函数g(x,y,z), 集合A=（x,y,
19、z）|g(x,y,z)=c,c为给定常数，则集合A称为函数g的等值面。Bloomenthal（ 1994）提出了一种隐式函数对模型进行多边形化的算法，文中与多种算法进行了对比，实验结果证明该算法能够很好地完成点云模型的。近年来, 多维空间中基于径向基函数（Radial Basis Function, RBF）的数据插值方法越来越受到国外学者的关注（Carr et al 2001；Ohtake et al 2003a，2003b；Turk et al 2001；Tobor et al 2004）。它是几何数据分析、模式识别、神经网络的标准工具，在各种数学文献中得到了广泛的研究（Shall Sam
20、ozino 2005），此外二次多项式隐函数也有较多的应用。Carr（2001）采用了一种多调和径向基函数对点云模型进行差值重构，该算法可以有效地重构出无孔洞流形曲面，并且同样适用于非均匀采样的数据。由于该算法中的径向基函数表示的是一个实体模型，所以曲面法线和梯度也就能够很容易确定，这对之后的网格优化、网格简化等后处理操作也有很大的帮助。Wendland（2002）提出了单位分解法（Partition of Unity，PU）结合RBF 函数插值的思想，来解决大规模的散乱点问题。Ohtake（2003）在单位分解法思想的基础上提出了MPU 方法（Multi-level Partition of
21、 Unity），为了获取曲面局部的细节特征，使用系数不同的分段二次多项式函数来逼近局部点云，最后通过权函数混合这些多项式函数，形成对整个点云数据集的函数拟合。Ohtake等人（2005）使用分段的二次多项式函数拟合散乱数据点，并利用类似均值漂移(Mean-Shift) 的方法将点迭代移动到该二次曲面上，使用点绘制中的曲面Splatting方法生成自适应的顶点和包围球，利用圆球之间的相交关系对点云网格化。Min等人（2011）提出了一种基于最小加权函数的散乱点集的表面重构算法，该算法集成了隐式和显示算法的优点，可以有效地实现散乱点集的表面重构。Matthew等人（2013）提出了一种点云数据表面
22、重构的比较和评价标准，提出了一种简单的管道测量表面重构方法，首先采用隐式曲面方法进行建模，然后进行采样、评价。李道伦等人（2006）介绍了一种基于径向基网络的隐式曲面重构算法，该算法开始通过给定的点云数据构造了一个显示函数，随后采用径向基函数对其进行拟合逼近。第一章 绪论 5该算法在数据点集数目较少的情形下重构结果非常理想，但是却无法符合大数据量模型重构的要求。钱归平等人（2008）通过建立贝叶斯概率模型对点云数据迭代收缩进行降噪处理，对于降噪后的点云，通过空间圆球沿着物体表面不断增长来快速搜寻邻近点，对点云进行曲面重构。苗兰芳等人（2010）针对密集散乱点云，提出了一种快速的隐式曲面重构算法
23、。该算法使用双边滤波函数作为构建的隐式曲面函数值，每个点的函数值可通过对其附近点的采样数据得到。实验证明，与传统的隐式曲面重构方法相比，该算法可以更加快速、有效地实现散乱点集的模型重构。田建磊等人（2011）提出了一种基于紧支撑径向基函数的保形隐式曲面重构算法，该算法首先通过构建八叉树对点云数据进行单元分解，然后在每个单元中构建紧支撑径向基函数对其进行逼近拟合，最终完成对整个点云数据的曲面拟合。通过自适应的调节支撑半径，该算法在时间效率和重构结果方面都取得了较为理想的实验结果。隐式曲面模型重构的方法由于连续性好、抗噪性好、对复杂物体的描述性强等优点，近年来已经成为点云模型重构算法的主流。但是，
24、构建一个时间、空间复杂度低，实验结果非常完善，鲁棒性好的隐式曲面重构函数却非常困难。1.2.3 基于学习的曲面重构 基于学习的曲面重构是指采用神经网络、统计学等方法，通过将给定的点云数据输入而不断学习、调节，最终完成对点云模型的三维重构的方法。基于学习的曲面重构方法最早由Kohonen等人（1982）开始研究，文中介绍了一种新的自组织过程的理论知识，并对这个自组织过程进行了计算机模拟。Hoffmann等人（1998）介绍了一种新的由无序数据点集重构实体模型的新方法。该方法首先采用人工神经网络对点云数据进行排序，形成一个具有四边形拓扑结构的控制点网格，随后采用自由曲面方法对点云数据进行曲面重构。
25、该方法可以处理任意的点集，即使点云数据较少的情况也同样适用。Yu（1999）介绍了一种采用自组织映射对无序散乱点云数据的曲面重构技术。已知曲面的拓扑结构，文中采用了一种神经网络学习算法获取曲面顶点的3D坐标。为了提高算法的速度和有效性，采用了边交换的网格优化算法和多分辨率学习算法，获得了非常成功的实验结果。 Steinke等人（2005）提出了一种统计学学习的方法逼近拟合点云数据的隐式曲面，该方法以支持向量机为基础，采用标准的机器学习方法来自动调整它的参数，曲面逼近拟合则是基于调整支持向量回归的基础上构建的。该算法可以有效地完成点云数据的三维重构，并且能够自动完成去除噪声点和孔洞修复的工作。J
26、enke等人（2006） 提出了一种新的基于贝叶斯统计的表面重构技术，该算法将测量物体的测量过程以及先验假设建模为概率分布，采用贝叶斯规则来推断最大概率重构。算法的主要思想是将测量过程与重构过程定义为点云数据，并对点云数据有限维表示的所有统计假设进行描述。算法的结果去除了噪声点，重构出了拥有良好采样的数据点的几何拓扑结构，基于点云的几何表面重构方法研究6最后由计算得到的数据的几何拓扑结构进行三角剖分。该算法适用于具有尖锐特征数据的分段光滑曲面的重构。Furao等人（2010）提出了一种基于自组织神经网络增量的在线半监督主动学习算法，该算法不需要先验知识，可以自动学习完成当前任务，并且可以实现线
27、增量学习，鲁棒性较好。范彦革等人（2005）针对基于径向基函数的人工神经网络重构算法抗噪性好等特点，根据给定的含躁散乱点云数据的特点，构建了一个合适的径向基函数对其进行曲面重构，取得了较为理想的实验结果。陈婧等人（2006）对上述算法实施了改进，采用了基于混乱学习的三维重构算法。肖秀春等人（2009）基于散乱数据点集模型重构问题，提出了新的基于学习的模型重构算法。该算法通过构建一个基于广义多项式神经网络的隐式函数对点云数据进行学习以及拟合重构，取得了很好的实验结果。基于学习的曲面重构算法的核心思想是自组织学习，主要采用人工神经网络和统计学等方法对给定的数据进行学习、组织，然后进行拟合、逼近。虽
28、然该算法实现较为简单，但是计算的时间复杂度较大，适用于简单曲面的重构，无法满足大规模复杂物体模型的三维重构问题的需求。1.2.4 网格孔洞修补算法随着计算机技术的进步以及三维扫描设备的持续更新，获得客观实体模型曲面的点集数据也越来越简单、越来越高效了。但不可避免的是，由于三维扫描设备本身的缺陷，扫描物体本身材质的反射以及人工扫描时的误差等等原因，扫描获取的点云数据通常都会存在孔洞问题，这给之后的曲面重构过程带来了很大困难。除此之外，通常的重构算法都存在着这样或者那样的问题，导致重构形成的模型曲面可能会有孔洞问题。网格孔洞修补算法便是针对上述这些问题，采用隐式曲面函数、人工神经网络等方法对其孔洞
29、进行修补完善的算法。James（2002 ）提出了一种新的孔洞修补算法以解决几何和拓扑结构过于复杂的孔洞修复问题。该算法首先构建了一个符号距离函数，用该函数的零集表示模型曲面。起初，该函数只定义了观测曲面的附近区域，通过对其扩展使其零集能够消除所有可能出现的孔洞。该算法实现简单，能够有效地产生流形曲面，适用于大规模的数据点集。Liepa （2003）提出了一种无组织的三角网格的孔洞修复算法，该算法包括边界识别，孔洞三角剖分，细化以及广顺等步骤，适用于流行网格的任意孔洞修复。杜佶等人（2005）提出了一种新的网格孔洞修复算法，取得了较好的实验结果。该算法包括以下三个步骤：首先构建一个基于径向基函数的隐式函数对孔洞周围的点进行逼近拟合；然后通过迭代地从孔洞边界向孔洞中心添加三角网格对孔洞进行修复；最后将新添加的三角网格的顶点映射到隐式曲面上使得修复区域与原区域无缝地结合。陈飞舟等人（2006）提出了一种有效的孔洞修补算法。该算法首先通过构建K 维树来定位点云数据的孔洞边界数据点；然后构建一个标准化的二次曲面函数对孔洞边界的
