毕业论文范文——基于点云的几何表面重构方法研究

基于点云的几何表面重构方法研究摘 要三维扫描技术与获取技术的不断发展，使得三维几何造型技术广泛地应用在计算机辅助设计，计算机辅助制造，逆向工程等多个领域。获取海量的三维点云数据信息成为了现实，但拥有大规模点云信息的三维几何模型的构造和处理给计算机的处理能力带来了极大地挑战，于是如何快速、有效、可靠地实现对点云数据的几何表面重构成为了计算机图形学研究的重点和热点问题之一。本文针对传统的三角网格生长法进行点云数据表面模型重构时，搜索第三点耗时太长，导致重构效率很低的问题，采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域，在每个子域内进行三角网格重构，避免了网格拼接的过程；采用最大角最小化原则进行三角网格优化；并运用三角面片定向的方法进行网格法向量一致化处理。该方法很大地（几十倍，上百倍）提高了表面模型重构的效率，形成的网格能够较好地体现模型的细节特征。本研究主要采用空间划分算法和三角网格生长算法探讨表面模型重构的关键技术，主要完成以下工作：（1）采用基于径向基函数的隐式曲面重构方法对点云模型进行曲面重构。采用八叉树分割算法法对给定点云数据进行空间划分，针对每个分割形成的子区域内的点，构建一个基于径向基函数的隐式函数对其进行拟合重构。（2）采用了自适应八叉树空间划分算法，依据点云数据密度的不同，将点云数据分割成均匀的相互有覆盖的较小的子区域。在每个子区域内对点云数据进行分别处理，大大提高了计算效率。（3）采用了三角网格生长算法对点云模型进行表面重构，分析研究了三角网格剖分的三种算法（逐点插入算法、分治算法和三角网格生长算法）的优缺点，最后确定了三角网生长法进行模型重构，通过设定一些限定条件，构成正则度较高的三角网格。采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域，在每个子域内进行三角网格剖分。实验结果表明，该方法几十倍甚至上百倍的提高了表面模型重构的效率，形成的网格质量也很好，能够较好地体现模型的细节特征，鲁棒性较好。关键词：表面重构；三角网格生长算法；隐式曲面；空间划分；点云 目 录第一章 绪论11.1研究背景与意义11.2国内外研究现状11.2.1 基于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三角网格生长法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作者简介4443致 谢第一章 绪论1.1研究背景与意义所谓点云，就是指大量的数据点聚集在一起形成的一个集合，这些数据点可以由三维扫描获取，也可以通过计算机随机生成，通常这些点会包含坐标、法向量等信息。点云几何表面重构，是指通过对散乱点云数据进行拓扑连接形成一定的几何网格形状（如三角形网格、四面体网格等）来表示点云数据的原始模型。表面重构是几何造型中的一个重要问题。近年来，由于激光扫描技术的发展和在工程设计，产品设计，医疗家电设计和考古学等领域的广泛应用，表面重构技术受到越来越多的关注。随着科学技术的飞速发展，逆向工程技术也有着越来越广泛的应用，如汽车制造、医疗保健、考古研究等领域。通常，逆向工程可以分为数据点采样，数据点预处理，三维模型重构，以及模型的后处理等几个方面。数据点采样，就是指采用三维扫描、计算机随机生成等方法，获得采样点数据（即点云）的过程；数据点预处理，是指在对采样点数据进行模型重构之前，对采样的数据点进行排序、归一化等一系列处理的过程；三维模型重构，是指运用隐式曲面重构、几何表面重构等三维重构算法对采样点进行拟合、逼近，还原采样点的原始形状；后处理，则是对重构形成的模型进行一系列的优化处理，使重构结果更加完善。在整个处理流程中，三维模型重构对整个逆向工程系统起着至关重要的作用，因此也是研究的重点和热点。计算机图形学技术的迅速发展和三维扫描设备的不断更新，使得获取复杂物体表面模型海量的点云数据成为现实。然而，海量的点云数据（几十万，上百万甚至更大）给三维模型重构技术带来了新的难题。首先是点云数据的空间存储问题，海量的数据给空间的有效存储带来了巨大困难；其次是噪声点的问题，在点云数据采集的过程中，不可避免地会带有一定的误差（操作失误，仪器本身问题等），因此海量的数据也就意味着相对大量的噪声点数据，同时还有可能产生因为数据点的采集缺失而造成点云数据的漏洞问题。上述这些难题，都给三维模型重构技术带来了极大的困难。针对上述的这些问题，诸多图形学等领域的学者提出了各种解决问题的方案，但是，迄今为止，大多数对扫描点云进行三维模型重构的方法，都存在不同形式的不足。鉴于以上所述的各种情况，本文研究并总结了众多学者的模型重构方法，采用了基于自适应八叉树空间划分的方法对点云数据进行分割，然后采用三角网格生长算法对点云数据进行几何表面重构，解决了大规模点云数据处理耗时过长的问题。1.2国内外研究现状随着计算机图形学与虚拟现实科技的飞速发展以及汽车、飞机等制造技能的进步，逆向工程技术的应用日趋广泛化，成为计算机辅助制造（CAM）、工程产品设计、考古学研究、计算机辅助设计（CAD）等领域研究的焦点（Guskov et al.2001;Hoppe et al. 1992;Kobbelt et al.2004）。逆向工程技术研究的理想目标是在不加入人工干预的条件下自动生成计算机辅助设计模型，但是就目前的研究现状来看，实现这个目标还需要很大的努力。根据重构曲面的表示形式不同可将曲面重构方法（武剑洁等 2004）分为以下四种:1.2.1 基于Delaunay的三角网格剖分基于Delaunay的三角网格剖分算法的主要思想是通过一定的剖分算法（如基于Voronoi图的三角网格剖分算法、三角网格生长算法等）对点云数据进行几何形状连接表示，连接形成的几何形状是Delaunay三角网格的形式。Lawson（1972）提出了最大化最小内角的局部优化准则，使剖分形成的三角网格质量更加优化。Amenta等人（1998）提出了基于Voronoi图和Delaunay三角剖分的全新曲面重构算法，称为Crust算法。该算法可以有效地对点云数据进行Delaunay三角网格剖分，但是采样点的密度和分布对算法的有效性影响较大，因而制约了概算法的应用范围。为了解决上述问题，Amenta等人（1999）又提出了Power Crust算法，该算法克服了Crust算法对采样点密度和分布的依赖性，并且剖分形成的三角网格可以更好地体现模型的细节特征。之后，Amenta等人（2002）在Crust算法的基础上提出了Cocone算法，节省了计算时间和内存消耗。Tight Cocone（2003）则在Cocone的基础上，改进了Coeone算法引入额外点的不足，并且能够从Delaunay三角剖分中寻找三角形填补孔洞。随后，Mederos等人（2005）以及Dey等人（2006）分别对Power Cruse算法进行了简化和扩展，获得了较好的重构结果。Lee和Schachter（1980）对Delaunay三角剖分算法做了一定的研究，并分别采用了分治算法和迭代算法进行了实验，最后对两种算法的时间复杂度进行了分析比较。Crossno和Angel（1999）提出了基于螺旋边的三角网格剖分算法，该算法在速度上比传统算法快了三个数量级。通过构建某个点与其邻域的一个星状三角网格剖分对曲面进行一个局部拟合。然后以这个星状三角网格为基础，向四周扩展，直至完成对整个点云数据的剖分重构。Mencl（1995）基于图论的思想提出了一种空间散乱点集表面重构的新算法。该算法的基本思想是计算给定点云数据的欧几里得最小生成树，然后对欧几里得最小生成树进行宽展生成表面描述图，最后用三角网格填充由表面描述图定义的框架以完成对整个点集的曲面重构。Gopi等人（2000）提出了一种基于低维局部Delaunay三角网格重构算法，快速有效地实现了散乱点云数据集的流形三角网格重构。该算法克服了采样点对于几何形状、拓扑结构以及边界等条件的限制，但要求采样点的模型必须是一个流形结构。Yin等人（2011）提出了一种基于容量约束的Delaunay三角剖分算法用于计算点云的分布，根据给定的简单多面体P和所需点的数目n，计算三角剖分，并通过不断更新迭代三角形的几何拓扑连接进行处理，使得生成的三角网格尽可能的均匀分布。徐青等人（2000）针对传统的分治算法和三角网格生长算法分别存在的问题，提出一种两种办法融合的方法。该方法通过将分块中的点云数目设定一个阈值而自适应地调整分块的大小，然后在各个分块中采用三角网格生长算法对块中数据进行三角剖分，实验结果表明该算法可以快速、有效地完成对点云数据的三角网格剖分。胡金星等人（2004）针对数字地形模型，以分治算法为基础提出了一种基于格网划分的三角网格剖分算法。董洪伟（2005）在基于增量扩散法的思想提出了一种三角网格重构算法，在进行第三点搜索时采用了探测邻域规则，提高了搜索效率。邓曙光、刘刚（2006）采用了直线分割式正负区的原理搜索第三点，每次只搜索点集中的部分点，在一定程度上提高了构网效率。邹徐文等人（2007）在分割-合并的思想的基础上，提出了一种基于AVL树的三角剖分算法，该算法通过与传统的三角网格生长算法和基于四叉树的分治算法做了对比，表明该算法具有鲁棒性好、效率高等优点。刘少华等人（2007）针对逐点插入算法定位点与三角形位置效率低下的缺点，研究分析基于点边关系以及基于边边关系的方向定位算法，采用了一种基于这两种算法的一个改进算法，有效地提高了三角网格重构的效率。刑建业等人（2007）针对数字高程模型中快速定位点所在三角形的需求，提出了一种快速的定位算法。陈伟，刘肖琳（2009）提出了一种基于栅格化分的三角网格生长算法。该算法针对传统的三角网格剖分算法效率低下的缺点，采用空间栅格对散乱点云进行空间分割，然后对每个栅格内的数据进行分别处理。与传统的三角网格生长算法相比，该算法在重构效率方面有了极大的提高，实验结果方面也有所改善。张霞等人（2011）介绍了一种新的基于三角网格生长算法的方法对含噪点云数据进行曲面重构。文中使用手动的方法对噪声点进行消除，然后采用空间栅格方法对点云数据进行划分，在每个分割的区域中采用三角网格生长算法对点云数据进行三角剖分，最终完成对整个点云数据集的曲面重构。聂建辉等人（2012）针对大规模散乱点云数据提出了一种快速的三维重构算法。该算法类似与三角网格生长算法，首先建立一个三角网格闭环（六边形），然后对其进行扩展构建初始的近似网格曲面，之后在对其进行细分割，并采用了B样条曲线对生成的点云数据进行层次优化。梁群仙（2013）针对三维扫描得到的规则的采样点数据，提出了一种基于扫描线的三角剖分算法。该算法利用了扫描得到的点云数据之间的内在关系对其进行网格剖分，极大地提高了模型重构效率。综上所述，以上算法都是通过一定的方法确定点云数据之间的拓扑连接，然后将这些点云数据连接成三角网格形式来表示点云模型。这些算法的优点就是重构曲面网格的复杂性和输入采样点的复杂性成正比，而且在采样浓度未知情况下，也能够界定重构质量。但是，这些算法也存在一些缺点和不足，所需时间复杂度或空间复杂度可能较大，在大规模数据领域的应用收到了限制。1.2.2 基于隐式曲面的模型重构方法基于隐式曲面的模型重构是指根据给定的点云数据，构建一个隐式函数（二次多项式函数、径向基函数等）对其进行曲面拟合重构。Lorensan和Cline（1987）提出了MC（Marching Cube）算法，将给定数据集分割成立方体体素，通过构建等值面对每个体素中的数据进行逼近拟合。所谓等值面，是指一个集合，该集合中的所有数据的函数值都是相同的常数。比如，三维空间中一曲面函数g(x,y,z), 集合A=（x,y,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 Samozino 2005），此外二次多项式隐函数也有较多的应用。Carr（2001）采用了一种多调和径向基函数对点云模型进行差值重构，该算法可以有效地重构出无孔洞流形曲面，并且同样适用于非均匀采样的数据。由于该算法中的径向基函数表示的是一个实体模型，所以曲面法线和梯度也就能够很容易确定，这对之后的网格优化、网格简化等后处理操作也有很大的帮助。Wendland（2002）提出了单位分解法（Partition of Unity，PU）结合RBF函数插值的思想，来解决大规模的散乱点问题。Ohtake（2003）在单位分解法思想的基础上提出了MPU方法（Multi-level Partition of Unity），为了获取曲面局部的细节特征，使用系数不同的分段二次多项式函数来逼近局部点云，最后通过权函数混合这些多项式函数，形成对整个点云数据集的函数拟合。Ohtake等人（2005）使用分段的二次多项式函数拟合散乱数据点，并利用类似均值漂移(Mean-Shift)的方法将点迭代移动到该二次曲面上，使用点绘制中的曲面Splatting方法生成自适应的顶点和包围球，利用圆球之间的相交关系对点云网格化。Min等人（2011）提出了一种基于最小加权函数的散乱点集的表面重构算法，该算法集成了隐式和显示算法的优点，可以有效地实现散乱点集的表面重构。Matthew等人（2013）提出了一种点云数据表面重构的比较和评价标准，提出了一种简单的管道测量表面重构方法，首先采用隐式曲面方法进行建模，然后进行采样、评价。李道伦等人（2006）介绍了一种基于径向基网络的隐式曲面重构算法，该算法开始通过给定的点云数据构造了一个显示函数，随后采用径向基函数对其进行拟合逼近。该算法在数据点集数目较少的情形下重构结果非常理想，但是却无法符合大数据量模型重构的要求。钱归平等人（2008）通过建立贝叶斯概率模型对点云数据迭代收缩进行降噪处理，对于降噪后的点云，通过空间圆球沿着物体表面不断增长来快速搜寻邻近点，对点云进行曲面重构。苗兰芳等人（2010）针对密集散乱点云，提出了一种快速的隐式曲面重构算法。该算法使用双边滤波函数作为构建的隐式曲面函数值，每个点的函数值可通过对其附近点的采样数据得到。实验证明，与传统的隐式曲面重构方法相比，该算法可以更加快速、有效地实现散乱点集的模型重构。田建磊等人（2011）提出了一种基于紧支撑径向基函数的保形隐式曲面重构算法，该算法首先通过构建八叉树对点云数据进行单元分解，然后在每个单元中构建紧支撑径向基函数对其进行逼近拟合，最终完成对整个点云数据的曲面拟合。通过自适应的调节支撑半径，该算法在时间效率和重构结果方面都取得了较为理想的实验结果。隐式曲面模型重构的方法由于连续性好、抗噪性好、对复杂物体的描述性强等优点，近年来已经成为点云模型重构算法的主流。但是，构建一个时间、空间复杂度低，实验结果非常完善，鲁棒性好的隐式曲面重构函数却非常困难。1.2.3 基于学习的曲面重构 基于学习的曲面重构是指采用神经网络、统计学等方法，通过将给定的点云数据输入而不断学习、调节，最终完成对点云模型的三维重构的方法。基于学习的曲面重构方法最早由Kohonen等人（1982）开始研究，文中介绍了一种新的自组织过程的理论知识，并对这个自组织过程进行了计算机模拟。Hoffmann等人（1998）介绍了一种新的由无序数据点集重构实体模型的新方法。该方法首先采用人工神经网络对点云数据进行排序，形成一个具有四边形拓扑结构的控制点网格，随后采用自由曲面方法对点云数据进行曲面重构。该方法可以处理任意的点集，即使点云数据较少的情况也同样适用。Yu（1999）介绍了一种采用自组织映射对无序散乱点云数据的曲面重构技术。已知曲面的拓扑结构，文中采用了一种神经网络学习算法获取曲面顶点的3D坐标。为了提高算法的速度和有效性，采用了边交换的网格优化算法和多分辨率学习算法，获得了非常成功的实验结果。 Steinke等人（2005）提出了一种统计学学习的方法逼近拟合点云数据的隐式曲面，该方法以支持向量机为基础，采用标准的机器学习方法来自动调整它的参数，曲面逼近拟合则是基于调整支持向量回归的基础上构建的。该算法可以有效地完成点云数据的三维重构，并且能够自动完成去除噪声点和孔洞修复的工作。Jenke等人（2006） 提出了一种新的基于贝叶斯统计的表面重构技术，该算法将测量物体的测量过程以及先验假设建模为概率分布，采用贝叶斯规则来推断最大概率重构。算法的主要思想是将测量过程与重构过程定义为点云数据，并对点云数据有限维表示的所有统计假设进行描述。算法的结果去除了噪声点，重构出了拥有良好采样的数据点的几何拓扑结构，最后由计算得到的数据的几何拓扑结构进行三角剖分。该算法适用于具有尖锐特征数据的分段光滑曲面的重构。Furao等人（2010）提出了一种基于自组织神经网络增量的在线半监督主动学习算法，该算法不需要先验知识，可以自动学习完成当前任务，并且可以实现线增量学习，鲁棒性较好。范彦革等人（2005）针对基于径向基函数的人工神经网络重构算法抗噪性好等特点，根据给定的含躁散乱点云数据的特点，构建了一个合适的径向基函数对其进行曲面重构，取得了较为理想的实验结果。陈婧等人（2006）对上述算法实施了改进，采用了基于混乱学习的三维重构算法。肖秀春等人（2009）基于散乱数据点集模型重构问题，提出了新的基于学习的模型重构算法。该算法通过构建一个基于广义多项式神经网络的隐式函数对点云数据进行学习以及拟合重构，取得了很好的实验结果。基于学习的曲面重构算法的核心思想是自组织学习，主要采用人工神经网络和统计学等方法对给定的数据进行学习、组织，然后进行拟合、逼近。虽然该算法实现较为简单，但是计算的时间复杂度较大，适用于简单曲面的重构，无法满足大规模复杂物体模型的三维重构问题的需求。1.2.4 网格孔洞修补算法随着计算机技术的进步以及三维扫描设备的持续更新，获得客观实体模型曲面的点集数据也越来越简单、越来越高效了。但不可避免的是，由于三维扫描设备本身的缺陷，扫描物体本身材质的反射以及人工扫描时的误差等等原因，扫描获取的点云数据通常都会存在孔洞问题，这给之后的曲面重构过程带来了很大困难。除此之外，通常的重构算法都存在着这样或者那样的问题，导致重构形成的模型曲面可能会有孔洞问题。网格孔洞修补算法便是针对上述这些问题，采用隐式曲面函数、人工神经网络等方法对其孔洞进行修补完善的算法。James（2002）提出了一种新的孔洞修补算法以解决几何和拓扑结构过于复杂的孔洞修复问题。该算法首先构建了一个符号距离函数，用该函数的零集表示模型曲面。起初，该函数只定义了观测曲面的附近区域，通过对其扩展使其零集能够消除所有可能出现的孔洞。该算法实现简单，能够有效地产生流形曲面，适用于大规模的数据点集。Liepa（2003）提出了一种无组织的三角网格的孔洞修复算法，该算法包括边界识别，孔洞三角剖分，细化以及广顺等步骤，适用于流行网格的任意孔洞修复。杜佶等人（2005）提出了一种新的网格孔洞修复算法，取得了较好的实验结果。该算法包括以下三个步骤：首先构建一个基于径向基函数的隐式函数对孔洞周围的点进行逼近拟合；然后通过迭代地从孔洞边界向孔洞中心添加三角网格对孔洞进行修复；最后将新添加的三角网格的顶点映射到隐式曲面上使得修复区域与原区域无缝地结合。陈飞舟等人（2006）提出了一种有效的孔洞修补算法。该算法首先通过构建K维树来定位点云数据的孔洞边界数据点；然后构建一个标准化的二次曲面函数对孔洞边界的数据点进行参数拟合；最后通过拟合形成二次曲面函数对孔洞进行插值修补。段德全，刘春红（2009）提出了一种基于粒子群算法的孔洞修复方法（Particle Swarm Optimization，PSO）。算法首先对孔洞周围的多边形边界进行初始的三角网格剖分，然后采用PSO算法对生成的三角网格进行修正、优化，算法鲁棒性好，可以对形状非常复杂的孔洞进行有效修复。王宏涛等人（2005）在基于径向基函数神经网络的基础上，提出了一种新的网格孔洞修补算法，用来解决数字化点云数据曲面重构形成的漏洞问题。钱归平等人（2010）提出了一种保持网格模型尖锐特征的网格修复算法，首先对给定散乱点云数据建立自适应八叉树，然后对模型孔洞周围的点集进行分段二次拟合，最后采用MC（Marching Cube）办法生成孔洞的三角网格面片。罗正伟（2012）提出了一种基于RBF函数的隐式曲面插值算法对孔洞进行修复，首先对给定点云数据中的孔洞周围的点构建RBF隐式函数，通过插值构造孔洞中的点，最后通过MC算法提取等值面，实现对孔洞中点的三角剖分。网格孔洞修补算法的核心思想是首先定位网格孔洞，然后采用一定的算法（比如神经网络算法、隐式曲面函数算法等）对孔洞进行网格剖分等修补操作，最后采用一定的拼接优化算法完成对孔洞区域和原模型区域的连接融合。由于孔洞修复算法通常是针对点云数据重构形成的模型孔洞问题，通常是作为点云数据模型重构的后处理操作，而不是以单独的三维重构算法形式出现。1.3研究内容鉴于上述，本研究主要以点云数据为研究对象，研究如何高效快速地进行点云数据的几何模型重构以及网格优化等问题。主要内容包括：模型三角网格重构技术、空间划分技术、网格优化等。（1）基于径向基函数的隐式曲面重构采用基于径向基函数的隐式曲面重构方法对点云模型进行曲面重构。首先采用八叉树分割算法法对点云数据进行空间划分，然后针对每个分割形成的子区域内的点，构建一个基于径向基函数的隐式函数对其进行拟合重构。（2）模型三角网格重构技术以给定数据点集为研究对象，研究模型三角网格重构的多种算法并进行对比，选出较优的重构算法。主要研究了三角网格重构的三种算法：逐点插入算法、分治算法以及三角网格生长算法，本文选择了能构成较优质量网格的三角网格生长算法进行三角网格重构，在网格重构的过程中加入二面角限制等条件进行网格重构。（3）空间划分技术针对点云数据量过大引起的重构效率低的问题，采用空间划分技术进行点云数据集合分割成若干较小的子集合进行处理，可以提高重构效率。本研究基于传统的八叉树空间划分算法，加入了自适应的条件，采用自适应八叉树划分算法对点云数据进行空间划分，该方法大大缩短了重构时间、提高了重构效率。1.4论文结构组织第一章，绪论。本章主要介绍了本文的研究背景和研究的主要内容。首先介绍了模型重构技术在各个领域的应用，列举了目前主流的模型重构算法以及国内外的研究现状，并分析各个方法的优缺点。介绍本研究的主要内容并给出论文的组织结构。第二章，基于径向基函数函数的隐式曲面重构技术。本章主要对点云的隐式曲面模型进行了描述，并详细介绍了基于径向基函数的隐式曲面重构方法，采用了多组点云数据进行实验，给出了实验结果。第三章，三角网格剖分算法。本章主要介绍了Delnunay三角网格剖分的基础知识，并详细介绍了Delnunay三角网格剖分的三种算法：逐点插入算法、三角网格生长算法和分治算法，最后对三种算法的优缺点进行了评价。第四章，自适应八叉树空间划分方法。本章主要介绍了八叉树与k近邻的定义，并介绍了八叉树空间分割方法求解数据的k近邻，采用的多组数据进行实验验证，并给出了实验结果与分析。第五章，实验结果与分析。主要介绍了网格优化的基本方法，包括重复网格去除、规范化网格以及法向量一致化，最后给出了网格优化后的实验结果。第六章，总结与展望。对本研究的内容进行了概括性的总结和评价，在此基础上对未来需要进一步完善的工作进行了介绍。第二章 基于径向基函数的隐式曲面重构技术第一章的绪论中主要对模型重构技术的研究目的、背景以及国内外的研究现状进行了详细的阐述。本章主要针对两种常用的模型重构技术（基于径向基函数的隐式曲面重构和几何模型重构）进行了简要介绍，并且对隐式曲面重构的算法进行了一个简单的模拟和实现。2.1 隐式曲面模型的描述在计算机图形学领域，三维模型曲面的表示方法主要有两类：参数曲面和隐式曲面。由于隐式曲面算法不但可以精确地表示复杂模型，而且能方便地对重构后的模型进行变换以及编辑等处理，所以该算法得到了广泛应用。在所有隐式曲面重构算法中，基于径向基函数的重构算法能够很好地解决散乱点云的插值拟合的难题。因此，该算法成为很多计算机图形学的学者研究隐式曲面重构的重要依据和参考。基本概念：点云：是指含有坐标、法向量等信息的大量数据点的集合，这些点通常由三维扫描获取，或者通过随机函数产生。显式：形如z=f(x,y)的表达式。对于一个平面曲线，显式表示一般形式是：y=f(x)。由于该方程中x与y是一一映射的关系，所以应用面较窄。隐式：形如f(x,y,z)=0的表达式。如一个平面曲线方程，表示成f(x,y)=0的隐式表示。相对于显示方程，隐式方程可以表示的曲面或者曲面范围更广，因而在数学、物理研究等领域有着更为广泛的应用。参数表示：形如x=f(t), y=f(t), z=f(t)的表达式，其中t为参数。即曲线上任一点的坐标均表示成给定参数的函数。插值：给定一组有序的数据点Pi，i=0，1，n，构造一条顺序通过这些点的曲线的过程成为插值，该曲线称为插值曲线。逼近：给定一组数据点Pi，i=0，1，n，构造一条在几何距离上最接近给定数据点的曲线的过程称为逼近，该曲线称为逼近曲线。拟合：插值和逼近则统称为拟合（fitting）。原始误差：由客观存在的模型抽象到物理模型产生的误差。包括模型误差和原始数据误差。截断误差：当求解所得的解由无限项组成时，通常会采用截断函数进行截断，由此导致的误差称作截断误差。舍入误差：在求解的流程中，因为使用进一法，四舍五入等方法取求解结果的近似值而产生的误差叫做舍入误差。径向基函数：已知p、p0Rn，则由多项式p-p0构成的函数系，若满足f(x)0，则称p-p0为径向基函数。误差点：在点的拟合过程中由于误差而产生的点。平凡解：矩阵代数中的定义，AX=0，行列式|A|=0，则X有非平凡解，否则，只有平凡解X=0。2.2空间划分采用八叉树空间划分算法，首先构建一个较大的长方体包围盒包含所有的点云数据，然后将点云数据分割到较小的子长方体内，然后在每个包含该子长方体的较大的区域内进行三角网格重构。该较大的区域取为以子长方体的中心为球心，以为半径的圆球，其中为长方体的对角线长度，为自定义的一个常数，本文取0.75。给定输入散乱数据点集，首先计算该点集中的点在三维坐标各个方向上的最大值和最小值xmin，xmax，ymin，ymax，zmin，zmax；然后由这些数据构造初始的包含整个点集的长方体包围盒，并将其作为八叉树分割的根节点；然后，根据设置的最大递归深度将根节点平均分割成八个等尺寸的小长方体，称为根节点的孩子节点；孩子节点又被进一步划分成八个尺寸更小的长方体，直至达到最大递归深度，最后对每个子域内的点云数据进行局部函数拟合重构。2.3局部形状函数估计基于径向基函数的隐式曲面重构算法的基本思想是根据已知的散乱点云数据，用基于径向基函数的拟合方法计算局部形状函数s(x)，然后由计算出的局部形状函数s(x)进行点云数据的拟合与显示。已知给定点云集合和这些点集对应的函数值集，则局部拟合函数映射需满足： （2-1）通常，传统形式的隐式曲面模型为一些径向基函数的线性组合。通过分析总结前人的方法，本研究采用如下的基于径向基函数的插值方法求解模型的曲面函数s(x)，即 （2-2）式中：p(x)=c1*x+c2*y+c3*z+c4 ,为一次多项式，表示s(x)的常数和一次项部分，c1，c2,c3,c4为未知数；为组合系数，|为欧几里德范数。本文采用C2连续且紧支撑的基函数=计算曲面函数，其中=|x-|。权系数则满足如下限定条件：（2-3） 本研究采用了(x) = x 作为插值基函数。综合上述各式得到一个线性系统： （2-4）可简记为：，其中， 为了避免出现平凡解，本研究采取了用0-0.1之间的随机取值作为隐式曲面函数的函数值的方法。用LU分解法可解得径向基函数的组合系数和多项式系数的值。2.4实验结果与分析采用径向基函数方法进行曲面拟合，对多组点云数据进行实验，主要实验结果如图2-1至图2-6所示。 (a) Venus原始点云数据 (b) Venus拟合生成点云数据 (a) Original venus point cloud data (b) Fitted venus point cloud图2-1 Venus点云模型Fig. 2-1 Venus point cloud model (a) Cow原始点云数据 (b) Cow拟合生成点云数据(a) Original cow point cloud data (b)Fitted cow point cloud图2-2 Cow点云模型Fig. 2-2 Cow point cloud model (a) Shark原始点云数据 (b) Shark拟合生成点云数据(a) Original shark point cloud data (b)Fitted shark point cloud图2-3 Shark点云模型Fig. 2-3 Shark point cloud model (a) Dinosaur原始点云数据 (b) Dinosaur拟合生成点云数据(a) Original dinosaur point cloud data (b) Fitted dinosaur point cloud图2-4 Dinosaur点云模型Fig. 2-4 Dinosaur point cloud model (a) Pig原始点云数据 (b) Pig拟合生成点云数据(a) Original pig point cloud data (b)Fitted pig point cloud图2-5 Pig点云模型Fig. 2-5 Pig point cloud model (a) Tyrannosaurus原始点云数据 (b) Tyrannosaurus拟合生成点云数据(a) Original tyrannosaurus point cloud data (b) Fitted tyrannosaurus point cloud图2-6 Tyrannosaurus点云模型Fig. 2-6 Tyrannosaurus point cloud model上述实验数据中的venus、cow、shark、dinosaur、pig数据是由公开库中获取的点云数据，最后一个tyrannosaurus的点云模型是通过三维扫描得到的tyrannosaurus点云模型（有一定的噪声点）。由上述实验结果可知，采用径向基函数方法进行曲面拟合所形成的点云数据完好保留了原始点云的特征，并对原始点云的部分漏洞进行了修复。但是该算法的实验结果并不理想，对于给定的含噪散乱点云数据，理想的算法应该是能有效去除噪声点数据并且能对点云漏洞进行修复。但本文算法只是严格保留的点云数据的原始特征，对噪声点数据没有做任何处理，并且在生成的点云数据中还存在有新的噪声点，如图2-2中的cow模型和图2-5中的pig模型。2.5本章小结本章首先介绍了隐式曲面函数的基本概念以及实现原理；然后针对常用的隐式曲面重构算法之一基于径向基函数的隐式重构算法进行了简单的模拟和实现，并对实验结果进行了简要分析与讨论。第三章 三角网格剖分算法近年来，随着基于视觉和多视图像三维模型获取技术的发展，基于点云的曲面重构技术广泛应用于逆向工程、计算机图形学、计算机视觉、虚拟现实等领域。作为常用的曲面重构方法之一的三角剖分技术，既是热点又是难点问题。上个世纪70年代，为满足汽车等产品制造、考古研究以及计算机图形学等领域的需求，三角网格剖分技术应运而生。3.1 Delaunay三角剖分在无任何附加条件的情况下，同样的数据会有若干种三角剖分结果，三角网格中可能存在畸形的网格单元。一般情况下，在众多三角剖分算法中，Delaunay三角剖分构建的网格质量是最优的(Miles 1969)。通常Delaunay三角剖分算法(余杰等 2003)可以分为以下三种：逐点插入算法、分治算法以及三角网格生长算法。逐点插入方法实现过程相对简单，所需空间复杂度较小，但它的计算效率较低。分治算法所学时间复杂度较小，但所需空间复杂度较大，很难应用到需要海量数据处理的领域。三角网格生长方法由于在搜索第3点时消耗时间太长，近年来传统的三角网格生长方法的比较少用。3.1.1 Delaunay三角剖分定义三角剖分，起初是二维平面中的一个定义，后来渐渐被用作三维点云数据的网格重构技术中。所谓三角剖分，简单来说，就是将给定二维点集通过一定的连接规则连接成三角网格集的过程。该三角网格集具有如下两个基本性质：（1）三角网格的边与边之间互不相交；（2）点云数据中所有点都在三角面片的顶点处，三角面片的边上不存在第三个点；因为每条边有两个点组成，也就是说除了线的两个顶点，线的中间不包含其他任意点。满足Delaunay准则Lawson(1972)的三角剖分叫做Delaunay三角剖分。Delaunay准则包括以下两个方面：（1）空圆特性：通过将给定点集进行Delaunay三角剖分形成的三角网格集中，任一三角网格的外接圆中不包含除三角网格顶点外的其他点集中的点。所以，Delaunay三角剖分确保了形成的三角网格集中，所有三角网格的边与边之间都不会相交。空圆特性的示意图如图3-1所示。（2）最大角最小化特性：通常，给定散乱点云数据集合，通过不同的拓扑连接规则可以形成多种三角剖分的形式。在所有形式的三角剖分中，Delaunay三角剖分所形成的三角网格集中，三角网格的最大角是最小的。所以，通过Delaunay三角剖分所形成的三角形更接近与正三角形，所构建的三角网格是最优的。最大角最小化特性的示意图如图3-2所示。A B C D 图3-1 空圆特性Fig. 3-1 Empty circle characteristicsABCDABCD(a)不规则的三角网格 (b)规则的三角网格(a) Irregular triangle grid (b) Regular triangle grid图3-2 最大化三角形的最小角Fig. 3-2 Minimal angle of maxmized triangle3.1.2 局部最优化处理由三角剖分所构建的三角网格集结果并不是唯一的，即使在构建的过程中使用了很严谨的限制条件，也无法确保所构建的三角网格全部符合Delaunay特性。通常会采用局部优化过程（Local Optimization Procedure LOP）对产生的网格进行优化处理。局部优化处理的基本步骤为：针对每一个有公共边的两个三角形所组成的四边形，采用空圆特性进行检测；如果存在第四个点在三角形外接圆的内部，则删除该四边形的对角线，连接另一条对角线；如果不存在第四个点在三角形外接圆的内部，则此时三角形已是最优的，不需要再进行优化处理。局部优化处理的过程如图3-3所示。ABCDABCD(a)存在第四个点在三角形的外接圆内 (b)局部优化处理后的结果(a) Triangle circumcircle contains the forth vertex (b) Local optimization processing result图3-3 局部优化处理Fig. 3-3 Local optimization processing3.2逐点插入法逐点插入算法由Lawson（1977）年提出，其方法的核心思想是：起初构建初始三角形，该初始三角形包含所有点云数据集；从点集中依次（随机排列）选择各点插入已生成的三角网格中，直至点集中所有点都已插入三角网格中；去除冗余的三角网格，并进行网格优化。该算法的基本步骤如下：Step1：构建初始的包括点集P中所有数据的大三角形；Step2：对点集P中所有点P0，P1，.，Pn进行随机排列，依次插入到点列表中；Step3：对点集P中的点Pm进行如下插入操作：（1）定位三角形PiPjPk，该三角形包含点Pm；（2）如果点Pm在三角形PiPjPk的内部，则连接点Pm与各顶点Pi,Pj,Pk,将三角形PiPjPk分成三个三角形PiPjPm、PjPkPm、PkPiPm；如果点Pm在三角形PiPjPk的一条边PiPj上，则连接Pm与共边PiPj的两个三角形PiPjPk，PiPjPr的第三个点，将这两个三角形剖分成四个三角形PjPkPm、PkPiPm、PjPrPm、PrPiPm；Step4：判断点列表是否为空，如果为空，执行Step5；否则重复执行Step3；Step5：去除包含大三角形顶点的所有三角形。Step6：采用边交换方法对剖分形成的三角网格进行规范化处理；逐点插入法的步骤如图3-4所示。(a)构造初始大三角形(b)插入第一个点构建三角形 (a) Construct original triangle (b) Insert first point to construct triangle(c)点在三角形边上的插入操作 (d)点在三角形内部的插入操作(c) Insert the point on triangle edge (d) Insert the point inside triangle(e)剩余点全部完成处理 (f)去除冗余的三角形(e) Insert the remaining points (f) Remove redundant triangles(g) 对生成的网格进行优化处理(g) Optimize generated meshes图3-4 逐点插入法步骤Fig. 3-4 The process of insertion point by point method 3.3分治方法分治方法的基本思想由著名学者Shamos和Hoey（1975）提出的，由Lewis和Robinson （1978）将此思想应用在Delaunay三角网格构建中。分治方法的基本思想是将整个数据点集分割成较小的集合，然后在每个小集合内构建三角网格，最后再进行集合合并。该方法的基本步骤具体如下：Step1：根据点集中所有点的坐标对其进行排序；Step2：将Step1中排序后的点集进行分割，形成两个点集UL和UR；Step3：如果点集UL中的点的数目大于N，重复执行Step2；Step4：如果UR中点的数目大于N，重复执行Step2；Step5：分别在子集合UL和UR内进行三角网格构建；Step6：合并点集UL和UR。其中，N为自定义常数。分治方法的步骤如图3-5所示。(a)原始点云数据 (b)将原始点云集合分割成