基于样点拓扑邻域的散乱点云曲面重建

论文摘要

散乱点云曲面重建作为逆向工程的核心技术,是逆向工程与CAD/CAE/CAM以及快速原型等先进制造技术进行衔接与集成的重要纽带。本文深入系统地研究了散乱点云曲面重建方法,提出两种基于样点拓扑邻域的插值曲面重建算法,使曲面重建在效率和质量上都得到了有效提高。主要研究内容与研究成果如下：1)提出适合于存储点、边、三角网格等任意几何单元的动态空间索引结构AMBB （Approximate Minimum Bounding Box）树。求解几何单元的近似最小包围盒,并实现了近似最小包围盒的相关几何运算,将近似最小包围盒与N叉树相结合,构建了新的动态空间索引结构AMBB树。实验证明,该索引结构具有数据适应性强、存储空间利用率大和空间查询效率高等特点。2)提出一种高效的散乱点云Voronoi图增点分裂重组算法。采用“点-面-体”数据结构存储Voronoi单元,初始化首点Voronoi单元,通过单元分裂与单元重组快速生成新增点的Voronoi单元并完成其相邻单元的维护。实验证明,该算法可快速准确地生成任意散乱点云的Voronoi图。3)提出样点拓扑邻域查询算法。构建散乱点云的AMBB树动态空间索引结构,基于该结构提出自适应扩展空心球算法查询样点的k近邻数据,通过偏心扩展和自适应扩展获取样点拓扑邻域参考数据,生成该局部点集的Voronoi图,获取样点拓扑邻域数据。实现了任意复杂散乱点云中样点拓扑邻域数据的准确查询,为实现散乱点云曲面重建提供了有效保障。4)提出两种基于样点拓扑邻域的插值曲面重建算法：a)查询样点的同层拓扑邻域数据,从中获取满足条件的匹配点,通过增量扩展实现散乱点云曲面重建,该算法可生成无隙曲面模型,有效解决了非均匀点云易产生非工艺孔洞的问题,对于工艺孔洞区域基于提出的边长过滤条件进行抠洞处理,以满足工艺要求；b)将提出的散乱点云Voronoi图快速构建方法应用于Cocone算法,并针对Cocone算法在采样过疏区域出现的孔洞问题采用提出的基于样点拓扑邻域的增量扩展算法进行补洞处理,使Cocone算法在曲面重建效率和质量上都得到有效提高。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究意义
• 1.2 曲面重建算法的研究现状
• 1.2.1 零集法及相关改进算法
• 1.2.2 基于局部增量扩展的三角网格曲面重建算法
• 1.2.3 基于Delaunay全局剖分的三角网格曲面重建算法
• 1.3 现有曲面重建算法存在的问题
• 1.4 本文主要研究内容与研究方案
• 第二章 AMBB树的研究与应用
• 2.1 引言
• 2.2 近似最小包围盒的定义与相关运算
• 2.2.1 几何单元的近似最小包围盒表示
• 2.2.2 构造近似最小包围盒
• 2.2.3 近似最小包围盒求并
• 2.2.4 算法时间复杂度分析
• 2.2.5 应用实例
• 2.3 近似最小包围盒聚类分簇
• 2.3.1 近似最小包围盒相似性
• 2.3.2 近似最小包围盒分簇
• 2.3.3 分簇中心的计算
• 2.3.4 结束分簇
• 2.3.5 算法时间复杂度分析
• 2.3.6 应用实例
• 2.4 AMBB树构造算法的研究与应用
• 2.4.1 AMBB树的定义
• 2.4.2 AMBB树构造算法概述
• 2.4.3 选择子树
• 2.4.4 结点分裂
• 2.4.5 结点调整
• 2.4.6 全局优化
• 2.4.7 算法时间复杂度分析
• 2.4.8 应用实例
• 2.5 结论
• 第三章 样点拓扑邻域查询
• 3.1 引言
• 3.2 范围查询
• 3.2.1 样点所在结点的查询
• 3.2.2 范围查询
• 3.3 k近邻查询
• 3.3.1 算法流程
• 3.3.2 构造初始空心球
• 3.3.3 范围查询
• 3.3.4 获取k近邻点
• 3.3.5 自适应扩展空心球
• 3.3.6 算法时间复杂度分析
• 3.3.7 应用实例
• 3.4 拓扑邻域查询
• 3.4.1 三维散乱点集Voronoi图的生成
• 3.4.2 样点拓扑邻域数据查询
• 3.5 结论
• 第四章 散乱点云曲面重建
• 4.1 引言
• 4.2 基于样点拓扑邻域的网格增量扩展算法
• 4.2.1 同层拓扑邻域数据的概念及获取
• 4.2.2 算法过程描述
• 4.2.3 抠洞处理
• 4.2.4 算法时间复杂度分析
• 4.2.5 应用实例
• 4.3 基于样点拓扑邻域的Cocone改进算法
• 4.4 结论
• 第五章 全文总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 攻读硕士学位期间的科研成果
• 致谢