（应用数学专业论文）基于对偶网格的变形技术.pdf

浙江大学硕士学位论文 摘要 网格变形是数字几何处理中最基本的问题之一，随着数字几何模型逐渐走入 人们的日常生活，网格变形在实际应用中也变得越来越有用，大型建模软件都集 成了变形这个工具。它的应用包括模型重用和重建，虚拟场景的物体模拟，计算 机动画中的帧序列，甚至三维特效的生成。 鉴于网格变形的应用前景，本文提出了一种新的网格变形的框架，步骤分为： ( 1 ) 输入三角网格( 2 ) 求解对偶网格( 3 ) 对对偶网格变形( 4 ) 从变形后的对 偶网格恢复三角网格得到变形后的结果。 本文回顾了三角网格的对偶网格的定义及其邻域特征。分析了对偶网格与原 三角网格的关系，考虑了如何从变形后的对偶网格恢复到原三角网格得到变形结 果的问题。本文的解决办法是利用细节编码将原三角网格的顶点编码为此顶点对 应的对偶网格面上的顶点的局部金字塔坐标，随后将变形后的对偶网格加上编了 码的细节，就能得到无收缩的三角网格上的变形结果，实现了由对偶网格驱动的 三角网格变形框架。 本文利用三角网格的对偶网格的1 邻域的简单规则结构、基面的共面性、以 及法向计算的稳定性来给出新的算法或者改进原有算法。 第一部分： 改进金字塔坐标变形算法，使得变形结果( 1 ) 迭代更加稳定( 2 ) 不失迭代速 度( 3 ) 保持相同的变形效果。也就是说金字塔坐标算法的稳定性得到了非常大 的改进，迭代速度也没有削弱，变形结果非常相似。 第二部分： 浙江大学硕士学位论文 相对于其它变形算法( 如a r a f ( 保刚性形状变形) ，线性旋转不变内在量 等) ，引进了一种新的表示形状保持的内在量，即伸缩不变内在量。该内在量具 有旋转、平移、伸缩不变性。首先在三角网格上面进行定义，发现矩阵的行列数 难以估计，然后给出对偶网格上伸缩不变内在量的定义，并且提出了基于对偶网 格上保持伸缩不变内在量的变形方法。最后给出了一个基于l a p l a c e 方法的一个 改进。 关键字：对偶，曲率流，伸缩不变内在量，金字塔坐标，l a p l a c e 变形 浙江大学硕士学位论文 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 eb a s i cp r o b l e m si nd i g i t a lg e o m e t r yp r o c e s s i n g w h i l et h e d i g i t a lg e o m e t r ym o d e li sg o i n gi np e o p l e sl i v e s ，d e f o r m a t i o nb e c o m e sm u c hu s e f u lt h a na n yt i m e b e f o r e l a r g e s c a l em o d e l i n gs o f t w a r ei n t e g r a t et h ed e f o r m a t i o na s 廿l e i rn e c e s s a r yt o o l s t h e a p p l i c a t i o no fm e s hd e f o r m a t i o nc o n s i s t so fr e - u s i n gm o d e l s ，r e c o n s t r u c t i o no fm o d e l s ，m a k i n g c o m p u t e ra n i m a t i o nf l a m e s ，a n dm a k i n ge f f e c t si nm o 、，i e s t h i sp a p e rp r o p o s e san e wf r a m e w o r kf o rt r i a n g l em e s hd e f o r m a t i o n t h em a i ns t e p s f o l l o w s ( 1 ) i n p u tat r i a n g l em e s h ( 2 ) c o m p u t et h ed u a lm e s h ( 3 ) d e f o r mt h ed u a lm e s h ( 4 ) g e tt r i a n g l e t h i sp a p e rr e c a l l st h ed e f i n i t i o no ft h ed u a lm e s ho fag i v e nt r i a n g l em e s ha n dt h e1 - r i n g n e i g h b o rc h a r a c t e r i s t i c sa n da n a l y z e st h er e l a t i o n s h i pb e t w e e nd u a la n dp r i m a lt r i a n g l em e s h t h e t r a n s f e rf r o md e f o r m e dd u a lm e s ht ot r i a n g l em e s hi st a k e ni n t oc o n s i d e r a t i o n t o g e t n o n s h r i n k i n gd e f o r m e dt r i a n g l em e s hf r o md e f o r m e dd u a lm e s h t h i sp a p e ru s e sp y r a m i dd e t a i l a l c o d i n gt or e c o r de a c hv e r t e xo ft r i a n g l em e s ha c c o r d i n gt ot h ec o r r e s p o n d i n gd u a lm e s hf a c e s v e r t i c e sa n dd u r i n gs t e p ( 4 ) i nl a s ts e c t i o nu s e st h i se n c o d i n gt or e c o v e rt h et r i a n g l em e s hv e r t i c e s s of a r , t h ew h o l ef o u rs t e p si nl a s ts e c t i o nc a nl e a dt oa l lt r i a n g l em e s hd e f o r m a t i o nf r a m e w o r k b a s e do nd u a lm e s h b yt a k i n ga d v a n t a g eo ft h es i m p l e ，r e g u l a r , c o p l a n a ra n ds t a b i l es t r u c t u r eo ft h ed u a lm e s h ， t h i sp a p e ru s e st h ed u a lm e s hf r a m e w o r kt oi m p r o v es o m ea l g o r i t h mo rp r o p o s en e wa l g o r i t h m t h ef i r s tp a r t ： i m p r o v ep y r a m i dc o o r d i n a t ed e f o r m a t i o nm e t h o da n da c h i e v e st h r e er e s u l t s ：( 1 ) m o r es t a b l e 浙江大学硕上学位论文 i t e r a t i o n ( 2 ) c o s ta l m o s tt h e $ a m ei t e r a t i o nt i m et og e tp l e a s i n gr e s u l t ( 3 ) g e ta l m o s tt h es a m e r e s u l t s s ot h ep y r a m i dc o o r d i n a t e sm e t h o di si m p r o v e di ns t a b i l i t yb u tw i t h o u tl o s ei t e r a t i o nt i m e a n dd e f o r m a t i o ne f f e c t t h es e c o n dp a r t ： r e l a t e dt oo t h e rd e f o r m a t i o na l g o r i t h m ，e g a s - r i g i d - a s - p o s s i b l ew h i c hk e e p sr i g i d i t yo fl o c a l s h a p e , t h i sp a p e rp r o p o s e sn f f v vi n t r i n s i cv a r i a b l e so nm a n g l em e s h e st ok e e ps h a p e s ，8 0c a l l e d s c a l ei n v a r i a n ti n t r i n s i cv a r i a b l e sw h i c ha l ei n v a r i a n tu n d e rt r a n s l a t i o n ，r o t a t i o n ，a n ds c a l i n g f i r s t l yg i v ed e f i n i t i o no nt r i a n g l em e s hf o u n dt h a tt h em a t r i x sr o wh u mh a sn o t h i n gt od o 谢m c o l u m nn u n l ，t h e nt h i sp a p e rp r o p o s e st h e & f r u i t i o no i ld u a lm e s h b a s e do nt h ed u a lm e s h d e f i n i t i o no fs c a l ei n v a r i a n ti n t r i n s i cv a r i a b l e s ，s e v e r a ld e f o r m a t i o nm e t h o d sb a s e do no p t i m i z e o b j e c t i v ef u n c t i o n s 、j l ，i t l lp r e s e r v i n gi n t r i n s i ci n v a r i a n tq u a n t i t i e sa 陀p r o p o s e dw h i l es o m ep l e a s i n g r e s u l t sa a c h i e v e d a n da tl a s tt h i sp a p e rg i v ean e wa l g o r i t h mb a s e do nn a i v el a p l a c e d e f o r m a t i o nm e t h o d k e yw o r d s ：d u a l , c u r v a t u r ef l o w , u ：a l e - i n v a r i a n tc o o r d i n a t e s ，p y r a m i dc o o r d i n a t e s ，l a p l a c e d e f o m a t i o n 浙江 学硕e 学位论立 1 数字几何模型 第一章绪论 数字儿何模型是继声音、图像和视频之后的义类新的数字贼体，随着虚拟现实技术的 进步和影视娱乐行业的发展数字儿何模鼎止逐渐走进人们的日常生活中数字儿何模型已 经渗透到模拟仿真、造型设计、医疗诊断、遗产保护、影视特效霸l 互动娥乐等领域中( 幽 1 1 ) 1 6 k 墨意。圈妇奄蹩鸶麟菇龋睁；- 簟闰 珊黼 图11 数字几何处理的戊崩 1 叼- 从左到右从上到f 依次为模拟仿真、造型设计、医疗 诊断、遗产保护、髟视特效和互动娱乐。 数字儿何模型的表示方法有很多不同的分类方法。根据整体上的角度来分，有实体表示 ( c o a s t m c t l v es o l i dg e o m e t r y , 简称c s g ) 和边界表示( d r yr e p c e s v a t a t i o n 简称 b r c d ) 。前者侧重丁实体空间后者侧重于表面边界。前者是对体素( 比如立方体，球嘲柱， 圆锥等) 定义交、并、差等正则集合运算而得到通常将运算表示成一颗二叉树的形式。 后者通常是由面的井集给出，包括几何信息和拓扑信息两个部分是儿何形体表示中最成熟 的表示方祛。两者的优缺点也非常明显。前者的优点是数据结构比较简单，容易转化为边 界表示，容易修改，缺点是形体的表示受体素的种类和运算类型的限制，局部操纵雌于实现， 另外绘制起来也比较难；后者的优点是几何元素显示给出易于局部操纵，方便在几何元素 上附加各种非几何信息，比如纹理坐标，标量场矢量场等：缺点是数据结构比较复杂，难 新江太学目土学位论立 于维护，另外形体的正则性和有效性根滩保证( 有效性比如有两个顶点重台普情况正4 性 比如三角形二个顶点共线等情况) 。多边形同格是一种典型的边界表示方法。 睬丁上述从整体上米对表示方法进 t 分类外，还有对基本元素( p r i m i t i v e ) 进行分类 比如点云表示、几何幽像表示、隐式表示和体桑表示，如f 酗1 , 2 ； 罐霹霉 哪碚点五 儿倒拄i 像隐式表币 酗l2 数字几何模型表示方法f 1 6 】 由于当前图形绘制流水线毋终都以一系列离散的三角形作为基本儿何幽元闪此三角形 同格已经成为目前致字儿何模型的主流表示方法，本文主要针对上酗中第一种表示方法米处 理网格编辑中一个变形问题。那什么是同格编辑呢? 1 1 网格的犏辑 目前数字几何处理是针对数字几何模型的研究包括模型获墩、几何滤波、几何分析、 几何模型编辑、模型参数化、模型检索、模型重建、数据压缩铘方向f 1 6 几目& 缉，* ，女+ p 嘲1 3 模型编辑类型【1 6 】 岱一声暑 矗， 豳垆氟攀一秒 酝蹦j 。、器 浙江大学硕士学位论文 1 2 编辑类型 其中模型的编辑又包括几何滤波、几何变形、几何差值、几何融合、几何信息重用和几 何重采样等方向【1 6 】( 如图1 3 ) 。 几何滤波：包括信号分析方法、双边滤波技术、基于曲率流的滤波技术、w i a m e r 滤波 技术和基于球面调和函数的滤波技术等。信号分析方法是将三维网格的几何信息转换为频谱 信号，运用离散f o u r i e r 变换或者小波变换，针对特定的信号频率区域进行处理，包括去噪 ( 削弱高频部分) 、增强( 增强高频部分) 、带通带阻等具体滤波类型。难点在于如何定义三 维几何信息的频谱以及具体的频谱分析方法。 几何变形：根据用户的设计意图对输入的原始模型的几何位置信息进行修改，得到新的 模型，往往拓扑信息不变。主要用于计算机动画或三维特效的制作。通过考虑变形结果的质 量，用户交互：【作量，算法时间来衡最算法的好坏。 几何插值：研究在多个模型之间进行插值，从而生成一系列渐变的序列模型，用于计算 机动画的生成。衡量算法好坏的标准是生成序列的特征保持情况以及是否符合物理运动规律 情况。 几何融合：将来自多个不同模型组件融合成为一个新的整体，用于原型数据的快速获取 算法衡量标准是看算法根据融合边界如何自适应调整各个组件的大小和形状以保持融合边 界自然过渡。 几何信息重用：将源网格的几何信息或者变形信息用于目标网格上，常用于数据驱动的 快速建模。算法衡量的标准是如何根据目标模型自适应地调整源模型的几何信息得到自然的 重用效果。 几何重采样：原始模型的采样可能不能满足某种编辑需求，就需要根据具体的应用对原 始模型重新采样。算法衡量标准包括采样是否均匀，是否根据曲率自适应调整采样密度，保 持尖锐特征，以及重采样的误差等。 由于本文主要是针对三角网格的变形技术，下一节简单回顾一下网格变形方法。 2 三角网格变形 3 蛳扛大学碰i - 学位论文 2 1 耐椿褒示符号 令m = ( r ，e ，f ) 为二维流形三角同格其中r ，e f 分别为幽中的顶点，边面 p - = “，咋) ，e = 岛) ，f = “， ”，j ，上= 帆。，叶：，h j ) 表示三宵i 形每个顶点 处的法向为v = ( n ，n 2 ，) f 为顶点叶1 邻域里面的顶点指标浆台，领域顶点为 vj 盘 顶点叶的l - 邻域三角形集台为 z ，) 变形后的悦鹫为矿；p ：，吐， 2 2 交互方式 选择三霸呵格上一个区域作为感兴趣的区域r o i ( r e g i o ao f i n t e r e s t ) 。井在这个区域里 面选择控制点( c o n t r o lh a n d l e s ) ，也可咀选择一些静态点( s ”d o n u ，a n c h o r s ) ，r o i 中除了 这些点之外的点本文称为自由点。如果没有特别指出，以r 部分中n 表示r o i 中所有顶 点数目( 包括控制点和静态点) m 表示所有r o i 中自由点数日。然后对控制点进行拖动来 实现三角罔格的变形( 如酗i4 ) 。 2 3 相关变彤方法综述 2 3 l 自由形式变形 麓_ 潘 凹14 交且方式豳片米白【14 】 从上个世纪八十年代的自由形式变形( f r e e f o r md 郴o r m s e o a ) 变形技术发源于 s = a = t ”m 和p a 时的开创性工作“f r e e - f o r m d e r o g a t i o n o f s o l l d g e o r a e l r i c m o d e l s 现在的 自由形式变肜技术已经非常成熟，一个经典的代表是m a y a 软仆中的w i r e 变形i 具。这兴 方法的主要步骤是：首先用户交互硬定代理横型，并将原始模型嵌入刘代理模趔中( 参效化) 浙江大学硕上学位论文 然后用户操纵代理模型来表达特定的编辑意图，最后根据变形后的代理模型以及原始模型的 参数化信息恢复出变形后的模型。算法简单，几何直观性强等优点，但是代理模型比较难设 置，设置不好影响变形结果质量，另外缺乏几何细节的约束，细节有可能保持不好。另外参 数化的方法中还包括参数化的光滑性，是否可以延拓到代理模型之外等问题等。具体对原始 模型的参数化可以采用m e a nv a l u ec o o r d i n a t e s 。h a r m o n i cc o o r d i n a t e s ，g r e e n c o o r d i n a t e s 5 - 7 ，1 7 ，2 0 等。另外很人一类自由形式变形方法是骨架驱动的变形方法。 2 3 2 多分辨率方法 上个世纪九十年代的多分辨率方法的产生土要是冈为c p u 处理能力承受不了巨型网格 的问题。最开始出现在样条曲面，后来运用到细分曲面和不规则网格。多分辨率方法主要是 根据自分小波变换或者累进简化技术，将高精度模型转化为一个精度由低到搞的网格序列， 各层之间通过编码来维护细节以待重建时重用。多分辨率方法的引入使得用户在低分辨率下 进行网格编辑操纵，从而使得编辑结果可以实时显示，然后通过累进重建算法将各层之间的 几何细节回代，最终获得高分辨率的结果。优点是能处理巨型网格并且保持细节。缺点一是 要预先构造网格的累进表示，二是大变形下重建算法不稳定，三是只适合整体形状的编辑， 对细节编辑仍然要同到高分辨率网格上操纵。更详细的内容请查看【3 ，4 ，1 9 1 等。 2 3 3 曲面局部坐标方法 最近几年里出现的内在几何处理方法【2 ，9 ，1 2 ，1 3 ，1 4 ，1 8 ，2 1 2 3 从考虑保持局部细 节特征的角度把变形问题转化为全局优化问题。这些方法允许用户指定一些操纵句柄( e g 网格顶点) 的位置或者法向，网格的其它部分通过求解线性系统来极小化形状扭曲。因为变 形后形状的目标细节存在一个旋转变换和平移变换，要达到令人满意的结果往往要额外考虑 变换的问题。这是局部坐标方法面临的主要问题。由于本文跟这些文章中的一些文章有比较 大的关系。下面做比较详细的介绍。 微分坐标变形方法【9 】： 图1 51 邻域及拉普拉斯坐标 l a p l a c e 坐标也称为微分坐标。定义每个项点m 处的l a p l a c e 坐标( 简称l c s ) 为 5 浙江大学硕 ：学位论文 ：窆( v ，一k ) ，如图1 5 ，嘞组成了一个矩阵l ，s 1 万：l v ， 其中 艿= ( ，。，：，1 ) r 。的取法至少有两种，一种取法是嘞- - i l f i ，即均匀权，另一 种取法是曲率流权，= c o t q + c o t 孱，其中q ，屈是边( f ，_ ，) 的两只对角，此时方 向与曲率流法向一致。其中矩阵l 的秩为n 1 。如果按照上述方程求解【厂，解不唯一， 需要再加至少一个约束方程。通过加入静态点作为软约束加入到方程中得 n l i i l e ( y ) = l 万一l v l l 2 + f l y ：一_ 0 2 ( 1 1 ) 这种问题通过求解如下法方程得到： 彳r 么v = a r b( 1 2 ) 得到。矩阵的分解在交互区域确定以后的预处理阶段进行处理，交互变形阶段不用再分 解矩阵使得这种方法能提供用户实时的反馈。由于尚朱考虑交互拖动导致l c s 发生的 变换，在大的拖动下变形结果会产生很大的扭曲。这种方法称为普通l a p l a c e 方法。 下面一些方法基于普通l a p l a c e 方法考虑局部变换问题。 对旋转进行考虑【2 2 】，先利用普通l a p l a c e 方法得到一个中间网格，然后利用这个 网格以及初始网格求得每个顶点处的一个旋转，然后根据r d ( v ) = d 似k ) ( 即先 对顶点作用旋转再求l c s 等于先求l c s 再作用旋转。其中的r 表示对网格的全局旋转， d 表示求微分坐标) 并假设网格比较光滑，那么对局部旋转r d ( v ) = d ( r k ) 式也 大致成立，然后将每个顶点处求出的局部旋转变换作用到该顶点处的初始坐标上，将旋 转后的微分坐标作为要保持的目标微分坐标，重新求解线性系统。这个方法的缺点是要 求被操作的网格比较光滑，对法向的要求比较严格，而且用中间网格作为对旋转的估计 不可靠。 文献【1 3 】提出了一种新的隐式计算变换的方法，重新组织了最小二乘方程，使得变 形操作后l c s 在旋转和伸缩的情况下不再敏感，同时没有失去实时反馈的计算速度，只 需要求解一个线性系统。主要思想是基于未知的顶点位置v ，对每个顶点计算一个恰当 的交换互，使得每个变换表示为v 的函数霉( y ) ，这样新的能量函数是 6 浙江大学硕士学位论文 其中 e ( v ) = i i 巧( 矿) - i , 1 1 2 + 一圳2 ( 1 3 ) f 譬if ；棚+ l y = ( v ：，也，e ) r = ( 一，一t ) 。 旧l ，= i 而互( 矿) 是根据一个线性近似来表达的：每个局部邻域之间的变换用 憾t刳y0 001 互= b i 乡ti lj 浙江大学硕t 学位论文 有发生变化，跟梯度域方法一样会发生平移导致的坍塌。 对偶l a p l a c e 方法【1 4 】 使用迭代方法来解决平移导致的坍塌问题，并用对偶网格来处理法向的估 计他们认为l c s 中的权很熏要，他们从多分辨率方法中分析认为，那些 方法让细节沿着法向进行编码或者让细节具有最小的切向分量，而l c s 表示的 是局部几何数据，正是细节，所以必须与局部的法向保持一致，这就是说权的 取法必须使l c s 跟法向是一致的，于是使用前面提到的曲率流权。迭代求解的 主要思想是： s t e p 0 ：输入网格项点y o ，o s t e p l ：根据，求解法方程彳r av = a r b 更新顶点位置得到v 1 s t e p 2 ：根据矿件1 计算f + 1 ，然后更新髟+ 爿l pi i 川+ 1 s t e p 3 ：如果还没收敛，重复s t e p l 至s t e p 3 。 此时的问题是：当网格采样很差或者儿何比较复杂的时候曲率流法向量容易翻转， 造成迭代发散；即使取了曲率流权，由于1 邻域顶点并没有共面，l c s 其实仍然 存在切向分量；另外，即使法向估计使用面平均法向与曲率流法向的内积去判断法 向有无翻转，法向的估计仍然不可靠【1 4 】。通过使用对偶网格作为求解域，这些问 题得到了很好的解决。具体对对偶网格的定义以及基于对偶网格的变形改进在下一 章中给出。 2 3 4a r a p 方法 所谓a r a p 就是a s r i g i d - a sp o s s i b l e 。这类方法的出发点是保持局部刚性。举个例子， 两个形状之间的弹性能量 e ( s ，s ) = j 恕i i 一j 眩+ 屯i i 口一口i i ；d u d v ， 其中，口是第一基本形式和第二基本形式。对曲面来说形状是由第一、二基本形式唯一决 定( 最多相差一个刚体变换) ，当这个能量极小化的时候( 往往达不到o ) ，也就是曲面s ，s 。的 第一基本形式和第二基本形式尽可能接近，认为基本上两个形状在每个顶点处具有刚体变换 8 浙江大学硕上学位论文 不变性。文献【1 5 】中的方法如下。每个顶点及其1 邻域定义为c e l l 。假定在每个c e l l 处存在 一个局部旋转墨，使得 q t 。，= r ( y f v i ) ， 每个c e l l 处的能量函数定义为 e ( g ，c ) ：兰l i 以一t 。，一r ( v k 。，) i | ：。 在c ：，c ：已知的情况下，可以通过求解 a r g 巧n 筹i l t 一叱一置( m 一) 1 1 2 求出弓。具体| 咐的是s v d 方法。全局能量函数为 e ( v ) ：窆w e ( g ，c ；) ：窆w 窆j lt t ，一r ( m m ，) l i z ( 1 4 ) 令偏导数等于0 ，化简为 竖j = 1 ( v ；一t ，) = 窆j = l 堕2 r 、 骨1 + r 从m 一) 。 左边刚好是普通拉普拉斯变形中方程的左边部分，右边需要利用足来计算。在墨已知的情 况下，就可以求解这个大型稀疏矩阵。算法步骤：先计算以及对稀疏矩阵进行分解。对 一个初始的圪，先求的墨，然后通过求解前面那个方程，求得k 。然后再令巧卜k ，继续 迭代，直到收敛。其中初始的圪由普通的拉普拉斯变形方法得到。该方法的优点是比较稳 定，简单，跟对偶拉普拉斯方法差不多，能处理平移问题，而且每次迭代都极小化一个具体 的能量函数。 3 本文工作 第一章绪论 这一章从数字几何模型开始介绍，引出与变形密切相关的编辑问题，再由编辑问题引出 变形问题。本文针对的是三角网格的变形。因为后续章节需要，本文在这里提出了三角网格 9 浙江大学硕士学位论文 的符号表示，以及网格变形的交互方式与符号。最后介绍了变形相关文献。 第二章基于对偶网格的变形技术 提出了在三角网格对偶网格上进行处理的方法，虽然三角网格的对偶网格并不是本文中 首次提出【1 4 】，但是本文第一次比较详细地将它独立作为一个工具来考虑，提出了基于对偶 网格的变形技术，指从原来的直接从三角网格变形到三角网格的变形步骤转变为( 1 ) 从三 角网格到对偶网格( 2 ) 对偶网格变形( 3 ) 再由对偶网格变回到三角网格的三步过程。中间 那一步对偶网格变形是比较笼统的步骤，可以采用以前提出的各种变形算法，也可以自己想 算法( 本文第三章) 米操纵对偶网格。这一章本文用对偶网格对金字塔坐标变形方法【l 】进 行了改进。 具体章节分布如下：第一节从金字塔坐标开始讲起。首先同顾金字塔坐标变形算法，分 析它的不稳定性，讨论了它的问题，讨论了法向计算对稳定性的影响。第二节引入三角网格 的对偶网格，并给出了一个基于对偶网格的三角网格变形框架，并用此框架对金字塔坐标进 行了改进。稳定性得到显著提高，又不失迭代效率，变形效果也不错。说明基于对偶网格的 方法完全是实用的方法。 第三章基于对偶网格伸缩不变内在量的变形技术 遵循前一章提出的基于对偶网格的变形技术，我们试图在对偶网格上尝试新的算法。基 于文献【1 0 】，本文从推广2 维多边g e 上f 拘内在伸缩不变内在量到三角网格的目的结合基于对 偶网格变形技术框架，提出每个对偶网格项点处伸缩不变内在量( 简记为s i i v ) 的定义。 之前也有考虑过直接在三角网格每个三角面上定义s i i v ，发现得到的线性系统是9 t 3 n 。 行列数没有必然联系。在对偶网格上这个问题得到解决，并且提出了单转角s i i v 优化目标 函数和三转角s i i v 优化目标函数，实验发现三转角s i i v 优化目标函数求解不会发散，本文 给出了几个求解例子。单转角s i i v 优化目标函数求解发散。 具体章节安排如下：第一节，介绍2 d 多边形的伸缩不变内在量和3 d 伸缩不变内在量。 第二节介绍基于伸缩不变内在量的变形方法。2 1 介绍三转角s i i v 优化目标函数。2 2 介绍 单转角s 1 1 v 优化目标函数。2 3 变形框架。2 4 实验结果与分析。第三节介绍基于l a p l a c e 变形方法的改进。 第四章，总结与展望。 l o 浙江大学硕士学位论文 第二章基于对偶网格的变形技术 本章介绍基于对偶网格的变形技术。本文发现在实现金字塔坐标的过程中主要包括以下 几个部分，第l 节主要介绍金字塔坐标方法，本文对网格上的细节进行编码得到金字塔坐标， 并利用这种刚体不变坐标米指导重建算法。第2 节主要介绍三角网格的对偶网格以及从对偶 网格反求原网格的方法。第2 节主要运j h ；j 对偶网格来进行金字塔坐标方法的改进。第3 节结 果比较与分析。第4 节h j 对偶网格进行变形存在的误差分析。 l 金字塔坐标 l 1 金字塔坐标回顾 文献【1 】中对每个项点的l - 邻域进行编码，分解成切向和法向两个部分。如图2 1 中( a ) 是三角网格某个顶点处的1 邻域，将整个1 邻域投影到该项点处的某个切平面上得到一系 列投影点( ( a ) 中黑色多边形内部的点为顶点的投影，多边形上的顶点为1 邻域点的投影，得 到了投影边，组成了切向部分( 2 1 中( b ) ) 。法向部分是由项点的投影点到顶点的向量， 如图2 1 ( c ) 。 定义2 1 ：定义切向部分中的投影边的长度 ) ，投影边之间的夹角 q ) ，以及法向部 分与原来的1 邻域边的夹角饵) 组成的三元组 ) ， j | ：) ， 层) ) 为金字塔坐标。 如果把网格的顶点位置理解为是一个全局的量，那么金字塔坐标就是网格的一种内在几 何量表示，或者说是一种局部形状表示方法。这种表示方法在刚体变换下保持不变，而在各 向异性伸缩变换以及剪切变换下并不保持。 局部形状表示方法的主要思想是：当物体发生其局部形状只经历旋转和平移的变形时， 变形后它的内在几何量仍然保持不变，因此根据局部内在量求全局位置的算法，可以将全局 坐标求出来。如图2 1 ，从( a ) 到( b ) 及( c ) 是从全局坐标到局部形状表示的分解过程， 而从( d ) 到( e ) 的过程是从局部坐标到全局坐标的重建过程，为了将每个顶点表示成有关 内在几何量 呸) ， ) ， 屈) ) 的表达式，需要依赖于每个顶点处周围的的l - 邻域点( 图2 i d ) 。 浙江人学硕士学位论文 p l ， 入 矗。，+ l ( a )( b )( c ) 图2 1 金子塔坐标图示。( a ) 表示原网格的某顶点处的1 邻域 ( 黄线部分) 。黑线部分是切向分量。蓝线表示法向分量。( b ) 是切向分量图示。( c ) 是法向分量的说明。( d ) 和( e ) 说明 的是从局部坐标到全局坐标的重建过程。 算法2 1 ( 从全局坐标到内在的金字塔坐标计算) 对每个顶点，利用其1 邻域顶点，根据前面定义2 1 中所叙述的那些几何量可以按照如 下步骤来计算金字塔坐标 呸) ， ， 屈) ) ： s t e p i ：计算法向刀= ( 以，嘭，他) 和投影面尸= n x x + n y y + n ：z + d = o ，其中 d = 一y v 力。 一 s t e p 2 ：计算投影点 t ) 和( 图2 1 a 黑色多边形以及投影边) 。 s t e p 3 ：计算切向元素2 ：= l lv 一一0 ，呸= 么( t 1 v ，t ) 。 具体实现的时候可以不保存q 而直接计算均值坐标咩= 塑堕堡三堕产【6 】， 并记录下来( 图2 1 b ) 。 s t e p 4 ：计算法向元素层= 么( 啊，q ) ，q = 1 ，一，具体实现的时候可以存储c o t 层( 图 1 2 浙江大学硕士学位论文 2 1 c ) 。 得到三元组 ) ， w ) ， c o t 屈) ) 本文也称为金字塔坐标，下文中如果没有特别指出的 话，金字塔坐标指此处的定义。这个三元组在刚体变换以及等距伸缩( i s o m e t r i cs c a l i n g ) 下保持不变。 正如前面所说的，当这些局部的内在量已经的情况下就可以根据1 邻域点的位置来对 该邻域顶点处的重建( 图2 1 d ，图2 1 e ) 。下面给出重建算法。 先米同顾下绪论中对交互方式的叙述，用户选择操作的区域r o i ，r o i 中顶点的分类包 括控制点，静态点和自由点。静态点一般是指区域边界上的顶点，用来指出边界，控制点指 交互控制了顶点位置的点，自由点就是位置未知的顶点。算法只对控制点和自由点进行重建。 算法2 2 ( 从局部坐标到全局坐标的重建算法) 对每个顶点m ，根据它的1 邻域来重新计算它的位置讲： s t e p l ：计算当前法向吩和投影面尸，投影 _ ，) 卿到尸上得到p u ) 赌。 w ，t ， s 眩设置t 2 1 i 。 s t e p 3 ：计算法向部分高度，囊，刊i 以。，一以i ic o t 屈，+ ( m 。，一谚，) 吩，如果顶点v f 是 自由顶点，那么令e = v ；+ 吩俪17 h u 。其中的e 就是新的顶点位置；如果k 是控制 顶点，那么计算周围1 - 邻域的点的新位置呓- ，。t ，( 州tw 南莩鸟) ) 。 给出了算法2 1 以后就可以来给出变形的算法了。因为变形算法主要的问题可能是变形 后的形状的金字塔坐标并不知道，如果一定认为金字塔坐标是完全一样的话，变形前后是不 能发生各向异性伸缩的，而这是不可能的。来看【l 】中给t t l 的算法。 算法2 3 ( 金字塔坐标变形算法) 结合算法2 1 ，算法2 2 ， s t e p l ：运用算法2 1 计算输入网格的金字塔坐标( 聪 ，( 咩) ， ， c o t 眵u ) 。即对偶网格上的金字塔坐标。 算法2 7 ( 重建) 对非控制点硎用公式访= ；- 1 吩壹。l l - 一舶t 阶其中葫= 壹j - i 赢 对控制点，硅，= 动，+ 幽弘其中妇驴= 访一( 喜吼，访，+ ；1 缶3 怕。，一v 一, i l c o t 矽u ) 。 算法2 8 ( 变形算法) s t e p l ：运用算法2