（计算机应用技术专业论文）基于草绘的网格模型变形算法研究.pdf

浙江大学硕士学位论文 摘要 摘要 3 d 模型变形技术在工业设计、模具生产、零部件加工、动画制作等领域有 着广泛的应用。传统的模型变形技术操作复杂、效率低下，针对这个问题，本文 对交互式网格模型变形技术展开研究，利用草绘曲线控制网格形状。 为了在变形过程中有效控制网格模型的表面微分性质，引入l a p l a c e 算子并 加以改进，实现了对模型表面法向和曲率的直接操作。利用离散的l a p l a c e 算子 构建线性方程组并运用最小二乘法进行求解，为网格模型的渐变效果提供了理论 依据。为了实现交互的变形操作，使用轮廓线对网格模型进行控制。首先根据网 格顶点的法向信息，利用网格顶点插值出网格边上的轮廓点；然后再将序列化的 轮廓点映射到用户交互绘制的条草图线上，通过解线性方程组求出变形后各顶 点的新坐标。另外，对于特定的感兴趣区域，通过绘制草图线可以对曲线周围各 项点的曲率进行调整，构造显著的模型特征。 由于传统的网格曲面编辑技术只能对模型的特征进行近似控制，本文提出一 种精确的特征控制方法，使得模型特征在整体曲面变形中保持原有形状。首先提 取形状特征的位置信息，作为变形过程中的刚性约束；然后根据改进的离散 l a p l a c e 算子建立反映网格曲面微分性质的柔性约束；最后采用拉格朗日条件极值 法建立线性方程组，求解刚性约束完全满足条件下的最优解，在保持形状特征的 同时实现网格曲面的整体变形。变形效果易于控制，且操作直观，可用于交互式 编辑操作。 关键词：网格变形；草绘；l a p l a c e 算子；侧影轮廓线；特征保持 浙江大学硕士学位论文a b s t r a c t a b st r a c t 3 d - m o d e ld e f o r m a t i o ni sw i d e l yu s e di ns u c ha r e a sa si n d u s t r i o u sd e s i g n ，m o d e l p r o d u c i n g ，a c c e s s o r yp r o c e s s i n g a n d3 da n i m a t i o n s t r a d i t i o n a ld e f o r m a t i o n t e c h n i q u e s a r et o oc o m p l i c a t e da n di n e f f i c i e n tt om a n a g e t os o l v et h i sp r o b l e m ， i n t e r a c t i v em e s hm o d e ld e f o r m a t i o nb a s e do ns k e t c h e si ss t u d i e d i no r d e rt oc o n t r o lt h ed i f f e r e n t i a lp r o p e r t yo ft h em e s hs u r f a c ei nt h ed e f o r m a t i o n p r o c e s s ，t h el a p l a c eo p e r a t o ri si n t r o d u c e da n dt h e ni m p r o v e dt om a n i p u l a t et h e n o r m a la n dc u r v a t u r eo fm o d e ls u r f a c ed i r e c t l y as y s t e mo fl i n e a re q u a t i o n sf o u n d e d o nd i s c r e t el a p l a c eo p e r a t o ri ss o l v e di nt h el e a s t s q u a r e ss e n s ea n dp r o v i d ea t h e o r e t i c a lp r o o ff o rt h er e a s o n a b l ed e f o r m a t i o no fm e s hm o d e l t oi m p l e m e n tt h e d e f o r m a t i o nm e t h o d ，t h es i l h o u e t t ei si n v o l v e dt oc o n t r o lt h em e s hm o d e l f i r s t l y , a s i l h o u e t t ei si n t e r p o l a t e do ne d g e so ft h em e s ha c c o r d i n gt ot h en o r m a lo fv e r t i c e s t h e nt h es e r i a l i z e ds i l h o u e t t ep o i n t sa r ep r o j e c t e dt oal i n es k e t c h e db yt h eu s e r i n t e r a c t i v e l ya n dt h en e wc o o r d i n a t eo fv e r t i c e sa r ca c h i e v e da f t e rs o l v i n gt h el i n e a r e q u a t i o n s i na d d i t i o n ，w h e nas k e t c hl i n ei sd r a w no nas p e c i f i e dr e g i o no fi n t e r e s t ，i t c a nc r e a t ear e m a r k a b l ef e a t u r ew i t ht h ec u r v a t u r eo fv e r t i c e sa l o n gt h el i n et u n e d t h et r a d i t i o n a ll h e s h e d i t i n gt e c h n i q u e sa l w a y sp r o c e s st h e f o r m - f e a t u r e s a p p r o x i m a t e l y t op r e s e r v ef o r m f e a t u r e si nag l o b a lm e s hd e f o r m a t i o n ，t h i st h e s i sp u t f o r w a r da ne x a c tm e s h - c o n t r o lm e t h o d a tf i r s t , t h el o c a li n f o r m a t i o no ff o r m f e a t u r e s i se x t r a c t e da sh a r dc o n s t r a i n t sf o rm e s hd e f o r m a t i o n ，a n dt h e ns o f tc o n s t r a i n t sa r e b u i l tu s i n gd i s c r e t el a p l a c eo p e r a t o r a tl a s t ，as y s t e mo fl i n e a re q u a t i o n se s t a b l i s h e d u n d e rl a g r a n g em u l t i p l i e r si ss o l v e dw i t ht h eh a r dc o n s t r a i n t se x a c t l ys a t i s f i e d t h a t p r o d u c e st h eg l o b a lm e s hs u r f a c ed e f o r m a t i o nw i t hf o r m - f e a t u r e sp r e s e r v e d i t s i n t u i t i v ea n de a s yt oc o n t r o la n dc a nb eu s e di nt h ei n t e r a c t i v ee d i t i n g k e y w o r d s ：m e s hd e f o r m a t i o n ；s k e t c h ；l a p l a c eo p e r a t o r ；s i l h o u e t t e ；f o r m - f e a t u m s p r e s e r v e d 浙江大学硕七学位论文 图目录 图目录 图1 13 d 扫描仪及获取的网格模型数据3 图1 2 基于空间变换的自由变形示例5 图1 3 基于分层的变形方法造成微分特性的丢失5 图1 4 基于解线性方程组的网格变形示例6 图2 1l a p l a c e 伞算子9 图2 2 公式( 2 4 ) 中的v o r o n o i 区域以及余切权值中的ai i 和1 3i j 1 1 图2 3 添加约束后的线性方程组超定。l3 图3 1 利用侧影轮廓线和草图线实施的变形流程1 6 图3 2 侧影轮廓线示例17 图3 3 轮廓点存在的必要条件18 图3 4 轮廓顶点序列化1 9 图3 5 利用轮廓线控制飞机模型的变形操作过程2 1 图3 6 利用轮廓线与草绘线的变形效果2 2 图3 7 利用草图线创建模型特征流程2 4 图3 8 和草图线最接近的网格路径2 5 图3 9 切向平移控制顶点。2 6 图3 1 0 网格路径投影到草图线上2 6 图3 1l 三角网格优化后的结果2 8 图3 1 2 利用草图线创建的尖锐模型特征2 9 图3 1 3 利用草图线创建的柔和模型特征3 0 图4 1 中间的突起特征在拉伸过程中发生了形变3 7 图4 2 在拉伸过程中，中间的突起特征得到保持。3 9 图4 3 特征区域( 大圆孔) 在拉伸过程中保持原状，其它未选做特征的圆孔 发生形变4 0 图4 4 弯曲变形前后效果对比4 2 图4 5 有无特征保持的弯曲变形效果对比4 3 浙江大学硕士学位论文表目录 表目录 表3 1 模型数据信息及相应处理时间3l 表4 1 深度优先搜索相对位置约束条件( c h 伪代码) 3 6 表4 2 模型数据信息及相应处理时间4 5 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：陈保宇签字日期：2 0 1 0 年1 月2 3 日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：陈保宇导师签名：李际军 签字日期：2 0 1 0 年1 月2 3 日签字日期：2 0 1 0 年1 月2 3 日 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 网格模型变形技术的研究背景 伴随着信息技术的飞速发展，计算机已成为各行各业不可缺少的应用工具， 从机械、电子、航天、冶金化工等传统的工业生产领域，到建筑、医疗器械、教 育、电影、动漫、广告等新兴产业都在计算机技术的帮助下发生翻天覆地的变化。 在工业设计与辅助建模领域，计算机辅助几何设计与制造( c o m p u t e ra i d e d g e o m e t r i cd e s i g na n dm a n u f a c t u r e ，即c a g d c a m ) 已经成为一个重要的研究方 向。通过利用计算机进行实体建模操作，可以大大缩短设计周期，提高工业生产 的效率，增强综合竞争力【l - 3 】。 计算机表示的实体模型是物理几何模型的数字化。实体模型现在广泛应用在 各个工业领域，从娱乐行业到卫生保健行业都有其身影。如今，它们在零部件制 造领域扮演着重要角色，在这些工业生产行业中通常采用实体建模软件( 或更一 般的称为c a d 软件) 来精确完成模型部件的生产和组装【4 捌。在工业设计领域， 设计过程通常是递增式的进行，在达到满意的目标之前一般需要反复的修改或补 充。设计师可能会指定一些顶点、曲线或曲面，并把它们组合起来实现对物体边 界的数字化定义，或者他们会选择一些模型作为设计原型，如立方体、球体等， 定义其维度、位置与方向，然后利用求并、求交或求补运算对这些模型进行组合。 最后得出的物体是一个明确的、完备的、详细的数字化几何模型或更多模型的组 合，诸如汽车引擎或飞机模型。另一方面，模型处理技术在数字电影制作、动画 角色构建与游戏制作中也有巨大的应用需求，甚至可以说计算机特效技术已成为 影视制作中不可或缺的一部分 6 - 9 。如今，3 d 动画与3 d 游戏的盛行也显示了数 字建模的魅力。通过计算机构建的虚拟世界已成为越来越多人关注的焦点，它不 仅能够还原人们生活中常见的场景，而且还能创造出我们头脑中幻想的影像，i l m ( 工业光魔) 与p i x a r 公司的成功充分体现了3 d 建模技术的强大生命力。 浙江大学硕士学位论文第l 章绪论 3 d 模型处理系统应用在工业设计的方方面面，诸如机械部件设计、建筑构 图以及在动画电影中绘制形形色色的场景。计算机建模已经在很多领域取代了传 统的绘画与物理建模。在传统的建模要求中，为了构建精确3 d 模型，通常需要 采用非直观的模型控制方法，设定一系列复杂的控制参数，导致用户界面非常复 杂，需要具备专业的技巧和丰富的经验才能有效完成操作任务，不利于大规模推 广应用。尽管这些系统能够有效而精确地生成3 d 模型，但对于精度要求不高或 粗糙建模的应用程序来说却显得并不合适。 现在的3 d 数字模型通常可以分为两类：一类是由连续的曲线曲面( 如：球 面、n u r b s 曲线曲面等【1 0 】) 表示的模型，另一类是由离散项点构成的点云或网 格模型【i l 】。前者能够很好的表达物理模型的特性，具有逼真度高、流线型等优点， 但这类模型通常较为简单，如果要表达更为复杂的模型，则必须由简单模型进行 组合拼接。因为这类模型必须由特定的参数进行设定，所以一旦需要进行变形或 修正操作，实际上就是对参数进行重新设定。但是它有两个缺点：第一，参数指 定不直观，不方便普通用户操作；第二，对于分块拼接的模型，在某一面片参数 重新设置后难以保证与相邻面片的光顺连接，不利于模型的统一操作。 鉴于连续模型处理的种种不利因素，很多实际应用中都是采用离散数据表示 数字模型。对离散模型的研究早已深入而广泛的展开 1 2 , 1 3 ，不论是离散模型的表 示，还是离散数据的处理，都已显示出这类技术的巨大应用潜力。离散模型最重 要的优点就是数据直观，模型表现力强。离散模型的数据获取简单，不仅可以利 用建模软件生成简单数据，而且可以利用3 d 扫描仪获得复杂数据。通过对实际 物体进行扫描( 如图1 1 所示) ，捕获3 d 实体表面，由此生成的原始数据经过过 滤、优化处理可以得到所需要的数字化模型。 2 圈113 d 扫描仪噩获取的耐格模型觳据 离散数据模型已经获得了广泛的认可，在工业设计领域已经出现了众多的离 散模型处理系统。针对点云数据，现在已经推出了多种网格化技术可以很方便 地转化为网格数据，因此本文着重于研究对网格模型的处理操作。 在工业化设计的前期，设计师通常会创作一些3 d 原型，以方便开发团队对 设计需求进行有效的评估。设计前期的评估可以帮助设计师理解产品要求，节约 生产成本，保证产品质量，方便用户维护。一般来说3 d 原型较为简单，只能反 映产品的初始形态，这是因为在设计初期总是伴随着反复的评估与概念修正如 果投入大量时间创建详细的扔期3 d 模型，那么也需要耗费大量精力进行修改， 不利于成本控制。一旦达到评估要求，产品概念敲定，设计师就可以在3 d 原型 上进行创作，对模型进行编辑操作。另外，逆向工程中通过扫描仪获得的3 d 数 据也可以作为设计的原型。在工程应用中，往往会提出各种新的设计需求，在原 模型的基础上进行变形以达到其设讣目标，不仅能保持设计理念的一致性还可 以大大节约设计成本。总之，网格模型变形技术的应用前景十分广阔，不论是汽 车零部件的设计，还是动画角色的修正，都需要变形技术的支持。 传统的模型创作工具过于复杂，它们主要是面向专家用户设计，难 三【推广应 用。为了简化建模过程，交互式创建直观易于理解的模型，逐渐发展出基于草绘 的模型操作方法。草图绘制操作简单，不需要用户进行复杂的参数设置，只需要 在二维屏幕上拖动鼠标或利用触摸屏技术即可实现全部操作。通过将草绘操作引 浙江大学硕士学位论文 第l 章绪论 入网格模型变形中实现了操作的简化，而且变形效果易于观察，为用户提供了快 速的图形化反馈，支持交互式创作。 1 2 网格模型变形技术的研究现状 在几何建模领域，模型变形技术是一个非常活跃的研究领域，它的应用覆盖 了从工业设计到艺术加工的范围。变形技术经过了几十年的发展，已经取得了突 出的成就【悼1 9 1 。现有的造型技术应用在工业生产领域，帮助设计师设计更生动活 泼、丰富多彩的实体模型，简化了用户的模型设计过程。 常规的建模手段分为两类。一类是利用连续的解析曲面进行建模，如张量积 曲面、样条曲面等，它具有函数表达精确、数学建模方便等优点，可以通过对曲 面控制网格的编辑达到曲面变形的目的。但是解析曲面的变形操作不够直观，需 要间接对参数进行事先估算或不断修正才能达到预期的变形效果，不利于交互式 编辑操作。另一类是基于离散数据的网格模型。利用简单的多边形面片拼接成网 格状的模型，数据关系简单一致，便于处理。网格模型应用广泛，可以适应多种 建模需要，而且操作直观，反馈快捷，有利于交互式模型编辑操作。网格模型变 形技术经过多年发展，现已日趋成熟，在工业生产应用中已经取得很好的效果。 现在的网格模型编辑技术主要建立在以下几种变形思想之上。一、基于空间变换 的自由曲线曲面变形。二、基于多层次、不同细节程度的变形。三、利用线性方 程组解决二次能量函数最小化问题。 自由变形技术 2 0 - 2 8 】是计算机图形学领域应用非常广泛的类方法，通过对模 型所在的空间进行重新映射来达到对物体变形的目的( 如图1 2 所示) 。尽管能够 利用对模型空间格子进行的操作实现对模型的控制，但由于操作的间接性，导致 变形结果不易控制，往往达不到预期目的。尤其对于特定的约束条件，自由变形 实现起来较为复杂，因为对控制端的操作并不是直接作用在几何物体上，难以控 制最终变形效果。 4 斯太目 位论女 囊一：霪- i 。j 茁12 基于空间变换的胄由变形示倒 基于分层思想的变形方法1 2 9 1 将模型划分为不同的细节层次，每一层次群在上 一层的基础上增加细节表现。首先，忽略模型细节提取整体特征然后对模型进 行整体变形，最后再根据相对位置将细节还原到变形模型上，实现对模型的编辑 操作。b o t s c h 3 0 将这种方法应用在交互网格编辑中；通过在低分辨层次下交互变 形，然后利用高分辨层次的细节来修复模型，以保持几何特征。但是在细节还原 的时候难以保证其微分特性( 如图13 所示) 。在此基础上发展而来的基于骨架 捌的变形方法采用了非线性的手段实现对模型的控制，但选代过程计算复杂， 不利于交互式变形操作。 名 r _ 1 图13 基于分屡的变形方法遣成徽分特性的丢失 为了在交互式变形过程中加强对模型微分性质的控制，s o r k i n e 等口3 疑出利用 新江 m 论立 第1 绪* 曲面微分特性建立线性方程组从而保证在变形过程中能够有效保持网格微分细 节如图l4 所示。对于离散的网播模犁，利用顶点与周围疆点的邻接关系，构 造离散l 印l a c e 算子以记录同格表面各项点的微分性质。离散l 叩l e 算子肚3 日是由 一个顶点与其周围邻接点的加权均值点之间的差值向量来表示，如果采用余切权 值则该l a p l a c e 算子就可以近似表示该顶点的平均曲率。n e a l e n 等口7 疆出一种基于 草图的l a p l a c e 变形方法；周昆等m 睫出了利用l 印l a 算子控制变形后模型的体 积。z i i 肿e 肿蛐等o ”提出了一种轮廓线对网格变形的控制方法，s e h m i d t 等呻荆 用草图线宴现了对模型的变形与组合。 -k 矿 圈14 基于解线性方程组的搠格变形示侧 目前的网格变形方法在动画设计、人物嫱型等领域能取得很好的效果，但很 难达到工程设计的精度要求，即使对特征约束条件添加较大的权值也未必能取得 所要求的效果。w e l c h 等h 1 删在曲面建模过程中对不同的约束条件区分处理，利 用条件极值法求解线性方程组，取得了较好的效果。在网格编辑过程中针对网格 曲面的法向可能会有不同的要求。对于拉伸或压缩操作，需要尽量保持原有法向： 然而对于弯曲或折叠操作则需要对所有点的涪向进行适当的旋转以保持曲面的 浙江大学硕士学位论文第i 章绪论 光顺过渡。对于较小的旋转角度，s o r k i n e 等【3 3 】采用解线性矩阵来近似实现旋转 操作。z a y e r 等【4 3 】利用四元数代替旋转矩阵实现法向的旋转操作，通过对四元数 进行插值求取各个顶点的法向旋转量。四元数能够实现快速有效的向量旋转，而 不必计算复杂的旋转矩阵。 1 3 本文研究目标 传统的3 d 模型处理工具都是为精确控制复杂模型而设计的，所以操作手段 过于复杂，对普通用户来说很难上手。为提供简单易使用的模型处理手段，本文 对网格模型变形方法进行研究，提出了一种易于操作和实现的网格变形算法，采 用草绘曲线对网格模型进行控制，避免了用户对参数的直接操作，大大简化了模 型处理复杂度。通过利用离散的l a p l a c e 算子建立线性方程组，实现对网格模型 微分特性的控制。对于特征区域提取其侧影轮廓线作为特征线，然后利用草绘操 作为特征区域指定新的特征线，实现侧影轮廓线到草绘曲线的映射。通过解线性 方程组完成特征区域的变形操作。由于方程组是由离散的l a p l a c e 算子构建，所 以在解方程的过程中，特征区域的微分特性得到了最大限度的保留，使得变形后 的曲面保持了良好的局部细节和视觉效果。由于离散l a p l a c e 算子自身的特性， 由此构造出线性方程组的系数矩阵是稀疏的，可以利用解稀疏矩阵的工具对方程 组进行快速求解，从而达到交互式操作的要求。 在此基础上，为了达到工程应用中对模型精度的要求，本文按照工程约束条 件的苛刻程度，将其划分为柔性约束条件和刚性约束条件。对于刚性约束条件， 必须保证条件的完全满足，而对于柔性约束条件则可以在一定的值域范围内进行 权衡。为了保证刚性约束条件的严格执行，根据拉格朗日条件极值法，将拉格朗 日乘子引入线性方程组的构建，利用最小二乘法对线性方程组进行求解，最终得 到期望的变形效果。 本文提出的变形操作易于控制，只要在二维平面上简单的绘制或拖动控制 端，就可以对3 d 网格模型实现变形，变形效果直观。 浙江大学硕士学位论文第1 章绪论 1 4 本文结构 后续章节结构安排如下： 第2 章详细阐述离散l a p l a c e 算子的构建方法，给出数学定义及几何意义； 介绍基于离散l a p l a c e 算子的网格模型变形方法原理，以及如何利用最小二乘法 求解超定线性方程组。 第3 章阐述网格模型侧影轮廓线的提取方法，以及如何将其映射到草绘曲 线上，实现对模型外观的控制；利用草绘曲线调整网格表面细节，然后在模型上 创建尖锐及柔和的模型特征。 第4 章阐述拉格朗日条件极值法的具体应用，构造新的l a p l a c e 方程组；介 绍刚性及柔性约束的区分，以及如何利用四元数快速实现法向旋转量的计算；介 绍如何完成具体的伸缩和弯曲变形应用。 第5 章总结全文，迸一步提出新的研究方向。 8 ! ! ! ! ! ! 丛! 兰苎! ! ! ! ! 生堕堑! ! ! ! ! ! ! ! ! 第2 章基于l a p l a e o 算子的网格模型变形框架 2 1 高散! 的l a p l a c o 算子 一般来说，网格模型由一个图结构表示：g = ( v e ) 其中v 表示顶点的集台， e 表示连接顶点的边的集合。设v = ( v 1 ，2 ，v n ) ，其中v i = ( x 。，y i , z i ) r 3 ，咀顶 点集v 表示原始的几何模型，v 表示变形后的几何模型。为了方便处理，通常采 片j 三角网格来记录边集e 的信息，即使是其它类型的多边形阿格也可很方便地转 化为三角网格。 为了在变形操作中保存网格的微分细节，需要一种记录网格顶点之间戈系的 因子。直觉上，对每个顶点的坐标与其周围邻接顶点坐标的线性组台能够表达这 一关系。即公式( 2 1 ) 所示的l a p l a c e 伞算子1 l ( v 。) 其中v ，表示顶点i 的坐标， v 表示与顶点i 邻接的各顶点坐标，d 表示顶点i 的邻接顶点个数。 l ( v ) = v _ 一v ， ( 21 ) “l 0 】f l a p l a c e 伞算子表示一个顶点i 邻接顶点的均值到该顶点i 的方向向量，其几何 意义如图2i 所示，它形如一把撑开的伞。这就是l 冲1 a c e 伞算子这个名字的由柬。 圉2 1l a p l a c e 伞算子 可以把公式( 2i ) 改写成如下形式，得到公式( 2 2 浙江大学硕士学位论文第2 章基于l a p l a 算子的网格模型变形框架 l ( v i ) - 玄。留t - v j ) q 2 从微分几何的角度来看，如果假设网格模型g 是对一个光滑曲面的离散逼近， 那么l ( v i ) 可以视为l a p l a c e b e l t r a m i 算子的离散化表示【4 5 1 ，公式( 2 2 ) 就是公式 ( 2 3 ) m 】的离散化逼近。其中n ( v i ) 为点v i 处的平均曲率，n i 为曲面在点v i 处的 单位法向。 l ( v i ) 2 1 1 i m 1 ，l y ( v i v ) d l ( v ) = 一h ( v i ) n i 2 3 因此，l a p l a c e 伞算子似乎可以近似表示某一顶点处的平均曲率与法向。不过 这一规则并非完美。当项点i 与周围邻接顶点处于同一平面时，可以认为该点处的 法向就是该平面的法向，该点的曲率为0 。但是，由公式( 2 1 ) 计算出的算子值 可能出现非零向量，且其指向并非平面的法向。根据m e y e 等【4 7 】的研究表明，采 用均一化的权因子一1 并非最佳选择，应该采用更为精确的权因子构造平均曲率法 d i 向( m e a nc u r v a t u r en o r m a l ) 的离散逼近值，如公式( 2 4 ) 所示。其中a i 表示顶 点i 周围的v 0 r o n o i 区域面积之和( 如图2 2 所示) ，a o 和6 d 是边( i ，j ) 所对的两个 角，具体如图2 2 所示。 l ( v i ) 2 瓦1 ( i ，惟( c o t o i j + c o t l 3 。) ( v i - - v j ) 2 - 4 l o 浙江大学硕士学位论文 第2 章基于l a p l a c e 算子的网垫模型变形框架 图2 2 公式( 2 4 ) 中的v o r o n o i 区域以及余切权值中的a 和bi j 采用余切值权因子的l a p l a c e 算子有效地记录了模型表面的曲率与法向信息， 不仅可以实现网格的平移变形操作，对于法向的旋转与曲率的缩放控制同样表现 出良好的稳定性。 2 2 l a p l a c e 变形框架 2 2 1l a p l a c e 变形的核心 在网格变形操作就是对网格顶点信息进行重置。设变形后的各顶点坐标为v ， 根据公式( 2 4 ) 可以建立如公式( 2 5 ) 所示的方程： 去。警僦0 j | j + c o t p 】| i ) ( v ；_ v j ) = 击。番似j 【j + c o t b i ) ( v i t - v j t ) q 5 由于变形过程对v o r o n o i 区域面积a i 的变化不予考虑，所以方程两端可以消 除a i 。重新构造出改进的l a p l a c e 算子，如公式( 2 6 ) 所示，其中权因子w i i 由 公式( 2 7 ) 定义。 浙江大学硕：e 学位论文 第2 章基于l a p l a c e 算亍的随模跫变形框架 e w 日v j 伞k 一透百 i ，j e e w i j = c o t c t i j + c o t l 3 日 ( 2 6 ) ( 2 7 ) 针对每个顶点根据l a p l a c e 算子建立方程，所有顶点的l a p l a c e 算子构成集 合a - - a i ，。为尽量保持变形前后的微分特征，变形后的顶点集合可由公式( 2 8 ) 决定，其中w 表示满足特定约束条件的模型v 的变形。 v = a r g m i n0 ( v ) 一( w ) 旷 ( 2 8 ) w 式( 2 8 ) 的二次能量方程表示在变形过程中，需要在变形控制条件与保持原 始模型的微分特性之间进行权衡。通常这一问题的求解是利用最小二乘法计算线 性方程组a x = b 。以下章节的网格变形操作都是基于这一理论基础。 2 2 2 建立基本的线性方程组 在网格变形过程中，针对不同的变形目的会有不同的约束条件。为了保证对 模型曲面微分特性的控制，首先要考虑的就是l a p l a c e 算子的方程。根据公式( 2 6 ) 建立方程( 2 9 ) ，实现变形前后微分特性的一致性。左侧的v 表示变化后的网格 顶点信息，右侧为已经利用公式( 2 6 ) 求出来的l a p l a c e 算子值。 乞w v j v i 掣 一= a i ( 2 9 ) 厶w o “j e e 为了实现模型的变形，还要增加控制顶点的位置约束。位置约束一般分为两 类，一类是维持边界稳定性的固定点，另一类是对模型变形效果进行控制的可控 点。可控点的坐标一般靠草绘线进行设定，也可以通过鼠标拖动实现对控制顶点 坐标值的设定，任何一种设置都是在原顶点坐标的基础上加上一个偏移量。方程 ( 2 1 0 ) 的两个式子表达了位置约束条件，v i 表示固定点，v k 表示可控点。 h 2vj(210) 【v k _ v k + d i s t k 假设网格模型共有n 个顶点，那么由( 2 9 ) 式就可以得到n 个方程。另外根据 用户具体的操作，还会自动生成m 个像( 2 1 0 ) 式一样的约束方程。由于约束条 件过多，导致方程组a v = b 超定( o v e r d e t e r m i n e d ) ( 如图2 3 所示) ，不能( 也不 需要) 求取精确解，所以必须利用正规方程组( n o r m a le q u a t i o n ) a t a v ，= a t b 来 代替原方程组进行求解。正规方程组的解与原方程组的最小二乘解互为充要，只 要求出正规方程组的精确解即可作为原方程组的最小二乘解。 n 厂 、弋 厂 弋 ( 。 1 图2 3 添加约束后的线性方程组超定 由方程( 2 9 ) 和( 2 1 0 ) 可知，每个方程中系数的个数相对于n 来说都是很 少的( 尤其对于规模较大的网格模型) ，即矩阵a 为稀疏矩阵，所以正规方程组 的系数矩阵a t a 也是相对稀疏的。利用现有的解稀疏线性方程组的工具可以快速 求解，本文的示例皆采用t a u c s 4 s 与u m f p a c k l 4 9 库求解。g o u i d 等1 5 0 】对其它 工具库的性能与适用情况做了评估和比较。 浙江大学硕士学位论文 第2 章基于l a p l a c e 算子的网格模型变形框架 + 2 3 本章小结 本章对基于离散l a p l a c e 算子的网格模型变形框架进行了阐述，详细介绍了 l a p l a c e 算子与网格微分特性的密切关系，并给出了一个采用余切权值的离散 l a p l a c e 算子建立方法，利用该方法能够有效控制网格的法向和曲率特性。然后给 出了一个基于l a p l a c e 算子的稀疏线性方程组的构建方法，并给出了解法。 1 4 浙江大学硕士学位论文第3 章利用侧影轮廓线和草图线实现部分网格变形 第3 章利用侧影轮廓线和草图线实现部分网格变形 3 1 利用侧影轮廓线和草图线实现变形 3 1 i 指导思想 通过草图画出图形的外形轮廓，就能够表现出一个模型的主要特征。操作起 来直观方便，这就是为什么设计师们总喜欢用纸和笔进行创作和交流。因此可以 考虑利用草图线来控制模型的形状。现在已经出现了一些基于草绘的建模方法 ( 如：s k e t c h 1 4 1 、t e d d y 1 5 1 、s m o o t h s k e t c h l l 6 等) ，并且在实际中也获得了广泛 的应用( 如：s h a p e s h o p l l 9 】等) 。这些建模方法通常只能创造出较为简单粗略的网 格模型，在实际应用中还需要进一步的编辑和变形处理。 为了实现对网格模型形状的控制，我们采用侧影轮廓线和草图线对感兴趣的 区域进行操作。在离散l a p l a c e 算子所构建的线性方程组的基础上，增加侧影轮廓 线上的虚拟顶点作为控制条件，通过将轮廓线上的控制顶点映射到草图曲线的相 应位置上，实现控制顶点位置的重新设置。利用最小二乘法求解离散l a p l a c e 算子 建立的方程组，将控制顶点的位移量适宜的分散到区域内的各项点，使得模型的 微分细节得到最大程度的保持，从而达到预期的变形目的。具体的操作步骤如图 3 1 所示。 1 5 浙江大学硕士学位论文第3 章利用侧影轮廓线和草图线实现部分网格变形 图3 1 利用侧影轮廓线和草图线实施的变形流程 变形区域通常是用户利用交互式操作方法进行设置，简单的方法是利用鼠标 进行框选，获取该区域中所有顶点。下面介绍针对选取区域提取侧影轮廓线，以 及利用虚拟顶点构造映射方程。 3 1 2 侧影轮廓线的提取 在三维空间中，侧影轮廓线是物体投射到观察者眼中的外围边晃曲线。理论 上来说，轮廓线应该是一条连续曲线，且对应表面各点处的法向量与视线方向垂 直，这样曲线前侧的表面就处于视线观察范围之内，而后侧的表面则被前表面所 遮挡。由此设某点v 法向量为n ，视点c 到v 点的向量为v i c ，则应有如下关系： n ( v c ) = o 。对于离散项点构成的网格模型，无法保证各项点处的法向一定具备这 种性质，所以不能简单计算。 从网格模型中提取侧影轮廓线的方法多种多样 3 9 , 5 1 , 5 2 】，考虑到具体应用，本 文采用顶点插值思想，快速生成网格模型轮廓线。首先，根据顶点法向判断识别 出轮廓线上的网格边，再利用线性插值计算出轮廓线上的离散点，最后顺序连接 所有离散点构造出一条侧影轮廓线的逼近曲线，如图3 2 所示。 1 6 * 江 学女弟3 w 用嘲# 4 8 自$ 围绕窑现日分目括变 围3 2 舅影轮霸线示倒 提取侧影轮廓线的具体步骤如下： 1 对变形区域内的所有顶点计算其法向量与视线向量的内积：v a l ，= n 。( v ，c ) 。 如果v a l 。2 0 ，则说明视线方向与该点法向成锐角即该点法向是指向“后”的，在 视点上该点不可见：如果v a l ( 0 ，月视线方向与该点法向成钝角，法向指向“前”， 4 说明该点可见。更进步可得出论断：若一条边的两端点的v a l 值分别为一正 一负，则该边必定跨越侧影轮廓线，也就是说例影轮廓线必经过该边上某一点。 一个合理的做法是：取两端点的线性插值点作为轮廓线上的点。 2 对区域中的所有i 角面，判断其3 个顶点的v a l 值是否同号( 这里之所以 采用三角面，是因为处理较方便，而且其他类型的多边形可以根容易分割为三角 形进行处理) 。若为否，则说明必然是两正( = 0 ) 一负( 0 ) 或两负一正。设v a l 值与另两个顶点不同号的顶点为”o ，另两个顶点按逆时针顺序依次为o l 、0 2 ， 如 图3 3 所示。( 顶点旁边的圆括号内的+ 、号表示该点v a l 值的符号) 浙江大学硕七学位论文第3 章利用侧影轮廓线和草 冬l 线实现部分网格变形 v o ( + ) v o ( 一) 2 v 1 ( _ ) v 2 ( 一)v 1 ( + )v 2 ( + ) 图3 3 轮廓点存在的必要条件 3 分别在线段v o v l 和r o y 2 上按对应顶点的v a l i 值取内比分点p l 和1 ) 2 ( 如图3 3 所示) ，将a x e 记录在轮廓点集s 中。当区域中所有的三角面都处理完毕， 就得到了轮廓线与所有网格边相交的点，即轮廓点。 4 经过上一步的处理得到了所有的潜在轮廓点，但是这些点是无序且冗余 的。为了在下一步能将所有轮廓点映射到草图线上，必须将轮廓点依次排序。轮 廓点序列化的依据是充分利用重复记录的冗余信息：如果一个轮廓点多次出现， 说明它存在于多个相邻的网格多边形中( 对于m a n i f o l d - - 角网格，最多只可能同 时落在两个相邻三角面片上) ，那么这个轮廓点必定连接着另外的两个轮廓点。 首先搜索轮廓点集s ，找出其中只出现一次的点，作为整个轮廓线的两个端点( 图 3 4 中的黄色点) ，设定其中一点为起始点s t a r t ，另一点为终止点e n d 。然后从s t a r t 点所在的点对 中的另一点( 1 i p p o 点) 开始进行匹配判断。所谓匹配判断， 就是判断该a p i 是否与其他点对中的一点重合，如果重合，则表示匹配成功；否 则，匹配失败。每次p i 点匹配成功后，就把p i 力口入轮廓点序列表中，然后对匹配点 对 的另- - a ( 即p i + 1 ) 开始新的匹配判断。如此循环，直至找至u e n d 点。这 样得到最终的轮廓点序列表就是一条离散化的侧影轮廓线。 1 8 浙江大学硕士学化论文第3 章利用侧影轮廓线和草图线实现部分网格变形 e n d 图3 4 轮廓顶点序列化 利用以上步骤可以快速识别出一段侧影轮廓线。如果选中区域造型比较复 杂，存在多条间断的轮廓线，上述方法只能构造出其中一条。若要适应更复杂的 情况，需要改进对轮廓点集s 的序列化过程。首先找出所有只在s 中出现一次的 轮廓点，构成端点集合l 。每次从l 中选择一个端点作为s t a r t 点，进行上述的序 列化过程，直至找到l 中的一个端点作为轮廓线的e n d 点。对于匹配成功的轮廓 点，从s 中删除相应点对。在得到一个有序点列时，与该点列相关的点对都已从 s 中删除，相应的端点也应该从l 中删除。这样就可以从l 中选择新的起始点， 进行新一轮的序列化处理，直到s 或l 为空。最终得到了一系列的侧影轮廓线， 每一条都应该以单独的链表存储记录。显示的时候可以用不同的颜色标示不同的 轮廓线，用户根据需要，交互地选择任一条作为控制线。 1 9 浙江大学硕七学位论文第3 章利用侧影轮廓线和草陶线实现部分网格变形 3 1 3 轮廓线到草图线的映射 为了对网格模型实施变形操作，需要为轮廓线上的离散点指定新的位置。我 们利用鼠标在二维屏幕上进行绘制，记录下鼠标经过的轨迹，这些离散点构成了 一条多边形折线。由于原轮廓线控制点很难直接与草绘顶点建立一一映射，所以 采用n u r b s 曲线代替多边形折线，以便建立均匀的映射关系。 以草绘离散点作为控制点，形成一个控制多边形，采用累加弦长法构造 n u r b s 曲线，将参数区间设定为f 0 ，1 】。由侧影轮廓线上的控制点的数目n ，在新 构造的n u r b s 曲线中，依次求出在参数值为0 ，l ( n 1 ) ，2 ( n 1 ) ，1 的点( n 为侧影轮廓线控制点的个数) ，作为轮廓线上控制点映射的目标点。 以上求映射目标点的过程是在屏幕坐标系下进行，因此还需要将得出的目标 点坐标转换到三维世界坐标系下。为了保证映射效果，首先要将轮廓线控制点坐 标从世界坐标系转换到屏幕坐标系，以取得其屏幕深度，然后将该深度赋给对应 的目标点。这样，就可以保证目标点和相应轮廓线控制点处于同一深