（计算机科学与技术专业论文）网格变形技术研究.pdf

浙江大学博士学位论文摘要 摘要 网格模型的变形是数字几何处理的一个核心技术，近年来得到了国内外研究 者的极大关注，且在逆向工程、模拟仿真、工业品创新设计及计算机动画等领域 得到了广泛应用。本文以计算机图形学、计算机辅助几何设计、离散微分几何学、 数字信号处理和计算几何为坚实的理论基础，对网格模型的变形技术进行了深入 研究；针对网格模型的主要变形技术所存在的问题，提出相应的处理方法。主要 内容包括： ( 1 ) 提出了基于最小二乘网格的自由变形技术。以最小二乘网格作为原始网格 的低分辨率网格，将两者之间的高低频差用局部标架编码，达到保持网格模型的 表面几何细节的目的。算法基本思想就是利用网格自由变形技术( 均值坐标) 控 制低分辨率的最小二乘网格，而不是直接控制原始网格；然后通过局部标架编码 重建变形后的网格。对于用户角度而言，所有的操作及速度与传统的网格自由变 形技术无异。但是在变形效果上克服了传统自由变形技术对于光顺模型变形效果 较好，但是对有几何细节的模型变形效果较差的弱点。 ( 2 ) 提出了保持几何特征的均值骨架子空间网格变形。以均值骨架作为变形 驱动的控制手段，并且利用微分域坐标以及骨架子空间模型来达到网格变形前后 骨架及表面几何细节的保持。算法基本思想是利用骨架驱动的子空间变形技术控 制骨架变形，然后利用原始网格的微分域性质及原始网格相对于均值骨架的性质 构建变形能量函数，最后通过最优化此能量函数得到变形后的网格。由于线性能 量函数最优化的计算能达到实时，因此对于用户角度而言，所有的操作及速度与 传统的骨架子空间网格变形技术无异。但是在变形效果上保证了原始网格的骨架 及表面几何特征( 平均曲率) 。 ( 3 ) 提出了一种基于均值骨架的网格变形复制。利用已有的变形网格序列复制 出更多的变形网格序列是三维几何模型重用的重要方法。本文提出了一种在线性 空间中，基于均值骨架的网格变形复制算法。通过均值骨架，自动建立起源网格 i i i 浙江大学博士学位论文摘要 与目标网格的对应关系，无需用户前期对应点的指定。通过均值骨架坐标与微分 域坐标变形技术的融合，将目标网格的变形转化为线性的能量约束问题，达到高 效计算的同时保持目标网格的几何特征。该方法不仅能够实时地生成视觉真实的 变形复制结果，而且操作简单适合动画制作初学者。 ( 4 ) 提出了基于动态轮廓模型的微分域网格变形技术。整个算法的关键是将 骨架和体积的特征约束通过动态轮廓模型的形式来进行近似的模拟，从而与微分 域上的变形技术结合在一起，通过解线性最小二乘法得到变形后的结果。算法的 目的是通过骨架和体积的近似保持将原本非线性的问题转换成线性求解来换取 变形的速度，从而平衡了最大限度保持原有网格特征的要求和变形时间复杂度之 间的矛盾。 关键词：网格，最小二乘网格，自由变形，骨架子空间变形，变形复制，微分域 坐标，均值骨架坐标，动态轮廓模型 浙江大学博士学位论文 a b s t r a c t a b s t r a c t m e s hd e f o r m a t i o ni st h ek e r n e lp a r to ft h ed i g i t a lg e o m e t r yp r o c e s s i n gw h i c h m o r ea n dm o r er e s e a r c h e r sa th o m ea n da b r o a da r ef o c u s i n go nr e c e n t l y m e s h d e f o r m a t i o nh a sw i d ea p p l i c a t i o n si nm a n ya r e a ss u c ha sr e v e r s ee n g i n e e r i n g , n u m e r i c a ls i m u l a t i o n s ，r a p i di n n o v a t i v ed e s i g na n dc o m p u t e ra n i m a t i o n ，e t c b a s e do n t h ei n t e n s i v es u r v e ya n dc o m p r e h e n s i v ea n a l y s e so fv a r i o u sa p p r o a c h e st ot h em e s h d e f o r m a t i o n ，s e v e r a ld e f o r m a t i o na l g o r i t h m sh a v eb e e nd e s i g n e d ，i m p l e m e n t e da n d v e r i f i e di nt h i sd i s s e r t a t i o nw h i c hm a i n l ya i m sa tt h ew e a k n e s so ft h ee x i s t i n g d e f o r m a t i o nt e c h n i q u e s t h et h e o r i e so fc o m p u t e rg r a p h i c s ，c o m p u t e r - a i d e dg e o m e t r i c d e s i g n ，d i s c r e t ed i f f e r e n t i a lg e o m e t r y , d i g i t a ls i g n a lp r o c e s s i n ga n dc o m p u t a t i o n a l g e o m e t r y a r ea l l i n c o r p o r a t e di n t o o u ra l g o r i t h m s m a i nc o n t r i b u t i o n so ft h e d i s s e r t a t i o ni n c l u d e ： ( 1 ) an o v e lf r e e f o r md e f o r m a t i o nb a s e do nl e a s t s q u a r em e s hb a s e di sp r o p o s e d i nt h ed i s s e r t a t i o n i no r d e rt op r e s e r v et h eg e o m e t r yd e t a i l so ft h eo r i g i n a lm e s h ，t h e l e a s t s q u a r em e s ho f t h eo r i g i n a lm e s hi su s e dt oe n c o d et h ed i s p l a c e m e n tb e t w e e n tt h e t w om e s h e s t h ea l g o r i t h mc o n s i s t so ft h ef o l l o w i n gm a i ns t e p s ：f i r s tm e a n - v a l u e c o o r d i n a t e si su s e dt oc o n t r o lt h el e a s t - s q u a r em e s hi n s t e a do ft h eo r i g i n a lo n e ；s e c o n d d i s p l a c e m e n tv e c t o r sa r ee n c o d e da n dd e c o d e di nt h el o c a lf r a m eo ft h ev e r t i c eo ft h e l e a s t s q u a r em e s ha n dd r i v et h eo r i g i n a lm e s ht od e f o r ma c c o r d i n g l y f r o mt h eu s e r s p o i n to fv i e w , t h ec o n t r o la n ds p e e do ft h ea l g o r i t h mi st h es a m ea st h e yd oi nt h e t r a d i t i o n a lf r e e f o r md e f o r m a t i o n h o w e v e r , t h ed e f o r m a t i o nr e s u l to fo u ra l g o r i t h mi s b e a e rt h a nt h et r a d i t i o n a lo n e se s p e c i a l l yi np r e s e r v a t i o no fm e s h sg e o m e t r yd e t a i l s ( 2 ) l o c a ld e t a i lp r e s e r v e dm e s hd e f o r m a t i o nb a s e do nm e a n - v a l u es k e l e t o n s u b s p a c ei si n t r o d u c e di nt h ed i s s e r t a t i o n t h em e a n v a l u es k e l e t o ni su s e dt oc o n t r o l t h em e s hd e f o r m a t i o n ，a n dt h ed i f f e r e n t i a lc o o r d i n a t e sa n ds k e l e t o ns u b s p a c em o d e l a r ea l s oi n c o r p o r a t e di no r d e rt op r e s e r v et h es k e l e t o na n dg e o m e t r yd e t a i l so ft h e o r i g i n a lm e s h t h ea l g o r i t h mc o n s i s t so ft h ef o l l o w i n gm a i ns t e p s ：f i r s tt h es k e l e t o n s u b s p a c ed e f o r m a t i o n ( s s d ) m o d e li su s e dt oc o n t r o lt h es k e l e t o n st r a n s f o r m a t i o n ； v 浙江大学博士学位论文 a b s t r a c t s e c o n dt h ed e f o r m a t i o ne n e r g yf u n c t i o nw i t hd i f f e r e n t i a lc o o r d i n a t e sa n dm e a n - v a l u e s k e l e t o nc o o r d i n a t e si sc o n s t r u c t e d ；f i n a l l yt h em e s hd e f o r m a t i o no c c u r st h r o u g ht h e o p t i m i z a t i o no ft h ee n e r g yf u n c t i o nl i n e a r l y b e c a u s et h eo p t i m i z a t i o no ft h ee n e r g y f u n c t i o ni sc o m p u t e di nr e a l - t i m e ，t h eo p e r a t i o nt a k e nb yu s e ri st h es a m ea st h e t r a d i t i o n a ls s d w h i l et h er e s u l to ft h ed e f o r m a t i o no fo u rm e t h o di sb e r e rt h a nt h e t r a d i t i o n a lo n e si ns k e l e t o na n dg e o m e t r yd e t a i l s ( m e a nc u r v a t u r e s ) p r e s e r v a t i o n 。 ( 3 ) an o v e lm e s hd e f o r m a t i o nt r a n s f e r b a s e do nm e a n - v a l u es k e l e t o ni s i n t r o d u c e di nt h ed i s s e r t a t i o n d e f o r m a t i o nt r a n s f e ra d d sag e n e r a l - p u r p o s er e u s e m e c h a n i s mt ot h ea n i m a t i o np i p e l i n eb yt r a n s f e r r i n ga n yd e f o r m m i o no fas o u r c em e s h o n t oad i f f e r e n tt a r g e tm e s h t h et a r g e tm e s he s t a b l i s h e sac o r r e s p o n d i n gr e l a t i o n s h i p w i t ht h es o u r c em e s ha u t o m a t i c a l l yt h r o u g ht h em e a n v a l u es k e l e t o n ，i n s t e a do ft h e t r a d i t i o n a lc o r r e s p o n d i n gm a r k e r ss p e c i f i c a t i o nb yu s e r t h em e a n v a l u es k e l e t o na n d d i f f e r e n t i a ld o m a i nt e c h n i q u e sa r ei n c o r p o r a t e di n t ot h et a r g e tm e s hd e f o r m a t i o n ，a n d t h em a i nc o m p u t a t i o ni sas o l u t i o no fal i n e a re n e r g yc o n s t r a i n tp r o b l e m ，s oi tp r o d u c e s t h el o c a lg e o m e t r yd e t a i lp r e s e r v e dt a r g e tm e s h e se f f i c i e n t l y t h ea l g o r i t h mp r o d u c e s v i s i o np l a u s i b l ed e f o r m a t i o nt r a n s f e ri nr e a l - t i m e ，a n di t sw e l ls u i t e df o rn e w a n i m a t o r s ( 4 ) ad i f f e r e n t i a ld o m a i nm e s hd e f o r m a t i o nt e c h n i q u eb a s e da c t i v ec o n t o u rm o d e l i si n t r o d u c e di nt h ed i s s e r t a t i o n t h ek e yp o i n to ft h ea l g o r i t h mi st h es k e l e t o na n d v o l u m ec o n s t r a i n ta r es i m u l a t e db yt h ea c t i v ec o n t o u rm o d e l t h e nt h ea c t i v ec o n t o u r m o d e li sc o m b i n e dw i t ht h ed i f f e r e n t i a ld o m a i nd e f o r m a t i o na n dt h ed e f o r m a t i o ni s c o m p u t e dt h r o u g hal i n e a rl e a s t s q u a r em i n i m i z a t i o n t h ep u r p o s eo ft h ea l g o r i t h mi s t oc o n v e i r tt h en o l i n e a rs k e l e t o na n dv o l u m ec o n s t r a i n ti n t ot h e1 i n e a ro n e s i tt r a d e so f f t h e c o m p u t a t i o n t i m ea n dt h ea c c u r a t e p r e s e r v a t i o n o ft h e o r i g i n a l m e s h s c h a r a c t e r i s t i e s k e y w o r d s ：m e s h ，l e a s t - s q u a r em e s h ，f r e e - f o r md e f o r m a t i o n ，s k e l e t o ns u b s p a c e d e f o r m a t i o n ，d e f o r m a t i o nt r a n s f e r , d i f f e r e n t i a lc o o r d i n a t e s ，m e a n - v a l u ec o o r d i n a t e s ， a c t i v ec o n t o u rm o d e l v i 浙江大学博士学位论文图目录 图目录 图1 1 三维数字几何模型的应用领域1 图1 2 传统f f d 与扩展的e f f d 的变形过程5 图1 3 骨架子空间变形算法及其改进算法1 1 图1 4 多分辨率网格变形技术的框架1 5 图1 5 基于相同l a p l a c i a n 坐标不同局部变换的变形结果一1 6 图1 6 论文组织结构2 0 图2 1 非流形网格2 3 图2 2 微分域坐标的余切权重2 4 图2 3l a p l a c i a n 坐标的几何表示2 5 图2 4 均值坐标的计算2 6 图3 1 基于最小二乘网格的自由变形算法框架3 4 图3 2 基于最小二乘网格的自由变形算法的步骤3 5 图3 3 加入空间几何约束( 控制顶点) 的线性方程组的简单实例3 8 图3 4 不同控制顶点生成的最小二乘网格4 0 图3 5 不同权重生成的最小二乘网格4 2 图3 6 顶点e 上的局部标架4 4 图3 7 带凸包的平面网格自由变形对比4 7 图3 8 人脸模型的自由变形一4 8 图3 9 马模型的自由变形4 9 图3 1 0 恐龙模型的自由变形一5 0 图4 1 保持几何特征的均值骨架子空间网格变形算法的框架5 4 图4 2 骨架子空间模型5 6 图4 3 不同影响因子下变形结果的比较5 8 图4 4 传统及改进s s d 和本章算法的变形结果比较6 l x 浙江大学博士学位论文图目录 图4 5 联动变形结果6 2 图4 6 人体模型变形复制到卡通模型6 5 图4 7 均值骨架信息6 6 图4 8 普通骨架与均值骨架对比示例6 6 图4 9 利用虚拟四面体计算骨架仿射变换6 7 图4 1 0 骆驼模型变形复制到狮子模型6 9 图4 1 1 形状不同的网格模型之间的局部变形复制7 0 图5 1 基于动态轮廓模型的微分域网格变形算法的框架一7 4 图5 2 动态轮廓模型的内部能量的计算7 5 图5 3 动态轮廓模型在收敛运动中的清理操作7 7 图5 4 动态轮廓模型的生成与编辑7 7 图5 5 动态轮廓模型在网格变形中的骨架约束7 8 图5 6 动态轮廓模型在网格变形中的体积约束7 9 图5 7 用户控制顶点的约束作用。8 0 图5 8 原网格模型在变形操作中的各个区域8 1 图5 9 不同影响因子下变形结果的比较8 2 图5 1 0 马模型的变形结果8 3 图5 1 1 恐龙模型的变形结果8 4 图5 1 2 兔子模型的变形结果8 4 图5 1 3 手骨模型的变形结果8 5 x i 浙江大学博士学位论文表目录 表目录 表2 1 计算三角网格均值坐标的伪代码2 7 表3 1 网格模型数据及变形计算时间4 6 表4 1 网格模型数据及变形时间6 0 表5 1 网格模型数据及变形计算时间8 5 x l i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝婆盘堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权澎姿态堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期： 年月日 签字日期： 年月日 浙江大学博士学位论文致谢 致谢 值此论文完成之际，谨在此向多年来给予我关心和帮助的老师、同学、朋友 和家人表示衷心的感谢! 衷心感谢我的导师张三元教授。在博士生涯中，我庆幸能在浙江大学计算机 图形与图像实验室，并在张老师的指导下进行计算机图形学的研究工作。张老师 知识渊博、治学严谨、思维活跃、工作勤奋、关心学生，这一切是我今后学 - j 和 工作的榜样；尤其要感谢张老师给我一个十分宽松的工作环境，让我致力于喜欢 的研究领域，并悉心指导我从中选题、制定研究计划、攻克遇到的难题、论文的 写作等。张老师传授给我的专业知识和教导给我的为人处事之道都将使我受益匪 浅。 感谢叶修梓教授在学 - - j 和科研上给予我的帮助和指导；叶老师学术造诣精深， 治学态度严谨，待人以诚，对学生高度负责和严格要求，这将深深地激励着我们 未来的学 - - j 和工作。还要感谢张引副教授在科研和学习上给予我的关心和帮助。 感谢潘翔、徐舒畅、李根、徐芝琦、蒋跃华、丁展、沈建国、谭光华、刘楠、 王仁芳、欧阳毅、宫勇、高路等实验室的师兄弟妹们给予的支持和帮助。 感谢好友汪月林、董子龙、马森江、苏柏坚、朱文敏、富浩、赵天鹤、孙朝 亮，对于他们一如既往的支持和帮助，在此一并表示谢意。 深深感谢我的父母，他们的理解、支持、关怀和爱，伴随着我走过人生的每 一个阶段，无论是挫折还是成功，他们都默默的支持着我。对此我怀着无限的感 激，正是他们无私的奉献，让我一步步走得更远。 感谢薇薇，在我求学的过程中，你默默的付出和鼎立的支持以及为我所做的 一切，是我人生中最值得珍藏的回忆。 再次感谢在浙大的学 - j 和生活中所有那些给予过我帮助的老师、同学、朋友， 感谢你们让我的生活因为你们而更加美好也更加充满希望。 浙江大学博士学位论文 致谢 许秋儿谨致 2 0 0 9 年4 月 于浙大求是园 浙大学博学位论文第1 章绪论 第1 章绪论 随着计算机硬件及软件技术的进步，正逐渐渗透到各行各 三维动画电影，到最近的神舟七号升天的模拟演示，都体 型作为一种新的数字媒体，正被越来越多的行业领域所接 ( d ) ( e ) ( c ) 图ii 二维数字几何模型的应用领域。( 曲三维影视动画( 2 0 0 9 奥斯卡最佳动画片 w a l l e ”) 、 ( b ) 互动游戏( 来自暴雪咎司的新作 d i a b l o i l l ”) ，( 0 航空航天( 神舟七号出舱三维模拟动画， 来自人民网) 、( d j 遗产保护( 来自s t a n f o r d 大学的“t h e d i s t a l m i e h e l a n g e l o 项目1 】) ，( e ) 医疗 诊断( 来自互联网) ，( o 地图建筑( 来自g o o g l e 公司的 g o o g l es k e t c h u p ”产品) 浙江大学博士学位论文 第】章绪论 正如二维数字图像一样，我们需要工具能对其进行编辑修改才能达到应用的 目的，比如针对一副二维人脸的图像，我们有类似p h o t o s h o p 等工具进行红眼去 除的编辑 2 】。针对三维数字几何模型也是一样，我们需要各种可以进行编辑的工 具来达到不同应用的目的，如上图中神舟七号出舱的模拟不仅需要工具首先建立 起神舟七号航天器、宇航员的模型和纹理等等，还需要工具能控制模型的形状改 变( 比如宇航员挥手等动作) 。相比较二维笛卡尔坐标下的二维图像，三维数字 几何模型编辑的内容更加多样：几何滤波、几何融合、几何重采样、几何简化， 几何插值、几何变形等【3 】。其中三维数字几何模型的变形作为其中的一种编辑工 具，在三维数字几何处理中占据了重要的地位。 首先介绍三维数字几何模型的内部表达，它是三维数字几何模型处理( d i g i t a l g e o m e t r yp r o c e s s i n g ) 的基础，不同的内部表达决定着不同的处理算法。从计算 机图形学的发展历史来看，基本上分为三大类：基于原始数据( r a wd a t a ) 的表 达方式、基于实体( s o l i d s ) 的表达方式与基于曲面( s u r f a c e ) 的表达方式。其 中基于原始数据的表达方式主要有：点云( p o i n tc l o u d ) ，深度图像( r a n g ei m a g e ) ， 多边形集合( p o l y g o ns o u p ) 。这种三维数字几何的表达，正如它们的名称，一般 都是从现实世界的物体采集而来的原始数据，因此优点是表达简单，缺点也是很 明显的拓扑关系缺失。基于实体的表达方式主要有：体素( v o x e l s ) ，构造实体几 何( c o n s t r u c t i v es o l i dg e o m e t r y ，c s g ) ，扫描体( s w e e p ) 。这种三维数字几何的 表达，其优点是简单，整体易于修改，但缺点是局部操作不易实现并且绘制困难。 基于曲面的表达方式有：参数曲面( p a r a m e t r i cs u r f a c e ) ，隐式曲面( i m p l i c i t s u r f a c e ) ，细分曲面( s u b d i v i s i o ns u r f a c e ) ，网格曲面( m e s h ) 。这种三维数字几 何的表达方式，由物体的边界的面集合表示，因此优点是对于物体的局部操作十 分方便，而且容易在数据结构上附加各种非几何信息，缺点是参数曲面、隐式曲 面、细分曲面很难表达复杂物体的边界信息，曲面与曲面之间的过渡很难达到自 然( 如几何连续性) 。 从以上分析可以看到，虽然三维数字几何模型最后显示到屏幕上的效果都是 模型绘制后的光栅图，但是内部的表达却是多种多样的。针对不同的应用领域， 2 浙江大学博士学位论文第1 章绪论 通常会用到不同的表达方式。在c a d 领域主要采用网格、参数曲面、构造实体 几何和扫描体等；在医学应用领域常采用网格、隐式曲面和深度图像等；在游戏、 电影等娱乐业领域主要采用网格、参数曲面、细分曲面、多边形集合等的表示方 式。可以看到，其中多边形网格曲面，由于其能任意精度来表达任意拓扑物体的 表面，而且现有图形绘制流水线硬件设计最终的绘制都是基于一系列离散的三角 形，因此三角形网格模型成为三维数字几何模型中应用最广泛的模型之一。一般 的多边形网格通过三角化都能转化为三角形网格，因此在下文中如无特殊说明， 我们称的网格模型或网格曲面都是三角形网格模型，简称三角网格。 正是由于三角网格模型的广泛应用，并随着互联网的发展，人们将自己创造 的网格模型放到互联网上与别人共享；随着硬件采集设备的进步，人们又将现实 世界中的三维模型采集成三维数字几何模型( 主要是网格模型) ；由此催生了网 格这种三维数字几何模型的大量增长。基于不重复制造轮子的原则，人们就尽可 能的利用现有的网格模型来生产符合自己应用的新模型，因此对于网格模型的后 期编辑，尤其是变形编辑提出了要求。网格变形编辑，理论上在原有网格上进行 逐顶点的操作，就能得到符合用户需要的具有新形状的网格模型。然而，对于有 成千上万顶点的网格模型来说，逐个顶点地进行编辑，不但耗费人工，而且很难 保证每个顶点编辑后与邻接顶点之间的局部光顺等几何属性。因此，通过少量的 控制操作，对网格模型进行整体或局部的变形，得到保持原有网格特征的新网格 的变形技术，得到了人们的极大重视。 接下来我们根据用户操纵网格变形方式的不同，分别介绍相关网格变形算法。 1 2 自由变形技术( f r e e f o r md e f o r m a t i o n ) 自上世纪六十年代以来，以样条曲面为代表的参数曲面以其强大的曲面表达 能力，外加灵活的曲面控制方式得到了深入的研究。因此当人们进行网格曲面的 编辑时自然会想到能否借鉴连续的自由曲面( f r e e f o r ms u r f a c e ) 的控制方式，来 控制网格曲面的变形。上世纪八十年代到本世纪初，基于自由曲面编辑方式的网 格变形编辑技术被大量的研究出来，形成了网格模型上应用时间和范围最广的自 浙江大学博士学位论文第1 章绪论 由变形技术。用户可以通过采用点、线、面、控制网格等简单几何元素来控制复 杂的网格模型的形状，本节我们将主要介绍自由变形技术的研究现状及存在的问 题。 1 2 1 基于控制网格的自由变形技术 s e d e r b e r g 和p a r r y 首先提出了自由变形( f f d ) 的概念【4 】，其基本思想是把变 形定义为从原始物体空间到目标物体空间的三维映射。具体方法是通过将网格模 型嵌入到变形晶格中( l a t t i c e ) ，通过控制变形晶格的顶点变化，达到对嵌入其中 的网格模型进行变形的操作。在此方法中存在着两个映射过程：首先将世界坐标 系中网格模型上的顶点坐标映射到变形晶格所定义的局部坐标系的对应点( 局部 坐标) ；然后将变形后的局部坐标系中的点映射回世界坐标系中的顶点。后者映 射采用了张量积b e m s t e i n 多项式，因此嵌入其中的网格模型变形趋势与变形晶格 的形状是一致的。由于此变形方法的简单，易操作，变形效果也符合一般应用的 要求，所以很早得被商业造型软件所广泛使用，一个典型的代表是m a y a ，见图 1 2 。 此方法的基本思想成为后来众多扩展的基础，仅仅是映射函数定义上的不同， 就产生了许多变种：g r i e s s m a i r 等人采用均匀b 样条函数作为映射函数5 1 ，由于 b 样条具有局部性，所以局部变形效果更好；k a l r a 提出采用有理b e m s t e i n 基函 数的f f d 方法( r a t i o n a lf r e e f o r md e f o r m a t i o n ，简称r f f d ) 【6 】，与传统f f d 相 比，r f f d 方法增加了一个权值作为额外的变形控制手段：权值越大，该控制顶 点对最后变形的影响越大；l a m o u s i n 等人提出了基于n u r b s 的f f d 方法( 简称 n f f d ) 【刀，n f f d 继承了上述b 样条f f d 方法与r f f d 方法的优点，但是该方 法在映射中需要通过复杂的数值方法求解，计算量变大。 上面介绍的基于变形晶格的f f d 方法，有一个共同的缺点是由于变形晶格是 平行六面体( p a r a l l e l e p i p e d i c a ll a t t i c e ) ，所以如果需要更精确的控制变形结果， 需要分片更多的晶格，因此造成了控制顶点个数的大量增长，增加用户的操作量， 失去了f f d 方法本身控制方便的目的。 4 断 学博学位论文第1 章绪论 不同于以上映射函数的改进，c o q u i u a r t 提出了扩展的f f d 方法( e x t e n d e d f r e e f o r m d e f o r m a t i o n ，简称e f f d ) 口】。该方法的核心是通过组合多个简单的棱 柱形变形品格( p r i s m a t i cl a t t i c e ) 构成复杂的符合物体形状的变形晶格，达到易 于交互的变形操作。扩展p p d 方法的其他部分与传统的f f d 方法是一样的，唯 一不同的是变形品格的形状以及计算局部坐标的方法，见图1 2 。虽然e f f d 允许 用户定义更加复杂的变形空间，使得变形操作更加直观，但是由于e f f d 变形晶 格的构造复杂，而且需要保持相互之问的连续性，因此在使用上受到了限制。 ( b ) ( d ) 圉1 , 2 传统f f i ) 与扩展的e f f d 的变形过程。( a ) ( b ) 为传统f f d 变形前后的状态( 来自三维 造型软件m a y a ) ，0 ) 埘) 为扩展的e f f d 变形前后的状态( 来自文献) 。 其后，许多改进控制网格的自由变形技术相继被开发出来，m a c c r a c k e n 等提 出7 一种控制网格为任意拓扑结构的f f d 方法【”，此方法的基本思想是：应用 c a t m u l l c l a r k 细分控制网格形成一系列的细小网格，被操作的网格模型的顶点 浙江大学博十学位论文 第l 章绪论 相对于细分的控制网格参数化。用户编辑控制网格，重新细分控制网格，根据再 次细分后的细小网格的顶点变化，利用参数化得到的参数计算出被操作的网格模 型顶点的新位置。后来，f e n g 等人在此基础上改进了此细分控制网格的自由变形 算法【1 1 】。因为控制网格可以是任意拓扑的，所以避免了e f f d 中组合多个控制晶 格时连续性的问题。但是此方法在每次变形计算时，都需要额外的迭代细分计算， 使得算法复杂度剧增。 最近，随着均值坐标( m e a n v a l u ec o o r d i n a t e s ) 的研究深入，j ut a o 等人进 一步提出了利用一般封闭三角形网格作为控制网格的自由变形技术【1 2 1 ，极大地扩 展了自由变形技术的应用范围。算法的基本思想是：对于给定的网格模型，计算 其每个顶点相对于控制网格顶点的均值坐标，在用户操纵控制网格时，通过均值 坐标插值计算出网格模型顶点的新坐标。此后，这种以封闭三角网格为控制网格 ( 被形象地称为c a g e ) 的自由变形技术不断发展，j o s h i 等人提出了基于调和坐 标( h a r m o n i cc o o r d i n a t e s ) 的自由变形技术【1 3 1 ，此方法改进了均值坐标不拥有的 两个属性：内部局部性( i n t e r i o rl o c a l i t y ) 和非负性( n o n n e g a t i v i t y ) ，获得了更 好的自由变形效果，但是此方法没有闭合的计算公式，需要通过迭代解获得，因 此效率上比均值坐标差。l i p m a n 等人提出了基于格林坐标的自由变形技术【1 4 】， 此方法改进了均值坐标仅仅插值网格顶点，增加了三角面片上的法向插值，因此 能够得到更好的自由变形效果，而且此方法有闭合的计算公式，只需线性解就能 得到变形结果，因此效率上比调和坐标好。 1 2 2 基于其他控制手段的自由变形技术 l a z a r u s 等人提出了轴变形( a x i a ld e f o r m a t i o n ) 方法【1 5 】，采用空间曲线控制 物体变形。此方法通过定义在三维空间中的曲线，与物体之间的对应关系，进行 变形操作。c h a n g 等人提出一种基于广义d ec a s t e l j a u 的轴变形方法【1 6 1 ，从效果上 看与轴变形方法类似，只是基于不同的数学原理：通过迭代仿射变换，使物体沿 一条b d z i e r 曲线变形。 w i r e s 变形也是一种利用曲线控制物体变形的技术【1 7 1 ，但是其变形控制手段与 6 浙江大学博士学位论文 第1 章绪论 之前介绍的轴变形技术略有不同，此方法模拟现实世界中雕塑家控制模型的方 法，用一组任意的曲线近似变形物体的几何外形，通过控制这些曲线来达到网格 模型的形状控制，所以此方法后来成为m a y a 中的极具特色的变形方法之一，沿 用至今。由于控制曲线的任意性，它被大量的应用到三维影视、游戏等人脸表情 的动画变形设计中。 相应的，基于曲面的自由变形技术也得到人们的广泛关注，f e n g 等人首先提 出了基于曲面控制的变形技术 1 8 】，在此方法中，用户主要通过形状曲面来控制物 体的形状，通过高度曲面来控制物体变形时的伸缩程度。之后冯结青等人又提出 了直接嵌入的曲面控制变形方法【1 9 】，由于局部坐标的计算是线性的，因此大大加 快了变形计算的速度。 前面介绍的自由变形技术都是通过控制简单的代理模型( 如控制网格，w i r e s 等) ，间接地完成对原始模型的变形编辑。h s u 等人于1 9 9 2 年提出了一种直接作 用于网格顶点上的自由变形技术【2 0 1 ，虽然此技术无需用户操作代理模型，但是它 的原理是利用最小二乘法通过变形后网格上的点的新位置来反求控制网格顶点 坐标的变化，因此在技术范畴上仍然属于自由变形技术。但是它的用户操作方式 对于后来的“基于网格曲面的变形技术( s u r f a c e b a s e dd e f o r m a t i o n ) ”起到了很好 的借鉴作用，下文有详细介绍。 m i l l i r o n 等人将自由变形的概念统一到一个空间变形的数学模型中，并且利用 此数学模型将之前的部分自由变形技术进行了改进，由此建立起一个自由变形技 术的统一框架【2 1 1 。 1 2 3 自由变形技术的优缺点 首先介绍自由变形技术的优点，以及其在网格变形的发展历史中不可替代的 位置。 ( 1 ) 操作简单直观。用户可以通过采用点、线、面、控制网格等简单代理模型 来控制复杂的网格模型的形状，这对于拥有成千上万顶点的网格模型的编辑来讲 是它最大的优点，也决定了自由变形技术成为当今商业软件中被使用最多的变形 7 浙江大学博士学位论文第l 章绪论 工具。 ( 2 ) 适合局部变形操作。用户可以构造局部的代理模型进行局部的编辑，比如， 将手臂变粗的变形( 可以使用e f f d 等) 或者将人脸眉毛弯曲的变形( 可以使用 调和坐标等) ，这种需要局部操作的并且改变原网格模型的几何细节，最合适的 变形技术就是自由变形技术。因为此种变形操作一般骨架语义是不明显的，所以 下文介绍的“骨架驱动的变形技术( s k e l e t o n d r i v e nd e f o r m a t i o n ) ”是不适合使用 的，而且因为又要改变原网格模型的几