（机械电子工程专业论文）基于三角网格模型的复杂曲面孔洞修复系统研究与开发.pdf

ad i s s e r t a t i o ns u b m i t t e dt og u a n g d o n gu n i v e r s i t yo ft e c h n o l o g yf o r t h ed e g r e eo fm a s t e ro f e n g i n e e r i n gs c i e n c e p o l y g o n a lm o d e lb a s e dh o l er e p a i rt e c h n o l o g yf o rc o m p l e x s u r f a c ep a r t s c a n d i d a t e ：z e n gx i a n g p i n g sp r o f g a oj i a n u p e r v i s o r ：r o fa oja ns j u n e ，2 0 1 0 s c h o o lo fe l e c t r o m e c h a n i c a le n g i n e e r i n g g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a ，5 10 0 9 0 摘要 摘要 零件修复是再制造工程领域的一个热门课题，国际上已经有一些关于孔洞修复的 论文发表，但是在国内，关于二维区域的孔洞修复研究较多，三维空间的孔洞填补研 究较少。本文基于磨损曲面零件的s t l 三角网格模型，着重开展曲面磨损区域的数据 插入、修复误差分析、修复区域的s t l 模型生成与输出以及修复系统开发实现等工作， 主要内容包括： 1 ) 探讨曲面修复领域的研究现状，分析该领域当前存在的关键技术问题，提出面 向自由曲面磨损零件的修复方案。 2 ) 研究在磨损孔洞中填补离散点的算法，提出基于能量构造法的磨损域离散点的 插入方法，以实现磨损孔洞中离散点集的填补，并通过球体模型实例对插入数据点的 误差进行分析和验证。 3 ) 基于填补的离散点云数据和磨损域的边界特征点，采用同向扩展法实现磨损域 点集的三角剖分和模型优化，实现修复模型的s t l 格式输出。 4 ) 基于修复前的曲面模型和填补的离散点云数据，研究孔洞填补点的误差计算方 法，分析曲面修复模型的误差大小。 5 ) 在上述算法研究的基础上，基于v i s u a lc + + 开发工具和o p e n g l 三维图形技术， 开发出面向曲面磨损零件孔洞修复的原型系统，并通过若干个实例对修复系统的可行 性和稳定性进行验证。 关键词：三角网格；孔洞填补；曲面能量构造法；三角剖分；快速迭代法 a b s t r a c t k e p a l ro fw o r np a r t sh a sb e c o m ea ni m p o r t a n tt o p i c f o rr e m a n u f a c t u r i n g e n g i n e e r i n g t h e r ea r em a n yj o u r n a lp a p e mr e l a t e dw i t hh o l ef i l l i n gt e c h n i q u eh a v e b e e np u b l i s h e di ni n t e r n a t i o n a lj o u r n a l sa n dc o n f e r e n c e s b u tt h e r ei sf e wr e s e a r c h w o r k f o c u s j n g o n3 dh o l e f i l l i n g o fw o m p a r t s b a s e d0 nt h e s c a n n e d s t e 伧o i i t h o g r a p h y ( s t l ) m o d e l ，t h i sp a p e rf o c u s e so nf i l l i n gh o l eo ft h ew o m a r e a 、 a n a i y s i n gr e p a i r i n ge r r o r 、g e n e r a t i n gs t lm o d e lo v e rt h e p o i n t sf i l l e d 、i m p i e m e n t i n g a n dd e v e l o p i n gs y s t e m t h em a i nw o r k i sd e t a i l e da sf o l i o w 1 ) t h i sp a p e ri n v e s t i g a t e dc u r r e n tr e s e a r c hs t a t eo f r e p a i rt e c h n o i o g y ，a n a l y s e dt h e k e yt e c h n i c a lp r o b l e m se x i s t e di nt h i sa r e a ，a n dp r o p o s e da nr e p a i rs t r a t e g yf o r f r e e - f o r mw o m p a r t s z ) i h i sp a p e 7p r o p o s e da ne n e r g yc o n s t r u c t i o n b a s e dh o l ef i l l i n g a l g o r i t h m t h e m e t h o di sd e s c r i b e da n d i m p l e m e n t e d ，w h i c hi sv e r i f i e d t h r o u g has p h e r e e x a m p l e 3 ) t h r o u g h tt h em e t h o do fs a m ed i r e c t i o ne x t e n t i o n ，t h ep o i n t sf i l l e di nt h eh o l ea n d t h eb o u n d a 吖p o i n t sa r et r i a n g u l a t e da n do u t p u t a ss t lm o d e l 4 ) b a s e do no r i g i n a lm o d e l ，f i l l i n gp o i n te r r o r sa r ec a l c u l a t e da n da n a l y s e df o rt h e f e a s i b i l i t ye v a l u a t i o no ft h em e t h o d 5 ) o nt h eb a s i so ft h ea b o v e _ m e n t i o n e ds t u d y ，a n dt h r o u g hv c + + 6 0s 咖a r ea n d o p e n gl3 dg r a p h i c st e c h n o l o g y ，ap r o t o t y p es y s t e mw a s d e v e l o p e dt oi d e n t i f y a n dr e p a i rt h es u r f a c e so ft h ew o r np a r t s ，a n dt h e f e a s i b i l i t ya n ds t a b i l i l t y 。f s y s t e mw a sv e r i f i e dt h r o u g ht h r e er e p a i re x a m p l e so fw o m m o d e l s k e y w o r d s ：t r i a n g u l a rm e s h ；f i l l i n gh o l e ；s u r f a c ee n e m y ；t r i a n g u i a t i o n ；i t e r a t i v e m e t h o d 目录 目录 摘要。i a b ；t r a c t i i 第一章绪论1 1 1 课题研究的背景和意义1 1 1 1研究背景1 1 1 2研究意义1 1 2 曲面修复技术的研究现状2 1 2 1曲面修复的方法2 1 2 2磨损区域离散点的插入3 1 2 3离散点集的三角剖分4 1 2 4孔洞修复存在的主要问题5 1 3 课题来源。6 1 4 本论文的章节内容一6 第二章磨损区域内离散点的插入方法7 2 1 磨损域孔洞边界原始信息的提取。7 2 1 1 矢量类c v e c t o r 3 d 及矢量运算7 2 1 2 三角面片法矢夹角的计算及特征边界点的提取8 2 2 基于能量法的磨损域孔洞修复9 2 2 1能量法的基本原理9 2 2 2 能量模型的处理1 0 2 2 3 磨损域边界点约束的能量法优化造型1 2 2 2 4 能量曲面未知控制顶点的求解1 4 2 3 球体模型的实例分析16 2 4 本章小结18 第三章修复曲面的误差计算与分析1 9 3 1 曲面误差的描述1 9 3 2 曲面误差的计算2 0 m 广东工业大学硕士学位论文 3 2 1 距离函数的定义2 0 3 2 2 填补点到原曲面的误差计算2 1 3 3 本章小结2 4 第四章离散点集三角剖分与s t l 格式的输出2 5 4 1 离散点集的三角剖分2 5 4 1 1 离散点集三角剖分的基本概念2 5 4 1 2 同向扩展法的原理及应用。2 6 4 2 三角剖分网格的优化2 9 4 2 1 优化准则2 9 4 2 2 三角网格优化及实例分析3 0 4 3 修复零件的s t l 模型输出3 l 4 3 1s t l 三角网格模型的引述。3 1 4 3 2s t l 格式零件模型中的拓扑关系3 1 4 3 3 三角网格模型的文件格式3 3 4 3 4s t l 格式中串行化功能的应用3 3 4 3 5 本修复系统中s t l 模型的结构与存储3 3 4 4 本章小结3 4 第五章曲面零件修复系统开发与实例验证3 5 5 1 曲面零件修复系统的功能模块3 5 5 2 曲面修复系统的程序开发和系统界面3 6 5 3 实例验证3 9 5 3 1 磨损曲面修复实例一( 曲率变化小的大孔洞) 3 9 5 3 2 磨损曲面修复实例二( 曲率变化小的小孔洞) 4 3 5 3 3 磨损曲面修复实例三( 曲率变化大的自由曲面) 4 5 5 4 本章小结4 9 总结与展望。5 0 总结5 0 展望。5 0 参考文献51 i v 目录 攻读硕士学位期间发表论文5 4 独创性说明5 5 致谢5 6 v 广东工业大学硕士学位论文 = e ! = ! 自! = = = 自= 目= = 目g 目= | = 目目自目= = e g = ；m l m m i 一目i 目= = 目自目g 目l 目e = g g j = = 目= = = 鲁 a b s t r a c t ( c h i n e s e ) i a b s t r a c t ( e n g l i s h ) i i c h a p t e r1i n t r o d u c t i o n 1 1 1b a c k g r o u n ds i n i c a t i o no fr e s e a r c h 1 1 1 1 b a c k g r o u d 1 1 1 2 s i g n i f i c a t i o n 1 1 2c u r r e n tr e s e a r c ho fs u r f a c er e p a i r i n g 2 1 2 1t h em e m o do fs u r f a c er e p a i r i n g 2 1 2 2 f i l l i n gd a t ai nw e r aa r e a 3 1 2 3 t r i a n 则a t i o n f o rp o i n t s 4 1 2 4t h em a i np r o b l e m si nf i l l i n gh o l e s 5 1 3s o u r c eo fp r o j e c to ft h i st h e s i s 6 1 4t h ef r a m e w o r ko ft h i st h e s i s 6 c h a r t e r2t h em e t h o do fi n s e r td a t ai nw o r n a r e a 7 2 1w o r nb o u n d a r ye x t r a c t i o nb a s e do ns t lm o d e l 7 2 1 1v e c t o ra n dc v e c t o r 3 d 7 2 1 2a c c o u n tt h en o r m a lv e c t o ra n g l e sa n dd e t e c tb o u n d a r yf e a t u r ep o i n t s 。8 2 2f i l l i n gh o l e s b a s e do n e n e r g yc o n s t r u c t 9 2 2 1t h ek e y s t o n eo f e n e r g yc o n s t r u c t 一9 2 2 2t h ed i s c u r s i o no f e n e r g ym o d e l 1 0 2 2 3t h ee n e r g yc o n s t r u c t i o nb a s e do nb o u n d a r yi n f o r m a t i o n 12 2 2 4 a n s w e ru n k n o wc o n t r o lp o i n t s 1 4 2 3a n a l y s e e x a m p l eb a s e do ns p h e r e 16 2 4s u m m a r y 18 c h a r t e r3e r r o ro fc a l c u l t i o na n da n a l y s i so f s u r f a c e 1 9 3 1o v e r v i e wo fr e c o n s t r u c t i o ns u r f a c e 。1 9 3 2c a l c u l a t ee r r o ro fs u r f a c e 2 0 v i 3 2 1t h ed e f m i t i o no fd i s t a n c ef u n c t i o n 2 0 3 2 2c a l c u l a t ee r r o ro fi n s e r t e dp o i n t s 2 1 ：；3s u m m a r y 2 4 c h a r t e r4t ria n g u t i o nf o rp o i n t sa n do u t p u to fs t l 2 5 4 1t r i a n g u t i o nf o rp o i n t s 2 5 4 1 1t h ec o n c e p t i o no f t r i a n g u l a t i o n 2 5 4 1 2t h ek e y s t o n ea n da p p l i c a t i o no fb e a r i n ge x t e n d 2 6 4 2t h eo p t i m i z a t i o no ft r l a n g u t i o n 2 9 4 2 1 o p t i m i z i n gr u l e 2 9 4 2 2t h eo p t i m i z a t i o no f t r i a n g u t i o na n da n a l y s i so f e x a m p l e 3 0 4 3t h eo u t p u t f o rs t lm o d e l 3l 4 3 1t h eq u o t a t i o no fs t lm o d e l 31 4 3 2d o m a n i a lr e l a t i o n s h i po fs t lm o d e l 。31 4 ：；3f i l ef o r m a to f s t lp a r tm o d e l 3 3 4 3 4 a c c e s s i n gs t lm o d e lb ys e r i a l i z i n gt e c h n o l o g y 3 3 4 - 3 5t h ec o n s t r u c t i o na n ds t o r a g eo fs t lm o d e l 3 3 4 4s u m m a r y 3 4 c har t e r5i 己e c o n s t r u c ts y s t e md e v e l o p l 、厦e n ta n dv e r i f i c a t i o n ：；! ； 5 1t h ei n t r o d u c t i o no fr e p a i rs y s t e m 3 5 5 2e m p o l d e rs y s t e m a n di n t r o d u c ei n t e r f a c e ：。3 6 5 3v a l i d a t ef o re x a m p l e 3 9 5 3 1 f i r s t ( s m a l lc u r v a t u r ea n db i gh o l e l 3 9 5 3 2 s e c o n d ( s m a l lc u r v a t u r ea n ds m a l lh o l e l 4 3 5 3 3 1 1 1 i r d ( b i gc u r v a t u r e ) 4 5 5 4s u m m a r y 4 9 c o n c l u s i o n sa n df u t i t er e s e a r c h s 5 0 c o n c l u s i o n s 5 0 f u t u r er e s e a r c h s 5 0 v i l 广东工业大学硕士学位论文 r e f e r e n c e 51 p u b l i c e dp a p e r s 5 4 a n n o u n c e 5 5 a c k n o w l e d g e m e n t 5 6 第一章绪论 第一章绪论 1 1 课题研究的背景和意义 1 1 1 研究背景 再制造就是以废旧产品为坯料进行批量化的加工处理，最终生产出合格产品的制 造过程，是回收利用的最佳形式，因为再制造最大限度地保留了产品的附加值。 由于 废旧零部件的磨损和腐蚀等失效主要发生在表面，所以表面修复技术是实施再制造的 重要技术之一i l l 。在工程实践中，以退役零件为毛坯，进行再制造坯料尺寸恢复显 得更为迫切，如磨损发动机叶片的修复、汽车曲轴表面的尺寸修复以及一些零件表面 的微小缺陷的修复，应用新的表面修复技术，或对已有技术加以改造提高，就能解决 生产实践中的许多实际问题，真正达到优质、高效、节能、节材、环保的要求。因此 对再制造工程中的零件修复技术进行研究具有很大的实用价值。 零件修复是再制造工程领域的一个热门课题。一方面再制造工程是国家为了推进 国民经济良性、循环地发展而提出的一个重大战略，解决由于制造业扩张导致的资源 和能源的快速消耗问题及减少废弃产品对环境的污染。另一方面是我国大量进口精密、 重要零件，由于没有图纸，这些零件磨损之后很难得到精密的、准确的修复【2 1 。 对于一般零件的修复，已经有很多修复方法。随着科技向航天航空和向微观方向 的发展，对精密仪器，高精度零件的修复，对复杂曲面，自由曲面的修复成了发展趋 势。磨损零件扫描后，需要对磨损区域进行修复。国内外对古文物的修复及对扫描时 数据点缺失作了很多研究【3 缶】。这些文献提到了很多关于对数据点缺失的修复，从已知 区域的数据点对缺失的区域进行曲面建模。 的方法。为了精确地修复零件的磨损区域， 地叙述。 这些方法为修复高精度零件提供了可借鉴 有必要对数据缺失区域曲面建模进行详尽 现有的零件修复方法都有一定的局限性，无法对精密的、要求精度高以及各种类 型的磨损零件进行修复。目前，国内外对于数据缺失的研究大都基于简单形状的修复， 因此对复杂曲面修复技术进行研究成为该领域发展的主要趋势。 1 1 2 研究意义 再制造工程的重要特征是再制造的产品质量和性能达到或超过新品，其成本却只 l 广东工业大学硕士学位论文 是新品的5 0 ，节能6 0 ，节材7 0 ，对环境的不良影响显著降低口1 。在2 1 世纪全球提 倡可持续发展战略和绿色制造的今天，利用高新技术促进发展的再制造工程能减少失 效和报废机械零件对环境的危害，最大限度地利用报废产品零部件的发展模式。因此 再制造工程已经成为目前研究的一个热门课题。在目前采用的修复废旧零件的方法中， 对于复杂曲面的修复采用目前的方法结果往往是精度不高对修复工人的技术要求很 高。如果知道欲修复零件的原始c a d 模型，采用c a d c a m 软件实现废旧零件的修复将 会更加高效、快捷、经济。因此利用计算机辅助实现复杂磨损曲面零件的磨损区域边 界提取和磨损区域曲面的重建方法的研究是具有明确的现实意义。 利用计算机程序开发一个复杂磨损曲面修复系统涉及到计算机图形学技术，自由 曲线曲面造形技术、重建曲面误差分析等许多学科领域。在国内外对此方向的研究还 较少，尤其磨损曲面边界的提取方法的研究还是一片空白，所以利用计算机辅助实现 曲面修复系统的开发具有一定的难度。但是随着逆向工程中曲面重建的研究渐渐成为 近几年的研究热点，借鉴孔洞曲面的修复方法和三维曲面模型特征线的提取方法开发 实现磨损曲面修复系统一旦应用于实际，必将促进再制造工程的发展，提高复杂磨损 曲面修复的精度，降低工人的技术要求和劳动强度。因此，研究面向再制造工程的复 杂曲面模型快速重建和修复方法，已经成为摆在再制造工程工作者面前一个重要的研 究课题。 1 2曲面修复技术的研究现状 1 2 1曲面修复的方法 由于反求工程技术应用十分广泛，曲面孑l 洞修复的研究受到了许多研究人员的重 视。在国内，研究较多的有南京航空航天大学【8 哪】、浙江大学1 8 1 9 1 等。在国外，典型的 代表人有c 一2 0 1 ，l i e p a 2 1 1 ，c u r l e s s 2 2 】，l e v i n 2 3 1 等目前，对简单孔洞的修复，大部分是 采用投影后直接三角化的方法，如李伟等利用d i r i c h l e t 域分割法对投影平面上的散乱 离散顶点进行d e l a u n a y 三角剖分，然后再映射到原曲面，从而完成孔洞曲面的修复。 部分学者也采用了一些其他方法完成了简单孔洞的修复，如王宏涛等提出利用径向基 函数对简单孔洞进行修复的方法。 简单孔洞的修复比较简单，上述研究技术基本能满足修复的要求。近年来对于复杂 孔洞的修复研究比较多。如唐杰、k e l e o n g 等人采用直接连接孔洞边界的方式填充孔 洞，其没有参考边界的其他信息，所以在曲面连续性上难以获的满意的效果。为了解决此 2 第一章绪论 问题，有学者在直接填充孔洞的基础上对孔洞三角片进行细分和优化，实现了新增三 角片与周围原有三角网格相协调。论文【8 1 l 】利用神经网格模型把孔洞边界和边界周围 的拓扑关系很好的联系起来，将其应用在孔洞修复上具有十分重要的意义。针对曲率 变化较小的孔洞，陈宏明等提出一种基于曲率的空间多边形孔洞修复的算法，l i e p a 提 出了一种处理杂乱三角网格孔洞的填充算法，c u r l e s s 提出了用非样条插值曲面在立体 凹面区域进行孔洞填充的算法，这些算法对曲率变化较小的孔洞获得了较好的效果， 但其修复的前提是孔洞相对于三维空间的整个实体面积较小。此外，对于曲率变化较小 孔洞，l e v i n 提出了一种填n 边孑l 洞的算法，该算法首先以c a t m u l l c l a x 细分准则为基础， 在边界多边形内部插入一些新的控制点和控制网格，然后根据原有边界和新插入信息 拟合成曲面，它的主要优点是保证了修复曲面和原曲面二阶连续。对于曲率变化复杂 区域的大面积孔洞缺陷，李伟等提出将复杂孔洞分割成简单孔洞的方法，该算法不受 孔洞形状的限制，运用范围较广，但由于其孔洞边界增加了顶点，使得孔洞区域的三 角网格质量比孔洞周围的三角网格较差，难以保证修复孔洞的精度要求。为解决此问 题，韦争亮等提出一种基于曲面拟合的光顺孔洞修复算法，此方法根据空洞边界及周 边信息获得孔洞内部采样点，同时通过加权分点曲面拟合，调整采样点的空间位置， 既满足了修复孔洞的逼真形，又保证了与周围原始网格的光顺性。田晓东等采用遗传 算法完成了模型表面网格的孔洞修复，较好的解决了网格孔洞修复的不确定性问题。 上述算法已经基本实现了小孔洞、大孔洞、曲率变化较小以及曲率变化复杂等类型 孔洞的修复，但其修复曲面和原始网格曲面的光滑性和连续性有待进一步完善。在现 有的许多修复方法中，曲面修复的关键性技术问题在于离散点的插入及离散点的三角 剖分等方面。 1 2 2磨损区域离散点的插入 根据周围原始网格空间点的位置插值调整新增采样点的空间位置是获得孔洞光顺 修复的关键技术之一t 2 4 1 。陈宏明等提出一种基于曲率的空间多边形孔洞修复的算法， 即在孔洞内逐渐插入点直到填满整个空白区域。成欣等利用破洞边界三角形的法矢信 息来插入新的离散点。 上述方法实现了离散点的插入，但其没有考虑网格曲面在孔洞附近的几何形态，因 而新增离散点不能和周围原有网格空间点之间过渡连续。最理想的插入点应该包含周 围空间点的信息，使修复后尽量接近原始真实形状，与周围曲面有很好的光滑连接。 广东工业大学硕士学位论文 如张丽艳眨5 1 等根据孔洞周围网格曲面的几何信息来增加孔洞内部的采样点，基本实现 了填充部分与整体曲面的光滑连接。姜振春吃6 1 等使用曲线插补方法实现了点列的插入， 并较好的解决了孔洞光滑填充问题。邱泽阳2 7 1 等使用曲面插补算法在孔洞区域插入离 散点，具有良好的连续性和比较高的精度。 1 2 ：3 离散点集的三角剖分 离散点集的曲面剖分就是根据三维散乱点集构造曲面的三角剖分，即对所给点集 p = p l ，p 2 ，p 3 ，p n ) ，用互不相交的三角形来近似表示点集形成的曲面，三角形 的集合即为该曲面的三角剖分 2 8 1 0 三角剖分有两种方法，其一是平面投影法，其二是直 接剖分法。不同类型的孔洞需要使用不同的剖分方法，所以采用合适的三角剖分方法 是提高曲面修复逼真性的又一大关键技术。 平面投影法的实质就是平面域的三角剖分。文献 2 9 1 对部分典型的算法做了较为详 细的综述。近几年来在离散点的三角剖分方面有较大的进展。当平面4 点形成凸四边 形时有两种剖分方法，分别是边的总长度最小化( 即最小权) 准则和最小内角最大准 则，在平面投影法中，应用最普遍的是最小内角最大准则 3 0 1 0 最小内角最大准则又称 局部最优准则，该准则可追溯到1 9 0 7 年，是由g v o r o n o i 玎图提出的，后来前苏联数学 家d e l a u n a y 3 2 】在此基础上提出了具体的d e l a u n a 三角剖分算法。d e l a u n a y 三角剖分的 主要原理是：假定在平面域( r 2 ) 上有n 个节点p = p l ，p 2 ，p 3 p n ) ，将这些节点 连接成三角形，那么存在且只存在一种三角形连接，使任何三个节点构成的三角形的外 接圆不包含除此三点之外的任何节点。近几十年来，一些学者提出了很多算法，不断 完善了d e l a u n a y 最初提出的算法。归纳起来有如下三种，l a w s o n 乃3 1 提出了逐点插入 法，其基本思想为：首先选择一个包括所有散乱点的多边形，然后将没有处理的散乱点 插入到已有的de launay 三角网格中去，最后对其优化，以保证生成的是delaun ay 三角网。s h a m o s 和h o e yb 4 1 提出了分治算法的思想，它采用递归分割点集直至每 个子集中仅含三个离散点而形成三角形的办法，经过自下而上逐级合并生成最终的de launa y 三角网。g r e e n 和s i b s o n 3 钉首次实现了一个生成d i r i c h l e t 多边形图的生长算 法，其实现的基本思路是：在离散点中任选一点，然后找出距离该点最近的点，并连 成初始基线，最后再根据delau na c t 条件找出第三点，重复此步骤，直至所有离散 点剖分完毕。上述方法实现了离散点集的三角剖分，但在时间复杂度及硬件的配置的 综合优化方面还需要完善文献 3 6 指出，t s a i 为比较算法性能，给出了上述三种算法 4 第一章绪论 的时间复杂度对照表。逐点插入法实现比较简单，占用内存较小，但它的时间复杂度 差，而分治算法恰好相反。有人提出了一些改进算法，如周知b 8 1 对生长算法进行了改 进，其基本方法就是首先生成一个满足条件的三角网，再以此为基础生成新的三角网， 直至完毕。占自才b 9 1 对分治算法进行了优化，使得其速度优势更为明显，该方法改进 之处在于采用了横向和纵向的双向分块方法，但其在合并时由递归变为了循环，在一 定程度上又与速度原则相悖。逐点插入法和分治算法各有优缺点，由此武晓波b 7 1 等人 提出了合成算法，它把逐点插入法根植到分治算法中，兼顾了空间与时间性能，具有 很大的应用价值。 直接三角剖分是直接对空间散乱数据点进行三角剖分。目前对直接三角剖分的研 究和应用很少，c h o im 1 提出的一种增量算法是较好的一种，应用的很广泛。该算法的 主要缺点是要寻找一点p ，使得从p 点能够看到所有的散乱点，这有时会显得十分困 难。近年来有些学者提出了一些新的算法。如赵杰h 等提出了利用三角形法向量夹角、 阈值距离以及最小内角几个参数进行空间离散点集直接三角剖分的新方法。该方法适 应性广并具有准确、高效的特点。慈瑞梅“2 1 等提出了基于微元网格扩张的三角剖分 算法，并就其中一些关键性问题进行了叙述，如散乱数据点的空间划分方法、存储结 构、空间点与直线的位置关系判断、空间多边形顶点凹凸性判断以及三角网格的法向 一致化等。上述研究已经基本实现了离散点集的三角剖分，其应用较多的是平面投影 法，直接剖分法研究的相对较少。总的来说，三角剖分技术的研究已经比较成熟，但 其还有有待完善之处。其一，在算法研究时，如何综合优化执行时间复杂度、编程效 率以及硬件的配置等还需要进一步完善。其二，在许多应用中，剖分是为了构造曲面， 如何保持曲面的连续和和保形特性还需要进一步探索。 1 2 4 孔洞修复存在的主要问题 曲面修复技术已经引起了国内外学者的高度重视。曲面修复技术在方法研究、离散 点的插入、离散点集的三角剖分等方面均取得了较为明显的进步，但在某些关键问题 上还需要进一步完善。其关键问题在于： ( 1 ) 在修复过程中，如何确保修复曲面具有较好的保形性。 ( 2 ) 如何进一步提高修复曲面和周围曲面之间的连续性。 ( 3 ) 如何集成上述各种算法，使其能同时适合小孔洞、大孔洞、曲率变化较小以 及曲率变化复杂等各种类型孔洞的修复。 广东工业大学硕士学位论文 1 3 课题来源 本课题得到国家自然科学基金项目f n o 5 0 6 7 5 0 4 0 ) ，广东省科技攻关项目 ( n o 2 0 0 9 8 0 1 0 9 0 0 0 4 8 ) 和高校博士学科点专项基金项目( n o 2 0 0 9 4 4 2 0 1 1 0 0 1 ) 资助。 1 4 论文的章节内容 本论文主要针对曲面类三角网格模型磨损区域的修复进行了研究。首先基于孔洞边 界信息使用能量法直接在孔洞中插入离散点；接着采用方向扩展法对边界点和填补点 进行三角剖分，获得孔洞内部的三角面片信息；最后根据非修复域和孔洞内部填入的 三角面片信息，输出修复后的网格模型。 第二章主要开展磨损区域数据点的填补研究。针对s t l 模型，基于非修复区域 的信息，给出了在破洞边界区域约束的三维空间中插入离散点集的方法。由于考虑了 孔洞边界信息，可以大大提高修复曲面和非修复区域的连续性。 第三章是基于孔洞边界点和所插入离散点集的三角剖分。在借鉴已有三角剖分的 基础上，利用破洞修复过程的特殊性，给出可以满足补洞要求的一种新的三角剖分方 法。并完成修复后整体三角网格模型的输出。 第四章对磨损区域所插入的离散点集和磨损前模型进行误差分析论述。提出了修 复曲面误差计算的方法，并详细说明了计算误差的过程。 第五章基于开发系统的实例验证。在上述基础上，提出系统的总体方案和软件模 块设计，并基于v c + + 6 0 软件开发平台，开发一个复杂曲面磨损孔洞修复系统。通过 若干个磨损模型，对系统的有效性进行验证。 6 第二章磨损区域内离散点的捅入方法 第二章磨损区域内离散点的插入方法 针对磨损区域数据点空缺的问题，需要在磨损区域填补相应的数据点。本章重点研 究如何有效的在三角网格模型中磨损孔洞区域内插入离散点集这一关键问题，基于边 界点集采用能量法对磨损孔洞区域进行曲面点集的填补。 磨损域孔洞填补要实现填补区域与非磨损区域的光滑连接，这就要求我们在插入离 散点集时必须考虑孔洞周边的信息，对于三角网格模型来说，即边界点和周边三角面 片的信息，并以此做为能量模型的约束条件，从而实现插入点集和周边区域的一致性。 2 1磨损域孔洞边界原始信息的提取 2 1 1 矢量类c v e e t o r 3 d 及矢量运算 矢量是带方向的单位长度，是几何运算中最重要的工具之一，几乎所有的几何运 算都会涉及到矢量的运算。如物体的移动、旋转、坐标系的变换等等。空间中的一个 矢量，由d x 、d y 、d z 三个分别沿坐标轴方向的标量组成。矢量没有固定的空间位置， 两个矢量，只要它们的长度和方向都一致，就认为这两个矢量是相等的。 在本开发的系统中定义空间矢量的数据结构如下： t y p e d e fs t r u c tt a g v e c t o r 3 d d o u b l ed x ； d o u b l ed y ； d o u b l ed z ； ) v e c t o r 3 d , * p v e c t o r 3 d ； 矢量类c v e c t o r 3 d 的部分代码如下所示： c l a s sc v e c t o r 3 d ：p u b l i cv e c t o r 3 d p u b l i c ： c v e c t o r 3 dg e t n o r m a l ( ) c o n s t ；计算矢量的单位矢量 d o u b l eg e t l e n g t h 0c o n s t ；计算矢量的模长 c v e c t o r 3 do p e r a t o r 宰( v e c t o r 3 dv ) c o n s t ；操作符重载，用于矢量叉乘 7 广东工业大学硕士学位论文 d o u b l eo p e r a t o r l ( v e c t o r 3 dv ) c o n s t ；操作符重载，用于矢量点乘 操作符重载，用于矢量与齐次变换矩阵相乘 c v e c t o r 3 do p e r a t o r 宰( c o n s tm a t r i x 3 d & m a t r i x ) c