数字几何图形网格变形理论和方法

摘要

近年来动画制作、视频游戏、计算机辅助几何设计等应用领域飞速发展，对数字几何图形网格模型的编辑方法提出了更高要求。人们希望用简单、直接的人机界面交互方式，快速获得符合直觉的网格变形效果。传统的骨架变形、自由变形(FFD)和多分辨编辑等方法有着各自的局限性，已经日益不能满足这种需求。由此，过去几年出现了基于最小二乘形式的非精确网格变形技术。这种方法用若干特征函数或约束函数描述网格的几何特征，并按最小二乘的形式求得这些特征函数的最优值，从而获得光滑的大尺度变形效果。由于交互式操作要求网格变形算法具有较快的求解速度，这就需要尽量用线性的特征函数构造最小二乘方程。但是现有方法必须采用迭代或者非线性的方式实现平移敏感等复杂变形效果，不能同时满足效率和效果要求，这是网格变形领域的难题之一。 针对这种需求，本文从理论和方法两个角度对大尺度网格变形问题进行讨论，提出新的观点和处理办法，主要包括以下几点： 第一，本文根据微分几何曲线和曲面论的活动标架原理，提出采用局部标架描述相邻几何特征的微分网格表示方法，指出相邻标架的仿射关系和相邻顶点的局部坐标是离散网格的内在几何不变量之一，是刚体运动无关的局部几何特征描述方式。结合最小二乘形式的优化计算，可使变形前后的网格在全局上具有相似的几何特征，实现平移敏感等复杂变形效果。 第二，为解决求解效率和变形效果的矛盾，本文提出一种基于局部标架的线性约束网格变形算法，通过一步求解线性方程组，获得图像和二维图形的平移敏感变形效果。本文提出采用局部标架描述相邻的网格特征，构造直角邻边之间的线性坐标分量约束关系，结合边界约束顶点位置，构造线性约束方程组。本方法用线性方式描述非仿射变形，步骤简洁，操作简单，效果较好。 第三，本文进一步提出一种基于曲线匹配的勾画式网格编辑方法。用户通过勾画出变形前后的控制曲线形状，生成一系列边界约束顶点及其新位置，控制网格的大尺度变形。本文分析了曲线对齐问题基本原理，指出必须根据大范围和局部的显著几何特征匹配曲线子段，阐述了一种基于多分辨分析的曲线对齐算法，让用户可以便捷地控制图像或二维图形网格的变形。 最后，本文还分析了传统Laplacian网格变形算法的不足，提出一种迭代编辑方法，通过不断修正中间网格的平均曲率法向量，更新最小二乘方程组的约束关系，计算新的顶点位置，实现三维网格的平移敏感、扭曲、弯曲等复杂变形效果。 本文的主要创新点包括： (1)本文提出标架和顶点的局部关系是离散网格的内在几何不变量，能在刚体变形中保持网格的局部几何特征。 (2)本文提出基于仿射和角度约束的线性网格变形新方法，实现了平移敏感等大尺度的非仿射变形效果，基本解决了图像和二维图形非刚体变形的速度和效果矛盾。 (3)本文提出了基于显著几何特征的曲线匹配算法，用于网格的勾画式编辑，简化了用户控制网格变形的操作。大量的实验说明，本文理论基本正确，方法有效、实用。

目录

文摘

英文文摘

声明

第1章综述

1.1数字几何模型的获取和编辑方法

1.2传统网格编辑方法和不足

1.3最小二乘网格变形方法

1.4本文研究内容

1.5本文章节安排

第2章局部几何特征的表示和求解

2.1网格的局部几何特征

2.2网格局部特征的表示

2.3基于最小二乘的局部特征全局优化

2.4线性方程组的数值解法

2.5本章小结

第3章线性约束网格变形方法

3.1图像和网格变形的需求及难题

3.2网格变形研究背景

3.3线性约束网格变形

3.4基于局部坐标的网格变形方法

3.5算法实现

3.6实验结果

3.7本章小结

第4章基于曲线匹配的勾画式网格编辑

4.1勾画式编辑方法

4.2曲线对齐的相关背景

4.3多分辨率曲线对齐算法

4.4曲线匹配实验结果

4.5勾画式网格编辑框架

4.6本章小结

第5章Laplacian迭代变形方法

5.1局部平均曲率法向量的表示

5.2基于Laplacian向量的迭代变形算法

5.3实验结果

5.4讨论与本章小结

第6章总结与展望

6.1研究成果

6.2将来的工作

参考文献

攻博期间论文和科研情况

致谢