保细节的曲面编辑算法研究 27页

'中国科学技术大学UniversityofScienceandTechnologyofChina本科毕业论文ADissertationSubmittedfortheBachelor’sDegree保细节的曲面编辑算法研究SurfaceEditingwithDetailPreservation姓名李勃B.S.CandidateBoLi导师刘利刚教授SupervisorProf.LigangLiu2013年5月May,2013 中国科学技术大学本科毕业论文致谢感谢中国科学技术大学多年在学习生活中的帮助，使学生在思想境界，学术水平上都有了比较大的提高。并感谢母校能给学生这样一个机会完成这篇论文。感谢中国科学技术大学刘利刚老师在本论文将近三个月的制作期间持续地耐心地解答学生的问题。刘老师不仅在论文中各种难点处给予学生自然而深刻的指导，而且在学生学习生活方面处于十分迷茫的时期提供了友善而有力的教诲，使学生能够正视人生道路上的困难，在接下来的若干年里学生也将跟随刘老师从事相关研究工作，希望老师不吝教导。同时感谢中国科学技术大学单文同学、丁超同学与华中科学技术大学的王康同学等在这段时间内提供的各种资源上和知识上的帮助。感谢孙琪同学在论文相关资源相关的方方面面的协助，孙琪同学在共同学习的四年中提供了学生各种各样的帮助，其所充满的专业精神与助人精神，是我所应该学习的。能够顺利的完成学业并走向新的道路我十分高兴，在此亦将十分感谢同宿舍以及邻舍的各位同学，给我创造了这样一个充满了善意与努力的环境。尤其感谢我的父母在各方面的无私的大力支持与默默的奉献，我以你们为荣。1 中国科学技术大学本科毕业论文目录致谢1摘要3Abstract4第一章绪论51.1引言..................................51.2相关工作...............................6第二章Laplacian编辑92.1Laplacian坐标............................92.2Laplacian编辑............................102.3Laplacian编辑的实现........................142.4Laplacian编辑的优缺点.......................15第三章ARAP编辑163.1ARAP局部分析...........................163.2ARAP整体处理...........................183.3ARAP编辑的实现..........................193.4ARAP编辑的特点..........................20第四章总结与延伸234.1总结..................................234.2延伸..................................23参考文献262 中国科学技术大学本科毕业论文摘要伴随着计算机图形学学科的深入发展与该学科应用于实际工作中要求的广泛加深，三维模型的形状变形问题变得相当基本而重要。本篇论文便主要介绍了三维模型形状编辑过程中能够有效保持模型表面细节的两种算法。分别为基于Laplacian坐标变换的Laplacian编辑以及以此为基础的进一步地施加刚性修正的ARAP编辑。本论文着重于介绍两种算法的原理、实现、应用以及发展，大致分为三个部分。第一部分，也就是第二章我们主要介绍Laplacian编辑。这种Lapla-cian编辑是一种先对选定区域中各点建立局部拉普拉斯坐标，然后通过引导其进行平移、旋转、放缩这几种可以保持细节部分的变换来完成保持模型表面细节的形状变形的一种算法。这种算法可以有效地完成保持模型表面细节形状变形，并且具有形式简洁，运算速度快等诸多优点。而第二部分，我们则介绍ARAP编辑，这将放在第三章中进行。ARAP编辑，即极大刚性编辑，作为Laplacian编辑不能良好的控制形变模型细节刚性这一问题的解决方案，要在Laplacian编辑的基础上建立晶格体系，通过奇异值分解提取之前坐标变换对每一个晶格结构变换的旋转分量，对之前变换进行晶格旋转变换的近似来达到刚性修正的效果。这一方法可以比较好地保持形状变形过程中的模型的刚性，从而达到Laplacian编辑所不能达到的效果。在最后我们也较详尽地比较了两者在形状变形过程中所达到的保持细节形式的差异，提出了保细节形状变形中的一些问题。这也是本论文的重要内容之一。关键字:图形变形，Laplacian编辑，ARAP编辑，稀疏矩阵3 中国科学技术大学本科毕业论文Abstract3DmesheseditingisbecomingmoreandmoreimportantwiththerapiddevelopmentofComputerGraphicsanditsapplication.Thispa-perintroducestwosurfaceeditingalgorithmswhichcankeepthesurfacedetails,theLaplacianeditingbasedontheLaplaciancoordinatesandAs-rigid-as-possiblesurfaceediting.Thethesisfocusesontheimplementation,applicationanddevelopmentofthetwoalgorithms.Thefirstone,laplacianediting,isbasedonthelocalLaplaciancoordi-nates,bydirectingitssimplecoordinatetransformationtokeepthesurfacedetails.Ithasmanyadvantagesuchascomputingfastandachievingeasily.Thelatterone,ARAPediting,keepsthemodelasrigidaspossiblebysettingupCells.ByusingsingularvaluedecompositiontoLaplaciansurfaceediting,itcanfindarotationapproximationforkeepingrigid.ThisapproachcanmakeitwhileLaplacianeditingcannot.Thedifferenceofthemisalsotheemphasisofthispaper,whichwewilldiscussattheend.Keywords:modelediting,Laplacianediting,ARAPediting,SparseMatrix4 中国科学技术大学本科毕业论文第1章绪论1.1引言形状变形是计算机图形学中十分重要的一类问题。在处理三维图形的实际过程中，三角网格在记录点、线、面的数据以及此三者之间关系的维护方面具有十分显著的优势，故三角形网格成为了此问题中比较常用的模型之一。从而形状变形的相关问题经常直接演变成处理三角网格坐标变换的问题。在以往的三角网格坐标变换的研究中，比较自然的想法是在世界坐标系中研究变换。然而，实际上对于处理形状变形细节的保持这一问题，大部分情况下我们并不需要对每个点的绝对位置进行关注，而只需要考虑点的邻域中的其他点与其的相对位置关系即可。这就是说我们可以根据网格中每个点与其周围的少数点建立局部的坐标架，通过这种局部标架就可以有效的处理点的平移、旋转、放缩变换过程中的细节保持问题。并且如此建立标架可以构建出坐标变换的大规模稀疏矩阵的线性方程组，利用方程组的显著的稀疏性就可以快速求出变换后各点的坐标。这就是目前的大部分形状变形相关的网格编辑的主要思路。Laplacian编辑就是这种思路所产生的一种图形变形算法。而无论是在工业生产或是日常生活中，具有一定刚性的三维模型均是十分平凡的。在处理这一类模型的形状变形过程中，保持细节部分的相对水平的稳定也是十分重要的一类问题。而在接下来的讨论中我们得出结论，仅靠Laplacian编辑来完成形状变形时会导致此类模型变换后细节的平衡上相对失真。对于这种情况，就可以通过ARAP编辑来进行有效的修正。其基本思路是先进行一次预测式的变换，这一步应用Laplacian编辑即可，然后通过逐点建立1-邻域的晶格结构，将之前的坐标变换视为对于每个晶格的基本变换。对此变换的矩阵利用奇异值分解的方法抽取其中的旋转变换，以此旋转变换作为该晶格的基本变换的近似来操作整个图形的变换，从而控制模型细节的刚性。5 中国科学技术大学本科毕业论文1.2相关工作三维形状变形的相关问题在计算机图形学领域占有重要地位，因而在以往已经有相当多的学者置身于这些研究之中了，而这篇文章就是主要基于Sorkine等的关于Laplacian编辑的文章[1]与这一研究小组关于ARAP编辑的文章[2]完成的。在此之前的相关研究中，比较古老的研究方向是将所编辑图形进行合理拆分，将三维网格中的光滑部分和细节部分通过特定的算法提取出来，并将两者分别进行编辑[3][4]，这种方法虽然可以实现，但是成本比较大，运算速度慢，占据资源多，此后就不太热门了。而后则出现一些基于整体编辑的形状变形，如Welch等的简易形状编辑[5]，Taubin等的光滑表面处理算法[6]，Veuvre等的基于有限元建模的形状变形[7]等等，这些算法产生于三维网格整体编辑研究的初期，对于处理相对光滑三维网格形状变形具有很好的效果，但对于处理具有显著细节需要保持的三维网格，这些方法的效果就不尽人意了。再之后，FORSEY等人提出了保细节形状变形在世界坐标系中实现的算法[8]，可以比较有效的保持形状变形中的细节部分，但是这种基于整体点的研究思路，也导致了运算上的规模过大的问题。后来在图像处理领域中Perez等将偏微分方程引入其中提出了基于泊松方程的图像拼接技术[9]，效果十分显著，且其所用的求解大规模稀疏矩阵方程组的运算技术发展十分迅速，运算速度非常之快。6 中国科学技术大学本科毕业论文图1.1:基于Possion方程的图像拼接技术[9]以此为鉴，Sorkine等在不久之后提出了相似的工作，即相似地通过建立数值微分方程来研究三维模型的形状变形[10]，进而提出了之后要介绍的Laplacian编辑[1]，在这之后Liu等又发展出了双重Laplacian编辑[11]。图1.2:基于Laplacian编辑的形状变形[1]另一方面，形状变形中细节保持的研究并不止于此，Laplacian编辑的非刚性结果并不令人满意，而解决这一问题成了更进一步的研究方向，随着以模型表面形状能量函数理论[12]控制刚性保持的方法得到重视，相关研究变得更多。但因为此能量函数实际上不是线性的，所以应用起来并不顺利。Koobrlt7 中国科学技术大学本科毕业论文等于是做了许多将其线性化的工作[13][14][15]。结合着另外一些基于特殊标架的形状变形算法[16][17]，Sorkine等又进一步提出了ARAP编辑[2]。图1.3:基于ARAP编辑的形状变形[2]8 中国科学技术大学本科毕业论文第2章Laplacian编辑2.1Laplacian坐标对于一个已知的三角形网格，对网格中所有点进行编号f1;:::;ng，并定义集合V表示网格中所有点的坐标的集合，即:V=fv1;:::;vng定义集合K表示网格中所有边的集合，就是说，若i与j为一条边的两个顶点，则(i;j)2K。取点i的1-邻域，即与点i直接相连成边的点的集合，定义为Ni，即：Ni=fjj(i;j)2Kg定义di为点i的度，表示点i的1-邻域内点的数量，即：di=jNij由此，用于代替世界坐标系分析局部问题，我们确立点i的局部Laplacian坐标。为了简洁起见我们只将“局部”限定在点i的1-邻域内，如此而言之后构建的线性方程组的稀疏性是最强的。定义：1∑L(vi)=vivj(2-1)dij∈Ni为点i的Laplacian坐标。其表示了点i相对于其1-邻域内的其他点的重心的偏移量，如图2.1：9 中国科学技术大学本科毕业论文图2.1:Laplacian坐标，即邻域中其他点到该点的向量定义Laplacian坐标为点i相对于其1-邻域内的其他点的重心的偏移量可以在下面的形状变形过程中保持局部细节变化的均匀性，以不至于使Laplacian坐标变换无意义化。如果改变定义中的权1为其他值会导致细节部分在平移、di旋转、放缩方面产生特异的变化，但只要不存在对于邻域中每个点过大过小的情况，则并不影响接下来所提出的Laplacian编辑本身的有效性。2.2Laplacian编辑对于三维模型的形状变形，我们探讨一种比较常见的方式。首先给定一个网格，在网格上选定某一部分作为选定区域，通过控制一部分点的变换来控制整个选定区域进行变换。如图1-2所示，将章鱼的一条触须选定，通过拖拽触须上的一部分点来控制整条触须变形。这一形状变形的过程，我们先要选定区域，然后在其上选择一部分点作为参照点，对其进行坐标变换并固定。定义交互区域中所有点完成变换之后的坐标的集合为：′′′V=fv1;:::;vng其中选为参照点，率先完成坐标变换并被固定的点为：′vi=ui;i2fm;:::;ng;m