三角网格曲面重建及求交理论、方法研究

论文摘要

本文深入系统地研究了三角网格曲面重建及其求交理论方法,实现了网格边界扩展与局部三角剖分相结合的三角网格曲面重建,并基于动态空间索引机制提出高效的三角网格曲面求交算法,对提高新产品开发效率与质量具有重要意义。主要研究内容与研究成果如下:1)引入k-means算法提出适合于各种三维空间数据对象分簇的四维聚类分簇算法,以此为基础提出R*S-tree构建理论方法,研究散乱数据点云等数据对象的动态空间索引机制,基于该机制实现样点拓扑邻域数据快速查询。实例证明R*S-tree动态空间索引机制具有复杂数据适应性强、存储空间利用率大及空间查询效率高等优点。2)提出基于散乱数据点云动态空间索引机制的三角网格曲面重建算法,为快速获取同产品型面拓扑一致的网格模型,该算法利用局部邻域点集Delaunay三角剖分在邻域点集上构造同产品外形拓扑一致的网格,通过已构造网格边界的膨胀、分裂及自裁剪实现网格扩展,完成三角网格曲面重建。实例证明本文提出的三角网格曲面重建算法能保证重建质量,且有效重建了产品各种细节特征。3)提出一种高效的三角网格曲面求交算法,基于三角网格曲面模型动态空间索引机制,根据各层结点包围盒相交检测实现网格曲面相交区域快速定位,采用改进的三角面片求交算法求解离散交线段数据,通过建立交线段动态空间索引结构提出交线快速跟踪提取算法,实现三角网格曲面求交,为基于三角网格曲面的各种几何操作奠定了基础。实例证明该求交算法复杂型面数据适应性强,可有效提高三角网格曲面求交效率。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 引言
• 1.2 三角网格剖分算法研究现状及存在问题
• 1.2.1 三角网格剖分算法研究现状
• 1.2.2 常用三角网格曲面剖分算法存在的问题
• 1.3 三角网格曲面求交算法研究现状及存在问题
• 1.4 本文主要研究内容及研究方案
• 第二章 数据对象动态空间索引机制及其理论、方法研究
• 2.1 引言
• 2.2 R*-tree作为各种数据对象统一空间索引结构的可行性研究
• 2.2.1 R*-tree的相关概念
• 2.2.2 R*-tree作为逆向工程空间数据对象索引结构的优越性
• 2.2.3 R*-tree作为逆向工程空间数据对象索引结构的局限性
• 2.3 空间数据对象R*S-tree索引结构及构造算法研究
• 2.3.1 离散空间数据对象R*S-tree构建原理
• 2.3.2 选择子树算法描述
• 2.3.3 结点MBR调整
• 2.3.4 四维聚类分簇算法描述
• 2.3.5 结点插入算法描述
• 2.3.6 算法复杂度分析
• 2.3.7 空间数据对象R*S-tree整体结构设计
• 2.4 R*S-tree与R*-tree比较
• 2.4.1 建树时间及结点重合区比较
• 2.4.2 R*S-tree与R*-tree复杂数据适应能力比较
• 2.5 基于R*S-tree的散乱数据点云k近邻查询算法研究
• 2.5.1 相关概念
• 2.5.2 动态空心球区域增长算法描述
• 2.5.3 R*S-tree动态空心球区域增长范围查询算法
• 2.5.4 算法复杂度分析
• 2.5.5 应用实例
• 2.6 本章小结
• 第三章 散乱数据点云三角网格曲面重建理论、方法研究
• 3.1 引言
• 3.2 局部Delaunay三角剖分
• 3.2.1 微切平面求解及点集参数化坐标计算
• 3.2.2 二维点集的Delaunay三角剖分
• 3.3 散乱数据点集Delaunay三角剖分
• 3.3.1 算法的相关概念
• 3.3.2 网格扩展算法描述
• 3.4 算法实现
• 3.5 算法分析
• 3.5.1 算法时间复杂度
• 3.5.2 网格构造质量
• 3.6 应用实例
• 3.7 本章小结
• 第四章 三角网格曲面高效求交算法研究
• 4.1 引言
• 4.2 算法概述
• 4.3 离散交线数据获取算法研究
• 4.3.1 目标三角面片相交数据的获取
• 4.3.2 三角面片交线段求解
• 4.3.3 算法复杂度分析
• 4.4 交线跟踪提取算法研究
• 4.4.1 下一条跟踪交线段获取
• 4.4.2 交线跟踪提取过程
• 4.4.3 算法复杂度分析
• 4.5 应用实例
• 4.6 本章小节
• 第五章 全文总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 攻读硕士学位期间发表论文
• 致谢