（计算机软件与理论专业论文）网格模型的微分方程编辑算法研究.pdf

摘要 随着三维扫描技术的快速进步，几何模型的数据复杂度迅速提高， 几何模型编辑处理技术也有了新的发展，特别是近几年新发展的三维 网格微分编辑方法。微分网格编辑方法将三维几何模型视为定义在三 维域网格上的标量场。从而通过操纵该网格的微分属性来对三维几何 模型进行编辑。这种编辑方式在编辑过程中有效的保持了几何细节 本论文首先引入了微分网格编辑方法相关的理论知识，然后对近 几年来新发展的一系列微分网格编辑方法进行了理论分析，对其性能 进行了比较，总结出了各种方法的优缺点，适用范围。接下来的章节 介绍了三维模型的光顺方法，分析了近年来的三维网格光顺方法，指 出其各自的优缺点，并在此基础上提出了一种新的基于梯度场的全局 泊松网格光顺法，试验证明该方法具有非迭代性，适应性较好，能取 得全局最优解且能够较好地保持细节。接下来，分析近年来微分网格 编辑算法的应用，特别是基于层的网格编辑系统，通过理论和实验分 析不足之处，改进后的系统更为实用。 最后简列出本文的主要贡献： 对当前最新的三维网格微分编辑算法做了详尽的性能分析和比较 提出了一种新的基于泊松方程的全局网格光顺算法 实现并改进了基于层的三维网格编辑系统。 主题词：数字几何处理，泊松方程，梯度场操纵，网格变形，网格光顺 a b s t r a c t w i t ht h ef a s ta d v a n c e m e n to f3 d s c a n n i n gt e c h n i q u e s ，t h ei n f o r m a t i o n c o m p l e x i t yo fg e o m e t r i cm o d e l sg r o w sq u i c k l yt o o t e c h n i q u e so f g e o m e t r i cp r o c e s s i n gt oh a n d l es u c hs i t u a t i o n sh a v es e e nn e wp r o g r e s s e s a c c o r d i n g l y ，f o re x a m p l e ，3 dd i f f e r e n t i a ld o m a i ne d i t i n gm e t h o d i t r e g a r d s3 dg e o m e t r ym o d a l sa ss c a l a rf i e l d sd e f i n e do nt h e3 dd o m a i n m e s h e s u n l i k ei t st r a d i t i o n a lc o u n t e r p a r t s ，t h i sm e t h o dp r o c e s s e s g e o m e t r i cm o d e l sv i ai m p l i c i t l ym a n i p u l a t i n gd i f f e r e n t i a lp r o p e r t i e so f m e s h e s i nt h i sw a y ，g e o m e t r i cd e t a i l sc a nb eb e t t e rp r e s e r v e d ii n t r o d u c et h et h e o r e t i c a lf o u n d a t i o no fd i f f e r e n t i a ld o m a i n m e t h o d si nt h eb e g i n n i n go ft h i sd i s s e r t a t i o n 。t h e ni a n a l y z eas e r i e so f p a p e r so nd i f f e r e n t i a ld o m a i nm e t h o d so fr e c e n ty e a r s ic o m p a r et h e i r e f f i c i e n c y ，r o b u s t n e s s ，a n da p p l i c a t i o n a r e at of i n dt h e i r r e s p e c t i v e a d v a n t a g e sa n dd i s a d v a n t a g e s i nt h ef o l l o w i n gc h a p t e r , ii n t r o d u c et h e m e t h o d so f3 dm e s hs m o o t h i n gp r o p o s e di nr e c e n ty e a r s b a s eo nt h o s e ，i d e v e l o pan e wm e t h o dw h i c hc a l l e dt h eg l o b a lm e s hs m o o t h i n gm e t h o d b a s e do np o i s s o ne q u a t i o no ng r a d i e n tf i e l d s t h ee x p e r i m e n t a t i o nr e s u l t s h o w st h a tm ym e t h o di ss i m p l e ，n o n - i t c r a t i v e ，f a s t ，f e a t u r e s - - p r e s e r v i n g ， a d a p t i v e ，a n da c h i e v e sg l o b a lo p t i m i z e ds o l u t i o n s t h e nt h ed i s s e r t a t i o n a n a l y z e sa p p l i c a t i o n so fd i f f e r e n t i a lm e s he d i t i n ga l g o r i t h m , e s p e c i a l l yt h e l a y e rb a s e d3 d m e s he d i t i n gs y s t e mt h r o u g ht h e o r ya n de x p e r i m e n t s t h e i m p r o v e ds y s t e mip r o p o s e si sm o r ep r a c t i c a l 。 ， f i n a l l y ，i l i s tt h em a j o rc o n t r i b u t i o n so fm yd i s s e r t a t i o nh e r e ： i c o m p a r et h e n e w e s t3 dm e s hd i f f e r e n t i a ld o m a i ne d i t i n g a l g o r i t h m s ip r o p o s ean e wm e t h o dc a l l e dt h eg l o b a lm e s hs m o o t h i n gm e t h o d i i i b a s e do np o i s s o ne q u a t i o no ng r a d i e n tf i e l d s ii m p l e m e n ta n di m p r o v et h el a y e rb a s e d3 dm e s he d i t i n gs y s t e m k e y w o r d s ：d i g i t a lg e o m e t r yp r o c e s s i n g ，p o i s s o ne q u a t i o n ，g r a d i e n t f i e l d m a n i p u l a t i o n ，m e s hd e f o r m a t i o n ，m e s hs m o o t h i n g i v 湖南师范大学学位论文原创性声明 本人郑重声赛：所星交酶学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注螺导| 用酶肉客外，本论 文不合任何其他个人或集体已经发表或撰写过的作器成果。对本文的 研究做出重要贡献的个人和集体，均巳在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 、， 一 学位论文作者签名：亏踟氆 沙厶8 年争月2 心甚 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保螫，使黑学位论文的规定， 圈意学校保留并向圆家有关部门或机构送交论文鲍复印件乖电子版， 允许论文被查阅和借阗。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文 本学位论文属于 l 、保密口，在年解密藉适用本授权书 2 ，不保密翻。 请在以上穗痘方框蠹打“， 作者签名： 导师签名： 莓熘 l 岔狮- 鹾期：苔年参月疑 日期：细p 年j ”月。日 朗络模鼙的微分编辑算法研究 1 。1 三维数据的获取 第一章绪论 网格模型是描述数字几何模型的一种数据结构。数字几何模型是 继声音、图像和视频之后出现的一种新的数字媒体格式。从计算机图 形学的角度来看，数字几何模型即是数字化的物理实体空间位置描 述。数字几何模型的应用很广，如医疗领域的c t 断层扫描、核磁共 振重建的数据；各种三维扫描仪获取的三维物体数据；还包括三维艺 术家创造的三维模型。 物体的三维数据包括表面点的三维几何坐标、物体的几何形状、 表面纹理、颜色等信息。 三维数据的获取可以通过以下几种方式：直接设计和测量、相机 拍照、机械探针和物体的物理接触以及各种扫描仪器。 我们定义采集样本的信息并且将其组织成为一种表达与样本一 致的结构的过程为三维数据的获取。采集样本三维信息的方法大致有 以下几种： 直接设计或测量：多用于早期建筑物三维模型的建立，用工程作 图的方式得到模型的三维视图。 图像方法：只逶过照片建立三维模型，焉拍照的方式同时获得几 何和纹理的信息，以此为基础重建样本的3 d 模型。 机械探针( m e c h a n i c a lp r o b e s ；：通过机械探针和样本的物理 接触采集表面数据。要求样本有一定硬度e 体数据( v o l u m e t r i cd a t a ) 恢复：使用样本的断层图像恢复出其 三维形状。多用于医药部门，可使用的体数据包括x 光图片、c t 图 片和m r l 图片等。 域扫描( r a n g es c a n n i n g ) ：通过估算从测量仪器到样本表面点 硕士学位论文 的距离来确定点在空间中的位置。包括光学三角测量，干涉测量等方 法。 三维激光扫描仪：随着三维激光仪器技术的发展和相关软件支持 的完善，三维激光扫描已经成为一种很重要的三维数据获取技术，甚 至引起了三维建模和绘制技术的革新。在本文中主要研究从三维激光 扫描仪获取的数据。下面，先简略介绍域扫描的过程。 第一步，定标。扫描过程中系统的坐标是由仪器的硬件和周围的 环境共同决定的，所以事先要确定一个统一的坐标系。定标的工作对 得到精确的三维数据是至关重要的。 第二步，扫描。物体表面在一个视点被采样，得到一张密集的域 图像。要进行多次的扫描才可以得到覆盖整个物体的采样图像。 第三步，配准。扫描所得的采样图像都处在各自的局部坐标系中， 它们必须被校准到同一个整体坐标系中。 在具体获取数据的过程中，配准是要借助定标中确定的坐标系信 息实现的。扫描小物体时可以固定扫描仪，记录物体放置台的转动角 度，从而得到各个局部坐标系间的关系。而在扫描大场景需要变换视 点的时候，可以通过在场景中的固定位置摆放特殊标识物来标记各个 局部坐标系 1 2 数字几何模型的表示方法 数字几何模型的表示方法很多，分类方法也很多【1 】。总的说来几 何数据可分为实体表示和边界表示。实体表示法通过对体素定义运算 而得到新的形体的表示方法，体素可以是正方体、圆锥等，从而由各 种基本的逻辑正则运算组成较复杂的物体。由于体素一般较为简单且 操纵方式有限，对于局部较复杂的操纵往往不易实现。边界表示法表 示的是实体的边界，这种方法应用较广较成熟。边界表示法包含两部 分信息几何信息和拓扑信息，几何信息主要表示顶点的几何位置，拓 网络模型的微分编辑算法研究 扑信息表示顶点之间的连接关系。 网格是三维几何模型的常用表示方式。任一网格m 可以表示为一 个二元组m = = ( p ，足) ，其中p 是k 个元素的三维欧氏空间点集 p = 只r , i i i ，集合中的每一点都对应着网格模型中的一顶点； k 是抽象单纯复型，描述网格邻接关系。 三角网格的数学描述： 为了给出三角网格的定义，首先了解单纯复形的概念，参考 d z o r i n 关于单纯复形的概念【2 】给出如下单纯复形的 设集合矿为 o ，i ，2 ，行一1 ) ，其中n 为顶点数，记缸歹) ：v i ，_ ，v 为vo v ，v 为v o v v ，则单纯复形是满足条件( 1 ) - ( 6 ) 的三元组k = 【v ，e ，f ) ，这里v 中的元素称为顶点；e ( e c 缸j f ) a v v ) 中的元素称 为边；f ( f c y p y o y ) 中的元素称为三角面。 【1 ) f 中每个面的所有边属于e ； ( 2 ) e 中每条边一定属于某个面； ( 3 ) v 中每个点一定属于某条边； ( 4 ) 一条边最多属于两个面； ( 5 ) 对于以i v 为端点的任意两条边巳和吃，一定存在一个以i 为顶点的多边形面序列石，五，五，使得q 和乞分别为多 边形面石和正的边，且石，石+ l ， ，= l ，k l 共有一条边； 【6 ) 两个面最多共有一条边。 多边形网格是一种边界表示模型，它将物体的表面表示成为一系 列面片的并集。另外由于图形显示设备的显示需求，无论采用三角形 网格还是多边形网格，最终显卡都会把三角形作为绘制的基本单元。 所以三角形网格已经成为数字几何模型的主流表示方法。本文所提网 格一般是指三角形网格。 对于离散网格模型，三角网格是一种较为常用的模型表示形式。 它是由三维空间中的三角形通过边和顶点连接而成的分片线性曲面， 3 硕士学位论文 定义相对比较简单，对于具有复杂拓扑结构的模型具有描述能力强、 边界适应性好的优点。用三角网格来表示模型的各曲面，不仅可以获 得较好的视觉效果，而且还可以通过控制模型中三角片的数量来得到 不同需求的三维网格模型，其在数控加工编程和快速原型制造等方面 有着重要的作用。三角网格模型在地质勘测、地理信息系统等领域也 有着广泛的应用。三维地质模型可以使不熟悉地质结构的人对地质空 间关系有一个十分直观的认识，提高对复杂地质条件的理解和判别。 利用三角网格模型重建技术绘制出详细的三维地形图，再对其进行处 理得到不同比例下的地形图。在地理信息系统领域，利用现代的卫星 遥感测量技术，对大地遥测数据进行特征识别和建模，可以建立三维数 字化真实感地图：利用声纳测量设备，可以获得海底及港口的地下形貌 数据，从而有利于资源利用、海上交通、资源普查等工作的开展。 1 3 网格编辑的基本问题 网格模型变形：网格模型变形主要研究如何按照用户的设计意图 将原始模型形变，常用于计算机三维动画或者电影中的三维特效 1 2 1 1 3 1 1 4 1 。变形问题的难点在于怎样讲用户的变形意图准确的实现。对 变形算法进行评估主要在于两点，一是变形结果的质量，二是用户完 成变形操纵需要的操作量。s e d e b e r g 最早提出自由变形技术，其核 心思想是不直接对物体进行变形操作，而是作用于物体所嵌入的空间 格子，然后传播到物体本身。s o r k i n e 等人提出了在曲面网格变形中， 使用一种顶点与其相邻点的关系的拉普拉斯坐标方法，取得了较好的 变形效果。 网格模型插值：主要研究从源网格模型如何自然的符合物理规律 的随时间渐变的生成中间模型序列从而变成目标模型【5 】【6 1 。问题关键 在于怎样建立从源网格模型建立到目标网格模型的映射以及怎样是 中间模型序列变形自然。在计算机动画中，通过造型和三维激光扫描 4 辩络模型的微分编辑算法研究 得到的物体模型已有很多，利用网格模型插值的思想，从现有模型中插 值出新的模型将大大提高动画师创作新模型的效率，激发动砸师的灵 感”而在由两个或多个三维模型插值成一个新模型的过程中，需要利用 网格插值光滑地把它们连接起来。网格插值技术在影视特技、三维广 告制作、娱乐游戏、虚拟现实等行业中具有广泛的应用前景。 网格模型光顺：由于从现实中物体采样的三维网格模型常常因为 误差而具有噪声，需要进行去噪尊该问题的难点在于如何消除噪声且 尽量的保持细节。相关的技术较多，如基于双边滤波的光顺技术 7 1 1 8 1 ， 基于球面调和函数的滤波技术 9 1 。t a u b i n 将拉普拉斯算子扩展到三 角形网格模型，并在此基础上为网格曲面设计了各种多项式线性滤波 器，较好地解决了网格曲面的光顺问题。目前普遍使用的曲面光顺方 法有拉普拉斯光顺法。其在信号和图像处理方面已经有着成熟应用。 网格曲面重建：是指从曲面上的部分采样信息来恢复原始曲面的 几何模型。我们知道，描述物体表面形状信息的数学表达式称之为物 体的几何模型，也称为曲面的数学模型，它是对物体进行分析、计算 和绘制的根据，是研究曲面性质的重要工具。网格曲面重建根据重建 曲匿的表现形式不同可以分为五种：分片线性重建方法、隐式曲面重 建方法、变形曲面垂建方法、参数曲面方法和细分曲面重建方法尊网 格曲砸重建的技术性问题很多，速度快、效果好这样完美的解决方案 几乎是不存在的，如何尽量保持网格曲面特征的情况下加快重建速度 仍是研究的重点。 1 4 本文的主要内容 本文在第二章详细分析了网格模型的微分表示方法理论知识。在 此基础上给出了当今流行的网格微分变形操纵各种技术，并且在其上 做了性能分析对比。另外还分析了网格模型光顺技术，并引入微分表 示的方法给出了一种新的网格光顺方法，并于以前的算法作了对比。 5 硕士学位论文 第三章分析了整个网格模型微分表示方法的线性化求解方法和一些 改进思路。第四章给出了网格微分编辑方法的应用一几何层编辑系统， 并介绍实现了的基于层的网格编辑系统。最后，我们在第五章总结全 文，并展望了未来的研究工作。 6 网络模型的微分编辑算法研究 第二章微分网格编辑方法 2 1微分网格变形 2 1 1 相关工作 物体变形是计算机图形学中一个常用的操作，根据用户的要求， 将原始模型进行变形，以反映用户的设计要求。如动画设计中，将原 始模型变形以设计动作，给人物加上多变的表情等。 自由变形技术是一种较老的技术，该方法通过用户操作原模型简 化的代理模型来驱动变形复杂的模型。自由变形技术可以分为三类根 据代理模型的类型，分别是基于网格的变形技术【1 2 1 【1 3 】【1 4 1 ，基于控制 曲线的变形技术【15 】【1 6 】【1 t j 1 8 1 以及基于控制点的变形技术【1 9 】。 自由变形技术的特点是用户可以任意的操纵代理几何模型来对 原始模型变形，变形结果可以任意扭曲，不受物理条件约束。采用自 由变形技术进行变形有三步，首先根据原始模型和变形意图确定一个 简化的代理模型，例如可以采用一条直线代理一个圆柱体。代理模型 选定后，可以采用各种合适的算法把原始模型顶点参数化到代理模型 上。在模型编辑时，用户操纵的是代理模型，然后系统根据变形后的 代理模型驱动原始模型变形。自由变形技术在商业软件中已经较成 熟，应用较广。自由变形技术的特点是操纵模型较简单易操纵，实现 方法较简单。但是原始模型的变换是由代理模型的变换间接完成的容 易导致问题：首先由于代理模型通常较原始模型大大简化，变形结果 往往不能有效反应原始模型上。另外由于代理模型细节点缺失，编辑 后的原始模型往往细节丢失。物体的变形也可以采用多分辨技术，通 过网格化简技术【2 0 】，可以得到一系列原始模型各种分辨率的模型。用 户可以通过对低分辨率的网格模型编辑，再还原到高分辨率的原始模 型上，可以得到满意的编辑结果。采用多分辨的技术可以处理原始模 型过于巨大而难以编辑的问题。 7 硕士学位论文 现有的网格编辑算法通常可转化为微分方程离散化求解问题，以 及各种能量最小化模型求解，如拉普拉斯网格优化，泊松网格优化，以 及各种梯度域方法，通过固定部分顶点的位置，求解线性或非线性方 程来重新调整整个网格的顶点位置信息。最小二乘法必不可少，通过 求解稀疏矩阵来达到各种限制在整体网格上的均匀分布，从而生成较 为合适的形变网格。此外，许多网格参数化方法被用于网格编辑中。 2 1 2 网格相关基本定义 网格( m e s h ) 定义2 1 1 ：如果单纯复形的一条边只属于一个面，称这条边 为边界边；如果一个顶点属于边界边则称此顶点为边界顶点；至少包 含一个边界顶点的面称为边界面；非边界的顶点、边和面称为内部边， 内部顶点和内部面。 定义2 1 2 ：设单纯复形k = ( 矿，e ，f ) 。对于顶点i v ，如果存 在矿，使得e = ( f ，) e ，称e 为顶点i 的邻边，称，为顶点i 的 相邻顶点，称j f 和i 为e 的端点。 三角网格是单纯复形的几何实现，它定义如下： 定义2 1 3 ：( k ，) 称为三角网格，其中k 为单纯复形，： y 一足是顶点到三维空间的单射函数。 退化网格：若网格中出现重合顶点，或者重合边的情况时，会导 致计算出现退化，此时网格称为退化网格。 若网格m 中任意两个顶点k 和之间，均存在一条有网格上的边 组成的路径只连通，则我们称m 为连通网格，否则称m 为非连通网 格。 在网格模型中，每一面片的顶点顺序称之为朝向，网格只有两种 朝向，分别是顺时针朝向和逆时针朝向。如果我们可以通过重新排列 顶点顺序使得网格肘中所有的面片朝向都是相同的，那么称m 是可 8 网络模型的微分编辑算法研究 定向的，否则称之为不可定向的。 网格上的场 网格上的标量场：我们考察域网格m ，若存在标量函数厂满足在 域网格m 上任一顶点杉处取值f c e ) = z ，且在m 上任意其它点v 处取值 为厂( y ) = ，z ，( v ) ，其中g ( ) 是分段线性基函数，在顶点k 处取值1 ， 在其他顶点( j f f ) 处取值0 。我们称函数为定义在域网格m 上的标 量场。显然，域网格m 的顶点坐标的三个分量可视为定义在其自身之 上的特殊标量场。 网格上的矢量场：我们考察域网格m ，若存在矢量函数形满足在 域网格m 上任一三角面片互处取值为常数形，我们称形为定义在域网 格m 上的矢量场。 矢量场分解：h e l m h o l t z h o d g e 矢量场分解定理【l l 】深刻刻画了矢量 场的内在性质，该定理被认为是上个世纪最重要的数学发现之一。这 个定理描述的是位于任意区域q 的光滑矢量场w 可以分解为三个组成 部分： w = v 矽+ v v + h ( 2 1 ) 其中驴是一个满足v ( v ) = o 的标量势场，v 是一个满足v ( v ) = o 的 矢量势场，h 是个一个满足v h = 0 和v x h = 0 的矢量场。，1 ，和h 这 三个分量又分别称为无旋分量，无散分量和调和分量。 离散微分算子 算子是刻画曲面几何特征的强有力工具，本节我们考察定义在域网 格m 上的离散微分算子，具体包括梯度算子，散度算子和拉普拉斯算 9 硕士学位论文 子。 梯度算子：离散梯度算子定义依赖于域网格上的分段线性基函数 的梯度v 唬( v ) ，在此基础上，定义域网格m 上的标量场厂在任意一点 ve m 处的梯度为： w ( d = 乃v 略 ) ( 2 - 2 ) 在域网格上的任意三角片w = 矿( 正) 内任意点，处，其三个顶点处的分段 线性基函数死，萌和欢的数值等价于v 点相对于三个顶点的重心坐标分 量。因此，我们采用几何法给出相应的基函数的梯度向量，我们以顶 点v 0 处的基函数死的梯度向量为例： v 唬= 寺r ( 吃一h ) ( 2 - 3 ) 厶 其中r 代表以三角面片丁中心为原点，绕丁的法向量逆时针旋转9 0 度，4 表示三角面片丁的面积。容易看出，顶点v 0 的基函数的梯度向 量方向为对边( h ，v 2 ) 的高的方向，模长为高的倒数，且在整个三角面 片丁内取值为常数。 散度算子：给定域网格m 上的一个矢量场形，它在m 的任意一个 三角形z 上取值为常数w = w c t 。) ，我们定义w 在顶点v i 处的散度为 ( d i v w ) ( v , ) - - 矿( 丁) v 蚰4 ( 2 4 ) 其中4 指三角形丁的面积，v 铀t 为顶点k 处基函数的梯度 三维变换 三维变换是描述三维空间物体运动关系的常用手段，在计算机图 形学中被广泛使用。7 _ 个三维变换r 将源三维矢量空间y 映射到目标 矢量空间形，若变换丁不退化，则目标矢量空间形也是三维的。常见 的三维变换包括平移变换，旋转变换，缩放变换，反射变换和错切变 换。通常而言，若采取齐次坐标来表示三维空间中的点，三维变换可 1 0 网络模型的微分编辑算法研究 由4x4 变换矩阵统一给出。常见的三维变换矩阵包括平移变换矩阵 t ： t = ( 2 5 ) 其中( 瓦，0 ，乏) 为平移量；绕x 轴旋转0 角的旋转变换矩阵r ： r = = 和缩放变换矩阵s ： s = 其中( 最，s ，疋) 为缩放因子。 2 1 3 网格微分变形处理流程 00 c o s o s i i l 9 s i n 0c o s 0 00 ( 2 - 6 ) ( 2 7 ) 整个微分变形处理流程包括三个部分，分别是微分表示，属性操 纵和坐标重建。首先将输入三角网格的顶点坐标转换为定义在其上的 三个标量场，用户操纵对应的微分属性得到修改后的向量场，最后通 过坐标重建得到最终变形结果。任何不破坏模型的顶点连接关系的几 何处理算法，本质上都是在构造一个映射关系d ，将模型中任一顶点 f 从初始的空间坐标形映射到处理后的空间坐标形，即k = 烈k ) 。我们 以网格变形为例，考察自由变形技术，多分辨率编辑技术和微分变形 技术三者在构造映射关系d 时所采取的方式。自由变形技术可以概括 如下： m = c ( m p ) ， 弓乏 o o l 0 o 1 o 0 1 o o 0 0 o 0 l o 0 最o 0 s o 0 瓯o o 0 硕士学位论文 m = c ( m 尸) ，( 2 8 ) 其中m 和m ，分别表示原始模型和代理模型，c 表示原始模型相对于代 理模型的嵌入函数，m 。和m p 分别表示变形后的原始模型和变形后的 代理模型。我们可以看出，在自由变形过程中，嵌入函数c 是不变的， 即原始模型在嵌入空间中的相对位置信息是不变的。在此基础上，映 射关系d 可由嵌入函数c 和变形后的代理模型m ，直接给出。值得指 出的是，自由变形技术的映射函数d 逐点定义的，由于代理模型的变 形是任意的，所以原始模型中邻接顶点的变形位移增量可能并不一 致，从而不能保证变形结果中的几何细节得到有效保持。我们再来看 多分辨率编辑技术，它可以概括如下： m = m l qm h m = m o ( 2 9 ) 其中心和分别表示原始模型m 的低频分量和高频分量，用户 变形低频分量得到m p 再通过细节重建函数。得到变形结果m 。在 多分辨率编辑过程中，高频分量m h 保持不变。由于低频分量和高频 分量分离，多分辨率编辑技术的映射关系d 包含了由重建函数。带来 的自适应几何细节调整的能力，因此能够在一定程度上保持变形结果 中的几何细节。然后，就其本质而言，现有多分辨率方法的细节重建 函数仍然是逐点定义，因此在低频分量发生大形变时，几何细节重建 过程的稳定性就难以保证了。最后我们来看微分处理技术，它可以概 括为： m = p ( g j ) ，o = 毛y ，z ) m = p ( g ，) ，( f = x ，弘z ) 。( 2 - l o ) 其中，g f 和g 。分别是原始网格m 的顶点坐标分量对应的梯度场 和对应修改后的梯度场，尸是基于泊松方程的重建算子。由于我们的 梯度场操纵是基于局部变换进行的，因此在微分网格变形中，微分属 1 2 网络模型的微分编辑算法研究 性保持不变。与自由变形技术和多分辨率编辑技术不同的是，由于微 分变形技术的映射关系d 中包含了泊松重建算子p ，所以变形结果的 顶点坐标不再是逐点定义，而是通过线形全局优化过程得到的。更进 一步的，由于泊松重建算子优化的对象正式量化表示几何细节的网格 微分属性，所以变形结果中的几何细节得到了有效保持。 给定一个三角网格m ，我们首先选定m 作为域网格，然后将m 的 顶点坐标值视为定义在域网格上的三个标量场： s = v s p v e r m ( i = x ，y ，z )( 2 i i ) 这样通过梯度算子对三个标量场进行梯度运算，我们得到了三个 梯度场，从而给出了三维几何的微分表示方程： g j = v s p v e r m ( i = x ，y ，z )( 2 1 2 ) 采用这样的变换方式后，我们对问题的分析对象从欧式空间转倒 了离散流形上的微分属性。该微分属性提供了丰富的几何信息，包括 网格的局部朝向信息和弯曲程度，另外，由于对每一顶点其微分属性 依赖于其邻接的其他顶点，从而由微分属性可以构建出各项点坐标之 间的全局联系。 微分属性操纵：操作微分属性，主要是通过改变局部的梯度，再 间接修改三维顶点坐标值来完成三维模型编辑的。 坐标重建：微分属性操纵之后，还要把操纵后的编辑结果反映到 顶点坐标上，称之为坐标重建。过程可以归结为如下泊松方程： a f - d i v ( v f ) - d i v w ( 2 1 3 ) 其中形来自于修改后的梯度场q ，厂为重建得到坐标分量。依次求解 三个方向坐标便得到了结果解。 。 2 1 4 基于微分曲面表示的变形 基于微分表示的曲面变形方法再最近几年中得到了很大的发展， 因为基于微分表示的曲面变形具有鲁棒性，高效性，和易于实现的特 1 3 硕士学位论文 点。而且采用基于微分表示的最大优点就是在变形中能够保持局部的 微分属性从而保证变形后能够达到一个自然的，保持细节的效果。总 的说来，该变形方法首先建立网格模型的微分表示，然后通过操纵这 些微分属性，最后由改变的微分属性求解变形后的顶点坐标，从而得 到变形后的网格模型。 微分曲面操纵最初由对图像的梯度操纵得来。图像的灰度函数的 梯度被认为包含了对于人类所敏感的视觉信息。许多图像处理技术应 用了这一结论，对于公式2 1 4 g - - - v ，( 2 1 4 ) 常常作为对图像的输入梯度，然后图像处理中常常通过全局优化 的方法寻找新的图像j ，j 的梯度g ，尽量满足以下公式： = 鹕m i n d 订一gi i 也t y , ( 2 - 1 5 ) 其中q 表示图像的操纵域。由欧拉拉格朗日方程导出以下的著 名的泊松方程 a 。= d i v g ， ( 2 1 6 ) 其中一些边界条件需要被满足。图像处理中泊松方程应用的例子 如高动态光影压缩技术【2 1 1 ，该技术可以将原始的输入图像的亮度值的 对比度大大调高。实现方法是通过改变灰度域的梯度以使强对比度部 分消弱，同时使亮度值变化小的部分保持。得到的结果图像是由泊松 方程在n e u m a n n 边界条件下重建的。 类比于泊松图像处理技术，微分网格编辑方法采用如下的步骤， 首先操纵网格的微分属性，然后重建该网格，通过对给定边界条件下 ( 大部分都是d i r i c h l e t 边界条件) 进行二次优化。然而3 维曲面和图 像域不同：3 维曲面通常不仅仅只有一个高度函数，当它们是用多边 形网格表示时，通常都不是规整的局部邻接关系。而图像的像素点之 间都是规整的邻接关系。 1 4 网络模型的微分编辑算法研究 首先把梯度操纵方法应用到网格处理中的方法 2 z l 是关于网格顶 点坐标的三个分量x ，y ，z 的梯度定义在基域q ( 常常就是输入的原 始网格) 上。在连续情况下，变形后的网格由坐标，矿，2 7 确定，使 得 小v x 一g 工1 1 2d u d l ， ( 2 1 7 ) 的值最小( 同理对其余坐标分量) ，其中的约束条件由具体的模 型编辑情况给出， g ，= v 善( 2 1 8 ) 公式2 1 7 确定了原始网格模型的梯度函数。由欧拉拉格朗日方 程可导出泊松方程如下： a x 。= d i v g 工 ( 2 1 9 ) 当网格模型是不连续情况时也容易定义该模型关于坐标的梯度。 可以在网格定义在线性分片曲面，这样的话坐标函数在每一个三角片 上便是固定的。实际上，当基域是网格本身时，x 坐标函数的梯度可 以看成单位x 轴( 1 ，0 ，o ) r 在三角网格上的投影。于是，我们定义一个 分段线性标量函数厂在域网格s 上： f ( u ，v ) = z 谚( 甜，v ) ，( 2 2 0 ) f = l 其中对每一顶点值z = 厂( h ) 采用重心坐标插值的方式。 2 1 5 泊松网格变形算法求解过程 泊松网格变形算法可以表示成已知原始网格，求变形后和原网格 具有相同拓扑但是顶点位置不同的网格过程。给定原始网格，首先在 其上定义域网格，再以原始网格的顶点坐标的x ，y ，z 三个方向的分 量为三个标量场。用户对标量原始模型的修改就转换为对原始模型的 标量场和模型边界条件的修改。通过标量场合模型边界条件的修改来 1 5 硕士学位论文 求解泊松方程，从而由方程的解驱动网格变形。 对梯度场的操纵是泊松网格编辑中的一个关键。如果对网格模型 中的每一个三角片都定义一个局部变换的话，几乎是一个不可能完成 的任务。因此将局部的变换自动扩展到全局网格是必需的。 网格的边界条件对网格形状有着很大的影响，通过改变网格的边 界再通过泊松方程求解能够较好的达到编辑效果。为了方便用户对网 格模型进行编辑，用户可以通过操作闭合的边界曲线或者一个顶点来 编辑网格模型。边界曲线可以或顶点可以是固定的也可以是随动的。 这样网格中其余的自由顶点便随着边界条件的改变有泊松方程驱动 求解。 2 1 6 局部变形操纵的传播方法 保细节的曲面变形算法关键在于正确的定义局部发生的变形。这 里的“正确 是指对曲面特征的保持如朝向体积等。因此，局部的变 形操纵因该定义为接近旋转或者平移，或者等方性的缩放。 测地线距离传播法。 这种方法把局部变形的传播根据测地线距离从变形发生源依次 传播到整个网格模型。为此，常常通过将变形的控制点的操纵由一个 变换矩阵提供。该变换矩阵常常被分解为旋转和错切矩阵：t = r s ； 然后再通过测地线距离从控制点在兴趣区域( r o i ) 进行插值传播： 互= s l e r p ( r , i ，1 - s i ) ( ( 1 一岛) s + s n( 2 2 1 ) 其中s l e r p 表示对四元组的插值函数，s ，是权重系数取值范围从0 到1 ，按照测地线距离从操纵点h 依次递减： dist(p,f) 1 驴丽瓦丽莉( 2 - 2 2 )1 如( 露。f ) + 搬( 号，日) 采用这种方法控制点的形变信息被依次在兴趣区域传播，而且小 网络模型的微分编辑算法研究 尺度的变形细节也被合理的传播了。 调和函数传播法。 测地线距离传播法并不是一个最理想的变形传播方法因为该方 法会消弱局部尖锐细节的变形【2 3 】【2 4 】。为解决这个问题调和函数法被 提出，其中最的值由一个定义在网格顶点上调和标量场s 决定，该方 法有l a p l a c e 方程导出 其中d i r i c h l e t 边界条件达到时，岛取值为0 ，当墨= 1 时顶点为控 制点。采用调和函数的附加条件进行计算，变形效果更加光滑。 基于材质的传播方法。 这种方法通过设定网格表面的材质属性，常常把这种材质属性 叫做刚度，用户通过操纵接口设置网格表面的刚度，然后再由程序通 过设定在网格表面的标量场计算各个顶点的插值权重；插值权重的计 算由以下二次函数的最小值取得： m i n 伤i is , 一s j1 1 2 ( 2 2 3 ) s j 副v i c v , ) 由此公式2 - 1 0 得出当刚性参数仍，越大时，网格曲面的局部变得 更硬更难于形变。采用这种传播方式类似于调和函数传播方式，通常 将固定的边界点设置参数为0 ，控制点设置为1 。 显式优化法。 这种方法产生局部变形通过求解和原网格曲面差的最d x - 乘网 格曲面来求解啪1 。此最小二乘方程的系数由原始网格推导出。这种方 法的主要思想是优化局部的变形来保持局部细节。 隐式优化法。 采用隐式优化的方法把待求解的网格优化变换z 表达为待求解 的顶点位置的函数： 1 ，2 ，刀) 采用全局迭代优化的方法来求解出变化 1 7 硕士学位论文 后的顶点位置【2 5 】。 2 1 7 微分网格编辑算法相关工作比较 下面来介绍基于微分表示的网格编辑算法，他们或者在微分曲面 表示上不同或者在局部编辑控制点的方法上不同。 a l e x a 第一次将微分坐标应用在网格编辑中乜6 i ；他提出了基于 原始曲面的拉普拉斯算子。但是这种方法只适合编辑光滑的曲面，不 适合编辑细节尖锐的曲面，而且对网格编辑中的旋转操纵处理效果不 好。 l i p m a n 对这一问题做出了改进，增加了一个对局部旋转操纵进 行估计的方法乜7 ，采用这种方法在计算上代价较大，但是对旋转编辑 操纵处理很好。 b o s t c h 为解决旋转效果的问题提出一个类似的技术汹3 ，他提出 先计算旋转后的坐标的梯度的方法，再用泊松方程重建顶点坐标的方 法，较好解决了旋转编辑效果不好的问题。 s o r k i n e 提出了一种基于拉普拉斯的隐式优化方法【2 9 1 。 这一节主要比较不同的微分网格编辑方法的效果差别。比较的目 的并不是找出每一种编辑方法最好的变形效果而是主要测试各种编 辑方法对一般模型编辑的通用性。比较结果如图2 1 ，2 2 ，2 3 ，2 4 所示： 网络模型的微分编辑算法研究 图2 - 1 原始待编辑三维网格模型 图2 - 2 采用基于梯度场的泊松编辑法变形后的模型 图2 3 采用拉普拉斯编辑法编辑后的模型 图2 4 采用旋转不变编辑后的模型 基于梯度函数的泊松编辑方法通过对网格曲面梯度的操纵来进 1 9 硕士学位论文 行各种编辑操纵，如进行模型的旋转，缩放等操纵。但是由于该方法 是对局部旋转进行显示传播，所以对于平面模型的操纵结果并不自然 并且不保持细节。改进方法可以在显式传播局部形变时考虑更加符合 物理学的加权函数。 和基于梯度函数的泊松编辑方法不同，拉普拉斯网格曲面编辑方 法啪3 隐式的网格中各个顶点的旋转方式，因此这种方法对于平移和旋 转操纵都很适用。它最大的缺点是需要对旋转操纵进行线性化，当大 角度的旋转时容易产生误差。 旋转不变的网格编辑方法瞳朝先求解了一个线性系统来保持顶点 领域的局部标架不变，从而达到了很好的旋转编辑效果，但是对于平 移操纵由于没有考虑到顶点的位置约束条件没有拉普拉斯编辑方法 自然。 总之当网格模型编辑中涉及到大尺度的平移和旋转操纵是对于 线性编辑方法来说都是一个挑战。当遇到这种编辑需求时复杂的非线 性编辑方法现在也有所提出【3 1 】，p 2 - 阎并且随着当前计算机计算能力 的大幅提高，这些方法在将来都有可能应用到编辑系统中。 2 2 网格光顺 2 2 1 常用光顺算法介绍 由海量测量数据点得到的三角网格模型不可避免地受到各种噪 声和扰动的干扰，并且由于所使用的三角化方法原因，可能存在大量 十分狭长的三角片。用这样的三角网格模型进行参数曲面重建困难是 很大的，因而有必要在满足几何精度要求的前提下，对模型进行光顺 调整，以消除噪声，匀化三角片。 标准拉普拉斯( l a pi a c i a n ) 光顺法 标准拉普拉斯光顺法【3 4 】，0 5 是一种近年来得到广泛应用的快速、简单、 有效的网格光顺算法，它对每个顶点定义一个拉普拉斯算子 网络模型的微分编辑算法研究 ( l a p l a c i a n ) 来确定一个调整方向，通过沿调整方向以一定的速度移动 顶点来调整网格。三角网格模型中顶点v i 对应的离散拉普拉斯算子 可以用下式表示： 地) = 哆心一k ) 驴( ，) ( 2 2 4 ) 权因子国，有多种选择方式，最简单的一种是取国，= 1 n ，n 是 n 【m ) 集合的元素个数。在此基础上，得到三角网格模型中每个顶点 对应的离散拉普拉斯算子如下： l ( v ，) = ( 寺1 ，) 飞( 2 - 2 5 ) ” ，j e n p ( v j ) 实际上，拉普拉斯算子l ( u ) 是将网格中的顶点移向其周围邻域 的形心位置。离散的拉普拉斯算子应用到三角网格模型中，可以迅速 消除模型中的噪声，它实际上就是使该顶点处的噪声向其邻域内散 开，进而促使网格中三角片的形状和分布逐渐趋于均匀一致。标准拉 普拉斯光顺法就是通过l ( k ) 对顶点进行调整： = v o 艋+ 彩三) ( 2 2 6 ) 其中，甜是一个正的常数，可以控制网格光顺的速度。通常需 要将式和式2 2 6 对每个顶点迭代多次后，才能得到较为理想的满足 光顺要求并且网格分布比较均匀的模型。标准拉普拉斯光顺法能够有 效调整所有的网格至规则形状，网格密度和形状都趋于均匀，但是对 于网格分布不均匀和含有大量不规则三角片的模型，这种均一化的调 整往往会导致原始模型的大范围变形。 t a u bjn 光顺法 t a u b i n 嘞3 指出拉普拉斯算子并不是一个真正的低通滤波器，当迭 代次数足够多时，模型会逐渐收缩到其形心位置。为了定义一个真正 2 1 硕士学位论文 的低通滤波器，他通过引入一个取值在0 到1 之间，但幅值大于u 的权因子入，提出一个能抑制模