（计算数学专业论文）基于细分的保弧长曲线变形.pdf

基于细分的保弧跃曲线变形 摘要 在几何造型、计算机动画和数渤工等领域中，变形是类具有重要作用和广泛应 用的技术。目前已有的空间变形技术和自由变形技术已经能够允许用户直观对物体进行 交互式的操作，并得到较好的变形效果。其中带约束，尤其是体积、面积、弧长等复杂 几何约束的曲线曲面变形问题是研究工作中的热点和难点。体积和面积约束下的变形已 有一些研究涉猎。而由于弧长计算的复杂性，目前尚无十分有效的方法可以实现带弧长 约束的曲线变形。 本文对国内外现有的带约束曲线曲面变形方法做了广泛研究的基础上，提出了_ 十 带弧长约束的曲线变形方法。采用离散的细分表示统一了曲线形状信息与弧长信息的统 一，对由曲线简化而得的控制折线的变形可以实现作用于曲线上任一点的变形，对控制 折线的细分重新得到光滑、包含细节的曲线；而在简化过程中弧长损失的记录和细分过 程中张力参数的控制保证了曲线弧长在变形前后局部和全局都是不变的。 本文在文中给出了模拟实验的结果，表明应用该方法可实现带弧长约束的曲线的变 形，同时还可以很好地保持曲线上的细节信息和光滑眭。因此该方法将在在游戏电影动 画制作、服装c a d 等领域有着良好的应用前景。 关键词：变形；弧长约束：细分；优化；简化 基十细分的保弧长曲线变形 a b s t r a c t i nf i e l d so f g e o m e l r i cm o d e l i n ga n dc o m p u t e ra n i m a t i o n , d e f o r m a t i o ni sa u s e f mt o o lt o s i m u l a t et h em a n i p u l a t i o na n do p e r a t i o na n dh a sb e e n e x t e n s i v e l y s t u d i e di nr e c e n t y e a r s g r e a t p r o g r e s sh a s b e e ni l a d ei nt h i sf i e l d , h o w e v e rt h es o m e p r o b l e m o f d e f o r m a t i o nw i t hc o 蛐t s a r es t i l lr i o t e n t i r e l yr e s o l v e d , f o re x a m p l e t h ev o l u m ec o m a a i n t ，t h ea r e ac o n s t r a i n ta n d a r c - l e n g t hc o n s t r a i n t t h ea r c l e n g t hc o n s l 吐 l ti sd i s c u s s e di nt h i sp a p e r i nr e a lw o r l d , w h e na no b j e c ti s d e f o r m e d , i t sj 嘞u s u a l t yr e m a i n sc o r l s l a l l lt h ew o r kp r e s e r a e di nt h i sp a p e rf o c u s e so n a r c - l e n g t hp r e s e r v i n gd e f o n - n a f i o n t h ec u r v ci sf i r a l ys i m p l i f i e di n t o ac o n l r o lp o l y l i n eb y r e c o r d i n gt h el o s ta r c - l e n f f d a 1 m p l e m t m tr e q u i r e dd e f o r m a t i o no n t h ep o l y l i n e t h ea l g o d t h m c o m p u t e st h en e w n o d ep o s i t i o n0 f 血ec o n t r o lp o l y l i n e , w h i l em i n i m i z i n gt h ek i l 埘ce n e r g y s u b j e c tt oj o i n ta n g l el i m i t f i n a l l y , a p p l ys u b d i v i s i o no nc o n l r o lp o l y l i n et 0o b t a i nas m o o t h c u r v e t h ep m a m e t e r so f t h es u b d i v i s i o ns c h e m ea l es e l e c t e dt op r e s e r v et h ea r c - l e n g t hu p o n e a c h s e g m e n t t h er e s u l t so f t h ee x p e r i m e n t si n d i c a t et h a tw ea 1 0 ea b l et oa c h i e v ee f f i c i e n td e f o r m a t i o n so n h i g h - d e t a i l e dc u r v e s a n dt h ed e f o m a e dc u r v eh a sa tl e a s tc c o n t i n u i t y t h i st e c h n i q u ea l s o p r o v i d e si n t e r a c t i v e1 1 e s p o n s eb yp r o g r e s s i v e l yr e f i n i n g t h es o l u t i o no f t h e o p t i m i t a f i o np r o b l e m , t h u si tw i l lh a sg o o d f o r e g r o u n do f a p p l i c a t i o n i nf l l i l l l a l i o lf o r 群i m e sa n d f i l m s ，s i m u l a t i o nf o r c l o t h ，a n dr o b o t sp r o g r a m m i n g k e y w o r d s ：d e f o r m a t i o n ；a r c - l e n g t hc o n s t r a i n t ；s u b d i v i s i o n ；s i m p l i f i c a t i o n 基于细分的保弧长曲线变形 1 绪论 控制物体形状的变化是计算机动画中项重要的研究内容，目前控制形状变化的手 段主要包括m o r p h i n g 技术和交形技术( d 面曲a d o n ) 。m o r p h i n g 是指将给定的源物体光滑 连续地变换到目标物体的过程，而空间变形是指通过扭曲单个物体的形状而得到所需的 新形状。较之t l f o r p h i n g ，d e f o r m a t i o n 技术更灵活随意，所以常称为自由变形。该方法 具有良好的交互性，使用户在修改物体形状时，可以像雕塑家用油泥进行造型一样直观 方便：另一方面，此方法与物体的具体几何表示无关，从而使其能很容易集成到现有的几 何造型或动画系统中。 变形在力学中是指物体在力的作用下发生的形状变化，利用变形方法可以简化三维 几何形体的构造和编辑。1 9 8 4 年，a a r r 1 将这- - 思想率先引入到几何造型领域中的， 模拟力学中常见的几种变形，如拉伸( t a p e r i n g ) 、均匀张缩( s c a l i n g ) 、扭转( t w i s t i n g ) 和弯雎( b e n d i n g ) 等，并给出这些变形的数学表示。应用b a r r 的方法，可以生成许多 类型的三维几何形状，可模拟某些重要的制造过程，例如条料和板料的弯曲，由于该方 法仅能用于特定的几何形体，一般称其为非自由变形技术。 之后，许多学者继续# 陈如何将自由造型方法融合至憔统的几何造型系统，以及如 何进行自由变形。1 9 8 6 年。s e d e r b e r g 和p a r r y 提出了自由变形( f r e e f o r m d e f o r m a t i o n ) 技术，简称f f d 2 。该算法假定物体削艮好的弹性，在外力作用下易于发生变形。其核 心思想在于：变形操作不直接作用于物体而是作用于物体所嵌入的变形空间；变形空间 变化，嵌 其中的物体的形状随之改变。其后的d f f d ( d i r e c tm a n i p u l a t i o n o ff r e ef o r m d e f o r m a t i o n ) 、e f f d 、r f f d 、n f f d 方法都是在f f d 方法基础上的自由变形技术领域的重 要进展。 鉴于许多物体的变形具有轴向性，l a z a r u s 等人 3 提出轴变形方法( a x i a l d e f o r m a t i o n ) 。这是种基于参数曲线的变形技术。在轴变形方法中，用户首先根据物 体变形的要求定义一条轴向参数曲线，将变形物体附在轴曲线的局部空间中，然后甩传 统的曲线编辑技术修改轴曲线的形状，变形则由轴线自动传递给物体。同样基于参数曲 线的变形技术还有基于广义d e c a s t e l j a u 算法的变形和w i r e s 变形。 空间变形( s p a c ed e f o r m a t i o n ) 与上面的方法不同，不需要嵌入参数空间，而是直接 操作物体上的点进行变形。近年来，i 塞：类技术也得到了迅猛的发展，出现了许多新的变 形方法以及原有方法的有益改进。 基于物理模型的变形是另一类重要的变形方法。较之于月村模型，物理模型计算量 较大，速度慢，但是它具有萁实性好，用户干预少，适用性广等优点，在软 本咬形和服 装c a d 领域有着重要的意义。物理方法般可以分为连续模型和离散模型两种。连续模 型主要建如生弹性理论基础上，模拟塑料、橡皮等高弹物质得到了 晦的效果。离散漠 型主要有质簧模型和粒子模型。静扩泛应用于人脸的造型与动画以及眼姿濮拟 基于细分的保弧长曲线变形 等领域。而粒子模型主要用于纺织品的变形模拟中，将布离散化后求解系统的最小能量 状态以得到纺织品变形后的静态形状，或分析受力，根据牛顿第二运动定律可得布的动 态变化情况， 此外，目前热点的研究方法还有：基于参数曲面的变形基于约束的变形。我们将在 第二章对变形方法加以介绍和总结。 1 2 基于复杂几何约束的变形 所谓基于约束的变形一般是指：变形时物体上的一些屙陛满足一定的约束条件。例 如，变形以后物体上的某个点能移动到指定的位置。约束变形技术的引入，使得用户可 以根据需要，实现对物体的更为精确的设计和编辑。 基于约束的变形最旱是由b o r r e l 和b e c l m a n n 提出来的 4 ，起初的约束主要者院点 约束。基于点约束的变形方法交互直观、计算速度较快。但是点约束较多时，约束求解 是通过计算伪逆矩阵方法的，变形结果可能会难以预料；另一方面变形效果要求的提离 也要求更多其他的约束，因而仅仅是点、线之类的简单约束已不足以满足当前变形的要 求，需要添加更为复杂的约束。如体积不变，形状保凸。 体积、面积和弧长分别是三维、二维和一维几何体的一种最基本的j 乙何属性，选择 它们作为变形约束显然是十分自然合理的。 体积不变的变形最早由p 缸p p o p o r t 等 5 首次提出， 6 7 8 等均对此问题做了研 究。孙岩松 8 提出并解决了保持面积不变的二维几何体变形问题，通过加入视觉标准， 迭代求解面积约束方程组，计算得到变形结果。 目前尚没有卧十分有效撇可以解决带争帐约束的曲线变形问题e w a n g d 酃n e 9 首次提出并解决了有弧长约束的平面曲线设计问题，用三次样矧西直于给定垂! 直点，且 j l 近任意两相邻节点间的弧长。但是静态的插值疗法不够灵活，且用于自由变形难以保 证局部弧长不变。金小刚、彭群生等 i o ，1 1 提出了弧长不变的曲线m o r p h i n g 方法， 在源曲线与已知的目标曲线弧长相等的前提下即可保证变形过程中弧长不变。但文中没 有提及如何得到与源曲线弧长相等的目标曲线a 1 3 本文的主要工作 本文主鄹f 究带复杂月侗约束，尤匡是带弧长约束的变形。在第二璋，我1 f 总结现 有空间变形技术，综述当前复杂几何约束条件下变形的已有工作 第三章中，我们提出一种基于刚性关节链模型的折线变形算法，这种方法可以有效 地实现点约束下一端固定和两端固定的折线变形，并且在此过程中保持折线的每一段长 度不变。 第四章中我们提出一种基于细分的保弧长曲线变形方法。在变形操作开始前逆翰p 数 据简化，从而使变形过程中需要处理的数据量大大减少，适用于大信息量高度细节化的 曲线变形。同时简单的细分准则自动生成变形后曲线，并能保证曲线的光滑性。 基于细分的保弧长曲线变形 2 变形技术 在几何造型和计算饥动画领峨通过传统的编辑技术如变换、拉动顶点或控制顶点， 固然可以对个已初步设计好的物体进行整体的调整，如弯曲、扭曲等，但是，如果物 体的形状非常复杂，则这种方式就会变得几乎不可行。因此，变形技术已经成为一种越 来越重要的工具。 变形数学上可看作是一个由r ”到自身的映射 1 2 ，x = f ( x ) ，其定义域是待变形 物体表面所包围的实体，其值域是变形后的物体。所以，关键问题是如何构造此映射， 使模型的构造具有较好的直观陛、交互性和透明性。所以，好的空间变形技术应具有自 然直观的特点，用户只需控制点、曲线、控制网格或其他简单体素，就能够直接控制复 杂的物体的形状。从这个意义上说，空间变形技术，就是把复杂物体的变形转化为简单 物体的变形。以下我们主要介绍当前空间变形技术的发展情况。 2 1 自由变形技术f f d 2 1 1b a i r 的整体和局部变形及其改进 b a r r 将尖角( t a p e r i n g ) 、扭曲( t w i s t i n g ) 、弯曲( b e n d i n g ) 以及它们的组合变形定 义为一个从r ，到自身的映射，该映射表达为变换矩阵的形式，而变换矩阵是位置的函数。 但是这种方法缺少直观的控制手段，后来w a t t 发展了b a r r 的方法 1 3 3 ，他扩展了 b a r r 的因子曲线( f a c t o rc u r v e ) 的定义范围，即因子曲线不仅包括空间域而且包括时间 域从而增加了变形过程中的控制方式。 b a r r 的整体非线性变形和w a t t 的时空因子曲线方法都不同程度地依赖于某种解析 表达式，不便于进行统一的控制，金小刚等 1 4 首次对因子曲线进行了分类，提供了种 统一的基于f a c t o rc u r v e 的控制方式，因而非常适合于动画系统把因子曲线本身作为 可变参数的动画控制方法不仅包含了b a r r 的t a p p e r i n g 和t w i s t i n g 操作，而且还包含 了w a t t 的因子曲线控制方法因而动画师有更多的余地进行有效的操作 2 1 2 自由变形技术f f d 自由变形的想法最早出现于文献 2 ，其核心思想在于：变形操作不是直接作用于物 体，而是作用于物体所嵌入的变形空间：如果变形空间被改变了，则嵌入其中的物体的 形状自然随之改变。 f f d 算法的前提是：物体具有很好的弹性。容易在外力的作用下发生变形a s e r d e r b e r g 和p a r r y 构造了个长方形框架，该框架由个均匀剖分的三参数张量积b e z i e r 体的控制顶点组成，称为l a t t i c e ：然后将待变形物体线性地嵌入到此框架中， 基于细分的保弧长曲线变形 当调整l a t t i c e 中的控制顶点位置时，参数体的形状会发生变化，嵌入其中的物体就随 之变形。具体如下： 1 在个包围待变形物体的长方体中构造局部坐标系o s t u ，如下图所示： z x 8 图2 1 构造局部坐标系 f i 9 2 1c o n s t r u c t l o c a l c o o r d i n a t e 其中以( d ) 为局部坐标系的原点，s ，y 和u 是轴矢量，笛卡儿坐标系o - - x y 中任 一点x 在局部坐标系中具有坐标( s ，t ，k t ) 。 x = x a + s s + t t + u u 式中为局部坐标系的原点。而s ，t ，u 分别为： t u ( x x d ) 炉了瓦矿 s x u ( x 一工o ) ”i 聂万f 一 “：s 。t 。( x - x o ) ( 2 。0 ) “2 了函矿 ”“7 显然，对控制框架内的任意点x ，局部坐标满足：0 s j ，“1 2 构造控制顶点 在长方体上构造控制顶点网格9 j 。，分别沿s ，t 和u 三个方向用平行于 0 ，丁uo s u 和o s t 坐标面的等距截面将d 苫0 t 和0 7 u 等分为，m 和竹个区间， 日j j q , 。可表示为： q 。= d 7 + ；s + 丢丁+ 告u ( z - ， i = 0 , 1 ，；j = 0 , 1 ，m ：k = 0 , 1 ，。，玎 框架内任意一点的笛卡儿坐标x 可以表示为： 4 基于细分的保弧长曲线变形 fm” x ( s f ，“) = q f 。e ( s ) b ，( t ) b k ，( “) ( 2 2 ) i = 0j = 0k = 0 式中b 。，( j ) ，b j ，。( ，) 和曰( “) 分别为，m s t l n 次b e r n s t e i n 多项式基函数。 由上式可知，变形物体上的点是，mx 拧个控制顶点的线性函数，可以将方程改写为 并= b q ，式中b 为个单行矩阵，其元素为样条基函数，每元素对应一个控制顶点。 q 是，m n 3 矩阵，其每一行为个控制顶点坐标的三个坐标分量。 3 变形后点的表示 建立了物体与框架的相互关系之后，用户可以通过改变q 聃的位置得到新的控制顶 点q 和变形后的控制框架，若原来控制框架内任一点x 所对应的局部坐标系是 ( s ，t ，u ) 。则该点在框架变形后所对应的笛卡儿坐标系x 倒可由下式变形规则来确定。 删= q ；b 1 f ( s ) b ，( 0 8 。，( “) ( 2 3 ) 性方程组。在用b e r n s t e i n 多项式来表示变形映射时，若原控制顶点满足式( 2 1 ) ，则 局部坐标可由式( 2 o ) 确定。为了讨论非线性方程组的求解过程，我们假定所用基函数 方程( 2 2 ) 所提出的非线性方程组，为了方便于分析讨论，我们可以将其写成向量的表 x = i ，f t x ，= 至虽1 ，x = 朝。 正q ) ：圭宝宝只：，。e ，o ) b j ，( f ) 瓯，( “) 一x ，即控审4 丰匡架顶点的x 方向坐标关于 墨，；( j ) ，b j ，( f ) ，玩3 ( ”) 的6 4 项线性组合； 五( x ) = x 。e 。x 3e , , ：。昼，( s ) 目，( ，) 取，( 越) 一y ，即控制框架顶点的，方向坐标关于 8 ( s ) ，b ，( f ) 和风，( 拓) 的6 4 项线性组合； 苎王塑坌塑堡墨堡些些变兰 333 六( z ) = 只：。b j ，( s ) q ，( f ) 吼，似) 一：，即控制框架顶点的z 方向坐标关于 i = 0j = 0 女- o b ( f ) ，b s 3 ( f ) 和风，3 ( “) 的6 4 项线性组合；只：彤以分别表示控制框架顶 点的x 坐标值，y 坐标值，= 坐标值。则原来求解待变形物体上任意点的局部坐标的非 线性方程组( 2 。2 ) 则可写成形式：f r x l = 0 。 最后用变形的牛顿变形法来求解上面的非线性方程组。 f f d 方法可方便地融入传统造型系统；可保持任意阶的导矢连续胜；可控制体积变 化的程度，可整体也可局部地使用，是柔性物体中最适用的种方法。但f f d 也存在着 些局限，控制点与物体本身没有直接的关系，物体的变形有时不与控制点的变形保持 一致。缺乏经验的用户难以得至4 希望的变形结果。 图2 ，2f f i ) 变形 f i g2 2t h ef f dd e f o r m a t i o n 2 1 3f f d 方法的改进和发展 f f d ；手l 法的改进主要是对嵌入空间的形状和基函数等方面进行改进，荆哿它蝴到 人体动画和物体动态藜f 生变形中。 d f f d 1 5 的也采用控制框架作为变形工具，不同的是，变形的时候选择物体上一点， 将该点移至所要求得的位置，反算出控制点的位置变化，并计算出物体上其他的点。d f f d 变形操作的点少，操作效率高，对用户豹透明往商，容易获得所要求的形侮。但由予控 制顶点的反求是通过计算伪逆矩阵实现的，因而计算量较大，会影响实时交互。 c o q u i l l a r e 提出的扩展f f d 方法( 简称e f f d ) 1 6 使得初始的l a t t i c e 可以有更多的 形状，如棱柱体、圆柱体等，从而增加了f f d 技术的使用范围。用尸修改眶架的分割数 可以实现局部变形，但这种方法不够直观。结果难以预测。 宵理f f d 方法( 简称r f f d 1 7 把l m t i c e 表示为有理形式的三参数张量积b 6 z j e r 体，从而使用户还可以通过调节权因子来控带0 变形，但用户往往难以预测改变权因子可 能产生的变形结果。 j a r m u s i n 等人 1 8 提出了种基于n u r b s 的f f d 方法( 简称n f f d ) ，控制点的非均匀 基于细分的保弧长曲线变形 分布便于在复杂区域的形状调整。 1 9 9 6 年，m a c c r a c k e n 和j o y 1 9 提出了用任意拓扑的l a t t i c e 来控制物体变形，使 得变形控制更加直观和灵活。 2 2 基于参数曲线的变形 2 2 1 轴变形 f f d 方法具有很大的灵活性，但是当la t t i c e 中控制顶点数目较多时，调整l a t t i c e 中控制顶点的工作将变得繁琐和费时。考虑到许多物体的变形具有轴向性，1 9 9 4 年 l a z a r u s 等人 3 提出轴变形方法陬i a ld e f o r m a t i o n ，简称a x d f ) ，采用空间曲线控制 物体变形，牺牲部分变形的自由度来换取交互的灵活性。变形过程如下：( 1 ) 用户根 据物体形状和变形的要求定义一条空间曲线，作为轴向参数曲线，轴线可以在物体的内 部，也可以在物体外部；( 2 ) 将变形物体定义到轴曲线的局部空间中，建立物体与控制 轴线的关联，计算物体e 点在曲线的局部坐标系中的局部坐标。这一步是轴变形方法的 核心，对于物体上的一点，l a z a r u s 选取控制轴线上距离该点最近的点，作为与之对应 的点。由最小旋转标架定义轴的局部坐标系：( 3 ) 用传统的曲线编辑技术修改轴曲线的 形状，则轴线t l 动将变形俪整给物体。在轴变形中，轴线变形对物体变形效果起决定作 用，而核心的问题则是建立物体与控制轴线的关联。 为了实现局部变形，轴变形方法还定义了影响域。刀。和刀。分别表示以轴线为 中心的柱形区域，物体在刀。；。内的部分发生完全变形，刀。外的部分不变，两者之间 的那部分方法通过前述二者的插值得到。 轴变形是一种十分有用的设计工具，现实生活中很多物体的变形都可以用轴变形来 实现，如蛇的爬行，象鼻子的卷曲，绳子的弯曲等等。 c h a n g 等人提出了种基于广义d ec a s t e l j a u 算法的轴变形技术 2 0 。该方法的核 心是通过迭代仿射变换，使物体沿一条b e z i e r 曲线变形。由用户在b e z i e r 曲线的每个 控制顶点处指定两个坐标轴，以定义局部仿射坐标系。它与物体包围盒定义的局部坐标 系是线性对应的，这样物体与曲线之间就建立了对应关系。当拄制曲线的形状发生 变化后，通过广义d ec a s t e l j a u 算法计算新的物体点的位置。i 蝌荆去的优点是物体 的参数化过程简单，只需计算物体的包围盒；用户在曲线的每个控制顶点处都可以自己 定义局部坐标轴，能获得更加细致的控制。 2 2 2w ir s s 变形 1 9 9 8 年s i n g h 和f i u m e 提出了另一种利用曲线控制物体变形的技术一一w i r e s 变形 【2 1 。w i r e s 通过模仿画家和雕塑家的动作，用一组粗糙的曲线( w i r e s ) 近似物体的几何 7 基于细分的保弧长曲线变形 外形，同时对物体进彳亍形状控制。变形过程分为两步：首先将物体绑定到控制曲线毗r e s 上，同时引入各种局部控制手段，任何对控制曲线的编辑动作都反映到物体上，用类似 于m e t a b a l l 的密度场技术实现变形。 w i r e s 变形的优点是物体在曲线控制区域外的部分不会变形，能保证变形的局帮| 生， 具有局部放缩、旋转的功能；同时采用了光滑分布的密度函数，能保证变形的光滑性。 2 3 基于参数曲面的变形 应用f f d 进行变形时，控制变形的工具是一个参数三变元张量积的b e z i e r 体、b 样 条体或者n u r b s 体，被变形物体首先以某种方式嵌入这个体的参数空间，常用的嵌 方 式有两种： ( 1 ) 物体的坐标( x ，y z ) 和体的参数坐标( u ，v ，w ) 之间建立线性对应关系 ( 2 ) 对于被变形物体，生成其3 d 包围盒然后以这个包围盒的种平行于三坐标平面 的分割所生成的空间网格作为变形控制网格：对于位于网格中的每个采样点或控制顶 点，反求出其相对于控制网格的参数坐标( u ，v ，w ) 作为其局部坐标： 这两种嵌入方法各有优缺点：前者计算量小，但可控性差：后者计算量大，但可控 性较好。将物体嵌入参数空间网格后，当我们编辑控制网格的形状时，网格的变形就会 自动传递给被变形物体，雨在变形过程中，物体上的每一采样点或控毒频点相对于参数 空间网格的局部坐标保持不变。如果f f d 方法中3 d 空间网格中含有的控制顶点较多， 则在编辑其形状时会令人感到不方便。 另外a x d f 中物体嵌入的参数空间为曲线的参数及曲线上的局部活动标架控制变形 的工具为参数曲线。这种方式操作灵活，但是变形范围要比f f d 方法窄，因为物体只能 沿益线变形。 应用参数曲面作为变形工具的方法是近年来提出的种新的自由变形方法 2 2 ，是 对f f d 和h x d f 的个补充。在这种方法中，控制变形的工具既不是3 d 空间网格，也不 是参数曲线，丽是两个参数鳇面，分别为形状曲顶和高度曲面，其中形状曲面控制物体 变形的形状，高度曲面控制物体变形时沿形状曲面法向的伸缩程度。这两个参数曲面的 初始形状均为平面，通过投影和反求方法，物体上的点和形状曲面的参数域建立一对 应关系，在变形过程中，这种对应关系保持不变。这样参数曲面的变形就会自动传递给 物体。 参数曲面的初始形状都是平面，这限制了变形的灵活性，例如无法将物体变形到指 定曲面上。冯结青等 2 3 提出了种新的基于参数曲面的自由变形方法。首先，控制物 体变形的参数曲面的形状可以是任意的。将物体嵌入曲面的参数空间时。不需要反求局 部坐标，而只需要通过映射亟数。即可建立物体与参数曲面间的对应关系，从而减 少计算量。在变形控制方面，一方面可以调节参数曲面的形状和高度参数控制物体变形， 另一方面，可以调节映射函数控制变形。通过关键帧参数的设置，可以实现动态变形。 基于细分的保弧长曲线变形 图2 3 基于参数曲面的变形 f i g2 3d e f o r r m t i o na l o n gap a r a m e t r i cs u r f a c e 参数曲面变形方法包含两步映射：物体所在空间到变形空间的映射和变形空1 3 至j l 动 画空间的映鼽由于两步映射般是不等距的，从而致使各部分变形不均匀，造成了变 形之外不必要的扭曲。 2 4 提出了种基于参数曲面控制的均匀变形方法，变形控制曲 面首先以等距或局部等距的方式展开为平面然后经由平面的线性映射，将待变形物体 嵌入控制曲面的参数空间中，从而产生符合控制曲面形状的局部均匀变形。 2 4 空间变形技术 空间变形方法 2 5 ( d o g 征，d e f o m a a f i o no fg e o m e t r i cm o d e l se d i t o r ) 是由b o n e 和 b 。c h m a 咖首先提出的，用以直接操作物体上的点进行变形，而不再需要嵌入框架。接 着b e e h m a n n 又和a u b e r t 起提出了保持体积不变的空间变形方法。该方法将变形表 示为n 维空间的变形函数d ，设，为压苎富函数，则i 疆可以表示为： d ( u b ”2 朋( 3 0 n ) f ( u ) ( 。i ) 再用伪逆矩阵的方法求解矩阵m ，晟终转化为约束问题，求得i 蔺足约束条件的解。 这种基于d o g 娅模型的保持体积变形方法能同时保持垃移约束和体积约束，适于多面体 表示物体的直接操作变形。 总的来说，通常几何法运算量小，易于交互和实时操作。但是缺点是需要较多的人 工千预，真实性蓖而且效果往往渐动画师的专业知讽受经验。近年来俐算机 硬件的飞速发展及 们对造型的质量要求越来越高，人们开始致力于物理方法。 2 5 基于有向极坐标的变形 金小剐 2 5 提出了种运用方向极坐标的新的三维变形方法。这是一种基于形状混 合的变形技术，由用户指定源物体和目标物体a 9 摹于细分的保弧长曲线变形 图2 4 星形物体的有向极坐标定义 f i 9 2 4 t h e d e f i n i t i o n o f d i r e c t i o n a l p o l a r c o o r d i n a t e s f o r a s t a r - s h a p e d 喇e c t 物体0 称为星形的( s t a r s v l a p e d ) ，如果始终有一个中心点0 ，使得任何由中心点出发 的射线与曲面恰好相交一次，用 表示个星形的物体渤图2 4 ) ，则物体上任 何一点p 可以表示成( n ，d ) ，称为有向极坐标，其中盯是从中心d 到p 的单位方向矢量， d 是矢量o p 的长度。 用 和 分别表示源星形物体( 以o s 为中心) 和目标星形物体 ( 以0 。为中心j ，则对于给定的点p ，变形算法如下： 计算0 。到尸的方向刀； 计算o s 到尸的距离 由o s 出发，沿以方向的射线交源物体于g 计算从o s 到绕的距离k ； 计算d = ，s l s ： 同样的，得到目标物体上相应的点q 。，以及d 。至q o 的距离k ； 要将点p 变形为p = 0 口+ 甩d d ， 在源和目标空间表示之间插值： p = “l f ) t o x + f o d ) + n * d ( t f ) 三s + l d ) 基于有向极坐标的变形方法可以控制任意星形物体的变形如多边形、扫掠曲面、旋 转曲面、二次曲面等。变形过程直观目效率高，可以实现一些传统变形方法实现不了的 变形。 t 0 基于细分的保弧长曲线变形 图2 5 基于有向极坐标的足球的变形 f i 9 2 5 t h e d e f o r m a t i o n o f a s o c c e r b a l l b a s e d o n d i r e c t i o n a l p o l a r c o o r d i n a t e s 2 6 基于约束的变形 b o r r e l 和b e c h m a n n 最早提出了基于约束的变形思想 2 6 ，定义了点约束下的变形 方法。在文献 2 7 中，f 电4 门对一般的约束变形进行了改进，提出了简单约束变形模型 s c o d e f 将影响范围限制为球形区域，将互不影响的约束点之间相互隔离歼来。 基于点约束的变形方法交互直观，计算速度快，但是约束求解是通过计算伪逆矩阵 方法的，往往会产生多个解，从而使得交形结果不可预料。同时实际的变形中，经常会 需要变形满足其他方面的要求，尤其满足几何、能量等的些物体的内在的属性，会使 得变形效果更加逼真。 2 6 1 基于复杂几何约束的变形 2 6 1 1 体积约束 一一一嗍 一一一 n 一 董主塑坌竺堡墨堡些塑壅型 优化得到物体的变形形状，并通过约束点的位置或其影响半径爿芒坌田调，该方法计算量小， 但不同的优化方法导致不同的变形效果，存在一定不可控性。 h i r o t a 和等 6 同样采用最小化弹性能的方法计算f f d 控制网格节点位置，由于采 用了多尺度的曲面表示，减小了非线性优化的计算开销。 图2 6 基于多尺度优化的保体积f f d 变形 f i g2 6v o l u m e - p r e s e r v i n gf l e ef ：0 m ad e f o r m a t i o nu s i n gm u l t i l e v e lo p t i m i z a t i o n 2 6 1 2 面积约束 孙岩松 8 介绍了种新的空间变形方法，可以用来处理在变形过程中保持= 维几何 图形面积不变的问题。图2 7 是应用该方法得到的圆的变形结果，以及变形后圆的面积 变化率。 l oo o 左圈：面积变化率0 1 4 7 5 右图：面积变化率o f 4 2 5 图2 7 面积不变的空间变形 f i g2 7 a r e a - p r e s e w i n gs p a c ed e f o r m a t i o n 2 6 1 3 弧长约束 一、带弧长约束的平面曲线设计问题的提出 w a n g d a m m e 9 首次提出并解决了有弧长约束的平面曲线设计问题，用三次样条插值 于给定型值点且逼近任意两相邻节点阃的弧长。他们将有弧长约束的平面曲线设计表述 如下数学问题： 对于给定的函数，( x ) c 1 o ，l 】，以及给定区间【o ，l 】上的个分划 q = 扛o ，x l ，x 。 ，0 = x o x l - 工。= 1 ， 1 2 基于细分的保弧长曲线变形 我们希望找到三次样条s g ) c i i o ，1 1 ，并且s g ) 蓠足： ( 1 ) s b ) 插值于给定的节点处的型值 s ( x 。) = f ( x 。) ；，i = 0 , 1 ，仃 ( 2 1 ) ( 2 ) s ( x ) 逼近相邻两节点之间的弧长： l 扣面丽虮l i zr 扣丽 ( 2 2 ) i = 0 ，1 ，h 显然这里的 f f ) 二满足： ，。- 1 ( ，。一，) 2 + ( x 。“一x ，) 2 ( 2 3 ) i = 0 , 1 ，- 一，” 为了便于书写，记 s x f + i x ，h = m a x h , ，并且记为，i = h 工，1 7 9 _ s s ( x ) 为在节点处满足插值条件( 2 1 ) 的插值- t - f ( x ) 的分段光滑三次样条 s ( x ) c ，则s ( x ) 显然有如下表述： s ( x ) = h 2 ( f ( 1 + 2 h , - 1 ( z x ，) ) ( z ，“一x ) 2 + z i x ，+ l x ) 2 + ，：1 ( x x ，+ 1 ) ( x 一工) 2 + ，+ l ( 1 + 2 i 1 ( 工。“- x ) ( x - x 。) 2 ) = ：f o ( x ) + ，+ f ( x ) + ，研( x ) + ，：。g i ( x ) ( 2 4 ) f ( x ) 、e - 1 0 ) 、g ? ( x ) 、g ? ( x ) 定义见下式： 只。( x ) = l 一三! 苎+ 三! 苎i ；丝 肛华一华眦、 g m ) - ( 一j ) - 竿+ 孚 g 卜掣+ 孚 这里x 1 基于细分的保弧长曲线变形 在节点处的函数一阶导数值是未知的，因此我们还需根据已知条件，即曲线的弧长 ， ，i = 0 , 1 ， 来估计函数的一阶导数值。 d a m m e & w a n g 算法的基本思路如下： 首先构造插值于给定弧长 ! j ，i = o ，l ，h 的光滑样条函数。 考虑修改后的弧长函数： 三( x ) = 、f i l + ( f ( t ) ) 2 d t x ( 2 6 ) 三( 力满足类似于( 2 2 ) 的约束： 工( 一) = t ，一x ， ( 2 7 ) i = 0 , 1 ，一，h 显然l ( x ) 是单调函数。我们寻找满足插值条件( 2 7 ) 的函数g ( x ) ，并用如下方法估 计出，： l + ( s ( 工，) ) 2 1 = g ( ) ( x ，) = l + ( 厂( x ，) ) 2 1 则有： 陬圳= 拓葡酉虿丽 ( 2 8 ) 这里需要g ( x ，) 0 这样的g ( x ) 很容易找到。我们可以使用一些已经存在的保单调 性的算法，例如著名的f r i t s c h - - c a r l s o n 算法。 d a m m e & w a n g 在此基础上建立了如下算法： ( 1 ) 在节点处用阶均差7 估计函数的一阶导数值，i = 0 , i ，h ： ( 2 ) 用f r i t s c h - - c a r l s o n 算法的扩展形式沟造保单调的样条函数g ( x ) ，g ( x ) 至少属于 c 1 ，且g ( 工) 插值于数据k ，一置 ，i = 0 , 1 ，”， g ( z ) 三( 工) ( 3 ) 用步骤( 2 ) 得到的g ( x ) ，使用( 2 7 ) 式。估计 f s ( x 。i ，i = 0 , 1 ，行 ( 4 ) 用步骤( 1 ) 得至q 的z 1 ，决定( x ；) 的符号： 1 4 基于细分的保弧长曲线变形 s ，( ) = s i g ( y ；, ) 4 9 i x ) ( 2 + g “) ) i = 0 , 1 ，- 一，h ， 在特殊情况，：= 0 下，两个符号都可取 ( 5 ) 用h e r m i t e 插值公式并用已知节点处型值及步骤( 4 ) 得到的s ( x 。) 构造我们希望得 到的三次样条函数s ( x 1 。 此外d a m e & w a n g 还讨论了算法的收敛性并给出了误差估计定理。 任小波 2 8 】将该方法加以推广给出了有弧长约隶的空闯曲线插值算法和有面积约 束的旋转曲面插值算法。 类似地，j o h n 等 2 9 用b e z i e r 三次曲线解决了给定弧长约束及切线方向的插值问 题。林贵献 3 0 1 基于其原理，构造二次有理曲线，将弧长约束转化为单变量递增函数，并 推广到双变量情形，实现了满足弧长约束的平面曲线插值。 以上都是利用样条插值方法解决弧长约束下的曲线设计问题。插值的方法固然解决 了曲线曲面设计中的一大类问题，但这种静态的插值不够灵活，尚不足以满足自由变形 的需求。 二、基于弧长不变的曲线m o r p h i n g 方法 金小刚、彭群生等 1 0 ，1 1 提出了弧长不变的曲线变形问题。 基于弧长不变的曲线变形是制作动画实践中常遇到的问题。柔性物体的动画可由其 骨架线所控制，即用曲线的变形来控制物体的变形。在现实世界里，许多物体在变形过 程中，其骨架线的长度基本上是保持不变的。例如，大象在卷鼻子时，象鼻子盼长度可 认为是常数：鱼在游动时，鱼身的长臣阿_ 认为是恒定的；龙在腾飞时，龙身的长度也可 认为是不变的。 金小刚等先对b e z i e r 曲线进行离散，得到逼近b e z i e r 曲线的折线，然后对关键帧 折线的边长和有向顶点角进行插值，再把插值得到的折线拟合回与原曲线具有相同形式 的b e z i e r 曲线，从而使骨架线的长度基本保持不变。 其中弧长不变的b e z i e r 曲线变形过程如下： 设只( “) 和只0 ) 是具有不同形状和位置的两b e z i e r 曲线，且它们的弧长相等，即 s 。= s 。= s 。要采用关键帧插值方法将只( “) 平滑变形为岛( “) ，且在变形过程中曲 线的弧长保持不变。如果将b e z i e r 曲线的表达式直接代入弧长计算公式，很难求得具 有弧长约束的中间帧曲线，因此采用间接的方法，在满足一定精度的条件下，先将只( “) 和p r ( h ) 离散为折线多边形。在离散的过程中，保注两曲线离散后，对应的参数相等， 折线的边数相等。设经离散后，得到满足定精度的折线级，和9 。，i = o ，l ，2 ，m 。 采用t u r t l e 几何，通过计算折线的边长和顶点有向角，得到折线