单文_三角网格平面参数化的研究

中国科学技术大学 科毕业论文 A s 角网格平面参数化的研究 姓 名 单文 导 师 刘利刚 2013 年 6 月 2013 中国科学技术大学本科毕业论文 致 谢 光阴荏苒，时光易逝，转眼间，四年的本科生活即将画上句号。这四年里，我结识了一批志同道合的同学，接受了多位老师细心的教导。这四年里，自已不仅仅增长了学识，还磨砺了意志，增加了阅历，这四年的时光必将成为我一生的宝贵财富。如今离别在即，藉毕业论文完成的机会，对四年来一直支持帮助我的人表达最诚挚的感谢。 首先要感谢刘利刚教授，是刘老师带我进入了图形学领域，让我感受到了图形学的奇妙。从大三上学期到现在，刘老师一直在鼓励我学习新知识，极大的开阔了视野，让我 对图形学产生很浓的兴趣，并决定研究生阶段继续钻研这一方向，希望 今后的研究生生涯继续在刘老师的教导下进行图形学的学习，感受科学的奥秘。 我还要感谢科大数学系的几位老师，四年间，这些老师孜孜不倦，兢兢业业的教书育人，史济怀教授和宋光天教授更以古稀之龄亲自教授数学分析和线性代数两门基础课，引领大家进入数学的殿堂，这两位老师崇高的敬业精神让我们每一个人深受感染。 最后，我要感谢我的父母，他们的理解与支持让我可以在学校专心学习，感谢他们的关爱，祝愿他们永远开心快乐。 二零一三年 五月 于合 肥中国科学技术大学本科毕业论文 1 目录 摘要 3 4 第 一 章 引言 5 念介绍 5 5 5 面参数化的一些结果 6 平面参数化的应用 7 纹理映射 7 重新网格化 7 曲面拟合 8 第 二 章 保形参数化 9 方法介绍 9 结果与分析 12 第 三 章 从局部到整体的方法 13 方法介绍 13 算法设计 14 最佳的 14 尽可能保相似的参数化方法 15 尽可能保刚性的参数化方法 15 混合参数化方法 17 结果与分析 19 第 四 章 比较与总结 22 中国科学技术大学本科毕业论文 2 几种参数化方法的比较 22 总结 22 其他结果 23 参考文献 25 中国科学技术大学本科毕业论文 3 摘要 在数字几何处理领域，三角网格是描述三维模型 最常用的表示方法，而参数化是数字几何处理领域基本而重要的问题，它在纹理映射、几何重建、几何建模等方面应用广泛。本文主要描述了两种三角网格平面参数化的方法，并进行了比较。 1. “法。 这种方法基于 图嵌入的思想提出了将网格的内部点表示为 1定边界点，进而通过解一个稀疏系统得到参数化结果的思想，这一思想也成为其后很多参数化方法的基本思 想。 2.“尽可能保持刚性 ” 方法。 这一方法使用了从局部到整体的策略，通过分析局部三角形仿射变换的奇异值，根据不同的要求调节 阵，进而整体求解参数化结果。这一方法是目前为止在控制几何扭曲方面最好的结果，其中从局部到整体的思想在几何处理的其他领域也大有用处。 关键字：数字几何处理 平面参数化 保形参数化 尽可能保相似 尽可能保刚性 中国科学技术大学本科毕业论文 4 n is D is a is in of as of of 1.“is on of of is as of by a of 2.“of to by of of by a is by in be 国科学技术大学本科毕业论文 5 第一章 引言 第 一 节 概念介绍 三角网格是在科学研究中描述三维模型时最常用的表示方法，是多边形网格的一种，它使用三角形为基本单元，通过相邻关系表示三维模型的表面，进而表示整个三维模型。 三角网格 三维模型 图 格与模型，该图来源于 3 三角网格采用点、线、面来表示三维几何数据，点定义了网格 的空间几何信息，线和面定义了网格的拓扑信息，可以将三角网格抽象为图，三角网格可以看做图在三维空间中的一个嵌入。 参数化 1,2是数字几何处理领域中一个很基本的问题，它主要研究如何将三维几何数据映射到参数域上，即建立三维几何数据到参数域的一一对应。 由于三维模型与参数域之间内在几何性质的差异，参数化过程通常会导致映射过后的三维数据 相对原始 数据 发生扭曲变形，可能会丢失原来的几何信息，不利于后续的操作，因此，一个好的参数化方法通常要求最小化各种几何度量的扭曲，这也是参数化的研究中一个很重要的问题。另外， 根据参数域选取的不同，可将参数化分为平面参数化，球面参数化，流形参数化等几类，其中平面参数化是最基本，研究最早，方法最多，最成熟的一个领域，本文的主要内容就是描述平面参数化中的两种基本方法并进行比较。 中国科学技术大学本科毕业论文 6 图 数化，该图来源于 3 第 二 节 平面参数化的一些成果 线性参数化方法由于其使用简单，速度快，结果好等优点是普遍使用的方法。曾提出重心坐标的理论，根据这一理论，可以通过将网格 上一点表示为周围邻点的线性组合，通 过固定三角网格上的边界点，进而求解整个线性系统，获得参数化结果： ( 通过选择不同的线性组合的系数，可以得到不同的参数化结果。最简单的是均匀系数，即 1/ij ， 也曾提出一种求解组合系数的方法，使用这种系数可以得到结果比较好的“保形”（ 参数化方法，本文第二部分将细致介绍这一方法。 固定边界的方法容易造成比较大的几何扭曲，特别是在边界区域，可以采用额外的方法诸如添加虚拟边界 6或增加额外的约束方程 7来减少扭曲。 另一种参数化的方法是直接优化定义原网格与参数化结果之间几何度量扭曲程度的函数， 这种方法不需要固定边界，可以有效地控制几何度量的扭曲，但往往要求解一个非线性方程，速度比较慢。在三角网格中，可以分别考虑每个三角形参数化过程中对应的 阵。由微分几何中的知识可知 ，几 何扭曲可以由 阵的奇异值描述 ，整个网格的能量函数的形式是每个 三角 形的能量函数之 和，因此整个优化问题可以表示成诸如二次优化等比较简单的形式。本文第三部分将讨论的“尽可能保持刚性”（ 8方法就是这类方法中的一种。 ii ij 中国科学技术大学本科毕业论文 7 第 三 节 平面参数化的应用 纹理映射 9是真实感绘制的重要方法，而参数化的问题最初就是在纹理映射 的过程中提出的。纹理映射指的是在计算机中进行绘制时，在物体表面添加一些细节特征，这些细节特征可以是颜色，法向，凹凸 10等，这样可以简化建模过程，绘制出真实感极强的表面以及模拟复杂的光照。 纹理映 射的关键步骤是将二维的细节特征附着在三维表面上，这其中最简便的方法是将三维表面与平面进行一一对应，这正是平面参数化的工作。 网格 纹理 纹理映射 图 理映射 新网格化 同一个模型可以用很多种不同的网格来表示，针对不同的应用，可以使用具有不同特征的网格 11。一般情况下，如果三角网格中很扁，很细或者很小的三 角形数量比较少 ，那么这种网格就是一个质量 比较高的网格。为了从质量不太高的网格得 到高质量的网格 ，平面参数化是一个很好的方法，将网格映射到平面上，经过处理之后再 映射回曲面，得到新的网格。比如 2等将网格映射到正方形，再 对正方形做均匀采样，可以得到比较规则的网格。 原网格 细分网格 图 新网格化 中国科学技术大学本科毕业论文 8 面拟合 用光滑的曲面拟合离散的三维数据是数字几何处理非常常见的应用。通过将网格参数化，可以在平面的参数域中构造拟合曲面，大大简化了这一工作。 中国科学技术大学本科毕业论文 9 第 二 章 保形参数化（ 1997 年的论文 “of 基于 平图嵌入的思想提出了将网格的内部点表示为 1定边界点，进而通过解一个稀疏系统得到参数化结果的思想，这一思想也成为其后很多参数化方法的基本思想。 第 一 节 方法介绍 将三角网格视为一个图 ( , ) ， G 包含 点集 : 1,., V i i N 和点对组成的边集 ( , ), E i j i j， 示第 i 个点 的邻点个数，网格的平面参数化 等价于寻找图在 2R 中的嵌入，由 理知三角网格必定存在平面嵌入。 将平面上的点记为 1 ,., 不妨设 11, ,.,n n Nu u u 为边界点且沿顺时针 方向排列，由 “to a 的结论，每个内部点都可以表示成其1对每个 1, ., ，存在 , 1,.,ij ，满足条件： (使得： (进行适当变形，可得： (若给定边界点的坐标，分别考虑平面上两个方向的分量，可以得到两个 线性方程组： (,A 是一个 的矩阵， A 的元素为： 显然 A 是主元占优的稀疏矩阵，因此 A 是一个非奇异阵，上述两个方程在给定 b 的情况下有唯一解，方程的解加上初始设定的边界点的坐标可以作为参数化的结果。 一般情况下可以将边界点均匀的分布在正多边形的边界上，只要计算出合适 的重心坐标就可以得到参数化结果，由于对于边数大于三的多边形其内部点的重 ,10 , ( , ) 0 , ( , ) 1Ni j i j i j E i j E ,1Ni i j ,11 , 1 , . . . ,i j j i j jj j nu u u i n 12,A u b A v b, , ,1 , ,i j i j i ja i j a i j 中国科学技术大学本科毕业论文 10 心坐标不唯一，因此 需要根据应用 取合适的重心坐标。例如取 , 1/i j ，可以得到 “果，这也是 到的最简单的重心坐标的形式 ，这种重心坐标没有考虑到网格的任何几何信息，除了计算简单用处不大。 出了另一种计 算重心坐标的方法，在三角形中，重心坐标是唯一的， 如图， 图 角形的 重心坐标 中， (将三角形中的计算方法应用到多边形中，可以得到一种对应的重心坐标。 任取网格中一个点 考虑该点与其 1, ,., j jx x x（下图左）： 图 边形的重心坐标， 该图来自 4 （ 1） 局部参数化 13：将局部结构映射到平面上，映射过程满足下列条件： (其中 O A B C O B C O A C O A C A B C A B Ss s s kk j ip p x x 11( , , ) 2 ( , , ) /k j i j ia n g p p p a n g x x x 中国科学技术大学本科毕业论文 11 （ 2） 如果 3， 即邻点个数为三，则按照之前叙述的方法计算重心坐标： (若 3，对每个 1,., ， p 的直线会与某一条边相交，不妨记这条边的两个端点为 ( ) ( ) 1,r l r ，考虑 ( ) ( ) 1l r l r lp p p ， 在唯一的重心坐标，可以按照之前的方法计算出来，设坐标为 1 2 3, ，则有： (定义 , 1,., ， , 1 ( ) , 2 ( ) 1 , 3 , , , 0l l r l l r l l k lu u u u ，对每个 l，有： (定义 (由于 ,零，故 ,于零，且有： 因此这是满足条件的一组重心坐标，从这一组重心坐标出发，按照之前提供的方法构造稀疏线性系统，可以求出形状变化比较小的参数化结果。 1 1 1 1 11 ( , , ) , ,ik k d j i j j j jk a n g x x x x x p p 1 2 32 3 1 3 12, , ,1 2 3 1 2 3 1 2 3( , , ) ( , , ) ( , , ),( , , ) ( , , ) ( , , )i j i j i ja r e a p p p a r e a p p p a r e a p p pa r e a p p p a r e a p p p a r e a p p p 1 2 3 1 2 ( ) 3 ( ) 10 , 0 , 0 , l r l r lp p p p , , ,11, 1 , 0l k k l k u p u u ,11 , 1 , .,j k l u k , , ,1 1 1 1 1 11 1 1i i i i i d d d d dk l k k l k i j ki i k k i ki i ip p u p u p pd d d , , ,1 1 1 1 1 11 1 1 11i i i i i d d d d di j k l k lk k i i k ii i d d 中国科学技术大学本科毕业论文 12 第 二 节 结果与分析 原网格 参数化结果 纹理映射结果 图 2.3 可以看出，将组合系数简单的设置为邻点个数的倒数得到的结果会有比较大的几 何误差，图 红线圈出的区域有很明显的变形。 原网格 参数化结果 纹理映射结果 图 2.4 考虑了每个点附近的几何信息后计算出新的权重在一定程度上的确起到了保形14的效果，图 已经没有 出现的很明 显的形状扭曲，但是观察球面上的正方形可以发现，纹理映射之后的正方形基本都有比较明显的拉伸，原先纹理图中的直 角在纹理映射图中不再是直角，因此这种方法在保角上的效果非常有限 。 中国科学技术大学本科毕业论文 13 第 三 章 从局部到整体的方法（ 上一部分介绍的参数化方 法是固定边界， 将每一个内点表示为 1再 求解线性系统的方法。接下来介绍的方法 是不固定边界，通过从局部到整体的策略，在局部调节每个三角形的仿射变换 ，使其满足一定的度量扭曲的要求，再进行整体求解，寻找最优的参数化结果。这种控 制扭曲的方法先是 5在网格编辑中应用，后来刘 利刚 等人 将其应用到参数化中，提出了几种可以有效控制度量扭曲的参数化方法。 图 局部到整体，该图来自 8 第一节 方法介绍 由微分几何的知识知，局部一个点附近区域的参数化可以由该点的 阵描述， 不妨 设为 J ，通过奇异值分解，可以将 J 表示为一个正交变换 ()U ，一个伸缩变换 () ，一个正交变换 ()V 的乘积 ，其中伸缩变换是一个 2 2 的对角矩阵 ： (正 交变换不会造成任何扭曲，因此局部区域上参数化的几何扭曲是由矩阵 决定的。 是一个对角阵，对角线上的两个元素是 J 的两个奇异值，这两个奇异值描述了映射在两个方向的伸缩，因此可以通过调节这两个奇异值控制映射 过程中三角形角度，形状，面积产生的扭曲。 12 ：角度未发生扭曲，是保角映射 121：形状未发生扭曲，是保形映射 具体到三角网格中，假设网格中每个三维三角形编号 1 到 T，每个三角形都 可以没有任何扭曲的映射到平面上，设三角形经过全等变换到平面中的三个点的 1200 V 中国科学技术大学本科毕业论文 14 坐标分别为 0 1 2 , , t t tx x x ，参数化之后的坐标为 0 1 2 , , t t tu u u ，则从 变换是一 个 22 的 阵，这个矩阵对不同的三角形是不同的，对三角形 t ，设这个 矩阵为 ()6。另外，为了控制参数化过程中三角形的几何扭曲，可以让 量接近指定的一个矩阵族 M ，对每个三角形设置一个从允许的变换族中 取出的矩阵，这样，我们就可以定义参数化结果与变化矩阵族 M 间的能量函数： (这里的 F 指的是 数 17，是一种衡量两个矩阵相似度的范数。 三角形的面积。将能量函数写成用 x 和 u 表现的形式可得： (是边 1( , )在三角形中的对角。 问题转化为解下列最优化问题： (尽管这个最优化问题需要同时求解 u 和 L ，但是只有 u 是需要的， L 只是扮演一个辅助的角色，在下一小节的内容中将利用前面所述的奇异值决定变形的原理设计解决这一最优化问题的算法。 第二节 算法设计 矩阵 从局部情况考虑，每一个三角形都存在一个几何变形最小的最优变换矩阵，这些最优的矩阵的集合就是前面定义的矩阵族 M ，设 J 是实际使用的变换矩阵，是矩阵族 M 中对三角形最优的变换矩阵，可以使用 数 17度量两 个矩阵的差异： (由上节内容知，将 J 做 解： U 和 V 是正交矩阵， 是对角阵： (21( , ) ( )Tt t t u L A J u L2 211101( , ) c o t ( ) ( ) ( )2 T i i i i it t t t t t u L A u u L x x ( , )( , ) a r g m i n ( , ) . E u L s t L M2( , ) ( ) ( ) L J L t r J L J L V1200 中国科学技术大学本科毕业论文 15 为便于计算，这里使用的有符号的 解，即保证 1 是非负的，这可以 通过调整 U 和 V 中元素的符号实现。 由 上节的内容知， 12 时，变换是保角的； 121时，变换是保形的，结合 析的知识，为了让变换尽可能 保形，应该把 1 和 2 设为 1，即V ；为了让变换尽可能 保角，应该把 1 和 2 都设为 12( )/ 2 ，这样就得到了两种目标不同的参数化方法。 可能保相似的参数化方法 能保证三角形的角度扭曲比较小，矩阵族 M 的形式应该为： (可以用两组向量代替所有的 11( , ., ) , ( , ., )a a b b b，在 固定的情况下，能量方程是关于 ,二次优化问题，求导之后可以转化为一个稀疏线性方程组。 为了验证得到的结果确实是最保相似的结果，可以使用 义的保角能量： 1,t 和 2,t 是 两个有符号的奇异值， 第 t 个三角形 的面积 ，文章的附录证明了上面叙述的算法和最小二乘保角映射（ 8）是等价的，最小化了角度变形的能量函数，因此这一结果是保角最优的结果。 与 法一样，对非可展曲面，整个优化问题存在一个平凡解，即参数化后所有的点收缩到了一点，这个平凡解对应了能量函数的“零能”状态，为解决这个问题，只需要在求解前任取两个点将其坐标固定，就能得到理想的结果。 可能保刚性的参数化方法 为了尽可能保证三角形的角度扭曲比较小，矩阵族 M 的形式应该为： (:,a b 21, 2 ,1 ()Tt t c o s s ( 0 , 2 )s in c o 中国科学技术大学本科毕业论文 16 为证明这种方法的确保持了刚性，可以使用如下的能量函 数： 这一能量函数与 量 19是相似的，文章附录证明了这一方法最优了这一能量函数。 由于 矩阵族 M 中矩阵形式比较特殊， 求解过程与 一定差别，可以使用先局部再整体的迭代算法而不需要直接求解一个最优化问题，大大简化了计算步骤，加快了速度。 先看局部情况，对每个三角形变形对应的 阵直接使用 解获得最优变换矩阵： (解得： (直接求出 图 角形的仿射变换 再考虑全局情况，局部部分求出了每个三角形对应的最佳变换矩阵，这样全局能 量函数就只剩下 1 ,., Tu u u 这一组未知数。 将其改写为半边结构： 221 , 2 ,1 ( 1 ) ( 1 ) Tt t 2 10( ) c o t ( ) ( )i i i Tt t t u u u120() 0 u U V V中国科学技术大学本科毕业论文 17 (式中， 网格中半边的集合， 第 i 个点的坐标， (, )ti j 为半边 (, )为半边 (, ), )ti j 中的对角。 令式 (度为零，可得关于 u 的一列线性方程组： (图 体求解 线性方程组的系数矩阵只依赖于原始网格的几何信息，因此该矩阵在算法中是固定不变的，计算时可以预先做 解，在迭代过程中重复使用系数矩阵而无需计算，故而大大加速了整个过程。 另外，这一算法的启动需要一个初始的参数化结果，对这一初始参数化结果的基本要求是参数化结果是正确的，没有过多的翻转而且可以很快的获得这一结果，上一章中提到的 出的 结果 及 结果都可以做为初始输入，而且在 一算法对初始输入不敏感，算法经过迭代后可以稳定的收敛到同一个解。 合参数化方法 综合以上 数化方法，文章中提出了一种介于两者之间的 2 211101( , ) c o t ( ) ( ) ( )2 T i i i i it t t t t u L u u L x x 2( , )( , )1( , ) c o t ( ) ( ) ( )2 i j i j t i j i ji j h eE u L u u L x x ( , ) ( , )( ) ( )c o t ( ) c o t ( ) ( ) c o t ( ) c o t ( ) ( )i j j i i j i j t i j j i t i j i i j N iu u L L x x 1,.,中国科学技术大学本科毕业论文 18 参数化方法 ，这种方法使用一个系数来控制保角和保形的“权重”，混合能量函数定义如下： (这里 其中 0, ) 当 0 时，上式等价于 数化；当 时，上式等价于 数化，而若 取值介于两者之间，就可以得到一定程度上介于保角和保形之间的参数化结果。 这一方法的求解过程和 似，可以分为一个局部步骤和一个全局步骤，并进行迭代。局部步骤中， u 固定，需对每个三角形解出最优的 ,等价于解一个三次方程，可以将 式表示出来。全局步骤中 ， a 和 b 固定，需解一个 u 为未知数的线性稀疏方程组，与 似，可以对系数矩阵进行预分解，从而加速求解过程。 2 2 2 2 2101( , , ) c o t ( ) ( 1 )2 T t t u a b e a b 11( ) ( )i i i it t t t u u x 中国科学技术大学本科毕业论文 19 第三节 结果与分析 结果一： 图 网格 1次迭代 2次迭代 4次迭代 最终结果 图 上图可以看出， 法收敛的速度很快，前几次迭代结果与最终结果相差 无几。在上图黑色笔迹圈出的地方有极个别三角形翻转的现象，这也是大多数参数化方法都会出现的问题，在本方法中，可以通过一些后续处理解决这个问题。 中国科学技术大学本科毕业论文 20 结果二： 初始结果（ 1 次迭代 2次迭代 最终结果 初始结果（ 1次迭代 2次迭代 最终结果 图 始输入对 影响 以上是分别采用 数化和 数化 作为 初始参数化 输入后得到的 结果，经过迭代后可以看出最终结果是一样的，说明依赖于初始输入。 中国科学技术大学本科毕业论文 21 结果三： （ ） （ ） 图 合方法的结果 以上是取不同权值的混合参数化方法的结果，可以看出随着 的增大，参数化的结果存在一个从 变的过程，其中， 0 时与 等价的， 时与 等价的。 中国科学技术大学本科毕业论文 22 第 四 章 比较与总结 第 一 节 几种参数化方法的比较 出的 法是最早的参数化方法之一，这种方法简单易行，速度快效率高，因而得到了广泛使用。此方法中将每个点表示成邻点凸组合这一参数化的思路更是被后来人广泛采用，在此基础上产生了很多别的方法。此方法不足之处也很明显，图 红色笔迹圈出的区域清楚的显示出这种方法会产生比较大的几何扭曲，这是由于它使用的重心坐标比较机械，无法包含比较细致的几何信息，这使得不管在真实感绘制还是网格编辑 中 ， 刘等人 提出的 法是一种最大限度的控