数学专业毕业论文-保体积的曲面变形技术研究

保体积的 曲面 变形技术 研究 摘 要 三维 网格曲面变形 作为三维造型的一种新兴手段 在商业、制造业、建筑业、教育、医学、娱乐、艺术领域有着广泛的应用，已成为计算机图形学领域十分活跃的一个研究热点。 通过对 三维网格曲面进行四面体剖分，得到曲面的内部 “ 体 ” 结构，然后 基于 四面体网格进行 编辑 ，从而维持三维模型的 “ 体细节 ”， 是本文的主要研究内容 。 首先， 利用 ILSD 度量 衡量四面体网格的形变程度， 将 极小化形变能量 问题 转化为无约束非线性优化问题。采用带 Armijo 线性搜索的非精确牛顿法求解最优化问题 ， 并利用控制顶点的位置预估 未知 顶点 的位置作为迭代的初值， 以减少迭代次数、 提高求解速率。然后， 对三维模型表面以及模型内部顶点分别定义了 Laplacian Coordinate， 在 保持三维模型表面几何细节 的 同时 ，保持模型内部的体细节。求解变形后顶点位置 的问题是 一个二次能量最小化问题， 其在 最小二乘法 意义下的解 即 为 对 法方程稀疏矩阵求解 的结果 ，并采用 LU 预分解技术加快求解速率。 本文将两者结合，进一步研究了保体积 的 Laplacian 网格编辑技术 。为了严格保证变形后 网格 不发生翻转， 增加约束将 原 无约束优化问题转化为约束优化问题，采用内点惩罚函数法进行求解。 并 应用此方法模拟实际应用中夹持器托起释放物体的形变过程，变形 后 网格质量高、效果自然，能够满足进一步研究材料、受力分布的需求。 关键词：网格 变形，四面体网格，最小缩放形变度量， Laplacian Coordinate，非线性优化 Volume-Preserving Surface Deformation Author: Su Jian-ping Tutor: Liu Jian-bo ABSTRACT 3D mesh surface deformation as a new means of 3D modeling has become a research hot spot of computer graphics, since it is widely used in commercial, manufacturing, construction, education, medicine, entertainment, art and other fields. This article gets the internal structure of surface through subdividing the mesh surface into tetrahedral meshes, then surface deformation is based on tetrahedral meshes, which could maintain the “volumetric details”. At first, use improved least scaling distortion metric to measure the distortion for tetrahedral meshes. Base on this metric, minimization deformation energy is an unconstrained non-linear optimization solution, which can be performed by using inexact Newton method with an Armijo line search method. Unknown vertices is Estimated by the controlled vertices, which could reduce the iterations and accelerate the solving speed. Then, respectively define Laplacian coordinates on model surface vertices and internal vertices, which could keep the details within model body while maintaining model surface geometric details. Volumetric detail preservation is represented by a quadric energy function. It can be efficiently minimized by solving a sparse linear system in a least-squares sense, at the same time using LU precomputed decomposition technology to enhance the efficiency of algorithm. This thesis combines the two methods, and further study the as-volumetric-as-possible Laplacian mesh editing technology. In order to ensure there is not one tetrahedron element flipping, unconstrained optimization problem is added constraints and translates into a constrained optimization problem. Interior point penalty function method is adopted to solve it. This method is applied to simulate the process of holder picking up and releasing object. By experiment, deformation effect is natural and meshes is high quality, which could meet the needs of further research of material and force distribution. Key Words: Mesh Deformation, Tetrahedral Mesh, Least Scaling Distortion Metric, Laplacian Coordinate, Non-linear Optimization 目 录 1 绪论 1 1.1 研究背景及意义 . 1 1.2 研究内容与现状 . 2 1.3 本文结构安排 . 3 2 基于形变能量极小的体网格变形技术 5 2.1 四面体网格形变度量 . 5 2.2 形变能量极小的最优化问题 . 7 2.2.1 最优化问题 7 2.2.2 数值计算 8 2.3 实验结果 . 11 3 基于局部细节保持的体网格变形技术 13 3.1 四面体网格的 拉普拉斯 算子 . 13 3.1.1 表面网格的 Laplacian 坐标 13 3.1.2 网格内部的 Laplacian 坐标 15 3.2 Laplacian 形变算法框架 15 3.3 实验结果 . 19 4 基于体积约束的体网格变形技术 21 4.1 算法概要 . 21 4.2 体积约束及其能量形式 . 22 4.2.1 网格质量约束 22 4.2.2 形变能量极小约束 22 4.3 约束优化问题求解 . 23 4.4 比较与分析 . 24 结 论 27 致 谢 28 参考文献 29 附 录 A . 31 1 绪论 1.1 研究背景及意义 曲面 变形技术是 三维模型编辑中的一 门 新兴 学科，其 最早 雏形 是计算机辅助几何设计 （ Computer Aided Geometric Design， CAGD） 中的自由曲线曲面造型技术 。 自由 曲线曲面造型技术是一门 多领域交叉的学科，其 综合了 数值计算的 散乱数据点插值以及 代数曲线曲面的 形状 匹配 、重建、变形和简化 等。三维模型的直接外观形式就是其外表面，使用 计算机离散系统环境 难以 对连续曲面进行 表示 ， 因此 通常 采用分段线性逼近的方法将连续曲面离散化为多边形网格，参见图 1.1 所示为三 角网格表示曲面的形式，这样对曲面的编辑可以转化为对 三角 网格的操作。 图 1.1 曲面的离散化表示 三维网格曲面变形 是 三维造型的一种手段， 在 商品 生产 、 机械设计 、 房屋 构造、教学科研 、 医疗设备 、 影视动画 、艺术 造型等 领域 中 被 大量应 用 ，长期以来 吸引 了 众多的学者不断研究 ， 现 已成为计算机图形学 （ Computer Graphics， CG） 领域 备受关注的课题方向 。 例 如 三维建模、三维电脑游戏、虚拟网络 商城、各种运动 仿真 模拟等领域 均 是一些具体的 实际应用 ， 尤其 地，三维网格 变形技术 在 计算机 动画 人物 造型和电子艺术作品造型 制作中不断展现出重要的作用 及 广阔的 发展前景 。 在动画设计人员进行动画 角色 创作时，希望 能够生动形象自然地展现出虚拟角色的动态形象 ，这 激励着 广大研究人士 不断创新，改善 原来效果生硬呆板的角色动画技术 。例如将原三维图形与形变后的三维图形进行插值便可以得到一系列中间图形，这样便可产生生动连续的动画效果， 因此 网格变形与编辑这一新兴领域在 最近几年 被逐渐开创 。 1.2 研究内容与现状 目前已经有许多优秀的算法，可以实现 简单 地 交互 编辑 并且产生 生动 逼真 的 编辑 效果 。 特别 是多分辨率技术与近些年来 飞速发展的 微分域 变形技术 ， 它能够 产生视觉上自然的变形效果， 在保持 模型 表面几何细节方面获得了 巨大的成功 。 Laplacian 网格编辑技术是一种 基于微分域 表达 的 网格 编辑技术 ， 因 其 算法 速度快 、鲁棒性好 、 交互 简便已经受到了 广大 研究人士的青睐 。 并且在实际应用中被广泛使用 ， 极具发展潜质 成为 当前 一门非常受欢迎 的三维网格 处理技术 。 基于微分域的网格曲面变形方法 旨在保持曲面的局部微分量， 算法主要为 优化相应的变形能量函数 ，顶点拉普拉斯坐标 （ Laplacian Coordinate， LC） 是其中一个重要的局部微分量 。 连 续光滑曲面上的 Laplace 算子 能很好 地 反 应曲面的局部细节，应用于网格曲面 则 需 将其离散表示 ， 一个顶点的 Laplacian Coordinate 可以 表示为 与其一阶领域点 所连成的边对应的向量 的 加权求和 。 应用 Laplacian Coordinate， Sorkine 等人 1提出了 一种维持 Laplacian Coordinate 的网格变形算法，它 能够 很好 地 保持 表面 的局部 细节特点 。为了克服 Laplacian Coordinate 不具有旋转不变 性 的弱点， Lipman 等人 2提 出了在网格 变形中 局部交互控制和 Laplacian Coordinate 的关系， 使得 Laplacian Coordinate 是线性旋转不变坐标， 此方法 采用了 离散微分几何第一和第二基本形式。 Yu 等人 3则使用另外一种局部微分量 梯度， 通过 泊松 方法 构建 网格 的 梯度域 ，与 Laplacian 网格编辑技术类似，为达到 平滑形变误差保持局 部细节的效果 ，在变形过程中保持局部微分量 ，充 分 利用 泊松 方程在 曲面 编辑 中 的 价值 。 然而 ， 目前 研究的曲面变形方法大多 考虑 怎样维 持模型表面的 细节， 却 忽略了模型的其他几何属性，如体积、边长等。 这些属性 是 非线性 几何量 ， 通常没有精确的求解方法 ，使得 模型在变形 程度较大时往往会产生不切合实际的变形结果 。因此对于大变形的情况，这些方法往往不能满足需求。其原因在于这些方法 虽然 保持了模型表面的几何细节 ，但缺乏 “体” 的约束 导致模型内部的 信息丢失 ， 可能造成内部 体积 严重塌陷或是反常膨胀 。 Sorkine 等人 4接着又 提出 了 尽可能 刚性的 3 维 网格曲面 形变算法 。他们为 网格 曲面上的每 一个 顶 点 建立一个局部标架 ， 在形变过程中 顶点 的 Laplacian Coordinate 在局部标架中的 坐标 表示 不变 ， 即 局部标架 是 顶点 的局部刚性区域 。同样 与 Laplacian 网格编辑一致 ， 在变形过程中 ， 构建 形变能量函数 ， 通过 求解最优化问题 来维持 模型表面 的几何细节 。 可是 ， 这些 算法仅 关注 模型表面的性质 ， 没有考虑模型 内部的结构，因此 在大尺度变形情况下 模型可能 会产生 明显的体积变化以及严重的 细节扭曲 。 Song 等人 5提出一种 度量方法来衡量每一个四面体网格 元素 的变形程度，称为 最小缩放形变度量 （ Least Scaling Distortion， LSD） 。 LSD 具有防止四面体网格发生翻转与尽可能维持四面体体积不变的性质， 因而 以此 度量 构造 的 形变能量函数，通过极 小化能量函数 的方式能够 实 现网格的 保体积 变形 。但是由于 LSD 度量的高度非线性，在求解优化问题时需耗费较多的时间，不能实现实时性。 Zhou 等人 6把 Laplacian Coordinate 从网格表面推广到体，定义模型表面及内部的 Laplacian Coordinate， 提出 了 基于体图的网格大变形方法 。 为 三 维模型建立相应的体图 ，通过体图计算 模型 表面以及内部的局部微分量，维持局部微分量以实现 网格表面以及内部的细节 保持， 有效 避免 了 模型在大尺度变形时体积 发生显著的变化。但是， 该方法首先需要 为 网格曲面 建立与之相匹配的 体图 ， 这为 计算 模型 变形后的 顶点位置 增加了难度 。而 且 表示 体图的 几何 单 元 不唯一 ，这使得难以 计算网格模型 当前 的体积 ，因而 模型变形时 体积变化 难以 被 精确 控制。 1.3 本文结构安排 本文主要讨论将三维网格曲面进行四面体剖分，得到曲面的内部体结构，然后 基于四面体网格进行 模型 变形操作， 同时 维持三维模型的 “ 体细节 ” 。 第 一 章 为绪论。 阐述课题 研究 的 背景及意义， 引入离散网格曲面的定义 ， 探讨 变形方法 的 研究 现状， 介绍 文章的 结构安排以及 主要研究内容 。 第二章 提出基于 极小化 形变能量 的 体网格变形 方法 。 将 ILSD 作为 衡量四面体网格变形 程度 的 度量 方法 ，极小化 目标函数 即 形变能量 最小 ， 实际上为 一个 带约束 的 非 线性优化问题 （ Constrained Nonlinear Optimization Problem， CNOP） 。选定合适的初值 后 可以 将其简化为一个 无约束非线性优化问题 （ Unconstrained Nonlinear Optimization Problem， UCNOP） ，采用带 Armijo 线性搜索的非精确牛顿法求解最优化问题。 第三章 改进现有的微分域形变方法，将 Laplacian 网格编辑技术从 多边形 网格表面拓展到 四面体网格实体 。对三维模型表面以及模型内部顶点分别定义 局部微分量Laplacian Coordinate，在形变过程中保持 局部微分量 不变，这样在保持三维模型表面几何细节的同时，保持模型内部的体细节。 第四章提出保体积的曲面变形方法 ，并模拟实际生产中夹持器夹起释放物体的形变过程 。 比较极小化形变能量以及 Laplacian 网格编辑技术这两种方法， 将两者结合 进一步研究了保体积的 Laplacian 网格编辑技术。为了严格保证变形后网格不发生翻转，在原无约束优化问题的基础上增加防止翻转约束 ，将无约束问题转化为约束优化问题 。 2 基于 形变能量极小 的体网格 变形技术 三角网格模型记为 ( , )M V K ， 表示一个二维 流行 曲面。其中 3 |1iV p R i n 为网格顶点的坐标， K 表示该网格的顶点连接关系，包含顶点 i ，边 ,ij ，面 ,i j k等基本元素。将此曲面 M 生成的四面体网格表示为 ,G PE ，其中 3 |1iP p R i N 是顶点位置， ,|ijE i j p p 与 相 连表示边的集合。 2.1 四面体网格 形变 度量 任 意 四面体 元素 e 由四个顶点 1 2 3 4, , ,p p p p 构成，如图 2.1 中左图所示 。定义四面体 元素 e 的关联矩阵 33AR 为： 2 1 3 1 4 1: , , .A e p p p p p p 易知关联矩阵 可以通过四面体 元素 的三条有向边 12pp ， 13pp 和 14pp ，形成一个 33的方阵 。 四面体 元素 e 的体积即为 1 det6 Ae，体积 为 正 时 四面体 网格 元素 顶点的排列 次序 为 正 向 ，为负时则顶点排列 次序 是 逆向。本文假定已给数据所 有 四面体网格元素的 顶点 排列次序 均为正向 ，这样 按照体积计算公式 所有 元素 e 的体积均大于零 ，每一个1Ae 均存在。 图 2.1 四面体 元素 e 形变为 e 对于两个任给的四面体 元素 e 和 e ，如果两者的体积均不为零，即 Ae 行列式不为零可逆，则可定义线性映射 :f e e ， 如图 2.1 所示 ，映射 f 的雅克比矩阵为： 1 .J e A e A e 线性变换 f 衡量了四面体 元素 e 到 e 的形变程度，如果两个四面体 元素 e 和 e 有相似的形状，也就是说边长对应成比例时， 即 对某一 0 有 ： 东北大学秦皇岛分校毕业设计（论文） 第 6 页 21213,3,de t .FA e A eA e A eA e A e矩阵 J 的奇异值反应了四面体体积的缩放程度， Zhou 等人 7基于此 提出 体拉伸度量的概念 ， 它反应了网格的 伸缩程度 ： 2221 2 32 1( ) ,33 FL J J (2.1) 其中 TFJ tr J J是 Frobenius 范数， 1 2 3, 是矩阵 J 的奇异值 ，这种拉伸度量主要应用于纹理映射方面以其 2D 形式。 由公式 （ 2.1） 可以 显然 得到 ， 体拉伸 度量 是旋转、平移不变量 ，但是 随着四面体 网格 元素 的缩放 而变化 。 尽管 能够 很好的维持体积不变 ，但 与此同时翻 转现象发生频率高 ，不能较好 维持四面体 元素原有的 性质 。 为了 防止四面体网格 元素 发生翻转 尽可能保持网格 元素 的体积， Song 等人 5综合以往的网格 变形程度 度量方法，提出了最小缩放形变度量，此度量方法能够使得变形后的元素 具有较好的保体积性，并且不发生翻转。 22 13( ) ( )( ) : .2 d e t( ) 2 d e t( )s L J L JLJ J J 如果 元素 e 与其 形变 后的 e 体积都不等于零， 且 变形前后两元素相似 ，即 A e A e ， 0 为常量，那么 11() 2sLJ 。当 1 时， ()sLJ达到最小值，这就意味着 LSD 度量值依赖于体积伸缩，因此在变形过程中四面体的体积将尽可能维持不变。 LSD 度量值的范围是 1, ，当 元素 e 与其变形后的 元素 e 不相似时 ， ( ) 1sLJ 。因此对于 任意 网格 元素 e ， 最小缩放形变 度量 不随 旋转、平移 变化 ， 随 缩放 变化 。 如果直接采用 LSD 度量作为能量 项 构建目标函数，会为最优化问题的求解增加困难。 因为 牛顿 下降 法求解最优化问题 时 需要计算目标函数的梯度以及 海塞 矩阵，然而最小缩放形变度量 LSD 中的 2()LJ二阶偏导计算困难，不仅无精确的解析表达式，也不能采用离散化的方式。 因此 本文 按 采用 崇金山 8 提出的改进 最小缩放度量 （ Improved Least Scaling Distortion Metric， ILSD）： 东北大学秦皇岛分校毕业设计（论文） 第 7 页 22 13( ) ( )( ) : .2 d e t( ) 2 d e t( )s L J L JLJ J J 方便求解目标函数的一阶 、 二阶偏导，这样在利用牛顿法求解最优化问题时能够高效精确计算出目标函数梯度以及 海塞 矩阵。 2.2 形变 能量极小 的最优化问题 2.2.1 最优化问题 如图 2.2 所示的简单四面体网格模型 G ，其中顶点 P 有两种类型 ，即 未约束点 uP 和约束点 cP ，而约束点 cP 又分为 控制点 hP 和 固定点 fP ，本文中的未约束点称为 未知点 或可动点 。 图 2.2 简单四面体网格模型顶点分类 操作 控制点 hP 平移或旋转驱动 模型 xG 变形到 yG ， 建立 变形 对应关系 为 ：: xyF G G ， 模型中的所有 元素 ixeG 都相应的变形为 iyeG ，且 元素 ie 的变形映射可表示为雅克比矩阵 1i i iJ A e A e 。在形变过程中，固定点 fP 位置不变，控制点 hP 的新位置作为已知点，这些点作为约束点 cP ，而其他的点作为未约束点 uP ，通过最小化整个网格模型的平均 ILSD 度量值进行求解。 1m i n ( ) ( ) ,y xs s eG eGxL F L J eG (2.2) . . d e t 0 , e ,exs t J G (2.3) , ,iip p i C (2.4) 东北大学秦皇岛分校毕业设计（论文） 第 8 页 其中 e 表示四面体 元素 e 的体积， xG 表示整个四面体网格模型 xG 的体积之和 ， ip 属于约束点 cp ， C 是约束点的索引集合。目标函数式 （ 2.2） 极小化整个模型的变形程度，从而使得 变形后模型 体积 尽量 不变。 为了 使得目标函数极小 ， 需要 所有 元素 的顶点 排列次序 一致， 不等式 约束条件 式 （ 2.3） 就能确保结果四面体网格 元素 顶点 与 原 网格 元素 顶点 绕向一致，这样可以防止网格 元素 变形后 存在翻转现象 。 在三角形和四面体网格质量最优化 时 ， 一个类似的优化问题 同样被构造， 与本文度量方法 所不同的是 Munson9采用的是反平均比率度量 （ Inverse mean ratio metric， IMR） 。但是由于 IMR 度量具有伸缩不变性且为无量纲值， 使得它无法应用到网格编辑中，因此也不适用于本文系统中。 在构造最优化问题时引入了严格不等式 （ 2.3） ，这是 为了保证变形过程中四面体网格 不发生翻转 ， 但 与此同时为 问题的求解 增加 一定的难度。 四面体网格模型 G 中的 元素e 相互连接， 由 式 （ 2.2） 能够 得 到 ，当存在 某个 网格 元素 趋近于零时，其所对应的雅克比矩阵 J 行列式 det( )J 无限接近于零，则目标函数 ()sLF值趋于无穷大，这在目标函数最小化的迭代过程中是不可能发生的 。因此条件 式（ 2.3） 能够 舍去 ， 因此 2.2.1 节 里 的CNOP 化 可以 化简 为 UCNOP， 1m i n ( ) ( ) ,. . , .y xs s eGeGxiiL F L J eGs t p p i C (2.5) 在 初始体积均为正值的条件下，一旦出现网格 元素 体积由正变为负 的情况 ，都会导致目标函数值无穷大。这 便限制 在 解决 UCNOP 时，赋予的初值必须满足 所有网格 元素的顶点排列次序为 正向 。本文所采用的四面体网格数据，均是由 Tetgen10网格剖分软件生成得到，它能够产生 遵守德洛内规则 （ Delaunay Rules） 的四面体网格 ，同时保证 *.ele文件中的四面体网格 元素 的顶点按照右手规则进行排列 ，因此读入内存中的初值不会出现 det( ) 0J 的情况。 2.2.2 数值计算 现在已经 将四面体网格变形问题公式化为式 （ 2.5） 的最优化问题， 本文采用非精确牛顿法 11以及 Armijo12线性搜索方法进行求解， Netwon 法 求解最优化问题需要建立东北大学秦皇岛分校毕业设计（论文） 第 9 页 Netwon 方程 ，方程系数矩阵为 海塞矩阵，非齐 次 项为梯度。 下面介绍如何计算梯度以及海塞矩阵 。 建立矩阵 A 和 B 的内积 关系 ： ,.TA B tr A B (2.6) 则 矩阵 B 的 F 范数即 为 ,FB B B， 对于任意网格顶点 p 有三个 坐标 分量 ， 用 符号 和 分别代表其中之一 ， 用 表示目标 函数 sLF对 分量的导数 ，这样 R 即为一个n 阶方阵 ,1 ,ijR r i j n 对分量 的一阶偏导。 设顶点 p 的领接四面体集合为 |T p e p e， 将 四面体网格 元素 e 的 ILSD 度量值 简记为 12()seLJ ，其中 2212 13, d e t( )L J L J J ， 经推导 可得顶点 p 的领接四面体 e 对于分量 的一阶偏导为： 1222,2 .3 2 6seFFJ J J JLJJJ (2.7) 由此 可得目标函数 sLF对于分量 的一阶偏导为： .s s ee T p xeL F L JG 由于 ,J 是 ,xyz 的线性函数，则 ,J 的值为零。经推导可得顶点 p 的领接四面体 e 对于分量 ,的二阶偏导为： 12,seLJ (2.8) 其中： 1111 24 21, 2 , , ,1 2,32 FFJ J J J J JJJ (2.9) 2222 24 22, 2 , , ,1 2.36 FFJ J J J J JJJ (2.10) 东北大学秦皇岛分校毕业设计（论文） 第 10 页 带 Armijo 线性搜索的非精确牛顿法详细步骤 如表 2.1： 表 2.1 非精确牛顿法 算法 2.1： 带 Armijo 线性搜索 的非精确牛顿法 a) 设置初值， 给出固定点 fp 、控制点 hp 和未约束点 up ，算法迭代终止阈值 610 ，令 0k ； b) 计算目标函数梯度 ksLx ，若 2ksLx 停止迭代，输出 kx ，否则转 c)； c) 计算目标函数 Hessian 矩阵 2 ksLx ； d) 构造牛顿方程 2 k k kssL x d L x ， 得到 下降方向 kd ； e) 采用 Armijo 规则计算 得出 满足下述不等式的大于零的最小整数 m ， ( ) ( ) ( )k m k k m k T kx x xF x d F x F x d 其中 0 1 2 0 1m ， 为常数 +1 +k k m kx x d ，转 b)。 实际求解过程如下所示，计算流程图如图 2.3 所示。 Step1 载入数据预处理：从 *.node、 *.ele 文件中读取模型数据，计算初始时每一个四面体 元素 的体积、关联矩阵，并交互得到固定点、控制点及未约束点。 Step2 计算梯度：选定初值后计算初始梯度 ()ksLx ，若 2ksLx 停止迭代；设置最大迭代次数 ，若迭代次数超过 同样停止迭代 ，否则转 Step3。 Step3 得到下降方向：计算目标函数 海塞 矩阵，构造牛顿方程 2 k k kssL x d L x ，求解得到下降方向 kd 。 Step4 获取移动步长： 用 Armijo 线性搜索法得到满足下列条件的最小非负整数 m ，其中 0.2 0.5， 为常数，令 +1 +k k m kx x d ，转 Step2。 东北大学秦皇岛分校毕业设计（论文） 第 11 页 图 2.3 牛顿法 流程图 2.3 实验结果 牛顿法求解最优化问题对于初值是敏感的，为了提高求解速度，需要 为优化问题赋予合理的初值。在本文的试验中为模型选取了固定点 fp 以及操作点 hp 作为约束点c f hp p p ，约束点 cp 的运动轨迹已知，可以依据约束点 cp 来预测未约束点 up 的位置，即通过将固定点 fp 以及操作点 hp 的运动方程线性插值到未约束点 up 上。 若已知操作点 hp 绕 x 轴 旋转 ， 旋转角度为 ， 则 可 估测得到 up 的 坐标 为 1 0 00 c os si n , 1 ,0 si n c osu u u h f hg gp k k p k p p p pkk (2.11) 其中uhgpp表示未约束点 up 到操作点 hp 的离散测地距离，fhgpp表示固定点 fp东北大学秦皇岛分校毕业设计（论文） 第 12 页 到操作点 hp 的离散测地距离。显然与操作点 hp 靠近 的点旋转角接近 于 ，与固定点 fp 距离 靠 近的点旋转角度 接近于 0，符合 认知 规律。 同样 若 操作点 绕 y 轴 、 z 轴 旋 转 ， 约束顶点 以及交互方式不变，仍然可以采用公式（ 2.11）预测不可知点的坐标 。以预测出的 up 作为初值，带入非精确牛顿法中， 不仅降低了迭代的数量，而且使得 求解 过程 快速收敛， 极大程度上 改 加快 求解速率 。 图 2.4 展示了对一个棒不同编辑方式的结果，原始的网格模型表面其中蓝色点为固定点红色点为控制点 (a)，及其剖视图 (b)。用户操作控制点拧 60 度 (c)，拧 120 度 (d)，拧180 度 (e)，用户操作控制点绕 黄色 轴弯曲 (f)、 (g)、 (h)、 (i)。 (a) (b) (c) (d) (e) (f) (g) (h) (i) 图 2.4 基于形变能量最小网格编辑 东北大学秦皇岛分校毕业设计（论文） 第 13 页 3 基于局部 细节 保持的体网格 变形技术 基于 Laplacian Coordinate 的 三维 模型 变形 技术 是 最近 几年兴起 的一 种 三维模型编辑手段 。 与以往的直接基 于 控制 顶点的曲面变形编辑问题相较 该方法对曲面局部差分坐标进行编辑，然后 建立能量函数 通过 求解最优化问题得到变形后顶点的位置 。利用此种技术 ， 仅需用户 施加较 少的交互操控 ， 模型便可 达到生动自然的 编辑 效果 ， 而 且 模型 表面 的局部 细节 可以 被 较 好地 维持 。 Laplacian 网格编辑技术 实现简单、 交互方便 、效果良好，并可实现形变、变形传递、 表面光顺 、融合等多种网格编辑 技术 ， 已经吸引了大量的研究人士 受到广泛的关注。 (a) (b) (c) 图 3.1 Laplacian 网格编辑 1 Laplacian 网格 编辑 技术 为了得到 Laplacian Coordinate 的微分表达形式，主要通过将 Laplace 算子 离散化 作用在 模型的 离散网格顶点上 。以往 的 Cartesian Coordinate 直接定义 了 所有 顶点 p 的 绝对 位置 ， 而 Laplacian Coordinate 则包含 了 长短 、方向等 关于 网格曲面 几何 细节 的 信息。 因此 为了 在 模型 编辑过程中，尽 量 保 持 模型表面 原有 的 几何 细节 ，保持 网格 顶点 Laplacian Coordinate 不变的算法 是可行有效的 。 3.1 四面体网格的 拉普拉斯 算子 3.1.1 表面网格的 Laplacian坐标 应用 Laplacian Coordinate 表 达模型表面 局部几何 细节的 精髓 是：寻找一种表示， 利用 网格上 一些 顶点 jp 做 加权求和 ， 来 估计得到 某个网格顶点 ip 的 Laplacian Coordinate，依据这些 顶点之间的关系 ， 展示 模型表面的细节特征 。 电磁场 中使用的 Laplace 理论 是 连续的 ， 然而 在 网格模型 中 要求的是 离散化的拉普拉斯形式。 东北大学秦皇岛分校毕业设计（论文） 第 14 页 () ()i ij ij ij N i pp 1ip p p ds 图 3.2 Laplace 离散形式和连续形式 对于 模型上的每一个顶点 ip ， 其拉普拉斯坐标 i 可以定义为， 可以表示为与其一阶领域点 jp 所连成的边对应的向量的加权求和 ： ()( , , ) ( ) ( ) ,x y z Ti i i i i i j i jj N iL p p p (3.1) 其中 ()Ni表示该顶点的一环领域， ij 代表顶点 ip 与 jp 之间的权重。把所有网格顶点的拉普拉斯坐标 i 合在一起写成矩阵 12, , , , ,TT T T x y znD ，公式 （ 3.1） 可以使用拉普拉斯矩阵 ijLl来表示： (), , ( ) , .0 , .ijj N iij ijijLP wh e re l j N io th e rwise (3.2) 不同的赋权方式 决定 拉普拉斯坐标 所 所描述的几何意义 以及 适 用 的范围 ， 对于网格表面的拉普拉斯坐标 ML 本文采取的是 1 c ot c ot2ij ij ij ， ij 与 ij 是与边 ijpp 对应的相反的两个角 13，如图 3.3(a)所示 。 (a)模型 表面顶点一 环领域 (b)模型 内部顶点一 环领域 图 3.3 模型顶点一 环领域 东北大学秦皇岛分校毕业设计（论文） 第 15 页 3.1.2 网格内部的 Laplacian坐标 对于四面体网格的 Laplacian Coordinate 即 GL ，我们通过计算一个二次规划问题来得到 其权值 6。对于四面体网格中的每一个顶点 i ， 解决 下 述 优化 问题 便可计算出 权重 ij 22( ) ( )()m in ,. . 1 .ji j j j j ij N i j N iij ijj N ip p p ps t a n d (3.3) 类似于网格光顺，我们总是希望 Laplacian Coordinate 的长度尽可能小，最小化能量中 第一项 就起到了这样的作用。 较为合理的 Laplacian Coordinate 赋权方式应该正比于边长的倒数，距离越远比重越小，这称为与 尺度相关的伞状算子 （ Scale-Dependent Umbrella Operator） ，增加第二项能量就是为了达到这样的效果 。参数 能够 调节 这两个 能量 项 的权重 比例 ， 在本文 将 和 均 取值 为 0.01 时 变形效果 良好 。 3.2 Laplacian形变算法框架 图 3.4 展示了 Bunny 原模型 (a)，选定头部红色顶点连成控制线， 模型由蓝色渐变到红色表示控制线对区域 影响 程度 的强弱， 与 控制线 较 近的部分 影响程度大 颜色偏蓝，越远 影响 程度 越小颜色 偏红 (b)，操作控制点使 Bunny 低头后模型为 (c) (a) (b) (c) 图 3.4 基于控制线变形 构建能量函数 Laplacian Coordinate 描述的是 网格模型的局部性质 ，因此 Laplacian Coordinate 的取值不会受 顶点在 全局空间坐标系中 绝对位置 的 影响 。利用 一个网格 模型 的 Laplacian Coordinate 矩阵 ， 应用公式 （ 3.2） 提出的方法，可以得到编辑后 模型顶点 的 位置坐标P 。由于拉普拉斯矩阵是一个 秩为 ( ) 1R L n的对称半正定 稀疏矩阵，为了求解的唯一东北大学秦皇岛分校毕业设计（论文） 第 16 页 性，则至少应该固定其中一个顶点的绝对位置。在实际使用 Laplacian 变形技术进行 三维 模型编辑时，一般会选择部分 顶 点 ip 作为约束点，其目标位置已知为 iq 。在本文用户首先需要在模型上选定控制点作为变形过程中的操作点 （ 用户可以任意选定两点，程序自动将两点沿着 网格边连接 ） ，用户通过控件实现对操作点的平移和旋转。基于此以控制点作为约束点，并且其目标位置由用户交互得到。这里假设约束顶点的索引集合为 1, 2 , , | 0C m m n ，则有下列约束需要被满足： , 1 .iip q i m (3.4) 上述 约束将作为软约束在最小二乘意义下被满足，这比其作为硬约束能够取得更自然的变形效果。 编辑后的模型顶点的位置坐标 ip ，可以通过求解以 下 最小化误差能量方程 的最优化问题 来 得到 2 2 21 1 1( ) ( ) ,n m NM i i i i G i ii i iL p p q L p (3.5) 其中， ML 是曲面网格 M 的拉普拉斯算子， G 是四面体网格 G 舍去 M 中的边界边 后 G 的子图。对 于曲面网格 M 中的点， (1 )i in 是变形后顶点 的 拉普拉斯坐标 。对于子图 G中的点， (1 )i iN 是形变后四面体网格的 Laplacian Coordinate。 目标函数 由三 项 能量组成 ， 第一部分 描述维持模型表面微分属性 ， 第二部分表示 考虑 用户 对于顶点位置的约束， 带三部分 保持四面体网格 内部几何属性 的程度。 用 来调节 模型 表面和 模型 内部的细节 维持 比例 权重 。在具体实现中，借助另外一个参数 来计算 ： nN 。 系数 nN起到 归一化的作用 ， 这样 可以减少 四面体剖分的 疏密 对于变形 效果 的影响。 基于 此种方式 ，经过试验 1 可以 较好均衡 模型 表面与 模型 内部网格的 几何属性维持 程度 。因为 控 制句柄的多少决定了 位置约束的强 弱 ： 交互时 用户选取的控制 句柄 越多， 那么相应的 位置约束越强 ， 所以 参数 没有必要 归一化 。一般情况下 0.1 1能获得很好的结果 ， 默认情况下，它被设置为 0.2。 与 方法 1-3 1414一样，基于四面体网格的变形方法需要估计变形 后的拉普拉斯坐标： i i iT 或 ,i i iT (3.6) 其中 ( ), ( )i G i i M iL p L p表示网格未变形时的 Laplacian Coordinate， iT 是一变换矩阵用 四元数表示 ， 得到 变形之后的 Laplacian Coordinate 即 ,ii。 有关局部变换的 求解 将东北大学秦皇岛分校毕业设计（论文） 第 17 页 在下文详细介绍。 获得变形后的拉普拉斯之后，由公式 （ 3.5） ，求解变形后顶点的位置就称为一个二次能量最小化问题。将该问题线性化 为 ： ( ) ( ) , 1 , , ,( ) , 1 , , , 1 , , .M i G i i iG i iiiL p L p i nL p i n Np q i m (3.7) 这构成一个稀疏线性方程组 Ax b 。矩阵 A 决定于变形之前的 三维 网格模型 即 Laplacian矩阵， b 则依赖于变形之后的 Laplacian Coordinate 和用户 规定 的约束点的坐标 。 如果 用户 选定 的约束顶点 不发生变化 ， 并且平衡各项能量的 参数 ， 恒为常数 ， 则 用户 操作模型的多数编辑方式中 ， A 一直 不发生变化，而 b 反应用户的交互方式 一直变动着 ，因此可以采取 LU 预编译技术加快求解速度 。 局部变换扩散 由于交互编辑时，用户仅指定了控制线上 顶 点变形之后的位置，目前已经有许多方法能够由控制点的位置 iq 得到 iT 2 3 14 15。本文采用与 扩散策略 3类似的 方法 ，首先根据控制点位置的变换估计其一阶领域的位 置，然后推测控制点处发生的局部变换，接着依据强度函数不同程度地向兴趣区域蔓延，最后插值 确定每个顶点的局部变换。 控制线的定义以及基于控制线的变形 ，如图 3.4 所示。 根据 WIRE 变形方法 16首先通过控制线上各目标顶点位置 iq