（通信与信息系统专业论文）基于形态学的变形方法中关键技术的研究.pdf

华中科技大学硕士学位论文 摘要 一7 i 随着现代社会对计算机和信息技术的广泛应用，人们对数字图像和图形处理的要 ， 求越来越高。而数学形态学作为一种很好的数学工具，己在图像学中取得了重要的地 ， 位，但是由于它本身的些重要问题还没有得到解决，使得它在图形学上的应用受到 了很大的限制，还处于探索阶段。实际上形态算子本质上是矢量运算，形态运算是图 形结构的运算，因此形态算子最终一定会在图形学领域有更大的使用价值。，) 本文首先综述了数学形态学的发展状况和图形变形技术的现状，并由此引出了用 形态学工具解决图形变形问题的途径。 本文接着解决了两个将形态学用于实时三维图形变形的难点。第一个是要提高计 算的效率。本文在分析了前人算法的基础上，提出了广义法矢球模型，将多面体的形 态特征直观地表示在一个球面上，并由此得到了凸多面体形态和的快速算法。实验证 明此算法比现有算法快2 0 0 倍以上非常有利于实时三维图形变换，是一种值得推广 的算法。第二个问题是匹配问题。变形过程都是先在对应物体之间建立映射关系，然 后各个对应部分进行中间插值以实现变形。当目标物体和初始物体非同构时，它们之 间的对应关系会直接影响变形的质量，这就是大部分图形变形方法中都会遇到困难的 匹配问题。本文通过分析形态学提供的另一个数学工具一骨架的优缺点，提出了近似 骨架的概念。并在此基础上提出了一种可行的匹配算法。实验证明，本算法巧妙地使 用近似骨架进行匹配可以得到较好的变形效果。 最后本文通过实验结果得出了形态学用于图形变形是可行的和它相对于其它方法 有一定优势的结论。并在实验中讨论了形态算子和本文提出的图形变形方法在字形合 成、衍生及造型等其它方面的应用。 关键词：形态学，三维图形，广义法矢球，近似骨架，毋魄，形态糯 华中科技大学硕士学位论文 a b s t r a c t i nm o d e ms o c i e t y , c o m p u t e r sa n di n f o r m a t i o nt e c h n o l o g ya r ew i d e l yu s e di ne v e r y f i e l d p e o p l eb e c o m em o r ea n d m o r ed e m a n d i n gi np r o c e s s i n gi m a g ea n df i g u r e s a sa n e x c e l l e n tt o o lo fm a t h ，m o r p h o l o g yh a db e e na ta l li m p o r t a n tp o s i t i o ni np r o c e s s i n gi m a g e b u ta sm a n yi m p o r t a n tp r o b l e m sh a v e n tb e e ns o l v e dp e r f e c t l yy e t ，m o r p h o l o g yh a sv e r y l i m i t e du s a g ei nc o m p u t e rg r a p h i c s t h en a t u r eo fm o r p h o l o g yo p e r a t i o ni sv e c t o ra d d i t i o n a n ds u b t r a c t i o n ，a l lt h e s ec o n t r i b u t et ot h eh i g hp r a c t i c a lv a l u eo fm o r p h o l o g yo p e r a t o r si n g r a p h i c s p r o c e s s i n g t h i sp a p e rs u m m a r i z e st h er e s e a r c ha n dd e v e l o p m e n to fm a t h e m a t i c a lm o r p h o l o g y s a p p l i c a t i o ni ng r a p h i c s a n ds u m m a r i z e st h et e c h n o l o g yo fg r a p h i c sm e t a m o r p h o s i s t h e n l e a dt ot h ep r o b l e mo f u s i n gm o r p h o l o g yi ng r a p h i c sm e t a m o r p h o s i s t h es e c o n dp a r ts o l v e dt w oi m p o r t a n tp r a c t i c a lp r o b l e m si nu s i n gm o r p h o l o g yi nr e a l t i m e3 dg r a p h i c sm e t a m o r p h o s i s t h ef i r s ti st om a k et h ea l g o r i t h mf a s t e r b a s e do nt h e a l g o r i t h ma l r e a d yu s e d , w eb u i l du pt h eg e n e r a ln o r m a lv e c t o rs p h e r e ，a n df i n daf a s t e r a l g o r i t h mf o rm i n k o w s k is u m m a t i o no f c o n v e xo b j e c t e x p e r i m e n t ss h o wt h ea l g o r i t h mi s 2 0 0t i m e sf a s t e rt h a nt r a d i t i o n a la l g o r i t h m t h es e c o n di st om a t c ht h e p a r t so f t h e o b j e c t si n t h em e t a m o r p h o s i s b a s e do nt h ea d v a n t a g e sa n ds h o r t c o m i n g so fs k e l e t o ni nm o r p h o l o g y ， w e d e v e l o p e d t h ea p p r o x i m a t es k e l e t o na n dd ot h em a t c h i n gi nt h em e t a m o r p h o s i su s i n gi t t h et w o a l g o r i t h m sa l eb o t hi m p l e m e n t e d i ne x p e r i m e n t s f i n a l l yw em a d eac o n c l u s i o nt h a tu s i n gm o r p h o l o g yi nt h em e t a m o r p h o s i si sv e r y p r a c t i c a la n dh a ss o m ea d v a n t a g ec o m p a r e dw i t ho t h e rm e t h o d s w ea l s od i s c u s s e ds o m e o t h e r u s a g eo f m o r p h o l o g y s u c ha sf o n d s c o m p o s i t i o na n d f o n d sd e r i v a t i o n k e y w o r d s ：m o r p h o l o g y , 3 dg r a p h i c s ，g e n e r a ln o r m a lv e c t o rs p h e r e ，a p p r o x i m a t e s k e l e t o n ，m a t c h i n g ，m i n k o w s k is u m m a t i o n 华中科技大学硕士学位论文 1 1 引言 1 绪论 虚拟现实、工业模拟、科学计算可视化的发展提出了对处理非刚性物体的运动与 变形的要求。传统的方法处理刚体的运动已非常完善，但对非刚性物体的运动描述则 非常困难，由物理模型来描述非刚体运动又受到模型复杂且不统一的限制。对柔性物体 的变形，s e d e r b e r g 提出了自由变形方法( f f df l e e f o r md e f o r m a t i o n ) 】，其基本原理为 将被变形物体嵌入一个三维参数空间，当参数空间变形时，物体也随之变形，f f d 方 法只能解决物体的同态变形，但不能解决任意两个物体间的形状过渡。 g h o s h 首先把形态学方法用于规则多面体的形态造型方法研究 4 - ”，m o u n t 和 s i l v e r m a n 提出多边形的可形态分解概念【6 】，k a u l 把形态学的方法引入三维物体的变形 ”】，解决从一物体自由变形到另一物体的问题，形态和方法对于解决凸多面体的变形 非常有效，但如果变形的源物体和目标物体为凹多面体或有孔，则此方法会产生病态 结果。 为了解决上述问题，本文对凹多边形进行凸剖分，并建立两个多边形子凸集的映 射关系，根据映射关系对两子凸集进行形态和运算再进行合成，把非刚体运动分解成 非刚体的变形和刚体的旋转。此方法对物体没有任何限制，是一种全局优化的非线性 内插方法。 1 2 形态算子及应用 形态学是1 9 6 4 年g m a t h e r o n 和j s e r r a 创立的。它的主要内容是设计一套变换f 运 算) 、概念和算法，用以描述图像的基本特征【8 】。它建立在积分几何以及随机集论的基 础之上，这是由于积分几何能够得到各种几何参数的间接测量，以及反映图形的体视 性质。而随机集论则是用于描述图像的随机性质。形态学的历史可回溯到1 9 世纪的 e u l e r ，s t e i n e r ，c r o r o n 以及本世纪初的m i n k o w s k i ，先是在法国创立了数学形态学； 此后，l c i t z 等人研究了基于数学形态学的图像处理系统。1 9 8 2 年出版的专著 体现了数学形态学在理论上的趋于完备和应 用的不断深入。1 9 8 6 年c u g i p 出版了数学形态学专刊，数学形态学蓬勃的发展起来。 由于数学形态学算法的并行快速，易于硬件实现而引起人们的酱遗关注。它在图像处 华中科技大学硕士学位论文 理、信号处理、计算机视觉中有广泛的应用前景。例如，现今广告中经常用到的变形 术，把一幅图像变成另一幅，就可以用数学形态学的方法来实现。如今，数学形态学 己成为图像学的一个重要分支。形态学包括形态和、形态差、形态开、形态闭四种运 算，统称为形态算子。后三种运算都可以由形态和得到。形态和的主要特点是能够综 合两个形体的几何特征。因此，它能较好解决图像的变形问题，使一幅图像非常平滑 的转变为另一幅图像。 形态算子应用于形状的描述是目前图形学中研究的热点，l o z a n o p e r e z 为了解决 机器人运动过程中的碰撞问题，首次提出了实现两凸多面体形态差算法【9 】，当两凸多 面体的顶点数均为d ( n ) 时，算法复杂度o ( n 2 l o g e n ) 。s c h w a r t z 为计算两凸多边形的最 小距离，提出了一个实现两凸多边形形态和的算法【1 “。该算法复杂度为0 ( r e + n ) ，其 中m 和7 1 分别为两多边形的顶点数。随后l o z a n o p e r e z 将形态差的概念应用到空间安 排( s p a t i a l p l a n n i n g ) 中】，他提出的二维凸多边形形态差算法的复杂度为d ( 肌+ n ) 。k a u l 和r o s s i g n a c q 提出了实现两多面体形态和的两种算法，种适用于任意多面体，另一 种针对凸多面体，两种算法的复杂度均为o ( n i n 2 ) ，其中n 1 ，n 2 分别为两多面体的顶 点数。1 9 9 0 年g h o s h 用形态运算实现了多边形包含、空间安排等问题，并提出了计算 任意两个二维平面区域形态差的算法【4 1 。将集合理论运用于形态差计算，使得计算复 杂度降低，由于集合理论适用于整个欧氏空间，凸多边形的形态差算法推广至高维任 意物体随之成为可能。1 9 9 3 年，他又在原有算法基础上提出了一个二维多边形、三维 多面体形态和、差在理论上统一的算法【5 1 【坦1 ，通过引入“负形状”，形态和差被归结为 一种运算。由于凸物体可表示为纯“正”或纯“负”的物体，凹物体可表示为正负物体之 和，故算法在凸、凹物体的计算上也得到统一。文中提出了一种新的多边形、多面体 表示方法，这种方法不仅使统一的算法概念更易于理解，而且提高了计算效率。 我们在文献【1 3 】中提出了一种曲线，曲面和多面体的形态和算法统一模型，并具 体实现了任意两个多面体的形态和算法【“】，把多面体形态和算法简化为点和面、边和 边、面和面的形态和运算，由于要检测两个多面体中任意两点、两边、两面之间满足 d h s ( d i f f e r e n th a l f s p a c e ) 关系【l “，算法较复杂。形态学方法广泛应用于扫成曲面造型、 字体合成及非同拓扑结构物体的自动内插，但由于形态和算子的膨胀特性，使得直接 用形态和算子进行图形变换会产生病态结果 1 5 】，解决这个问题的办法是把非凸物体进 行凸分解，产生一系列的子凸体，然后分别对子凸体进行形态操作，再进行合并。因 此，快速的凸多面体形态算法是形态学在图形学中应用的基础。 以下是本文用到的有关形态学的一些基本原理。 錾矗谶蠹潦溘，漱矗菇惑逡 华中科技大学硕士学位论文 定义1 2 1 如果集合x c e 8 的补集是e 。的开集，x 为e 。的闭集称为x 的闭 包，记为又。其中g ( 4 ) 和f ( 4 ) 表示a 的闭包和内部，称满足y ( a ) ；a 的集合是规则 的。 定义1 2 2 一个点集a 的规则性，( 4 ) 由下式定义。 ，( 4 ) 三g ( f ( 4 ) ) 。 下面的讨论都针对规则的实体多面体和多边形进行的。 定义1 2 3 设e ，中的集合x 和结构元素b 为e 3 或其予空间2 ，e 1 中的一个点 集，称集合x 关于结构之集b 的形态和算子定义为如下实体 x o b = 工：b x n x 妒 其中吃= 工一b ：b b 。 性质1 2 1x ( x 0 b ) = l x 0 a 占。 性质1 2 2x 0 ( b u c ) = 弘o b ) u ( x 0 c ) 。 利用性质1 2 2 ，可以把几个物体的形态运算分解成单个物体的形态运算，并可通 过布尔运算把复杂的物体分解成简单物体的形态运算。 性质1 2 3x ( b o c ) = x 0 b ) u ( z o c ) 。 把b 进行分解，b = b l o b ：o 0 b 。，利用性质1 2 3 ，对b ，进行重新排序，提 高形态运算的速度。 定理1 2 1 【h 1 两个多面体的形态和的闭包与坐标系选择无关，与坐标变换无关， 只与前后形状有关。 定理1 2 2 两个实体集合a 和口的形态和边界e ( 彳。口) 是它们各自边界的形态 和边界的子集，即e ( a o b ) c e ( e ( a ) o e ( b ) ) ) 。 定理1 2 ，1 4 1 设任意两个多面体的实体4 ，b ，记e o 动的闭包为i 0 曰) ， 则有x ( 爿0 b ) = x ( e ( a ) o e ( b ) u y ( 4 ) o f ( b ) u v ( b ) o ，( 爿) ) ，式中v 表示顶点集， f 表示面集。 推论1 2 1a b 的面只能是e ( 4 ) 0 e ) ，( 彳) o 三( b ) ，f ( b ) o e ( 爿) 中的某一 个。 定理1 2 3 与推论1 2 1 给出求两个三维多面体形态和的方法，但复杂度较高。 在实际应用中，凸多面体的形态和算法更具广泛性。根据三维物体法矢球的统一 形态算法模型【s 】，任一三维物体都可用唯一的法矢球来表示，则两物体的形态运算转 垡塑鲨叁堡箜塞垒重兰：凸垒亘签丝鎏叁蕉自三叠坌缦感：玺匿签生丝亘避鎏叁燮 华中科技大学硕士学位论文 上的一个点，多面体中的一条边对应由与边相邻的两个面法矢球上的二个点的连线， 即法矢球的一条弧，多面体中的顶点对应法矢球上由顶点相邻的边对应的弧垡所围成 的一个球面片。多面体中除面外，边和顶点的法矢不唯一。因为多面体是凸的，没有 凹点和凹边，则法矢球上任一点只存在唯一法矢。 1 3 物体变形技术现状 1 3 1 物体变形的基本概念 广义上的变形主要包括两种情况。一是给定被变形物体，设计变形参数模型对物 体进行变形，变形的结果仅仅由参数模型所决定。这类方法中最具代表性的是由 s e d e r b e r g 和p a r r y 提出的自由变形f f d ( f r f o r md e f o r m a t i o n ) 概念【l j 。这种变形仅 仅只是被变形物体的一种线形变换，所得的最终结果和初始物体通常仍是同态结构。 这并不适用于非同构物体间的相互变换，从而大大限制了其应用范围。 另一种情况则是给定初始物体和目标物体的具体形状，且两物体可以是任意形状， 研究者所要做的工作是设计两个物体之间的变形过程，将初始物体平滑、自然地过渡 到目标物体【l “。现实中应用的大多是这种情况。如在动画设计中，给出一定数目的关 键帧，通过变形方法内插出中间帧，实现连续动画效果；或是通过从初始物体到目标 物体的变形生成一些新的、融合了两个物体特性的特殊物体等等，诸如此类的应用还 很多。应用的广阔性及技术的复杂性促使许多研究者对变形技术进行了大量的研究， 推进了变形技术的快速发展。 对两个给定的物体而言，从其中一个变形到另一个可以有无穷多个变换序列。但 令人满意的变形序列则应满足以下三个条件：一是变形过程中产生的中间状态应保持 单调平滑的变换；二是中间状态的边界曲面应尽量保持光滑；三是被变形物体和目标 物体所共有的一些特征在变形过程中应该被保留。由以上三点可知，令人满意的变形 序列应该是平滑的；并且在变形过程中应尽量的体现出两个形状的特征，体现出初始 物体特征的渐渐消失和目标物体特征的逐步凸现；且无其他无关特征的出现，即不出 现病态的中间状态。如下图1 3 1 1 所示即为一种效果较好的典型变形过程。 这里所说的物体包括二维图像、多边形、多面体、二维或三维折线、二维或三维 曲线、基于体元表示法的三维物体等。针对于物体的不同表示方法，变形技术也是不 同的。因为物体表示方法的多样性、变形技术的复杂性、变形质量评价的主观性，近 年来不同的研究者提出了各种不同的方法。本节的主要目的就是对这些方法进行分类， 4 f_ 。i 。鬟鬣誊叠漶；勰缸 麓数。 华中科技大学硕士学位论文 并行昕子；：方法的适闫范围，优缺点，分沂变形技术的发展方向。 1 3 2 三维物体变形技术 图1 3 i 1 物体变形的一般过程 由于三维形状在计算机中的应用日益广泛，三维变形效果也具有更强的真实性， 近年来，三维物体变形技术受到了越来越多研究者的重视，并得到了很大的发展。 前面提到的间接变形的方法在三维变形中得到了广泛的应用。对于拓扑结构不一 致的物体，h u g h e s 提出了用三维f o u r i e r 变换的方法 1 ”，先把物体变换到频谱空间对 低频系数进行内插，逐步加入高频系数，从而尽可能地减少由高频分量引入的误差。 再用反变换转换到物体空间，实现物体变形。这种方法的实质就是在变形过程中将物 体的粗轮廓和形状细节分开来进行考虑。h e 则利用小波变换取代傅立叶变换重新研 究了这一问题1 1 8 。这两种方法都是对空间域的采样数据进行处理，变形过程不能进行 人工干预，而且这两种方式都很耗时，对于大小为n3 的物体，计算每个中间插值的复 杂度分别为o ( n 3l o g 月) ”埽口o ( n 3 ) 【”】。 l e r i o s 在b e i e r 和n e e l y 提出的二维图像算法f 】9 】的基础上给出了对三维物体进行变 形的算法【2 ”。先将物体纳入一定的参数空间，对变形物体进行弯曲，然后再对弯曲过 后的物体进行变形，用户人工对点、线、面进行匹配映射。但这种方法参与计算的数 据量较大，时间花费也较长，中间插值形状会出现模糊。 变形方法中的一类算法是形状混合算法，其原理是将被变形物体和目标物体相互 重叠，通过初始物体的渐渐消失和目标物体的逐步凸现来重建一系列的中间状态。但 当两个形状的重合部分不是很多时，中间状态可能出现病态现象，近年来采用 d f i ( d i s t a n c ef i e l di n t e r p o l a t i o n ) 的物体变形方法可以较好地解决这个问题，取得了令人 满意的成果。d f i 是由l e v i n 在1 9 8 6 年首次提出并进行了分析，并将之应用于图像 重建中。d f i 是一种由多个n l 维类似物体剖面形状重建n 维物体模型的集合值内插。 可以实现非同拓扑结构物体之间的变形。 华中科技大学硕士学位论文 h e m l a n ：瞎d f i 方法成功地应用于三维生物医学图像的重建中“。p a y n e 和t o g a p “ 给出了三维生物医学物体的d f v ( d i s t a n c ef i e l d 、- , b l u m e t r i c ) 表示方法。但j 童们的这 种方法不对初始物体和目际物体进行弯曲，也不建立他们之间的对应关系，因此无法 对整个变形过程实施人工干预，可能产生不理想的变形结果。 c o h e n 基于d f i 提出了一种对两个常见三维物体变形的方法。首先对物体进行 体元分解，通过选取匹配控制点来定义弯曲函数以实现面的变形。弯曲函数分解为刚 体部分和弹性部分以减少插值模型的扭曲。刚体变形函数决定了物体的整体形状。控 制了整个变形过程中物体的形状。选取匹配控制点的工作需要人工来完成，这可以说 是该方法的一个不足之处。这种方法提供直观、简单的人工控制。该方法的一个优点 在于不需要在对应的变形物体之间建立匹配对应关系，而且被变形物体和目标物体可 以具有不同的拓扑结构，这就大大提高了该方法的适用性。这种方法最大的优点在于 提供了一种“自然”的变形过程。且变形过程比较平滑自然，可以说是近年来最令人满 意的一种变形方法。 图1 3 2 1 文献1 2 4 1 中给出的三维物体变形效果 形态学的非线性对于处理物体的变形有着极大的优越性。物体变形过程的中间状 态必须具有初始物体和目标物体的几何特征，这样才能满足平滑变换的特点。考虑到 形态和算子具有融合两物体几何特征的性质，用形态和描述物体变形可以得到很好的 效果，并且基于形态学的非同构物体变换较好地描述了自然界中的变形过程，经过不 断执行形态变换算法将一个形态变到另一个形态的过程最接近自然的变形过程，这是 由于形态算子是种全局算子，可以不断地增加和减少点、边、面去逼近另一物体， 通过凸分解可以解决变形过程中的病态问题。而且形态运算具有升维性质，三维实体 易于用二维图形甚至一维线段表示，使得形状描述非常简洁，形态算子是欧氏空间中 蕊、i 滥嚣滔蕊磊鑫；i 。溢照mi 。 华中科技大学硕士学位论文 定义的矢量运算，本身具有几何、拓扑特性，因而比集合算子更适合于描述实体变形 及建模。 国际上g h o s h 首先把形态学方法引入平面多边形的表示，并用于规则多面体的形 态造型方法研究，提出平面凸多边形的快速形态和算法1 2 ”。9 1 年m o u m 和s i l v e m 锄 提出多边形的可形态分解概念【6 】，证明了一个凸多面体可在d ( n 2 ) 的时间内分解为一组 不可再分解物体的形态和。 a n i lk 锄l 把形态学的方法引入三维物体的变形，提出了基于形态和的插值方法。 设初始物体为4 ，目标物体为口，则变形体c ( ，) = ( 1 一r ) a o 坩，r o ，1 。这种方法不 需要在4 和b 之间建立匹配对应关系。a 和b 形态和的边界是爿的边界和b 的边界的 形态和的子集p 】。这部分工作在e u r o g r a p 蝴c s 9 1 会议上获奖，对于解决凸多面体 的变形非常有效。x a u l 和r o s s i 印a c 还进一步将形态和与b e z i e r 公式相结合以产生多 面体的交形过程的中间插值【2 “。对于凸体的变形而言，这一类方法是非常行之有效的， 但对于非凸体的变形而言，这一方法会产生病态结果，中间态并非是预想的结果。原 因是形态和是一种膨胀算子，通常先把凹多面体变成凸多面体再变回成凹多面体，达 不到实用的要求。文献 2 7 2 8 1 中也是利用形态和来实现物体的变形，但仍是只对凸体 有效，对于凹体变形的病态问题仍没有很好解决。因此，对此类方法的改进应着重于 解决凹体变形的病态问题。 文献【2 9 】利用形态算子的强几何性，给出了一种非线性的形态变换的模型，能较 好的解决对于复杂物体利用传统方法建模所具有的控制困难，直观性差，某些情况下 易产生病态结果等缺点，在形态学应用于图形处理方面做了很好的尝试，显示了广阔 的应用前景。故此，利用形态学的理论来研究物体的变形也将是今后一个重要的研究 方向。 上面所介绍的一些方法都是对被变形物体整体上的考虑，而对于一般物体而言， 形状特征是最重要的，所以有相当多的物体变形首先考虑的是物体形状的变形。基于 形状的变形方法所要考虑的仅是物体的边界，故参与变形的数据量比考虑整体要少的 多，这就可以大大提高变形的速度。而其他一些如色彩、纹理等物体特征的变换和形 状也有密切的联系。基于形状的变形方法包括了匹配和插值两部分。由于是以形状表 示物体t 所以这类变形方法是通过计算两个物体拓扑结构的对应关系来实现的。这类 方法首先对两个物体分别建立一个描述物体拓扑结构的点、线、面关系的图表，然后 建立两个图表间的对应关系，采用线形插值或非线形插值实现变形。 最早的与形状有关的方法是在两个不同物体的控制点之间定义一个映射关系，利 华中科技大学硕士学位论文 用内插得到中间物体。对于有相同拓扑结构和同等数目顶点的物体，三维变形就是简 单的顶点之间的内插 ”】。对于顶点数不同的物体，一般通过球形变换或柱形变换先得 到相同的顶点数，再进行内插，得到中间状态。b e t h e l 和u s e l t o n 提出了一种变形方 法 3 l ，仅仅对两个物体的拓扑结构关系进行匹配而没有考虑其几何结构，这样就可能 将在初始物体中相邻的两点映射为目标物体中相距非常远的两点，从而引起变形的失 真，当然，这是变形最初采用的方法，它的意义在于为后人提供了一个研究方向。 k e n t 给出了一种变形方法 3 2 1 3 3 】，每个点都沿着由中心点连出的射线方向移动，通 过融合映射到球面的物体网格实现变形，这类变形方法适用于星形的多面体变形，人 工交互性较好，当顶点数为n 时，寻找中心点的复杂度为d 0 ) 。这一方法为其他作者 提供了一条思路。如文献【3 4 】也是对星形物体的变形进行研究。 p a r e n t 采用递归过程来划分网格，对应顶点之间采用线形插值的变形方法口”，这 类方法适合于球状物体的变形，可以自动划分网格也可人工完成。但由于顶点之间是 线形插值，变形结果不是很平滑。 l - 3 3 结论 本文对物体变形技术的发展做了简单的总结，对具有代表性的算法做了简要的评 价，指出各种算法的适用条件，以及它们各自的优缺点。 基于物体整体的变形技术对复杂的、不同拓扑结构的物体变形具有较好的效果， 但仍然存在着一些限制。如自动变形法由于没有人工干预，不能控制变形过程中的映 射和匹配，得到的结果不是很理想。文献 7 2 6 1 提供了基于加权形态和的变形方法对 于解决凸物体的变形效果很好，但对于凹物体的变形则产生病态的结果。在今后研究 中应主要解决非凸体的变形问题。文献 2 4 】在点和特征元素之间建立映射关系，通过 控制关键点变形来实现整个物体的变形。这类方法取得了目前为止效果最好的变形。 但当被变形物体和目标物体非同拓扑结构时，这类方法就过于繁琐了。 基于形状的变形方法一般都需要人工进行匹配阶段的工作，完全自动的方法不能 产生令人满意的变形效果。在限定被变形物体的形状，并增加一些人工干预的情况下， 某些方法就可以获得令人满意的结果。 在基于形状的变形方法中，形状变形后，纹理、色彩的相应变换直接影响了变形 的最终效果，因此纹理映射也是必须在变形方法中考虑的一个重要问题。 从前面的分析可以看出，一般而言，变形过程都是先在对应物体之间建立映射关 系，然后各个对应部分进行中间插值以实现变形。当目标物体和初始物体非同构时， g 。漱娥嗣瓤o j 建 华中科技大学硕士学位论文 寻找它们之间合适的对应关系直接影响了变形的质量，而插值方法的不同也决定了变 形的平滑性和自然，一般来说，采用非线形插值方法比采用线形插值方法效果要好。 因此匹配映射和插值方法的好坏是提高变形质量的关键。目前为止，大部分的研究者 集中在匹配方法的研究上，采用线形方法完成插值。非线性插值方法的研究应是变形 技术的一个重要的研究方向。 由前一部分的分折来看，无论是采用那种方法对被变形的物体形状仍然有所限制， 实现任意结构物体间的自然变形是研究的热点。 在前面的引言部分我们指出了评价变形质量好坏的三个标准，可以看出，这些标 准是以观察者的主观判断为基础的，并没有任何客观判断的准则和方法。因此在今后 的工作中，如何给出评价变形质量的客观标准也是值得研究的课题。 华中科技大学硕士学位论文 2 1 引言 2 凸多面体形态和的快速算法的研究 形态和计算在物体变形、造型、字型合成、由二维切片重建三维物体等方面都有 很高的使用价值，但由于它的膨胀性，直接用于物体变形会使中间状态失去一些凹的 特征而显得不自然，不能直接用于字型合成及三维重建等，一般处理方法为将原物体 和目标物体剖分成凸子集匹配后分别求形态和，而现有凸多面体算法的效率不能令人 满意，需要在研究现有算法的基础上找到更好的算法【” d 3 e 3 6 1 。k a u l 的算法中，要计算 顶点与面的形态和及边与边之间的形态和，设a 、b 多面体的顶点数分别为n u m 巧、 r l u m ，面数分别为n u m f 、n u m f b ，边数分别为n u m e a 、n u m e a ，则执行形态运算的 次数最少为1 2 ( h u m n * n u m f a ) + l 2 ( n u m 4 n u m f a r ) + l 2 ( n u m e , f + n u m e a ) ，并且计算每次 形态和之前要先判断是否满足l s d ( l i m i t e ds p a c ed i r e c t i o n ) 条件【7 】，由于对多面体的 每一点，每一条边和每一个面要进行l s d 判断，这个过程非常费时，通常计算两个3 0 0 个面的凸多面体的形态和需2 个小时，达不到实用的效果。 在研究k a u l 算法之后，可以得知形态和算法的计算量主要集中在s d 判断上，由 凸多面体的性质，这些判断结果之间有相当大的关联性，而k a u l 的每次判断都是孤立 的，是对每一对点一面或边一边的局部方向进行比较，在文献 3 6 1 中我们通过减少这 种比较的工作量提高效率1 0 一1 4 倍，但仍无法完全利用l s d 判断结果之间的相关性。 本文的算法引入了广义法矢球模型，不再孤立的比较每个表面元素的局部方向，而是 在广义法矢球空间里进行形态和计算，在相关的l s d 判断之间建立起联系，减少了计 算量，不需要处理重叠( 或部分重叠或共一平面) 的面，同时有利于实现并行处理。 2 2 广义法矢球模型的提出 一般意义上法矢的定义是指向图形外，与图形边界垂直的矢量，它的缺点是在二 维图形的顶点、三维图形的顶点和边上没有定义。现在我们把它延拓如下。 定义2 2 1 对于二维图形彳上的一点p ，当且仅当存在以p 为圆心的开圆b 和开 半空间协：( x - p ) b o 的交集与a 不相交时，是a 在p 点的广义法矢。 如图2 2 1 中，是a 在p 点的广义法矢。定义2 2 1 的开圆改为开球即得到三维 1 0 + ；数。；蕊。= ； _ _ j 潍， 华中科技大学硕士学位论文 图形广义法矢的定义， 分冲 a 翻if p v 图2 2 1a 在p 点的广义法矢 定义2 2 2 广义法矢球是三维空间上以原点为球心的单位球。凸多面体a 的面i 的广义法矢在球上的投影为一点，称为法矢点，记为n p ( i ) 。a 的面f 和面，所夹的边 的广义法矢在球上的投影为一条圆弧，称为法矢弧，记为n a ( i ，_ ，) 或i r a ( p ( f ) ，p ( ) ) 。 n a ( i ，) 的圆心在原点，两端为n p ( i ) 、n p o ) 。a 的全部法矢弧的并集称为口的法矢网， 记为n n ( a ) 。口的顶点k 的广义法矢在球壳上的投影为k 所在的边的法矢弧围成的小于 半球的部分球壳，称为法矢面，记为n f ( k ) ，法矢面上有一个赋值，为k 的三维坐标， 称为法矢面赋值，记为v a l ( k ) 。具有上述法矢面的单位球壳称为a 的广义法矢球，记 为n s ( a ) 。 n p ( i ) 周围法矢面的赋值为面f 的所有顶点坐标。 如图2 2 2 中四面体的广义法矢球，四个圆弧的交汇点为法矢点，分别代表四面体 的四个面，六条圆弧为法矢弧，代表四面体的六条边，四个带有赋值的部分球面为法 矢面，代表四面体的四个顶点。由定义2 2 2 可知每个广义法矢球代表的凸多面体是唯 一的。 图2 2 2 一个四面体的广义法矢球模型 定理2 2 1 设a 、b 、c 为三个凸多面体，若法矢网n n ( c ) = n n ( a ) u n n ( b ) ，且对任 意三个顶点f c 口、k e b ，当法矢面j ，( f ) c f ( - ，) 且n 伊( f ) c n f ( k ) 时v a l ( i ) = v a 彤) + v a t ( ，则c = 口o b 。 证明：根据形态和的性质可推出，当且仅当凸多面体a 、b 表面上的点a 、b 具有 相同的广义法矢时，a + b o c ，符号表示c 的边界，且为4 坩的广义法矢。 所以对口、6 任意顶点a 、b ，n f ( a + b ) = h 4 ) n f ( b ) ，由n n ( c ) 兰n n ( a ) w n n ( b ) ，n s ( c ) 的法矢面完全与之相同，赋值亦同为v a t ( a ) + v a t ( b ) 。证毕。 华中科技大学硕士学位论文 图2 2 3 广义法矢球模型表示的凸多面体形态和 定理2 2 1 指出用广义法矢球模型表示凸多面体形态和的方法为将两个凸多面体 的广义法矢球重叠，将相交的法矢面的赋值相加作为新法矢面的赋值。如图2 2 3 ，v 、 v 2 为相交的两法矢面赋值，v l + v 2 为新法矢面赋值。由于此方法不需复杂的l s d 判断， 故算法在时间复杂度上得以提高。 2 3 基于广义法矢球模型的凸多面体形态和快速算法 基于广义法矢球模型的凸多面体形态和快速算法的过程可分为三步如下。 1 ) 将两凸多面体口、b 分别用n s ( a ) 、n s ( b ) 表示。 2 ) 按定理2 2 1 求n s ( c ) ，具体算法中简化为求c 的每个法矢点周围的法矢面赋值。 3 ) 由c 的每个法矢点周围的法矢面赋值，得到c 每个面周围的顶点。 c 即为a 、b 的形态和。其中2 ) 是算法的主要部分。因为将新法矢网完全建立起来 需要将某些原法矢弧分割，将两个分割后的法矢网连接起来，然后将新法矢点周围的 法矢弧排序，实现起来比较困难。而算法的最终目的是为了求c ，只需要知道c 的每 个面的顶点，所以简化为求c 的法矢点及其周围法矢面赋值。c 的法矢点可分为以下 两类。 第一类法矢点是法矢网n n ( a ) 、n n ( b ) 的交点。这一类法矢点又可以分为三型：i 型，a 、b 的法矢点重合形成的新法矢点，如图2 3 1 ( a ) 中法矢点由图7 ( a 1 ) ( a 2 ) 中法矢 点重合形成，虚线和实线分属两个原法矢球；i i 型，( 或6 ) 的法矢点落在6 ( 或口) 的法 矢弧上形成的新法矢点，如图2 3 1 ( b ) ；i 型，口、b 的法矢弧的交点形成的新法矢点， 如图2 3 k c ) 。 第二类法矢点是d ( 或6 ) 的法矢点落在6 ( 或n ) 的法矢面的内部形成的法矢点，如图 2 3 1 ( d ) 中法矢点c 、b 。 1 2 * 融；， ? 溢 辩 华中科技大学硕士学位论文 l v m n 7 ( a 1 ) l e l l e ， ( b ) l 髓 l ( c ) ( d ) 图2 3 1 新法矢点周围法矢面赋值的求法平面圈 第一类法矢点周围法矢面赋值的求法以i 型为例，图2 3 1 ( a 1 ) 中的法矢点周围法 矢面按逆时针排序其赋值分别为，、m 、月，图2 3 1 ( a 2 ) 中的法矢点周围法矢面按逆时 针排序其赋值分别为x 、y 、z ，当这两个法矢点如图2 3 1 ( a ) 形成i 型法矢点时，由它 们的六条法矢弧按逆时针排列的次序可得新法矢点周围的法矢面按逆时针排序其赋值 分别为h 呵、“_ y 、m + y 、m + z 、n + z 、n 乜。图2 3 1 ( b ) ( c ) 中型和型法矢点周围的法 矢面赋值的求法与之类似，只是e 1 、e 2 、e 3 这三条法矢弧在新法矢点周围排序时要 分成两段来考虑。 第二类法矢点周围法矢面赋值的求法以图2 3 i ( d ) 中b 、c 为例。法矢弧e 的数据 结构中存有两边法矢面赋值，求4 周围法矢面赋值时，取出实线三角形的法矢面赋值 f 若a 、b 之间没有法矢网交点，则占落在这个实线三角形的法矢面内，它周围的法 矢面赋值为原来虚线法矢面赋值分别加上f 。此过程称之为由4 把法矢面赋值传递给b 。 传递后，存于曰所在原法矢点中，用于向相邻的第二类法矢点所在的原法矢点传递。 c 不与第一类法矢点相连，但与口相连，所以可由b 把，传递给c 。由凸多面体法矢 网的连通性，这种方法可以处理所有第二类法矢点。 2 4 基于广义法矢球的凸多面体形态和快速算法的实现 由2 3 节，在原法矢网中寻找第一类法矢点，求其周围原法矢弧的排序以及传递 第二类法矢点所需的法矢面赋值为算法的具体工作。为了防止计算误差造成新法矢面 的局部结构之间产生矛盾和减少重复的计算。应归纳出一个统一标准，尽量使上述工 作借由这个标准就可以完成。这个标准就是面边关系。在得到面边关系之前，先给出 华中科技大学硕士学位论文 法矢弧矢量的定义。由法矢弧定义知法矢弧所在的平面与形成它的边垂直。 法矢弧n a ( i ，) 的矢量定义为a d ( i ，) ，其方向与形成n a ( i ，j ) 的边平行。与法矢 点i 、j 满足右手规则，大小为1 。 图2 4 1 面边关系 定义2 4 2 当法矢点a 和a d ( i ，) 的点积为0 时这个a 和n a ( i ，- ，) 面边关系为o n ， 大于0 时为l e f t ，小于0 时为r i g h t ，记为f e ，i ，) 。 以下介绍面边关系的几何含义和由它完成以上工作的方法。 如图2 4 1 ，以i 为下，上，与n a ( i ，力面边关系为e f ，的法矢点a 在n a ( i ，) 所在的平面左边，为r i g h t 的法矢点d 在右边，为o n 的法矢点占、c 在平面上 为叙述方便，将算法使用的c 语言数据结构列下： t y p e d e f s t r u c t v e c te r e c t ；本法矢弧表示的边矢量 i n tl f a c e ；，( 以v e c t 2 在上方) 左法矢点号 i n t ，f a e e ；( 以v e c t 2 在上方) 右法矢点号 i n tv e c t l ；本法矢弧表示的边的起点的法矢面号 i n tv e c t 2 ：本法矢弧表示的边的终点的法矢面号 ) e d g e ；法矢弧 t y p e d e fs t r u c t b o o ld i r ：法矢点为本法矢弧f a c e 时为l ，否则为0 i n tn u t ? ；法矢弧号 e d g e l i s t ；一个法矢点的法矢弧表的元素 t y p e d e fs t r u c t v e c tn o r m ：法矢点矢量 b o o l f l a g ：当本法矢点落在对方法矢面内部时或未判断时0 ，否则为1 ， i n t 埘m ；本法矢点的法矢弧个数 1 4 蓉囊巍蕊盏溢氟燕浮。 华中科技大学硕士学位论文 c dr , e l i s t * i z e a d ：本法z 点的，圭矢甄袁 以f 受量为传递法矢面重替睛扼而设 b o o l n e a r v 赋过值后为1 ，否则为0 b o o l 班需要比较法矢弧交点确定n e a r v 时为1 否列为0 i n t