《空间散乱点曲面重构的三角剖分技术研究》由会员分享，可在线阅读，更多相关《空间散乱点曲面重构的三角剖分技术研究（62页珍藏版）》请在金锄头文库上搜索。
1、南京航空航天大学 硕士学位论文 空间散乱点曲面重构的三角剖分技术研究 姓名：孙存亮 申请学位级别：硕士 专业：机械设计及理论 指导教师：陈炳发 20090101 南京航空航天大学硕士学位论文 i 摘 要 逆向工程中曲面重构是一种被广泛采用的技术，曲面重构的关键步骤是散乱点云的三角网 格划分。如何在数以万计的数据点中寻找出点云数据间的拓扑关系，并且用三角网格把这种拓 扑关系表现出来，需要把散乱点云划分成高质量的三角网格，才能准确，细致，贴切的还原出 物体的原始表面模型。 本文研究空间散乱点的直接三角剖分技术， 算法的时间复杂度为 O(KN)， 得到了较高质量的三角网格模型，主要工作如下： 本文首
2、先介绍了课题的研究背景，散乱点云测量与分类，总结了目前平面和空间三角剖分 研究领域中的各种典型算法，对空间散乱点 k 邻域搜索技术进行了研究，探讨了八叉树， K-D 树和空间划分策略中利用 Hash 函数定位的 k 邻域搜索算法，深入研究了 Hash 函数在空间划分 策略中的 k 邻域算法，把不含数据点的包围盒设置成已处理来提高其搜索效率。着重研究了空 间散乱点的直接三角剖分技术，以空间局部三角网格生长法为算法主线提出了种子三角形坐标 极限端点选取法，考虑三角网格生长中出现的各种情况，结合 Delaunay 三角剖分准则，采用角 度约束，孔洞判断，法向量约束，空间重叠判断等多种约束判断条件对三
3、角网格的生长加以优 化，使用优化的空间散乱点直接三角剖分算法进行三角网格模型构建，并给出实例，验证算法 可行性。 关键词：关键词：逆向工程，散乱点云，包围盒，三角剖分，网格模型 空间散乱点曲面重构的三角剖分技术研究 ii ABSTRACT The important technology of reconstructing of surface in Reverse Engineering, the key process in reconstructing of surface is the triangulation of scattered point cloud, How to fin
4、d the topological relation in Millions of scattered data point, and make the topological relation in triangular mesh, which need to divide the scattered point cloud to high quality triangular mesh, could restore the initial surface model precise, detail and good. The text researched the direct Trian
5、gular Mesh technology of space scattered point, the algorithms time complexity is O(KN),obtained a higher quality Triangular Mesh model, Following are the primary works. This paper first introduces the research background subject, the classify and measure of the scattered point cloud, summarizes the
6、 various kinds typical algorithms in planar and spatial field at present, then researches the k-nearest neighbor search technique of the spatial scattered point, probes the k-nearest neighbor search technique of the octree, K-Dtree and the Hash function which based on the spatial scattered point, in
7、tensive studies the k-nearest neighbor search technique of the Hash function in spatial scattered point. Sets the ambient-box into having Processed which having no points, improved the efficiency of search. Primary studied the direct triangulation technique of spatial scattered point, proposed the e
8、ndpoint of limits of seed triangle choice method based on spatial local growth methods of triangular Mesh, pondered the cases in the triangular method process, combined the Delaunay triangulation standard, adopted the angle, distance, normal vector and Overlapping Spaces constraint and judge conditi
9、ons to Optimize the growth of triangular Mesh, by this method to construct the triangular Mesh model at last, gave the example validated the Algorithms is viability. Key Word：Reverse Engineering, Scattered Point Cloud, ambient-box, Triangulation, Mesh Model 南京航空航天大学硕士学位论文 v 图、表清单 图 1.1 数据获取方法分类.2 图
10、2.1 Delaunay 三角剖分(实线)和 Voronoi 图(虚线).6 图 2.2 三角形及其法矢量.9 图 2.3 0 维、1 维、2 维、3 维单纯形.11 图 3.1 八叉树编码规则举例.17 图 3.2 二维K-D树及其记录的表示.19 图 3.3 二维K-D树的空间划分表示.19 图 3.4 K-D树搜索算法流程图.20 图 3.5 小正方体包围盒.22 图 3.6 顶点结点和邻接结点.23 图 3.7 K邻近的数据结构图23 图 3.8 Hash 函数定位搜索的K邻域流程图23 图 4.1 三角网格构建流程图.25 图 4.2 边界边与边界环.26 图 4.3 扩展点选择的基
11、本原则.27 图 4.5 右手螺旋法则保证法向量指向.28 图 4.6 种子三角形构造流程图.29 图 4.7 过渡平稳的三角形更可取.30 图 4.8 边界边更新与法向量夹角.31 图 4.9 孔洞被填补的情形.32 图 4.10 二维中的距离约束表示.33 图 4.11 最优扩展点与有向线段位置判断.34 图 4.12 逆时针生长保证待扩展点与待扩展边所对顶点分属其两侧 .35 图 4.13 最优扩展点与三角形位置判断.36 图 4.14 凸包与内点.36 图 4.15 边链更新示意图.37 图 4.16 边链更新流程图.37 图 4.17 三角网格生长.39 图 4.18 空间散乱点直接
12、三角剖分流程图.39 空间散乱点曲面重构的三角剖分技术研究 vi 图 5.1 OpenGL 图形的操作步骤 41 图 5.2 可视系统功能框架.45 图 5.3 螺母点云，网格模型和光照模式.46 图 5.4 保龄球点云，网格模型和光照模式.47 表 4.1 算法的时间复杂度比较.40 表 5.1 OpenGL 中的基本图元定义常量.43 承 诺 书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。 对本论文所 涉及的研究工作做出贡献的其他个人和集体， 均已在文中以明
13、确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件， 允许 论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书) 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 第一章 绪论 1.1 研究背景 Delaunay 三角剖分在许多领域得到广泛应用，逆向工程(Reverse Engineering)中散乱点云的 三角网格模型重建，地理信息系统 GIS1(Geographic Information Systems)中三角网数字地面模 型 TIN(Triangulated
14、Irregular Network)三角化的研究等都对散乱点的三角剖分提出了要求。目前 在 GIS 中，按地形数据采样的分布情况，对 TIN 点三角化分为三大类，不规则分布数据三角剖 分，规则分布数据三角剖分，基于等高线采样数据的三角剖分。其中不规则分布数据点情况普 遍存在，本文所研究的内容属于逆向工程中不规则分布数据的三角剖分技术。逆向工程是一个 从实物样件获取产品数学模型的技术，它已经发展成为 CAD/CAM 中一个相对独立的范畴。广 义的逆向工程包括形状反求，工艺反求和材料反求等诸多方面，是一个复杂的系统工程。目前， 大多数有关逆向工程的研究都集中在几何形状，即重建产品实物的表面模型方面
15、。 现阶段逆向工程中散乱点集所采用的曲面重构模型主要分为：矩形参数域(NURBS)曲面2 和三角参数域(BEZIER)曲面3。基于 NURBS 曲面重构的局限性很多，本文采用曲面重构中三 角域的方法。曲面重构算法大致可以分为两类一类是属于计算机图形学领域，一类是属于计算 几何领域。两类算法的主要区别在于最后产生的曲面是否完全地并且是精确地经过采样点。计 算机图形学领域中的算法着重于产生三维曲面来逼近原始曲面，也就是说，结果曲面并非精确 地经过每一个采样点。 而计算几何领域的算法通常是采样 Delaunay 三角化的一个子集来代表结 果曲面，根据 Delaunay 三角化的性质，每一个采样点都会
16、精确地落在最后产生的曲面即三角网 格面上。 目前在通过三角网格构造连续光滑的曲面研究方面已有多种较为成熟的算法4，但是对如 何得到三角网格 T，如何将数据点三角化，特别是对三维散乱数据的三角化一直是整个问题的 难点与瓶颈，对它的研究还很不成熟，还没有达到实用化点程度5。本文正是对空间散乱点曲 面重构中三角剖分技术展开研究，研究一种适应性强，网格模型比较贴切的三角剖分方法。 1.2 散乱点三角剖分研究目的和意义 所谓散乱数据的三角剖分，就是给定一组散乱点，将各数据点以三角形相互连接，形成一 张三角网格，以三角网格反映数据点与其邻近点间的拓扑连接关系。正确的拓扑连接关系将有 效的揭示散乱数据集所蕴涵的原始物体表面的形状和拓扑结构。 目前用于获取物体三维数据的测量方法有很多14，可分为两大类：接触式与非接触式，如 图 1.1 所示。接触式测量方法主要有坐标测量机和机械手；非接触式测量根据测量原理的不同， 空间散乱点曲面重构的三角剖分技术研究 2 大致有光学测量、超声波测量、电磁测量等方式。 测 量 点 的 获 取 触碰方式 非触碰式 触
