基于材料特性的三维形变方法

学士学位论文 基于材料特性的三维形变方法 作者姓名：姜仲石 学科专业：数学与应用数学 导师姓名：刘利刚 教授 完成时间：二一六年五月 University of Science and Technology of China A dissertation for bachelors degree Material Aware Volumetric Deformation Method Authors Name:Zhongshi Jiang Speciality:Mathematics and Applied Mathematics Supervisor:Prof. Ligang Liu Finished Time:May, 2016 中国科学技术大学本科毕业论文 致谢 随着毕业论文的结题, 大学四年即将画上句点. 值此之际, 向所有教导过我的 老师, 帮助过我的同学们, 致以由衷的谢意. 首先, 感谢我的导师刘利刚教授一直以来的悉心指导, 向我展示了计算机图 形学的魅力. 刘教授严谨的治学态度和勤勉的工作精神, 使我受益匪浅. 其次, 感谢周围的同学和朋友们, 在四年来的学习和生活上给我无私的帮助. 最后, 感谢我的家人, 是你们的一贯支持与理解使我得以安心专注学业. 我将带着师长, 家人和朋友的关怀和期望, 踏上人生新的征程! I 中国科学技术大学本科毕业论文 目录 摘要 3 Abstract4 第一章 绪论 5 1 形变算法 5 2 三维网格 6 2.1 离散化7 2.2 数据结构 7 3 本文内容与结构 7 第二章 材料性质基础8 1 应变张量 8 2 弹性理论 9 第三章 形变能量11 1 线性形变 11 1.1 微分坐标框架11 1.2 离散微分算子11 1.3 线性化瑕疵 13 2 旋转不变性 15 2.1 迭代法15 2.2 插值法15 3 依材料形变 17 4 小结 19 第四章 实验结果20 1 用户界面与交互 20 1 中国科学技术大学本科毕业论文 2 效果图 21 2.1 基本形变 21 2.2 材料感知 22 第五章 总结与展望 24 参考文献 25 2 中国科学技术大学本科毕业论文 摘要 快速而又真实的形变, 是计算机图形学中许多操作的基础步骤: 在对于编辑 几何的模型中, 模型师控制局部区域的位置等信息, 余下的几何可以自然地改变 形状; 在动作或表情捕捉与转移的过程中, 预设的控制点位置的改变也驱动着整 个模型的变化; 在动画制作时, 几何模型在关键帧之间的变化也离不开有效的形 变操作. 因此, 数字几何处理领域发展出了许多方法, 处理基于多边形网格的几何 模型的形变操作. 随着近来虚拟现实/增强现实技术的兴起, 几何模型越来越多得被用于在现实 情景中的渲染和显示. 3D 打印更是要求几何模型足够符合物理特性, 从而可以被 真实生产出来. 从而, 更加真实的形变方法变得尤为重要. 本文, 我们介绍一个可 以更加符合物理直观的快速易用的三维形变算法. 它可以考虑材料特性, 并允许 交互地对几何体进行操作. 我们采用了文章 8 中的框架与线性弹性理论的知识, 定义了基于材料特性 的二次形变能量. 接下来, 我们通过迭代的方法克服其不保持刚体运动的局限性. 进一步, 我们又通过矩阵分解加快了计算的效率, 通过控制柄变换的插值提高了 收敛的速度. 同时, 我们也设计了用户界面和交互, 可以按照材料特性进行模型的 编辑. 最后, 我们通过编写程序实现了算法, 通过所做的实验可以看出, 我们的形 变算法得到了定性上较为满意的结果. 3 中国科学技术大学本科毕业论文 Abstract Fast and realistic deformation is a crucial step for various operations in computer graphics: when editing a digital geometric model, modeler manipulates the local infor- mation of the handle regions, and the rest of the geometry deforms its shape automat- ically; during motion or facial expression transfer, positions of predetermined control points drive the transformation of the whole object; for the production of animation, generation of geometric models between key frames also requires effective deforma- tion operations. Therefore, there is ample methods developed within the field of digital geometric processing that deals with deformation of polygonal meshes. As the emerging of virtual reality or augmented reality, more geometric models are used for rendering in real life scenes. Moreover, 3D printing demands such physical compatibility that the models are able to be actually manufactured. So more realistic deformationalgorithmshavebecomemoreandmoreimportant. Herein,weintroducean approach that deals with volumetric geometric models and is more intuitive physically. It considers material properties and allows interactive manipulation of objects. Weemploytheframeworkfrom8andknowledgefromlinearelastictheorytode- fine the quadratic deformation energy based on material properties. Next, we improve the scheme to preserve rigid body movement by iterative modification. Furthermore, we expedite computation by matrix decomposition and improve convergence by inter- polation of the handle region transformations. Meanwhile, we design the user interface and interaction for real-time model editing taking into account of material properties. Finally, we implemented the algorithm, and through experiments with it, we are able to observe that our algorithm achieves results that qualitatively comply with the material definition. 4 中国科学技术大学本科毕业论文 第一章绪论 几何物体的形变操作, 是模型编辑, 动画制作以及动作转移等研究领域的基 础. 一直以来, 数字几何处理的主要研究对象是网格结构, 因为其具有理论和应用 的简洁性, 并且可正常处理生产生活中常见的高亏格曲面. 对于网格结构的几何 模型, 形变算法读取用户的控制后, 而通过调整整体模型中各个顶点的位置 (一般 不改变离散网格的拓扑结构), 来生成适应用户的要求的新模型, 同时保持整体的 光滑性和局部的细节. 对于用二维多边形网格表示的几何对象的外表面的形变操作, 处理的数据量 较少, 可以较好地满足其在屏幕上设计和编辑的操作, 但却从本质上无法兼顾材 料, 体积等几何体内部的物理特性. 近年来, 随着 3D 打印技术, 虚拟现实技术的蓬 勃发展, 和更逼真的动画制作的需求, 形变操作的重心向基于体积的几何对象转 移. 所以才用四面体网格表示离散化几何模型的内部, 我们可以方便地定义材料 特性, 得到更加符合物理直觉的结果, 这便是本文的主要内容. 1形变算法 文献中有许多用于模型编辑的形变的算法, 我们将基于以下因素对它们加以 分类考察 8. 易用性: 算法的输入输出可以较好地被用户理解和实现. 实时性: 变形过程中要有较高的效率, 便于对模型的实时编辑或动作实时跟 踪. 直观性: 变形的结果要符合用户的直观, 即契合物理直觉. 可扩展性: 算法复杂度不应过高, 要对越来越精细或大型的模型有处理能力. 在实际应用中不一定是理论复杂度, 还要考虑平均情况所需的时间. 通用性: 算法适用于各种不同的拓扑和形状. 因为现实生活中遇到的模型可 能具有各种不同的拓扑特性. 按照形变的原理, 常见的形变算法可分为以下几大类: 基于框架: 这类算法尤其常见于对动画人物的操作, 通过对骨架的操作移动 其关联的肢体 5, 7. 这一方法可以很快速的处理变形, 但不适用于一般的 5 中国科学技术大学本科毕业论文 不基于骨架几何形体, 以及无法处理对细节的编辑. 空间变形: 通过对对应空间的变形扭曲操作, 达到快速变形效果 14. 然而 大规模形变的情况下很容易看出瑕疵. 物理方法: 物理方法即是求解对应的微分方程, 一般采用有限元方法. 但是 精确计算需要大量的时间和资源, 精确性也限制了用户控制的方法. 在数值 模拟的应用中, 精度要求很高, 一般只能采用物理方法. 如果仅是模型的设 计和编辑, 可使用简化的有限元方法并结合模型简化来达到近似实时的效 果 10. 几何方法: 通过微分几何领域提出的概念与方法来刻画几何对象所需要保 持的特征 8. 这类方法一般提出基于几何的形式上较为简洁的能量函数, 通过变分方法可以较快求得一个满足需求的几何对象. 一般的几何方法易 于使用并且交互性较强, 但是对于物理特性的考虑有限. 我们的方法便主要 是几何方法, 通过引入材料特性, 来更好的适应物理特性的要求. 2三维网格 在 3D 计算机图形学中, 有多种方式来存储与表示一般的几何对象 (包括曲 线, 曲面以及三维几何体). 分段线性表示, 因为简单和直观, 受到了广泛的关注和 应用. 图1.1显示了一维, 二维和三维几何体的分段线性表示. (a) 用十二边形逼近圆(b) 骆驼头的三角网格表示(c) 四面体化兔子模型 图 1.1分段线性表示 注意到, 对于一般的三维几何对象, 我们可以选择直接用三维的多面体离散 化其内部, 也可以选择用二维多边形网格表示其表面. 并且, 二维曲面的表示方法, 因其数据表示较为简单, 数据规模较小备受青睐. 然而我们的形变算法选择直接 6 中国科学技术大学本科毕业论文 对三维网格进行操作, 是基于如下的考虑: 硬件的发展使我们已经可以应对更大规模的计算, 三维网格在数据规模不 是非常大时, 也可以达到较为满意的实时效果. 编辑三维对象时, 其外表面并不能蕴含内部信息, 难以顾及内部的体积变化 以及相关的弹性力作用. 3D 打印等技术的产生, 使得图形学的研究内容不只局限于在电脑屏幕上的 显示与渲染, 也要兼顾几何对象的物理特性. 对于三维单形网格的生成, 已经有较为成熟的算法. 2.1离散化 我们采取常见易获得的二维网格作为输入, 在保持表面剖分不变的情况下对 其内部进行三维单形离散化, 即四面体剖分. 在这一步中我们使用 TetGen16, 一 个用 C+ 编写的易用的四面体网格生成库. 四面体网格的相关研究中, 有一些常见的网格质量的标准. 纵横比由最大的 边长度和最小的高度之比决定. 径边比通过外接球半径与最小边长之比计算得到. 在 TetGen 中, 可以通过调节相关输入参数, 得到较为满意的四面体剖分. 2.2数据结构 在二维的多边形网格情形中, 常见的有翼边, 半边等数据结构, 它们区别于点 线面连接关系的存储方式 2. 三维网格情况也有类似的表示方法, 这里我们仅采 用一个最直观简单的列表存储, 叙述如下. 四面体网格可定义为二元组 M := (V,T), 其拓扑关系取决于四面体集 T := t1,.,t|T|, 其中 tj V V V V . 通过顶点位置矩阵 (|V |3) 和拓扑关系矩 阵 (|T| 4) 即可存储三维四面体网格. 通过对拓扑关系矩阵逐行遍历, 我们便可 以对每个单形进行几何操作. 3本文内容与结构 本文的主要内容是基于材料的三维形变算法. 先推导出基于材料特性和微分 坐标的二次能量. 再用迭代修正的方式补偿其中应变能的近似线性化. 本文的后续部分按如下的顺序进行组织与编排: 第二章简述将用到的线性弹 性材料模型. 第三章推导兼顾计算效率与物理直观的形变能量. 第四章介绍实现 的应用程序的交互操作和实验结果. 第五章总结并展望未来工作. 7 中国科学技术大学本科毕业论文 第二章材料性质基础 弹性固体的力学性质一般由应力和应变的关系所刻画. 线性弹性理论假设这 些关系都是线性并且忽略历史效应, 热效应等. 这对于计算带来很大便利的同时 做出了在一般变形下较好的近似. 在我们的应用中, 我们假定以下特性 线性材料: 在小规模形变中, 大部分材料会表现出线性的应力-应变关系. 当 形变程度超过加大时可能会变为非线性, 这个行为被描述为比例极限. 这个 假设虽然会带来在大规模形变下的不准确, 但极大地简化了计算. 弹性材料: 这一类材料忽略了历史效应 (如黏性力). 对于非精确模型编辑的 应用, 时间维度一般并不考虑. 各向同性: 很多材料都是, 对于不同方向的应力表现出不同的应变行为, 为 了简化模型, 我们暂时只考虑各向同性的材料. 1应变张量 在我们的应用中, 几何对象为分段四面体表示. 进一步我们也近似假定材料 也是分段常值 (即网格中每个四面体具有均匀材质). 经典力学可以将形变效果描述为弹性固体内的位移场. 局部位移 d 可以表达 为位置 p 和局部的 (四面体内) 线性变换 T = V V1 的函数, 其中 V 表示原顶点 坐标,V 为变形后 (未知) 的顶点坐标. d=p p =(T d)p + t = (t1,1 1)p1+ t1,2p2+ t1,3p3 t2,1p1+ (t2,2 1)p2+ t2,3p3 t3,1p1+ t3,2p2+ (t3,3 1)p3 + t, 微分得到, dp= Tdp, 8 中国科学技术大学本科毕业论文 这里 T 可以被称为形变梯度或位移梯度张量, 有如下表达, Tm,n= pm pn . 注意到 dRp= RTdp, 形变梯度不保持刚体变换. 进一步, 通过 |dp|2 |dp|2=dp|T |Tdp dp|dp =dp|(T |T I)dp =dp|2dp, 我们可以得到 Green 应变张量= 1 2T |T I, 它在旋转不变的意义下描述了形变 的程度: = 1 2(RT) |RT I = 1 2T |T I =. 小形变情况下也会用到其线性近似 Cauchy 应变张量= 1 2(T | + T) I. 2弹性理论 我们有熟知的胡克定律 (Hookes law): 弹簧弹力正比于弹簧拉伸的长度. F = ka. 现代的弹性理论 17 将其推广: 弹性对象的应变正比于其上的应力. 然而, 因 为应变/应力有多个分量, 其比例 “系数” 不再是一个标量, 而是一个张量. 为了衡 量材料的弹性特性, 根据广义胡克定律 (generalized Hookes law), 我们考虑以下五 个物理量. 杨氏模量 (Youngs modulus) E 描述了材料沿轴向应力的应变程度. 泊松比 (Poissons ratio) 描述了垂直轴向应力的应变程度. 体积模量 (Bulk modulus) K 描述了对于均匀压力 (如深水中) 的应变程度 拉梅参数 (Lame Parameter) 描述了材料对于体积的应变程度 剪切模量 (Shear Modulus) 描述了材料对于剪切力的响应. 9 中国科学技术大学本科毕业论文 对于各向同性的材料, 它们不是相互独立的, 并可由其中任意两个模量确定, 如通 过 , 我们有: E= (3 + 2) + = 2( + ) K= 3 + 2 3 . 进一步, 我们可以将对象当前状态下的弹性应力张量 与应变张量的关系 表示如下 17: = Tr()I + 2. 在我们的应用中, 弹性力并不是用来促进对象的进一步变形, 而是在用户输 入的约束条件下, 为了达到近似稳定的状态所需要减弱的物理量. 为了量化定义 这一行为, 我们可以引入应变能: U= 1 2 3 m=1 3 n=1 m,nm,n = 1 2Tr() 2 + |2 F;. 这是一个正定二次能量, 取最小值当且仅当应力 = 0 或应变= 0, 这确实是我 们预期的效果. 10 中国科学技术大学本科毕业论文 第三章形变能量 形变问题可以理解为: 在满足用户输入的顶点位置等约束条件下, 找到一个 视觉效果较好的新的三维流形. 我们所要解决的关键就是对于约束条件和优化目 标的选择. 注意到约束条件可写为能量形式, 作为待优化的一部分 (如罚函数法), 从而 应用更快的求解方法. 所以, 我们这里寻求一个统一的形变能量表达. 1线性形变 形变算法重要目的包括方便几何模型的实时编辑以及进行进一步的动画制 作. 这给算法的响应时间提出了很高的要求. 所以将能量表达为二次函数, 从而使 得求解过程为线性方程组, 是自然的想法. 1.1微分坐标框架 我们的目的是求得全局上较为光滑并且保持局部特征的形变状态. 所以我们 引入几何对象的微分, 称为微分坐标. 使目标对象的局部微分信息不偏离源对象 太多的同时, 考虑控制区域的软约束, 便得到如下能量表达: E = DiV i|D(D i) di| 2 + DiDb i|D i bi| 2. 其中 D 表示指定的线性微分算子 (梯度, Laplacian 等), D 代表局部几何 (顶点, 多 边形面片, 多面体以及其它想要控制的局部几何对象). d 表示源几何体的微分信 息. b 表示用户控制的区域 (控制柄) 局部几何对象的目标位置或旋转约束. i,i 为相应的权重. 这个无约束二次规划问题, 代入选取的微分信息和约束信息, 可化为线性方 程组求解 参见 8, pp. 11-12. 1.2离散微分算子 为了方便进一步的讨论和计算, 我们将在这一节推导出四面体网格上离散梯 度和离散 Laplacian 算子的表达形式. 11 中国科学技术大学本科毕业论文 考虑四面体 tj= vk,vl,vm,vn 中的点 pu|tj, 它被其相对于四个顶点 vk的重 心坐标函数 k(u)|tj唯一确定. pu|tj= vktj k(u|tj)pk. 三维情形中, 重心坐标基函数是用来表示体积的比例, k(u)|tj=vk,vl,vm,vn= volume(pu,pl,pm,pn) volume(pk,pl,pm,pn) = 1 3area(pl,pm,pn)hu 1 3area(pl,pm,pn)hk = 1 hk hu, 其中hk与hu分别表示点pk和pu与面vl,vm,vn)的距离. 再记h为面vl,vm,vn) 指向 pu| 的单位向量, 则重心坐标基函数的梯度 k(u)|tj在四面体中为常量, k(u)|tj=vk,vl,vm,vn= 1 hk hu = 1 hk |(pu pn)|h| = 1 hk h, 计算可得 pk pnpl pnpm pn| |z V | j k|tjl|tjm|tjn|tj |z j = 1001 0101 0011 |z K , 从而, 关于坐标函数的梯度可如下求得. 12 中国科学技术大学本科毕业论文 p|tj=vk,vl,vm,vn=k|tjp| k + l|tjp| l + m|tjp| m+ n|tjp | n =jpkplpmpn| |z P| j =V | j KP | j =V | j 1001 0101 0011 pkplpmpn| =V | j pk pnpl pnpm pn| =I. 为了求得 Laplacian 算子, 只需要对上面求得的分段常值的梯度取离散散度. pi=divpi =i tjTi ji|tj =i. 其中 Ti为与顶点 vi相邻的四面体集, 和 为与四面体和顶点相关的离散权重. 文献中有多种选取方式, 这里我们选取如下: i= 1 i, 其中 i 是顶点 vi的 Voronoi 体积 9, i= Vi为该四面体的体积. 将这些微分算子代入微分坐标形变能量框架中, 便可得到基本的变形效果, 如图3.1. 1.3线性化瑕疵 对于理想的变形效果, 我们自然地假设它可以保持刚体运动, 即平移和旋转 不会增加形变能量. 微分方法很好的解决了平移的问题. 而不幸的是, 对于上一节 中的梯度算子, 无法保持旋转不变性. Rp|tj=vk,vl,vm,vn=V | j K(RPj)| =V | j KP | jR | =R|. 事实上, 我们可以证明 13 中国科学技术大学本科毕业论文 图 3.1基于微分坐标的变形 注：左图为原型, 中间为基于梯度的变形, 右图为基于 Laplacian 的变形, 引用自 8 . 命题 3.1对于三维体网格无法构造一种二次能量, 使得剪切和拉伸被考虑, 而刚体变换被忽略 (即刚体变换的情况恰使形变能量达到极小值). 证明 假设有满足题设的能量并将其作用在单个四面体网格(0,0,0),(1,0,0),(0,1,0),(0,0,1) 与其变形后的非退化四面体 (0,x|,y|,z|) 上. 记 V = x yz, 这给出了一个二次函数. 不妨设其无常数项, Q(V ) = V |AV + BV , 忽略刚体变换的条件使得对任意旋转 R, 应满足 Q(V ) = Q(RV ), 即 V |AV + BV = V|R|ARV + BRV , 对 V 恒成立使得 BV = BRV . 由非退化条件以及旋转矩阵的可逆性,B = O. 即能量中只有二次项: Q(V ) = V |AV. 进一步, 为了使得能量可以取到极小值,Q 必为半正定能量, 而这蕴含在 V = O 处, 退化时取得了极小值, 与题设矛盾. 14 中国科学技术大学本科毕业论文 2旋转不变性 为了使形变能量忽略刚体变换 (因为微分过程中已经忽略了平移, 这里只需 考虑旋转), 可以使最终的旋转矩阵作用在源对象的微分坐标上. E = DiV i|D(D i) Ridi| 2 + DiDb i|D i bi| 2. 然而, 求得最终形变之前, 我们怎么能得到其旋转呢? 所以, 我们提出两种近 似方案: 任取旋转值并不断修正 (迭代法), 或通过其它方案预估最终旋转 (插值 法). 我们的应用中, 采用插值方式得到较好的初始值, 再进行较少步骤的迭代操 作, 便可以达到更快的收敛速度. 对于复杂的大规模形变, 也可以直接采用插值得到的旋转结果, 赋给逐个四 面体, 再加入顶点位置对齐的约束, 得到形变结果 13. 2.1迭代法 通过迭代的过程, 我们可以对于特定的旋转初始值, 优化形变能量. 再将结果 中局部几何对象的旋转作为下一次优化的初始值. 1. 通过前一次迭代的计算结果, 求得局部形变 TjVj= V j Tj= V jV 1 j . 其中 Vj为源对象的局部四面体顶点坐标. 其 V 1 j 可以注册模型之前预先计 算好, 所以这一步只有简单的矩阵乘法. 2. 极分解到其旋转分量 Tj= RjNj. 这里我们采用 4 的近似计算方法. Rj,0= Tj,Rj,k+1= 1 2(Rj,k + R| j,k), 直到 Rj,k+1 Rj,k. 实际应用中, 约两次就可以达到较为满意的精度和时间 之间的平衡. 3. 将旋转分量代入下一次迭代. 2.2插值法 梯度域调节技术最早出现在 19 中, 依赖于附加的用户输入来确定局部的变 换. 我们同样通过插值的办法得到预设的旋转域, 来满足旋转不变的要求. 下面考 虑插值方法和插值权重的选取. 15 中国科学技术大学本科毕业论文 权重域19提出了在网格上的调和插值方法. 第m个控制柄的标量调和域hm,u 满足调和方程 hm,u= 0. 再限制控制柄上的顶点的插值权重 hm,i= 1 便可以求 解得到能量. E(hm) = vi/ Vb ih2 m,u+ viVb,m i(hm,i 1)2+ viVb,m,m=n ih2 m,i. 我们选取调和域方法. 再结合到杨氏模量的物理意义 (抵抗形变能力, 可以理 解为硬度), 代入第三章中得到的 Laplacian 算子, 得到如下能量 E(hm) = vi/ Vb i(i vkVi Ei,ki,k(hm,ihm,k)2+ viVb,m i(hm,i1)2+ viVb,m m=n ih2 m,i. 通过对这个能量的求解, 我们可以得到关于顶点的 “硬度” 权重. 插值方法空间旋转的四元数表示, 因其数学上的优雅与简洁, 与其方便的插值 算法, 得到广泛的应用. 四元数的插值一般采用球面线性插值法 (Spherical Linear Interpolation, SLERP 15). 然而由于四元数乘法, 以及一般矩阵乘法的不可交换性,SLERP 并不能完全 满足我们的需求: 在面部表情跟踪合成等应用中, 需要解决多个锚点同时变换位置的问题. 而 SLERP 实际上是一个两点插值法, 四元数的乘法不交换性使得推广 SLERP 是非平凡的. 即使在我们的编辑中, 每次只操控一个控制区. 用四元数的插值方法, 操控 的先后顺序会影响插值结果. 这也是四元数非交换性引发的问题. 基于以上考虑, 我们采用 1 中提出的可交换的矩阵代数. 先定义两个新运算 和 , 它们基于矩阵的指数和对数运算, A B = exp(logA + logB), A = log( logA), 其中, expA = k=0 Ak k! , A = logX expA = X. 16 中国科学技术大学本科毕业论文 这样, 我们将线性变换 T加权 下的混合表示为 T . 这些运算对于三维旋转矩阵的是良定且封闭的, 更多细节以及数值近似计算 方法参见 1. 从而, 混合公式表示为 (T) = exp( i logT). 在算法中, 预计算权重域, 再在操作步骤中记录每个控制柄的旋转变换, 便可 以通过以上公式插值得到预估的旋转量. 3依材料形变 通过第二章中的基础知识, 我们现在将材料特性整合到微分框架中, 得到可 以根据物体的材料特性的能量函数. 为了得到可以线性求解的二次能量, 我们使 用 Cauchy 应变张量, 再通过迭代旋转的方法修正旋转不变性. = 1 2T |T I 1 2(T | + T) I. 从而, 应变能 U = 1 2Tr( 1 2(T | + T) I)2+ |1 2(T | + T) I|2 F. 进一步, 我们假定所有的局部变换 T 都是对称的 (事实上, 在收敛时我们可以得到 这样的结果, 见命题3.2), 应变张量可以进一步简化 j=Tj I = jV 1 j I, Uj= 1 2Tr(V jV 1 j I)2+ |V jV 1 j I|2 F, 其中,Vj为原顶点位置, V j 为形变后的未知顶点位置. 由本章中1.2小节的推导, 可 以注意到第二项同时刻画了梯度的差异, 即我们的能量包含了同时光滑约束. E(V)=E应变能+ E控制约束 = tjT jUj+ viVb i|pi ci|2 = tjT j (1 2jTr(V jV 1 j I)2+ j|V jV 1 j I|2 F ) + viVb i|pi ci|2. 其中 i为取每个四面体的体积作为应变能权重, 为控制约束的权重, ci为控制 柄的目标位置. 17 中国科学技术大学本科毕业论文 再考虑旋转不变性, 将源对象的顶点坐标 V 替换为 RV 便有 E(V)= tjT j (1 2jTr(V jV 1 j Rj| I)2+ j|V jV 1 j Rj| I|2 F ) + viVb i|pi ci|2 = tjT j (1 2jTr(RjV | j V j I)2+ j|V | j V j Rj|2 F ) + viVb i|pi ci|2 = 1 2| V1(A(R)p a)|2+ |V2(Bp b(R)|2+ | (Cp c)|2. 命题 3.2迭代收敛时, 局部的变换矩阵 T = T| 证明进行旋转修正后, 用来计算局部变换的顶点位置为 (R1V )1= V 1R| 1. 故此时局部变换为 T = TR| 1. 其中 T 为未经旋转修正时的局部变换 V V1. 通过极分解方法 15, T = RN, 其中 N 为对称正定矩阵. 注意到迭代收敛蕴含 R = R1. 从而, 此时的局部变换为 T = RNR|= T |. 为了方便求解, 我们将其填充为矩阵形式并取极小值, 可以得到线性系统如 下 参见 8, 6.3, pp.57, (1 2A |V1A + BV2B + C ) p= 1 2A |V1a + BV2b + Cc. 其中 V1,V2为 |T| |T| 与 9|T| 9|T| 对角矩阵, 记录对应四面体体积. , 为 |T| |T| 对角矩阵, 记录对应四面体的拉梅参数和剪切模量. A 为 |T| 3|V | 矩阵, 用来计算局部线性变换 RjTj的迹. B 为 9|T| 3|V | 矩阵, 计算局部线性变换 Tj的各项系数. C 为示性对角矩阵, 在控制顶点处值为 1. 为 3|V | 3|V | 对角矩阵, 记录对应顶点的权重, 我们取一个较大的值乘以 其周围的 Voronoi 体积. a 为常值 |T| 维向量, 记录了每个局部旋转矩阵的迹. b 为 9|T| 维向量, 记录了每个局部旋转矩阵的各项系数. 18 中国科学技术大学本科毕业论文 c 为 3|V | 维向量, 记录了控制顶点的坐标. 左侧的矩阵维度为 3|V | 3|V |, 对称正定. 迭代旋转求解的过程中, 需更新的 有 A,b. Cholesky 分解在实线性代数中, 正定对称方阵 U 的 Cholesky 分解将其分解为 U = LL|, 其中 L 为一下三角矩阵 18. 对 U 的预分解可以极大地加快求解线性 方程组 Ux = b 的效率, 特别是对于不同的 b. 正因为这一特点, 这一技术常在计 算机图形学领域用来进行快速的实时计算 12. 不幸的是, 在我们的系统中,A 的更新导致了左手边矩阵的变化, 无法预先进 行 Cholesky 预分解. 然而, 因为稀疏结构没有改变, 我们可以进行符号化的预分 解, 再进行数值求解. 但在实验中这对性能的提升并不足以进行实时化的编辑. 所 以, 为了可以通过 Cholesky 分解加快运算效率, 我们忽略对 A,a 的更新, 在形变的 效果上并没有明显影响, 这一现象的原因还有待进一步的研究. 4小结 本章我们用微分坐标框架, 结合材料的物理特性, 推导得出了依材料的形变 能量. 在此过程中涉及到了线性化的应变能. 为了修正其丢失的旋转不变性, 进一 步地通过迭代方法, 得到了保持刚体运动的迭代算法. 我们的实验中, 采用 Cholesky 预分解方法, 可以达到较好的实时化编辑效果. 19 中国科学技术大学本科毕业论文 第四章实验结果 1用户界面与交互 在我们的实验中, 通过鼠标操作定义材质和控制柄 (用不同的颜色标出), 并 在进行预计算之后, 通过鼠标操作进行对控制柄的移动和旋转, 进行变形操作. 图 4.1程序界面,GUI 采用 LibIGL 库 6 下面我们将逐步骤简述所实现程序细节的操作方法和涉及到的算法. 程序代 码托管于 GitHub 1. 区域选择我们的控制柄设定和材料的定义都是通过选区方法完成的. 在二维情 形中, 区域选择只需记录起始点和结束点, 选择矩形包围的像素即可. 而在三维情 形中对于网格的选择, 这不是一个平凡的问题. 这里我们采用光线跟踪方法, 在矩形包围的区域中逐像素沿垂直屏幕的方向 向内发射光线, 记录与模型上的交点并计算得到其相邻顶点作为选择的结果. 为 了更快的速度, 我们使用 Intelrembree 光线跟踪库, 以及层次包围盒 (Bounding Volume Hierachy) 进行预处理来提升多次选取的效率 3. 1/jiangzhongshi/MaterialAwareDeformation.git 20 中国科学技术大学本科毕业论文 材料定义实验中对材料的定义采用如下方案: 用户选择外表面的区域定义分块 均匀材质, 我们的程序对内部顶点进行再通过插值的方式对内部逐块定义. 程序 中目前采取的插值方案是先用 AABB 树方法进行预处理, 再计算顶点与所选择最 近的被定义表面顶点, 取相同的材质参数. 控制柄调整模型的朝向角度和位置是靠鼠标的操作控制的. 当用户选择调整一 个特定的控制柄时, 鼠标的交互操作会变为针对其进行的旋转或平移. 实时化控制我们可以通过一个小技巧来得到好的用户体验. 即调整控制柄后的 每次迭代结果, 都输出到屏幕. 用户可以选择性的停止查看或继续迭代, 以得到更 满意的视觉效果. 2效果图 2.1基本形变 图4.2展示了我们得到的基本变形结果. 左图为原型, 不同颜色标识了不同的 控制柄. 我们通过设置手掌与指尖为控制柄, 进行不同的位移和旋转操作, 可以很 轻松地得到不同的手势. (a) 原型(b) OK 手势(c) 胜利手势(d) 指示手势 图 4.2手模型的变形结果 21 中国科学技术大学本科毕业论文 2.2材料感知 在线性弹性材料模型中, 有五个参数: 杨氏模量, 泊松比, 体积模量, 拉梅参数, 和剪切模量. 它们可以由其中任意两个确定. 下面的实验中, 我们通过调整参数来 定性验证我们的形变算法对于材料特性的考虑. (a) 原型 (b) 均匀材料(c) 左半段设为剪切模量较高的材料 图 4.3长棍的变形结果 (a) 泊松比为正时的拉伸和压缩效果 (b) 泊松比为负时的拉伸和压缩效果 图 4.4方体变形结果 22 中国科学技术大学本科毕业论文 从图4.3c中可以看出, 我们对于剪切模量的控制调整了长棍对于切向应变的 反应, 较好地符合了预期. 图4.4中, 泊松比为横向应变与轴向应变比值的相反数. 常见材料的泊松比为正, 体现在拉伸会导致横向的收缩. 反之, 对于一些 “拉胀” 材料, 如纸张和一些矿物 11, 受内部结构影响, 拉伸反而会导致横向的膨胀. 我 们的线性弹性模型也可以较好地刻画这个性质. 进一步地, 我们可以通过利用定义材料特性, 来进行更真实的模型编辑. 如 图4.5, 我们对马模型嘴部的控制, 在均匀材料的情况下, 导致整个马头的扭曲. 然 而, 我们通过对整个头部设置较高的硬度 (体现在较高的剪切模量与杨氏模量), 可以将扭曲的 “任务” 更多地交给脖子, 得到更为真实的效果. (a) 原型(b) 设定均匀材料 (c) 头部设置为较高剪切模 量与杨氏模量 图 4.5马模型的变形结果 23 中国科学技术大学本科毕业论文 第五章总结与展望 本文介绍了一个基于材料特性和物理性质, 对三维四面体网格进行操作的形 变算法. 我们的算法具有相对易用, 实时, 直观, 可扩展和通用的特点. 通过附加适 当的属性, 模型设计者可以较为直观地编辑和制作模型. 1. 我们采用了 8 的微分框架, 通过线性弹性材料理论, 得到了基于材料物理 特性的二次微分能量. 为了保持旋转不变性, 采用迭代修正的方法. 2. 对能量的求解过程中, 通过适当的处理, 得以采用 Cholesky 预分解方法, 这 不仅达到了很高的实时性, 还使得迭代算法也可以接近实时化. 3. 为了进一步加快迭代过程的收敛速率同时允许多控制柄同时操控, 算法应 用了文章 1 中提出的可交换的矩阵代数. 4. 最后, 通过实现和实验结果可以看出, 我们的算法对于所规定的材料特性有 着定性的体现. 与此同时, 我们的方法还有一些方面, 由于个人时间和精力的限制, 没有进行 进一步的完善. 以下几点可以作为未来工作: 迭代过程的收敛性还没有严格证明. 这个证明的意义不光是数学上的完备, 同时, 通过更加细致的分析, 我们可能得到更好的寻找迭代初值的方法, 与 更快的收敛速度. 用户对控制柄的控制作为能量中软约束, 可能不会在优化过程中完全保持 预期的位置. 而在有些情况下, 用户却是并不需要其完全保持的. 我们可以 考虑提供分级的自适应权重, 即让用户指定对应的控制柄的贴合程度, 然后 算法计算得到能量中相应的权重. 对于更加复杂的网格, 可以通过并行化或模型简化的手段处理. 实现的程序中对于模型材料的体现更多的是定性上的, 如果想要更准确的 材料特性, 还需要更仔细的对能量中参数的调节. 目前对于模型内部的控制有限, 需要更好的交互手段对内部的材质或控制 区进行操作. 24 中国科学技术大学本科毕业论文 参考文献 1 M.Alexa. Linearcombinationoftransformations. ACMTransactionsonGraphics (TOG), 21(3):380387, 2002. 2 A. Edward.Interactive Computer Graphics: A Top-Down App