网格分割算法和相关技术研究

论文摘要

随着计算机技术及测量技术的发展,利用CAD/CAM技术、先进制造技术来实现产品实物的逆向工程,已成为CAD/CAM领域的一个研究热点。逆向工程是将实物转化为CAD模型的数字化技术。利用现代测量设备,可以获得实物的点云数据。点云数据的三角化,可以获得原实物的三角网格数据。三角网格数据保留了点云数据的几何,并从三角化上推导点云数据代表实物的拓扑性质。对于点云数据和三角网格数据的处理算法,是数字几何处理、图形学、数学和计算机科学等学科共同关注的研究领域,具有重要的理论意义和实用价值。本文首先简单回顾了逆向工程的发展、测量数据处理技术等相关内容。然后在网格分割算法这个重要研究方向上,讨论了分割形式、特点和分割效果判别等问题,并对一些相关的算法和技术研究进行了分析和阐述。针对逆向工程的造面功能,根据造面和二次曲面识别的特点,探讨了特征区域识别和无缝自动分割两格分割形式和算法实现,研究了工程软件在分割功能实现上的一些问题。在特征区域识别的网格分割形式上,本文做了以下工作:●提出了一个基于分水岭原理的网格分割算法。算法准确标识网格特征区域,将网格分割成曲率变化平缓的分片。分割得到的分片可以用于逆向工程二次曲面识别和曲面逼近。●根据分水岭分割算法基于网格顶点离散曲率的特点,分析了已有的噪声网格离散曲率计算方法和网格光顺算法,指出了原有方法的不足,解决了噪声网格分割的鲁棒问题,同时保持分割算法简易、实用、快速的特点。相对于网格光顺预处理后分割,本文提出的噪声网格分割方法,具有无需指定特定参数,无需用户交互判断网格噪声等优点。相对于使用“法向量投票”等噪声鲁棒的曲率计算方法,本文的方法具有运算量小,无需指定相关参数的优点。和分水岭算法框架结合,满足了逆向工程软件特征区域识别分割网格功能的要求。在无缝自动分割网格的形式上,本文做了以下的工作:●在基于简化网格参数化的基础上,提出了新的关键算法,应用网格边收缩技术于网格参数化。●全局光顺网格参数化提出了边穿越算法,以提高参数化光顺效果。本文在这个算法启发下,提出了利用参数化映射结果直接构建网格边穿越结果的算法。●根据上述新算法的结果,本文提出利用边穿越结果,在原网格边插点,并重新分割网格的算法。这一系列新算法和结果,被应用到逆向工程软件自动分割网格造面的功能中。不同于以往的基于简化网格的参数化,本文利用边收缩的主流网格简化技术代替以往算法中常用的点移除重新三角化的技术。这样可以更好地构建简化网格基域,简化网格三角形形态更好,参数化结果更为光顺。相对于全局光顺网格参数化(Globally SmoothParameterization,GSP),本文提出的基于参数化映射直接构造边穿越结果的算法,简单、快速、鲁棒。这些算法技术也可以应用于构建参数化方程组。利用这些结果,本文提出插点,重新三角化和映射新增网格顶点的算法,无缝分割原始网格。分割得到的网格分片,形态是三角形的。在简化网格上实行合并聚类,对应地聚类三边网格分片为同胚于四边形的分片,用以构造无缝光顺邻接的曲面片。相较于以往的参数化算法,本文的方法无需求解复杂的线性方程组,也无需根据参数化结果逆映射。本文还给出了新参数化在重网格化和网格变形中的应用和实验结果。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景和意义
• 1.2 相关研究
• 1.2.1 网格分割算法
• 1.2.2 网格离散曲率计算方法
• 1.2.3 网格去噪光顺方法
• 1.2.4 几何逼近算法及误差分析
• 1.2.5 基于简化网格的参数化
• 1.3 本文研究内容与主要贡献
• 1.4 本文章节组织
• 第2章 基于分水岭原理的网格分割
• 2.1 引言
• 2.2 相关工作
• 2.3 分割算法框架
• 2.3.1 分水岭高度函数定义
• 2.3.2 特征区域、特征边标示和聚类网格面片
• 2.3.3 特征区域聚类后处理
• 2.3.4 再分割、手动编辑功能
• 2.4 实验结果
• 2.4.1 分割结果实例
• 2.4.2 分割造面过程
• 2.5 本章小结
• 第3章 噪声网格的鲁棒分水岭分割
• 3.1 问题提出
• 3.2 相关工作
• 3.2.1 网格顶点的曲率计算
• 3.2.2 网格光顺算法
• 3.3 几何拟合（Geometric Fitting）的基本理论
• 3.3.1 问题定义
• 3.3.2 线性约束优化问题和KCR下限
• 3.3.3 典型的线性约束式
• 3.4 噪声鲁棒的曲率计算方法
• 3.4.1 曲率计算对噪声网格分割的影响
• 3.4.2 算法介绍
• 3.4.3 算法流程和分析
• 3.4.4 误差公式设计
• 3.5 实验结果
• 3.6 本章小结
• 第4章 应用边收缩的网格参数化
• 4.1 引言
• 4.2 相关工作
• 4.2.1 网格简化算法和技术
• 4.2.2 基于简化网格的参数化算法
• 4.3 相关概念和算法标记
• 4.4 应用边收缩技术的网格参数化算法
• 4.4.1 算法流程和总体框架
• 4.4.2 构建收缩网格边的保角映射
• 4.4.3 直接边归类算法
• 4.4.4 处理边收缩简化算法新增网格顶点的映射
• 4.4.5 原网格特征线的保持
• 4.5 实验结果和讨论
• 4.5.1 算法复杂度分析
• 4.5.2 实验结果
• 4.6 本章小结
• 第5章 基于参数化的网格分割
• 5.1 引言
• 5.2 相关工作
• 5.2.1 利用参数化结果的分割造面算法
• 5.2.2 MAPS逆映射
• 5.3 基于参数化技术的网格分割
• 5.3.1 算法描述的符号和标记
• 5.3.2 算法框架
• 5.3.3 利用边归类结果插点
• 5.3.4 聚类分割
• 5.4 实验结果
• 5.5 本章小结
• 第6章 总结和展望
• 6.1 论文总结
• 6.2 进一步工作的展望
• 参考文献
• 攻读博士学位期间主要的研究成果
• 致谢
• 作者简历