《毕业论文范文——基于点云的几何表面重构方法研究》由会员分享，可在线阅读，更多相关《毕业论文范文——基于点云的几何表面重构方法研究（48页珍藏版）》请在金锄头文库上搜索。
1、基于点云的几何表面重构方法研究摘 要三维扫描技术与获取技术的不断发展，使得三维几何造型技术广泛地应用在计算机辅助设计，计算机辅助制造，逆向工程等多个领域。获取海量的三维点云数据信息成为了现实，但拥有大规模点云信息的三维几何模型的构造和处理给计算机的处理能力带来了极大地挑战，于是如何快速、有效、可靠地实现对点云数据的几何表面重构成为了计算机图形学研究的重点和热点问题之一。本文针对传统的三角网格生长法进行点云数据表面模型重构时，搜索第三点耗时太长，导致重构效率很低的问题，采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域，在每个子域内进行三角网格重构，避免了网格拼接的过程；采用最大角最小化原则
2、进行三角网格优化；并运用三角面片定向的方法进行网格法向量一致化处理。该方法很大地（几十倍，上百倍）提高了表面模型重构的效率，形成的网格能够较好地体现模型的细节特征。本研究主要采用空间划分算法和三角网格生长算法探讨表面模型重构的关键技术，主要完成以下工作：（1）采用基于径向基函数的隐式曲面重构方法对点云模型进行曲面重构。采用八叉树分割算法法对给定点云数据进行空间划分，针对每个分割形成的子区域内的点，构建一个基于径向基函数的隐式函数对其进行拟合重构。（2）采用了自适应八叉树空间划分算法，依据点云数据密度的不同，将点云数据分割成均匀的相互有覆盖的较小的子区域。在每个子区域内对点云数据进行分别处理，大
3、大提高了计算效率。（3）采用了三角网格生长算法对点云模型进行表面重构，分析研究了三角网格剖分的三种算法（逐点插入算法、分治算法和三角网格生长算法）的优缺点，最后确定了三角网生长法进行模型重构，通过设定一些限定条件，构成正则度较高的三角网格。采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域，在每个子域内进行三角网格剖分。实验结果表明，该方法几十倍甚至上百倍的提高了表面模型重构的效率，形成的网格质量也很好，能够较好地体现模型的细节特征，鲁棒性较好。关键词：表面重构；三角网格生长算法；隐式曲面；空间划分；点云 目 录第一章 绪论11.1研究背景与意义11.2国内外研究现状11.2.1 基于De
4、launay的三角网格剖分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
5、.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研究背景与意义所谓点云，就是指大量的数据点聚集在一起形成的一个集合，这些数据点可以由三维扫描获取，也可以通过计算机随机生成，通常这些点会包含坐标、法向量等信息。点云几何表面重构，是指通过对散乱点云
6、数据进行拓扑连接形成一定的几何网格形状（如三角形网格、四面体网格等）来表示点云数据的原始模型。表面重构是几何造型中的一个重要问题。近年来，由于激光扫描技术的发展和在工程设计，产品设计，医疗家电设计和考古学等领域的广泛应用，表面重构技术受到越来越多的关注。随着科学技术的飞速发展，逆向工程技术也有着越来越广泛的应用，如汽车制造、医疗保健、考古研究等领域。通常，逆向工程可以分为数据点采样，数据点预处理，三维模型重构，以及模型的后处理等几个方面。数据点采样，就是指采用三维扫描、计算机随机生成等方法，获得采样点数据（即点云）的过程；数据点预处理，是指在对采样点数据进行模型重构之前，对采样的数据点进行排序
7、、归一化等一系列处理的过程；三维模型重构，是指运用隐式曲面重构、几何表面重构等三维重构算法对采样点进行拟合、逼近，还原采样点的原始形状；后处理，则是对重构形成的模型进行一系列的优化处理，使重构结果更加完善。在整个处理流程中，三维模型重构对整个逆向工程系统起着至关重要的作用，因此也是研究的重点和热点。计算机图形学技术的迅速发展和三维扫描设备的不断更新，使得获取复杂物体表面模型海量的点云数据成为现实。然而，海量的点云数据（几十万，上百万甚至更大）给三维模型重构技术带来了新的难题。首先是点云数据的空间存储问题，海量的数据给空间的有效存储带来了巨大困难；其次是噪声点的问题，在点云数据采集的过程中，不可
8、避免地会带有一定的误差（操作失误，仪器本身问题等），因此海量的数据也就意味着相对大量的噪声点数据，同时还有可能产生因为数据点的采集缺失而造成点云数据的漏洞问题。上述这些难题，都给三维模型重构技术带来了极大的困难。针对上述的这些问题，诸多图形学等领域的学者提出了各种解决问题的方案，但是，迄今为止，大多数对扫描点云进行三维模型重构的方法，都存在不同形式的不足。鉴于以上所述的各种情况，本文研究并总结了众多学者的模型重构方法，采用了基于自适应八叉树空间划分的方法对点云数据进行分割，然后采用三角网格生长算法对点云数据进行几何表面重构，解决了大规模点云数据处理耗时过长的问题。1.2国内外研究现状随着计算机
9、图形学与虚拟现实科技的飞速发展以及汽车、飞机等制造技能的进步，逆向工程技术的应用日趋广泛化，成为计算机辅助制造（CAM）、工程产品设计、考古学研究、计算机辅助设计（CAD）等领域研究的焦点（Guskov et al.2001;Hoppe et al. 1992;Kobbelt et al.2004）。逆向工程技术研究的理想目标是在不加入人工干预的条件下自动生成计算机辅助设计模型，但是就目前的研究现状来看，实现这个目标还需要很大的努力。根据重构曲面的表示形式不同可将曲面重构方法（武剑洁等 2004）分为以下四种:1.2.1 基于Delaunay的三角网格剖分基于Delaunay的三角网格剖分算法
10、的主要思想是通过一定的剖分算法（如基于Voronoi图的三角网格剖分算法、三角网格生长算法等）对点云数据进行几何形状连接表示，连接形成的几何形状是Delaunay三角网格的形式。Lawson（1972）提出了最大化最小内角的局部优化准则，使剖分形成的三角网格质量更加优化。Amenta等人（1998）提出了基于Voronoi图和Delaunay三角剖分的全新曲面重构算法，称为Crust算法。该算法可以有效地对点云数据进行Delaunay三角网格剖分，但是采样点的密度和分布对算法的有效性影响较大，因而制约了概算法的应用范围。为了解决上述问题，Amenta等人（1999）又提出了Power Crus
11、t算法，该算法克服了Crust算法对采样点密度和分布的依赖性，并且剖分形成的三角网格可以更好地体现模型的细节特征。之后，Amenta等人（2002）在Crust算法的基础上提出了Cocone算法，节省了计算时间和内存消耗。Tight Cocone（2003）则在Cocone的基础上，改进了Coeone算法引入额外点的不足，并且能够从Delaunay三角剖分中寻找三角形填补孔洞。随后，Mederos等人（2005）以及Dey等人（2006）分别对Power Cruse算法进行了简化和扩展，获得了较好的重构结果。Lee和Schachter（1980）对Delaunay三角剖分算法做了一定的研究，并
12、分别采用了分治算法和迭代算法进行了实验，最后对两种算法的时间复杂度进行了分析比较。Crossno和Angel（1999）提出了基于螺旋边的三角网格剖分算法，该算法在速度上比传统算法快了三个数量级。通过构建某个点与其邻域的一个星状三角网格剖分对曲面进行一个局部拟合。然后以这个星状三角网格为基础，向四周扩展，直至完成对整个点云数据的剖分重构。Mencl（1995）基于图论的思想提出了一种空间散乱点集表面重构的新算法。该算法的基本思想是计算给定点云数据的欧几里得最小生成树，然后对欧几里得最小生成树进行宽展生成表面描述图，最后用三角网格填充由表面描述图定义的框架以完成对整个点集的曲面重构。Gopi等人
13、（2000）提出了一种基于低维局部Delaunay三角网格重构算法，快速有效地实现了散乱点云数据集的流形三角网格重构。该算法克服了采样点对于几何形状、拓扑结构以及边界等条件的限制，但要求采样点的模型必须是一个流形结构。Yin等人（2011）提出了一种基于容量约束的Delaunay三角剖分算法用于计算点云的分布，根据给定的简单多面体P和所需点的数目n，计算三角剖分，并通过不断更新迭代三角形的几何拓扑连接进行处理，使得生成的三角网格尽可能的均匀分布。徐青等人（2000）针对传统的分治算法和三角网格生长算法分别存在的问题，提出一种两种办法融合的方法。该方法通过将分块中的点云数目设定一个阈值而自适应地
14、调整分块的大小，然后在各个分块中采用三角网格生长算法对块中数据进行三角剖分，实验结果表明该算法可以快速、有效地完成对点云数据的三角网格剖分。胡金星等人（2004）针对数字地形模型，以分治算法为基础提出了一种基于格网划分的三角网格剖分算法。董洪伟（2005）在基于增量扩散法的思想提出了一种三角网格重构算法，在进行第三点搜索时采用了探测邻域规则，提高了搜索效率。邓曙光、刘刚（2006）采用了直线分割式正负区的原理搜索第三点，每次只搜索点集中的部分点，在一定程度上提高了构网效率。邹徐文等人（2007）在分割-合并的思想的基础上，提出了一种基于AVL树的三角剖分算法，该算法通过与传统的三角网格生长算法
15、和基于四叉树的分治算法做了对比，表明该算法具有鲁棒性好、效率高等优点。刘少华等人（2007）针对逐点插入算法定位点与三角形位置效率低下的缺点，研究分析基于点边关系以及基于边边关系的方向定位算法，采用了一种基于这两种算法的一个改进算法，有效地提高了三角网格重构的效率。刑建业等人（2007）针对数字高程模型中快速定位点所在三角形的需求，提出了一种快速的定位算法。陈伟，刘肖琳（2009）提出了一种基于栅格化分的三角网格生长算法。该算法针对传统的三角网格剖分算法效率低下的缺点，采用空间栅格对散乱点云进行空间分割，然后对每个栅格内的数据进行分别处理。与传统的三角网格生长算法相比，该算法在重构效率方面有了极大的提高，实验结果方面也有所改善。张霞等人（2011）介绍了一种新的基于三角网格生长算法的方法对含噪点云数据进行曲面重构。文中使用手动的方法对噪声点进行消除，然后采用空间栅格方法对点云数据进行划分，在每个分割的区域中采用三角网格生长算法对点云数据进行三角剖分，最终完成对整个点云数据集的曲面重构。聂建辉等人（2012）针对大规模散乱点云数据提出了一种快速的三维重构算法。该算法类似与三角网格生长算法，首先建立一个三角网格闭环（六边形），然后对其进行扩展构建初始的近似网格曲面，之后在对其进行细分割，并采用了B样条曲线对生成的点云数据进行层次优化。梁群仙（2013）针对三维扫描得到的规则的采样点
