（计算数学专业论文）带几何约束条件的空间变形方法.pdf

摘要 摘要 在几何造型，数控加工领域中。常常需要应用变形技术来处 理一些易于弯曲伸缩的物体。像模拟力学中常见的几种变形。如： 拉伸，弯曲，扭转，压缩等操作。在众多易于操作的交互式的变 形方法中，空间变形技术和自由形式变形技术( f f d ) 是两种功 能强大的变形工具，它们被广泛应用于数控加工和模拟计算机动 画领域。这些技术的派生和改进允许用户能够直观地对物体进行 变形。但是从来没有一种变形方法解决了在变形过程中加入几 何约束条件的问题。在论文的第二章中，我们详细介绍了自由变 形造型方法及其推广的模型；在论文的第三章中，我们介绍了一 种新的空间方法，它可以用来处理在变形过程中保持三维物体体 积不变和保持二维几何图形面积不变的问题。我们提出的方法是 建立在名叫d o g m e 的空间变形模型的基础上。通过引入优化项 和迭代方法，改进了d o g m e 模型，从而解决了变形过程中带有 几何约束条件的问题。 关键词：空间变形，自由变形技术，迭代法，参数空间，优化项 约束顶点。 a b 舛r a c a b s t r a c t i n g e o m e t r i cm o d e l i n g ，t h em a n i p u l a t i o no fo b j e c t sm a yn e e d c o m p l e xo p e r a t i o n ss u c ha sc o m p r e s s ，e x p a n do rt w i s tap a r to fa n o b j e c t s u c ho p e r a t i o n s a r eu s e f u lt of o t i nc o m p l e xs h a p e so rt o s i m u l a t et h eb e h a v i o ro fa l lo b j e c t f o re x a m p l e ，d u r i n gas t r e t c ha n d ab u m p s e v e r a ld e f o r m a t i o nm o d e l sp r o p o s ei n t u i t i v em e t h o d st o d e f i n et h e s ek i n d so f 丘e ef o r m o p e r a t i o n s i n t h e s es k i l l s f r e e f o r md e f o r m a t i o na n d s p a c e d e f o r m a t i o n t e c h n i q u e s a r e p o w e r f u lt o o l sw h i c h c o u l dm a n i p u l a t ea n da n i m a t eo b j e c t s al o to f e x t e n s i o n so ft h e s e t e c h n i q u e s a l l o wu s e rt o i n t u i t i v e l y d e f e l r m o b j e c t s b u tn o n eo f t h e s ep r o p o s eas o l u t i o nt op r e s e r v et h ev o l u m e o fo b j e c t so rt op r e s e r v et h ea r e ao f g e o m e t r i cf i g u r et h r o u g h o u tt h e d e f o r i l l a t i o n i nt h i sp a p e r , w ei n t r o d u c ef l e ef o r md e f o r m a t i o ni n d e t a i l sa n dw ea l s oj n t r o d u c ean e wm e t h o dt od e f o r ma no b j e c to rt o d e f o f i naf i g u r e i t sv o l u m eo ri t sa r e a b e i n gp r e s e r v e d 0 b rm e t h o d i s b a s e do nt h es l ：i a c ed e f o r r n a t i o nm o d e lc a l l e dd o g m e w eu s e a d i s t i n c t i v ef e a t u r eo fd o g m et os o l v et h e p r o b l e mo fv o l u m e p r e s e r v a t i o no ra r e ap r e s e r v a t i o n i nt h ep a p e r , w ea p p l yt h em e t h o d t 0t h e p o l y h e d r a lf i g u r ea n d t h er e s u l ti sg o o d k e yw o r d s ：s p a c ed e f o r m a t i o n ，f f d ，i t e r a t i v em e t h o d ，p a r a m e t r i c s p a c e ，o p t i m i z a t i o ni t e m ，c o n s t r a i n tp o i n t s 撼一窜绪论 第一章绪论 在几何造型和计算动砸领域中，变形技术已经成为种越来 越重要的工具。在几何造型中，变形技术可以用来模拟力学中常 见的变形，如拉伸，扭转和弯曲等。并且可以给出这些变形的数 学表示。在计算机动画领域，变形技术则可以用来模拟柔性物体 的变形，具有很大的应用价值。因为，在自然界中，动物的肌肉 是柔性的，动物运动时，其肌肉的变形是一种柔性变形。如人的 四肢运动，动物的爬行等。这些变形效果的模拟通过传统造型和 计算机动画技术难以实现。变形技术则较好的适应了这种需要， 从而引起了人们的广泛兴趣和重视。 我们下面介绍一下变形技术的发展背景和各种变形算法的数 学原理。 1 1 非自由变形方法和自由变形方法( f f d l 1 9 8 4 年，b a r r 首先提出了整体的和局部的非自由变形的方法 ( 见参考文献【1 】) 。b a r r 的非自由变形方法主要的结论有两个： 1 变形后物体表面上任意一点的法矢可以由变形前对应点的法矢 与一个变换矩阵计算得到，该变换矩阵与变形公式的j a c o b i a n 矩 阵有关；2 物体变形过程可以按照层次型结构组织，逐步地由形 状比较简单的物体变形成比较复杂的物体。因此，在b a r r 的非自 由变形方法中，变形可以表示为作用于物体顶点或控制顶点的变 换矩阵，而变换矩阵是空| t 目位置函数。通过这种方法，拉伸，弯 曲，扭转等变形可以简单的实现。可是，作为变形表示形式的函 数矩阵没能提供种直观的控制手段。所以有其r 一定局限r 阵。后 第一奇绪论 来，w a t t 发展了b a r r 的非自由变形的概念使f a c t o rc u r v e 既是 卒【- n j 的函数，又是时间的函数，从而使b a n 方法变的实用。 在8 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 md e f o r m a t i o l l ，简称f f d ( 见参考文献 1 ， 2 ) 。 在参考文献 1 9 中，有人把f f d 算法的实施比喻为雕塑家的 手，其每实施一次，相当于用手把整个物体雕塑一边，随着f f d 算法的逐次实施，最终把物体雕塑成所希望的形状。在s e d e r b e r g 和p a r r y 之前，已经有人认识到雕塑几何模型是一种自然而为人 们所熟悉的设计工作方式，曾提出过一些雕塑方法。但其应用范 围有很大的局限性：局限于多面体模型，或局限于某一类参数曲 面，而且不能直接作用于实体模型。而f f d 算法则可以结合进任 何类型的实体造型系统，也可以融入曲面造型系统。 f f d 算法的前提是：假定物体有很好的弹性，容易在外力的 作用下发生变形。应用f f d 方法造型时，需先构造一个长方体框 架，该框架是由三维控制顶点构成。由此框架和一组基函数构成 一个实体，所用的基函数是矢值三变量b e r n s t e i n 多项式。而后 将物体嵌入框架中，对框架施加外力使其变形，物体的形状亦随 之改变。框架的变形是由其上的控制顶点的变化而产生的。因此， 可通过框架上的控制顶点来改变和控制物体的形状。一般称该框 架为控制框架。 这种方法具有很大的灵活性和很广的变形范围，所以在几何 造型和计算机动画领域中被广泛应用。但这也绘用户带来一个问 题：当定义三维参数空间的控制顶点的个数非常多时，渊整这些 顶点的工作就会变得繁琐。s e d e r b e r g 等还研究了陌d 方法的连续 笫一章绪论 性控制，局部变形，体积摔制及其应用，并得出了许多有益的结 论。 s e d e r b e r g 和p a r r y 的方法具体讲大致可以分为四个步骤： 1 构造实体是实现f f d 算法的四个主要步骤中的第一步； 2 ，将待变形的物体嵌入该框架之中，确定待变形物体上任意 一点g ，y ，z ) 所对应的参数坐标( 虬v ，w ) ，一般情况下，该问题需要 f月，” 求解非线性方程组：x ( s ，“) = q 。蟹，( s ) 毛。，o ) 玩，弛) 。 i = 0i = ok = o 式中z 0 ，t ，“) 为物体上任意一点的笛卡儿坐标，e ，0 ) ，b ，m 0 ) 和 色。0 ) 分别为，肌和丹次g e r n s t e i n 多项式基函数，q 。，为控 制框架顶点。 3 第三步是对参数实体施加变形，这个过程通常由移动三维 框架的控制顶点来实现。 4 最后，计算框架变形对嵌入物体的影响，此时，通过第二 步所得物体上点的参数值和变形后的控制框架来计算变形后的物 ，mn 体上相应点的新位贸：z 。o ，t ，“) = q “t 毋，( s ) g ，( f ) b 。( “) ， i - - oy = ok - - o 其中d “为变形后控制框架顶点的坐标。 在本文的第二章，我们将详细介绍f f d 变形方法的数学模型， 并且具体实现了f f d 方法。( 参阅参考文献 7 ， 8 - 11 ) 。 在f f d 方法的基础上，人们进行了广泛深入的研究。其中， 扩展的自由变f ( e x t e n d e df r e e f o r md e f o r m a t i o n ，简称e f f d ) 年h 直接控制自由变形( d i r e c t m a n i p u l a t i o no ff r e e f o md e f o n n a t i o n 第一章绪论 简称d f f d ) 是两项比较重要的成果。此外，参考文献 5 】， 6 】中 提到的z h u 研究了纂于b 样条表示的变形造型，k a l r a 等探讨了 有理自由型变形( r a t i o n a lf r e e f o r md e f o r m a t i o n ，简称r f f d ) 的 应用，l a m o u s i n 等则研究了基于n u r b s 的自由型变形。 1 2d f f d 方法和其他自由变形造型技术 1 2 1 f f d 算法的问题 f f d 算法是一种非常有效的几何造型工具，但用其实现复杂 形体的变形则非常困难，用f f d 算法实现所要求的变形，可操作 的控制顶点很多，需要进行选择，而且屏幕上网格和物体的现实 混杂在一起，更增加了操作的难度，就变形物体而言，控制顶点 只是实现变形的一种工具，与物体本身无直接的关系，物体的变形 并不与控制顶点的位置改变保持一致。换言之，对控制顶点的操 作并非总能得到所希望的形状。 借调整控制顶点以实现变形的主要问题是： 1 难以准确控制物体的形状。 2 难以准确控制物体上点的位移。 3 不熟悉曲面造型的用户不易理解控制顶点的作用及移动控 制顶点可能产生的结果。 4 当屏幕上有许多控制顶点或者这些控制顶点的与变形物体 重叠时，操作将非常困难。 为了克服f f d 方法的缺点，需要采用一种新的算法。 1 2 2 d f f d 算法的提出 第一帝绪论 法( 参阅参考文献 1 2 ) 仍采用控制框架作为变形工具，它吸取 j f f d 算法的优点，克服了f f d 尊法的不足。应用d l 1d 铮法时， 用户操作的是物体上的点，而不是控制顶点，其核心思想是：选 择物体上的一点，将该点移至所要求的位置，反算出控制顶点的 位置变化，并计算物体上其它的点。d f f d 求解过程需要诩算矩阵 的广义逆( 在参考文献 1 4 ) 。在第二章罩我们会对d f f d 方法进 行讨论。 1 2 3 其他自由变形造型技术 下面简单介绍一下e f f d 和r f f d 两种变形技术。 1 扩展的自由变形造型技术( e f f d ) e f f d 算法扩广了f f d 技术，可使用非长方体框架，在参考文 献 1 0 c o q u i l l a r 定义了基本的和组合的棱柱形框架，通过移动 和合并长方体框架得到基本的棱柱形框架，组合框架则由基本的 框架组合而成，也可采用非棱柱形框架，但使用复杂的框架将导 致不可预测的结果。 基本框架由块状体组成，每一块由三变量三次b e r n s t e j n 多项式和4 x 4 x 4 控制顶点表示。为计算由基本框架的变化而产生 的变形，必须计算变形物体上的点在框架参数空间内的坐标。为 此，首先确定变形物体的点在那个块中，然后利用n e w t o n 逼近法 计算物体上的点在该块中的坐标，最后，个块中物体上点的变 33， 形公式由式子d ( u ) = 只0 e ，0 ) b 小o ) 眈，0 ) 定义。 i = o = 0 ；0 式中e ，( s ) ，b j ，( ，) 和玩，( “) 是三次b e r n s t e i n 基函数：麒是物 体上被变动的点；p o 是改变后的控制点。 粥章绪论 因为移动一个给定的控制顶点只改变对应块中的点，阕此用 块来定义基本框架a _ 以控制局部变形，用户可通过修改框架的分 割数使变形局部化。然而，如果用户不熟悉b e r n s t e i n 多项式， 则其分剖过程就难以理解。此外，这种方法没有提供直观的方法 来控制变形区域的尺寸大小，位置和边界。用户难以预测移动几 个控制顶点的局部变形。因此，这种方法适用于整体变形，用，o 通过操作框架来实施变形。 2 有理自由变形造型技术( r f f d ) 有理自由变形造型技术是f f d 方法的另一种扩广。应用该法 时，每个控制点均附加权因子，其初始控制顶点仍位于长方体框 架上。当每个控制顶点的权因子都等于l 时，与f f d 方法等价， 用户可以通过移动控制顶点或者修改权因子来控制变形，与前述 方法相同，在变形之前必须首先计算物体上的点在框架参数空问 的坐标变形函数由下面公式定义： 只：”彬，b i 。0 ) b 。：( f 圾， 0 ) d ) ：竺型 、兰宝芝彬。b i b i 。o ) q ，。( r 域，。o )艺彬。0 ) q ，。( r 域，。0 ) 式中彤。t 为与控制顶点曩对应的权因子；毋。g ) ，b 。：( f ) 和 b k , p ，0 ) 分别为n ，p 2 和a 次的b e r n s t e i n 多项式。 r f f d 和f e d 的区别在于：权因子提供了另一个控制变形的 自由度。然而，用户难以预测改变权因子口j 能产生的变形结果。 第一章绪论 1 3 各种自由变形方法之间的比较和分析 i ：f d 变形限于使用均匀分割的长方体框架，在实施过程叶 ， 需要沿框架的每个方向选择控制顶点数目，并将变形物体或其一 部分嵌入框架中，框架对应于变形区域。为使变形局部化，可仪 将物体的一部分嵌入框架，用户通过移动原框架的控制顶点来实 施变形。程序自动计算物体在框架参数空问内坐标和变形后的笛 卡尔坐标。这种方法非常适用于整体变形，要求局部变形时，应 适当处理与物体相交处的连续性问题。 e f f d 技术是f f d 的一个拓广，应用与f f d 相同的数学公式， 但变形工具是由几个任意形状的框架组成的复杂框架。每一框架 本身由一组基本块组成。用户可选择预先定义的棱柱形框架( 圆 柱体，球等) 或者通过合并几个框架而构造一个组合框架，其余 过程与f f d 类似，但局部坐标的计算比较烦杂，而且构造一个适 合的框架非常困难。 r f f d 是f f d 的另一拓广，每一控制顶点都对应一个权因子， 其交互技术类似于f f d 算法，可通过移动控制顶点或者改变权因 子来实施变形。由于权因子的影响很不直观一般难以通过修改 权因子来实现所要求的变形。 f f d ，e f f d 和r f f d 技术应用相同的数学公式，变形区域和变 形形状都依赖于基函数。为使变形局部化，初始框架应只包含物 体的一部分。这几种方法都没有提供特别的方法来控制变形区域。 d f f d 方法易于实现变形物体上点的精确移动。与前述各种方 法样，i ) f f d 力法也没有提供控制变形区域的工只。 变形造型技术的提出已经十几年了，可是理论和应用研究方 第- 章绪论 面还不成熟，很欠缺，尚未达到实用化。所以，有必要列变形造 型技术作进一步的研究。 1 4 轴变形技术 与自由变形技术相似的轴变形技术也是种借助于其他媒介 的变形方法。轴变形( a x d f ) 技术( 见参考文献f 1 7 1 ) 是由l a z a r u s 等人提出的。这是一种直观的变形技术。用户首先指定一条轴， 即一条空间参数曲线。待变形物体上的点根据最近点规则嵌入曲 线轴上相应点的局部坐标中。当曲线的形状改变时，物体的形状 也会随之改变。该方法的优点在于可以通过轴的变形来控制物体 的变形。c h a n g 等人基于广义的d ec a s t e l j a u 算法，提出了另一类 的轴变形方法。即首先在b e z i e r 曲线的控制多边形的每一点的起 始端点处建立一个局部放射标架，然后定义在造型空间中的物体 变换到上述局部坐标系中，再对物体作迭代仿射变换，从而实现物 体沿曲线进行变换。这种方法也具有操作简单的优点，而且计算 量小。 在上述变形方法，除b a r r 的非自由变形方法，其余的变形方 法均借助于其他的媒介，如三变元的参数体，参数曲线等。变形 时，将物体嵌入到中间媒介的参数空间，当媒介被变形时，物体 自然随之改变形状。由于从参数体或参数曲线的参数空间到物体 空间的映射是非线性的( 见参考文献 1 7 1 ) ，所以，在变形过程中 难以保持或控制物体的长度和体积， 为了更好的模拟物体的变形，我们可以在变形过程中加入一 第一章绪论 些j l 何约束条件。而上述的变形方法却无法实现这种想法，所以 我们需要寻找不同于上述变形技术的另一类变形方法一空间变形 技术。 1 5 空间变形技术( s p a c e - - d e f o r m a t i o n ) 1 9 9 0 年，b o r r e l 和b e c h m a n n 提出了基于空间变形方法( 见 参考文献 1 ， 2 ) 的数学模型。该模型被命名为 d o g m e ( d e f o r m a t i o no fg e o m e t r i cm o d e i se d i t o r ) 下面简单说明一下d o g m e 模型的基本原理。 在d o g m e 模型中，变形是定义在f 空间里( 通常我们都考虑 取n = 3 ) 的。空间变形过程需要给出一个变形函数d ：彤_ 彤。 设待变形物体上任一点u 的( 笛卡尔) 坐标为u = “，岵；q ，) ， 且点u 的位移为a u = 池，趣，- ；龇) 。那么我们就有下面的公 式： u = 荆= “) ，硅如) ，；也” 由于函数d 可以作用于月”空间中的任意一点，所以变形函数 d 就定义了整个空间的变形。虽然整个空间在函数d 作用下都会 发生形变，但是我们有时可以将变形应用到我们选定的一组点上。 我们通常考虑物体是由一系列具有拓扑关系的点来表示的。这样 变形就可以按照点的拓扑关系独立地修改和调整点的空间位置。 上面所提到的在空州中的变形函数d 是出一个函数利 一个线性变换r 复合定义的。下面给出在尺3 空间中的变形函数“ 第章绪论 的定义：d p ) ( 1 川= m b 卅1 、，眇 。) 。其中函数，是将席空问中的 点映射( 转换) 到r 空间，m 是任意给定的维数。而线性变换丁则 是函数厂的逆过平旱，它的作用是将彤空间中的点映射( 转换) 到帮 空间。而m 就是线性变换r 所对应的变换矩阵。 空间变形方法采用伪逆矩阵的方法来求解约束。物体变形的 形状，通过约束点的位置来控制，同时又可以用每一约束点的影 响半径来进行细调。该方法的计算量较小，可以在工作站上实时 实现。但是由于求解约束方程是一个优化问题，所以对于结果存 在一定的不可控性。即不同的优化方法导致最终变形效果不同。 在本文，我们应用了种迭代的方法来求解加入几何约束条件的 空间变形问题。并且作出了二维条件下的实例。 1 6 本文的主要工作 在上面，我们已经详细介绍了变形算法发展的历史和背景。 为了在众多的变形方法中选择合适的技术来研究处理问题，我们 需要提出一个分类的标准来将变形方法分类介绍和研究。在文中 我们所采用的分类的标准为：看变形过程是否借助于其他媒介。 按此标准，我们将变形技术分为两大类。前者为在变形过程借助 于其他媒介，比如自由变形方法( f f d ) ，此方法在变形过程需构建 三变元的参数体，与之类似的还有轴变形技术，该技术在变形过 程需要指定一条空间的参数曲线。我们取自由变形方法f f f d ) 和 d f f d 方法为这类变形方法的典范在第二章里详细介绍。在第二 章我们采用了简化的牛顿算法来求解f f d 方法在变形过程所提 笫一章绪论 出的非线性方程组，并且做出了三个f f d 变形实例来检验f f d 方法的变形效果和连续性。 而与上述变形方法不同的另一类变形方法是直接对变形物体 上的点进行变形操作，其过程不需要借助于媒介。例如空问变形 方法，还有一些空间变形方法的推广模型。在上面我们已经提到 过由于参数体或参数曲线的参数空间到物体空间的映射是非线性 的，所以，在变形过程中难以保持或控制物体的长度和体积。所 以要想在变形方法中加入几何约束条件，则必须由空间变形方法 入手考虑。本文在第三章详细介绍了空间变形方法的基本模型， 以及在基本模型基础上加入几何约束条件的d o g m e 模型。在三 维情况下我们加入了保持物体体积不变的几何约束条件；而在二 维情况下则加入保持图形面积不变的约束条件，并且做出了几个 简单的实例来分析误差。 筘二带自由= 盎= 形造型( f f d ) 与d f f d 第二章自由变形造型( f f d ) 与d f f d 2 1 f f d 变形方法的数学模型 变形，数学上可以看作一个由r 3 到凡3 的映射= 中& ) ，其 定义域是待变形物体表面所包围的实体，其值域是变形后的物体。 所以，关键问题是如何构造此映射，使模型的构造具有较好的直 观性，交互性和透明性。 s e d e r b e r g 和p a r r y 使用三变量张量积b e r n s t e i n 多项式 ( 参阅参考文献 1 5 ， 1 6 ) 和控制框架来构造映射m g ) ，其算 法模型如下。 2 1 1 构造局部坐标系 在一个包围待变形物体的长方体中构造局部坐标系 0 。一s 丁u ，如下图所示： x z 其中x 。( 0 。) 为局部坐标系的原点，s ，t 和u 是轴矢量，笛卡尔 坐标系o - x y 中任一点爿在局部坐标系中具有坐标0 ，r ，“) 。 ) ( = x b + s s + t t + u u 第二常自由变彤造型( f f dj ，l ) f f i ) 式巾。为局翻；学标系的原，_ 。而s ，t ，分别为 。一t x 坠塑 t u s f ：s x u ( x - x o ) “： 一 一 s u ts t 乙 ( 2 0 ) 姐然，对控制框架内的任意点，局部坐标满足：o ，t “1 。 2 1 2 构造控制顶点 在长方体上构造控制顶点网格q 。，j n n s ，7 和uj 个方向用平行于0 。t u ，0 s u 和0 。s t 坐标面的等距截面将0 s f ) t 和o u 等分为，m 和”4 区f b j ，则q 。可表示为： q 。t2 。+ ；s + 考r + ；u ( 2 1 ) i = 0 , 1 ，一，t ；j = 0 , i ，一，m ；k = 0 , 1 ，一， 框架内任意一点的笛卡尔坐标x 可以表示为： x ( s ，f ，“) = q 。e ，o ) _ b 。o ) b ，。u ) ( 2 2 ) t - - oj = ok = 0 式中b g ) ，b 。( f ) 和b k 。0 ) 分别为，m 和n 次b e r n s t e jn 多 项式基函数。 由式( 2 2 ) 可知，变形物体上的点是l x m x n 个控制顶点的线 1 件衙数- 可以将方程( 22 ) 改写为= b q ，式中b 为一+ 0 4 9 矩阶，其元素为样条基函数( 或b e r n s t e i n 基函数) ，每一，l 素i 列 应一个控制顶点。q 是l m 3 矩阵，其每一- t r 为一个控制顺 点坐标的i 个坐标分量。 2 1 3 变形后点的表示 建立了物体与框架的栩7 i ：父系之后，用户可以通过改变q “ 的位置得到新的控制顶点q 。荆j 变形后的控制框架，若原来控制 框架内任一点x 所刈应的局部坐枷、足( s ，r ，) 。i f ! l j 该点确二框架变形 后所对应的笛卡尔坐标。，可由下式变形规则来确定。 |m” 爿删= q 。e ，0 归。，( ，) b ”，妇) ( 2 3 ) s = o ，= 0 = 0 上式表明，由新的控制顶点计算变形后的物体时，应首先确定原 来控制顶点框架内任点x 所对应的局部坐标0 ，f ，“) 。一般来 说，此过程应根据原控制顶点和式( 2 2 ) 来解非线性方程组。在 用b e r n s t e i n 多项式来表示变形映射时，若原控制顶点满足式 ( 2 1 ) ，则局部坐标可由式( 2 0 ) 确定。为了讨论非线性方程组 的求解过程，我们假定所用基函数是矢值的三变量b e r n s t e i n 多 项式，即= 所= h = 3 。 方程( 2 2 ) 所提出的非线性方程组，为了方便于分析讨论， 我们可以将其写成向量的表示。令 sl f if ( 功： i “i 彳 左 z 肚阱 333 其中z g ) = p j ，。b 。0 ) 口阳( f ) 坟，( ”) 一x ，即控制框架顶点 j t o ，u ok = o 的x 方向坐标关于b 0 ( s ) ，b j 3 ( f ) 和峨，( z f ) 的6 4 项线性组合 鹅二章自由变形造型( f f d ) 与d f f d 3l， 0 ) = 只- 。口。0 ) b 。0 ) 曰。，0 ) 一y ，即控伟9 框架顶点的y 方向坐标关于b ( j ) ，b 邝( ，) 和玩，( “) 的6 4 项线性组合 333 g ) = 只j ，。3 。0 ) 詹小( f 归0 ) 一z ，即控制框架顶点的z 方向坐标关于b 。( j ) ，b j , 3 ( r ) 和皿、；( ) 的6 4 项线性组合 只j ，。，e ：，。和只j ，。分别表示控制框架顶点的x 坐标值，y 坐标值 和z 坐标值。则原来求解待变形物体上任意点的局部坐标的非线 性方程组( 2 2 ) 则可写成形式：h 曲= 0 。 2 1 4 牛顿法及牛顿变形算法 下面介绍用参考文献 1 6 中牛顿法及牛顿法的变形来求解非 线性方程组：f ( x ) = 0 的过程步骤。 从视觉效果上讲，变形效果的好坏依赖于计算待变形物体上 每一点x 所对应的局部坐标0 ，r ，”) 的计算精确度，而待变形物体 上每一点z 所对应的局部坐标0 ，t ，“) 的求解又依赖于方程组 f ( x ) = o 的求解过程及其收敛性。所以，非线性方程组：f ( z ) = o 解的好坏对变形物体的最终效果起着至关重要的作用。 通过比较分析众多迭代法，我们选择了牛顿法的变形来求解 非线性方程组：f ( x ) = 0 。 具体讲如下： 当f + d c r “叶r ”，求解非线性方 晕组f ( x ) = 0 的牛顿法是 第二章自由变形迸掣( f f d ) ，d f f d 一= i 的牛顿法的推广。当一= ih , 1 ，若x 是方程厂( x ) = 0 晌一个近 似解，i l i t jf ( x ) = 0 在x 的一个线性近似为：缃 够) 谚) e o ) = o 。 用线性近似x 作为厂( x ) = 0 的新近似解x “i ， 则 x = x 一厂g ) 。1 厂b 。l 尼= 0 , 1 ，这就是”= 1 的方程求根牛顿 法。 将它推广到” 1 的方程组：f ( x ) = 0 。设x = & ，一，x ：) d 为方程组：f ( x ) = 0 的一个近似解，将f = u ，：| ) 7 在x 处线 性展开可得： ，。，p ) + 善粤戗一# ) + + 錾粤k 一) ：of ：1 ，2 ，。 啦瓯 它的向量表示形式为：f g ) z f g ) + f b b _ x k ) = 0 。这里 f ) 就是f 在处x 。的雅可比矩阵。求此方程的解记作z “。 当f o ) 非奇异，则得z “= x 一f b ) - 1 f g l ：0 , 1 ，。称为 方程组f ( x ) = 0 的牛顿迭代法。 由x 计算x “的过程是： 步1 解线性方程组f 0 b = 一f ( x ) ( 此方程也称为牛顿 方程) 得到解缸。 步2 x “1 = x + x 。 由此看到牛顿法每步迭代要计算次f 值和一次f 。的值，计算值 第二章自由坐形进型( f f d ) 2jd f f d f 相当于计算”个f 值，工作量较大“ 为了减少牛顿法每步的汁算量可将q + 坝迭代法简化为： x ：x 一fb 。) “f b 。l 女= 0 , 1 ( 2 ，d ) 称为简化牛顿法( 牛顿法的变形) ，它每步只计算一次f 的值， 虽然( 2 。4 ) 的迭代序列只是线性收敛，但其计算结果具有精确度 高，误差很小的特点( 见参考文献 2 2 ， 2 3 ) 。 2 1 5 关于向量形式的牛顿迭代法收敛性的证明 我们用已知下面的定理1 来证明向量形式的牛顿法的收敛性 定理1 假定g ：d c r ”斗r ”在x i n t ( d ) 处可导，x 为g b ) 的 不动点，若p ( c g ) ) = 占 o ) ，使映射g ( r ) = x f ( z ) 。f ( x ) 对所有 z s 有意义，且牛顿法生成的序列 x = x 一f b ) 。f g l = o ，i 超线性收敛于x 。若还存在常 数b 0 ，侧f ( x ) 一f b ) 1 0 x - - x j 协酣 则迭代序列扛譬至少平方收敛。 旺明：因f 。扛+ ) 非奇异，令= 1 f 。b ) “i 0 ，又因f 。g ) 连 瓤一章自由变彤造型( f f d jd f i ? i ) 纠。_ 酬满足o c5c 去舭，j do ，使当xen = 帖，占) c k 、】彳丁扩( 。) 一，b ) lc s ，于是根据摄动引耻， b ) “存在，且 k - ( 寸1 1 1 南c 2 ，巩es 。 因此映射g g ) = 工一f b ) 。f ( x ) 在x s 上有定义，而且 x = c ( x ) 再由上式，可得j i g ( x ) 一g 0 】j = 忙一，g ) “厂b ) - - x j ； = 1 卜f b ) 。p g ) 一f g ) b x ) + 妒g ) 一f o ) ) b x s2 p l l , ? ( x ) 一f g ) 一f g ) b x + 1 i f g ) 一，b 1 1 1 x x 0 。 由于f b ) 存在，由- d 数定义，对充分小的万 0 ，有： 护g ) 一f 0 ) 一f 0 b - - x * 】| f 忙一x l l ，对一切x es 仁。，艿) 成立， 荐由| | f b ) 一f g + i 占，上式可变成 荆一砖i 蔓2 _ 藤+ 占x - - x + 8 =。胁iix-xii或崆垒掣。肛这里。为零矩阵。 根据导数定义，显然有g b ) = o ，所以p ( g g + * = o t ，根据定 凯啡嚯慨l i m 九x 瑚! 晚筒- o o 它表 明扛。努足超线性收敛的。关于平方收敛的结论，此处就不证明了。 在文中，我们采取由左至右，由下列上，r h 前往后的顺序来 构造6 4 个网格控制顶点。将o s ，o t ，o u 轴等分成p q 段；并 第一案白【打变形造型( f f d ) i jd f f d 一06 ，0 6 。如图所示 一：1 2 此处取初始迭代值x 。= ( o 0 , 0 0 ，0 o ) 。( 初始值的可在区间( o ，1 v f - ( x o ) = l 。0 0 ，0 8 。3 3 3 3 | t - 0 8 3 3 3 30 0 控制顶点g 。，其实就是b e r n s t e i n 多项式的系数。与b e z i e l 第二章自由变形造型( f f d ) 与d f f d 当整个物体都位于框架内时，移动一个控制顶点将影响整个 物体的形状，为了使变形局部化，可采用较小的框架。当物体的 一部分位于框架内时，将获得局部变形。 2 1 6 变形实例 1 三维n l i r b s 曲线的变形结果： 2 三维n u r b s 曲面的变形结果 量墓 第：章自由垒形造型( f f d ) 与d ：f d 的变形结果： 通过变形结果我们容易看：_ ；：所调整的控制网格顶点数目与得到 的变形效果密切相关。所以要想得到理想的变形效果必须通过 不断调整不同的控制网格顶点的位置来得到。 2 1 7 f f d 方法连续性控制的充分条件 下面我们来推导关于f f d 方法连续性控制的充分条件。 雷够脑一留 m 一葶自由变形造型( f f d ) 与d f f d 构造较为复杂的形体时，可能需要对物体施加两个甚至更多 的f f d 变形，为了保持跨界导矢的连续性，需要讨论连续性控制 问题。任何曲面都可局部参数化。因此可在曲面岗部参数情况下 讨沦。假设曲面的局部参数为( n w ) ，则曲面可表示为 x ( s ，“) = 片( j ( v ，w ) ，t ( v ，w ) ，“( v ，w ) ) 若两个f f d 变形x l 倒( s ，o “，) 和2 删( s 2 ，f 2 ，“2 ) 具有共同的 边界毛= s ：= 0 ，则变形后曲面沿v 和w 方向的一阶导矢可分别由 下面两个公式来计算。 竺! 型生! 塑：竺里鱼+ 竺里旦；竺丝塑 机a sa va ca v乩a v 竺! 型! ! ：塑：竺坐鱼+ 竺盟鱼+ 竺盟丝 却西却。西舢锄跏 因为宴，i 3 t ，宴，妻，芸，罢都与变形无关，因此，满足一阶 囚刀丽石面蕊，丽，丽郁与父彤尢天凼此，墒足一髟 导矢连续的充分条件为： 硝埘( o ，o “。) 瞄毒。) 衙- - 捌，倒( 0 l ，“) 6 钵 硝2 ( 0 ，2 ，t “2 ) ：竺塑坠：型 ( 2 5 ) = = 一 ，、， 硝：倒( o ，：，“：) 却， 本质上，上式所表示的条件及更高阶的连续性条件是b e z i e r 曲线，曲面的连续性条件的推广。 第一带自由变形造掣( f f d ) 。，d f f d 2 2 直接控制的自由变形造型( d f f d ) d f f d ( d jf e c t m a n i p u 】a t i o n o if r e e f or l n ld e f o r m a t i o n ) 算 法( 参阅参考文献 1 2 ) 仍采用控制框架作为变形工具，应用d f f d 算法时，用户操作的是物体上的点。其思想是：选择物体上的一 点，将该点移至所要求的位置，反算出控制顶点的位置变化，并 计算物体上其它的点所以在实现d f f d 方法时，需要求解矩阵的 广义逆。 2 2 1 最小二乘法与矩阵广义逆( 在参考文献 1 4 ， 2 3 ， 2 4 ) 定义给定线性方程组：y = b x 。广义逆b + 是一矩阵，它使 = b + y 为上述方程组在最小二乘意义下的最优解，即。使 1 】e k v i i 2 取得极小，且1 | 甄| l 最小。其中b 为，舣，2 矩阵。 我们知道方程组y = b x 的最小二乘解x 。满足法方程组： 矿且y = b 7 y 。当b 不是列满秩矩阵时，矩阵曰7 占的秩小于”，即 ，铆女0 7 口) 胆，此时法方程组b r 肼：b r t 的解并不唯一， 但可以证明，其最小范数解是唯一的。我们一般依据下述定理来 计算广义逆曰+ 。 定理假设嚣的秩为k ，b = b 。，b 的秩分解为b = c d , 其中c # j m k 矩阵，d 为k n 矩阵，c 和d 都具有秩k ，则 b = ( d 黟) 1 ( c 7c ) 1 9 。 第一章臼f ；h 变形造型( f f d ) 坶d f f d 实际卜，m a c d u f f e l 就是依据上面式子来定义广义逆的。需 爱注意的是：定理中矩阵口的秩分解不唯，但口的广义逆矩阵 并小依赖于8 的其体分解，可以证明，任意两种分解所得到的j 一 义逆是相同的。公式= j ( d d ) “( c 7 0 “c 7 可用于欠定的和超定 的线性方程组，对于欠定的方程组。若b 的秩与其行数。相等， 则可取c = f ，d = b ，此时只需计算( b b 7 r 。对于超定方程 组，若8 的秩与其列数相等，则取d = ，因此只需计算 0 7 8 ) - 召7 。若艿为单行非零矩阵，则其广义逆为矿2 届。 一般情况下的矩阵分解可采用正交分解方法。 2 2 2 单点约束 d f f d 算法与f f d 方法不同，是根据变形物体上点的位移来计 算控制顶点的变化。这个问题是“欠定的”。也就是说，为达到 所要求的变形，控制顶点位置的变化并不是难一确定的。t e 较直 观的方法是根据物体点的位移平移控制顶点。另一种方法是移动 最近的控制顶点直至达到所要求的变形。最自然的方法则是用最 小二乘法来重新配置控制顶点，由此所得的变形曲面对其它部分 的影响是逐渐变化的因此可以得到所要求的变形，并且具有直 观的物理特性。 假设通过三变量三次曰样条来实现变形操作，则其变形公式 为q ，2 e ，。e e 。 e“，“+。目(s)b，(f)b。(“)。式中q。为物体上00忙oj = z 一“，” 被移动的点列：晶。为控制框架网格点：局仞，岛国，b 。( “) 分 别为二次的b 样条基函数。 第二章自由变形造型( f f d ) 与d f f d 33 山上式q 。= p + ，。尽( 曲玩( f ) e ( 呐可知，变形物体一l 的点是6 4 个控制顶点的线性函数，可以将此方程改写为 q = b p 。式中b 为一个单行矩阵，其元素为b 样条基函数，每 元素对应一个控制顶点。p 是6 4 3 矩阵，其每一行为一个控制 顶点的坐标的三个坐标分量。当q 移至新的位置q 。时，各控制 顶点也要做相应的移动：级。= 口( p + a p ) 或a q = b a p 。 式中a q 是物体点位置的变化，为已知量；a p 是控制顶点位置的 变化，为待求量。为求a p 可以利用b 的广义逆曰+ 。 设已计算得到b 的广义逆口+ ，则由物体点移动所引起控制顶 点变化的改变p 可由下式得到。 p = b + q 的。 ( 2 6 ) 由于广义逆给出了最小二乘解，所以控制顶点的变化是最小 综上所述，单点约束情况的计算过程如下： 1 计算选定点的参数坐标。 2 计算选定点的位移q 及广义逆占+ 。 3 计算控制顶点的变化尸。 4 将新控制顶点代如变形公式，得到变形结果。 2 2 3 多点约束 对于复杂物体，需要移动较多的点才能达到所要求的变形，当 然，可以通过每次移动一个点的方法来达到目的。但计算量较大， 第二章自由变形造型( f f d ) 与d f f d 因为每次移动一个点都需要计算变形物体上所有点的新坐标。比 较理想的方法是将所有需要移动的点都移到相应的位置之后再来 计算对应控制顶点位置的变化。为此，可利用与上节相同的方法。 但由于未知量个数的增加，系数矩阵的行数应与所选择的