（航空宇航制造工程专业论文）三角网格模型的孔洞修补及b样条曲面拟合.pdf

南京航空航天大学硕士学位论文 摘要 在逆向工程通过测量海量数据建模中，由于零件局部遮挡成测量手段的限 制，所获得的三角网格横烈中往往存在数据缺失，形成孔洞，因而需要对孔洞 进行修补以形成完整的零件模型。同时，为了便于零件的改型设计及其他的后 续应粥，霭迄三热薅搀搂鍪转 皂为参数纯款巍滢b 襻条蔻嚣摸爨。本文霹三夤 丽捂模爱上的孔洞修补及分片光滑b 样祭魏蕊的毅合技术遗行了研究。主要上 作如下： 在三角网格孔洞修补技术的研究基础上，设计了一种简易有效的平面封 闭孔洞修补算法，提出了一种基于曲率的空间封闭孔洞的修补算法，并 霹瑟瘸获魏滠懿骖 进嚣了磺究。 研究了矩形送城内数据点的重新均匀采样以及光滑分片b 样条曲面的 拟合问题。提出了种空间四边界区域的均匀采样方法以及基于力平衡 原理的采样点均匀分布优化方法，嶷域了三角网格模型的重新均匀采样 和参数化。在此熬蠢蛙 上，实现了三麓网格模型的光滑b 样条曲面的拟 合。 设计并实现了稽疵软件模块，并辩上述算法迸行了实例验证。 关键字；逆向工程，三角网格，孑l 洞修 ，参数仡，b 榉条鳆嚣，曲露羧合 三角 嘲格模型的孔洞修补及b 样条曲面拟合 a b s t r a c t i nt h ep r o c e s so fm o d e lr e c o n s t r u c t i o nw i t hm e a s u r e dd a t ac l o u di n r e v e r s e e n g i n e e r i n g ，t h e s ea r eo f t e nd a t al o s eo w i n g t op a r t i a lc o v e r i n go ft h ep a r to rl i m i t o ft h em e a s u r i n gi n s t r u m e n tw i t h i nt h ea c q u i r e dt r i a n g u l a rm e s hm o d e l t h e s eh o l e s m u s tb er e p a i r e dt of o r mc o m p l e t em o d e lo ft h ep a r t a tt h es a m et i m e ，w en e e dt o t r a n s f o r mt r i a n g u l a rm e s hm o d e lt op a r a m e t e r i z e ds m o o t hb - s p l i n es u r f a c e si no r d e r t o r e d e s i g nt h ep a r to ro t h e rc o n s e q u e n ta p p l i c a t i o n h o l er e p a i r i n g i n t r i a n g u l a r m e s hm o d e l sa n dp i e c e w i s es m o o t hb s p l i n es u r f a c e sf i t t i n gh a v eb e e ns t u d i e di n t h i sd i s s e r t a t i o n t h ef o l l o w i n ga r et h ep r i m a r yc o n t e n t s ： o nb a s i so fh o t e r e p a i r i n gr e s e a r c hi nm e s hm o d e l sas i m p l ea n de f f e c t i v e a l g o r i t h m o fh o l e r e p a i r i n g f o r p l a n a r c l o s e dh o l e si s d e s i g n e d ，a n d a n a l g o r i t h mo f c u r v a t u r e * b a s e dh o l er e p a i r i n gf o rt h r e e d i m e n s i o n a lc l o s e dh o l e s i s p r e s e n t e d ，i na d d i t i o n ，t h ea l g o r i t h mo fh o l er e p a i r i n gf o ri s l a n d h o l e si s s t u d i e d t h i su n i f o r mr e s a m p l eo fd a t ap o i n t si n r e c t a n g u l a rr e g i o n a n d f i t t i n g o f p i e c e w i s e s m o o t h b * s p l i n e s u r f a c e sa r e e x p l o r e d 。au n i f o r m l ys a m p l i n g a l g o r i t h mo f t h r e e d i m e n s i o n a ls e g m e n t e dq u a d r i l a t e r a lb o u n d a r yd o m a i na n d a nu n i f o r m l yd i s t r i b u t e d s a m p l i n gp o i n to p t i m i z e d m e t h o db a s e do nf o r c e e q u i l i b r i u ma r ep r e s e n t e d t h e no nb a s i so f t h ea b o v er e s e a r c h e s ，t h es m o o t h b s p l i n es u r f a c ef i t t i n gi si m p l e m e n t e d 。 t h er e l a t e ds o f t w a r em o d u l e sa r ed e s i g n e da n di m p l e m e n t e da n dt h ea b o v e a l g o r i t h m sa r e v e r i f i e dw i t hs a m p l e s k e y w o r d s ：r e v e r s ee n g i n e e r i n g ，t r i a n g u l a rm e s h ，h o l er e p a i r i n g ，p a r a m e t e r i z a t i o n ， b s p l i n es u r f a c e s ，s u r f a c ef i t t i n g 南京航空航天大学硕士学位论义 第一章绪论 1 - 1 逆向工程中的曲面重建技术 逆向工程在设计制造、生物医学、地理信息及计算机动画等领域已得到广泛 的应用。逆向工程的关键是根据测量所得的反映几何形体特征的一系列离散的数 据点，建立c a d 模型，目前大多数为表面模型。由于如汽车、飞机等制造产品 的表面多为自由曲面，难以用精确的数学模型来表示，所以自由曲面成为设计制 造领域逆向工程中曲面重建的研究重点。在逆向工程中，曲面重建有如下一些特 点： 1 ) 测量数据点大多是密集的“点云”数据，数据量极大。 2 ) 测量数据点散乱，曲面边界和形状常常也很复杂，难以用常规方法直接 构造。 3 ) 曲面对象往往不是简单地由一张曲面构成，而是由多张曲面经过延伸、 过渡、裁剪等生成，必须进行分块构造。 4 ) 受到测量条件的限制，数据采集要分块进行。另外，为了保证数据采集 的完整性，各测量块之间数据有一定的重叠，必须进行多测量块之间数据的融合。 因此，曲面重建的研究内容一般包括下面几个方面： 1 ) 数据预处理：根据具体采用的测量方法，对测量数据进行测头半径补偿、 噪声数据处理、多视拼合等。 2 ) 数据分块：实际的曲面对象往往是由多个不同类型的表面共同构成的， 采用一个曲面表示是不可能的，因此，要进行边界检测，曲面特征线的提取，据 此将曲面对象分成多片单张曲面进行拟合，最后进行整体拼合。 3 ) 数据优化：压缩不必要的数据点，确定合适数量的反映曲面拓扑特征的 测量数据点，以减少后期数据处理。 4 ) 曲面模型生成：建立数据点的拓扑关系，生成构造曲面的要素，建立曲 面模型。 目前，重建的曲面模型有两类 2 】【3 1 ，一类是离散网格模型，如三角网格或 四边形网格模型；另一类是参数曲面模型，如b 样条、非均匀有理b 样条 ( n o n - u n i f o r m r a t i o n a l b - s p l i n e ，n u r b s ) 或三角域b e z i e r 曲面模型等。 对于离散网格模型，三角网格模型是一种较常用的表示重建结果和拓扑结构 的模型，它是由三维空间中的三角形通过边和顶点连接而成的分片线性曲面，其 中每条边最多包含在两个三角形中。它的定义相对比较简单，对于复杂拓扑的几 何形状的描述能力强，用三角网格来表示模型的各个曲面不仅可以获得较好的 视觉效果，而且还可以通过控制模型中的三角片的数量来得到不同需求下的三维 三角阐格模型的孔洞修补及b 样条曲面拟台 网格模型，并在某些数控加工算法和快速原型成型( r a p i dp r o t o t y p i n g m a n u f a c t u r i n g r p m ) 等方面有着重要的应用。但是三角网格模型一般存储最大、 光滑性较差、不易修改。另外，这种模型侧重于对离散点的分割，即是一种“自 底向上”的过程，没有从宏观上考虑其c a d 特性，不能满足有较高连续性的零 件，因此，象汽车覆盖件这种对外形审美要求很高的零部件的重建结果就不能用 三角网格模型表示。 随着有限元在工程上的广泛运用，网格生成技术越来越受到了人们的重视。 对 二平面三角形网格的生成方法，比较成熟的是基于d e l a u n a y 准则的一类网格 剖分方法( 如b o w y e r - w a t s o na l g o r i t h m 和w a t s o n sa l g o r i t h m ) 和波前法 ( a d v a n c i n gf r o n tt r i a n g u l a t i o n ) 的网格生成方法：另外还有一种基于梯度网格 尺寸的三角形网格生成方法，这一方法还处于发展当中。基于d e l a u n a y 准则的 网格生成方法的优点是：生成速度快，网格的尺寸比较容易控制。缺点是：对边 界的恢复比较困难，很可能造成网格生成的失败。波前法的优点是：对区域边界 拟合的比较好，所以在对区域边界要求比较高的情况下( 如流体力学中) ，常常 采用这种方法。它的缺点是：区域内部的网格生成的质量比较差，生成速度比较 慢。曲面三角形网格生成方法主要有两种，一种是直接在曲面上生成曲面三角形 网格；另外一种是采用结构化和非结构化网格技术偶合的方法，即在平面上生成 三角形网格以后再投影到空间曲面上，这种方法会造成睦面三角形网格的扭曲和 局部拉长，因此在平面上必须采用一定的修正技术来保证生成的曲面网格的质 量。 相对而言，有限元分析精度较高的全四边形网格自动生成技术，仍显得不够 成熟。现有的方法大部分以成熟的三角形网格生成法为基础，通过单元合并，构 成四边形网格，其缺点是边界及区域内不可避免地存在一些三角形单元。只有少 数方法能直接生成四边形单元，如铺砌法( p a v i n g ) 、模板法、映射法等。四边 形网格生成算法的主要问题是对复杂区域的适应性差，自动化程度不高。 对于参数曲面模型，主要是以b s p l i n e 或n u r b s 曲面为代表的。这种曲面 重建的方法能够以较为简洁的形式统一表示各种几何形体，同时具有优良的局部 控制能力，已经成为几何造型中最为流行的技术，同时也是s t e p 国际标准中描 述产品几何形状的唯一方法。但是这种方法对测量数据点有较严格的要求：一是 要求以张量积的形式分布，二是测量数据点不能变化太剧烈，否则曲面的光顺性 得不到保证。在逆向工程中，型值点数据具有大规模、散乱的特点，因此实际的 产品模型很难满足这一要求。如果用这种重建方法不可避免的要对散乱数据点进 行区域划分，区域划分又带来了曲面片之间的光滑拼接问题。所以对散乱数据点 的区域划分和多片曲面的光滑拼接称为这种方法的关键。 三角域的曲面重建也是另一种较为重要的曲面重建方法。其中剥j 角域 b e z i e r 曲面的研究最多，它是将测量出来的空间数据点集用三角b e z i e r 曲面片表 示，进行产品模型的建立。三角域b e z i e r 曲面的构造主要包括下面一些步骤：( 1 ) 南京航空航天大学倾上学位论义 对测得的数据点进行三角剖分，并作必要的修正，以建立拓扑关系；( 2 ) 计算三 角网格边界条件，构造初始三角曲面：( 3 ) 构造整体g 1 连续的散乱数据插值曲 面。由于j 角域的曲面和通用c a d 系统中的曲面表示形式不兼容，因而其应用 收到了一定的限制。 1 2 国内外研究现状及论文选题依据 曲面重建是逆向工程中的关键技术之一。这一问题得到了美国、加拿大、欧 洲各国等许多国家学者的高度重视，九十年代以来，国际著名刊物c o m p u t e r a i d e dd e s i g n 、c o m p u t e rg r a p h i c s 、i e e ep a m i 等对逆向工程的研究报到明疆增 多。 目前基于测量数据的三角网格曲面模型重建的相关算法已经比较成熟，无论 对有规律的截面数据组织的测量点以及人工规划的测量点的曲面重建问题，还是 对完全无序的海量散乱点集的曲面重建问题，都有较好的解决方案。如h o p p e l 4 】 等人根据稠密的散乱点集自动计算法矢信息，用切平面线性逼近待重建曲面的局 部形状，然后利用实现等值面抽取的步进立方体( m a r c h i n gc u b e ，m c ) 算法输 出曲面的三角化模型。c h e n 5 1 直接判定三点形成的三角形的最小内角，应用最小 内角的最大原则建立测量点的三角化模型。周焰拍锵遗传算法应用到物体表面的 三角划分上，利用遗传算法能够在概率上达到全局最优，因而较好地解决了物体 表面三角划分的问题。 关于参数曲面模型的重建主要是以n u r b s 曲面的研究最为j 。+ 泛。逆向工程 中大多数采用样条曲面对几何模型进行重建，概括起来主要有四种方法：整体 逼近曲面模型，任意拓扑结构曲面模型、基于截面线的曲面模型及按功能分解 的曲面模型。整体逼近法首先构造一张四边界初始逼近曲面，然后通过解数据 点与逼近曲面间的距离平方和的最小二乘问题，经过反复迭代求出最终逼近曲 面的未知参数( 比如样条曲面上的控制顶点) ，再由数据集中获得曲面的边界信 息，最后用边界曲线剪裁逼近曲面，得到真正的重构曲面。这种方法相对简单， 用户干预少，但对不同拓扑结构的曲面适应性较差，只能近似于四边界域的情 况，不能用于复杂拓扑结构几何体的重建。任意拓扑结构曲面模型的基本思路 是：首先重建散乱测量数据的拓扑结构，然后构造出原始模型的三角网格模型， 在此基础上对三角网格模型进行自动分片( 一般是分片连续的四边界域) ，然后 对分片区域采样并且根据边界光顺性构造边界条件生成拟合曲面。这种方法的 主要优点是理论基础牢固，拓扑适应性强，自动化程度高，生成的样条曲面质 量高。主要缺点是散乱数据三角化的方法复杂，速度慢，且会丢失原有的部分 细节。基于截面线的曲面模型的思路是：首先对一组截面曲线排序以使每条截 面线的起点一致，然后在原截面线的基础上构造一组控制顶点数和阶数都相等 的曲线，作为重构曲面的等参数线，最后利用等参数线进行n u r b s 曲面拟合。 这种方法的主要缺点是只利用了部分测量数据，存在明显的不可靠因素，而且 三角网格模型的孔洞修补及b 样条曲面拟台 根据测嚣数据自动构造截面线本身就是十分复杂困难的，因此一一般需要人1 。交 互进行特征截面线的构造。按功能分解的曲面模型试图在曲面重建过程中理解 原始模型包含的设计意图，然后根据设计意图重建几何模型。这种方法从：【程 角度来说是最理想的，但是根据测量数据识别出原始模型的几何特征，并且生 成样条曲面，是十分困难的，有待于进一步的深入研究。 无论重建何种模型，测量数据的完整性是重建成功的关键。但在对样件的数 据实际采集中，由于零件本身的某些部分被损坏，会造成测量所得的三角网格模 型中存在孔洞。另外，由于夹具、光学贴片的遮挡会造成无法测得模型的完整的 数据，也会在网格模型中出现孔洞。网格模型中存在孔洞缺陷会影响许多后续操 作，例如，快速原型制造r p m 中输入的三角网格模型不允许存在孔洞，否则会 造成系统不能正常运行；在对三角网格模型的特性进行分析时，也不允许孔洞的 存在，否则会导致不正确的结果。因此有必要在应用前，对带有这些缺陷的三角 网格模型进行数据修复处理，以确保模型数据的完整性。 国内外学者对三角网格模型的孔洞修补技术已进行了不少研究。g u 7 】和孙 玉文 8 通过建立测量点云的神经网络结构，模拟出曲面其他点在某方向上的深 度信息，当给定网络的参数化信息时，应用三个神经网络可以生成修补数据在 三维空间的坐标值。d a v i s 9 1 将测量点处的曲面用体表示法( v o l u m e t r i c r e p r e s e n t a t i o n ) 来描述，并用扩散法在等值面上插入新的数据，实现三角网格 模型的复杂孔洞数据的修复。上海交通大学的田晓东f lo 提出了一种基于遗传算 法的网格孔洞技术，利用遗传算法多目标的优化特性，将三角面片的单体优化 程度和三角面片的整体光顺程度同时考虑，并且提出了独特的编码方法和适应 度函数，并对传统的遗传算法做了调整，但是其适应度函数只是利用孑l 洞边界 本身的顶点，并没有考虑在孔洞内部增加新的顶点。南京航空航天大学的张丽 艳j 提出了孔洞多边形特征面的概念，通过沿孔洞多边形构造新三角片，然后 在孔洞多边形特征面上对其进行方向合法性和位置合法性的检查，避免了狭长 和错误三角片的出现，由此获得三角片形状优化的修补结果。但是此算法对空 间孔洞多边形不接近平面多边形的那类孔洞的修补效果并不理想，同时算法也 较复杂。总的来说，大多数研究在修补孔洞时没有增加新的顶点，导致修补后 的三角面片并不优良，同时也没有很好的解决空间孔洞与相邻曲面片的光滑连 接问题，也没有涉及到岛屿状孔洞的修补，所以有必要对这个方面作一定的研 究。 由于三角网格模型没有固定的拓扑结构，要进行整体的光滑样条曲面拟合 往往是十分困难的。为此就需要对任意拓扑结构的三角网格曲面进行区域划分， 使得划分后的局部区域根据需要具有特定的拓扑结构，如四边界区域，然后就 可以对各个四边界区域进行参数化和曲面的光滑拟合。m a 旧通过向基曲面投影 的方法实现了散乱点的参数化，基曲面可以是平面、圆柱、c o o n s 曲面等任意可 参数化的曲面，但要求数据点在基曲面的局部有唯一的映射。e c k 0 3 1 和f i o a t er 1 4 1 南京航空航天大学坝土学位论文 通过建立一个三维三角网格向二维平面三角网格的映射，在二维平面上给出数 据点的参数值，再将其映射回三维三角网格中，解决了三角网格的参数化问题。 南京航空航天大学的张丽艳【巧1 研究了三角网格模型的四边界区域划分，提出了 三维三角网格到平面凸四边形域的参数映射及其逆映射算法，实现了叫边界区 域的重新采样和参数化。对于多张曲面的光滑拟合，就是求解在曲面拼接处连 续性约束下的数据点与拟合曲面间的距离的最d , - 乘。m i l r o y 【l 6 】通过建立满足 g l 连续的罚函数来实现了一种近似全局g 。连续的分片b 样条曲面的拟合方法。 k r u t h ”咖崔汉锋研究了散乱点在满足位置、切矢或曲率连续等约束条件的b 样条曲面拟合方法。 随着坐标测量设备的迅速发展，特别近年来激光扫描设备的发展，使得人 们能够快速、方便地获得实物模型上大量的测量数据。然而相应的软件却落后 于硬件的发展，如美国的s u r f a c e r 、v e r i s u r f r e v e n g ，英国的d e s a u l t ，法国 的s t r i m 等，目前在功能覆盖域、自动化、稳定性及可靠性等方面还不够成熟， 不同程度地存在各种各样的问题。 南京航空航天大学c a d c a m 工程研究中心从7 0 年代初期开始，一直从事 c a d c a m 技术的研究、开发与推广应用，完成了多项国家重点科技攻关项目、 国防科工委重点预研项目、航空总公司预研项目和江苏省科技攻关项目，加上 最近引进的国际著名的几何开发平台a c i s 以及购买的一台德国g o m 公司的 a t o s i i 流动式光学坐标测量机，使其软件开发站在更高的起点上。先后开发了 多种具有自主知识产权的c a d c a m 软件，在海量测量数据的预处理、三角网 格模型的生成、误差分析和自动三边界区域划分等领域都作出了有效的解决方 案。 1 3 本文主要研究内容及安排 作者通过广泛收集消化国内外相关资料，对逆向工程中的三角网格模型的 数据修复技术和分片光滑b 样条曲面的重构技术进行了深入的理论研究和应用 实践，并在a c i s 几何开发平台上用语言v c + + 6 0 加以实现。 本文主要研究内容如下： 第一章论述了逆向工程中的曲面重建技术，并由此引出了本文的选题依据 和研究内容。 第二章提出了一种基于曲率的三角网格孑l 洞修补的算法。主要对平面封闭 孔洞、窄间封闭孑l n s n 岛屿孔洞的修补进行了详细的阐述。 第三章研究了矩形区域内数据的参数化以及光滑拼接的b 样条曲面插值问 题，提出了一种基于矩形域的重新采样和参数化方法，同时还对分片b 样条曲 面的两阶段曲线反算法拟合进行了阐述，实现了分片光滑b 样条曲面的拟合。 第四章介绍了软件开发的环境和实现的方法。 第五章对本文工作的总结和后续工作的展望。 三角网格模型的孔洞修补及b 样条曲而拟合 本文研究工作得到了高等学校优秀青年教师教学科研奖励计划和航空科学 基金( 编号为0 3 h 5 2 0 5 9 ) 以及江苏省创新人才培养基金( 编号b k 2 0 0 1 4 0 8 ) 的 资助。 南京航空航天大学硕士学位论文 第二章三角网格模型的孔洞修补 i 角网格模型的描述较为简单，对坐标测量设备及模犁拓扑结构的适应性也 较强，且目前大多数c a d 造型系统都支持三角网格模型。三角网格模型所具有 的这些优点使得它在许多领域得到了广泛的运用，如计算机i 訇形学、计算机仿真、 逆向工程、数控加工的刀具轨迹计算和干涉检查、有限元分析、快速原型制造 ( r p m ) 、电影特技制作以及医用图像生成等。 一个完整的三角网格模型对于后续的曲面重建是非常必要的。但由于测量时 零件的局部遮挡或测量手段的限制，通过测量数据获得的三角网格模型中往往存 在数据缺失，形成孔洞。本章主要阐述了三角网格模型中三种不同类型的孔洞修 补技术，以恢复在数据测量中或因零件本身缺损而丢失的数据信息，这样修复后 的网格模型可作为其他后续操作的原模型。 2 1 测量数据的获取及组织结构 获取样件的三维几何数据的测量方法有很多，按照测量部件与被测样件的位 置关系，可以分为接触式和非接触式两大类。接触式主要包括基于力触发原理的 触发式数据采集和连续式数据采集，通过监测测头上的探针与样件表面的接触情 况进行数据采集。接触式方法对物体表面的颜色和光照没有要求，但对软质材料 难以测量。非接触式主要基于光学原理进行数据采集，典型方法有激光三角形法、 激光测距法、结构光法等，其特点是测量装置不与样件接触，因而可以有较高的 速度，并可以测量软质材料，但对物体的颜色和光照有较高的要求，测量方式决 定了它的精度较低，数据处理较复杂。按照能够获取物体不同部位的数据也可以 将测量方法分为两类，是能获得物体外表面的( 从外部可见的) 位置数据的方 法，例如坐标测量机法、激光三角形法、模式光法、图像分析法等方法；二是能 获得物体内部以及内表面数据的方法，例如工业c t ( c o m p u t e rt o p o g r a p h y ) 、医 学c t 、m r i ( m a g n e t i cr e s o n a n c ei m a g i n e ) 扫描以及层析扫描等方法。这些方 法在精度和速度上都存在较大的差异，但是从建模角度出发，更关心的是测量数 据反映的特征及其组织结构。 不同测量方法输出数据的常用组织结构如下 i9 ：( 1 ) 散乱点：无论采用何种 测量设备，如果使用了多次测量的策略，将导致数据在分布上不遵循特定的规则， 无明显的几何关系，则称这些点为散乱点，在测量整个零件的外表面时常会出现。 ( 2 ) 栅格点：在采用激光扫描仪和光学数字化仪测量时，测量点在扫描平面上 呈等距栅格状分布，数据点间具有确定的位置关系。( 3 ) 等值线：在采用c t 、 层析式设备等测量时，数据点沿某方向的一系列面簇与目标表面相交形成，如地 形等高线和头骨截面线。对于c t 设备而言，每层轮廓线的生成还需要对原始图 三角网格模型的孔洞修补及b 样条曲面拟合 像进行复杂的预处理，包括边缘提取、分析内外轮廓等工作。( 4 ) 特征点和线： 如零件上的规则面较多，就专n 测量相关的特征点，用以形成平面、圆柱、圆锥、 球等基本几何元素；而对于某些由运动学方程形成的复杂曲面，可测量其母线及 运动轨迹；对于那些完全没有生成规则的曲面还可以先按照交线进行分割，在每 块区域沿某个方向测量一些脊线，作为将来建模的依据。 2 2 三角网格模型中孔洞形成的原因及数据修复 三角形网格和三边域曲面重构方法适用于上述三类测量数据( 即散乱点、栅 格、等值线) 的建模，对数据几何结构特征无特殊要求，同时对复杂曲面结构具 有很大的灵活性，故广泛应用于数据的可视化、快速原型制造、仿形加工等领域。 一般情况下孔洞主要是由以下几个方面的原因引起的：( 1 ) 被测量样件本 身的某些部位已经损坏，造成测量数据的不完整，从而导致了7 l 洞的产生。( 2 ) 在测量过程中，有时会需要一定夹具或支撑，样件和夹具接触部位的坐标数据就 无法获得，也会产生孔洞。( 3 ) 采用光学法测量时，由于零件局部遮挡或光学贴 片的遮挡，也会产生孔洞。除此之外，一些正向设计软件中，在由曲面或者实体 模型产生三角网格模型时也会产生孔洞。据r o s c o e 在文献 2 0 1 中介绍，有约l 7 的s t l 文件存在孔洞等缺陷。 三角网格模型中的孔洞一般表现为三种情况：一是平面封闭孔洞，即孔洞边 界为一平面曲线，一般是由于工件底部放在工作台上无法测到而造成的，也无需 测出；二是空间封闭7 l 洞，一般是由于工件表面缺陷或测量时局部被遮挡而造成 的：三是岛屿状的孔洞，是由于工件表面一环状封闭带无法测量或其他测量原因 而引起的。如果不对这些孑l 洞进行修补，就无法获得完整的样件模型。 三角网格模型中的孔洞修补可以归结为一个空间多边形的三角剖分问题，国 内外许多学者( 7 。1 2 0 - 2 4 对此都进行了研究。但由于大多数算法在构造新三角片时 仅仅采用原有的孔洞多边形顶点，而没有增加新的三角片顶点，造成修补的网格 与周围的三角片不能光滑的过渡，因而难以获得较好的用于填补孔洞的三角片形 状，修补效果不够理想。c h u ac h e e k a i 【22 【2 3 】等人在对s t l 文件进行修补时略去 了三角片的拓扑关系，采用遍历算法来处理。这种方法虽然简单、明了，但却耗 费大量的时间，效率低。张丽艳【l l 】等人提出了一种空间多边形孔洞的修补算法， 该算法每次寻找三维孔洞多边形中夹角最小的一对邻边，在孔洞多边形特征面上 构造新三角片，然后更新孑l 洞多边形，直到新增三角片完全覆盖了原有的孔洞。 根据其算法可以获得三角片形状较为优化的修补结果，避免了狭k 及错误三角片 的出现。但是这种修补方法的前提是假设空间孔洞多边形接近平面多边形。另外 大多数文献没有考虑岛屿状孔洞的修复，这也是一个值得研究的问题。 在孔洞修补过程中，一个比较困难的问题是：一般我们并不知道模型样件上 孔洞所在部位的原来曲面的真实形状，那么就会存在修补后的曲面不能与周围相 邻的曲面片实现光滑的连接。所以我们要从这方面着手研究，使得修补后的孔洞 南京航空航天大学硕士学位论文 部分与整体模掣能够达到较好的光滑过渡。 2 3 平面封闭孔洞的修补 我们这里所讲的平面封闭孔洞是指组成封闭孔洞的所有边位于或者基本上 位于同个平面上。这是三角形网格模型孔洞类型中最为简单的一种，较为常见。 对t - f 面划闭孔洞的修补已有许多文献1 1 2 0 - 2 3 进行了研究，但由于大多数算 法在构造新三角片时仅仅采用原有的孔洞多边形顶点，而没有增加新的三角片顶 点，因而难以获得较好的用于填补孔洞的三角片形状，修补效果不够理想。本文 所用的平面封闭孔洞修补算法是在文献均基础上作了一定的改进，主要包括以 下三个方面：( 1 ) 孔洞多边形特征面的简化，避免了求解矩阵的单位特征向量的 过程。( 2 ) 孔洞多边形相邻边的最小夹角的查找，不需要先判断孔洞多边形的方 向后再计算每对邻边的夹角了，从而提高了效率。( 3 ) 新增三角片的构造，由原 来的四种情况改为现在的三种情况，因为实际的最小夹角不可能大于n 。本算法 主要分为孔洞多边形的检测与排序、确定孔洞多边形的特征面、构造新三角片、 新增三角片合法性检查等几个步骤。该算法同样可以避免狭长三角片和错误三角 片的出现，达到较好的修补效果。另外，也简化了程序的实现，缩短了运行的时 间。 2 3 1 孔洞多边形的检测与排序 考虑封闭结构的三角网格模型，如果网格模型中没有孔洞，那么该模型中的 任意一条边属于且仅属于两个三角片。如果存在某条边仅属于一个三角片，则该 条边是构成孔洞多边形的一条边，我们称之为边界边；如果某条边属于两个三角 片，则称该条边为内部边。由边界边首尾相连组成的封闭平面( 或空间) 多边形 称为孔洞边界。 按照上述边界边的定义，就可以找出三角网格模裂中所有的边界边。在软件 实现中，由于初始求得的边集是无序的，且可能存在多个孔洞，因此必须对其进 行排序和组织，形成若干条完整的边界。单个孔洞边界的数据结构是边界边的有 序链表，多个孔洞边界用链表的链表来组织。 孔洞边界边的分类和排序算法如下】： ( 1 ) 从初始边界边表e 中取出一条边e 1 加入新边表e ，并将其从e 中删 除； ( 2 ) 若e 中边的个数等于零，检查e 中的边是否封闭；e 若不封闭，则弹 出错误信息，退出排序和分类处理；e 若封闭，则完成了一个孔洞的排序，将e 加入孔洞链表，结束分类和排序： ( 3 ) 在e 中查找下一条边e 2 ，使得e l 的终点等于e 2 的起点； ( 4 ) 若找到这样的e 2 ，则将e 2 加入e 中，并将其从e 中删除。令e 1 等于 三角嘲格模型的孔洞修补及b 样条曲面拟合 i j i ；i i i j i ；j i i i i i i ；j i i i ；i i i i i i i i i ；i i i # e 2 ，返回( 2 ) ； ( 5 ) 若未找到这样的e 2 ，则检查e 中的边是否封闭：e 若不封闭， 错误信息，退l t 排序和分类处理；e 若封闭，则完成了一个孔洞的排序 加入孔洞链表后清空，返回( 1 ) 。 则弹出 将e 对于非封闭结构的三角网格，模型本身的边界与孔洞多边形样由仅属于一 个三角片的边构成，即由边界边构成。在软件实现的过程中，本文将经过排序的 边界逐条高亮显示，并由用户根据需要选择是否需要修补该边界。如果某条边界 是模型本身的边界而非j l 洞边界，可以选择不修补。 2 3 2 孔洞多边形特征面的建立 在孔洞多边形的检测和排序结束后，假设某一孔洞多边形为p o p i 肼是由顶 点p o ，p l ，肼按顺序组成的，那么局部坐标系的原点d 就取该多边形的形i l , 氘即： 。：渤p 仁。， 0 = 一7 f 21 1 坐标系的z 轴方向由两向量p 护o 、p o p ，的叉积向量一决定，其中p 。、p ，分别表示 位于孔洞多边形顶点的总数的1 3 、2 3 处的点。于是可以由原点0 和向量h 来定 义一个平面，我们称之为孔洞多边形的特征面。坐标系的y 轴方向由向量印。决 定，其中p 。表示点内在孔洞多边形的特征面上的投影点。坐标系的x 轴方向由 y 轴的单位向量和z 轴的单位向量的叉积向量来决定。 2 3 3 坐标系的转换 对三角网格模型进行坐标系的转换的主要目的是：便于寻找孔洞多边形任意 两相邻边的最小夹角和校验新增三角片的合法性。 新的坐标系建立后，就必须先把孔洞边界上的顶点和它们邻点的坐标值转换 为局部坐标系下的坐标值，然后才能构造新增三角片，直至孔洞修补结束。最后 再把这些顶点的坐标值恢复为原坐标系下的值。 2 3 4 新增三角片的构造 为了使填补孑l 洞的三角片具有良好的形状，运用如下的构造方法：首先对孔 洞多边形的每两个相邻边的夹角进行排序，确保每次构造新增三角片时都是从夹 角最小的一对邻边开始。 o 南京航空航天大学硕士学位论文 假设某一i l 洞多边形p o p l 肌夹角最小的一对相邻边的夹角为臼，在特征面 上的投影多边形为p 。p i p ，其中p 。表示第i 个顶点在特征面上的投影点，臼 在特征面上的投影为0 。因为本算法是针对同一平面上的孔洞或者基本上位于同 一个平面上的孔洞，可以近似认为i l 洞多边形相邻边的夹角在投影以后改变不 大，故我们可以假定0 对应的目也是最小的。这里假设特征面上一对相邻投影边 列应的共顶点单位向最为a 、b ，所夹的内角为，特征面的法欠为，l ，如斟2 - 1 所1 j 。因为最小夹角曰不可能大于n ，所以在求最小夹角时，可以按下面的方法 计算： i f ( 佃6 ) h 0 ) 0 = a r c o s ( a 6 1 ； e l s e c o n t i n u e 图2 1 计算邻边的最小夹角示意 这样无论孔洞多边形的边界边是按逆时针或者顺时针排序，都能保证排除夹角大 于n 的一对相邻边，查找出夹角最小的一对相邻边。 于是每次在构造新增三角片时，可以根据孔洞多边形的投影在特征面上的最 小夹角0 的大小，然后就在孔洞多边形上相应的最小夹角目之间增加数量不等的 三角片。处理方法如下： ( 1 ) 当臼 2 时，直接生成一个三角片，如图2 - 2 ( a ) 所示。 ( 2 ) 当n 2 0 5n 6 ，生成两个三角片，如图2 - 2 ( b ) 所示。新增点v 1 在p 川、 p l 和p h 三点组成的平面上，p i v l 将z p i i p p i + i 二等份，r j l p i v l | ：( 妇f i p ，l + l p i p 川i ) 2 ； ( 3 ) 当5n 6 占 时，生成三个三角片，如图2 - 2 ( c ) 所示。新增点v 1 、v 2 在肌l 、p ，和p 三点组成的平面上，线段p fv i 、p i l ：2 将p t p i p l 十1 三等份，且慨v “ = n ”2 户( t p i i p i f + ip i p i + 1 ) 2 ； 按照上述方法可以确定新增点的位置。 i 角删格模型的孔洞修补及b 样条曲面拟台 p p i 1 ( a ) 0 j t 2 。 n ( b 1n 2 0 0 ，则转至步骤( 6 ) ，否则程序结束。 本文的采样和均匀优化方法保证重新采样的点仍然在原三角网格曲面上， 而且呈拓扑矩形阵列均匀排列，因此采样点p “的参数( u f ，v j ) 为： u i = i n ，i = o ，1 ，n ； v j 2 j n ，j = o ，1 ，n 。 如下图3 - 6 是一柴油机进气道型芯的模型。图3 - 6 ( a ) 是通过交互生成的一四 边界区域的模型图：图3 - 6 ( b ) 是初始均匀采样后的结果，局部有明显的不均匀现 象出现；图3 - 6 ( c ) 是运用力平衡原理优化后的采样结果，可以看出不均匀现象得 到了改善。 3 0 南京航空航天大学硕士学位论文 ( a ) 生成的四边群区域削 ( b ) 胡始均匀采样结浆( c ) 优化螽的采样结果 匿3 + 6 鲻边域的均匀采样及优化 3 。3 光滑分片b 样条曲面拟合 3 3 。ib 榉条鳆线曲面的基本瑾论 b 样条是对给定型值点进行局部逼近且相邻溻近曲线段之间有逋续性要求 的曲线描述方法，b 样条曲线可以表示为i ”】： p ( “) = e a + n , 。伍) 3 6 ) 其中d i j , i = o ，l ，h 为控制顶点，又称德布尔点。顺序连成的折线称为b 样条 控制多边形，又常简称为控制多边形。n 。( “) ，i = o ，1 ，月为k 次规范b 样条基 函熬，荬中每一个穗为趣范b 撵条，麓穆b 嚣条。宅跫壶一令懿为繁患矢量翁 j 递漾参数# 豹序鲥u ：翰“l “椭+ l 所凌宠静k 次分段多项式，可阻写 成如下递摊形式： 三角网格模型的4 d i i 修补及b 样条曲面拟合 f ) = 协 若“，h “h 其他 n 。( “= 旦n 。 u i + i 一“1 规定旦：0 0 ( “) + 上吐n i l ( “) u i + + i 一“l + i ( 3 7 ) 给定( m + 1 ) ( n + 1 ) 个控制顶点d i j ，f = o ，1 ，脚：j = 0 ，l ，n 的阵列，构成一 张控制网格。又给定参数“和v 的次数k 和f i 和两个参数方向上的节点欠量 u = k ，“一，。 与v = k ，v ，v 。】，k x l 次b 样条曲面定义为如下张量积 形式： p ( u ，v ) = d 叫n ( “) v 川( v ) ， “ “细斛i，v i s v 列川( 3 8 ) i = 0 j = 0 其中b 样条基n ( “) ，i = 0 , 1 ，m 与j ( v ) ，= 0 , 1 ，n 分别由节点矢量u 和按 式( 3 - 7 ) 决定。 3 3 2b 样条曲面拟合的基本理论 任意拓扑的三角网格模型经过四边域划分和均匀采样后，数据点的拓扑呈矩 形阵列分布。因此，在本文中b 样条曲面重建就是要构造一张k x f 次b 样条曲 面插值给定的呈拓扑矩形的数据点p 护f - o ，l ，朋；产o ，l ，月，数据点阵的四 个角点是要拟合的b 样条曲面的四个角点，使其它数据点成为相应的相邻曲面 的公共边界上的点，数据点阵中的每一排数据位于曲面