（应用数学专业论文）轻松交互式网格曲面建模方法的研究.pdf

浙江大学博士学位论文摘要 摘要 三维几何造型与处理是计算机辅助设计、计算机图形学中和计算机动画的非 常重要的研究课题之一，它在三维游戏、医学可视化、影视特效、数值仿真、计 算机辅助制造和建筑等应用领域都有着广泛的应用外形建模速度的快慢、操作 手段的灵活性以及建模结果的质量高低等问题是这一课题的焦点所在在传统的 几何造型系统中，用户不仅需要具有较高的专业知识和建模技能，而且进行高逼 真度的三维建模非常费时费力因此，之前的建模方法和手段并不能很好地满足 上述几个方面的应用需求随着三维数据获取技术及图形建模方法的快速发展， 已经产生了越来越多的三维模型对已有的三维模型进行分割、组合、编辑和优 化的复用建模方式将节省大量的人力和物力本文围绕着三维网格曲面的轻松建 模方法这一主题展开了深入的研究，建立起一系列简易高效的曲面建模算法，取 得了以下丰富的创新性实用成果： 1 提出了一种基于轻松勾画交互的网格分割技术该方法交互简单自然，用 户只需用鼠标在物体表面上通过勾画的方式大致标明希望获取的部分和抛除的部 分，该技术就能很快地从三维网格模型中提取出用户希望获取的有意义的部分 由于模拟了人们日常生活中通过笔在纸上表达意图的操作方式，这种勾画交互方 式很容易让人操作和接受基于人体感知学中的极小值法则，解决了交互式分割 模型上有意义部位的难题基于区域增长法，使得分割算法效率非常高，完全能 够胜任实时交互基于该技术，通过泊松融合等方法将从不同模型上提取出来的 子部分重新组合生成新的三维模型，从而对已知三维模型进行高效的复用这种 轻松交互的勾画式网格分割方法在降低建模难度和提高模型利用率及建模效率方 面具有特别重要的实用意义 2 提出了通过勾画的统一网格分割和编辑的交互方式该编辑方法不仅交互 方式简单自然，而且充分利用了分割时的勾画线条来辅助引导模型的变形，因为 线条可以认为带有模型的“姿势”信息结合拉普拉斯网格编辑方法，保持了网 格曲面上的细节此外，利用一维骨架跟用户勾画的线条之间的相似关系，提出 了一种勾画式的基于骨架的网格编辑方法，用勾画结果引导骨架，再以骨架驱动 物体的变形首先检测了模型上的突起特征顶点，在这些顶点的辅助下抽取了形 式简洁的但是反映了物体拓扑结构的一维骨架在抽取模型骨架的同时，还建立 了模型的骨架球表示，从而解决了如何将勾画与骨架相结合的问题骨架一球表 示既有一维骨架简单的表示形式，又带有占据物体空间的球体，提供了一种更加 溉江大学博士学位论文 接要 灵活的编辑手段，可以制作出更擒丰富的编辑效果 3 提出了两种各具特色的非迭代的全局优化算法一种是基于拉普拉斯算子 的全局优化算法，目的是均匀化网格的三角形，可用于光顺阏格或提高网格的三 角形质量在顶点约柬瑟重心约束以及共嚣约束等约束条件下，优化鼹格的同 时还保持了模型表面的特征以及整体形状另一种是曲率驱动的顶点流动算法， 在保持网格的连接关系不变的前提下让顶点从平坦部位自动流向特征区域，从而 增强7 模型的视觉感观特征。两种方法都是灵需次性求解一个稀疏线性方程 组，不需要迭代步骤，使用正定矩阵的c h o l e s k y 分解，使得算法效率很高由于 经过分割和融合等操作产生的新网格往往需要提高三角形的质量，而本文的全局 优化方法赢是梵了这个目的，可以大大改善融合网格的质量，铁面保障了本文方 法能够制作高质量的网格模型 本文结合了勾画式的分割、编辑以及保持或者增强特征的优化方法，提出了 轻松交互式的网格曲面建模方法，适合用予快速建模本文方法改善了传统的建 模方式，减少了交互鬟，大大提高了建模效率 关键词：三维建模，勾画式交互，网格分割，极小值法嬲，曲率计算，网格拼 接，网格编辑，骨架抽取，全局优化。 一珏一 a b s t r a c t t h r e e d i m e n s i o n a lg e o m e t r i cm o d e l i n ga n dp r o c e s s i n gi sa l li m p o r t a n tr e s e a r c h t o p i ci nc 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 sa n dc o m p u t e ra n i m a t i o n i th a sb e e n w i d e l yu s e di nv a r i o u sa p p l i c a t i o n si n c l u d i n gc o m p u t e rg a m e s ，m e d i c a lv i s u a l i z a t i o n ，e n - t e r t a i n m e n ti n d u s t r y ，s i m u l a t i o n ，c o m p u t e r - a i d e dm a n u f a c t u r i n g ，a r c h i t e c t u r ea n ds oo n t h ee f f i c i e n c y ，f l e x i b i l i t y , a n dt h eq u a l i t yo ft h em o d e l i n gm e t h o da r et h ep r i m a r yc h a l l e n g e s t h ep r e v i o u sg e o m e t r i cm o d e l i n gs y s t e m sg e n e r a l l yr e q u i r em u c hp r o f e s s i o n a l s k i l l sa n de f f o r t sf r o mt h eu s e rt om o d e lc o m p l e xa n dh i g h q u a l i t y3 dm o d e l s o nt h e o t h e rh a n d ，al a r g en u m b e ro f3 dm o d e l sh a v eb e e nc r e a t e di nr e c e n ty e a r sw i t ht h ef a s t d e v e l o p m e n to f3 dd a t aa c q u i s i t i o nt e c h n o l o g i e s i ta p p e a r st h a tac o m p o u n da p p r o a c h u s i n gd e c o m p o s i n g ，m e r g i n g ，e d i t i n g ，a n do p t i m i z a t i o nw o u l db e c o m eu s e f u la n dp o w e r - f u li nam o d e l i n gt 0 0 1 i nt h i sp a p e r , w eh a v es t u d i e do nt h ei n t e r a c t i v ea p p r o a c hf o re a s y 3 dm o d e l i n ga n dd e v e l o p e das e r i e so fs i m p l ea n de f f i c i e n tm o d e l i n ga l g o r i t h m s o u r c o n t r i l ) u t i o n sa r es u m m a r i z e da sf o l l o w s i b a s e do i ls k e t c h i n gm e s hd e c o m p o s i n g ，a ni n t e r a c t i v em e s hc u t t i n gt o o li sp r o p o s e d ，w h i c hi sa ni n t u i t i v ea n de a s y t o u s em e s hc u t o u tt 0 0 1 u s e r sc a nc u tm e a n i n g f u l c o m p o n e n t sf r o mm e s h e si n s t a n t l yb ys i m p l yd r a w i n gf r e e h a n ds k e t c h e st or o u g h l ys p e c i f yw h i c hp a r t so ft h em e s ha r ew a n t e do ru n w a n t e d s k e t c h b a s e di n t e r f a c e so f f e ra n a t u r a lm e t h o do fi n t e r a c t i o nw i t hc o m p u t e ra p p l i c a t i o n sb e c a u s et h e ym i m i ct r a d i t i o n a l e x p r e s s i o no np a p e ru s i n gp e n c i l s t h es e g m e n t a t i o ni sb a s e do nt h em i n i m ar u l ei n h u m a nc o g n i t i v ev i s i o nt h e o r y , w h i c hs o l v e st h ep r o b l e mo nd e c o m p o s i n gm e s h e si n t o m e a n i n g f u lc o m p o n e n t si n t e r a c t i v e l y b a s e do na ni m p r o v e dr e g i o ng r o w i n ga l g o r i t h m ， i n s t a n tv i s u a lf e e d b a c kc a nb ep r o v i d e df o ru s e r s c o m b i n e dw i t ht h ep o i s s o nm e r g i n g a p p r o a c h ，i tr e u s e se x i s t i n gm o d e l se f f i c i e n t l y i tp r e s e n t si t si m p o r t a n c ei np r a c t i c a lt o i m p r o v et h er e u s a b i l i t yo fm o d e l sa n d t h ee f f i c i e n c yo ft h et h r e e d i m e n s i o n a lm o d e l i n g ， a n dt or e d u c et h ed i f f i c u l t yo f3 dm o d e l i n g 2 au n i f i e ds k e t c h b a s e dm e s hd e c o m p o s i n ga n de d i t i n ga p p r o a c hi sp r o p o s e d o n o n eh a n d ，t h es k e t c h b a s e di n t e r f a c e sa l es i m p l ea n dn a t u r a lf o rm e s he d i t i n g ；o nt h e o t h e rh a n d ，t h es k e t c h e su s i n gt od e c o m p o s et h em o d e la r er e u s e dt og u i d et h ed e f o r m a - t i o n ，b e c a u s et h e yc a nb ec o n s i d e r e da sam o d e lo f “g e s t u r e ”i n f o r m a t i o n c o m b i n e d w i t hl a p l a c i a nm e s he d i t i n g ，o u rm e t h o dc a np r e s e r v ed e t a i l so ft h es o u r c em e s h i na d d i - 一一 浙江大学搏士学位论文 a b s t r a c t t i o n ，c o n s i d e r i n gt h es i m i l a r i t yb e t w e e nt h es k e t c ha n dt h eo n e d i m e n s i o n a ls k e l e t o n ，w e p r o p o s e das k e t c h b a s em e s he d i t i n gm e t h o d c o m b i n e dw i t ht h es k e l e t o n p r o n gf e a t u r e p o i n t sc o r r e s p o n dt ot i p so ft h eb r a n c h e so ft h es h a p e a r ed e t e c t e d ，t h e nt h es k e l e t o ni s c o m p u t e dw i t ht h ea s s i s t a n c eo fp r o n gf e a t u r e s an o v e lr e p r e s e n t a t i o n - - s k e l e t o na n d b a l l sa r ec o n s t r u c t e ds i m u l t a n e o u s l y , w h i c hg i v e sas o l u t i o nt oc o m b i n i n gt h es k e l e t o n a n ds k e t c h i n g t h i sr e p r e s e n t a t i o ni ss i m p l eb u tp r e s e r v e st h et o p o l o g i c a ls t r u c t u r eo f t h eo b j e c t ，a n dp r o v i d e sam o r ef l e x i b l ef o r mw i t hw h i c ho n e c a np r o d u c em o r ee d i t i n g r e s u l t s 3 t w od i f f e r e n tt y p e so fn o n i t e r a t i v ea n dg l o b a lo p t i m i z a t i o na l g o r i t h m sa l ep r o p o s e d o n ei st h eg l o b a lo p t i m i z a t i o na l g o r i t h mb a s e do nl a p l a c i a no p e r a t o r , w h i c hi s d e s i g n e dt ou n i f yt h et r i a n g l es h a p eo fm e s h e s ，a n dc a nb eu s e dt os m o o t ho ri m p r o v et h e q u a l i t yo ft r i a n g u l a rm e s h e s t h eg l o b a ls h a p ea n df e a t u r e so ft h eo r i g i n a lm e s hc a nb e p r e s e r v e db ya d d i n gav a r i e t yo fc o n s t r a i n t si nt h es y s t e ms u c ha sv e r t e xp o s i t i o n ，f a c e b a r y c e n t e rc o n s t r a i n t sa n dc o p l a n a rc o n s t r a i n t s t h eo t h e ro n ei st h ec u r v a t u r e d r i v e n v e r t i c e sf l o wa l g o r i t h mw h i c hi sd e s i g n e dt om a k em e s hv e r t i c e sf l o wf r o ml o w c u r v a t u r e r e g i o n st oh i g h c u r v a t u r er e g i o n s ，t h u st oe n h a n c ef e a t u r e so ft h em e s h i to n l yn e e d s t os o l v eal i n e a rl e a s ts q u a r e sw i t h o u ta n yi t e r a t i v es c h e m e ，w h i c hi se f f i c i e n tu s i n gt h e c h o l e s k yf a c t o r i z a t i o no fs y m m e t r i cp o s i t i v ed e f i n i t em a t r i c e s o u rg l o b a lo p t i m i z a t i o n a l g o r i t h m sa r ed e s i g n e dt oi m p r o v et h eq u a l i t yo fm a n g l e so nn e wm e s h e sp r o d u c e db y t h ed e c o m p o s i n ga n dm e r g i n go p e r a t i o n s a f t e ro p t i m i z a t i o n ，t h em e s hq u a l i t yi sg r e a t l y i m p r o v e d ，w h i c he n s u r e st h a to u rm e t h o dc a np r o d u c eh i g h q u a l i t ym e s hm o d e l s t h i sp a p e rp r o v i d e sa ni n t u i t i v ea n ds i m p l es k e t c h - b a s e di n t e r f a c ef o rb o t he x p e r t u s e r sa n du n t r a i n e du s e r st om o d e l3 dm e s h e si na ne a s ym a n n e r w eh a v ep r o p o s e d c o u p l e so fi n t e r a c t i v ea p p r o a c h e sf o re a s yg e o m e t r i cm o d e l i n gi n c l u d i n gt h es k e t c h b a s e d m e s hd e c o m p o s i t i o n ，e d i t i n g ，a n df e a t u r ea w a r eo p t i m i z a t i o n o u ra p p r o a c h e si m p r o v e t r a d i t i o n a lm o d e l i n ga p p r o a c hb yi n v o l v i n gh u m a nu s e r si nt h ep r o c e s s ，y e tm i n i m i z i n g u s e ri n p u ta n dp r o v i d i n gr e a lt i m ef e e d b a c k k e yw o r d s ： 3 dm o d e l i n g ，s k e t c h b a s e di n t e r f a c e s ，m e s hs e g m e n t a t i o n ，m i n i m ar u l e ， c u r v a t u r ee s t i m a t i o n ，m e s hm e r g i n g ，m e s he d i t i n g ，s k e l e t o ne x t r a c t i o n ，g l o b a lo p t i m i z a - t i o n 一一 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿叁望或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位敝储躲了f 断签字嗍瑚莎年占月厂日 学位论文版权使用授权书 本学位论文作者完全了解迸姿盘堂 有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：加矿年 计趼 t 1 月j日 导师签名： 垌9 移 签字日期： 如p 年月厂日 浙 学博j 学位治文绪言 第一章绪言 随着计算机图形学及相关技术的发展3 d 网格模犁正神成为继声音、留 像和视频之后的另种重要的多媒体数据类型南于近年来辅工业界得到丁 r 泛的应用，以至于催生了计算机图形学下面一个崭新的分支：数字几何处 娜( d g p ：d i g i t a l g e o m e t r y p r o c e s s i n g ) 数字儿何处理的研究内弈就是如何用计算 机对三维几何数据进行处理，如三雏重建、三维造型、网格去噪、网格简化几 何压缩、喇格编辑、重新嘲格化等随着技术的不断发展与成熟，它被广泛应用 于j 维游戏、数字仿真、影视特效、医疗诊断、计算机分子图形学等领域 本文的重点在于3 d 榄犁的制作根据几何数据的创作思路不同可以将它分成 两类一类是虚拟制造，就是用各种3 d 造型软件手工制作3 d 模型另一类则是从 现实世界中获取，比如通过三维扫描仪获取现实世界中的物体，或者通过摄像机 拍照再由图像构建出3 d 模型近年采随着三维扫描技术的发展三维几何的获取 能力也随之增强，将现实世界中存许的物体转化为三维数字几何模弛变得越米越 容易图1i 中的牲型就是通过三维扫描仪秩取数据后再经三维重建得到的，图中 的1i ( a ) 模型具有7 2 0 多万个三角片，而图1i l b ) 中的模型具有5 6 0 0 万个三角片图 中可以看出这些模型的表面部具有丰富的细抽特征而手工制造数字几何模型 的过程相对麻烦一点，往往需要专门的训练才能胜任，甚至要求设计者有定的 艺术素养，这在某种程度t 将般人阻挡在亲自打造魅力无穷的3 d 世界的门外 另外传统的造型软什缺乏构建具有高度复杂表面特征的3 d 模型的能力章运的 是随着z b r u s h ，m u d b o x 等软件的出现，使得手工制作大规模的复杂的具有申富 露函 b )( b ) 器：。喜黼嚣馨裟霖盘船吴端。盖然勰茹嘶a n “l r d 。3 ” 浙江大学孵l 学位论文 绪占 函越 黔镪甜篙锱瓣i 荐器鼎髫锶黜盏搂器濯腓。者所 细节的模型成为可能故有人将这些软件的出现视为一场3 d 建模的革命图12 q 例子分别为使用软件z b m s h 和m u d b o x 制作的模型，u ，以看卅这些模型具有复杂的 几何细悔这对于传统建模软件来说是难于想象的不过闱这些软件制作模型需 要雕刻相关的技能和训练 随着软件和硬件技术的不断进步3 d 模型的制作越来越方便越来越人性 化，制作的横犁也越来越复杂在敏述3 d 模型的构建之前，先米敏述一下3 d 模型 的表示形式 11 3 d 模型的表示形式 计尊机图形学的研宄内容可以简要概括为两部分：建模和渲染( 绘制) 即模 型在计算机中如何表示，如何绘制率文主要研究3 d 模型的构建方法，首先涉及 到的概念就是模型的表示形式 三维几何模型通常包含几何模型的形状及表面属性两部分内容几何的表面 属性包括物体表面的材质、光照性质、纹理图案，以及绘制相关的微观几何属性 一表面法向及几何位置的微小扰动等，主要与渲染有关而描述几何模型形状的 方法多种多样，从表示的元素来看可以分为实体表示法和边界表示法( b o u n d a r y r e p r e s e n t a t i o n 简称b r c p ) 前者比如体素表示法( v o x e l ) 、c s g ( c o n s t r a c t i v es o l i d g e o m e t r y ) 树表示法等而后者包括参数曲面、细分曲面、多边形网格( 包括三角 形两格) 、隐式曲面、点模型表示和几何图像( g e o m e t i y i m a g e ) 等如图l 坤所 不 伴随着三维计算机图形学的发展，多边形网格是种非常受欢迎的模犁表示 形式它具有以下一些优点： 自r 江大学怫士学位论文绪吉 田国u u 幽 印墨， s p l i n t 3 表示数字 1 4 8 器 甓端瓣瑟赫：耥髻麓i 粼莴怒妥镗票 【7 2 1 ；( e l 隐式曲而1 6 8 f 毋几何图像【7 0 1 i 】形式简单，便十存储和处理： 2 ) 可以表示拓扑非常复杂的模型而日可| 三【存任意精度下逼近模本_ 曲面 3 ) 多边形表示是一种分段线性的表示彤式，适合于顶点各种属性的线性插 值比立只需存储顶点的位置坐标及属性即可裘示物体的几何信息而汁算多边 形内一点的属性时，可由顶点的属性线性插值得到，因而便于采用硬件加速技术 来绘制模型等 多边形阿格模犁得到绝大多数的建模软件的支持，可以由如m a y a ，3 d s m a x ，s o f l i m a g e tl i g h t w a v e ，h o u d i n i ，h e x a g o n ，r h i n o tb l e n d e r ，z b r u s h ，s i l o ， m u d b o x ，c i n e m a4 d ，m o d o 等各种3 d 软件生成，圄14 中所示的是用软 件l i g h l w a v e ，c i n e m a4 d 和s i l o 制作的模型也可以通过三维扫描仪扫描 物体表面获得顶点法向等信息后再由三维重建算法生成多边形网格，见 图i5 ( a ) 和i5 ( b ) 另外，还可咀根据2 d 照片来构建3 d 模型，图i5 ( c ) 所示的是 用c r e a t i v ed i m e n s i o n3 d s o mp r o 软件构建的茶壶模型 堵； 翩鬻圃 图i4 再种3 d 软件制作的橙型( a ) l i g h t w a 、c ；( b l c i n c m a 4 d f c ) s i l o 2 ；1 ：) 根銎蔫：镉诺青；尝裂巫建”模型“。实际物体。扫描6 乖建得到的3 0 模 12 曲面造型技术简介 汁算机图形学研究的基本内容就是物体在训算机中立何表示和绘制没有模 型那么切就无从说起，毕竟巧妇难为无米之炊所以第一步就是将物体构建 h 来由此可见几何选型( 建模j 是关键，也是计算机图形学和c a d 系统的一个重 要组成部分另外计算机图形学、c a d c a m 、计算机动画、三维游戏、计算 机视觉、模拟仿真，机器人、计葬机分子图形学等领域都把造型作为基础h 璺 用到；p 算机图形学的领域，都离不扦三维几何模型汽车、船舶，飞机、飞船阱 及导弹等民片j 军用设备的外型设计及动力学分析；地形地貌、水流，水浪、山 川、河流、云彩、雾霭、火焰等自然景物及现象的模拟；家用电器、轻工产品的 工业造型设计、衣服、帽子、鞋子等服装服饰的三维打样和款型设汁；人体建 模、三维游戏和影视特教等的角色建摸r 体外貌和内部器官的盯、磁共振等数 据的医学三维重建；科学计算中的速度场、温度场，应变应力的可视化显示城 市规化园林设计、g i s 等应用领域都需要强有力的3 d 造型工具近年来，由于 几何造型技术研究的迅速发展和计算机硬件性能的丈幅度提高，已经出现了许多 浙江大学博士学位论文 绪言 以几何造型作为核心的实用化系统，在航空航天、汽车、造船、机械、建筑、医 疗和电子等行业得到了广泛的应用 伴随着计算机硬件和计算机图形学的发展，三维几何造型技术也在不断地发 展，随着工业应用的推动及新理论的提出，各种造型技术不断涌现下面简要介 绍一下现有的一些造型技术，主要有参数曲面造型技术；隐式曲面造型技术；细 分曲面造型技术等 1 2 1 参数曲面造型技术 参数曲线曲面表示作为描述几何模型的主要形式，起源于实际的工业生产 中，主要是汽车、船舶、飞机等的外形放样设计工艺 1 9 6 3 年，美国波音公司的f e r g u s o n 提出了以参数的矢函数来表示曲线曲面的 方法【5 9 】1 9 6 4 年，美国麻省理工学院( m i t ) 的c o o n s 用封闭的四段边界曲线定义 一张曲面【4 3 】但以上方法都存在形状控制与连接问题1 9 7 1 年法国雷诺汽车公 司的工程师b 6 z i e r 提出了用控制多边形设计曲线的新方法【1 3 1 这种方法的优点 在于可以方便地修改曲线的形状以及曲线的大致形状跟控制多边形接近，所以具 有良好的可控制性及交互性另外，法国雪铁龙( c i t r o e n ) 公司的d ec a s t e l j a u 也独立 地研究出与之类似的方法 1 9 7 2 年，d eb o o r 【4 8 和c o x 【4 6 分别独立地给出了b 样条计算的标准算法一d e b o o r - c o x 递推公式1 9 7 4 年，美国通用汽车公司的g o r d o n 和r i e s e n f e l d 【6 7 】将b 样 条理论用于形状描述，提出了b 样条曲线和曲面，使其作为在c a g d 中的一个 形状描述的基本方法1 9 7 5 年，v e r s p r i u e 首先提出有理b 样条方法【1 6 5 】，它可 解决二次曲面的精确表示问题后来，经过众多学者的深入研究，至8 0 年代后 期p i e g l 和t i l l e r 【1 3 6 1 将有理b 样条发展成非均匀有理b 样条( n o n u n i f o r mr a t i o n a l b s p l i n e ) 方法，即n u r b s ，它是定义工业产品几何形状的唯一数学方法【1 6 4 】大 多数的造型软件包含有唧r b s 建模功能，如m a y a 、3 d sm a x 、s o f t i m a g e 等，而超 级n u r b s 建模工具r h i n o 是完全以n u r b s 作为其基本的数学表示形式 2 0 0 3 年，s e d e r b e r g 等人提出了t 样条与r - m 瓜c c s ，解决了在几何外形设计 中拼接参数张量积曲面会导致产生过量控制点的问题【1 4 8 由于t 样条能以 比n u r b s 更少的控制顶点为特点来建造模型( 可参见图1 3 ( a ) ) 以及更灵活的表达形 式，像m a y a 、r h i n o , s 类的软件都槲条建模的插件 总之，参数曲线曲面造型技术的核心思想就是以一组基函数为权因子，以一 组初始控制向量的线性( 或有理线性) 组合来得到模型的连续表示如今，该类方 一5 一 浙江大学搏学位论文 绪言 法已经形成以拟合( f i t t i n g ) 、捶值( 1 n l e p o l a l i o n ) 和逼近( a p 磐o x i m a i o n ) 这三种手段 为主的实用几何理论体系 1 2 。2 隐式曲面造型技术 所谓隐式蛆面，是指用形如，缸，寥，名) = o 的隐式方程来表示三维空闻中的曲 面，当函数，是多项式时，该隐式曲面也称为代数曲面事实上，隐式曲面造型 技术的提出早予参数赫线曲面造型技术，早在上个世纪钧年代，航空工业界就邑 成功地用代数馥蘧来表示飞机机身豹完整外形但是由子隐式方穰几何含义不明 确、曲面形状不易控制和不易作局部修改等原因，使得参数曲面造型技术某种程 度上超越了它成为曲面造型的主流 耜对予参数睦瑟造型技术，隐式曲蘑表示也具有参数盎西缺少的许多优点， 如：隐式曲面容易判定空间中某点位于曲面上或者曲面的某一侧；与参数曲面 相比，隐式曲面具有爱多的自由度；在构造复杂曲面的时候，能够得到更高光滑 度，提供雯多豹彩状控制手段；隐式鼗瑟表达形式紧凑，具有凡俺运算下的封闭 性【1 4 5 ，1 4 6 1 ，而且，任何参数或隐式曲面之间如求交、等距操作等几何运算的结 果均可表示成隐式形式【2 4 模型运算的封闭性使得经过这些操作所得到的曲面 无需逼近或近似转化即可表示出来，这将大大方便予益西造型系统鲶统一设计 随着代数几何这一研究领域的发展，隐式代数逮面造型技术的 理论基础得到了巩固1 9 8 5 年，s e d e r b e r g 给出了分片代数曲面的描述 方法1 9 8 9 年，p a t r i k a l a k i s 进一步提出了隐式代数睡面样条酶表示方法 【1 3 2 】b a j a j 等在1 9 9 2 年前艨进一步研究了用隐式代数样条进行多面体的9 1 光 顺、代数曲面的h e r m i t e 插值、代数曲面的高阶插值等一系列问题【2 5 1 随着造型研究的不断深入以及计算杌硬件技术的发展，隐式曲面造型技术在 各个领域特别是c a g d 和计算枫图形学领域遗经得到了越来越多的应用其中， 一个应用广泛的隐式曲面造型技术称为元球造型技术( m e t a b a l l ) ，在下文中会作简 要介绍 1 2 3 细分曲面造型技术 细分技术，顾名思义就是由粗略到精细的建模思路它是一种由离散到离散 的表示形式回顾历史，细分技术早在7 0 年代就明确提国来了f 3 6 ，随着计算机 熬发展_ 穰硬件能力的提高，到9 0 年代逐濒成为一耪菲常流行的造型技术褥深受商 业建模动耐软件的青睐大有如鱼得水，后来居上之势 一6 浙江大学博士学位论文绪言 细分技术主要由两部分组成，初始控制网格及细分规则，不同的细分方法具 有不同的细分规则细分方法可理解为是一种层次化、过程化的重采样方法，它 将曲面的几何属性巧妙地转换成了细分规则 细分方法从不同的角度可以得到不同的分类根据细分规则的不同，最终 的曲面m 7 可以逼近( 如c c 细分【3 6 】) 或者插值( 如b u t t e r f l y 细分1 5 5 1 ) 原始网格m o ? 根据几何规则( 计算细分过程中新顶点的几何位置的规则) 在细分过程中是否 保持不变则可分为静态细分方法( s t a t i o n a r ys u b d i v i s i o n ) 和动态细分方法( d y n a m i c s u b d i v i s i o n ) 曲面的细分造型技术起源于曲线的离散生成算法，即多边形割角( c o m e r c u t ) 算法曲线的快速生成算法，即通过对一个多边形递归地割角得到一条光 滑曲线，是由c h a i k i n 于1 9 7 4 年提出的【3 9 1 9 7 8 年，c a t m u l l 和c l a r k 通过分析3 次 均匀节点b 一样条曲面的离散生成方法，提出了著名的c a t m u l l c l a r k 细分方法( 简 称c c 细分) 【3 6 】同年，d o o 和s a b i n 合作发表了关于细分曲面极限性质的理论 研究，开创了利用离散f o u r i e r 变换，进行细分规则收敛性矩阵特征分析的先河 【5 3 c - c 细分和d o o s a b i n 细分分别是将双三次和双二次b 样条曲面推广到任意 拓扑网格上的细分算法，它们的提出标志着细分正式成为曲面建模的一种方 法1 9 8 7 年，l o o p 提出一种三角网格的逼近型的细分方法【1 1 9 d y n 等人则提 出了一种四点插值的曲线细分规则【5 4 】，并据此给出了基于三角网格的插值型 细分方法，即蝶形( b u t t e r f l y ) 细分方法【5 5 1 ，该算法能够插值初始控制网格的顶 点以及细分过程中所产生的新顶点1 9 9 8 年，s e d e r b e r g 和郑建民等人提出了广义 的c a t m u l l c l a r k 细分规则和d o o - s a b i n 细分规则，在细分过程中引入了节点距，使 得n u r b s 成为它的子集i1 4 9 】另外，1 9 9 8 年对于细分造型技术是有纪念意义、 不同寻常的一年在该年的s i g g r a p h 大会上共有8 篇关于细分的论文，以及同年 著名动画制作工作室皮克斯( p i x a r ) 公司的一部完全使用细分曲面造型与绘制技术 的动画片( g e r i sg a m e ) 获得奥斯卡最佳动画短片奖这些科研成果及实际运用 可以看做细分作为一种造型技术发展成熟的标志 相对于n u r b s 参数曲面等表示形式，细分方法能够构造任意拓扑结构的模 型，且算法实现简单直观，所以深受欢迎绝大部分商业3 d 建模与动画软件， 如m a y a 、3 d sm a x 、s o f t i m a g e 、l i g h t w a v e 、z b r u s h 、m o d o 、s o l i 等都提供了细分 模块，将它作为一种重要的造型方法 一7 一 濒江大学博士学位论文 绪言 1 2 4 其他造型技术 1 2 4 1 曲面重建技术 曲面重建是逆向工程中的一个核心问题，即得到模型表面的采样数据点后如 讶重建枣原始表蘧随着计算机技术豹发展和成熟以及快速、准确的三维数字扫 描设备( 如激光测距扫描仪，计算机辅助断层扫描仪，接触式探测扫描仪等) 的不 断涌，逆向工程成为了一门新兴学科与技术 国内外研究学者提出了很多曲面重建方法，如果按基西表示形式来分类，冀簦 面重建算法大致可分为三类：参数曲面重建、隐式曲面重建、网格曲面重建 参数曲面重建方法b a j a j 在1 9 9 5 年【2 3 1 给出了一种稠密、规则采样数据的 曲谣重建方法它蓄先构造一g 1 连续的分片代数曲面作为定义域曲面，计算出它 的宥向距离场透数，利用o t s h a p e 锝到该定义域曲露的分片线性逼近，并在此定 义域曲面上重建出连续的b e m s t e i n b 6 z i e r 曲面片作为重建曲面1 9 9 6 年，e c k 等人 f 5 7 1 提出了用b 样条曲面对任意给定拓扑网格进行重建的方法同年，h a l s t e a d 等 人1 7 4 提出了稠用b 样条熊面构造高精度地逼近需要重建的曲面法向的方法它 以b 样条为工具，为包括b 6 z i e r 在内的各种参数曲面参与曲面重建的工作奠定了基 础。2 0 0 0 年p i g e l 移掰l e r 【13 5 提出了用b 一样条曲面逼近离散采样点的方法 隐式曲瑟重建方法隐式蓝瑟重建方法它具有易于表示拓努复杂的咒何形体 和便于布尔运算等优点m u r a k if 1 2 5 1 弓i 入b l o b b ym o d e l ，通过求解一个非线性最 优化问题来确定隐式函数；h o p p e 等入【8 1 1 通过构造有向的距离场函数，取得到 辫近点集切平面的符号距离来达到拟合点云的翳静a l e x a 等人1 1 2 通过m l s ( 移 动最小二乘曲面) 来构造隐式函数c 撒等人【3 5 使用全局支集的多元调和径向基 函数( r a d i a lb a s i sf u n c t i o n ，r b f ) 从点云数据重构出光滑的流形曲面及修复不完全 采样的荫箍；勰0 6 年，k a z h d a n 等入f 1 0 1 根据法向信息建立泊松方程求得隐式函 数，并且使用自适应多尺度算法提高了效率 网格曲面重建方法基于网格的重建方法大多基于v o r o n i 图与d e l a u n a y 剖 分，可以概括为区域增长法和面片剔除法两种区域增长算法铁一个种子三角 片开始，通过蔓延将所有顶点连接在一起，g o p i 等人【6 6 采用二维d e l a t m a y - - - 角 剖分的策略，