（应用数学专业论文）基于层次b样条的网格曲面编辑技术.pdf

摘要 摘要 随着计算机硬件和3 d 扫描技术的快速发展，离散网格及其处理已经成为几 何造型和计算机图形学领域中的热点研究内容，其研究成果已广泛应用于制造 业，娱乐业，游戏工业等领域 网格曲面编辑是网格处理的核心技术，其目的是为用户提供直观，高效的曲 面编辑手段，实现复杂几何模型的构造近年来，一些学者相继提出了多种网格曲 面编辑算法，归纳起来可分为两类：一类是将曲面嵌入到均匀网格体的f f d 方法 及其扩展，另一类是基于曲面微分属性的编辑方法前者的编辑模式直观，效果便 于控制，但交互方式不够灵活；后者编辑效果较佳，但表达形式特殊，不便与已有 造型系统集成 可见，研究一种交互方式直观，高效可控，表达方式统一的网格编辑方法是 很有意义的鉴于此，本文研究并提出了一种形式统一且能够体现曲面内在几何 属性的多分辨率几何表达方式，该表达方式由逼近曲面的一张光顺的基曲面及 定义在该基曲面上的一组局部变量构成基于该表达方式，我们利用层次b 样条 表示基曲面，提出了一个网格曲面编辑框架，并在该框架中实现了自由变形，几 何细节迁移等功能在框架的处理流程中，用户首先交互地在网格上选取编辑区 域，程序随后完成所选区域的参数化和均匀重采样，并用层次b 样条光顺拟合这 些均匀采样点作为该网格的基曲面，然后计算所选区域中网格顶点相对b 一样条基 曲面的局部变量( 该局部变量具有平移，旋转不变性，可将其视为曲面在编辑过程 中的内蕴几何特征) ，从而可以实现通过编辑层次b 一样条基曲面来达到编辑原网 格曲面的目的利用层次b 样条，还可方便地实现多分辨率编辑借助于直接操纵 的d f f d 方法，该框架也可对网格曲面进行直接编辑，以精确控制编辑结果 在曲面编辑过程中分解得到的局部变量可作为曲面的几何细节，将其映射到 自身变形后的基曲面上即得到变形后的网格曲面，也可将其映射到不同物体的基 曲面上，以实现几何细节的迁移实验结果表叽该方法主要特点是操作直观方 便，无论对整体还是局部编辑，都能取得可控、可靠的编辑效果，且采用b 样条表 达方式易于与已有的造型和动画系统合成 关键词：网格曲面，几何细节，特征映射，层次变形，层次b 样条 a b s t r a c t w i mt h er a p i dd e v e l o p m e n to f3 ds c a n n i n gt e c h n o l o g y , m e s hp r o c e s s i n gh a sb e c o m eo n eo ft h eh o t t e s tt o p i c si ng e o m e t r ym o d e l l i n ga sw e l la sc o m p u t e rg r a p h i c s a n di t sr e s e a r c hr e s u l t sh a v eb e e nw i d e l ya p p l i e di n t oag r e a td e a lo fa r e a s s u c ha s m e c h a n i c a lm a n u f a c t u r e ，m o v i ee n t e r t a i n m e n t ，g a m et e c h n o l o g ya n ds oo n a st h ec o l et e c h n o l o g yo fm e s hp r o c e s s i n g ，m e s he d i t i n ga i m sa tt h ee f f e c t i v e c o n s t r u c t i o no f c o m p l e xg e o m e t r ym o d e l sw i t hi n t u i t i v ea n dh i g h e f f i c i e n c ye d i t i n g a p p r o a c h i nr e c e n ty e a r s ，l o t so f m e s he d i t i n ga l g o r i t h m sh a v eb e e np r o m o t e d ，w h i c h c a nb em a i n l yc l a s s i f i e di n t ot w oc a t e g o r i e s ：t h ef f db a s e de d i t i n gm e t h o d sw h i c h e m b e dt h es u r f a c ei n t o3 du n i f o r ml a t t i c ev o l u m ea n ds u r f a c ed i f f e r e n t i a lp r o p e r t i e s b a s e dm e t h o d s f f dm e t h o dp r o v i d e si n t u i t i v ee d i t i n gm o d ea n de a s y - t o c o n t r o le d i t i n gs t y l c w h i l ei t su s e ri n t e r a c t i o ni sn o tf l e x i b l e 1 1 1 ed i f f e r e n t i a lp r o p e r t i e sb a s e d m e t h o d sc a nb r i n go u t s t a n d i n gd e f o r m a t i o nr e s u l t b u ti ti sd i f f i c u l tt ob ei n t e g r a t e d i n t oe x i s t i n gt e e h n o l o g i e sd u i n gt oi t ss p e c i a lr e p r e s e n t a t i o nf o r m s oi ti sg r e a ti m p o r t a n tt oi n v e s t i g a t eo ne f f e c t i v em e s he d i t i n gm e t h o df e a t u r e d w i t hi n t u i t i v ei n t e r a c t i o n ，e a s y - t o c o n t r o le d i t i n gs t y l ea n du n i f i e dd a t ar e p r e s e n t a t i o n m o t i v a t e db yt h i s ，a nu n i f i e dm u l t i - r e s o l u t i o ng e o m e t r yr e p r e s e n t a t i o nf o r mi sp r o p o s e d i nt h i st h e s i s ，w h i c hp r e c i s e l yd e n o t et h ei n t e r n a lg e o m e t r i cp r o p e r t i e so f s u r f a c e a i l e r t h ed e c o m p o s i t i o no f o r i g i n a ls n l l f a c e ，w ec a ng e tt h eu n i f i e dg e o m e t r yr e p r e s e n t a t i o n f o r mc o n s i s t i n go fas m o o t h i n gb a s es u r f a c ea n dag r o u po fl o c a lv a r i a b l e sd e f i n e do n t h eb a s es u r f a c e u s i n gh i e r a r c h i c a lb - s p l i n e st or e p r e s e n tt h eb a s es u r f a c e , w ec o n s t r u c tac o m p r e h e n s i v ea n dp o w e r f u lm e s he d i t i n gf r a m e w o r ka n di m p l e m e n tm o s to f m e s he d i t i n ga p p l i c a t i o n ss u c h 觞f i e e f o r md e f o r m a t i o n ，g e o m e l r i cd e t a i lt r a n s f e ra n d s oo n d u r i n gt h ep i p e l i n eo f o u rf r a m e w o r k , f i r s tr e g i o no f i n t e r e s t ( r o i ) i ss e l e c t e d i n t e r a e t i v e l yo nt h em e s h t h e nt h er o ii sp a r a m e t e r i z e da n dr e - s a m p l e du n i f o r m l y t h er e - s a m p l e dp o i n t sa r ef i t t e dw i t hh i e r a r c h i c a lb - s p l i n es u r f a c e s t h ei o c a lc o o r - d i n a t e so f t h ev e r t i c e si nt h er o ic o r r e s p o n d i n gt ot h eh i e r a r c h i c a lb - s p l i n es u r f a c e s a r ec o m p u t e d ( t h e s el o c a lv a r i a b l e sa l et r a n s l a t i o na n dr o t a t i o ni n v a r i a n t w h i c hc o u l d b er e g a r d e da si n t r i n s i cg e o m e t r i cv a r i a b l e sf o rt h em e s ha n dr e m a i n e du n c h a n g e dd u r - i n ge d i t i n g ) b a s e do nt h i s ，t h eo r i g i n a lm e s hc o u l db em a n i p u l a t e dt h r o u g he d i t i n g t h eb - s p l i n eb a s es u r f a c ea n dm u l t i - r e s o l u t i o ne d i t i n gc o u l db ea r c h i v e de a s i l y g e n i i a b s t r a c ! e r a l i z i n gd f f dm e t h o dt ot h ef r a m e w o r k ，t h ed i r e c tm e s hm a n i p u l a t i o nc o u l da l s ob e i m p l e m e n t e de f f e c t i v e l y f u r t h e r m o r e ，t h ee x t r a c t i v el o c a lv a r i a b l e sc o u l db em a p p e dt od i f f e r e n tm e s h e s b a s es u r f a c e s t h ef r a m e w o r ka l s oc a nr e a l i z et h eg e o m e t r i cd e t a i lt r a n s f e r e x p e r i - m e n t a lr e s u l t sd e m o n s t r a t et h a to u rm e t h o dp r o v i d e si n t u i t i v ea n dp o w e r f u lo p e r a t i o n s f o rb o t hg l o b a la n dl o c a lm e s he d i t i n g s i n c et h eh i e r a r c h i c a lb s p l i n e sa r ew i d e l ya p - p l i e d ，o u rm e t h o dc a nb es e a m l e s s l yi n t e g r a t e di n t oc u r r e n ta n i m a t i o na n dm o d e l l i n g s y s t e m s k e yw o r d s ： m e s hs u r f a c e ，g e o m e t r yd e t a i l ，f e a t u r em a p p i n g , h i e r a r c h i c a ld e f o r m a - t i o n ，h i e r a r c h i c a lb s p l i n e s 一i 第一章绪论 第一章绪论 近年来，随着计算机软件，硬件和三维测量技术的发展，一种新的几何表达方 式数字几何诞生了! 尽管传统的几何造型技术已经发展了多年，但手工制造几何模型的繁琐过 程大大阻碍了三维几何模型的应用近年来，得益于各种高，中，低档三维激光测 距仪和投影一相杌系统三维几何获取能力的迅速发展，现实世界中的物体数字化 已经不再困难其中最著名的饲予就是s 协1 1 f o r d 大学的d i g i t a lm i c h e l a n g e l op r o j e c t 【l e v o y 2 0 0 0 ( 见图1 1 ) 该项目通过一整套三维扫描硬件和三维重建软件系统完 成了一些大型雕塑的数字化过程，生成的最复杂的三维模型包括2 0 亿个多边形 和7 0 0 0 幅彩色图像作为继声音，图像，视频之后的又一种数据表示方式，三维数 字几何技术可以直接将现实世界中的物体数字化，并可方便地利用计算机来进行 处理，可视化 o d 曲i m m l i n p l o p 删- d s t a r t l e du h e e r s t t i 如b r - n d 啊- 1 b “i l s 州 - n o r h p e rh i 删n u d jr _ z 御n 口i 九p i t a 、 n k l _ 由h d h 如 图1 1三维几何获取能力飞速发展 从多媒体技术的发展历程可以发现，从7 0 年代的数字声音至t j 8 0 年代的数字 图像再至 j 9 0 年代数字视频的出现、普及应用，每种新的多媒体数据都需要新的相 应的处理工具的支持，这就引发了大量关于数字信号处理的研究的出现对每一 种媒体的研究都产生了一门新的学科，如对研究图像的数字图像处理和研究视频 的数字视频处理比较典型的信号处理应用包括：去噪声，压缩，传输，增强，检测， 分析以及编辑等等 第章绪论 数字几何处理( d i g i t a lg e o m e t r yp r o c e s s i n g ，简称d g p ) 是研究如何利用计算 机对三维几何数据进行处理的一门学礼虽然诞生仅十余年时间，但先后已经 有许多专家学者投入到这门新兴的学科中来，其中的一些研究成果已在工业界 得到广泛的应用随着计算机运算和存储能力的大大提高以及各种图形加速 卡的出现，使得在个人计算机上处理大容量的三维几何数据变得很方便这些 因素再加上i n t e m e t 技术的飞速发展使得我们有理由相信三维几何将继声音，图 像和视频之后掀起新轮的多媒体数据革新高潮事实上，这几年三维数字几 何研究的飞速发展及其在影视工业，游戏工业和制造工业的广泛的使用已经验 证了这一点以p a r a s o l i d ，a c l s 为代表的几何造型内核，以p t c ，c a t i a ，s o l i d w o r k s ， 3 d s m a x ，m a y a ，等为代表的计算机辅助设计软件，彻底改变了制造业生产的模 式。 本文着眼于数字信号处理的方法，通过将高频信号与低频信号分离，为离散 的数字几何提供了一种新的表示方式并且基于该表示方式提出了一个鲁棒的保 特征的鼯格曲面编辑框架在这个框架下可方便地对网格益面进行空阔变形，几 何细节迁移等操作 1 1 数字几何处理的发展一从工业界到娱乐界 1 ，1 ，1 几何表示 在计算机图形学中，三维几何模型通常包含两部分内容：一部分是几何模型 的形状，另一部分是几何模型的外观属性描述物体形状的方法有很多种，如体素 表示法( v o x e l ) ，c s g 树表示法以及边界表示法等等其中边界表示法又有隐函数 曲面，参数曲面，细分曲面，多边形网格( m e s h ) 和点几何表示等从三维计算机图 形学发展的初期开始，多边形网格就是最通用的表示物体形状的方法多边形网 格模型具有以下优点：1 ) 多边形形状简单，便于计算和处理；2 ) 多边形可以任意精 度逼近一曲面物体，可以表示拓扑非常复杂的物体；3 ) 只需存储各多边形顶点的 位置坐标及属性即可表示物体的几何信息，在计算多边形内任一可见点的光亮度 时，所需的信息可由顶点的信息插值得到，这使得对多边形网格的绘制可采用硬 件加速技术来实现多边形网格模型可以由各种商用动画软件；如a l i a s , w a v e f r o n t ， s o r i m a g e ，m a y a 和3 d s m a x 生成，或者通过三维激光扫描仪在物体表面测得一系 列离散点后由表面重构算法生成，或者由曲面模型离散得到图1 2 给出了几个多 边形网格模型的例子，图1 3 给出了一些带有颜色属性的三角形网格模型本文的 2 第一章绪论 研究对象就是多边形网格曲面因为任意多边形可以很方便地被剖分为三角形 网，故本文只讨论三角形网格曲面的处理 圈1 2激光扫描仅获取的三维几何 图1 3带纹理信息的网格曲面 1 1 2 数宇几何处理( d g p ) 概述 广义的数字几何处理包括三维几何数据的获取和处理两部分，获取是指对真 实世界中的物体进行测量和采用，生成三维几何模型几何获取是数字几何处理 的基础，最常用的获取技术是通过三维激光扫描仪和投影相机系统，在物体表面 测得离散点云后，利用散乱点重构算法生成网格模型 1 7 】【6 】 2 7 1 另外也有些算 法能从物体的多幅深度图像中重建三维几何模型【8 】与数字图像处理类似，数字 几何处理涵盖了几何数据的去噪，存储和传输，版权保护，编辑，变形和动画等等 图1 4 显示了一个龙模型的低通滤波过程 图1 4 低通滤波结果 一3 一 第一章绪论 随着三维几何模型在工业界的广泛应用，d g p 的应用领域也越来越广最为 人们所熟知的是影视娱乐行业为了带给观众在真实世界中无法体验到的视觉 感受，大量的三维动画技术被应用到影视制作中较早的有1 9 8 2 年纽约理工学院 的t o mb r i g h a m 制作的由一个女人变成一只山猫，近几年的工作更足不胜枚举，例 如迈克尔杰克逊的音乐带黑与白这首歌中1 3 个不同性别和种族的人的相 互渐变；终结者中机械杀手t _ 1 0 0 0 由液体变为金属人，又由金属人变为影片 中的其他角色；e x x o n 公司的影视广告中，一辆银色的轿车缓缓滑行渐变成一只 老虎，最近几年中的大片指环王和加菲猫等等更是采用了大量的动画技 术在这些动画效果的制作过程中，曲面变形技术无疑充当了重要的角色，曲面变 形方法与物体的表示有密切的关系，如可通过移动物体的顶点或控制顶点来对物 体进行变形为了使变形方法能很好地结合到造型和动茴系统中，近1 0 年来，人们 提出了许多与物体表示无关的变形方法，在商业动画软件中也提供了大量的编辑 工具 可见随着n u r b s 表示方法的成熟和广泛应用，几何造型与处理的研究 经历了一个新的变革从上世纪9 0 年代以来，几何造型的研究，已经从面向工 业造型，基于边界表示和n u r b s 表示的参数化设计，转到面向数字娱乐( d i g i t a l e n t e r t a i n m e n t ) 和影视业的基于细分曲面，网格曲面表示的测量造型上随着这些 行业的飞速发展，传统的研究内容和方法均受到挑战新的应用和来自实践的问 题，会给这个”年轻”的学科带来新的活力和机遇 因此有人对几何造型与处理的趋势作了大胆的预测【3 8 】：以工业设计为目的 的几何造型研究将成为历史! ! 这是由于： 1 f r e e - f o r mm o d e l m g 成熟起来，已经由研究走向应用： 2 几何造型与处理的重要应用产业- 机械工业的不景气也对这个学科的发展 产生了一定的影响： 3 在几何造型与处理研究领域，余留的难题有： ( 1 ) 几何计算的容差传播与控制，它直接影响到参数化设计的稳定性； ( 2 ) 曲线曲面的形状计算，分析与处理( 编辑，光顺等) 是目前迫切需要解决的问题综上我们可以看出，曲面编辑是当前数字凡何处理 的核心内容，下面我们来回顾这个研究领域的发展历史并讨论最近的工作进展 4 第一章绪论 1 2 曲面编辑相关工作介绍 三维几何形状编辑是几何造型和计算机图形学领域中一个重要的研究分支 现在的主流造型方法是参数曲面设计( 【1 l 】s ) ，且可利用细分技术推广到非奇异参 数域 2 9 】曲面编辑是几何造型与处理的核心内容，其目的是为用户提供直观，高 效的曲面编辑工具，实现复杂几何模型的构造其内容包括局部形状调整，曲面剪 切粘贴，几何纹理迁移，曲面融合，大范围变形，模型的完成化等等本文中要编辑 的曲面一般是利用三维扫描设备获取的现实世界中已经存在的物体，如果初始的 陆面是光滑的，一般要求编辑后的曲面也应该是光滑的 3 4 】【3 3 1 如果曲面包含几 何细节( e g as h a r pf e a t u r e ) ，那么这些细节应该在编辑的过程中保留下来也就是 说曲面编辑操作一般要求在尽可能保留曲面结构信息的同时自然地改变曲面的 外形经过多年的努力，许多研究者相继提出了许多巧妙的方法来实现这一目标 曲面编辑方法大致可以分为两类：一类是基于空间均匀网格的自由变形方 法( f f d ) 【3 0 】 7 i 【2 6 】，第二类是最近研究比较熟的基于曲面微分属性的方法下 面依次介绍这两类方法的发展，基本思想以及最近的研究进展首先来看下目 前最常用的f f d 方法 1 2 1f f d 方法及其扩展 1 9 8 4 年，b a r r 【3 】提出了物体形状整体和局部变形方法该方法实现高效，但 是缺乏直观的交互手段b a r r 方法的创新性在于当对物体的各部分实施变换时， 变换矩阵不再是一个恒定值，而成为变换点位置的函数 1 9 8 8 年，s e d e r b e r g 和p a r r y 首先提出了自由变形( f r e e - f o r md e f o r m a t i o n ，简 称f f d ) 的概念 3 0 】，这是一种与物体表示无关的变形方法其基本思想是把 变形定义为从原始物体空间到目标物体空间的三维映射在具体实现时，该方法 将物体嵌入一个三交元b 6 z i e r 体，用户通过编$ 0 ；b 6 z i e r 体的控制顶点，改变参数 体的形状，进而使嵌入其中的物体发生变形自由变形方法的直观性表现在物体 的变形趋势与b 6 z i e r 参数体的形状是一致的f f d 变形方法适用面广，可以说是 当前物体变形中最实用的方法之一f f d 方法不对物体直接进行变形，而是对物 体所嵌入的空间进行变形s e d e r b e r g 最初提出的f f d 方法中的l a t t i c e 块的形状为 平行六面体，这在一定程度上限制了它的应用 后面的研究者在此f f d 方法的基础上做了许多改进但是其基本思想不变， 即通过b 6 z i e r , b 样条或者n u r b s 体来变形物体m a c c r a c k e n 2 6 等提出了控制 第章绪论 1 2 曲面编辑相关工作介绍 三维几何形状编辑是几何造型和计算机图形学领域中个重要的研究分支， 现在的主流造型方法是参数曲面设计( 【1 h s ) ，且可利用细分技术推广到非奇异参 数域 2 9 】曲面编辑是几何造型与处理的核心内容，其目的是为用户提供直观，高 效的曲面编辑工具，实现复杂几何模型的构造其内容包括局部形状调整，曲面剪 切粘贴，几何纹理迁移，曲面融合，大范围变形，模型的完成化等等本文中要编辑 的曲面一般是利用三维扫描设备获取的现实世界中已经存在的物体，如果初始的 皓面是光滑的，一般要求编辑后的曲面也应该是光滑的 3 4 】【3 3 】如果曲面包含几 何细节( e g as h a r pf e a t u r e ) ，那么这些细节应该在编辑的过程中保留下来也就是 说曲面编辑操作一般要求在尽可能保留曲面结构信息的同剥自然地改变曲面的 外形经过多年的努力，许多研究者相继提出了许多巧妙的方法来实现这一目标 曲面编辑方法大致可以分为两类：一类是基于空间均匀网格的自由变形方 法口f d l 3 0 】 7 【2 6 第二类是最近研究比较热的基于曲面微分属性的方法下 面依次介绍这两类方法的发展。基本思想以及最近的研究进展首先来看一下目 前最常用的f f d 方法 12 1f f d 方法及其扩展 1 9 8 4 年，b a r r 3 1 提出了物体形状整体和局部变形方法该方法实现高效，但 是缺乏直观的交互手段b a r r 方法的创新性在于当对物体的各部分实旖变换时， 变换矩阵不再是一个恒定值，而成为变换点位置的函数 1 9 8 8 年，s e d e r b e r g f t p a r r y 首先提出了自由变形( f r e e - f o n nd e f o r m a t i o n ，简 称f f d ) 的概念 3 0 】，这是一种与物体表示无关的变形方法其基本思想是把 变形定义为从原始物体空间到目标物体空间的三维映射在具体实现时，该方法 将物体嵌入一个三变元b 6 z i e r 体，用户通过编辑b e z i e r 体的控制顶点，改变参数 体的形状，进而使嵌入其中的物体发生变形自由变形方法的直观性表现在物体 的变形趋势与b 6 z i e r 参数体的形状是一致的f f d 变形方法适用而广，可以说是 当前物体变形中最实用的方法之一f f d 方法不对物体直接进行变形，而是对物 体所嵌入的空间进行变形s e d e r b e r g 最初提出的f f d 方法中的l a t t i c e 块的形状为 平行六面体，这在一定程度上限制了它的应用 后面的研究者在此f f d 方法的基础上做了许多改进但是其基本思想不变， 即通过b e z i e r , b 样条或者n u r b s 体来变形物体m a c c r a e k e n 2 6 等提出了控制 即通过b e z l e r , b 样条或者n u r b s 体来变形物体m a c c r a c k e n 2 6 等提出了控制 第一章绪论 网格为任意拓扑结构的f f d 方法，他们利用体细分技术在任意拓扑三维网格上 定义变形空间，可以很好地逼近任意拓扑的物体外形但是生成具有任意拓扑 且贴近物体外形的空间网格仍是件很困难的事情；此外该方法的时间和空间开 销极大，难以实时交互；并且作者对于其由细分体定义的变形空间光滑性没有证 明b e c h m a n n 4 】提出的连续自由变形技术( c o n t i n u o u sf f d ) 与e f f d 类似s i n g h 等【3 l 】在1 9 9 8 年提出了线约束方法，该方法的控制手段是空间曲线和隐式场函数 具有相当的灵活性，适合运用于动画设计领域基于f f d 的变形动画一般是这样 来实现的，先对物体所嵌入l a t t i c e 的控制顶点设置动画，然后变形传播到物体本 身作为有意思的推广，c o q u i l l a r t 等提出的拓广的f f d 方法( 简称e f f d ) 7 允许变 形工具和物体单独设置动画，即物体位于l a t t i c e i 内的局部坐标可不再保持不变冯 结青等【1 2 】提出了基于参数曲面控制的变形技术，其控制手段是规则矩形b 样条 曲面的控制顶点该方法变形速度快，空间开销小然而定义在矩形拓扑上的张量 积曲面难以逼近物体的外形，所以其控制手段仍然不够灵活 图1 5f f d 方法编辑网格曲面 h s u 等【1 8 】于1 9 9 2 年提出了一种直接操纵的f f d 方法( d i r e c t m a n i p u l a t i o no f f f d ，简称d f f d ) j j 采用了另一种策略：首先将物体嵌入b 样条体，通过编辑所选 取物体上点的方法控制物体变形其实现方法是：根据用户选择点的位移。反求 导致这种变化的f f d 控制网格的位移，从而达到直接操纵物体变形的目的b 样 条体控制顶点的反求是通过计算伪逆矩阵的方式实现的所以d f f d 方法的变形 控制最为直接，但是由于涉及伪逆矩阵的计算，该方法的计算量增加很多，从而影 响了用户的实时交互h u 等【1 9 】在2 0 0 1 年提出的基于n u r b s 体直接操纵f f d 方法 采用了类似的思想，但其不需要解伪逆矩阵，本文将该方法应用到b 样条曲面上， 提出了直接操纵的网格蓝面变形方法 总的来说，f f d 方法的主要优点是：与物体的表示方法无关，交互控制直观， 变形过程光滑等但由于控制顶点较多，难以逼近任意拓扑的物体形状，所以物 6 第一章绪论 体变形控制不够灵活和直观人们要获得所需的变形效果，通常要进行多次繁琐 的控制顶点编辑工作当l a t t i c e 变形和物体变形之间的对应关系并非很直观时，基 于f f d 的变形方法就难以奏效 f o r s e y 和b a r t e l 【1 4 【1 5 】等基于局部求精的原理提出的层次b 样条变形方法 是b 样条曲面变形方法的一大发展他们解决了变形的范围问题，即用户可在更 局部的范围控制曲面的变形，并且无需产生过多的控制顶点l e ef 2 3 提出了一种 交互多分辨率编辑网格曲面的方法，该方法将编辑区域嵌入到二维矩形域中然 后利用多层b 样条曲面插值用户交互提供的编辑信息，以此来达到多分辨率光滑 变形的目的，但该方法不能保持物体的固有几何特征，且由于每次编辑操作均需 要用多层b - 样条进行插值，因此该方法比较费时且很难对大规模区域进行处理 k o b b e l t 等 2 1 】提出了一种将低分辨率物体的变形传递到高分辨率表示上的 方法用户通过一个手柄多边形来指定变形约束，初始网格细节加到变形后的光 滑曲面上，得到变形后的高分辨率网格该方法通过少量的约束给用户提供有限 的网格控制能力，剩下的网格细节通过解能量最小方程而被唯一确定 1 2 2 基于微分属性的曲面编辑方法 微分属性操纵方法则是最近两年研究比较热的曲面编辑方法，该方法将传统 基于顶点直接操纵的曲面编辑和形变问题转化为曲面局部几何微分属性的操纵， 然后通过优化技术重建编辑后的曲面基于这一方法，用户只需采用很少的编辑 操作，即可实现曲面的高效编辑，且在曲面变形过程中能够很好地保持曲面几何 细节本节首先对微分属性操纵方法的数学基础，实现难点和应用背景以及近年 的相关工作作一详细的介绍 2 0 0 4 年，s o r k i 鹏将拉普拉斯坐标方法推广到三角网格上【3 2 】网格上广义的 拉普拉斯坐标被定义为该点与其局部邻域质心所组成的向量【1 】拉普拉斯坐标 是关于网格曲面全局几何的线性方程，这样就可以通过求解一个稀疏线性方程组 的方法来进行网格全局和局部表示之间的转换s o r k i n e 利用定义在三角网格曲面 上的广义拉普拉斯坐标，提出了一个网格曲面编辑框架( 见图1 6 ) 该方法的基本 思想是以编辑前后的网格顶点拉普拉斯坐标位移最小作为约束条件，建立一个最 小二乘目标函数，通过解一个稀疏的线性系统可以对网格进行自由变形，曲面移 植，几何细节迁移等操作广义拉普拉斯坐标为网格曲面提供了种内在几何表 达方式，使得在给定造型约束下重建全局坐标的时候能尽可能保持物体的局部几 何特征拉普拉斯坐标是平移不变的，但受旋转和缩放操作的影响，这给拉普拉斯 7 一 第一章绪论 坐标的实际应用带来了一定的问题 图1 , 6 基于广义拉普拉斯坐标的网格曲面编辑 s o r k i n e 2 0 0 4 】 在图像域中使用微分表示来进行编辑操作是非常有效的，但是和网格曲面 不同的是，图像域上已经有了一个天然的规则参数化，在梯度场上也有了连续的 定义这就可以把许多编辑操作转换成求解离散泊松方程的问题最近，俞益洲 等 3 6 1 提出了一种基于泊松方程的网格编辑方法( 见图1 7 ) ，该方法通过操作网格 梯度场来达到编辑目的，编辑后的曲面通过解一个带d i r i c h l e t 边界条件的离散泊 松方程a f = g 重建，编辑的效果被均匀扩散到网格睦面上 图1 7 基于泊松方程的网格曲面编辑w u2 0 0 4 】 1 3 本文的研究目的及解决方案 计算机图形学中的曲面通常被定义在全局坐标系中，大体可分为显示表示和 隐式表示两种方式显示表示用欧几里德坐标表示的顶点或者加上拓扑连接关 系来加以表示隐式表示方式用定义在欧几里德空间中的水平集描述曲面形状 全局坐标系在牵涉到别的物体的运算时是很自然的选择，比如说绘制，求交测试， 曲面属性计算，模型变换年n c s g 操作等但在象局部曲面形状调整等情况下，一般 更希望表达方式能反映曲面的局部几何特征( 例如曲面的内在几何属性) ，而不是 曲面在欧几里德空间中的绝对坐标和方向在绝大多数的曲面编辑操作中大都要 求保持曲面的局部几何特征如自由变形【3 0 】 7 】，剪切和粘贴【5 】，曲面融合【2 0 ， 第一章绪论 m o r p h i n g 1 】等注意到在这些操作中，我们并不太关心网格曲面的绝对位置和方 向，因此为这些操作提供种网格曲面的内在特征表达方式是很有意义的。多分 辨率分解 1 4 】【2 l 】 1 6 】是网格曲面的一种局部内在几何特征表示方式结合曲面 编辑的一般要求以及当前研究的现状，本文拟提出的曲面编辑方法应具有以下特 点： 1 操作直观方便； 2 保持物体的局部几何特征； 3 无论对整体变形还是局部变形，都能取得可控、可靠的变形效果； 4 对任意类型的网格模型，都能取得鲁棒的变形效果； 5 易于与已有的处理系统合成 针对上述问题，我们提出了种新的三维数字几何多分辨率表达方式，并且 基于基于该方式开发了一个网格曲面编辑框架，我们的多分辨率表达方式由物体 的光顺基曲面以及定义在该基曲面上的组局部变量共同定义这样就能达到在 曲面编辑过程中保持物体内在几何特征的目的，考虑到交互操作以及与常用造型 系统合成的方便，我们采用b - 样条作为基曲面表达方式简言之，本文的曲面编辑 框架旨在通过简单的用户交互，人为地为网格物体引入类似于n u r b s 曲面的控 制顶点用户通过编辑控制顶点，即可实现对网格的多分辨率编辑其主要过程包 括：首先由用户交互地选取编辑区域，算法自动将该编辑区域参数化到矩形域上， 并在参数域中均匀重采样网格点，然后用层次b 样条曲面光顺拟合这些均匀采样 的网格顶点，构成待编辑区域的基曲面根据层次b 样条曲面拟合中的参数化。可 以快速计算待编辑区域中各网格顶点相对基曲面的局部坐标，该局部坐标可以视 为曲面的内蕴几何特征，它们在变形或编辑过程中保持不变实验结果表明，该方 法对任意类型的网格模型都能取得鲁棒，有效和高质量的变形结果 1 4 本文的贡献 在过去的研究工作中，多分辨率网格表示是保特征的几何造型的标准方法 几何细节通常采用局部标架来表j 2 i 1 4 】【2 1 】【1 6 特别地，【2 1 】通过解一个带约束 的薄板样条髓量最小问题，提出一种低分辨率上网格曲面变形的方法用户通过 个多边形手柄来控制变形区域，原始网格的几何细节附着到变形后的光顺基曲 9 第一章绪论 面上来获得网格曲面变形后的结果但该方法只给用户提供非常有限的编辑手 段，即操作多边形手柄上稀疏分布的一些控制点，余下部分的网格几何则通过解 一个能量最小化问题求得与之相比，本文提出的方法可提供更为便捷的控制手 段，允许用户编辑物体的任意区域，提供了完全类似b 样条编辑的交互方法，并且 基于层次b 样条的原理，可对三维几何进行层次编辑 本文借助层次b 样条为三维数字几何提供了一种多分辨率表示方式，且基于 该表示方式提出了一个鲁棒的，交互便捷，能处理任何拓扑类型的网格曲面编辑 框架，在该框架下，网格曲面被表示成一张光顺的基曲面和定义在该基曲面上的 反跃物体内在几何缅节的一组坐标，层次b 一样条为基曲面提供了多分辨率的表达 方式，同时也使得几何细节的定义也是多分辨率的，且随着基曲面光顺程度的变 化丽变化，总体来说，本文的贡献主要有以下几点： 1 为三维几何数据提出了一种新的多分辨率表示方式：该表示方式由光滑 的b 样条基曲面和定义在该基曲面局部标架上的一组表示内在几何属性的 坐标组成； 2 提出了一个有效的，可控的网格曲面编辑框架：与已有的自由变形方法相 比，文本提出的框架中变形操作更加直观方便，完全类似于b 一样条曲面的编 辑操作，并且提供了编辑控制网格和直接操作曲面两种变形方式； 3 变形过程中保持物体的局部几何特征：在变形过程中，表示曲面内在几何 特征的一组局部变量保持不变，因此我们的方法能够在曲面编辑过程中很 好的保持物体的表明细节的几何特征 4 对任意网格曲面提供层次变形方法：借助于层次b 一样条的表达方式，网格 曲面的几何细节可以被定义成一种层次的表达方式，从而方便地实现多分 辨率编辑的功能，且无论对整体变形还是局部变形，都能取得光滑的变形结 果 5 该曲面编辑框架易于与已有造型系统合成：由于利用计算机表达b 一样条 有诸多便利，b 样条已被广泛应用于各成熟的商业软件中，女f l a u t o d e s k 公 司的3 d s m a x 和a l i a s 公司的m a y a 等，因此，与已有方式相比，本文框架采 用b 样条的表示方式，更容易与这些成熟的造型系统合成，从而显著加快工 作效率 1 0 第二章基于层次b ，样条的网格曲面编辑框架 第二章基于层次b 一样条的网格曲面编辑框架 本章概述我们提出的网格曲面编辑框架为了描述方便，第一节先给出本文 用到的一些术语的定义；第二节详细描述本文框架处理亏网格曲面的主要流程， 包括编辑区域选取，参数化及重采样，单层b 样条拟合，局部坐标计算和多层b 样 条拟合等；第三节基于我们提出的三维几何多分辨率表示方式，介绍了相应的网 格曲面变形技术以及几何细节迁移技术，并给出了详细的实验结果；第四节总结 了本文的工作，并对未来工作作了展望 2 1 基本定义 离散网格已经成为几何造型和计算机图形学领域中物体表示的主要方式之 离散网格表示通常中含有顶点和拓扑连接关系等信息由于网格表示的拓扑 连接关系没有限制，所以它可以表示其有任意复杂拓扑和细节的几何物体。同时， 网格曲面是线性连续而非高阶光滑的曲面，所以网格不具有类似于n u r b s 曲面 的控制顶点，本文的研究对象就是多边形嘲格曲面，鉴于任意多边形可以很方便 地被分割为多个三角形面片，因此本文中只讨论三角形网格曲面的处理 2 1 1 网格曲面 三角形网格曲面m 表示为三元组：m = ( ，k m ，嘞) ，其中= l ，2 ，m 是m 的顶点集合( 1 肘l 表示顶点数目) ：是包含m 中所有拓扑连 接关系的集合；砌为m 中所有顶点的属性向量集合= 吼li ) 其 中0 i = ( ，l ( i ) ，2 ( i ) ，厶( i ) ) 表示顶点 t ) 的n 个属性值，包括位置坐标，法向量和 颜色等，显然p d 包含了m 的所有几何信息 k m 的元素分三种类型：项点0 ) ，边e = i 】，) 和面，= ，z 女) 如 果“j ) k m ，则顶点 t 和d ) 被称为邻居顶点 i ) 的1 环邻居被定义 为0 ) = dl ，j ) k 彳) ，顶点矗 的入度( v a l e n c e ) 被定以茭j n ( i ) v o 的元素 个数i n ( i ) i ，边e = 托) 的1 环邻居被定义为( e ) = n ( i ) u n ( j ) “j ) 依 此类推，设共享