（计算机软件与理论专业论文）网格模型上基于手绘的四边形生成.pdf

浙江大学硕士学位论文摘要 摘要 在工业设计和制造中，经常需要对已有的物体或部件进行数字化，并建立相 应的数学模型：首先通过扫描仪采集模型的三维坐标信息，得到一系列的空间数 据点，然后通过对数据点的拟合建立相应的曲面模型。这也就是通常所说的逆向 工程。针对不同的应用目的，研究人员常采用不同的曲面表示方法来拟合这些数 据。n u r b s 作为事实上的工业标准在该方面有着广泛的应用。对于一个复杂的物 件模型，单独用一张曲面拟合是不充分的，因此一个良好的数据分片方法对于物 体最终模型的建立有着举足轻重的作用。 三角网格曲面进行四边形区域划分是逆向工程的一项关键技术，其目的是将 网格模型划分成若干四边形区域，然后对每个四边形区域采用一张曲面来拟合， 同时要求在相邻的曲面之间满足一定的几何连续性。近年来，一些学者相继提出 了多种网格曲面四边形生成算法，归纳起来可分为两类：一类是完全自动地将网 格区域划分成若干四边形区域；另一类是通过交互直接将网格模型划分成若干四 边形区域。前者较少地需要人工交互，但不便于用户控制四边形设计，可能生成 较多的奇异点或者出现非四边形，不能较好地控制局部四边形的走向；后者交互 方式不够灵活，需要较多地人工交互，工作量非常大，对于复杂的实体模型直接 划分四边形几乎不可能。 可见，研究一种交互方式直观，高效可控的四边形生成系统是很有意义的。 鉴于此，本文研究并提出了一种基于手绘的四边形生成系统。在系统的处理流程 中，首先通过特征提取算法自动提取实体模型主要的特征线，同时通过删除一些 冗余的特征线，将特征线进行合并以及对其中一些特征进行延伸的方法勾勒出物 体的主要结构特征；然后用户通过我们提供的工具很方便地编辑特征线，以及通 过示意的方式添加特征线，系统会根据具体情况对要求对特征线进行延伸以获得 用户想要的特征线，最终可以获得在实体模型表面上的一个奇异图；同时用户可 以通过系统指定哪些奇异线是需要严格沿着四边形边界，哪些奇异线只是代表一 个区域内部一个走向；最终我们通过构造一个离散调和方程求解出整个模型每个 顶点的参数值，并自动提取实体模型的四边形划分结果。实验结果表明，该方法 浙江大学硕士学位论文 摘要 主要特点是自动提取实体模型的结构特征，减少用户的交互次数，同时提供了一 系列的交互工具，使用户操作直观方便，无论对整体还是局部编辑，都能取得可 控、可靠的编辑效果，使最终生成的四边形能较好地沿着实体模型的结构特征。 关键词：网格曲面，结构特征，细节特征，奇异图，特征延伸 浙江大学硕士学位论文 a b s t r a c t i nt h ea r e ao fi n d u s t r i a ld e s i g na n di n d u s t r i a lm a n u f a c t u r e ，i ti sd e s i r a b l et o d i 醇i z et h ep r o d u c ta n db u i l di t sm a t h e m a t i c a lm o d e l ：f i r s tal a r g ea m o u n to fd a t a c o u l db eo b t a i n e df r o ms c a n n e r s ，a n dt h e nt h ed e s i g n e r sc a nb u i l dt h es u r f a c em o d e l f r o mt h e s ed a t a t h i sp r o c e s si sw e l lk n o w na sr e v e r s e e n g i n e e r i n g t h en u r b s h a s b e c o m ead ef a c t os t a n d a r df o r t h er e p r e s e n t a t i o no fc u r v e sa n ds u r f a c e si nc a d b u t i ti sn o ts u f f i c i e n tt or e p r e s e n tt h em o d e lu s i n go n l yo n ep i e c eo fs u r f a c e ，s oi ti sv e r y i m p o r t a n tt os e g m e n tt h em o d e li n t os e v e r a lp i e c e so f p a t c h e s p a r t i t i o n i n gas u r f a c ei n t oq u a d r i l a t e r a lr e g i o ni sac o m m o nr e q u i r e m e n ti nr e v e r s e e n g i n e e r i n g i ti st op a r t i t i o nt h em e s hm o d e li n t oq u a dr e g i o n ，a n dt h e nf i tb s p l i n e $ u r f a c ef o re a c hp a t c hs a t i s f y i n gg e o m e t r i cc o n t i n u a l l yc o n d i t i o nb e t w e e np a t c h e s r e c e n t l y , al a r g en u m b e ro fa l g o r i t h m sh a v eb e e np r e s e n t e df o r t h eg e n e r a t i o no fq u a d e l e m e n t s t h e yc o u l db ec l a s s i f i e di n t ot w oc l a s s e s ：a u t o m a t i cq u a dd o m a i ne x t r a c t i o n ； i n t e r a c t i v eq u a dg e n e r a t i o n t h ef o r m e rm e t h o dn e e dl e s su s e ri n t e r a c t i o n , b u tt l l e y a l l o wn oc o n t r o lo v e rd e s i g na n dl e a v el i t t l ec o n t r o lo v e rt h el o c a la l i g n m e n to ft h e m e s he l e m e n t s ，r e s u l t i n gi n s i n g u l a r i t i e sa tc o n s p i c u o u sp l a c e sa n de l e m e n t so f a r b i t r a r ys h a p e s t h el a t t e ri sn o tf l e x i b l ea n dn e e dm o r ew o r k i ti sd i f f i c u l tt oe x t r a c t t h eq u a dd o m a i nf o r t h ec o m p l e xm o d e l i ts h o w st h a ti ti sw o r t h w h i l et os t u d yah i g hi n t e r a c t i v ea n dh i g he f f e c t i v e l y c o n t r o l l a b l es y s t e mw h i c hg e n e r a t e sq u a d r a n g l e s w ep r o p o s eq u a d r a n g l e sg e n e r a t o r s y s t e mb a s e do nm a n u a ls k e t c h d u r i n gt h ep r o c e s so ft h es y s t e m , t h ef i r s ts t e pi st o a u t o m a t i c a l l y e x t r a c tt h em a i nf e a t u r el i n e so fe n t i t ym o d e lb yf e a t u r ee x t r a c t i n g a l g o r i t h m ，d e l e t es o m ea b u n d a n tf e a t u r el i n e s ，m e r g et h ef e a t u r el i n e sa n de x t e n ds o m e f e a t u r el i n e st os t r o k et h em o d e l sm a i ns t r u c t u r e t h e n , t h eu s e r su s et h et o o l s p r o v i d e db y0 1 1 1 s y s t e mt oc o n v e n i e n t l ye d i tt h e s ef e a t u r el i n e sa n da d df e a t u r el i n e s t h r o u g hi n d i c a t i n gm a n n e r a c c o r d i n gt ot h ec a s e s , t h es y s t e mw o u l de x t e n dt h e f e a t u r el i n e st oo b t a i nt 1 1 ed e s i r a b l el i n e sw h i c ht h eu s e r sn e e da n du l t i m a t e l yw ec a n 浙江大学硕士学位论文a b s t r a c t g e tas i n g t a a r i t yg r a p ho nt h e 汕 f a c eo fe n t i t ym o d e l a tt h ef l a m et i m e ，t h eu s c rc a n i n d i c a t ew h i c hs i n g u l a r i t yl i n e ss h o l l l d p r e c i s e l yw a l ka l o n gt h eb o u n d a r yo f q u a d r a n g l ea n dw h i c hl i n e so n l yr e p r e s e mad i r e c t i o no fr e g i o n si n t e r i o r f i n a l l y , w e o b t a i nag l o b a lp a r a m e t e r i z a t i o nb ys o l v i n gt h ed i s c r e t e l a p l a c i a ne q u a t i o na n d a u t o m a t i c a l l yo b t a i nt h er e s u l to ft h eq u a de x t r a c t i o no ft h ee n t i t ym o d e l t h e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t e t h a tt h em a i n a d v a n t a g eo fo u ra p p r o a c h i s a u t o m a t i c a l l ye x t r a c t i n gt h em a i nf e a t u r es t r u c t u r eo f t h em o d e la n dn e e dl e s st i m e so f u s e r s i n t e r a c t i o nb yp r o v i d i n gas e r i e so fi n t e r a c t i v et o o lw h i c hm a k et h eu s e rc o n t r o l m u c he a s ya n dc o n v e n i e n t o u ra p p r o a c hc o u l do b t a i ng l 【o b a lc o n t r o l l a b l ea n dl o c a l c o n t r o l l a b l ee f f e c t sb ys k e t c ht om a k et h eq u a de x t r a c t i o na l o n gt h em a i ns t r u c t u r eo f t h em o d e l k e y w o r d s ：m e s h ，s t r u c t u r a lf e a t u r e ，d e t a i lf e a t u r e , s i n g u l a r i t yg r a p h , f e a t u r e e x t e n d 浙江大学硕士学位论文图目录 图目录 图1 1 逆向工程流程图 图】之由曲率线密度设置引起的悬挂着的曲率线【7 】3 图1 - 3 奇异图，黑色的点表示奇异点，灰色的线表示不同类型的奇异线【9 】3 图1 - 4v s a 形状逼近效果【1 l 】4 图1 5 三维网格模型自动分割算法效果 1 8 1 。5 图2 - 1b u n n y 模型谷线提取阶段性示意图1 1 图2 - 2h o r s e 模型谷线提取阶段性示意图1 l 图2 - 3e x t r a c tf e a t u r e 模型谷线提取阶段性示意图。1 l 图2 - 4b u n n y 模型腿部子特征线精简效果1 2 图2 5 h o r s e 模型腿部子特征线精简效果1 2 图2 6 谷线提取效果1 3 图2 7b u n n y 模型脊线提取示意图1 4 图2 8h o r s e 模型脊线提取示意图1 4 图2 9e x t r a c tf e a t u r e 模型脊线提取示意图1 4 图2 - 1 0 特征线提取效果1 5 图2 1 l 闭合特征线的延伸1 6 图2 1 2 闭合特征线的最终延伸结果1 6 图2 1 3 各成本函数的图示1 8 图2 1 4 开特征线延伸效果比较1 8 图3 1 编辑工具a ) 示意图2 2 图3 2 编辑工具b ) 示意图2 4 图3 - 3 亏格为l 的l o r u s 模型添加分割线效果图( 内圈的线由特征线提取时获得) 图3 - 4 跨区域的分割线添加2 5 图3 - 5 编辑工具b ) 示意图2 2 5 图3 - 6 编辑工具c ) 示意图2 6 图3 7 非封闭的n e f e r t i t i 模型的分割图2 7 1 1 1 浙江大学硕士学位论文图目录 图3 8h o r s e 模型的手绘效果2 8 图3 - 9b u n n y 模型的手绘效果2 8 图3 1 0h e a d 模型的手绘效果2 8 图3 - 1 1e x t r a c t _ f e a t u r e 模型的手绘效果。 图4 1 部分网格区域边界，黑色的点表示分叉点3 1 图4 - 2 分段区域边界走向的确定 图4 3 全局参数化结果。 图4 4 各模型四边化结果 3 l 3 2 3 3 图4 5 四边形区域划分结果不能对齐到奇异线的情况一3 4 图4 - 6 通过我们方法处理后的四边形划分结果 图4 7 效果对比 图4 8 逐步优化的四边形生成( 纹理贴图效果) i v 3 5 3 6 浙江大学硕士学位论文第1 章绪论 1 1 研究背景 第1 章绪论 三维四边形网格，在计算机图形学、计算机辅助几何设计以及逆向工程 ( r e v e r s ee n g i n e e r i n g ) 等领域中，有着广泛的需求。像纹理分片( t 瓠t u i ea t l a s g e n e r a t i o n ) 、b 样条拟合、有限元分析等应用，都可在四边形网格上进行。但是， 对于不同的应用，其对应的四边形网格质量的评价准则，例如局部的四边形形态、 网格节点的正则性、整体上四边形是否对齐到结构特征，会各有侧重。本文中， 我们关注三维四边形网格在逆向工程中的应用。 逆向工程【1 1 ，是指由实物模型产生数字化模型的过程。在工业设计和制造领 域中，逆向工程具有广泛的应用，例如在工程图纸丢失的情况下制造备件，对已 有的模型进行重建以用于分析改进，定制适合人体外表面的配件如头盔、太空服 等。逆向工程是快速原型制造( r a p i dp r o t o t y p em a n u f a c t u r e ) 中前处理模块的重 要组成部分，也是产品创新设计的重要手段。它的流程如图1 1 ：首先通过扫描 仪采集模型的三维坐标信息，得到一系列的空间数据点；接着对数据点进行噪声 点去除、冗余数据精简、残缺数据拼合等预处理操作；然后应用网格剖分技术建 立数据点间的拓扑关系，一般为三维三角形网格；接下来在网格剖分结果上进行 基于三角域曲面或四边形域曲面的几何重建；最后得到c a d 模型。 图1 1 逆向工程流程图 在曲面重建阶段，针对不同的应用目的，常采用不同的曲面表示方法来拟合 网格数据【2 】。其中，非均匀有理b 样条( n u r b s ) 方法，作为事实上的工业标准， 在该方面有着广泛的应用。对于一个复杂的实物模型，单独用一张曲面来拟合是 不充分的，因此需要根据一定的规则先将网格数据划分成一系列的网格区域，然 浙江大学硕士学位论文第1 章绪论 后对每个网格区域用一张曲面来拟合，同时要求在相邻的曲面之间满足一定的几 何连续阶。在上述曲面重建过程中，一个重要的问题是如何还原模型的整体结构 特征 3 1 4 1 。而网格区域划分的结果对上述问题有着直接影响。因此，一个良好的 区域划分，对最终模型的建立起着十分重要的作用。 在本文中，我们的主要工作是对于一个三维三角网格模型，生成其对应的四 边形区域划分，即生成其对应的三维四边形网格，以便将来在此基础上进行b 样 条曲面的拟合。 1 2 三维网格模型的四边化方法 根据在三维四边形网格上的后续应用，我们来分析四边形网格质量的评判准 则。为使b 样条曲面能够在节点处实现方便的拼接，要求四边形网格具有良好的 正则性。为使最终生成的曲面能够尽量保持网格模型的整体结构特征，要求四边 形网格能够尽量保持整体结构特征。所以，我们对于四边形网格的要求是在尽可 能生成正则四边形的同时，尽量保留原三角网格模型的整体结构特征。 基于上述要求，我们来分析回顾近年来三维网格模型的四边化方法。 为了使生成的四边形能够对齐到网格模型的结构特征，a l l i e z 掣5 】首先提出了 将网格模型的曲率张量场映射到参数域并进行平滑，然后对参数域的张量场从脐 点出发分别对最小、最大曲率线进行追踪，通过线密度的控制形成了一系列的曲 率线，对这些曲率线进行求交，就得到了一个各向异性的以四边形为主的三维网 格。但是，在有噪音的情况下，曲率张量场虽经平滑仍难保证能找到正确的脐点， 可能出现脐点数目很多或者脐点位置不合理的情况。此外，曲率线的追踪过程因 需进行数值积分而存在着不稳定性。在后续m a r i n o v 等 6 1 提出的改进方法中，因 不再需要全局参数化而不再要求输入网格的亏格为0 ，并且在各向同性区域的采 点上提出了更为成熟的方法，即将可信赖的主方向从各向异性区域传递至各向同 性区域，还在更为可靠的各向异性区域中设置曲率线的追踪起始点以使曲率线的 追踪过程更为稳定。对于上述基于曲率线追踪的方法，其不足之处在于曲率线密 度的设置是基于局部信息的，所以在网格模型上会出现较多的悬线，如图l - 2 。 这种睦率线的分布和选取策略，将导致最终生成的网格正则性较差而且存在t 型 节点。 2 浙江大学硕士学位论文第1 章绪论 图1 2 由曲率线密度设置引起的悬挂着的曲翠线f 7 】 为了获得较好的网格正则性，d o n g 等1 8 i 提出通过构造调和标量函数来进行网 格四边化的方法。首先，在网格模型上生成一个平滑的调和标量场，计算调和标 量场的梯度生成梯度矢量场，然后在梯度矢量场中进行数值积分得到梯度流线， 进而在调和标量场中提取等值曲线得到封闭的等参流线，最后对两种流线进行求 交得到最终的多边形网格。在此方法中，由标量场的调和性质，保证除了用户指 定的奇异点外不存在局部的极值点，所以最终生成的以四边形为主的三维网格具 有较好的正则性而且只有较少的t 型节点。但这种方法的缺点是通过用户指定或 半自动生成奇异点或奇异线，并不能保证最终生成的四边形能够对齐到网格模型 的结构特征。此外，该方法仍需进行数值积分。 图1 - 3 奇异图，黑色的点表示奇异点，灰色的线表示不同类型的奇异线【9 】 t o n g 等【9 】提出利用离散调和形式( d i s c r e t eh a r m o n i cf o r m s ) 来计算网格的全 局参数化，进而得到三维四边形网格。此方法需要先在原始网格上建立一个奇异 图( s i n g u l a r i t yg r a p h ) ，如图1 3 ，并且保证奇异图每条边上的连续性。上述连 续性要求，对奇异图的构造提出了较高要求：奇异图的每个面必须形式上看成平 面上各个边与坐标轴平行的多边形，以便确定奇异图各条边的参数走向。然后， 通过求解一个奇异边上参数差值的方程计算出奇异图各个顶点的参数值。最后， 浙江大学硕士学位论文第1 章绪论 通过求解一个由原始网格构成的调和方程得到网格的参数化，并由追踪参数等值 线得到四边形网格。此方法通过设置奇异线和分数指标的奇异点，对网格模型的 四边化提供了良好的控制。另外，因其不需积分在数值计算上更为稳定。但是， 在奇异图的构造上，需要相当大的人工努力来满足其奇异边上的连续性要求。 m a r i n o v 等0 0 提出通过两步分别实现局部上具有较好的网格正则性、整体上 对齐到网格结构特征的方法。首先，应用可变的形状逼近( v a r i a t i o n a ls h a p e a p p r o x i m a t i o n ) 1 q 对网格模型进行分割，使分割后的网格面片边界能够对齐到网 格整体结构特征，接着用光滑的3 次曲线逼近面片边界并进行等距采样，映射到 参数域后，由任意两个采样点计算一条弯曲能量最小的3 次曲线，由此构成面片 内的曲线网，从中选取出一个子集以生成具有良好的形态的四边形。因为v s a 本意是用于形状逼近，若用于分片虽然能够使分片的边界尽可能沿着网格的结构 特征，而且使每个网格分片近乎平坦，但是存在着分片过多过碎的问题，如图1 4 。 另外，在采样点较多的时候，例如网格面片所含区域较大或进行较高分辨率采样 时，曲线数目会比采样少时急剧增加，使得选取合适的曲线网子集的复杂度也急 剧上升。 图1 - 4v s a 形状逼近效果【1 1 j 为了使最终生成的四边形网格具有良好的正则性，我们认为可以通过离散调 和形式的全局参数化方法来实现。而对于整体上尽量对齐到网格结构特征的要 求，我们考虑是否可以通过网格分割时分割线的控制来满足，并由上述分割线构 成一个初步的奇异图。 4 浙江大学硕士学位论文第1 章绪论 1 3 三维网格模型的分割方法 三维网格模型的分割方法，可分为基于面片( p a t c h - t y p e ) 的网格分割和基于 部件( p a r t - t y p e ) 的网格分割两类。 基于面片的网格分割方法，将网格模型分割成一些同胚于圆盘的面片，其主 要应用为网格压缩1 1 2 1 、纹理映射1 1 3 】、形状逼近【1 等。典型的方法，如基于层次关 系的面片聚类算法1 1 4 1 。 基于部件的网格分割方法，将网格模型分成有意义的部件，例如将动物模型 分割成腿、身子、头等部分，其主要应用为网格变形【1 6 1 、骨架提取、形状混合1 7 1 等。这类方法对部件的拓扑不做限制。典型的方法，如基于模糊聚类的层次分解 方法【1 6 1 、智能化手动网格裁剪方法1 1 8 1 。 三维网格模型的自动分割算法一般采用区域合并f 1 4 1 或区域扩张技术来实 现，其对应的效果如图l 。5 。对于这类方法，很难确定分割区域的形状。而且， 因为分割边界是由分割算法所确定的，不方便用户进行交互。 ( a ) 区域扩张 ( b ) 区域合并 图1 - 5 三维网格模型自动分割算法效果f 侣1 基于模糊聚类的层次分解方法，主要通过在部件问设置模糊区域来优化最终 的分割。但是，它是用阀值约束的聚类来确定模糊区域，而不是更多的关注在网 浙江大学硕士学位论文第1 章绪论 格结构特征上。 智能化手动网格裁剪方法，首先提出先获取分割线，再对网格模型进行分割 的方法。此方法从网格结构特征出发，依照人类的感知系统和极小规则，结合一 定的人工交互来获取分割线，实现有意义的分割。 智能化手动网格裁剪方法与我们的需求比较接近，我们在此方法上进行必要 的改进和拓展，例如上述方法只在网格模型的凹区域中寻找分割线，而我们同时 也需要凸区域中的特征线，譬如棱线。由此，我们得到了一些对齐网格结构特征 的分割线，并用其构成一个初步的分割图。 1 4 基于手绘的交互方式 由上节得到的初步分割图，只是一个分割线的集合，并不满足构成完整奇异 图的要求。为此，我们考虑通过手绘的方式，来完成最终奇异图的构造。 基于手绘的交互方式，因其能够使用户方便地参与到设计过程中来，并且能 够较为自由便捷地表达其意图，而在多个领域中得到广泛应用，如图象分割u 9 1 、 图象中对象的选取 2 0 1 、几何建模【2 l 】、圆，网格编辑c 2 3 1 等。 在j i 等【2 4 】提出的便捷网格分割方法中，提供了基于手绘的用户交互界面，通 过按住左键( 右键) 绘制线条来标识前台区域( 后台区域) ，基于上述标识应用 改进的i s o p h o t i c 度量距离进行区域扩张，以达到分割的目的。 f u n k h o u s e r 等【2 5 】提出了基于实例的建模方法：为了构建新的模型，可以从不 同的模型中分割出所需要的部件进行组合。他们的分割技术也采用了基于手绘的 交互方式：先要求用户勾画出大致的分割线，再以一定的线宽作为选中区域，在 选中区域内计算出所有起始点集间的代价约束的最短路径，并在不可见区域中 ( 选择区域的后面) 也计算出所有起始点集间的代价约束的最短路径，然后综合 上述结果得到一条封闭的最小代价的分割线。 在智能化手动网格裁减方法中，也提到了先在屏幕上画一条直线段，然后将 其映射到网格上作为一条候选分割线的交互方法。 与上述方法不同，我们的目的是在初步分割图的基础上，通过手绘形成符合 要求的奇异图。在初步分割图所反应的网格划分中，存在多种不符合要求的情况， 例如网格区域存在多条区域边界，网格区域内部存在孤立的分割线，网格区域需 6 浙江大学硕士学位论文第1 章绪论 要继续进行分割等等。对于上述等情况，我们将提供一套基于手绘的编辑工具， 来帮助用户进行有效地处理。 1 5 本文的研究内容与研究意义 三角网格曲面进行四边形区域划分是逆向工程的一项关键技术，其目的是将 网格模型划分成若干四边形区域，然后对每个四边形区域采用一张曲面来拟合， 同时要求在相邻的曲面之间满足一定的几何连续性。近年来，一些学者相继提出 了多种网格曲面四边形生成算法，归纳起来可分为两类；一类是完全自动地将网 格区域划分成若干四边形区域；另一类是通过交互直接将网格模型划分成若干四 边形区域。前者较少地需要人工交互，但不便于用户控制四边形设计，可能生成 较多的奇异点或者出现非四边形，不能较好地控制局部四边形的走向；后者交互 方式不够灵活，需要较多地人工交互，工作量非常大，对于复杂的实体模型直接 划分四边形几乎不可能。 可见，研究一种交互方式直观，高效可控的四边形生成系统是很有意义的。 鉴于此，本文研究并提出了一种基于手绘的四边形生成系统。首先，通过特征线 的提取和延伸，构成初步的分割线；接着通过基于手绘的编辑，生成符合要求的 奇异图；然后确定奇异边的连续性类型，并选择需要严格对齐的奇异线，在利用 离教调和形式计算网格的参数化，得到四边形区域的划分；最后，可对划分结果 进行改进，逐步优化生成的四边形网格。 本文共分五章： 第一章首先讲述研究背景，然后分析回顾四边化相关技术，最后指出研究意 义，并提出我们的解决方法。 第二章先对网格模型主要特征线的提取进行了讨论，提出了一种脊线提取算 法，取得了较好的效果。然后，对闭合特征线的延伸和开特征线的延伸进行了分 析，提出了开特征线延伸的成本函数，得到了较为满意的特征线延伸结果。 第三章对奇异图的要求进行了分析，提出了一套基于手绘草图的交互方式， 方便用户进行奇异图的构造。我们提供了4 种便捷的编辑工具，并对每种工具的 适用情况进行了分析讨论，也给出了相应的图示。 第四章对四边形的生成进行了阐述，提出了将四边形区域划分结果严格约束 7 浙江大学硕士学位论文第1 章绪论 到奇异线的方法，并取得了较好的结果。另外，对于复杂模型，提出了通过在扭 曲严重的地方添加分割线来逐步优化四边形结果的方法。 第五章在总结全文工作和创新点的基础上，指出了本文有待进一步研究的内 容。 8 浙江大学硕士学位论文第2 章特征线的提取与延伸 2 1 引言 第2 章特征线的提取与延伸 几何特征是几何造型的关键要素，它对控制几何形体的形状具有极为重要的 作用。在曲面重建时，嵌入棱线、脊线等特征线，对提高模型的精度、增加数据 压缩比有相当重要的作用【2 6 】，因此我们需要在四边形区域划分过程中，使四边形 区域划分边界线尽可能沿着上述特征线。也就是说，四边形区域划分结果必须尽 可能体现原网格模型整体结构特征以及重要的特征线。本章将主要阐述如何从网 格模型中提取主要的几何特征以及如何对这些特征线进行处理。 2 2 特征线的提取 几何形状特征，主要表现在曲面的连续性上。曲面的不连续性特征，可以通 过估计曲面的法矢和曲率来判断。因此，对于网格模型上的任意一个顶点，可以 根据该点邻域内其他点的曲率与该点的曲率关系，判断出该点是否为曲率极值 点、曲率不连续点1 2 6 。特征线就是由这些曲率不连续点连成的线或者曲率极值点 连成的线。由于网格模型中可能存在噪音，加上离散曲率的计算存在误差，如果 直接应用上述方法进行判断，会产生远远多于实际所需的特征点，所以需要进行 局部误差的消除和整体误差阀值的控制【2 7 l 。但是对于不同的网格模型以及不同的 特征要求，上述参数的合理设置依然存在困难。 在微分几何学中，对于一个光滑的可定向曲面，可以根据曲面上某一点在其 主方向上的主曲率极值类型，判断出该点是否位于脊线( r i d g e s ) 或谷线( r a v i n e s ) 上阴。s o n g 等1 2 9 1 提出先进行网格简化，再根据简化的网格基域拟合出一张光滑 的参数曲面，就可对脊线、谷线进行精确地求解。此方法，通过网格简化可去除 网格上的一些噪音。但是，该方法提取出的特征较多地依赖于拟合出的参数曲面， 网格简化的程度以及网格简化结果。 因此我们在特征线提取方面进行了一系列研究。我们将网格模型特征分为两 大类：结构特征和细节特征。我们将网格模型中能体现整个实体模型主要形态的 9 浙正、。7 硕十学位论文第2 章特征线的提取与延伸 特征定义为结构特征；对于网格模型中一些局部区域的特征，我们称之为细节特 征。在本章自动提取的特征主要为网格模型的结构特征，对于细节特征，在后续 进行划分结果优化时有选择地进行提取。 下面，我们将对谷线、脊线的提取进行详细阐述。 2 2 1 谷线的提取 由于谷线的特征要求与基于部件的网格分割的分隔线要求相近，我们采用文 献【l 司中所提到的方法，并根据我们的要求做相应调整。 在基于部件的网格分割中，一般应用极小值规$ j ( m i n i m ar u l e ) 1 3 0 1 来实现有意 义的分割。极小值规则指出人类感知系统通常沿着由主曲率为负极小值的点所构 成的区域将模型分成不同的部分。因此，文献【1 8 1 将每个顶点处估计的最小主曲率 值作为此顶点的特征值。 对于每个顶点处曲率张量的计算，采用文献1 5 1 中使用的方法： m 卜高g 。风力旧邶h p ( 2 。1 ) 式中，v 表示网格顶点，曰表示用于张量估计的v 的邻域，厦p ) 表示边e 的有向两 面角( 凸为正，凹为负) ， e r u p t 表示边e 的有效长度( 若e e b 则为e 的长度，否 则为o ) ，e 表示与边e 同向的单位向量。 根据公式2 1 ，可得到一个3 x 3 的对称半正定矩阵，其中绝对值最小的特征值 所对应的特征向量即为此顶点处的单位法向量，另外两个特征值根据其长度分别 为最小、最大主曲率( 置。、气。) ，k 。所对应的特征向量为最大主曲率方向，k ， k 。所对应的特征向量为最小主曲率方向。此方法的理论基础可参见文献3 。 由此，我们得到每个顶点处的最小、最大主曲率。但是，对于不同的模型， 其最小主曲率为负极小值的范围差别很大，所以需要进行标准化变换【1 8 1 ，如下： r ( v ) = ( _ | ( v ) - z ) a r ( 2 2 ) 式中，颤v ) 表示顶点处的最小主曲率，威示所有顶点的平均主曲率，d 表示所有 顶点的主曲率的协方差。 对于每个顶点处的标准化变换后的最小主曲率，其可视化效果如图2 1 ( a ) 、 1 0 浙江大学硕士学位论文第2 章特征线的提取与延伸 图2 - 2 ( a ) 、图2 - 3 ( a ) 。我们使用1 司中提到的滞后阀值p 3 1 参数，即将r ( v ) d 、于1 2 的顶点和“v ) 小于- 0 8 且相邻顶点中有r ( v ) 小于1 2 的顶点标记为特征点。 ( a ) 特征值场( b ) 特征区域( c ) 特征骨架 图2 1b u n n y 模型谷线提取阶段性示意图 ( a ) 特征值场( b ) 特征区域( c ) 特征骨架 图2 - 2h o r s e 模型谷线提取阶段性示意图 ( a ) 特征值场 ( b ) 特征区域 ( c ) 特征骨架 图2 3e x t r a c t _ f e a t u r e 模型谷线提取阶段性示意图 由连接两个特征点的边的邻面构成特征区域，如图2 1 ( b ) 、图2 2 ( b ) 、图 2 3 ( b ) 。对于每个特征区域，我们应用从边界边逐渐向内剥离该区域内部边的骨 架抽取算法1 3 3 1 ，得到一个有分支的特征骨架，如图2 一l ( c ) 、图2 - 2 ( c ) 、图2 - 3 ( c ) 。 将特征骨架在分支处断开，得到一些单独的子特征线。这里，我们需要对子 特征线进行精简合并，以形成少数几条最为主要的特征线。我们的处理方法是， 浙江大学硕士学位论文第2 章特征线的提取与延伸 对于每个分叉点，建立一个从此点出发的子特征线集合，从中选出最长的子特征 线作为基线，然后在剩余的特征线中选取合适度值最大的子特征线作为拼接线。 其中，合适度的评价函数如下： s ( f ) = 口l e n ( 1 ) l e n ( l 5 + 声c o s ( ，l ) + y x l i n k e d ( 1 )( 2 3 ) 式中，表示当前的子特征线，上表示最长的子特征线，三，表示次长的子特征线， l i n k e d 表示当前子特征线的另一顶点是否为分叉点，若是值为1 ，否则为0 。公 式各项分别代表拼接线选取时在长度、方向、连接性上的考虑，即希望选取方向 相近的长度较大的而且还可再扩展的子特征线作为拼接线。 当选定基线和拼接线后，将两线进行拼接并更新拼接线的另一顶点处的连接 信息。然后，对剩余的子特征线进行处理，对于l i n k e d ( r ) 值为0 的线标记为可删 除；对于l i n k e d ( i ) 值为1 的线设置此线的反向l i n k e d ( ) 为0 。对于标记为可删除 的线，在所有拼接完成后，通过判断其包含的网格边的数目以及其长度对于最终 得到的特征线的长度比例，决定是否予以保留。 在实现中，对于子特征线方向7 ，由线上靠近当前分叉点的边的方向进行平 ( a ) 特征区域( b ) 精简前1 1 条子特征线( c ) 精简后3 条主要特征线 图2 - 4b u n n y 模型腿部子特征线精简效果 ( a ) 特征区域( b ) 精简前9 条子特征线 ( c ) 精简后1 条主要特征线 图2 5h o r s e 模型腿部子特征线精简效果 浙江大学硕士学位论文第2 章特征线的提取与延伸 均得到，参数o 【、d 、y 的值取为l ，精简效果如图2 4 、图2 - 5 。若在最终的特征 线中，还存在分支的，在分叉点断开得到由分叉点起始的多条特征线，如图2 4 。 经过上述精简后，我们得到最终的谷线，如图2 - 6 。 2 2 2 脊线的提取 图2 - 6 谷线提取效果 对于脊线的提取，我们采用与谷线提取相似的方法。在特征点的标识上，我 们通过以下两步来完成。 首先，对于网格模型上的任意一边，通过其两个对顶点的平均法向所定义的 两面角( e s o d 算子1 3 3 1 ) 来做判断。如果其有向两面角是凸的，而且角度大于阀 值，我们将此边的两个顶点标记为特征点。在实现中，我们取角度阀值为6 0 0 。 上述方法实现简单，速度快，但是只能处理较为简单的情况，对于粗糙的网格模 型或者光滑过渡的网格区域就不能进行很好的处理。 对于较为普遍的情况，我们采用判断主曲率极值的方法。在上节中，我们已 利用公式2 1 计算出每个顶点处的最大主蓝率，然后我们利用公式2 2 对最大主 曲率进行标准化变换。经标准化变换后，虽然各网格模型的主曲率分布已接近正 态分布，但是其最大主曲率为正极大值的范围还是有较大差别，例如h o r s e 模型 的范围从1 0 3 到1 3 5 ，而b u n n y 模型的范围从1 2 4 到1 6 1 ，h e a d 模型的范围从 1 7 到2 1 4 。为此，我们在所有最大主曲率集合中，以从小到大的顺序，选取位 于5 处的值作为有效下限，位于9 5 处的值作为有效上限。这是因为最大、最 小值与集合所在的主要区间偏差过大，并不适合作为有效区间的度量。接着，由 公式2 4 计算出主曲率阀值： t h r e s h o m = a 奉u p p e r + ( 1 一五) + l o w e r ，五【o ，1 】 ( 2 4 ) 浙江大学硕士学位论文 第2 章特征线的提取与延伸 式中，u p p e r 表示有效上限，l o w e r 表示有效下限。在实现中，我们取a 的值为o 8 。 其对应的效果如图2 - 7 ( b ) 、图2 - 8 ( b ) 、图2 - 9 ( b ) 。 ( a ) 特征场( b ) 特征区域( c ) 主要特征线 图2 - 7b u n n y 模型脊线提取示意图 ( a ) 特征场( b ) 特征区域( c ) 主要特征线 图2 8h o r s e 模型脊线提取示意图 ( a ) 特征场( b ) 特征区域( c ) 主要特征线 图2 - 9e x t r a c t _ f e a t u r e 模型脊线提取示意图 如上节，可由特征点构成特征区域，并从中提取出特征骨架，精简后形成主 要的特征线。脊线提取的效果，如图2 7 、图2 8 、图2 - 9 。 通过谷线、脊线的提取，我们得到了网格模型中的主要结构特征。如图2 1 0 所示，对于( c ) ，提取出的特征线已经构成了一个比较好的划分；而对于( a ) 、( ”， 提取出的特征线还比较分散，没有相连形成一个有效的分割。为此，我们将通过 “ 浙江大学硕士学位论文 第2 章特征线的提取与延伸 特征线的延伸来解决部分问题。 ( a ) b u n n y 2 3 特征线的延伸 ( b ) h o r s e ( c ) e x t r a c t _ f e a t u r e 图2 1 0 特征线提取效果 对于特征线的延伸，根据延伸类型，可分为闭合特征线的