（计算机应用技术专业论文）感兴趣区域的拉普拉斯网格形变算法.pdf

摘要 摘要 三维网格形变技术是计算机图形学领域的研究热点，在制造业，娱乐业， 游戏工业等领域有着广泛的应用。 随着三维扫描技术的日益成熟，人们可以方便地获取几何细节丰富的三维 网格模型，在精确刻画模型局部几何特征的同时也为三维网格的形变处理提出 了新的挑战。传统的自由形变和多分辨率算法在形变过程中难以高效地保持网 格曲面的原始几何细节特征，而最新提出的基于局部表示的拉普拉斯差分坐标 形交算法在细节特征的保留方面取得了新的突破，具有明显优势，但是拉普拉 斯差分坐标在旋转和缩放变换是不具有不变性。 本文针对三维网格模型的感兴趣区域，以拉普拉斯差分坐标为基础，提出 了感兴趣区域的拉普拉斯网格形交算法框架。实验结果表明，我们的算法形变 自然，具有良好的视觉效果。本文的具体工作如下： 1 将对偶拉普拉斯差分坐标表示方法引入到感兴趣区域网格形交中，提出了 感兴趣区域的对偶拉普拉斯网格形交算法。以对偶拉普拉斯差分坐标表示 网格的局部参数信息和局部几何信息，结合位置约束，形变方程可归结为 一个二次误差函数。最小化该误差函数得到一个超定的稀疏线性方程组， 在最小二乘意义下迭代求解，重构形变后的网格。迭代过程采用预处理双 共轭梯度算法( p r e c o n d i t i o n e db i c o n j u g a t eg r a d i e n tm e t h o d ，p b c g ) 。该算法 通过行索引稀疏存储模式( r o w - i n d e x e ds p a r s es t o r a g em o d e ) 压缩存储稀疏 的系统矩阵，相对于传统的牛顿、高斯一赛德尔算法，具有更好的效果。 在迭代中通过逐步更新对偶点的位置和对偶拉普拉斯坐标，进一步提高形 变的运算效率，减小失真。 2 将加权的思想应用于拉普拉斯形变算法，给出了感兴趣区域的加权拉普拉 斯形变算法。通过对拉普拉斯项、形变控制项和边界控制项设定不同的权 值，实现三维模型感兴趣区域网格的不同形变效果，提高了网格形变算法 在实际中的适用性。 3 给出了直观易用的交互界面。用户只需要直接的屏幕选点即可完成感兴趣 区域的选择和边界区域的确定，避免了一般三维模型形变界面对非专业人 士的复杂性。 关键词对偶拉普拉斯；加权；感兴趣区域；三维网格形变 a b s t r a c t m e s hd e f o r m a t i o ni so n eo ft h eh o t t e s tt o p i c si nc o m p u t e rg r a p h i c s ，a n di t s r e s e a r c hr e s u l t sh a v eb e e nw i d e l ya p p l i e di nag r e a td e a lo f a r e a s ，s u c ha sm e c h a n i c a l m a n u f a c t u r e ，v i d e oe n t e r t a i n m e n t ，g a m ei n d u s t r ya n ds oo n w i t ht h er a p i dd e v e l o p m e n to f3 ds c a n n i n gt e c h n o l o g y , i ti sc o n v e n i e n tt o o b t a i n3 dm e s hm o d e l sw i mr i c hd e t a i l s i tn o to n l yi m p r o v e st h ea c c u r a c yi n d e s c r i p t i o no fm o d e l s ，b u ta l s ob r i n g san e wc h a l l e n g ei n3 dm e s hd e f o r m a t i o n s i m u l t a n e o u s l y i t sn o ta ne f f e c t i v ew o r kt ow r f o r mt h ed e f o r m a t i o nb yu s i n gt h e c o n v e n t i o n a lf r e e - f o r md e f o r m a t i o n s ( f f d ) a n dm u l t i - r e s o h i f i o nt e c h n i q u e h o w e v e r , t h em e t h o dw h i c hd e s c r i b e st h em e s hs l l g f a c 七w i t hl a p l a c i a nd i f f e r e n t i a l c o o r d i n a t e sg i v e sab r e a k t h r o u g h , a n di ti s g o o d a t p r e s e r v i n gt h eg e o m e t r y i n f o r m a t i o no fo f i g m a ls u r f a c ei nd e f o r m a t i o n , b u tt h el a p l a c i a nd i f f e r e n t i a l c o o r d i n a t e sw i l lc h a n g ew h e nr o t a t ea n ds c a l ep r o b l e m i nt h i sp a p e r , w ea i mt ot h ed e f o r m a t i o ni nt h er e g i o no fi n t e r e s t ( r o i ) o ft h e m e s h b a s e do nt h el a p l a c i a nc o o r d i n a t e s ，w ep r o p o s en e wm e s he d i t i n gm e t h o d s f o rt h er o ii nm e s h e x p e r i m e n t ss h o wt h a to u rs y s t e mc g i v en a t u r a ld e f o r m a t i o na n d p l e a s i n gv i s u a le f f e c t ，s p e c i f i c a l l y , w em a k et h ef o l l o w i n gc o n t r i b u t i o n s ： 1 w eh a v ei n t r o d u c e dt h ed u a ll a p l a c i a nc o o r d i n a t e si n t om e s hd e f o r m a t i o ni nr o i ， a n dg i v ean e wm e s hd e f o r m a t i o nf r a m e w o r ki nr o i 、衍t 1 1d u a ll a p l a c i a n w e d e s c r i b et h es u r f a c eb yd u a ll a p l a e i a nc o o r d i n a t e s t h eg e o m e t r yp r o p e r t yi s d e c o m p o s e di n t ol o c a lp a r a m e t e f i z a t i o ni n f o r m a t i o na n dl o c a lg e o m e t r yi n f o r m a t i o n w h i c ha r et w os e t so fs c a l a rd a t a c o m b i n e dw i t ht h e p o s i t i o n c o n s t r a i n t s ，t h e r e c o n s t r u c t e dm e s hi so b t a i n e db ys o l v i n gaq u a d r a t i cm i n i m i z a t i o np r o b l e m w h i c hp r e s e r v e st h em e s hd e t a i li nl e a s ts q u a r es e n s e p r e c o n d i t i o n e db i c o n j u g a t e g r a d i e n tm e t h o d ( p b c g ) i sa d o p t e dt oi t e r a t i v e l yu p d a t et h ep o s i t i o n so ft h e p r i m a lv e r t i c e sa n dd u a ll a p l a c i a nc o o r d i n a t e s p b c gs t o r a g e st h ee l e m e n t so f s p a r s es y s t e mm a ：t r i xw i t hr o w - i n d e x e ds p a r s es t o r a g em o d e c o m p a r e dw i t ht h e c o n v e n t i o n a lr u l e sa sn e w t o na n dg a u s s s e i d e l ，p b c gw o r k sm o r ee f f i c i e n t ，a n d t h eu p d a t ep r o c e s si m p r o v e st h ee f f i c i e n c ya n dr e d u c e sd i s t o r t i o n s 2 c o m b i n e dw i t hw e i g h t i n gs c h e m e ，w e p r e s e n tw e i g h t i n gl a p l a c i a nm e s h d e f o r m a t i o ni nr o i b yu s i n gd i f f e r e n tw e i g h t si nl a p l a c i a no p e r a t o rh a n d l e sa n d b o u n d a r yv e r t i c e s ，t h ew e i g h t i n gl a p l a c i a nd e f o r m a t i o nf r a m e w o r kc a ng i v e d i f f e r e n tr e s u l t so f3 dm o d e l st os a t i s f y i n gd i f f e r e n tr e q u i r e m e n t s i ti m p r o v e st h e i l l 北京工业大学工学硕士学位论文 a d a p t a b i l i t yi nt h ea p p l i c a t i o n 3 o u rs y s t e mp r o p o s e sa ni n t u i t i v ei n t e r f a c ew i t he a s ym a n i p u l a t i o n u s e r sc a n s e l e c tt h er o ia n db o u n d a r yv e r t i c e s b yo n l yc l i c kt h ev e r t i c e so nt h es c r e e n d i r e c t l y i tm a k e st h ed e f o r m a t i o ni n3 dm e s hb e c a m es i m p l e ，e s p e c i a l l yf o r n o n e x p e r t s k e y w o r d sd u a ll a p l a c i a n ；w e i g h t i n g ；l e g i o l lo f i n t e r e s t ( r o d ；3 dm e s hd e f o r m a t i o n w 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：驻日期：肄缚归目 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：驻导师签名：二嵫日期：班月p 目 第1 章绪论 1 1 引言 第1 章绪论 三维几何模型作为一种新的数据媒体，近十年得到广泛的应用。凭借以往 媒体无可比拟的逼真性和交互性，三维模型给用户带来图像、视频等媒体所不 具有的视觉感受。逼真的三维图形场景可使用户感觉就像是处于真实的世界中， 甚至超越真实，如实现比现实更逼真的照明和音响效果等，并可以以多种方式 与场景进行交互，从而给用户带来沉浸式的体验。三维几何数据所表示的场景 可以是计算机合成出来的虚拟场景，从两极大地节约实物的使用。除了能产生 与图像、视频等媒体不同的视觉和交互体验外，三维几何数据通常还携带了图 像和视频所不具有的几何信息，而这些几何信息对于c a d 等的应用是非常重要 的。 三维几何模型大都以网格的形式来表示，主要是通过三维建模软件创作或 者通过三维扫描仪来获取【】初始图形，然后通过离散化处理，由采样点的相互 连接构成能够逼近原始物体的三维网格模型，如果用三维建模软件来制作复杂 的三维模型，则需要较熟练的技能以及细致耐心的操作。目前市场上最流行的 三维扫描仪是美国c y b e r w a r e 公司的产品【6 j 。 三维网格形变作为三维造型的一种新兴手段，以其巧妙的实现，实用的价 值，诱人的前景，不断吸引着更多的研究，已成为计算机图形学领域十分活跃 的一个研究热点，在商业、制造业、建筑业、教育、医学、娱乐、艺术等领域 有着广泛的应用。比如网上虚拟商城、网络视频游戏、建模、各种运动模拟等 应用领域就是一些具体的实例，特别地，三维网格的形变在动画制作中不断展 现出的重要作用和发展前景，把原三维图形和形变后的三维图形进行插值可以 得到一系列中间图形，这样可以产生动画效果。各种新的三维网格形变算法在 动画形变，动画角色夸张及网格渐变等方面得到广泛的应用，这些应用反过来 又为三维网格形变算法的深入研究提供了新的推动力。所以，随着三维网格形 变处理研究的深入，三维几何数据将越来越广泛地进入人们的生活，改变人们 的生活、生产方式以及工作、交流方式，会给人类和社会带来很大的方便和利 益。因此，本课题的研究也是相关实际应用的迫切需求，具有巨大的应用前景 和社会、经济价值。 三维网格形变的研究是涉及计算机图形学、拓扑学、微分几何等学科的交 叉性课题。相对于文本、声音、图像、视频等数据编辑的研究工作而言，三维 北京工业大学工学硕士学位论文 网格形变的研究还是一个较新的课题。三维网格模型的几何数据与其它媒体数 据有很大不同，比如与图像相比，网格的顶点间存在着不规则的连接关系，难 以控制，并且数据量更大，这些都给三维网格模型的形变带来了新的问题和挑 战。虽然很多学者对三维网格形变进行了一些研究工作，并且取得了一定的进 展，但或者算法比较繁琐，计算量较大，不能实时交互，或者不能产生自然逼 真的三维图形，离完全实用还有较大的差距，还存在着很多的问题需要解决。 对三维网格形变的研究也能促进对三维几何数据的获取、表示等技术的研究。 因此，本项目具有较大的学术价值。 目前三维网格形变的研究正方兴未艾，新的成果不断涌现。研究成果比较 显著的国外研究机构主要有：美国的m i c r o s o f t 、贝尔实验室、加州理工学院、 麻省理工学院，德国的达姆斯塔特科技大学，以及以色列的特拉维夫大学和以 色列理工学院。据作者的了解，国内目前只有浙江大学c a d & c g 国家重点实 验室和北京大学视觉听觉信息处理国家重点实验室等少数单位从事相关的研究 工作。因此，对三维网格形变的研究工作应给予重视。 1 2 三维网格数据的表示 根据所采用的三维场景建模、绘制方法的不同，三维图形数据主要可分为 多边形网格、纹理映射时所用的纹理图像、基于图像的绘制( i m a g e b a s e d r e n d e r i n g ，i b r ) 、三维动画以及参数化图形数据等。 本文所研究的是三维多边形网格模型的形变问题。由于可以将任意多边形 剖分成三角形，多边形网格可通过三角化转化为三角形网格，所以，三角形网 格是多边形网格模型的最基本形式，正因如此，三角形网格得到了很多图形库 ( 如o p e n g l ”，d i r e c t 3 d i s l ) 的支持，大量的图形处理芯片也是针对三角形网 格设计的。图1 1 显示了一个三维三角形网格模型。 图1 - 1 三角形网格 f i g u r e1 - 1 a i r i a n g l em e s h 第1 章绪论 下面对三维三角形网格的定义与表述进行介绍。 三维三角形网格模型是连续曲面的分段线性逼近，网格顶点是连续曲面上 的离散采样点，这些离散采样点相互连接成为若干三角形，作为曲面上对应部 分的线性逼近。三维三角形网格模型在形式上可以表示为g ( k ，其中k 是 一个单纯复合形( ( s i m p l i c i a lc o m p l e x ) ，用以记录网格模型的点、边、面连接关 系，即网格模型的拓扑信息；v = v 。1 1 f 即 ，v ；er 3 是网格顶点位置集合， 记录了网格各顶点的坐标位置，即网格模型的几何信息。 单纯复合形k 由顶点序号集合“1 2 ，n 的子集族构成，这些子集族称之 为单形( ( s i m p l e x ) ，在三维三角网格模型中，单形分为三类：顶点( o 维单形) ， v e r t e x = ( 1 ) ，( 2 ) ，( 田 ；边( 1 维单形) ，e d g e = ( f ，- ) ，) ，( 1 i , j 疗) ，如果 ( i ，) e d g e ，则表明顶点i 与j 之间有边相连；面( 二维单形) ， f a c e = ( f ，j ，d ，k ( 1 i , j ，k ”) ，如果( f ，j ，k ) f a c e ，则表明顶点i ，j 与k 连 接成一个三角形。 如果网格顶点v ，与v ，之间有边相连，则称v ，为v 。的邻接顶点，而由顶点v 。 的所有邻接顶点组成的集合称为顶点v ，的邻接集合，记为 n ( o = v ，i ( i ，) e d g e ，邻接顶点的总数称为顶点v 。的度( v a l e n c e d e g r e e ) ，记 为d 。 每个顶点有j ，y ，彳三个坐标分量，每个三角形由它的三个顶点确定。每 个顶点除了坐标以外，还可以包含其它各种用于绘制的属性信息，如每个顶点 的法向、颜色、纹理坐标等。上述描述方法广泛应用于各种网格文件格式中， 如常用的p l y ，o b j ，w r l ，3 d s ，x ，o f f 等格式。 1 3本文的研究内容及方法 在实际应用中，用户可能只对三维两格的小部分区域感兴趣，希望该区域 能够快速地实现高质量的形变效果，而网格中其它的大部分区域并不参与形变 运算，在整个过程中保持不变。在形变编辑中，如果对这两部分区域一视同仁， 将整个模型的网格顶点都进行运算求解，计算过程将非常复杂，对大网格模型 的形变运算尤其如此。这无疑是一种浪费，而且增加了运算的复杂度，影响了 形变的有效性。所以，针对感兴趣区域进行的形变也就势在必行。 在三维网格形变编辑的各种算法中，拉普拉斯差分坐标形变算法实现简单、 效果良好、操作简便，并可实现形变、m o r p h i n g 、光滑、融合等多种网格编辑 功能。但是，由于拉普拉斯差分坐标是在全局坐标中来表示的，尽管其能保持 平移不变性，但不是由于存在旋转和缩放变换的问题，给实际应用带来了一定 的影响。 北京工业大学工学硕士学位论文 针对以上情况，本文以感兴趣区域的拉普拉斯网格形变为研究内容，主要 进行了以下两方面的工作。 一，提出了感兴趣区域的对偶拉普拉斯网格形变算法，同时给出了一个直 观易用的形变交互界面解决感兴趣区域的确定问题。本方法的思想是通过采用 对偶拉普拉斯差分坐标来表示网格曲面的几何特性，以形变位置为约束条件， 最小化形变前后曲面对偶拉普拉斯算子的误差。形变方程可归结为一个二次误 差函数，最小化该误差函数得到一个超定的稀疏线性方程组，在最d , - 乘意义 下求解，并采用预处理双共轭梯度算法进行迭代，以减少失真，得到重构网格 的顶点位置坐标。实验结果表明，该算法具有较高的编辑效率，形变结果自然， 视觉效果良好。 二，提出了感兴趣区域的加权拉普拉斯形变算法。通过引入加权机制，对 拉普拉斯形变框架中的拉普拉斯细节保留项、形变位置控制项和边界位置控制 项分别采用拉普拉斯权因子、形变控制权因子和边界控制权因子进行加权处 理。针对不同的应用场合和应用需求，改变各权因子的值，即可得到不同的形 变效果，增强了网格形变算法的需求适应性。 1 4论文结构 本文的研究工作主要针对感兴趣区域的三维网格拉普拉斯形变算法。各章 的安排如下： 第一章绪论。主要介绍了三维网格形变的研究背景及意义，说明了三维 网格数据的表示，并对本文的研究内容及方法做了总体介绍。 第二章三维网格形变综述。阐述了网格形变应满足的要求，并主要介绍 了三维网格形变的各种算法，包括空间自由形状( f f d ) 及其扩展算法、多分辨率 网格形变算法、基于局部表示网格形变和它的一些改进算法。 第三章拉普拉斯形变算法基础。介绍了当前网格形变的研究热点拉普拉 斯形变算法，对拉普拉斯的基本数学原理、拉普拉斯差分坐标的建立、拉普拉 斯网格形变框架进行了详细阐述，同时也指出了拉普拉斯形变算法存在的问题。 第四章感兴趣区域的对偶拉普拉斯形变。对感兴趣区域的网格，提出了 一种感兴趣区域的确定方法。针对拉普拉斯存在的问题，采用对偶拉普拉斯差 分坐标来表示网格曲面特性，结合形变位置约束，最小化一个二次误差函数， 在最小二乘的意义下重构形变网格，并结合实验结果进行了分析和讨论。 第五章感兴趣区域的加权拉普拉斯形变方法。引入加权的思想，介绍了 拉普拉斯坐标的几种不同加权机制，并通过加权机制对拉普拉斯形变框架进行 了改进，最后给出了感兴趣区域的加权拉普拉斯形变的实验结果和相关分析。 第1 章绪论 最后，结论部分对本文的研究工作进行总结，并对该课题下一步的研究方 向进行了展望。 第2 章三维网格形变综述 2 1引言 第2 章三维网格形变综述 三维网格形变技术起源于几何造型领域，它最初是作为一种几何造型方法 提出来的，后来由于它在模拟柔性物体动画方面的巨大潜力，逐渐地在计算机 动画领域中得到了很大的发展和广泛的应用【9 】。 网格形变( m e s hd e f o r m a t i o n ) 是指利用用户指定的形变特征点的目标位置 作为约束条件，将三维网格模型调整为用户预想的姿态或形状，在动画制作中 可以形成动画序列中的关键帧。另外网格形变也是获得夸张的动画角色的重要 手段，而夸张正是动画艺术的主要特征之一，所以网格形变是关键帧动画等设 计中的重要工具，也是网格模型编辑中最重要的部分。形变示例如图2 1 所示。 a ) 源曲面b ) 形变后的曲面 图2 1 形变示例 f i g u r e2 - 1a ne x a m p l eo f d e f o r m a t i o n 一个基本的形变算法是移动网格的一个顶点，这个顶点的位置变化传播到 此网格上的周围顶点，使周围顶点的位置也随其发生变化，这种形变方法简单 直观，并且功能强大，好像在处理柔软的物体。实际上有许多更高级的网格形 变法都用到了这个基本的编辑方法。 网格曲面形变是网格处理的核心技术，其目的是为用户提供直观，高效的 曲面编辑手段，实现复杂几何模型的构造。网格模型形变算法的内容比较丰富， 主要经历了早期的自由形变( f r e e f o r md e f o r m a t i o n s ，f f d ) ，其后的多分辨率算 法( m u l t i r e s o l u t i o n ) 和近期的基于局部表示的网格形变算法。 北京工业大学工学硕士学位论文 这一章从形变技术的发展状况、实际应用以及各种形变方法优缺点等各个 层面对三维网格的形变算法作了阐述。结构组织如下：2 2 节介绍了网格编辑的 要求；2 3 节集中介绍了早期出现的自由形变( f f d ) 和它一系列的拓展方法；2 4 节对后来出现的多分辨率网格模型编辑算法进行了总结；2 5 节则介绍了基于局 部表示网格形变算法的研究现状以及他的一些扩展算法；2 6 节是本章小结。 2 2网格形变编辑的要求 网格形变是当前计算机图形学上的一个研究热点和难点问题。一方面，随 着经济的发展，计算机动画、三维影视及机械曲面造型对网格形变技术的迫切 需要，使得形变编辑成为应用技术的研究热点，另一方面，由于形变技术本身 的高要求和复杂性，使得网格形变成为富有挑战性的难点问题。 网格形变要求在对模型进行自然形变的时候，既要保持其形变位置的准确 性，同时还要保持原始网格本身的局部细节特征。形变位置是对编辑的空间要 求，而局部细节则是对编辑的几何特性要求。在编辑的过程中，这两个方面的 重要性都不容忽视。此外，形变算法的复杂性、实时性以及用户界面的交互性 都是网格形变中需要认真考虑的问题。 尽管三角形网格形变已经取得了一定的进展，但还是存在许多的问题有待 解决。本章接下来的几节将对网格形变算法进行介绍。 2 3自由形变( f f d ) 及其扩展 为了更方便、直观地构造和编辑三维形体，b a r r 率先将形变思想引入到几何 造型领域1 1 0 1 。他模拟了力学中常见的几种形变，如拉伸、均匀张缩、扭转和弯 曲等，并给出了这些形变的数学表示。应用b a r r 的方法，可以生成许多类型的三 维几何形状。由于该方法仅能用于特定的几何形体，一般称其为非自由型形变。 1 9 8 6 年s e x i e r b e r y f i p a r r y 提出了一种崭新的形变算法，称为自由形变l l ”。其核 心思想在于：形变操作不是直接作用于物体，而是作用于物体所嵌入的形变空间， 如果形变空间被改变了，则嵌入其中的物体自然随之改变。f f d 首先引入一个形 变工具，由一个均匀剖分的三参数张量积b e z i e r 体的控制顶点组成，称为格子； 然后将形变物体线性地嵌入此b e z i e r 体的参数空间，当调整格子中的控制顶点位 置时，参数体的形状会发生变化，嵌入其中的物体就会随之形变。采用自由形变 方法对模型进行形变运算的示例如图2 2 所示。f f d 方法是柔性物体形变中最适 用的一种方法，但其格子块的形状为平行六面体，这在一定程度上限制了它的应 用。 c o q u i l l a r t l l 2 】提出的扩展f f d 方法( 简称e f f d ) 使得初始的格子可以有更多的 第2 章三维网格形变综述 形状，如棱柱体、圆柱体等，从而增加了f f d 技术的使用范围。有理f f d 方法( 简 称砌7 f d ) 是对f f d 方法的另一种推广“，它把格子表示为有理形式的三参数张量 积b e z i e r 体，从而使用户还可以通过权因子来控制形变。l a z a r u s 等人【1 4 】提出了轴 形变方法( a x i a ld e f o r m a t i o n ) ，以牺牲一部分形变的自由度来换取交互的灵活性， 在轴形变方法中，用户首先根据物体形变的要求定义一条轴向参数曲线，将形变 物体附着在轴曲线的局部空间中，然后用传统的线编辑技术修改轴曲线的形状， 形变则由轴线传递给物体。不同于f f d 的轴形变的方法，冯结青 1 5 j 6 将物体嵌入 到参数曲面空间，然后通过改变参数瞌面来控制物体的形变。 图2 - 2f f d 形变示例 f i g u r e2 - 2t h ed e f o r m a t i o nw i t hf f d h s u 等人【17 】于1 9 9 2 年提出的直接操作f f d 方法( d i r e c tm a n i p u l a t i o no ff f d ， 简称d f f d ) 则采用了另一种策略：首先将物体嵌入b 一样条体，通过编辑所选取物 体上点的方法控制物体形变。其实现方法是：根据用户选择点的位移，反求导致 这种变化的f f d 控制网格的位移，从而达到直接操纵物体形变的目的。b 一样条体 控制顶点的反求是通过计算伪逆矩阵的方式实现的。所以d f f d 方法的形变控制 最为直接，但是由于涉及伪逆矩阵的计算，该方法的计算量增加很多，从而影响 了用户的实时交互。h u 等人【i8 】在2 0 0 1 年提出的基于n u r b s 体直接操纵f f d 方法 采用了类似的思想，但其不需要求解伪逆矩阵。2 0 0 3 年，s h i n 等人1 1 9 1 提出了基于 骨架的自由形交算法，通过提取原始网格的范诺图骨架网格，然后针对骨架网格 进行自由形变。但是该方法对于球状物和具有突兀边界的物体的形变具有局限 性。j u 等人【2 0 1 2 0 0 5 年将中值坐标引入f f d ，用于封闭三角形网格的形变。 总的来说，f f d 方法的主要优点是：与物体的表示方法无关，交互控制直观， 形变过程光滑等1 2 1 1 。但由于控制顶点较多，难以逼近任意拓扑的物体形状，所 以物体形变控制不够灵活和直观。人们要获得所需的形变效果，通常要进行多次 繁琐的控制顶点编辑工作。当l a t t i c e 形变和物体形变之间的对应关系并非很直观 北京工业大学工学硕士学位论文 时，基于f f d 的形变方法就难以奏效。而当模型含有丰富细节并且运动形态较为 复杂时，该方法不能保留其局部几何细节特征，其形变能力有限。针对这个问题， 出现了多分辨率编辑方法和基于微分属性的局部表示网格形变算法。 2 。4 多分辨率网格形变算法 多分辨率三维网格模型形变( m u l t i r e s o l u f i o nm e s hd e f o 】m a t i o n ) 圈算法是 基于多分辨率表示的。其主要思想是对原始网格模型进行网格重构 ( r e m e s h i n g ) ，将原始网格模型的几何信息分解为若干频带，获取一组由基两格 ( b a s em e s h ) 及若干层细化( r e f l n e m e n t ) 网格组成的多分辨率网格表示，其中基网 格反映了原始网格模型的基本轮廓，而细化网格模型由粗至精逐层包含了原始 网格模型的局部几何细节。利用多分辨率网格表示进行网格形变时，操作者首 先将分解后的简单的基网格手工调整为预想姿态，再通过细化算子将各层细化 网格的几何细节成分自动恢复到形变后的基网格上而获得网格模型的最终的形 变效果。多分辨率表示能够使得原始网格模型在不同频带上的细节在形变过程 中得到了有效地保持，因此可以获得自然而合理的形变结果。采用多分辨率算 法进行形变运算的示例如图2 3 所示。 普通三维网格模型并不具有多分辨率表示形式，需要对网格模型进行重构 与改造方能获得多分辨率表示。实现网格多分辨率表示的方法可分为两类：第 一类方法基于网格子分算法( s u b d i v i s i o n ) ，在多分辨率分解过程中将原始网格模 型简化为基网格，并在简化过程中建立原始网格模型到基网格的参数化映射， 在多分辨率重构过程中，利用子分算法逐层获取细化网格，并根据参数化信息 记录各层细化网格模型中网格顶点位置的预测误差，作为多分辨率表示中的细 节信息。该方法可用较少的层级表示原始网格模型，基网格与各层细化网格模 型之间存在固定的子分拓扑连接关系，易于分层编辑与合成，但却改变了原始 网格模型的拓扑连接关系，这类算法主要有文献 2 3 - 2 7 ，其中文献唧提出的m a p s 方法最为常用；第二类方法基于累进网格模型( ( p m ) ，在每一层分解过程中进行 一次“边折叠”操作，便删除一个顶点，并根据“边折叠”操作后的邻接顶点 预测删除顶点的位置，并记录此预测误差作为本层分解中的细节信息，这类算 法的优点是在多分辨率的分解与合成过程中不改变原始网格模型的拓扑连接关 系，对具有复杂拓扑结构的网格模型更具普遍性，缺点是分解层级过多。这类 算法主要有文献【2 8 2 9 。 1 9 9 7 年z o r i n 等人提出了多分辨率网格编纠3 0 】，在他们的算法中，用边折 叠进行简化，所以在编辑一个顶点时，该顶点的一邻域( o n er i n g ，与该顶点构 成条边的所有顶点) 顶点都受到影响。k o b b e r 等人| 3 1 , 3 2 , 3 3 1 解决了这个问题， 第2 章三维网格形变综述 他们没有采用从粗到细的分层，而是根据平滑程度分层，在编辑过程中，用户 选定感兴趣区域和控制点，并确定控制点的编辑尺度，感兴趣区域中其它的顶 点随之进行用户定义的变换。每次用户指定控制点的形变，感兴趣区域内的网 格根据受约束的能量最小化方程进行形变。l e e 提出的方法1 3 4 是，用户选定感 兴趣区域和一系列控制点后，感兴趣区域的形变是将控制点的变换通过多层b 样条插值来完成。2 0 0 6 年s h i 等人针对大曲面或大体积的网格形交，提出了快 速多重网格算法【3 5 】，其基本原理也是基于多分辨率思想的。 图2 - 3 网格模型的多分辨翠表不 f i g u r e2 - 3t h er e p r e s e n t a t i o no f m e s hm o d e l w i t hm u l t i r e s o l u t i o n 该类算法的优点在于可以根据网格模型多分辨率表示提供的分层信息，对 模型的大致轮廓与多尺度细节分别独立地进行编辑，可得到丰富的编辑效果， 但将普通多面体网格模型转化为多分辨率表示的过程本身实现困难、运算较慢， 且编辑操作较为复杂，实时效果不好，使该类算法的通用性受到限制。 2 5基于局部表示的网格形变及其改进算法 一些多分辨率编辑技术是分成两个频率带 3 i , 3 6 ：平滑的基网格和细节网格， 细节网格是在基网格的局部坐标系下进行表示。这个方法可以看作与近期 l i p m a n 等人阳、s o r k i n e 等人3 川和y u 等人【3 卅提出的直接在原始网格上进行 编辑的方法类似。 2 0 0 3 年，a l e x a 4 0 l 简要的讨论了对三维网格进行拉普拉斯变换在自由形状 建模方面的潜能，详细地探讨了在顶点的邻域可能退化( 比如是平面) 的情况 下获得仿射不变坐标比较困难。l i p m a n 等人在文 3 7 d p ，建立一个由离散的拉 北京工业大学工学硕士学位论文 普拉斯坐标及边界条件产生的线性方程组，应用基于平滑曲面估计局部旋转角 度的方法定义拉普拉斯坐标的局部标架来保持局部细节，在最小二乘意义下重 建网格曲面。s o r k i n c 等人【3 8 】在线性重建过程中，对每个顶点计算相应的变换， 把这些变换应用到各自的拉普拉斯坐标，以此重构形变网格。z h o u 等人】也利 用了s o r k i n e 等人的思想，并且在网格内部建立一个格子结构，表示网格内部的 体积，在形变时加入一些体积上的约束，阻止体积上非自然的改变，保留细节。 在网格外部也建立一个格子结构，防止在形变时网格的局部有交叉。该算法能 产生大的形变。y h 等人在文1 3 9 q 。提出了一种基于泊松方程的网格编辑方法， 该方法通过操作网格的梯度场来达到编辑的目的，形变的效果被均匀扩散到网 格曲面上，形变后的曲面通过在最：b - - 乘意义下求解一个带d i r i c h l e t 边界条件 的离散泊松方程a f = - g 来重建。n e a l e n 等人i , t 2 的算法中，通过画两条曲线，一 条作为感兴趣区域的边界，另一条作为目标曲线，利用拉普拉斯算子及约束条 件，建立方程组，在最小二乘意义下进行形变运算并且保留细节。如图2 - 4 所 示。这类方法主要是对人或动物模型的身体或四肢进行形变，而对于一些有细 密纹理的曲面，比如眼睛，形变编辑运算通常很困难的。 图2 q 骆驼头模型 4 4 1 f i g u r e2 - 4t h ec a m e lh e a dm o d e l m 】 这些方法都尽量地保留曲面的某些局部特性，比如网格曲面的离散拉普拉 斯坐标口7 ，3 8 1 或网格坐标函数的梯度【3 9 】。因此，将这类形变编辑方法统称为基于 局部表示网格形变算法。 2 0 0 4 年，s h e f f e ra n dk r a e v o y 提出了一种旋转不变的金字塔坐标( p y r a m i d c o o r d i n a _ t c s ) 用于网格编辑【4 3 1 。对于各网格顶点，金字塔坐标可以看作是其切线 部分信息和法线部分信息的结合，通过顶点与各邻接点的角度值和长度值来直 接表示网格的局部几何信息，由于其长度和角度在刚体变换中保持不变，所以 金字塔坐标在刚体变换过程中能够保持不变性。基于金字塔坐标，他们提出了 一种新的三维网格编辑方法，主要是用于形变( d e f o r m a t i o n ) 、渐变( m o r p h i n g ) 和 融合( b l e n d i n g ) 。该方法能很好的解决形变过程中的旋转变换问题，但是由于重 构过程是非线性的，计算复杂，所以对于大模型的编辑，该方法具有局限性。 第2 章二维网格形变综述 2 0 0 5 年l i p m a n 等人又引入了刚体线性旋转不变坐标( l i n e a r r o t a t i o n i n v a r i a n tc o o r d i n a t e s ) 4 4 j 。该方法采用了间接的表示方法，首先建立个 顶点的坐标系，然后在各顶点坐标系之间建立联系，以此来表示网格局部特性。 基于这种离散坐标表示方式，在最小二乘意义下求解稀疏线性系统获取离散坐 标系数和顶点新坐标，实现重构过程。这种方法由于其具有线性特点，较采用 金字塔坐标的编辑方式更为方便，但是该方法也存在自相交叉的问题，有待于 进一步改进。 图2 - 5 划线网格形变旧 f i g u r e2 - 5s k e t c h i n gm e s hd e f o r m a t i o i l s h 司 2 0 0 5 年k h o 和g a r l a n d 给出的划线方式实现网格形变的编辑方法是令人 心动的【4 5 l 。该方法提供了一个灵活的交互式用户界面。首先由用户在屏幕上划 线，系统通过映射、求相切平面及边界，即可确定其感兴趣的编辑区域，在感 兴趣的区域内，用户描出参考曲线以及相对应的目标曲线，通过参考曲线与目 标曲线之间的一一对应关系，定义包含变换和旋转的重构方程，求解即可实现 网格模型的形变。采用该方法实现网格模型形变的过程如图2 - 5 所示。与n e a l e n 等人的算法一样，这种方法对于形体的形变效果比较好，但对于细节变化，如 眼睛、面部的细微变化，编辑效果并不理想。 2 0 0 6 年黄等人提出一种基于子空间梯度场的网格形变算法 4 6 1 ，这种算法不 仅可以解决线性约束问题，也可以解非线性约束问题。在处理非线性约束问题 时，将网格形变转换为非线性的能量最小化问题，并用迭代方法进行求解。解 这种非线性问题的最大困难是收敛速度慢，并且迭代值非常不稳定，为了解决 这两个问题，他们提出了子空间方法，在原始网格周围构建一个粗糙的控制网 格，采用中值插值的办法将形变能量和约束投影到控制网格顶点上，在控制网 格顶点上解这个能量最小化问题。该方法对于某些非线性约束计算比较快，迭 代值比较稳定。 此外，根据微分思想，z a y e r 等于2 0 0 5 年将谐波场的思想应用于三维网格 的曲面形变1 4 7 1 。2 0 0 6 年f u n e k 等人则提出了基于向量场的形变m 1 。k i m - c h u n g 北京工业大学工学硕士学位论文 提出了对偶拉普拉斯方法用于三维网格模型的整体形变 4 9 1 ，从某种程度上解决 了拉普拉斯形变算法所存在的旋转变换的问题。 2 6 小结 本章中，我们首先给出了网格形变的要求，然后介绍了三维网格形变中的 两种主要算法：自由形变算法和多分辨率算法，主要从其发展历程、基本原理、 算法本身的优缺点等方面来进行阐述。 f f d 方法是一种直观的网格形交算法，该与物体的表示方法无关，而且形 变过程光滑。但由于控制顶点较多，难以逼近任意拓扑的物体形状，所以物体 形变控制不够灵活。当l a t t i c e 形变和物体形变之间的对应关系并非很直观时， 基于f f d 的形变方法就难以奏效。而当模型含有丰富细节并且运动形态较为复 杂时，该方法不能保留其局部几何细节特征，形变能力有限。 针对局部细节保留的问题，多分辨率算法根据网格模型多分辨率表示提供 的分层信息，对模型的大致轮廓与多尺度细节分别进行独立地编辑，可得到丰 富的编辑效果，但过程本身实现困难、运算较慢，且编辑操作较为复杂，实时 效果不好，通用性