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

'中国科学技术大学UniversityofScienceandTechnologyofChina本科毕业论文ADissertationSubmittedfortheBachelor’sDegree三角网格平面参数化的研究TheMethodofPlanarParametrizationofTriangularMesh姓名单文B.S.CandidateShanWen导师刘利刚SupervisorLiuLigang2013年6月June,2013 中国科学技术大学本科毕业论文致谢光阴荏苒，时光易逝，转眼间，四年的本科生活即将画上句号。这四年里，我结识了一批志同道合的同学，接受了多位老师细心的教导。这四年里，自已不仅仅增长了学识，还磨砺了意志，增加了阅历，这四年的时光必将成为我一生的宝贵财富。如今离别在即，藉毕业论文完成的机会，对四年来一直支持帮助我的人表达最诚挚的感谢。首先要感谢刘利刚教授，是刘老师带我进入了图形学领域，让我感受到了图形学的奇妙。从大三上学期到现在，刘老师一直在鼓励我学习新知识，极大的开阔了视野，让我对图形学产生很浓的兴趣，并决定研究生阶段继续钻研这一方向，希望今后的研究生生涯继续在刘老师的教导下进行图形学的学习，感受科学的奥秘。我还要感谢科大数学系的几位老师，四年间，这些老师孜孜不倦，兢兢业业的教书育人，史济怀教授和宋光天教授更以古稀之龄亲自教授数学分析和线性代数两门基础课，引领大家进入数学的殿堂，这两位老师崇高的敬业精神让我们每一个人深受感染。最后，我要感谢我的父母，他们的理解与支持让我可以在学校专心学习，感谢他们的关爱，祝愿他们永远开心快乐。二零一三年五月于合肥 中国科学技术大学本科毕业论文目录摘要…………………………………………………………………………………3Abstract………………………………………………………………………………4第一章引言………………………………………………………………………51.1概念介绍……………………………………………………………………51.1.1三角网格…………………………………………………………………51.1.2参数化……………………………………………………………………51.2平面参数化的一些结果……………………………………………………61.3平面参数化的应用…………………………………………………………71.3.1纹理映射………………………………………………………………71.3.2重新网格化……………………………………………………………71.3.3曲面拟合………………………………………………………………8第二章保形参数化………………………………………………………………92.1方法介绍……………………………………………………………………92.2结果与分析………………………………………………………………12第三章从局部到整体的方法……………………………………………………133.1方法介绍…………………………………………………………………133.2算法设计…………………………………………………………………143.2.1最佳的L矩阵………………………………………………………143.2.2尽可能保相似的参数化方法………………………………………153.2.3尽可能保刚性的参数化方法………………………………………153.2.4混合参数化方法……………………………………………………173.3结果与分析………………………………………………………………19第四章比较与总结………………………………………………………………221 中国科学技术大学本科毕业论文4.1几种参数化方法的比较…………………………………………………224.2总结………………………………………………………………………224.3其他结果…………………………………………………………………23参考文献…………………………………………………………………………252 中国科学技术大学本科毕业论文摘要在数字几何处理领域，三角网格是描述三维模型最常用的表示方法，而参数化是数字几何处理领域基本而重要的问题，它在纹理映射、几何重建、几何建模等方面应用广泛。本文主要描述了两种三角网格平面参数化的方法，并进行了比较。1.“shape-preserving”方法。这种方法基于Tutte平图嵌入的思想提出了将网格的内部点表示为1-邻域的线性组合，固定边界点，进而通过解一个稀疏系统得到参数化结果的思想，这一思想也成为其后很多参数化方法的基本思想。2.“尽可能保持刚性”方法。这一方法使用了从局部到整体的策略，通过分析局部三角形仿射变换的奇异值，根据不同的要求调节Jacobi矩阵，进而整体求解参数化结果。这一方法是目前为止在控制几何扭曲方面最好的结果，其中从局部到整体的思想在几何处理的其他领域也大有用处。关键字：数字几何处理平面参数化保形参数化尽可能保相似尽可能保刚性3 中国科学技术大学本科毕业论文AbstractInthedigitalgeometryprocessing,triangularmeshmodelisthemostcommonrepresentationof3Dmodel,andtheparameterizationisabasicandimportantproblemwhichiswidelyusedinlotsoffields,suchastexturemapping,geometryreconstruction,geometricmodeling,etc.Thispaperproposedtwomethodsofplaneparametrizationoftriangualrmeshandcomparedthem.1.“Shape-preserving”method.ThismethodisbasedontheideaofembeddingplanargraphwhichwasproposedbyTutte.Theideaofthismethodisthatrepresenteachinteriorpointasthelinearcombinationofitsneighbor,fixboundarypointsandobtainfinalresultbysolvingasparsesystem.Thisideahadbecomethefundamentalofmanysubsequentparametricapproaches.2.“ARAP”method.Thismethoduseslocal/globalstrategy,adjustsJacobianmatrixofeachlocaltriangleaccordingtodifferentrequirementsbyanalyzingsingularvaluesoflocalaffinetransformationofeachtriangleandobtainsthefinalresultbysolvingaglobalproblem.Thismethodisthebestway,byfar,incontrollinggeometricdistortions.Itslocal/globalstrategycanalsobeusedintheotherareasofDGP.Keywords:digitalgeometryprocessing,planeparametrization,shape-preser-ving,as-similar-as-possible,as-rigid-as-possible4 中国科学技术大学本科毕业论文第一章引言第一节概念介绍1.1.1三角网格三角网格是在科学研究中描述三维模型时最常用的表示方法，是多边形网格的一种，它使用三角形为基本单元，通过相邻关系表示三维模型的表面，进而表示整个三维模型。三角网格三维模型图1.1网格与模型，该图来源于[3]三角网格采用点、线、面来表示三维几何数据，点定义了网格的空间几何信息，线和面定义了网格的拓扑信息，可以将三角网格抽象为图，三角网格可以看做图在三维空间中的一个嵌入。1.1.2参数化参数化[1,2]是数字几何处理领域中一个很基本的问题，它主要研究如何将三维几何数据映射到参数域上，即建立三维几何数据到参数域的一一对应。由于三维模型与参数域之间内在几何性质的差异，参数化过程通常会导致映射过后的三维数据相对原始数据发生扭曲变形，可能会丢失原来的几何信息，不利于后续的操作，因此，一个好的参数化方法通常要求最小化各种几何度量的扭曲，这也是参数化的研究中一个很重要的问题。另外，根据参数域选取的不同，可将参数化分为平面参数化，球面参数化，流形参数化等几类，其中平面参数化是最基本，研究最早，方法最多，最成熟的一个领域，本文的主要内容就是描述平面参数化中的两种基本方法并进行比较。5 中国科学技术大学本科毕业论文图1.2参数化，该图来源于[3]第二节平面参数化的一些成果线性参数化方法由于其使用简单，速度快，结果好等优点是普遍使用的方法。Tutte[4]曾提出重心坐标的理论，根据这一理论，可以通过将网格上一点表示为周围邻点的线性组合，通过固定三角网格上的边界点，进而求解整个线性系统，获得参数化结果：qqijNiijj(1.1)通过选择不同的线性组合的系数，可以得到不同的参数化结果。最简单的是均匀系数，即ij1/di，Floater[5]也曾提出一种求解组合系数的方法，使用这种系数可以得到结果比较好的“保形”（shape-preserving）的参数化方法，本文第二部分将细致介绍这一方法。固定边界的方法容易造成比较大的几何扭曲，特别是在边界区域，可以采用额外的方法诸如添加虚拟边界[6]或增加额外的约束方程[7]来减少扭曲。另一种参数化的方法是直接优化定义原网格与参数化结果之间几何度量扭曲程度的函数，这种方法不需要固定边界，可以有效地控制几何度量的扭曲，但往往要求解一个非线性方程，速度比较慢。在三角网格中，可以分别考虑每个三角形参数化过程中对应的Jacobi矩阵。由微分几何中的知识可知，几何扭曲可以由Jacabi矩阵的奇异值描述，整个网格的能量函数的形式是每个三角形的能量函数之和，因此整个优化问题可以表示成诸如二次优化等比较简单的形式。本文第三部分将讨论的“尽可能保持刚性”（as-rigid-as-possible）[8]方法就是这类方法中的一种。6 中国科学技术大学本科毕业论文第三节平面参数化的应用1.3.1纹理映射纹理映射[9]是真实感绘制的重要方法，而参数化的问题最初就是在纹理映射的过程中提出的。纹理映射指的是在计算机中进行绘制时，在物体表面添加一些细节特征，这些细节特征可以是颜色，法向，凹凸[10]等，这样可以简化建模过程，绘制出真实感极强的表面以及模拟复杂的光照。纹理映射的关键步骤是将二维的细节特征附着在三维表面上，这其中最简便的方法是将三维表面与平面进行一一对应，这正是平面参数化的工作。网格纹理纹理映射图1.3纹理映射1.3.2重新网格化同一个模型可以用很多种不同的网格来表示，针对不同的应用，可以使用具有不同特征的网格[11]。一般情况下，如果三角网格中很扁，很细或者很小的三角形数量比较少，那么这种网格就是一个质量比较高的网格。为了从质量不太高的网格得到高质量的网格，平面参数化是一个很好的方法，将网格映射到平面上，经过处理之后再映射回曲面，得到新的网格。比如Gu[12]等将网格映射到正方形，再对正方形做均匀采样，可以得到比较规则的网格。原网格细分网格图1.4重新网格化7 中国科学技术大学本科毕业论文1.3.3曲面拟合用光滑的曲面拟合离散的三维数据是数字几何处理非常常见的应用。通过将网格参数化，可以在平面的参数域中构造拟合曲面，大大简化了这一工作。8 中国科学技术大学本科毕业论文第二章保形参数化（shape-preserving）Floater在1997年的论文“Parametrizationandsmoothapproximationofsurfacetriangulations”中基于Tutte的平图嵌入的思想提出了将网格的内部点表示为1-邻域的线性组合，固定边界点，进而通过解一个稀疏系统得到参数化结果的思想，这一思想也成为其后很多参数化方法的基本思想。第一节方法介绍将三角网格视为一个图GVE(,)，G包含点集V{:ii1,...,}N和点对组成的边集E{(,),ijij}，di表示第i个点的邻点个数，网格的平面参数化等价2于寻找图在R中的嵌入，由kuaiwaski定理知三角网格必定存在平面嵌入。将平面上的点记为{,...,uu1N}，不妨设un11,un,...,uN为边界点且沿顺时针方向排列，由Tutte在“Howtodrawagraph”中的结论，每个内部点都可以表示成其1-邻域的凸组合，即对每个in{1,...,}，存在ij,jN1,...,，满足条件：Nij0,(,)ijEij0,(,)ijEij,1(2.1)j1使得：Nuu(2.2)iij,jj1进行适当变形，可得：nNuiij,,ujijuj,i1,...,n(2.3)j11jn若给定边界点的坐标，分别考虑平面上两个方向的分量，可以得到两个线性方程组：Aub12,Avb(2.4)uv,代表每个点坐标的两个分量组成的列向量，A是一个nn的矩阵，A的元素为：a1,ija,ijij,ij,ij,显然A是主元占优的稀疏矩阵，因此A是一个非奇异阵，上述两个方程在给定b的情况下有唯一解，方程的解加上初始设定的边界点的坐标可以作为参数化的结果。一般情况下可以将边界点均匀的分布在正多边形的边界上，只要计算出合适的重心坐标就可以得到参数化结果，由于对于边数大于三的多边形其内部点的重9 中国科学技术大学本科毕业论文心坐标不唯一，因此需要根据应用取合适的重心坐标。例如取ij,1/di，可以得到“uniform”结果，这也是Tutte提到的最简单的重心坐标的形式，这种重心坐标没有考虑到网格的任何几何信息，除了计算简单用处不大。Floater提出了另一种计算重心坐标的方法，在三角形中，重心坐标是唯一的，如图，图2.1三角形的重心坐标ABC中，O点的重心坐标的表现形式为OABCSSSOBCOACOAB(2.5)sssABCABCABC将三角形中的计算方法应用到多边形中，可以得到一种对应的重心坐标。任取网格中一个点xi，考虑该点与其1-邻域{xxj12,j,...,xjdi}（下图左）：图2.2多边形的重心坐标，该图来自[4]（1）局部参数化[13]：将局部结构映射到平面上，映射过程满足下列条件：ppxxkjkiangppp(,,)2angx(,,xx)/(2.6)kk1jkkij1i其中10 中国科学技术大学本科毕业论文diiangx(jk,,xxijk1),xjdii1xj1,pjd1p1k1（2）如果di3，即邻点个数为三，则按照之前叙述的方法计算重心坐标：areappp(,,)areappp(,,)areappp(,,)231312(2.7),,ij,1areappp(,,)ij,2areappp(,,)ij,3areappp(,,)123123123若di3，对每个ld{1,...,}i，pl到p的直线会与某一条边相交，不妨记这条边的两个端点为pprl(),rl()1，考虑pplrl()prl()1，pl存在唯一的重心坐标，可以按照之前的方法计算出来，设坐标为1,,23，则有：0,0,0,pppp(2.8)1231l2rl()3rl()1定义u，kd1,...,，u,u,u,u0，对每个l，有：kl,ill,1rll(),2rl()1,l3kl,ddiipupkl,k,ukl,1,ukl,0(2.9)kk11定义1diij,,kukl,k1,...,di(2.10)dik1由于u非零，故大于零，且有：kk,ij,k1di1dididi1didippupkl,kupkl,kij,kpkdii1dii1k1k1dii1k1didi1di1didi1diij,kuukl,kl,11k1k1dii1dii1k1dii1因此这是满足条件的一组重心坐标，从这一组重心坐标出发，按照之前提供的方法构造稀疏线性系统，可以求出形状变化比较小的参数化结果。11 中国科学技术大学本科毕业论文第二节结果与分析原网格参数化结果纹理映射结果图2.3uniform参数化结果可以看出，将组合系数简单的设置为邻点个数的倒数得到的结果会有比较大的几何误差，图1.2中红线圈出的区域有很明显的变形。原网格参数化结果纹理映射结果图2.4shape-preserving参数化结果考虑了每个点附近的几何信息后计算出新的权重在一定程度上的确起到了保形[14]的效果，图2.2中已经没有1.2中出现的很明显的形状扭曲，但是观察球面上的正方形可以发现，纹理映射之后的正方形基本都有比较明显的拉伸，原先纹理图中的直角在纹理映射图中不再是直角，因此这种方法在保角上的效果非常有限。12 中国科学技术大学本科毕业论文第三章从局部到整体的方法（local/globalapproach）上一部分介绍的参数化方法是固定边界，将每一个内点表示为1-邻域的凸组合，再求解线性系统的方法。接下来介绍的方法是不固定边界，通过从局部到整体的策略，在局部调节每个三角形的仿射变换，使其满足一定的度量扭曲的要求，再进行整体求解，寻找最优的参数化结果。这种控制扭曲的方法先是Sorkine[15]在网格编辑中应用，后来刘利刚等人将其应用到参数化中，提出了几种可以有效控制度量扭曲的参数化方法。图3.1从局部到整体，该图来自[8]第一节方法介绍由微分几何的知识知，局部一个点附近区域的参数化可以由该点的Jacobi矩阵描述，不妨设为J，通过奇异值分解，可以将J表示为一个正交变换()U，一个伸缩变换()，一个正交变换()V的乘积，其中伸缩变换是一个2×2的对角矩阵：10T(3.1)JUV02正交变换不会造成任何扭曲，因此局部区域上参数化的几何扭曲是由矩阵决定的。是一个对角阵，对角线上的两个元素是J的两个奇异值，这两个奇异值描述了映射在两个方向的伸缩，因此可以通过调节这两个奇异值控制映射过程中三角形角度，形状，面积产生的扭曲。：角度未发生扭曲，是保角映射121：形状未发生扭曲，是保形映射12具体到三角网格中，假设网格中每个三维三角形编号1到T，每个三角形都可以没有任何扭曲的映射到平面上，设三角形经过全等变换到平面中的三个点的13 中国科学技术大学本科毕业论文012012坐标分别为{,,xxx}，参数化之后的坐标为{,,uuu}，则从x到u的变换是一tttttttt个2×2的Jacobi矩阵，这个矩阵对不同的三角形是不同的，对三角形t，设这个矩阵为Jut()[16]。另外，为了控制参数化过程中三角形的几何扭曲，可以让Jt尽量接近指定的一个矩阵族M，对每个三角形设置一个从允许的变换族中取出的矩阵，这样，我们就可以定义参数化结果与变化矩阵族M间的能量函数：T2EuL(,)AJu()L(3.2)tttFt1这里的指的是Frobenius范数[17]，是一种衡量两个矩阵相似度的范数。A是Ft三角形的面积。将能量函数写成用x和u表现的形式可得：T21iii11ii2EuL(,)cot()tAut(tut)Lxt(txt)(3.3)2ti10iii1是边(,xx)在三角形中的对角。ttt问题转化为解下列最优化问题：(,)argminuLEuL(,)st..LM(3.4)(,)uLt尽管这个最优化问题需要同时求解u和L，但是只有u是需要的，L只是扮演一个辅助的角色，在下一小节的内容中将利用前面所述的奇异值决定变形的原理设计解决这一最优化问题的算法。第二节算法设计3.2.1最佳的L矩阵从局部情况考虑，每一个三角形都存在一个几何变形最小的最优变换矩阵，这些最优的矩阵的集合就是前面定义的矩阵族M，设J是实际使用的变换矩阵，是矩阵族M中对三角形最优的变换矩阵，可以使用Frobenius范数[17]度量两个矩阵的差异：2TdJL(,)JLtr(JL)(JL)(3.5)F由上节内容知，将J做SVD分解：TJUVU和V是正交矩阵，是对角阵：10(3.6)0214 中国科学技术大学本科毕业论文为便于计算，这里使用的有符号的SVD分解，即保证是非负的，这可以1通过调整U和V中元素的符号实现。由上节的内容知，时，变换是保角的；1时，变换是保形的，1212结合Procrustes分析的知识，为了让变换尽可能保形，应该把和设为1，即12TLUV；为了让变换尽可能保角，应该把和都设为()/2，这样就1212得到了两种目标不同的参数化方法。3.2.2尽可能保相似的参数化方法能保证三角形的角度扭曲比较小，矩阵族M的形式应该为：abM:,abR(3.7)baii可以用两组向量代替所有的L，a(,...,aa),b(,...,bb)，在x和固定的情t11TTtt况下，能量方程是关于abu,,的二次优化问题，求导之后可以转化为一个稀疏线性方程组。为了验证得到的结果确实是最保相似的结果，可以使用Levy定义的保角能量：TA()2t1,t2,tt1和是J的两个有符号的奇异值，A是第t个三角形的面积，文章的附1,t2,ttt录证明了上面叙述的算法和最小二乘保角映射（LSCM[18]）是等价的，最小化了角度变形的能量函数，因此这一结果是保角最优的结果。与LSCM方法一样，对非可展曲面，整个优化问题存在一个平凡解，即参数化后所有的点收缩到了一点，这个平凡解对应了能量函数的“零能”状态，为解决这个问题，只需要在求解前任取两个点将其坐标固定，就能得到理想的结果。3.2.3尽可能保刚性的参数化方法为了尽可能保证三角形的角度扭曲比较小，矩阵族M的形式应该为：cossinM:(0,2)sincos(3.8)15 中国科学技术大学本科毕业论文为证明这种方法的确保持了刚性，可以使用如下的能量函数：T22At[(1,t1)(2,t1)]t1这一能量函数与Green-Lagrange能量[19]是相似的，文章附录证明了这一方法最优了这一能量函数。由于矩阵族M中矩阵形式比较特殊，ARAP的求解过程与ASAP有一定差别，可以使用先局部再整体的迭代算法而不需要直接求解一个最优化问题，大大简化了计算步骤，加快了速度。先看局部情况，对每个三角形变形对应的Jacobi矩阵直接使用SVD分解获得最优变换矩阵：2Ju()cot()(iuiui1)T(3.9)tttti0SVD分解得：10T(3.10)Ju()UVt02直接求出L:tTLtUV图3.2三角形的仿射变换再考虑全局情况，局部部分求出了每个三角形对应的最佳变换矩阵，这样全局能量函数就只剩下u{,...,uu}这一组未知数。1T将其改写为半边结构：16 中国科学技术大学本科毕业论文T21iii11ii2EuL(,)cot()(tutut)Lxt(txt)(3.11)2ti1012EuL(,)cot()(uu)L(xx)(3.12)ijijtij(,)ij2(,)ijhe式中，he为网格中半边的集合，u和x是第i个点的坐标，tij(,)为半边(,)ijii所在的三角形的序号，为半边(,)ij在三角形tij(,)中的对角。ij令式(3.12)梯度为零，可得关于u的一列线性方程组：cot()cot()(uu)cot()Lcot()L(xx)ijjiijijtij(,)jitij(,)ijjNi()jNi()in1,...,(3.13)图3.3整体求解线性方程组的系数矩阵只依赖于原始网格的几何信息，因此该矩阵在算法中是固定不变的，计算时可以预先做Cholesky分解，在迭代过程中重复使用系数矩阵而无需计算，故而大大加速了整个过程。另外，这一算法的启动需要一个初始的参数化结果，对这一初始参数化结果的基本要求是参数化结果是正确的，没有过多的翻转而且可以很快的获得这一结果，上一章中提到的Floater提出的shape-preserving的结果及LSCM的结果都可以做为初始输入，而且在2.5节的结果中可以看出，这一算法对初始输入不敏感，算法经过迭代后可以稳定的收敛到同一个解。3.2.4混合参数化方法综合以上ASAP和ARAP参数化方法，文章中提出了一种介于两者之间的17 中国科学技术大学本科毕业论文参数化方法，这种方法使用一个系数来控制保角和保形的“权重”，混合能量函数定义如下：T21ii2222(3.14)Euab(,,)cot()tet(atbt1)2ti10这里iii11abttiie(uu)(xx)tttttbatt其中[0,)当0时，上式等价于ASAP参数化；当时，上式等价于ARAP参数化，而若取值介于两者之间，就可以得到一定程度上介于保角和保形之间的参数化结果。这一方法的求解过程和ARAP类似，可以分为一个局部步骤和一个全局步骤，并进行迭代。局部步骤中，u固定，需对每个三角形解出最优的ab,，这tt等价于解一个三次方程，可以将a和b显式表示出来。全局步骤中，a和b固定，tt需解一个u为未知数的线性稀疏方程组，与ARAP类似，可以对系数矩阵进行预分解，从而加速求解过程。18 中国科学技术大学本科毕业论文第三节结果与分析结果一：图3.4原网格1次迭代2次迭代4次迭代最终结果图3.5ARAP由上图可以看出，ARAP方法收敛的速度很快，前几次迭代结果与最终结果相差无几。在上图黑色笔迹圈出的地方有极个别三角形翻转的现象，这也是大多数参数化方法都会出现的问题，在本方法中，可以通过一些后续处理解决这个问题。19 中国科学技术大学本科毕业论文结果二：初始结果（shape-preserving）1次迭代2次迭代最终结果初始结果（ASAP）1次迭代2次迭代最终结果图3.6初始输入对ARAP的影响以上是分别采用Floater的shape-preserving参数化和ASAP参数化作为初始参数化输入后得到的结果，经过迭代后可以看出最终结果是一样的，说明ARAP不依赖于初始输入。20 中国科学技术大学本科毕业论文结果三：（）（）图3.7混合方法的结果以上是取不同权值的混合参数化方法的结果，可以看出随着的增大，参数化的结果存在一个从ASAP到ARAP渐变的过程，其中，0时与ASAP是等价的，时与ARAP是等价的。21 中国科学技术大学本科毕业论文第四章比较与总结第一节几种参数化方法的比较Floater提出的shape-preserving方法是最早的参数化方法之一，这种方法简单易行，速度快效率高，因而得到了广泛使用。此方法中将每个点表示成邻点凸组合这一参数化的思路更是被后来人广泛采用，在此基础上产生了很多别的方法。此方法不足之处也很明显，图2.7中红色笔迹圈出的区域清楚的显示出这种方法会产生比较大的几何扭曲，这是由于它使用的重心坐标比较机械，无法包含比较细致的几何信息，这使得不管在真实感绘制还是网格编辑中，shape-preserving的效果都差强人意。刘等人提出的ARAP方法是一种最大限度的控制几何扭曲的方法，结果与shape-preserving方法相比明显好很多（图3.6）。ARAP方法虽然需要迭代，但是收敛速度很快，因此实用价值很高，到目前为止，这种方法仍然是参数化中最好的方法。ARAP方法中使用了从局部到整体的求解思路，并且在此基础上结合Procrustes分析将LSCM，ASAP与ARAP这几个方法在数学上统一了起来，让我们可以从更清楚的角度认识参数化这一问题。第二节总结平面参数化是数字几何处理中一个基础且重要的问题，应用极为广泛。从图论大家Tutte的“Howtodrawagraph”开始，研究者们提出了很多方法来解决参数化过程的各种问题，本文比较细致了介绍了Floater的shape-preserving方法及刘等人的ARAP方法，比较了这两种方法的优缺点。其中，shape-preserving方法简单易行，使用了重心坐标这一应用广泛的数学工具，这使得这篇文章几乎成为数字几何处理领域中初学者的必读文章。而刘等人的ARAP方法结果优秀，效率很高，其蕴含的从局部到整体的思想在数字几何处理的其他领域同样应用广泛。参数化的方法千千万万，由于水平有限，这篇文章只介绍了两种方法，其他的诸如ABF[20]，LSCM等经典算法未能详细探究。本文中的两种方法都蕴含了很深刻的数学思想，如何将这些思想应用到其他领域也是一个很有意义的问题。22 中国科学技术大学本科毕业论文第三节其他结果图4.1原网格（cat_head）参数化结果：Shape-preservingASAPARAP图4.2cat_head参数化结果纹理映射结果Shape-preservingASAPARAP图4.3cat_head纹理映射结果23 中国科学技术大学本科毕业论文图4.4原网格（Neferti_face）参数化结果：Shape-preservingASAPARAP图4.5Neferti_face参数化结果纹理映射结果：Shape-preservingASAPARAP图4.6Neferti_face纹理映射结果24 中国科学技术大学本科毕业论文参考文献1.Sheffer,Alla,EmilPraun,andKennethRose."Meshparameterizationmethodsandtheirapplications."FoundationsandTrends®inComputerGraphicsandVision2.2(2006):105-171.2.Hormann,Kai,BrunoLévy,andAllaSheffer."Meshparameterization:Theoryandpractice.".SIGGRAPHCourseNotes(2007).3.张磊.从局部到整体的参数化算法研究[D].博士学位论文,杭州,浙江大学,2009.4.Tutte,WilliamT."Howtodrawagraph."Proc.LondonMath.Soc13.3(1963):743-768.5.Floater,MichaelS."Parameterizationandsmoothapproximationofsurfacetriangulations."ComputerAidedGeometricDesign14.3(1997):231-250.6.Lee,Yunjin,HyoungSeokKim,andSeungyongLee."Meshparameterizationwithavirtualboundary."Computers&Graphics26.5(2002):677-686.7.KamiZ,CraigGotsman,andStevenJ.Gortler."Free-boundarylinearparameterizationof3Dmeshesinthepresenceofconstraints."ShapeModelingandApplications,2005InternationalConference.IEEE,2005.8.LiuLigang,etal."Alocal/globalapproachtomeshparameterization."ComputerGraphicsForum.Vol.27.No.5.BlackwellPublishingLtd,2008.9.Bennis,Chakib,Jean-MarcVézien,andGérardIglésias."Piecewisesurfaceflatteningfornon-distortedtexturemapping."ACMSIGGRAPHcomputergraphics.Vol.25.No.4.ACM,1991.10.Blinn,JamesF."Simulationofwrinkledsurfaces."ACMSIGGRAPHComputerGraphics.Vol.12.No.3.ACM,1978.11.Alliez,Pierre,etal."Recentadvancesinremeshingofsurfaces."Shapeanalysisandstructuring.SpringerBerlinHeidelberg,2008.53-82.12.Guskov,Igor,etal."Normalmeshes."Proceedingsofthe27thannualconferenceonComputergraphicsandinteractivetechniques.ACMPress/Addison-WesleyPublishingCo.,2000.25 中国科学技术大学本科毕业论文13.Welch,William,andAndrewWitkin."Free-formshapedesignusingtriangulatedsurfaces."Proceedingsofthe21stannualconferenceonComputergraphicsandinteractivetechniques.ACM,1994.14.Gansner,EmdenR.,YehudaKoren,andStephenNorth."Graphdrawingbystressmajorization."GraphDrawing.SpringerBerlinHeidelberg,2005.15.Sorkine,Olga,andMarcAlexa."As-rigid-as-possiblesurfacemodeling."ACMInternationalConferenceProceedingSeries.Vol.257.2007.16.Sander,PedroV.,etal."Texturemappingprogressivemeshes."Proceedingsofthe28thannualconferenceonComputergraphicsandinteractivetechniques.ACM,2001.17.Pinkall,K.Polthier."ComputingdiscreteminimalsurfacesandtheirconjugatesExp."Math.2(1993).15–3618.Gower,JohnC.,andGarmtB.Dijksterhuis.Procrustesproblems.Vol.3.Oxford:OxfordUniversityPress,2004.19.Lévy,Bruno,etal."Leastsquaresconformalmapsforautomatictextureatlasgeneration."ACMTransactionsonGraphics(TOG)21.3(2002):362-371.20.Maillot,Jérôme,HusseinYahia,andAnneVerroust."Interactivetexturemapping."Proceedingsofthe20thannualconferenceonComputergraphicsandinteractivetechniques.ACM,1993.21.Zayer,Rhaleb,BrunoLévy,andHans-PeterSeidel."Linearanglebasedparameterization."FifthEurographicsSymposiumonGeometryProcessing-SGP2007.2007.26'