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

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

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展望

参考文献

攻读硕士学位期间发表论文

致谢