计算机辅助设计几何课程论文

基于三角网格的网格变形综述作者：谢育钢学号：1400203026摘要：网格变形作为一种几何模型交互编辑技术在几何建模和计算机动画中具有重要价值。近年来，网格变形技术得到了国内外研究者的极大关注,且在逆向工程、模拟仿真、工业品创新设计及计算机动画等领域得到了广泛应用。模型表面的细节信息是模型特征的一个重要内容，在网格变形中需要保持这些信息的局部不变性，变形才能有效，符合实际效果。从骨骼变形、曲面变形、空间变形3个方面对各种经典的网格变形算法进行描述和比较，并提出结论。关键词：网格变形Laplacian坐标空间变形梯度场引言网格变形是通过用户输入编辑操作，几何模型发生相应修改的几何处理技术。随着3D扫描技术的发展，复杂形状的网格曲面模型相关技术的研究已成为曲面编辑的主流，其在CAGD(计算机辅助几何设计)领域，具有广泛的应用。现代工业的快速发展，基于传统规则形状特征(平面和二次曲面表示的曲面)不能满足现代工业在功能及外形上的需求，自由曲面形状特征的应用在产品设计日益广泛与深入。利用自由形状特征，设计师可以设计出各种复杂多样的品模型，以满足现代工业的设计要求。显然，自由形状特征更加复杂的几何元素，更多的自由度等特点，并且实现模型的建模与处理遇到困难。然而，目前游戏动画领域已积累了大量的三维数字化模型，利用现有的模型重通过变形处理新编辑出新的模型将大大提高设计师的建模效率，从而设计复杂的模型，提高工作率。实现自由形状特征的设计重用具有重要的意义。从早期的自由曲面变形（FFD）、骨骼蒙皮变形、到近年来流行的微分域(differentialdomain)网格变形，国内外研究人员不断提出新的有效的网格变形算法并将网格变形技术应用到各种应用问题中。文献[1,2]对基于拉普拉斯(Laplacian)变形为主的梯度域网格变形从变形能量的相关性分析和细节保持性等角度进行了较为系统的综述。本文进一步对其他变形技术，如自由曲面变形，骨骼蒙皮变形研究进行分析，以助对网格变形处理技术更深一步的理解及研究。1基于骨骼的蒙皮变形蒙皮是一种基于局部操作的表面变形算法,该方法可以通过图形化界面为每个皮肤顶点指定对应的骨骼以及对应的权重。“蒙皮”算法速度较快,但是在指定权重时需要动画师具有一定的经验。“蒙皮”方法本质上是一种插值算法,其基本原理可以用下式表示:11niiiivMDv11nii（1-1）其中,v是变形前的皮肤顶点坐标,iM表示在初始参考姿态下与皮肤顶点相关的第i段骨骼的由局部坐标到全局坐标的转换矩阵,1iDv表示在第i段骨骼局部坐标系中皮肤顶点的坐标值,i表示第i段骨骼对于当前顶点的权值,v表示变形后的皮肤顶点坐标。“蒙皮”算法的基本思想是使关节附近的皮肤顶点同时受到与关节相邻的两段骨骼的影响,影响的大小由权值i确定。早在1972年，Catmull[3]就提出骨骼驱动的动画技术。1988年，Thalmann[4]提出基于定制函数的3维骨骼蒙皮技术将皮肤的运动看成潜在骨骼的函数。关节依赖的局部变形是最早的骨架驱动的皮肤变形方法，又称骨架子空间变形（SSD）。SSD技术可以由以下公式表达：1sijjijvwtv（1-2）其中,iivv分别表示变形前后的网格顶点，下标j表示骨架上第j个控制单元所对应的量，s代表骨架上的控制单元个数，jt代表作用于该控制单元的局部变换，可以由用户输入，也可以从运动捕获等途径输入，ijw是加权权重，表示骨架对网格顶点的影响程度。SSD计算速度快，但变形效果受加权权重ijw的影响，常常会出现几何丢失的情况。针对SSD方法的缺点,Lewis等综合SSD方法和形状插值提出了一种统一的皮肤变形方法,称为姿态空间变形（PSD）方法[5]。PSD方法能有效地对SSD方法变形效果进行修正，可以模拟肌肉凸起以及皮肤折皱的效果,这是SSD等光滑皮肤变形方法无法企及的。Wang等人改进公式(1.1)中的权值[6],对权值的维度进行了扩展,由一个标量扩展为通过拟合用户给定的样本得到的12个权值。Ladislav等人通过改进式(1.1)中的线性插值计算方法[7],将局部变换用球形线性变换替换,得到了更好的变形效果。2基于曲面的网格变形2.1基于多分辨率多分辨率变形算法[8]是一种经典的变形算法。该算法，先把原网格分解成低频信号和若干个高频信号网格。低频信号网格相当于网格的底层光滑模型，而高频信号网格相当于模型上的细节信息。通过多分辨率算法变形，实质上是先对低频信号网格（也叫基网格）进行变形，然后将高频信号网格的细节信息重新整合在变形后的基网格上，达到最终的变形。高频网格的层数越多，模型变形后的局部细节信息就越精确。当然也会导致更多的储存数据，使得整个变形处理花销更大。图1图1是多分辨率变形方法的算法框架图。分析可知，多分辨率变形方法实质上是线性变形方法与多层次分解方法的结合。多分辨率变形算法的鲁棒性不够，在大角度或其他特殊变形时候，变形结果不稳定，即变形不自然。主要是由于把局部信息分层来表示模型细节，网格变形是对基网格，而不是整个网格，最终的变形是间接实现，在后来的细节还原时候就会导致不连续，不自然。此外，当分层过多时候，明显增加数据的存储量，必然导致最终实现的延迟，不能很好的实现实时编辑。2.2基于微分坐标基于微分坐标的变形技术是用微分坐标（也叫拉普拉斯坐标）表示模型的局部细节，在满足用户约束的条件下使模型编辑尽可能多的保持这些反应几何细节的微分坐标。整个变形过程，主要分为两部分：编码和解码。编码是指把欧式空间中的网格顶点的坐标转换到微分域的拉普拉斯坐标。拉普拉斯坐标本质上将模型曲面的局部细节保存起来，再进行变形。解码过程是通过拉普拉斯坐标反求顶点在欧式空间中的坐标，这过程通过求解一个稀疏线性系统来实现。2.2.1离散拉普拉斯坐标给定具有n个顶点的三角网格模型()MV,E,F,V为顶点集，E为边集，F为三角面片集合。设1,nvv为点集V中的点，对于每个顶点iv，用传统的笛卡尔坐标表示，记()iiiivx,y,z；用(){()}Nij/i,jE，表示第i点的1-ring邻域顶点构成的集合，如图2.1，定义iv处的拉普拉斯坐标为：(i)()iiiijjjNL(2-1)i(i)1()ijjNd1()()idl图2均匀权微分坐标和曲面的局部特征近似其中,i为顶点iv的拉普拉斯坐标，()L为网格的拉普拉斯算子，ij为jv点相对于iv点的权值，且1ij。关于权值的计算方法很多，如均匀权值[9]、余切权值[10]、正切权值、弹簧权值等。本文只简单介绍权均匀权值、余切权值。(1)均匀权值计算公式：1ijid(2-2)其中，id为顶点i的度(邻接顶点的个数)，由于这种权值只是简单的平均，故又称为均匀权值。这种权重直接采用均匀权，与顶点邻接三角面片的信息无关，往往不能满足精度要求。(2)余切权值计算公式：cotcot2ijijij(2-3)其中,ij、ij是边i、j的两个邻接三角面片的对角，如图2.2所示。图3余切权值网格变形归结为如下位置约束的优化问题：2211min(||()||||||)immiiiiiipq(2-4)方程经过化简，最终只需求解如下方程问题：LAVVbHh(2-5)求解以上稀疏线性系统既可以求出变形后的顶点的坐标，重新拟合成曲面，既可以实现变形操作。由于拉普拉斯坐标只具有平移和比例不变性，不具有旋转不变性（旋转后法失方向发生改变，导致重构曲面时候受到影响），容易发生扭曲变形。围绕拉普拉斯变形的许多研究工作集中于如何更好地逼近未知的拉普拉斯坐标，特别是处理拉普拉斯坐标的旋转问题Lipman[11]通过估计曲面的局部旋转的方式重建变形曲面，即先基于原始拉普拉斯坐标计算变形网格，基于变形网格求解每个顶点的局部旋转并用该局部旋转对最原始拉普拉斯坐标进行变换，再根据新拉普拉斯坐标重新求解变形网格。Zayer[12]则沿调和场传播句柄变换以更新拉普拉斯坐标。Zhou[13]将拉普拉斯操作从曲面扩展到其内部，用所谓的体拉普拉斯坐标表示几何细节，采用Wire[14]的交互变形技术对由网格顶点构成的3维投影控制曲线变形，并将控制曲线变换传播到所有网格顶点以更新体拉普拉斯坐标，求解类似的优化问题得到变形网格，可以避免体积的不自然变化和局部自交。Lipman[15]提出基于局部坐标架的离散形表示几何细节，相邻顶点的局部坐标架的差可用其中一个顶点的坐标架表示:1111112213jiijiijiijibbbbN2221122223jiijiijiijibbbbN（2-6）31132233jiijiijiijiNNbbN式中，系数ijkl由原始网格的离散形确定，相邻顶点构成的边向量也可用其中一个顶点的局部坐标架表示:11223ijiijiijijibbN,ijE（2-7）式中系数ijk可由原始网格的离散形和局部坐标架矢量决定。当用户交互指定句柄顶点及其旋转变换后，通过两步的稀疏线性系统的求解依次确定顶点的局部坐标架和变形后的顶点坐标。该方法虽然能健壮地产生高质量的变形结果，但需要用户指定句柄的旋转变换，给使用者带来了不变，限制了该方法的应用特别是不适用于那些非交互的网格变形应用。2.3基于梯度域除了这些使用Laplacian坐标来表示网格,并以此控制网格变形的方法之外,还有以网格梯度场来表示的网格变形。Yu等人受到二维图像上的Poisson编辑[16]的启发,在网格曲面上建立起三角形的梯度,要求变形后的三角形梯度的散度变化最小,从而得到Poisson方程,通过解此方程得到变形后网格的新顶[17]。Xu等人将墓于Poisson的三角网格梯度场的变形方法进行更深入的研究[18]。Summer等人利用变形梯度来复制网格变形及基于网格的逆向运动学变形,他们将网格上的三角形通过新增一沿法向量的虚拟顶点扩展为四面体,然后以四面体变形前后的局部变换作为变形梯度来表示网格的变形。可以证明基于三角形梯度场及变形复制的变形梯度在理论上是等价的[19]。基于梯度场的网格变形技术,与基于Laplacian坐标的网格变形技术一样都是操作网格模型微分属性的变形技术,因此对于梯度场也需要估算其局部变换。前述的基于测地线、调和场等方法同样适用于基于梯度场的局部变换计算。2.3.1网格上的标量场在网格M上任意顶点i处取值()iiff，且在M上任意其它点v处取值为()()iiiff，其中()i是分段线性基函数，在顶点i处取值为1，其他顶点()iji处取值为0。们称函数f为定义在域网格侧上的标量场。显然,域网格M的顶点坐标的三个分量可视为定义在其自身之上的特殊标量场。2.3.2矢量场分解Hemlhotlz-Hdoge矢量场分解定理[3][20]深刻刻画了矢量场的内在性质,该定理被认为是上个世纪最重要的数学发现之一。这个定理描述的是位于任意区域几内的光滑矢量场w可以分解为三个组成部分:wvh（2-8）其中是一个满足()0的标量势场,v是一个满足()0的矢量势场,h是一个满足0h和0h的矢量场。、v和h这三个分量又分别称为无旋(CuriFree)分量、无散(DivergenceFree)分量和调和(Harmonic)分量。2.3.3梯度算子离散梯度算子的定义依赖于域网格一上的分段线性基函数的梯度()iv,在此基础上,我们定义域网格M上的标量场f在任意一点M处的梯度为:(v)(v)iiiff（2-9）在域网格M上的任意三角面片012(,,)Tvvv内任意点v处,其三个顶点处的分段线性基函数0、1和2的数值等价于v点相对于三个顶点的重心坐标分量。顶点0v处的基函数0的梯度向量：900211(vv)2TRA（2-10