（计算机软件与理论专业论文）网格上曲面拟合和变形的研究.pdf

山东大学博士学位论文 摘要 随着三维扫描和相关技术的进步，三维数字几何模型已成为一种新兴的数字 媒体，在三维游戏，计算机动画，电影特效，工业造型设计，计算机仿真以及数 字文化遗产保护等方面取得了日益广泛的应用。针对这类数据进行高效的处理， 也成为计算机图形学的一个研究热点，即数字几何处理( d g p ：d i g i t a lg e o m e t r y p r o c e s s i n g ) 。数字几何处理研究的问题主要包括三维数字几何模型的建模、处理 和应用等方面。近十多年来，无论是学术界还是工业界，数字几何处理都引起了 人们的关注，技术也得到了很大的发展，但是，随着相应研究的不断深入和应用 范围的愈加广泛，数字几何处理研究中仍然充满着挑战。 本文主要讨论曲面形式的三维模型表示。曲面一般以连续形式或者离散形式 表示。连续形式主要包括样条曲面、隐式曲面和细分曲面，而离散形式主要是网 格和点云。基于网格形式表示的数字几何，本文主要围绕网格上的样条曲面拟合 和变形技术进行了深入探讨，创新点主要包括以下三个方面： ( 1 ) 提出一种在不规则四边形网格上构造有理双三次样条曲面的方法 对任意拓扑四边形网格上，通过均匀双三次b 样条基函数的分解和子基函数 的分类，将b 样条曲面方法推广到任意四边形网格，从而在任意网格上构造样 条曲面。给定一个任意四边形控制网格，首先对每个控制点构造一个基函数；然 后所有控制点加权组合形成整体曲面。构造的曲面是分片双三次有理参数多项式 曲面。新方法可看成是b 样条曲面构造方法的扩展，如果控制网格是规则四边 形网格，那么构造得到的曲面与均匀双三次b 样条曲面是一致的。 ( 2 ) 提出使用法向叉乘目标函数项以及带约束的特征保持尺寸调整方法 模型复用中，对已有模型调整尺寸以适合应用的需求是非常常见的问题。对 此，本文提出新的特征保持的模型尺寸调整方法。新方法通过对每条边的缩放来 驱动模型尺寸的调整，然后以缩放前后三角形法向的叉乘为目标函数项进行优 化，几何意义上，该法向叉乘项表示极小化每个三角形的法向变化：w i l l m o r e 能量意义上，该项可以近似地极小化缩放带来的能量变化。另外，对需要精确保 持某些特征区域的模型，采用带约束的尺寸调整方法，通过引入拉格朗日乘数来 山东大学博士学位论文 求解满足约束条件的优化问题，从而能够精确保持模型的重要特征，目前已有的 三维模型尺寸调整方法还不能做到这一点。 ( 3 ) 提出一种特征敏感的模型变形方法 特征对于形状表达和模型的理解与分析具有特别重要的作用。因此，变形过 程中，应该很好的保持特征细节不变。基于特征敏感度量，新方法更加注重保持 网格模型的特征细节区域。具体是通过在对偶网格中使用特征敏感度量的思想， 直接将法向量考虑进来，导出特征敏感的拉普拉斯算子。与已有离散拉普拉斯算 子相比，该算子对特征细节更加敏感，用于变形时能够更好的保持模型的特征细 节。另外，在变形中通过将对偶网格中的1 邻域四面体作为基本变形单元，并且 引入四面体约束，通过极小化该四面体底面三角形的扭曲和相应高的变化来尽量 保持四面体的形状不变。从而，新方法能够在变形过程中很好的保持模型的特征 细节。同时，新方法的时间复杂性与已有线性拉普拉斯变形方法接近。 关键词：数字几何处理；不规则网格；样条曲面；模型尺寸调整；特征保持； 特征敏感度量 i i 山东大学博士学位论文 a b s t r a c t w i t ht h ef a s td e v e l o p m e n to f3 ds c a n n i n ga n dr e l a t e dt e c h n i q u e s 3 dm o d e l sa r e n o ww i d e l yu s e da sa l le m e r g i n gt y p eo fm e d i ai n3 dg a m e s ，c o m p u t e ra n i m a t i o n ， i n d u s t r i a lm o d e ld e s i g n ，c o m p u t e rs i m u l a t i o n ，d i g i t a lc u l t u r a lh e r i t a g ep r o t e c t i o na n d s oo n t e c h n i q u e sf o rp r o c e s s i n g3 dg e o m e t r yd a t ah a v ea l s ob e c o m eah o tr e s e a r c h t o p i ci nc o m p u t e rg r a p h i c s ，w h i c hi sc a l l e dd 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 ) t h e r e s e a r c hc o n t e n t so fd g pc o v e rm o d e l i n g ，p r o c e s s i n ga n da p p l i c a t i o no f3 dd i g i t a l g e o m e t r i cm o d e l s n om a t t e ri ni n d u s t r yo ra c a d e m i cw o r l d , m u c ha t t e n t i o nh a sb e e n p a i do nd g p , a n dt e c h n i q u e sh a v eb e e ng r e a t l yd e v e l o p e d h o w e v e r , a st h er e l a t e d r e s e a r c hc o n t i n u e st od e v e l o pa n dt h ea p p l i e dr a n g ei sb e i n ge n l a r g e d ，t h e r ea r es t i l l m a n yc h a l l e n g e si nd g p i nt h i st h e s i sw ef o c u so n3 dr e p r e s e n t a t i o nb a s e do ns u r f a c e s 3 ds u r f a c e sc a n b ec l a s s i f i e di n t ot w oc a t e g o r i e s ：c o n t i n u o u sf o r ms u r f a c e sa n dd i s c r e t ef o r ms u r f a c e s c o n t i n u o u sf o r ms u r f a c e si n c l u d es p l i n es u r f a c e s ，i m p l i c i ts u r f a c e s ，s u b d i v i s i o n s u r f a c e sa n ds oo n a n dd i s c r e t ef o r ms u r f a c e si n c l u d em e s ha n dp o i n tc l o u d b a s e d o nm e s hr e p r e s e n t a t i o n ，t h i st h e s i sp r e s e n t ss e v e r a ln o v e lt e c h n i q u e sf o rs p l i n es u r f a c e f i t t i n ga n dd e f o r m a t i o nf o r3 dm o d e l s t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ( 1 ) w ep r o p o s ean e wm e t h o df o rc o n s t r u c t i n gr a t i o n a lb i - c u b i cs p l i n es u r f a c e so n i r r e g u l a rm e s h e s f o rs p l i n es u r f a c ef i t t i n go na r b i t r a r ym e s h e s ，w ee x t e n db - s p l i n em e t h o dt o i r r e g u l a rm e s h e st h r o u g ht h ed e c o m p o s i t i o na n dc l a s s i f i c a t i o no fu n i f o r mb i c u b i c b s p l i n eb a s i sf u n c t i o n g i v e naq u a dm e s ho fc o n t r o lp o i n t s ，ab a s i sf u n c t i o ni s c o n s t r u c t e df o re a c hc o n t r o lp o i n t t h e nt h es u r f a c ei sd e f i n e db yt h ew e i g h t e d c o m b i n a t i o no fa l lt h ec o n t r o lp o i n t su s i n gt h e i ra s s o c i a t e db a s i sf u n c t i o n s t h i s s u r f a c ei sap i e c e w i s eb i c u b i cr a t i o n a lp a r a m e t r i cp o l y n o m i a ls u r f a c e i ti sa n e x t e n s i o nt ou n i f o r mb s p l i n es u r f a c e si nt h es e n s et h a ti t sd e f i n i t i o ni sa na n a l o g yo f t h eb - s p l i n es u r f a c e a n di tp r o d u c e sau n i f o n nb i - c u b i cb s p l i n es u r f a c ei ft h ec o n t r o l m e s hi sar e g u l a rq u a dm e s h i i i 山东大学博士学位论文 ( 2 ) w ep r e s e n tt ou s et h ec r o s sp r o d u c to fn o r m a l sa st h eo b je c tf u n c t i o nt e r ma n d p r o p o s ean e w m e t h o dt or e s i z em o d e l s 、加mc o n s t r a i n t s t or e u s ee x i s t i n gm e s hm o d e l s ，r e s i z i n gi so f t e nn e c e s s a r yt os a t i s f ye n g i n e e r i n g r e q u i r e m e n t s w ep r e s e n tan e wr e s i z i n gm e t h o di nt h i st h e s i s t h er e s i z i n gi sd r i v e n b ys c a l i n ge a c he d g eo ft h em e s h a n da no b j e c t i v ef u n c t i o nc o m p o n e n t ，w h i c hi s e x p r e s s e da st h ec r o s sp r o d u c to fn o r m a lv e c t o r so ft r i a n g l e sb e f o r ea n da f t e rs c a l i n g ， i sd e v i s e dt oo p t i m i z et h er e s i z i n gm o d e l i t sg e o m e t r i cm e a n i n gi st om i n i m i z i n gt h e v a r i a t i o no fn o r m a lv e c t o ro fe v e r yt r i a n g l e i nt h es e n s eo fw i l l m o r ee n e r g y , t h ec r o s s p r o d u c ti t e mc a na p p r o x i m a t e l ym i n i m i z et h ev a r i a t i o no ft h ew i l l m o r ee n e r g yb e f o r e a n da f t e rr e s i z i n g f o rs o m ei m p o r t a n tf e a t u r e dr e g i o n so ft h em o d e l ，w h o s es h a p e s h o u l db ea c c u r a t e l yp r e s e r v e d ，ac o n s t r a i n e dr e s i z i n gm e t h o di sa l s op r e s e n t e d l a g r a n g em u l t i p l i e rm e t h o di su s e dt op r e s e r v et h es h a p eo ft h e s er e g i o n s h o w e v e r , e x i s t i n g r e s i z i n gm e t h o d sh a v en o tc o n s i d e r e dt h ea c c u r a t ep r e s e r v i n go ft h e s e i m p o r t a n tf e a t u r e dr e g i o n s ( 3 ) w ep r e s e n taf e a t u r es e n s i t i v ed e f o r m a t i o nm e t h o d f e a t u r e sa r ec r u c i a lf o ra c c u r a t er e p r e s e n t i n gg e o m e t r y , a sw e l la su n d e r s t a n d i n g a n da n a l y s i so fm o d e l s t h e r e f o r e ，t h ef e a t u r ed e t a i l ss h o u l db ew e l l - p r e s e r v e dd u r i n g d e f o r m a t i o n b a s e do nf e a t u r es e n s i t i v em e t r i c ，w ep a ym o r ea t t e n t i o no nt h ef e a t u r e r e g i o n so ft h em e s hm o d e l s f i r s t l y , t a k i n gu n i tn o r m a lv e c t o r si n t oa c c o u n t ，w e d e r i v eaf sl a p l a c i a no p e r a t o r , w h i c hi sm o r es e n s i t i v et of e a t u r e dr e g i o n so fm e s h m o d e l st h a ne x i s t i n go p e r a t o r s s e c o n d l y , w eu s et h e1 - r i n gt e t r a h e d r o ni nt h ed u a l m e s ha st h eb a s i sd e f o r m a t i o nc e l l 。t op r e s e r v et h es h a p eo ft h et e t r a h e d r o n ，w e i n t r o d u c el i n e a rt e t r a h e d r o nc o n s t r a i n t sm i n i m i z i n gb o t ht h ed i s t o r t i o no ft h eb a s e t r i a n g l ea n dt h ec h a n g eo ft h ec o r r e s p o n d i n gh e i g h t t h e s ee n s u r et h a tg e o m e t r i c d e t a i l sa r ea c c u r a t e l yp r e s e r v e dd u r i n gd e f o r m a t i o n t h et i m ec o m p l e x i t yo fo u rn e w m e t h o di ss i m i l a rt ot h a to fe x i s t i n gl i n e a rl a p l a c i a nm e t h o d s k e yw o r d s ：d i g i t a lg e o m e t r yp r o c e s s i n g ：i r r e g u l a rm e s h e s ；s p l i n es u r f a c e ；m o d e l r e s i z i n g ；f e a t u r ep r e s e r v i n g ；f e a t u r es e n s i t i v em e t r i c 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：啤日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) ， 论文作者签名：厶篁l 墅0 导师签名： 论文作者签名：7l 堕銎导师签名： 山东大学博士学位论文 第一章绪论 随着三维扫描和相关技术的进步，三维数字几何模型已成为一种新兴的数 字媒体，在三维游戏，计算机动画，电影特效，工业造型设计，计算机仿真， 医疗诊断以及数字文化遗产保护等方面取得了日益广泛的应用。针对这类数据 进行高效的处理，也成为计算机图形学的一个研究热点，即数字几何处理【1 ，2 】 ( d g p ：d i s t a lg e o m e t r yp r o c e s s i n g ) 。数字几何处理研究的问题主要包括三维 数字几何模型的建模、处理和应用等方面。近十多年来，无论是学术界还是工 业界，数字几何处理都引起了人们的关注和重视，技术也得到了很大的发展， 但是，随着应用范围的愈加广泛和相应研究的不断深入，数字几何处理研究中 仍然充满挑战。 为了在计算机中有效的表达、处理和存储三维模型，需要有效的三维模型 表示形式。这里主要讨论曲面形式的三维模型表示。三维曲面一般以连续形式 或者离散形式表示。连续形式主要包括：样条曲面、隐式曲面和细分曲面，而 离散形式主要是网格和点云。本文主要基于网格形式表示的数字几何，对其中 不规则网格上样条曲面拟合、保持特征的模型尺寸调整和特征敏感的模型变形 等问题进行了深入探讨。 1 1 研究背景 本节主要对三维曲面表示形式和数字几何处理进行简单介绍。 1 1 1 三维曲面表示 要对三维几何模型进行有效的存储、表达、处理与显示，就需要有效的三 维表示形式。本文主要基于曲面形式的三维模型表示，三维曲面的表示方法包 括连续形式表示和离散形式表示两大类。连续形式曲面主要包括：参数曲面( 包 括在几何造型中常用的张量积样条曲面) 、细分曲面和隐式曲面，而离散形式最 主要的是网格和点云。 山东大学博士学位论文 1 1 1 1 样条曲面 在c a d 系统中，张量积样条曲面已经成为自由曲面的标准表示形式。常常 用于构造高质量的曲面，或者用于控制曲面的变形。 样条曲面可以方便的表示为一些样条基函数的张量积。一张r 1 次的张量积样 条曲面j 是一个分段多项式曲面，各个分片的多项式曲面拼接后满足c ”1 连续， b 样条曲面的表达式如下 s ( u ，v ) = 巳l ，。 ) 妈，。( d ， i = 0j = 0 其中m ，。( ”) 是b 样条基函数，匕，i = o ，1 ，2 ，m , j = o ，1 ，2 ，玎构成曲面的控制 网格。样条曲面上每个点都是控制顶点p ，的凸组合，因此曲面在控制网格的凸 包内，而且，由于b 样条基函数的局部支撑性，每个控制顶点仅影响瞌面的局 部区域。上述两个性质保证曲面逼近控制网格，因此我们可以非常直观的通过 调整控制网格来调整曲面的形状，这非常有利于交互设计。图1 1 显示了一个b 样条曲面及其控制网格。 - 一 如图1 2 即为图1 1 所示b 样条曲面的参数分割，张量积曲面定义在矩形参 数区域上，所以曲面本身也是嵌入到r 3 中的四边形区域。因此，为了表示更复 图1 1b 样条曲面及其控制网格图1 2 圳平面的分割 杂拓扑结构的曲面，就需要用多张张量积曲面片拼接而成。由于张量积曲面表 示方法在表达拓扑类型上的局限，一般c a d 模型都由多张面片拼接而成，这样 就要考虑曲面拼接时的连续阶问题，对每个张量积曲面增加几何限制。这就增 加了使用张量积曲面建模的复杂性。 1 1 1 2 细分曲面 细分方法可从任意形状网格出发构造光滑曲面而无需考虑几何连通性问 2 山东大学博士学位论文 题。细分曲面既不像b 样条曲面受拓扑类型的局限，也不像隐式曲面难于绘制。 它通常是对一个控制网格不断进行细化而得到的。这里的控制雕髓类似于b 样 条曲面的控制网格，但可以是不规则网格。早期，细分曲面的思想就是在b 样 条细分性质的启发下产生的。b 样条曲面的细分仅限于规则控制网格，如果将 此细分算法扩展到不规则控制网格，那么就可以得到任意拓扑类型的曲面。细 分曲面有两种优点：首先，细分方法与b 样条细分紧密相关，得到的曲面与b 样条曲面类似，都是控翩网格的光滑逼近；其次在控制网格的规则区域生成 的衄面就是b 样条曲面，因此非常便于结合b 样条曲面使用。而且，在每一个 细分层次的细分曲面都是模型的一个逼近，因此非常方便用于多分辨率网格和 层次细节等。 细分曲面就是在控制网格上不断进行细分算法的极限曲面，因此，通常不 能解析表示，求任意点的导数或者曲率比较困难，这导致在实际使用中非常不 方便。细分曲面通常用多边形网格表示，为了避免失真必然需要丈量多边形， 因此处理起来比较繁杂。 圉1 3 所示为几种常用细分算法的结果。其中，图1 3 ( 8 ) 为原始网格；图 ( b ) ( e ) 分别是使用d o o - s a b i n 细分方法、c a m l u l l - c l a r k 细分方法、l o o p 细 分方法和撕细分方法经过三次细分后的结果。 f m f oj 圈1 3 使用不同细分方法得i 4 的细分曲面鸭( a ) 原始网格；( b ) d o o - s a b i n 细分方 去 ( c ) c a t 血m _ c l a 出细分方法l ( d ) l o o p 细分方法：( e ) i 细分方法 盆 多 昏 些查奎兰堡圭耋堡篁圣 111 3 隐式曲面 隐式曲面形式没有b 样条曲面的拓扑局限性。有很多种方法表示隐式曲面， 比如连续的代数曲面，径向基函数或者离散的体素等。无论在哪一种表示中， 一张隐式曲面表示如下 f ( x , y ，z ) = 0 ， 其中，x ，y ，：分别是三维点的三个坐标分量。曲面定义为满足上述方程的点的集 合。函数，通常是r ，y ，：的多项式。在曲面内部的点函数值为负数，衄面外的点 函数值为正数，因此对于隐式曲面，很容易判断空间中一点和曲面的位置关系， 只要计算对应的函数，的值就可以。这使得隐式曲面非常适合于构造实体几何 ( c o a s t r u c t i v es o l i dg e o m 目r y ) 操作。臆式曲面可以容易的改变拓扑，在进行 人体的肌肉、水滴、云和烟等物体的造型和表现动画方面有很大优势。 与参数曲面相比，隐式曲面具有更多的自由度，能够表达任意拓扑类型的 曲面，且能够得到更高的光滑度。其曲面实质卜是关于瞬数，的零等值面，它 可以是任意二维流形。隐式曲面的表达式比较紧凑，很容易判断窄间中一点与 曲面的位置关系，曲面之间的求交、等距操作等几何运算的结果均可表示成隐 式形式 4 1 。 对于给定的曲面，其隐式表示函数，不是唯一的。一般较常用的隐式函数 是有向距离函数，空间中每个点的函数值为该点到曲面的有向距离。这样的定 义不仅方便了判断点和曲面的位置关系，而且也简化了点到曲面的距离计算。 在几何处理中，点到曲面的距离可阻用作处理后网格和原网格之间的误差。 图14 隐式曲面表示方法 山东大学博士学位论文 图1 4 显示了两个隐式曲面的例子。但是，由于隐式曲面的拓扑过于自由， 有些隐式瞳面的拓扑可能非常复杂，甚至很难绘制出来。曲面的几何形状不直 观，而且难于控制，微调其参数也会引起拓扑类型发生不可预测的变化，可能 出现满足方程的盹面片却违背设计者本来意愿的情况。而且，隐式曲面没有提 供参数化信息，纹理映射等操作比较困难。 111 4 网格曲面 近年来，多边形网格曲面在计算机图形学和几何处理中得到了广泛应用， 多边形网格是采用点、线、面来表示三维几何数据，其中，点定义了网格的几 何信息，线和面则定义了网格的拓扑信息，即顶点之间的连接方式。多边形网 格的表示方法中不仅包含曲面的形状信息( 拓扑信息和几何信息) ，还可以包含 曲面的其他属性，比如网格顶点的颜色、透明度和纹理信息等。图15 显示了 一个网格模型实佣。 ( a ) 两悟模型( b ) 带纹理的网格模型渲染结果 圈1 5 网格表示 网格曲面的数据结构简单，与目前的硬件显示渲染结构最相符合，非常适 合用于多媒体和人机交互，因此非常易于存储和绘制，而且可以表示任意拓扑 的曲面，对光滑曲面的逼近精度可控，逐渐成为图形学中流行的陆面表示形式， 网格曲面表示方法的广泛应用也促进了离散微分几何研究的发展。 网格模型一方面可以由设计人员使用3 d 建模软件( 比如3 d sm a x ，m a y a 山东大学博士学位论文 等) 设计得到；另一方面可以通过对现实中物体进行三维扫描获得。随者三维 扫描获取技术的不断发展，人们很容易就能将现实物体转化为网格模型数据， 因此网格模型越来越流行。 1115 点云曲面 点云是几何模型表面采样点的集台，其数据结构比网格更加简单，只需存 储点的信息，而点足最基本的几何定义实体。与嘲格相比，点云表示方法中没 有拓扑信息，表达能力更加灵活，可表示任意的几何形状，而且不受连续性的 要求。近年来，由于几何数据模型越来越复杂，存储和处理多边j 移网格越来越 凼难；而且随着三维扫描技术的发展，获取的数据精度越来越高，使得仅需点 云数据就可以有效的表示几何模型。因此点云的研究受到重视，应用也越来越 广泛。如图16 就是点云表示的一个实例。针对点云表示的渲染和几何处理也 得到了广泛研究。 巍i 鬻 a ) 点云模型 2 数宇几何处理 圈1 6 点云表示 ( b ) q s p l a t i l 渲染结粜 数字几何处理中茸先需要研究的是高教的模型获取和表示方法。这方面的 工作包括点云重构网格( 5 - 7 等) ，网格简化( 8 1 3 】等) ，网格重剖( 如【1 4 一1 9 1 w ) ， 网格分割，点云、网格与样条等其他表示方式的转换等。 数字几何处理的研究重点之一是建立有效的处理工具来对模型进行处理。 对于网格而言，最基本的工具是参数化( ( 2 0 i 等) 。参数化主要研究如何将三维几 山东大学博士学位论文 何数据映射到一个参数域上，也就是寻找一个三维几何数据和参数域上点的一 一对应关系。此外，由于参数化过程中，三维几何数据本身和参数域之间一般 存在几何度量的差异，因此通常还希望映射后得到的几何体尽可能保留或近似 于原几何实现的性质。参数化能把复杂的二维流形映射到规则的参数域上，可 以起到化繁为简的目的，是很多具体应用的基本工具。 在此基础上，数字几何处理包含了很多基本问题的解决方法，这些问题包 括去噪与光j l 页l ：l , z 2 ，编码与压缩c 2 3 】，形状建模和处理( 如布尔操作、f f d 变形【2 4 l 等】、存储与传输等。随着三维模型数量的增长，数字几何处理研究的重心也从 如何获取数字几何模型以及对模型进行加工转换为对模型的分析与理解，并在 此基础上进行模型的处理和复用。 本文的研究工作主要基于网格形式表示的数字几何，围绕网格上的样条曲 面构造和网格模型变形技术进行了深入探讨。首先，研究了网格上样条曲面的 拟合，由网格模型获得更高质量的连续样条曲面表示。另外，已有网格模型的 重用也是一个重要课题，即研究如何使用已有的网格模型进行创作设计，比如， 由一个尺寸的模型得到另一个尺寸的模型，由一个姿势的模型得到另一个姿势 的模型等等，对这两个具体问题，本文分别给出了一种新的模型尺寸调整方法 和特征敏感的模型变形方法。 1 2 研究现状 本节主要回顾与本文工作密切相关的国内外的研究现状及进展情况。 1 2 1 网格上曲面拟合 由1 1 1 节可知，网格曲面表达能力强，可以表示复杂拓扑的曲面，并且易于 获得，比传统的样条曲面更适合于造型设计等应用，缺点是网格是分段线性的， 连续性不高：样条曲面虽然具有很好的连续性，但是在表示复杂拓扑物体方面存 在着许多困难。因此，从任意拓扑网格上构造高质量曲面问题就成为一个重要问 题。对此问题，目前主要有面片拼接模型，细分曲面模型，细分网格的样条表示 模型和基于流形的样条曲面模型等。 用现有样条曲面方法表示任意拓扑复杂形状的嗌面，最常用的方法是通过对 样条曲面的裁剪和拼接来实现。在实际应用中，已有的系统，l 匕女a l i a s w a v e f r o n t 山东大学博士学位论文 和s o f t i m a g e 等都使用了面片的裁剪和光滑拼接技术，但是这种解决方案存在以 下困难：裁剪比较费时，而且有数值误差；如果模型是动态变化的，那么要在曲 面的接缝处保持光滑度，即使是近似的光滑也是困难的。 文献 2 5 3 0 等介绍了一类方法，首先，对网格进行细分，然后在网格上构造 分片的三角b 6 z i e r 面片或者张量积b 6 z i e r 面片进行拼接。这种方法避免了费时的 裁剪，b 6 z i e r 面片拼接的连续性可以通过对控制点施加约束来实现。但是由于进 行了细分，所以，面片数较多，构造过程较为繁杂。l o o p 等 3 1 】提出的s p a t c h e s 是定义在凸刀边形域上的面片，它是三角b 6 z i e r 面片和张量积b 6 z i e r 面片在理论上 的统一和推广。l o o p 等 3 2 】使用s p a t c h e s 在不规则网格上构造样条曲面，在网 格的不规则处构造s p a t c h e s ，并且使之与周围面片的拼接满足连续性要求。但是， 由于边数玎的不同，面片的次数相应不同，整个曲面次数较为混乱，难于处理， 并且设计曲面时也不能通过简单调整控制顶点达到调整曲面形状的目的，设计过 程的直观性较差。 上述方法还在面片拼接方面存在如下问题：1 ) 拼接问题变为求解连续性约 束方程，随着连续性要求的提高，这种求解会更加困难。p r a u t z s c h 3 3 提出了一 种方法，在参数空间求解连续性约束方程，简化了求解过程，但是，在不规则点 附近曲面存在常曲率问题。2 ) 相邻面片拼接的连续性要由相关控制点的连续性 约束条件保证，如果模型是活动的，或者要通过调整个别控制点对曲面进行交互 的修改，那么，要保证相邻面片拼接的连续性就必须保持相关控制点满足连续性 约束条件，否则，不能保证连续性。3 ) 面片拼接方法着眼于面片的构造和拼接， 而忽视了曲面的整体性，不是真正的b 样条的扩展。 c h a i k i n 3 4 提出了一种切角算法，通过对控制多边形进行递归的切角从而得 到光滑的曲线，而且该曲线是均匀的二次b 样条曲线。受此启发，d o o 和s a b i n 3 5 】 以及c a t m u l l 和c l a r k 3 6 提出了任意拓扑网格上光滑曲面的生成算法，即 d o o s a b i n 细分曲面和c a t m u l l c l a r k 细分曲面。对规则的控制网格，d o o s a b i n 细 分产生的是均匀双二次b 样条曲面；c a t m u l l c l a r k 细分产生的是均匀双三次b 样条 曲面。所以，这两种细分曲面分别是双二抽样条曲面和双三次b 样条曲面在任 意拓扑上的扩展。s e d e r b e r g 等【3 7 】又将d o o s a b i n 和c a t m u l l c l a r k 细分曲面推广到 了非均匀细分的情况。 山东大学博士学位论文 皇曼曼曼曼曼寰：- _ -_ _ _ _ - - _ _ mmm mmm l i ! 细分曲面通过对b 样条曲面的细分得到规则点处的细分规则，然后扩展到不 规则点处，从而突破了b 样条的拓扑局限，成为表示任意拓扑曲面的有效工具。 细分曲面方法不需要裁剪，不需要面片拼接，没有接缝，其连续性自动得到保证， 因而可以方便的通过调整控制点进行修改而无需考虑保持连续性。h o p p e 等 3 8 】 和d e r o s e 等 3 9 】通过对细分规则适当的修改，使得细分曲面可以描述尖点、折痕、 镖形过渡点等不连续的特征，扩展了细分曲面的描述能力。但是，细分曲面毕竟 来源于曲面的绘制算法，是一种离散曲面造型方法，所以在曲面的传统表示方面 存在先天的不足，如没有解析表达式，细分曲面的精确计算比较困难。而且，原 来一些比较成熟的用于n u r b s 曲面建模的工具不易用于细分曲面建模中。 针对细分曲面存在的上述问题，d e r o s e 等 3 9 】首先提出了将细分网格变换到 样条表示法的思想，但是使用的是大量的小面片，而且在网格不规则点处的变换 不够好。n a s r i 和p e t e r s 4 0 使用d o o s a b i n 细分曲面的逼近曲面来近似计算细分闭 合体的体积，但是，使用的逼近曲面仅仅是c o 连续的。p e t e r s 【4 1 】给出了一种从 c a t m u l l c l a r k 细分网格得到m 瓜b s 面片的方法p c c m ，可以在任意细分层次网格 上用s t a n d a r ds p l i n e ( n u r b s ) 面片得到其显式的曲面表达式，而且面片的个数 等于初始四边形网格的四边形个数。p e t e r s 4 2 提出的算法可由三角形网格得到光 滑、低次的多项式曲面，其中使用的是四次三角b 6 z i e r 面片。j i nj i n z h e n g 等【4 3 】 首先对网格最多进行两次c a t m u l l c l a r k 细分，然后，在网格不规则点周围构造c 2 连续的g r e g o r yp a t c h ，在网格规则处构造双三次b 6 z i e r 面片。从而，整体上达到 c 2 连续。 上述方法，通常只能达到一阶或者二阶连续，为了寻求曲面的高阶连续性， n a v a u 和g a r c i a 4 4 基于流形技术也提出了一种任意拓扑曲面的造型方法。但 是，该方法建立在较为复杂的数学基础之上，计算耗费较大。 综上所述，现有方法虽然可在任意多边形网格上构造拟合曲面，但这些方法 和规则四边形网格上的b 样条曲面方法相比，在造型方式上明显不同，远不如b 样条曲面方法简单直观。因此，目前关于任意拓扑网格上的曲面构造的研究结果 还远远不能满足实际应用的需求。如何将b 样条曲面方法扩展到任意拓扑网格 上，找到一种任意拓扑网格上的b 样条曲面表示方法就成为亟需解决的问题。这 将为曲面造型提供新的理论和方法，为动画和电影特技制作、虚拟现实等领域的 山东大学博士学位论文 应用提供有效的新工具。因此具有重要的理论意义和实际应用意义。 1 2 2 模型尺寸调整 三维模型的尺寸调整，本质上是一种特殊的模型变形方式。目前主要的网 格模型变形方法有基于空间的变形，基于表面的变形，多分辨率的变形等。早 期的变形方法都是假设模型由同一种材料组成，变形是均匀分布的。因此，为 了有效的处理包含多种材料属性的模型，又引入了材料相关的模型变形方法 4 5 4 7 】，根据材料属性的不同，变形在模型上的分布是非均匀的。但是，使用 现有的变形方法对模型进行非均匀缩放，不仅需要施加复杂的约束条件，还要 指定相应的材料属性等等，操作过程通常是比较繁琐的。因此，这就有必要对 模型的缩放问题进行专门的研究。 最近，在图像和视频领域，内容相关的尺寸调整已经得到广泛的关注和研 究 4 8 5 2 】。a v i d a n 等 4 8 】展示了通过将误差分布到有限的“缝”集合，图像的 大部分像素维持不变从而使图像的整体得以保持。与此相反，g a l 等 4 9 】提出的 方法采用全局的观点使误差在所有像素内分布。这样的全局观点使得图像的重 要区域可以旋转或者均匀缩放，从而将误差尽可能的分布到非重要区域。 2 0 0 8 年，v l a d i s l a v 等【5 3 】将内容相关的图像尺寸调整推广到三维网格模型， 提出了一种基于空间的非均匀尺寸调整方法。首先将网格模型嵌入到保护性栅 格中：接下来基于面的s l i p p a g e 敏感性分析和法曲率，确定每个栅格的缩放因 子；然后将模型的整个栅格缩放到指定大小；最后，重新计算得到新的网格模 型。最近，w a n g 5 4 等基于表面的变形方法，也提出一种内容相关的三维模型 尺寸调整方法。该方法通过边的敏感性分析( 也是根据s l i p p a g e 和法曲率) ，确 定每条边的可伸缩性，采用迭代的方法逐步将模型缩放到指定的大小，将缩放 带来的变形主要分布在非敏感的部分。这两种方法，能够在一定程度上保持模 型的敏感区域，但是都不能精确保持某些特征，这使其应用受到很大的局限。 对网格曲面的约束变形问题，m a s u d a 等 5 5 】基于表面的变形方法，由用户 提供重要性映射，从而将扭曲变形分散到整个模型。在变形中，通过硬约束保 持某些重要的f o r mf e a t u r e s 及其可能的共线、共面关系。 对带约束的n u r b s 曲面缩放最初的方法是z h a n gp 等 5 6 】提出的 a t t a c h a n d d e f o r m 方法。该方法先把原曲面按要求进行缩放，然后把要保持的 1 0 山东大学博士学位论文 特征附加到已缩放的曲面上。附加特征的操作会使已缩放的曲面产生变形，为 了保证这个变形最小，使用了一个目标函数。该方法效果不甚理想，所允许的 放大倍数很小，且曲面特征不能保持完全不变。2 0 0 1 年，z h a n gc 等【5 7 】提出 了f i x a n d s t r e t c h 方法，该方法能够允许更大的放大倍数，且可以保证要保持 的特征完全不变。该方法的基本思想是先将给定曲面上含有特征和剪切曲线 ( t r i m m i n gc u r v e ) 的区域固定住，再延展曲面的其余部分，使其和靠近边界的部 分光顺地过渡。伯彭波等 5 8 采用一个完全基于几何概念的新的目标函数 导矢叉乘目标函数。该目标函数在导矢叉乘平方的积分意义下，保证了两曲面 在各点的法向尽可能地接近，从而在高光线意义下保证了新、旧曲面的形状最 为接近。上述几种带约束的n u r b s 曲面缩放可以保持曲面上含有特征和剪切曲 线的区域形状不变，但是，对其余区域采用的是均匀缩放的方法，而且，这些 方法还没有用于网格的缩放。 1 2 3 网格模型变形 一模型变形是计算机图形学中的一个常用的几何处理工具，主要是通过用户 的交互操作，使原始模型的形状发生变化，以表达用户特定的创作意图。在动 画等应用中，如果对每个三维模型和三维模型的每个姿势动作都进行数据采集 或者重新建模不仅效率低下，而且往往难以保证连续模型之间的对应关系，不 能重用已有的纹理外观等属性信息。因此，大多数已有变形方法都充分利用原 网格的