（计算机应用技术专业论文）曲面重构中网格参数化及修复技术的研究.pdf

浙江大学硕士学位论文 曲面重构中网格参数化及修复技术的研究 摘要 为了解决复杂网格存储和传输代价很大、编辑困难的问题，常常需要运用简 化算法来获得物体模型的一系列模拟。本文针对这个问题，主要研究了参数化、 网格熏构以及孔洞修补三部分内容，并给出了相应的算法。 本文用了三种不同的参数化方法，分析了不同参数化方法对重构网格质量的 影响，利用参数化的结果，通过细分算法将任意拓扑结构的网格重构成为规则的 三角形网格或四边网格。本文中的网格重构算法不仅解决了一类三角化后有边界 没有孔洞的模型，而且对于封闭的模型，提出了一种比较有效的基于延伸边界的 解决方法，还提出了动态网格重构和基于轮廓线的网格重构方法。孔洞修补作为 网格重构之前的预处理，可以分为散乱点模型上孔洞的修补和三角网格模型上孔 洞的修补。对散乱点模型上孔洞的修补采取寻找孔洞边界点及其邻近点，将这些 点插值成曲面，然后将曲面离散成均匀的点，填补到孔洞中，以达到修补孔洞的 目的；对三角网格模型上的孔洞，结合实际应用，采用修补简单孔洞和修补复杂 孔洞两种不同的方法来修补不同类型的孔洞，较好地解决了孔洞修补过程中曲面 的连续性和光滑性问题。 本文的算法在原型系统中，用了多个模型做了测试，验证了它们的有效性。 关键词：逆向工程，参数化，网格重构，虚拟边界，拓扑，孔洞修补 浙江大学硕士学位论文曲面重构中网格参数化敷修复技术的研究 a b s t r a e t i no r d e rt os o l v et h ep r o b l e mt h a tc o m p l e xm e s hn e e d sah u g es t o r a g ea n dh i g h t r a n s m i s s i o np 西c e ，a n di sd i 镬c u l tt ob ee d k d ，s i m p l ea l g o “t h 那sa r eo 托e nr e 唾u i r e d o b t a i n i n gas e r i e so fo b j 。c ts i m u l a t i o n s p a r a m e t e r i z a t i o n ，r e m e s h i n ga n dh o l e f j l i i n g a r es t u d i e df o r t h en e e d so ft h i sp r o b l e m 1 nt h i sp a p e t h r e ed i f r e n tp a r a m e t e r z a t i 。n 巅g o r l t h m sa 辩a d o p t e dt oa n 矗l y z e t h e 打d 谢奄r e n te f f e c t so nm e s hq u a l i t ya 最e rr e m e s h i n g b a s e do nt h ep a r a m e t e r i z e d m e s ho v e rap l a n a rd o m a i n ，s u b d i v i s i o na l g o r i t h mi su s e dt ot r a n s f o r mt h em e s hw j t h a r b i t r a r ys t r u c t u 驿t oar e g u l a r 仃i a n g u l a ro rq u a d r 主l a t e r a im e s h t h ea l g o r i t h m si nt h j s p a p e ra i ma tf e m e s h i n gn o to n l yd i s k l i k eo b j e c t sw i m o u th o l e sb u ta l s o c l o s e d o b j e c t s ，w h i c hu s i n gt h ec o n c e p to fe x t e n d e db o u n d a r y t h ea l g o r i t l l m so fd y n a m i c r e m e s h n ga n dr e m e s h i n gm e t 圭l o db a s e do nc o n t o u fc u ea r ea l s op u tf 。r w a r d h 0 1 e - f i l l i n ga g o r i t h ma sp o s t p r o c e s s i n gb e f o r er e m e s h i n gc a nb ed i v i d e di n t o 椰，op a r t s t h a ti st on l lh o i e si np o i n t sc l o u dm o d e la n dt of i l lh o l e si nt r i a n g u l a rm e s hm o d e l t o 6 i lh o l e si np o i n t sc l o u dm o d e l ：t h ep o i n t so fh o l eb o u n d a r ya n d 伽ep o i n t sn e a r 幽e b o u n d a r yp o i n t sa r ef 。u n dt of o r mt h ef b e f o n ns u r f a c e ，a r e rt h a t ，t h es u h c ei s t u r n e di n t op o i n t sf o rt h ep u r p o s eo f 棚l i n gt h eh o l e t of i l lh o k si nt r i a n g u i a rm e 8 h m o d e l ：b e c a u s eo fd i f f e r e n tt y p e so f h o l 。sa 毹rt r i a n g u | a t i o n ，t w od i 髓r e n th o l e - 6 i l i “ga l g o r i t h m s ，s i m p l eh 。l e 一蠡l i n ga n dc o m p i e xh d i e 一6 l l i n g ，a r eu s e dt on l lt h e d i f 诧r e n tt y p e so fh o l e s t h ec o n t i n u i 妙a n ds m o o t hp r o b l e ma r ew e l lr e s o l v e di n 廿1 e p r o c e s so fh o l e f i j l i n g + t h ea l g o r i t h m si nt h i sp a p e ra p r o v e dp r a c t i c a la n de f 嚣c i e n tl no u rp r o t o 蛰，p e s v s t e m x 叼r w o r d s ：r e v e r s ee n g i n e e f i n g ，p a 糖r n e t e r i z 雏i o n ，r 科n e s h ， v i n u a l b o u n d 铷了 t o p o l o g y ，h o l ef i l l i n g 浙江大学硕士学位论文曲瓤重构中喇格参数化及修复技术的硖究 第一章绪论 1 1 逆向工程的应用背景 传统的产品开发流程是一种预定的顺序模式，即从市场需求蹦发，抽象出产 品的功能描述，然后进行概念设计，在此基础上进行总体设计和详细的零部件设 计，制定工艺流程，设计工具夹具，宪成加工及装配，通过检验及性测试，这 种开发模式的前提是已经完成了产品的蓝图设计或c a d 模型。然而在很多场合 下，产品的初始信息状态不是c a d 模型，而是各种形式的物理模型或实物样件， 这就需要用到逆向工程技术。 随着计算机技术的普及和进步，计算机辅助设计与制造技术也得到了迅猛的 发展，自由睦面造型技术在现在工业产品的设计和制造中有着广泛的应用，然而 在许多情况下，只有产品模裂和实物模型，而没有产品的定义和图纸。为了适应 先进制造授术的发展，需要将这些样件和实物转化为c a d 模型。这种根据实物 模型和祥件测量数据，建立数据模型，得到其设计思想，从而进一步修改原有设 计，然后将这些模型和表征用于产品分析、制造和加工生产的过禊就是逆向工程。 所谓“逆向”实际上是相对于传统的c a d c a m 系统工作流程而言的，可以这 么认为，传统的计算机辅助设诗是首先来源予一个设计思想，然而根据该思想建 立几何模型，并最终生产出产品的过程。与此相反，在逆向工程当中，首先拥有 的是一个物理或实物模型，通过对它进行数据采集，麴藕重建，从而得到它的几 何模型和设计思想的过程。随着数控测量技术的发展，逆向工程技术已被广泛应 用于魅空、航天、造船、汽车和模其等现 弋制造业的各个领域。 逆向工程技术是随着计算机技术的发展和成熟以及数据测量技术的进步而 返蛞起来的一一f 1 新兴学哥萼与技术。它豹出现，泼交了原来e 如系统中从图纸到实 物的设计模式，为产品的快速开发以及快速原型化设计提供了一条新的途径，广 泛地应耀子梳械、轻工、靛空、汽车、家电、玩具等领域。同瓣，它与九十年代 新崛起的快速成型制造技术相结合，可快速实现复杂物体的三维拷贝；若经c a d 系统修改参数重薪建模，受可以实现零 牛的变异复原。 浙江大学联士学位追文 麴蕊重捣中鼹格参数纯及修复按零鲍磷究 遂彝工程菝零在诲多王数镣域皆蠢蓉广泛麴应爰。镄魏褒仿登设诗中，瓣瑟 宠隆莱个产品，熬羲逶豢鸳没霄该产躁豹濂始设诗草案或文穗；又盍蓄在零静瓣静 改与改凝设计中，需要从现存的产晶琏i 发，构造出它的几何模型，从丽可以利用 糯有的c a d 系统进行避一步豹分橇攀畦伉纯，从丽开发密新的产晶；在汽车王业等 领域，车体外壳的荧学设计鼹得尤越徽臻，对于众多设计师而言，他们更辫欢的 是在现实豹滩刻或涟泥模蘩主遴行浚计，实物模型稻对予诗算掇二维屏幕黼言夔 能真实地反映物体的形状，更有利于设计师阐释他的设计思想：另外，在特制的 服装、鞋螺等产品定制领域，挂i 予每个人的瑟帮、身俸缩褥不弱，统一醵尺鹅势 不一定遥台窖户的要求，又出于批爨小，甚至霹鼹就只生产一律产菇，鲻接统的 设诗方法，冗长赞薅，在经济上寐说墩楚不台遥楚。遂彝工程髂系瑟季奄，幽离散 数耩获蕺援术、数嚣颓处理秘三三绦震建以及快速到造三都分组残。 逆囱工程学孛挺到姨一个耱髂建遂一个e 勰模型，这个模型能被律为个渡 计工具来用作构建一个物体的模型，选出一个融经存在的模型的浸计方法，或者 礁糯设计个存在的郢分。在遵翔工校学中，模型由没计瘴设计姆，一般怒德用 木头外形或者粘土模具，现采样然艏再从模型数据转化为c a d 模型作为以尉虑 瘸。直接采样数据缎往会得到一个缀大豹离散豹点集。壹接采样豹数攒舆肖秃规 律性，而且数据量大，如果蛊接应用，对计算机设备的计算速度和存储空间舞求 授严格，褒楚理时瞧要耗费墓犬豹运簿黠闽，不符合磺究泰应臻。霹格夔擒藏跫 上述翘题冀孛熬静解决方法。本文i 睡l 楚篓乎这令滔题对蕊穆重稳及英稳关技零 乍了一系弼篷萋莠究。 1 2 参数化的勰用背景 随饕褒代网络技术豹不断发燧秘满效精密测量设餐戆推出，三维几僻数据成 为继声音、图像和视频之后的篇心代彩媒体数据类型。而三角网格表示成为现在 主流的复杂形状表两三维模型表示方法之，基予三角瓣格梅造n u r b s 曲粼进蕊 梭造实髂模型已成为霹前热f j 的磷炎谍题帮产娩讫方向。三三角网擦通常楚出三搬 耩测霪蕊、3 0 激光扫擂役以及工照爝嬲辊等获玫复杂袭蚕采样点躲咒鳄蔼感， 并逶过瓠挣重建、特薤滚复、觳攒融合等过程褥到。三热阚捂豹参数纯怒对遮蹙 浙江大学硕士学位论文 曲面重构中网格参数化及修复技术的研究 三角网掇几何郓拓豁傣息作进一步处理酌基磴，它在诗算枫整形学、计算搬辕驹 几何设计和数字几何处理等方面有着广泛的应用。比如纹理映射利用表面网格参 数化信息，把一幅文理图案映射到三维网格上，使得表面网格看上去更加生幼逼 真：瞄暖拟台通过参数化把离散的3 d 数据点耀一个光颁的参数化曲瑟采拟会； 重新网格亿( r e m e s h i n g ) 则利用参数化把三角化曲面转化为规则阏格t w 3 ，在此基 础上分析截面线和特征曲面，进而构造复合n u r b s 曲面；还有很多数字几何处理， 如交互式三维绘画、三维网格编辑、网格变形等都需要事先把踺格参数化到一个 容易交互处理的参数域上。 参数化在许多科学和工程领域得到了应用，包括离散数据的装配，部件表面 的重耨参数化，c a d 模型的修复。但是促使第一种参数化方法诞生的最大动力 是诗冀枫图形学中纹理粘赡的应用。接着，由予3 d 扫描技术的快速发展，需要 有效的压缩复杂的三角网格，其它的一些应用如表面拟合、重新网格化促进了进 一步的发展。参数化方法可分为平面参数佬和球面参数化。本文中的算法所使用 的是平丽参数化方法，所戬在这墼详细分绍一下平面参数化。 直观上讲，平两参数化就是把一个空间三角网格平摊成平而三角网格，在保 证平面三焦网格有效性的同时最小化变形。参数化方法的研究对象主要集中在带 单条边赛的二维流形网格上，因为辩闭网格甚至怒任意拓聿卜的阏格都可以通过分 而治之的方法转化为带边界网格。图1 1 所示为其中的一种平丽参数化方法。 ( a ) 原始网硌 ( b ) h a m 砌a i ce m b e d d i n g 图1 1 平面参数化示例 参数化几乎总会产生角或区域的变形。一个好的映射是使变形程度最小。这 存在缀多不同的处理方法。局部参数化问题是比较容易解决静，比如参数健一组 浙江大学硕士学位论文 曲面重构中网格参数化及修复技术的研究 围绕蕾一个参考点r 的点，可以通过指数映射( e x p o n e n t i a lm a p p i n g ) 或者把它们投 影戮r 点的切平面上。但是全局问题处理起来就比较复杂。 l e ee ta 1 2 】通过同时创建三角化层次r ：r n 丁o 。这个过程叫做网格削减 ( m e s hd e c i m a t i o n ) ，参数化：n ，。斗n ，。在每步削减中从矿( 丁) 移除一个点以 及它邻接的三角形并对其重新三角化。所以r 和7 1 一之间只有局部不同扩也不难 找到。结合每个最矮形成参数讫$ ：q ，“呻q ，$ = ”。1 。 b e n n i se ta 1 ( 5 提出了一种基于微分几俺学的方法。他们把等参蛉表露睦线 映射到参数化域上使得每个点处测量的曲率不变。然后参数化曲线向两侧调整值 直到满足某一变形鞭制。由于这种方法需要把寝面劈开成为许多独立的区域，所 以般不被看作解决全局问题的方法。 m aa n d k r u t h ， 6 把数据点鼻投影到个基于参数化的表面s ：q 斗脶3 ，投 影点的参数化值表示为只。这些在文献2 一1 3 中的方法有以下共同的策略： 1 ) 参数化边界点 2 ) 最小化边的能量函数 e = c 。慨一，旷 1“i i o j - 甄j 。占4 9 2 3 ( 1 ) 来确定内部点的参数化值。 边系数q 可以用不同的方法确定。f l o a t e r 选择可以表面几何形状保持不变 的系数值，g r e i n e ra n d h o r n l a n n 使勺= “怕一p 川7 ，o 因为他们想最小化网 格的弹性势缝。两牙孛方法都是人们熟知的参数化曲线成果。使用能量函数( 1 ) 来 平滑多面体表面，发现r = l 时产生好的结果。 m a i l l o te ta 1 吲通过最小化拉格朗日变形张量忆一刈2 ( 十的第一基础范式到某 单佼2 2 矩阵范式的距离) 来减小三角形的变形。不过，这导致了个高度非 线性化函数。由于他们对交互式静方法感兴趣，所以他们瘸一个拉穆朗习张基豹 简化版来取代。 i 。e v ya n dm a l l 娃【8 通过保持等参曲线的正交性和间隔距离来使变形最小。 s h e 臁r 和s t u r l e r 9 坝u 通过保持三角形的角来达到这个强的。 激江大学硕士学谴论文鳇面囊构中网格参数纯及修复技术酚磷究 壅予霹诲多应蘑摇旁中表嚣羧会瓣考虑。m a 强d k r n 斑溺建滚绕开不熬投影 到平禹豹闫题两恕点投影到一个空阏的参数优基础圈捂s ：q 斗豫3 。然蘑袋髑熟 知的参数化方法参数化s 。不过潋个算法要求基础网格的形状接近q ，。寻找这 样一个合适的任意三角网格的熊础网格是十分困难的。这个问题首先被眦ke t a 1 【1 进行了讨论 出于对保形性的要求，y u n 骱l o o 1 0 】通过虚拟边界的方法达到减少边界三角 形及和边界三角形相邻的三角形在从三维空间向二维映射时的变形。虚拟边界参 数化方法如图l ，2 所示。 ( a ) 原始网格 ( b ) 康边界为正方形( c ) 虎边界为圆形 圈l 。2 虚拟边界参数化 l 。3 嬲捺重梅戆应臻曹爨 随着薪静秘穆生残技术豹穗撬，瑷在稳模型 菝褥越来越禧绸，数援羹囊然 i 耋 越来越大。对复杂鼹强避舒存储、传输的代价很大，编辑起来也十分困难，缀然 现在图形硬件的性能已经相当出色，但是如果不使用特殊的技术来减少三角形的 显示个数，这些程序还是很难实现实时性。为了弥补功能需求和硬件性能之间的 差距，可以运用简化算法来获得物体模型的一系列近似模拟【。 近年来已经有很多文献对这方献做了研究。e c ke ta i 提出了一个分三步 的重新网格化算法。首先，把绐定的网格分割成三角形区域。接着，计算给定网 格在每个三角形内的参数化，这是邋过谐波映射使局部变形最，、来实现的。最聪， 按照菜一翘羹莲递l 捉遗鳃分每令麓璐三煮形势怒点还原裂三维空阖就簿爨了囊淘 溺襁。k e la | 。 2 3 挺窭了一謇孛不麓瓣方法，逶过移豫颈点傻麓揍变粒穗飘嚣形 浙江大学硕士学位论文 曲面重构中网格参数化及修复技术的研究 成綦础嘲格作为非平面参数化域。通过把移除的点投影到剩余网格上实现参数 化。这个参数化也是局部平滢的，为了获待全局平潺在双值点她不进行参数化， 而魁通过。一种不同的循环细化机制计算出来，然后还原到三维空间。k o b b e l te ta 1 朝阐述了收缩包装法的实现。它的基本思想是在一个任意的三角形网格周围形 成一个具有细分连通性的三焦彤网格，然后再把它收缩到这个三角形网格上，在 这个过程中需要模拟两个力，一个是使点向原始细分网格表面移动的引力，另一 个把点分京妥这个两穆表面的驰力。使用这手中方法可以形成和球体同构的网格。 k h o n n a n ne ta 1 4 】则提出了用最大等容参数化方法对多边形网格进行熏构。它 的核心思想就是使用最大等容参数化方法获得最小变形的平面域网格三角形。在 阐格重构过程中，三焦网格参数化是一个重要豹步骤，不同的参数化方法对重构 后的网格质量有蓑一定的影响。三角网格参数化 。一 是对这些三角网格几何和撼 扑信息做谶一步处理的摹础。网格重构则利用参数化把三角化曲简转化成为规则 网格，在此基础上分幸厅特征麴线帮特，饪曲面，进而构造复合n u r 8 s 睦面。 在上述文献 卜4 中，并没有实现对封闭模型的重构。本文中，提出了一和对 封闭模型进行重构的一种新的方法，并且尝试性地提出基于轮廓线的网格墓构方 法来解决不仅只夜一条边界模型的网格重榴闫题。 鹜1 3 弼格爨构：细分次数递增 1 4 孔洞修补的应用背景 在逆向工程中，非接触式光学扫描仪能得到非常密集的点云，但是这些点云 中往往存在一些不希望鸯的孔灞。例如，在测量过程中，常需要一定的支撑或夹 具，模型与夹具接触的部分，就无法获得真实的坐标数据；实物零件中经常存在 经裁减等生成的外形特征，如表面凹边、孔及槽等，使曲面出现缺口，这样孔洞 濒汽大学硕士学位论文曲磊重构中溺貉参数纯及修复技术的硪究 的存在会影响许多后续的搡作，如逆向建模、快速原型制造、有限元分析等。在 对网格重构之前，如果三角网格模型有孔洞存在，那么很多网格重构算法就不能 应用于这个三角网格模型，所以对有孔洞的三角网格模型，应该先对这个模型补 洞之后再对其重构。 三角网格模型的描述较为简擎，相关算法也较为成熬，因而在许多领域中德 到了广泛豹应瘸，通过测量数攥重建得到豹三角网格模嫠中，往往存在一些不希 凝有的i 0 洞。如果只需要测量某个模型的一部分，如入的头部，那么被铡部分与 熬体的连接面的坐标数据是无法获取的。即使在一些正向发计软件中，根据曲面 或室体模型产生的三角网格模型也会存在一定的缺陷。国内外许多文献 m z 2 对 此都进行了研究。但由于大多数算法在构造新三角片时仅仅采用原有的孔洞多边 形顶点，雨没有增热颏的三角片顶点，圆而难以获得较好的用于填补孔洞的三角 片形状，修补效粟不够瑾怒。 补洞算法可以对教乱点数据的衿洞，也可毗对曲隘补洞，很多文献对此作了 研究：p a v e l ” 提出了一种在散乱点模型上补洞的算法，这种方法首先计算每个 点的邻近点，确定孔洞边界，利用边界点和边界点的邻避点构造曲面来填补孔洞。 l j c p a ”1 提出了一种在三角网格模型上补洞的算法，在确定网格模型的中边界之 后，将孔洞边界三角化、细化，然后调节薪加的点的位鼹。这剥，可以应用于任意 形状豹藐涸边器明礁熊魏濑。不过列予形状晓较复杂的孔溺，这静方法修於之履 的效果不是很好，琢始模墼的空间信息可能会无法修补。d 纠i se ta i 2 1 提出了一 种修补复杂孔洞的算法，这种方法首先构造了一个距离函数，这个函数的零集代 表曲面，然后使用一种扩散的过程进一步对曲面进行处理，确定孔洞。孔洞确定 之僭，进而填补孔洞。这种方法适用于曲面孔洞，而并不适合于三角曲面。 图l + 4对c a t sh e a d 模型孔洞修补 浙 互大学硕士学位论文盏鬻重构中网格参数化及修复技术的研究 1 5 本文概述 本文针对参数化、网格重构和孔洞修补提出了一些自己的观点，并在反求软 件s u r f e d i t o r 中用v i s ua jc + + 加以实现。本文先对参数化方法作了比较详细的分 析，眈技了各种参数化方法的优缺点和应用情况，分析了线性参数化方法、最大 等容参数化方法和虚拟边界参数化方法。葵中虚拟边界参数化是和线栏参数化方 法或最大等容参数化方法相结合的方法，虚拟边界参数化是为了解决边器三角彤 在参数化的时候，被投影到指定的二维空间后，边界三角形的较大变形会引起相 邻三角形的交形而提出来的。康拟边界参数化是原始网格在添加了虚拟边界点和 虚拟边界三角形之后，溺线性参数化方法或是最大等容参数化对其参数化，然后 秀拆除虚拟边器，从曩孬襻爨二维空润中的踊格模型。文中缩台实际应蠲提出了一 种比较有效的添加康拟边界的方法。 接下来本文研究了几种网格重构的方法，绝大多数的文献提出了对于非封闭 模型网格重构方法。本文在这些文献基础上，提出了一种对封闭模型进行网格重 构的方法，邵基于参数化的封闭模型网格重构的方法：对封闭模型分块处理，将 封翊模型分头成为几个攀封闭模型，使用基予参数化的 封闭模型礴格震构方 法，对它们进 亍重构，然后将分块合并，从露解决封闭模型的网格重均。她外， 还研究了动态网格重构的方法以及基于轮廓线的网格重构方法。动态网格熏构珥i 需耍将模型参数化，而是在分析模型的每条边及其相邻三角形的基础之上，遍历 每条边，对符合条件的边进行边分裂、边合并和边交换操作，从而得到三角网格 形状较好的重构网格。基于参数佬的菲葑闭模溅网格重构方法，是相对于只有一 条边界的情况下提出来的，薤基于轮廓线豹嬲辏重构方法是摆对于不仅只有一条 边界的模型来考虑的，可以解决不仅只有一条边界的模型熏构的目题：将模型中 的散乱点数据转换为截面线数据，然后根据截面线数据提取每层截面的轮廓 线，最后将每一条轮廓线离散成一定数量的点，利用这些离散点构造三角网格或 是溜边网格，以达到网格重构的目的。 最后，本文磷究了i l 溺修 算法，将散蔑点模型三角纯戒弼格模型之焉，由 于散乱点的缺失或是三角化的闻题，可能会馒网格模型有不少的孔澜，这对网络 重构的质量有着一定的影响。上述网格重构的方法，是不考虑模型有孔洞的情况， 所以在本文中提出了孔洞修补的算法。本文中，孔洞修补算法分为对散乱点模型 滤泛大学硕士学位论文睦面重构中掰捂参数化及鲣复技术的研究 朴洞和对网格模型补洞。对散乱点模型的孔洞修补，利用我洞周围的点构造自由 插值曲面，然后将自由插值曲面离散成均匀的点，选取在孔洞内部的点来修补孔 洞。对网格模型的孔洞修补。研究了两种孔洞修补的算法；简单孔洞修补和复杂 孔洞修补，这两种孔洞修补算法各有各的应用领域。 本文在第2 章分橱了各种参数化方法并且绘出了实验结果，在第3 章中详细 撬述了各种鼹揍重梅方法，慰实验结果送行了比较。孔涸骖衿方法将在第4 章中 糖出，也给出了实验结果。在第5 章总结了全文的主要研究成果，并对和本文研 究内容有关的其他方面提出了以后努力的研究方向。 9 浙江大学硕士学位论文 曲面重构中刚格参数他及修复技术的研究 第二章参数化方法 参数化可阻分为平面参数化和球面参数化。本文的算法采用平面参数化的方 法，所以在奉章中详细介绍了平嚣参数化方法。实际上，三角网格参数化可翔结 为这棒一个阊题：绘定个崮三维空润点集只仨岔缀裁麴二维流形三角网格 膨= l ti 翻个二维流形参数域q 。，寻求一个参数域上的点霉q ，到# 肘 的一一映萄雪，使得参数域上的丽捂与鹰始嚼格拓丰 同构，并在保证参数城上三角 形不重叠的同时，谋求某秽与原始网揍之润的几侮度爨的变形最小化】。本文 的算法采用了三种不同的参数化方法：线性参数化方法、最大等容参数化方法和 虚拟边界参数化方法。 2 1 线性参数化 2 1 1 边界为圜形的参数化方法 把边界点安蓬到一个单位圆上，如图2 1 ( a ) ，它们之间的距离通过弹簧模型 确定。如果我们让参数纯点的值为： v ( q ) ：p q l ，扛”埘 l s l n a ； 那么个合理的度量两个参数化点之间距离为q 。一q 所对应的弧长。这样 边界点的参数化可以被认为是一个单变量的参数化，其中= o ，+ 。= 2 7 c 为固定 端点。我们墩弦长权黧毋= 圳+ 一圳，那么 ，+ 务川，九埘腩甜= 盎 图2 2 ( b ) 就为这种参数化方法的效果。 浙江大学硕士学位论文曲面煎构中网格参数化及修复技术的研究 嘶) ( 8 )( b ) 图2 1 ( a ) 边界为圆形的参数化( b ) 边界为矩形的参数化 2 。1 2 边界为矩形的参数化方法 把边界点映射到个弱的凸多边形上，如图2 1 ( b ) 。尤其是纹理映射需要一 个正方形或者长方形的参数域。这需要确定四个边界上的角点并把它们映射到矩 形豹四个焦。鲡果我们令q c ： 岛 e 。为四个角点豹序号，诖它们参数优点的 坐标分别为( o ，o ) ，( a ，o ) ，( a ，b ) ，( o ，b ) ，然后参数化剩余的边界点到矩形 0 ，口】x 【o ，6 】 上，妇： v c 叶，= ( 0 ，t + 。= t + 着，= 以+ ，c ，一- ，“= 赤口”d 乞：= 。 可以采取多种方法来选取这些角点，比如通过计算每个边界点处的角度，然 后选取小于菜个限定傻豹点( 该方法要求边界上省明显的四个点处的角度比瑟它 点的角度小) ，或者等距的选取四个点，为了更加方便和准确地确定这些角点， 我们采用交互式的方法选取这些点。图2 2 ( d ) 就为这种参数化方法的效果。 ( a ) b l a d e 的原始网格 ( b ) 边界为圆形的参数化 浙涯大学硕士学位论文 麴垂重掬中潮楱参数誊匕及修复技术的磺毙 ( c ) n a u t o 的原始刚格 ( d ) 边界为矩形的参数化 圈2 2 两种不同的参数化方法 2 2 最大等容参数化 由主嚣豹两种参数化方法，胃以看出，这两种方法比较适合遮界形状类议圆 形或是矩形的原始网格，不然参数化之后会产生较大的变形，影响网格重构后的 效果。最大等容参数化在一定程度上解决了这个变形问题。 我们清楚地看到，( 投影) 可以被分解为原子的线性映射厂映射一个表面三 角形乃= ( p 。，弓，0 ：) 到对应的参数化三角形o = a 妒乃，岛：) 。所以它足够衡 爨这年孛变形线蛙映射：如果e 是这样一个变形函数，最婷的参数亿可戳被轻易豹 我到只要使，e ) 最小化。 现在，让占b ) = 爿x + 6 作为映射一个表面三角形，到参数化三角形，的原子 线性映射。注意通过引入一个局部坐标系，这个函数可以看作是一个衄z 呻麒2 的映射。用基于条件乃。6 删泌 b r 辫| | b 数来代替一个2 2 矩阵的2 范式条 馋数，当然它仍满足衡量线瞧函数变形熬能量丞数豹四个条髂两且更方便处理： 和i 舭忙厢2 + 2 警= 要鲁矧小南 a l d 2 a 2o i 一4 七2 叫j ：塑划 d e t 一 ( 2 ) ( 3 ) 浙江大学硕士学位论文曲面熏构中嘲格参数化及修复技术的研究 从公式( 2 ) 中我们可以看到k 秘也的密切关系，因此为得到变形簸小的映射， 不管是哪一个最小化都没宵多大的区别。现在我们将要用公式( 3 ) 柬得到一个适 合数值诗冀的k 表示。 图2 3 分解线性函数g 如鬃我们根据图2 3 来分解线性函数g ，矗，e ： 是豫2 中的标准基，我桐有 g = v 。译。避一步的我们宥爿= 西= 0 v 却，产生缀少的汁算： 地鲰陆罨掣= 尝= 裂 一c o t al h r 婴t p 2 i ! 型! i 丛 从公式( 4 ) 和观察得知d e t a v 是二倍的参数亿三熊形的丽积，我们可以把能量函 数砟解释变形为单位参数化面积的狄利克雷能量。 2 。3 康叛边界参数他 保形性楚对各辩参数饯方法盼最基本要求，秘参数化方法要确保蹶先的三受 形在参数化之后，变形尽量最小。但是对于边界三角彤来说，萁变形相对于内部 三角形还是比较大的。虚拟边界参数化方法就是为了解决边界变形较大的情况而 提出来的。如果熔虚拟边界投影到给定的凸多边形上，那么真安的边眷三焦形及 其相邻三角形形状的变形将可以减小。 浙江大学硕士学位论文曲面重构中网格参数化及修复技术的研究 2 3 1 虚拟边界参数化步骤 本文中，虚拟边界的添加采用边界延伸的方法。基于三角网格的虚拟边界添 抽的方法，峦予强扑结构的本屡差剐，三角舔掇豹虚拟边界的添舰有其特殊瞧。 鉴于三角网格曲丽豹特殊性，有必要对三角网格虚拟边界添搬的研究范畴遴行礞 定和再定义： 1 ) j ；= 考虑基线是边券线的清瑟。 2 ) 只考虑延伸面与基滥g c ，连续性。 蒸于上述对研究范畴的定义，下面就可以给出三角形网格模型添加虚拟边界 的步骤： 1 ) 依据延伸方向和延伸步距计算基线的近似等距线，得到一系列离散点( 称为虚 拟边界点) ： 2 ) 对虚拟边界点进行自动调整和处理； 3 ) 在边界点和虚拟边界点之间进行三角划分； 4 ) 将新褥翻的三角形追加到基面的网格上，形成攘体的三三角网格； 5 ) 将追加虚拟边界三角形后的网格用| 二述的参数化方法投影到二维空间； 6 ) 最后，将虚拟边界点和根据虚拟边界点追加的三角形拆除。 根据以上凡步就能得弱变澎兜较，j 、的边界。菡2 ，4 为盥拟边界参数化示钢。 ( a )虚拟边界点的添趣( b )虚拟边界三角影豹追加 浙扭大学硕士学位论文曲两重构中网格参数化及修复技术的研戴 ( c 最大等容参数化 图2 4 2 。3 2 盘拟边界点的计算 ( d )虚拟边界拆除之后 虚拟边界参数化 虚瓠边界参数化首先要解决钓怒如何计算虚拟边界点的空间信息，在本文 中，虚拟边界点空间信息的计嚣利用真实边界点的空间信息对嶷实边界延伸得 到。在本小节中详细地描述了虑拟边界点的添加： 1 ) 确定三角网格模型边界三角形的最小内角氏。和 。； 2 ) 遍历三角网格模型豹边赛边，找到最短边界线段毛。和最长边界线段z ， 联谓边爨边是只蠢一个邻接三角形戆边； 3 ) 分别以k 。和k 。为底边作等腰三角形，则与角如，。和4 。相对应的三角形的 高分稍为： 岛= ( k 。2 ) ，t a n t 氐。2 ) 缟= ( 三m 。2 ) ，t a n ( 氐。，2 ) 群l = ( 工。2 ) ，t a n ( k 2 ) 皿= ( 。2 ) t a n ( k ，2 ) 显然，延饰距离d 应该满足曩 d 如，井延三角形的影获才院较好。 虚拟边界点的计算是构造基线的近似等趿线的过程。设最为真实边界点， m 为尽处相应的延伸方向，d 为延伸距离，则虚拟边器点e 的计算公式为： e 。辟十州 ( 5 ) 浙江大学硕士学位论文曲面重构中网格参数化及修复技术的研究 2 。3 + 3 虑拟边爨三角形的追嬲 根据公式( 5 ) 计算出纛拟边界点的空间位置之后，还需要建立虚拟边界点的 拓扑信息，在虚拟边界点和真实边界点之间追加三角形。在每两个相邻真实边界 点难应静瀣拟边赛点之阕添加一个点，该点可以设为援邻两个盘拟边界点静中 点，i 角形的追加如黼2 5 所示。 追加了三角形之后，可以使用上述的参数化方法对网格模型参数化，这样虚 拟边界就代替囊实边爨被投影到指定黔参数化多边形上，参数化之后，姆虚拟边 界点和刚退加的三角形拆除，真实边界三角形以及相连的内部三角形就一i 会因为 真实边界需要被投影到参数域边界上而引起较大的变形。 2 4 本章小结 2 4 1 小结 昀点 建拱边羿土豹患 囊卖透界上的点 真实边界土豹煮 图2 ，5 虚拟边界拓扑信息的添加 本章详缀介绍了乎藤参数化的几羊孛方法。对于参数纯方法，最霪要豹，点就 是保形性，也就是说将三维空间的网格投影到二维空间之后，原先三角网格的形 状能够较好地保持。线性参数化方法，是将三维模型的边界点投影到指定平面的 嚣形或矩形边赛上，这样，翅果三维模塑的边界不是类似于圆形或是矩形的话， 那个参数化之后= - 角网格的变形是比较大的，不符台保形性的要求。而最大等容 参数化能够比较好地解决这个问题，这种方法是将三维模型的边界按照原来边界 的形状投影到二维空灏，这样能够比较好她保持原来的形状。毽建对于边界三角 形来说，在将其投影至二缀空间之后，还是会有变形，和边界三角形相邻的内部 三角形也会受到影响，为了解决这个问题，本章提出了虚拟边界参数化的方法， 这种方法采用虚拟边界代替真实边弊投影到参数域边界上，较好蟪解决了边界三 6 浙江大学硕士学位论文曲面重构中斛格参数化及修复技术的研究 角形变形较大的阀题。 虚拟边界参数化方法最主要的问题是虚拟边界的构造，在本章中，使用了一 种边界延伸的方法来构造虚拟边界。本章的几种参数化方法在多个模型上作了测 试，已经能很好地应用于备种形状只具有一条边界的模型。 2 4 2 实验结果 表格1参数化方法的比较( 3 0 0g h zp e n t i u m4c p u ，5 1 2 船内存) i 参数化方法( f a c e 模型) 点数 边数三角形数计算时间( s ) 线性参数化( 圆形边界) 3 5 11 0 0 66 5 68 线性参数仡( 矩形边界) 3 5 ll 0 0 66 5 67 最大等容参数化 3 5 l l 0 0 66 5 66 虚拟边界参数化 3 5 l l 0 0 66 5 6 l o ( a ) f a c e 原始网格 ( b ) 边界为圆形的线性参数化 ( c )边界为矩形的线性参数化 ( d ) 最大等容参数化 浙江大学硕士学位论文 阀丽重构中网格参数化及修复技术的研究 。) 虚拟边界点的添搬 虚于；i 边界三鬼形的追加 ( 酚鼹大等窑参数纯 ( h )虚拟边界的拆除 图2 6实验鳍采 溉江丈学颧士学位论文曲面重构审瞪格参数化及修鬟技术的研究 第三章网格重构 3 1 基予参数化的j 封闭模型两格重构 网格重构町以理解为这样一个近似的操作吼：m _ s ，即把一组特定的网格 槲欧壤嚣其每继分连通社的网格s 上，使褥产生静暖格能够很好蜷模拟缀始网 格。这个生成的具有细分连通性的网格被称为原始网格的重构网格。 陶3 1网格重构的基本思想 木殳中的算法是将原始网格采】= 某种参数化方法投黟到二维卒间，对二维空 瞄的嬲格进行处理，然后再貌射到三维空阔。通过一缝空间对网椿避行重构，拆 不是盲接任二三维空间i 重构，这是因为在_ 纰空阐的些操作往往比证三维空间 巾来得简单。矧3 + 1 说明了嗣格重构算浊的基本思路。 3 1 1 基础网格的刨建 参数化之扁，需要在参数化的基础之上建立一个用于细分的基础罔格。可以 只用一个三蹙形作为基础娜格，不过多数情况狠难产生令人满意的重幸句渊格。所 以我到个好的初始网格础是非常重要的。 1 ) 三角形网格的基础恻格 线性的参数化方法己经确定r 边界的形状，对于阉形来说我们在边界等距的 选择4 个点，加上圆心作为幕本网格的点集；对于矩形来说如粜长宽比不大于 1 5 倍，m 幢取4 个顶点和中心点作为基础网格的点集，如果太于则谯长边上插 1 9 浙江大学硕士学位论文曲黼露掏中网按参数化及骖复技术的研究 入几个新点使得每祭边的距离大致相等。至于最大等容参数化则需要计算边界点 处每个角，然后迭敬鄢些小予给定角度的点作为基础掰格豹点。这些点可能是不 等距的，为了避免在基础网格中形成尺寸相差较大的三角形我们在边界插入些 点使得边界点之间约距离大致相嗣。两个边界点五和i 的距离的计算方法如下： 使用还原函数f ，我们得到了网格边界上的点豆= f 恬) 和茸= f e j ，如图 3 2 所示，沿着边界计算这两个点的距离。最后通过d e l a u n a y 三角化算法形成 商质量的平面基础网格。 图3 2 两点间距离的计算撇( 骞，茸) = 0 毒一e + 。忡0 4 。一岛。忡6 罨。一犀。忙忙。一鸟1 i 2 ) 黯边翳楱的基础网格 对于四边网格我们等距的选取4 个边界点形成基本网格。从上面三角形基础 网格的计算中可以看出，对于投影到单位圆和矩形上的网揍寒说锓容易选到4 个边界点( 对于投影到单位圜上的网格我们可以等距的选取4 个点，对于投影到 矩形上的网格我们则选取4 个礞点) ，丽楣对予最大等眷参数化采说则比较麻烦， 为此我们采用交互式的方法选取4 个点，这样可以保证取到4 个角点，从而保持 边界网格的基本形状。 ( 8 )( b ) 浙江大学硕士学位论文曲面重构中网格参数化驶修复拄术的研究 ( c ) 图3 3 创建基础辅格：b i a d e 原始刚格在斑用边界为戳形的参数亿之后，规 则三角形列格的基础网格( b ) b l a d e 原始网拚在应用边界为圆形的参数化之席，规 则四边形闻格的基础网格( c ) n a u t o 原始网格在应用边界为矩形的参数化之后，规 则三角形网格的基础网格( d ) n a u t o 原始网格在应用边界为矩彤的参数化之后，舰 则四边形网格的基础嘲格( e ) f a c e 原始髓格在应用m l p s 参数化之后，规则三凫 形网格的基础网格( f ) f a c e 原始9 目格在应用m i p s 参数化之后，规则四边形网格的 基础卿格 3 1 2 基础稠格的细分 确定了基础嘲格蜃就可以开始细分优化操作了，我们采用插入边的中点的方 法进行缨分操作。对于三角形来说连接每两个中点把一个三角形分成四个，这样 可以保证形成的四个三煮形形状不变。对于四边形来说豫了插入边的中点，还要 在每个四边形中心插入一个点把四边形一分为四。图3 4 为三角形网格细分和四 边弗网格绷分的示意图。 激 互大学硕士学位论文曲面重构中网格参数化及修复技术的磷究 口 图3 4 三角形网格细分厍四边形网格细分 在边界处插入中点的时候，插入的中点应该在原始网格参数化后的边界上。 在各个中点插入之后，计算重构的每个三角网格或圈边网格的面积是否差不多， 如祭偏差较大的话，调整中点的德置，确保每个三角弼格或四边网格的滔积偏差 不是很大。 ( a ) 磊始网格 ( b )三次绍分( c ) 五次缀分 熙3 5网格细分 3 。l 。3 二维空闻到三维空闽的映射 当达到一定的细分层次后就需要通过还原函数，把平面网格转换到三维空 间。其体处理方法如下，对于每个参数化域上的点a 懿计算它在围绕着它的 三角形o = a 咕p p m 日：) 中的重心坐标f = 叩 + 印，i + 归，：，o 【+ p + y = 1 。 对应的三维空间的点f = f ( 芦) 就可以运用相同的重心缝合得副。0 。= f 如。) ， 0 ，= f 瓴，) ，舀= f 如：) 为对应的三角形i 峨的三个顶点e 三维空间的点可以 这个公式芦= “弓。+ p 弓，+ 蚂：得到。 图3 6 为基础网格经过5 次细分之后的匿构网格。 浙江大学礤士学位论文曲面重构中网格参数化及修复技术的研究 ( a ) 原始网格( b ) 5 次缨分薏的蓬捣网格 图3 6两捺重构 3 2 基予参数化的封闭模型网格重构 对于越羽模裂的处理，首先是要将封瀣模挺分割成为容易被主述算法( 基予 参数化的非封阕模型弼格照构) 处理豹一系列丽格曲面，也就是说将封闭摸壁分 割成只有一条边界的非封闭模型，然后对这些网格曲面分别进行处理，网格重构 之后再将分块网接睦露合并成封阔模型。 3 2 。l 封 l l 模型的分块处理 在本文的算法中，对封闭模型的分割首先要在点西上匿分划麴曲线，构造分 割曲线。在点云上构造分割曲线的算法如下： 1 ) 确定分割曲线在点云的大概位霞，得到一个平面； 2 ) 将平西附近的点投影到这个平面上，获得点集j p ，计算点集p 申的点之闯的 最短距离，记为如。； 3 ) 在平面上先根据平面上投影点的位置确定曲线的四个点，加入点集r 中： 4 ) 遮历点集置中的每两个点，获得两点的中点在投影点集p 上的投影，加入点 集r 中( 新加入的点不参与本次遍