（计算数学专业论文）平面多边形变形技术的研究.pdf

两北丁 _ 业大学硕 卜 学位论文 摘要 物体变形 ( m o r p h i n g ) ， 又称物4 本 渐变 ( m e t a m o r p h o s i s ) ， 是指将一给定的 初 始物体 ( 这里的物体包括数字图像、多边形、自由曲线曲面、网格、多面体等) 在视觉上光滑、 连续、自 然的变化 到月 标 物体。 随着计算机技术的 迅速发展， 物 体变形技术广泛应用于计算 机图形学、 工业产品 设计、计算机动画、虚拟现实、 影视特技制作等领域。 平面多边形变形是 物体变形的重要组成部分， 不仅在关键 帧动画、模式识别， 而且在曲面重建和三维造型中 也有重要意义。 本 文 简 要 介 绍了 平 面多 边形 变 形技 术 的 历 史 及 研 究 现 状， 指 出 该 领 域内 各 种 方法的 特点、 不 足及遗留问题。 变形过程中如何避免多边形 边界自 交现象及如何 较好地保持多 边形内在几何属性的 均匀变 化是两 个较难且有意义的问题。 这些问 题前人已有一些研究成果， 但仍需进一步改进。本文给出了一种可降低算法复杂 度、 避免多 边形 边界自 交、 又 能较好地保持几何属性变化较均匀的 变形方法， 取 得了令人满意的变形效果。该方法首先利用最小二乘原理求得一仿射变换， 使得 初始多边形形状经此变换与目 标多 边形形状在整体上尽可能接 近， 以实 现刚性变 形、 保持多边形几何 属性较均匀变化， 然后将初始多边形和目 标多边形分别嵌入 到同构的三角网格中去， 并用 m e a n v a l u e 重心坐标表示， 通过三角网格的变形来 实现初始多边形到 目标多边形的变形过程。 本文还提出一种通过插值初始多边形和目 标多边形对应边向量及其旋转变 换矩阵的多边形变形的向量方法。 该算法简单直观， 计算量较小， 运行速度较快， 能够实时 一 实现。 文中给出的计算实例表明本文算法有效易行，变形效果较流畅、自 然。 关键词变形多 边形变形同 构三角网格 m e a n v a l u e 重心坐标 p l e a : 分解 边向量插值 两北下业大学硕 1 学位论文 ab s t r a c t mo r p h i n g , a l s o k n o w s a s m e t a m o r p h o s i s , i s t h e c o n t i n u o u s , s mo o t h a n d n a t u r a l t r a n s f o r m a t i o n o f a s o u r c e o b j e c t i n t o a t a r g e t o b j e c t , w h e r e t h e o b j e c t c a n b e d i g i t a l i m a g e s , p o l y g o n s , f r e e f o r m c u r v e s a n d s u r f a c e s , m e s h e s , p o l y h e d r o n s e t c . a l o n g w i t h t h e s p e e d y d e v e l o p m e n t o f c o m p u t e r t e c h n o l o g y , m o r p h i n g i s b e c o m in g p o p u l a r i n m a n y a r e a s , s u c h a s c o m p u t e r g r a p h i c s , i n d u s t r ia l d e s i g n , c o m p u t e r a n i m a t io n , v i rt u a l r e a l i t y a n d f i l m s t u n t . s h a p e m o r p h i n g o f p l a n a r p o l y g o n , t h a t i s s h a p e b l e n d i n g , i s a l s o a t t r a c t i v e , w h i c h h a s g r e a t s i g n i fi c a n c e i n k e y f r a m e a n i m a t i o n , p a t t e r n r e c o g n i t i o n , s u r f a c e r e c o n s t r u c t i o n a n d t h r e e - d i m e n s i o n a l m o d e l in g . i n t h i s t h e s i s , w e i n t r o d u c e t h e h i s t o r y a n d t h e c u r r e n t d e v e l o p m e n t i n t h e a r e a o f p l a n a r p o ly g o n m o r p h i n g c o n c i s e l y , a l s o p o i n t o u t r e s p e c t i v e l y t h e c h a r a c t e r i s t i c s a n d i t s i n s u f f i c i e n c i e s o f t h e m a i n m e t h o d s i n t h i s r e s e a r c h a r e a a s w e ll a s i t s o p e n q u e s t i o n s . i n t h e m o r p h i n g p r o c e s s , h o w t o a v o i d e d g e s e l f - i n t e r s e c t i o n a n d p r e s e r v e t h e g e o m e t r i c a l p r o p e rt i e s o f t h e i n t e r m e d i a t e s h a p e s a r e t w o c h a l l e n g e s . s e v e r a l f r u i t s o n t h e s e p r o b l e ms a r e g a i n e d b y t h e f o r m e r r e s e a r c h e r s , b u t t h e s e s e e m s i n s u f f i c i e n t . w e p r o p o s e a n e f f i c i e n t a p p r o a c h w h i c h h a s l o w c o m p u t a t i o n a l c o m p le x i ty , a n d i s e d g e s e l f - i n t e r s e c t i o n - f r e e a n d c a n p r e s e r v e s t h e g e o m e t r y b e t t e r i n m o r p h i n g p r o c e s s . i n t h i s m e t h o d p r e s e n t e d i n t h i s p a p e r , w e f i r s t d e t e r m i n e a n a f f i n e t r a n s f o r m a s r i g i d t r a n s f o rma t i o n b y l e a s t s q u a r e p r i n c i p le s o t h a t t h e r e s u l t i n g p o l y g o n p o s s i b l e a f t e r t h e t r a n s f o r m a t i o n b e i n g a p p l i e d o n t h e s o u r c e p o l y g o n i s a s c l o s e a s t o t h e t a r g e t i n t e r m e d i a t e p o l y g o n p o l y g o n i n t h e w h o l e , w h i c h p r e s e r v e s t h e g e o m e t r y o f t h e m o r p h i n g m o r e u n i f o r m l y . t h e n w e e m b e d t h e s o u r c e p o l y g o n a n d t a r g e t p o l y g o n i n t o c o m p a t i b l e p l a n a r t r i a n g u l a t i o n a n d e x p r e s s t h e i r v e r t i c e s b y m e a n v a l u e c o o r d i n a t o r s r e s p e c t i v e l y , s o t h e s h a p e b le n d i n g i n d e t a i l p a rt i s p e r f o r m e d 西北丁业大学硕 卜 学位论又 b y m o r p h i n g t h e c o r r e s p o n d i n g c o m p a t i b l e t r i a n g u l a t i o n s . i n t h i s p a p e r , b a s e d o n t h e e d g e v e c t o r r e p r e s e n t a t i o n s o f p l a n a r p o l y g o n , w e a l s o p r e s e n t a n e w me t h o d f o r p o l y g o n mo r p h i n g b y i n t e r p o l a t i n g t h e c o r r e s p o n d i n g e d g e v e c t o r s a n d t h e i r r o t a t i o n m a t r i x e s o f t h e i n i t i a l p o l y g o n a n d t h e t a r g e t p o l y g o n . t h i s a l g o r i t h m i s s i m p l e a n d h a s l o w c o m p u t i n g c o mp l e x i t y , a n d r u n s f a s t t h a t c a n b e d o n e i n t i me s e v e r a l e x a m p l e s s h o w o u r a l g o r i t h m s a r e v a l i d a n d f e a s i b l e , a n d n a t u r a l mo r p h i n g e ff e c t s a r e p e r f o r m e d . k e y w o r d s m o r p h i n g p o l y g o n m o r p h i n g c o m p a t i b l e t r i a n g u l a t i o n m e a n v a lu e c o o r d i n a t o r p o l a r d e c o m p o s i t i o n e d g e v e c t o r i n t e r p o l a t i o n j i 2 西北丁业人学硕 卜 学位论文 第一章绪论 1 . 1 引 言 物体变形 ( m o r p h i n g ) ，又称物体渐变 ( m e t a m o r p h o s i s ) ,形状融合 ( s h a p e b l e n d i n g ) 等， 是指将一给定的刃 始物体 ( 这里的 物体包括数字图 像、 多边形、 自 山曲 线曲 面、网 格、 多面体等)在视觉上光滑、连续、自 然的 变化到目 标物体。 近年来，随着计算机技术和信息技术的 迅速发展， 物体变形技术已 广泛应用于几 何 造型、工业产品设计和计算机动画 系统中。 此外，它又是虚拟现实、 科学计算 可视化、影视娱乐及广告等领域的 一种常用技术手段。在关键帧动画 设计中， 通 过变形技术可以插值出中间帧，减少动画师的手工劳动，实现连续动画效果;在 影视娱乐领域，物体变形技术可以 产生令人惊叹的 特技效 果;应用于几何造型与 工业产品设计，既可以把不同造型特征相互交融，生成融合不同造型特征的新产 品，又可作为预测产品潮流走向的一种手段。随着物体变形技术的不断发展，它 又被应用于字体生成、肌肉运动描述等诸多领域。 显而易见， 对两个给定物体而台 ，从 初始物体到目 标物体的 变形可以 有很多 种途径。 正是由于物体变形技术的多 样性和复杂性， 以 及应用目 的的不同、到目 前为 止， 关于物体变形 技术的好坏还没有一个客 观统一的 标准。 一般认为， 一 个较好的 令人满意的物体变形应满足以下三个条件: 令变形过程中产生的中间状态应保持单调平滑; .中间状态的边界曲线曲面应尽量保持光滑; 令初始物体和目标物体所共有的一些特征在变形过程中应该被保留。 由此可知，物体在变形过程中应尽量体现出初始物体特征的逐渐消失和目标 物体特征的逐步凸现 ， 且不能有其他无关特征的出现， 即不出现病态的中倒状态。 物体变形方法 与物休的表示方法密切相关，如图像、多边形、三维体少 u 、多 西北丁业人学硕 卜 学位论文 第一章绪论 1 . 1 引 言 物体变形 ( m o r p h i n g ) ，又称物体渐变 ( m e t a m o r p h o s i s ) ,形状融合 ( s h a p e b l e n d i n g ) 等， 是指将一给定的刃 始物体 ( 这里的 物体包括数字图 像、 多边形、 自 山曲 线曲 面、网 格、 多面体等)在视觉上光滑、连续、自 然的 变化到目 标物体。 近年来，随着计算机技术和信息技术的 迅速发展， 物体变形技术已 广泛应用于几 何 造型、工业产品设计和计算机动画 系统中。 此外，它又是虚拟现实、 科学计算 可视化、影视娱乐及广告等领域的 一种常用技术手段。在关键帧动画 设计中， 通 过变形技术可以插值出中间帧，减少动画师的手工劳动，实现连续动画效果;在 影视娱乐领域，物体变形技术可以 产生令人惊叹的 特技效 果;应用于几何造型与 工业产品设计，既可以把不同造型特征相互交融，生成融合不同造型特征的新产 品，又可作为预测产品潮流走向的一种手段。随着物体变形技术的不断发展，它 又被应用于字体生成、肌肉运动描述等诸多领域。 显而易见， 对两个给定物体而台 ，从 初始物体到目 标物体的 变形可以 有很多 种途径。 正是由于物体变形技术的多 样性和复杂性， 以 及应用目 的的不同、到目 前为 止， 关于物体变形 技术的好坏还没有一个客 观统一的 标准。 一般认为， 一 个较好的 令人满意的物体变形应满足以下三个条件: 令变形过程中产生的中间状态应保持单调平滑; .中间状态的边界曲线曲面应尽量保持光滑; 令初始物体和目标物体所共有的一些特征在变形过程中应该被保留。 由此可知，物体在变形过程中应尽量体现出初始物体特征的逐渐消失和目标 物体特征的逐步凸现 ， 且不能有其他无关特征的出现， 即不出现病态的中倒状态。 物体变形方法 与物休的表示方法密切相关，如图像、多边形、三维体少 u 、多 西 北 下 业 人学 硕 卜 学位 论 文 面体等变形方法各不相同。 但无论那种物体的变形都必须考虑这样两个主要问题， 即 对应问 题 ( c o r r e s p o n d e n c e p r o b l e m) 和插值路径问 题 ( i n t e r p o l a t i o n p r o b le m ) . 对应问题，就是对初始物体和目标物体的顶点、体元等特征属性建立对应关系。 一般此过 程需要人工参与，对应关系选择的 适当与否对变形效果有着 至关重要的 影响。 插值路径问题即 如何使初始物体各部分 ( 包括顶点、 边、 面、 体元等) 按 对应关系随时间自然变换到目标物体对应各部分。插值路径的选择影响着变形过 程的平滑性和自 然性， 若选择不当， 可能 会使中间 物体产生边界自 交或萎缩等不 自然现象。 1 . 2 二维物体变形 二维物体的变形比较简单、直观，算法实现比较容易，而且速度快，在计算 机动画、模式识别、曲面重建和三维造型中得到广一 泛应用，具有重要意义。因此 国内外许多专家和学者对此作了大量 研究。 二维 物体变形主要包括二维图像变形、 平面多边形的变形以及自由曲线曲面的变形。 1 . 2 . 1 二维图像变形 图 像变形，又称图像的自 交融合 ( c r o s s - d i s s o l v i n g ) ， 是指把一幅源数字图像 以 一种自 然流畅的方式变 换到目 标数字图像。由 于二维图 像能 使人产生 三维图形 的感觉， 因此， 图像变形也是一种非常有用的技术， 广泛应用于影视特技、 教育、 娱乐与计算机动画中，具有特殊的 视觉效果。 早期的图像变形算法中 较好的一种 是1 9 9 2 年b e ie : 和n e e l y p 提出 的 基 于 特征 线 对的 变 形 方 法， 这 种 方 法 先由 用 户 在源图像和目标图像中定义 一系列特征直线对，对 一 于目标图像中的每个1氛 ，根据 它与各 特征线的关系求得源图像中的一系列对 应点， 然后将这些对 应点进 行加权 平均求得目 标点在源图 像中的最终对应位w。 该方法允许用户用 线对变形 进行直 观的控制， 通过交互地指定图像的特征，可以 方便地达到预期的视 觉效果。1 9 9 8 年 ， w o lb e r g (2 1发表 了 一 篇 关 于图 像 变形 研究 现 状的 文 章， 介 绍了 各 种图 像 变 形的 方法及其特点、不足等。随着国内外专家和学者的关注，关于图像变形不断涌现 西 北 下 业 人学 硕 卜 学位 论 文 面体等变形方法各不相同。 但无论那种物体的变形都必须考虑这样两个主要问题， 即 对应问 题 ( c o r r e s p o n d e n c e p r o b l e m) 和插值路径问 题 ( i n t e r p o l a t i o n p r o b le m ) . 对应问题，就是对初始物体和目标物体的顶点、体元等特征属性建立对应关系。 一般此过 程需要人工参与，对应关系选择的 适当与否对变形效果有着 至关重要的 影响。 插值路径问题即 如何使初始物体各部分 ( 包括顶点、 边、 面、 体元等) 按 对应关系随时间自然变换到目标物体对应各部分。插值路径的选择影响着变形过 程的平滑性和自 然性， 若选择不当， 可能 会使中间 物体产生边界自 交或萎缩等不 自然现象。 1 . 2 二维物体变形 二维物体的变形比较简单、直观，算法实现比较容易，而且速度快，在计算 机动画、模式识别、曲面重建和三维造型中得到广一 泛应用，具有重要意义。因此 国内外许多专家和学者对此作了大量 研究。 二维 物体变形主要包括二维图像变形、 平面多边形的变形以及自由曲线曲面的变形。 1 . 2 . 1 二维图像变形 图 像变形，又称图像的自 交融合 ( c r o s s - d i s s o l v i n g ) ， 是指把一幅源数字图像 以 一种自 然流畅的方式变 换到目 标数字图像。由 于二维图 像能 使人产生 三维图形 的感觉， 因此， 图像变形也是一种非常有用的技术， 广泛应用于影视特技、 教育、 娱乐与计算机动画中，具有特殊的 视觉效果。 早期的图像变形算法中 较好的一种 是1 9 9 2 年b e ie : 和n e e l y p 提出 的 基 于 特征 线 对的 变 形 方 法， 这 种 方 法 先由 用 户 在源图像和目标图像中定义 一系列特征直线对，对 一 于目标图像中的每个1氛 ，根据 它与各 特征线的关系求得源图像中的一系列对 应点， 然后将这些对 应点进 行加权 平均求得目 标点在源图 像中的最终对应位w。 该方法允许用户用 线对变形 进行直 观的控制， 通过交互地指定图像的特征，可以 方便地达到预期的视 觉效果。1 9 9 8 年 ， w o lb e r g (2 1发表 了 一 篇 关 于图 像 变形 研究 现 状的 文 章， 介 绍了 各 种图 像 变 形的 方法及其特点、不足等。随着国内外专家和学者的关注，关于图像变形不断涌现 西 北 下 业 人学 硕 卜 学位 论 文 面体等变形方法各不相同。 但无论那种物体的变形都必须考虑这样两个主要问题， 即 对应问 题 ( c o r r e s p o n d e n c e p r o b l e m) 和插值路径问 题 ( i n t e r p o l a t i o n p r o b le m ) . 对应问题，就是对初始物体和目标物体的顶点、体元等特征属性建立对应关系。 一般此过 程需要人工参与，对应关系选择的 适当与否对变形效果有着 至关重要的 影响。 插值路径问题即 如何使初始物体各部分 ( 包括顶点、 边、 面、 体元等) 按 对应关系随时间自然变换到目标物体对应各部分。插值路径的选择影响着变形过 程的平滑性和自 然性， 若选择不当， 可能 会使中间 物体产生边界自 交或萎缩等不 自然现象。 1 . 2 二维物体变形 二维物体的变形比较简单、直观，算法实现比较容易，而且速度快，在计算 机动画、模式识别、曲面重建和三维造型中得到广一 泛应用，具有重要意义。因此 国内外许多专家和学者对此作了大量 研究。 二维 物体变形主要包括二维图像变形、 平面多边形的变形以及自由曲线曲面的变形。 1 . 2 . 1 二维图像变形 图 像变形，又称图像的自 交融合 ( c r o s s - d i s s o l v i n g ) ， 是指把一幅源数字图像 以 一种自 然流畅的方式变 换到目 标数字图像。由 于二维图 像能 使人产生 三维图形 的感觉， 因此， 图像变形也是一种非常有用的技术， 广泛应用于影视特技、 教育、 娱乐与计算机动画中，具有特殊的 视觉效果。 早期的图像变形算法中 较好的一种 是1 9 9 2 年b e ie : 和n e e l y p 提出 的 基 于 特征 线 对的 变 形 方 法， 这 种 方 法 先由 用 户 在源图像和目标图像中定义 一系列特征直线对，对 一 于目标图像中的每个1氛 ，根据 它与各 特征线的关系求得源图像中的一系列对 应点， 然后将这些对 应点进 行加权 平均求得目 标点在源图 像中的最终对应位w。 该方法允许用户用 线对变形 进行直 观的控制， 通过交互地指定图像的特征，可以 方便地达到预期的视 觉效果。1 9 9 8 年 ， w o lb e r g (2 1发表 了 一 篇 关 于图 像 变形 研究 现 状的 文 章， 介 绍了 各 种图 像 变 形的 方法及其特点、不足等。随着国内外专家和学者的关注，关于图像变形不断涌现 西北不业大学硕 f : 学位论文 出新的 研究成果，如h a o l l , z h u l 0 l , z h u 5 1 等。 1 . 2 . 2 平面多边形变形 由于一般的平面物体都可以用其边界线来描述其形状，因此用平面多边形逼 近 物 体 边界 线 就 可 将二 维 物 体的 变 形 简化 为 平面 多 边形 的 变 形 来处 理 。 s e d e r b e r g 和g r e e n w o o d l6 l 于 1 9 9 2 年 提出 了 一 种基 于 能 量的 顶点 映 射 变 形方 法 ，该 方 法 将 初始多 边形和目 标多 边形视为一段金属丝， 建立一种物理模型，通过使初始多边 形经弯曲和伸缩变形到目标多边形所需的能量最小建立顶点对应关系，再线性插 值对应顶点实现变形。该方法对相似形状变形效果较好， 但当两个多边形形 状有 较 大 差 异 时， 会 出 现中 间 图 形 的 扭曲 与 萎 缩 。 1 9 9 3 年， s e d e r b e r g 等 人 7l利用 乌 龟 几何定义平面多 边形的 几何内 在量，即多边形的边长和相邻边i旬 的有向 转角。 通 过插值初始多边形和目 标多边形的内 在量构 造出中间多边形， 从而实 现变形。 采 用几何内在量的变形算法直观简单，计算速度快，且能在一定程度上避免萎缩和 扭结现象， 但当初始多 边形和目 标多 边形包 含较多短边时中间多边形形状可能会 发 生 较 严重 的 畸 变。 1 9 9 5 年 ， g o ld s te in 和g o ts m a n 8 利 用 图 形 的多 分 辨率 表 示 来 对两个简单多边形变形，该方 一 法对两个重合部分较多的多边形具有较好的 变形效 果， 但 不 能 避 免多 边 形 的 边界自 交 现 象。 s h a p ir a 和r a p p o p o r th l 提出 一 种星 形连 通骨架方法，又称极坐标方法，利用连通骨架控制多 边形的边界来实现变形。该 方法由于同时考虑了多边形的边界和内部，一定程度上减少了中间多边形边界自 交的可能性， 变形效果较好， 且能用于图像变形和多个多 边形变形的情况。1 9 9 6 年 ， z h a n g l1 0 1 等 提出 了一 种 基 于 模 糊数 学 的 平面 多 边 形 变 形 方 法。 该 方 法 首 先从 模糊数学的角度定 义一个相似函数， 通过使初始多 边形到目 标多 边形的相似度达 到最大建立二者间的对应关系， 然后又用模糊数学的方法对顶点 插值。该方法能 处 理具有不同位置、 方向、 大小或形 状的多 边形， 易于 推广到曲线形状。 1 9 9 7 年， c o h e n -o ; 和c a n n e l l 1提出 了 一 种 基于d f i( d is ta n c e f ie ld in te rp o la ti o n ) 的 插 值 方 法，该方法首先由用户选择 一 系列锚点定义一个弯曲函数，使得初始多边形与口 西北不业大学硕 f : 学位论文 出新的 研究成果，如h a o l l , z h u l 0 l , z h u 5 1 等。 1 . 2 . 2 平面多边形变形 由于一般的平面物体都可以用其边界线来描述其形状，因此用平面多边形逼 近 物 体 边界 线 就 可 将二 维 物 体的 变 形 简化 为 平面 多 边形 的 变 形 来处 理 。 s e d e r b e r g 和g r e e n w o o d l6 l 于 1 9 9 2 年 提出 了 一 种基 于 能 量的 顶点 映 射 变 形方 法 ，该 方 法 将 初始多 边形和目 标多 边形视为一段金属丝， 建立一种物理模型，通过使初始多边 形经弯曲和伸缩变形到目标多边形所需的能量最小建立顶点对应关系，再线性插 值对应顶点实现变形。该方法对相似形状变形效果较好， 但当两个多边形形 状有 较 大 差 异 时， 会 出 现中 间 图 形 的 扭曲 与 萎 缩 。 1 9 9 3 年， s e d e r b e r g 等 人 7l利用 乌 龟 几何定义平面多 边形的 几何内 在量，即多边形的边长和相邻边i旬 的有向 转角。 通 过插值初始多边形和目 标多边形的内 在量构 造出中间多边形， 从而实 现变形。 采 用几何内在量的变形算法直观简单，计算速度快，且能在一定程度上避免萎缩和 扭结现象， 但当初始多 边形和目 标多 边形包 含较多短边时中间多边形形状可能会 发 生 较 严重 的 畸 变。 1 9 9 5 年 ， g o ld s te in 和g o ts m a n 8 利 用 图 形 的多 分 辨率 表 示 来 对两个简单多边形变形，该方 一 法对两个重合部分较多的多边形具有较好的 变形效 果， 但 不 能 避 免多 边 形 的 边界自 交 现 象。 s h a p ir a 和r a p p o p o r th l 提出 一 种星 形连 通骨架方法，又称极坐标方法，利用连通骨架控制多 边形的边界来实现变形。该 方法由于同时考虑了多边形的边界和内部，一定程度上减少了中间多边形边界自 交的可能性， 变形效果较好， 且能用于图像变形和多个多 边形变形的情况。1 9 9 6 年 ， z h a n g l1 0 1 等 提出 了一 种 基 于 模 糊数 学 的 平面 多 边 形 变 形 方 法。 该 方 法 首 先从 模糊数学的角度定 义一个相似函数， 通过使初始多 边形到目 标多 边形的相似度达 到最大建立二者间的对应关系， 然后又用模糊数学的方法对顶点 插值。该方法能 处 理具有不同位置、 方向、 大小或形 状的多 边形， 易于 推广到曲线形状。 1 9 9 7 年， c o h e n -o ; 和c a n n e l l 1提出 了 一 种 基于d f i( d is ta n c e f ie ld in te rp o la ti o n ) 的 插 值 方 法，该方法首先由用户选择 一 系列锚点定义一个弯曲函数，使得初始多边形与口 西北 工 业 大学 硕卜 学 位 论 义 标多边形在几何形状上达到尽量对齐的目的，然后用曲线演化的方法建立项点对 应关系。再通过弯曲函数的刚性变换和弹性变换实现对应顶点的插值问 题。 该方 法 变形 效 果良 好 ， 但 仍 不能 避 免 中 间 多 边 形 的 边 界自 交 现 象。 2 0 0 0 年， z h a n g 和 h u a n g l 1 利 用 小 波分 解 和 小波 重构 重 新 研 究了 基 于 几何内 在 量的 平 面 多 边 形 的 变 形算法上 述各种方法山于较少考虑多边形形状的内部，因此容易发生内部面积 的扭曲变化，以及中间多边形的边界自 交现象。 2 0 0 0 年， a le x a 等 人 !13 在 s ig g r a p h 会议 上 提出 了 同 时 考 虑 多 边 形内 部 的 变 形 方法， 并使得变形过程中尽量保持刚性变换。该方法首先 对初始多边形和目 标多 边形的内部作同构的三角剖分，在对应三角形间建立仿射变换，并将仿射变换分 解为 旋转变换和伸缩变换分别线性插值，然后用最小二乘原理求得实际期望的仿 射变换，并由 此确定中间多 边形。该方 法可 使得多边形在变形过程中 达到局部形 状扭曲 最小的效果，且不易产生边界自 交， 但总体形状扭曲 效果未必是最佳的。 2 0 0 1 年 ， s u r a z h s k y 和 g o ts m a n 14 1给出 了 一 种 可 避 免 边 界自 交的 平 面 多 边 形 的 变 形 方法，使平面多边形的变形技术取得了突破性的进展。不同于以往直接致力于多 边形 本 身变 形的 方 法研 究， s u r a z h s k y 和 g o ts m a n 基于1 9 9 9 年f lo a te r 和 g o ts m a n 1 51 提出的具有共同凸边界的平面三角网格的凸组合变形算法，定义平面三角网格内 顶点的m e a n v a l u e 重心坐标，并将其应用于平面多边形的 变形。该方法首先将初 始多边形和目 标多边形分 别嵌入凸边界相同的平面同构三角网格中去， 并 用m e a n v a l u e 重心坐标表示出三角网 格的内 顶点，通过插值得到中间网格内顶点的 m e a n v a l u e 重心坐标表示， 再求 解一个线性方程组得到中间网格的内 顶点坐标， 在计算 机上显示时去除不属于中间多边形的边和顶点，即得多边形的变形过程。由于在 变形过程中，中间网 格始终与 初始网 格及目 标网 格同 构，故中间多边形不 会出现 边界自 交现象。但该方法需要对初始多边形和目 标多 边形做同构的三角剖分，使 用了 较 多的 额 外点， 故算 法较 复杂 ， 且 难以 保证 刚体 变 形。 2 0 0 3 年 s u r a z h s k y 和 g o t s m a n u f 又 对基于m e a n v a l u e 重心坐标的多 边形变形方法作了 进一步研究， 提出 平面三角网格的内在变形算法，即通过插值构成m e a n v a l u e 重心坐标的相关边长 西北下业大学硕 卜 学位论文 和角 度代替 直接插值m e a n v a l u e 重心坐标来实现变形。此类方法由于同时考虑了 多边形的边界和内部，因此变形效果较好， 但山于参与变形的量较多，又需解相 关的 线性方 程组， 故算法复杂度较大， 较为耗时。 2 0 0 5 年， 浙江大学的杨文武等 1 7 1 提出一种基子视觉 特征分解的多边形变形方法，由 用户交互地对多 边形进行同构 地特征分 解建立初始多 边形和目 标多边形间的 特征对应， 通过对对应特征子多 边 形的光 滑过渡与控制来实现变形。该方 法直观、简单，计算量较小，能实现多 边 形的特征保留，但用户手工劳动量较多，且不能避免边界自交现象。 1 . 2 . 3 自由曲线曲面的变形 自由曲 线曲面 造型是计算机辅助设计与制造 ( c a d / c a m) 的主要研究内 容， 研究自 由曲线曲 面的变形 对几何 造型、曲 面重建等均具有重要意义。 一般来说 , 对自由曲 线作变形，首先须对曲 线做分 段线 性逼近。最简单的方法是在曲线的参 数域内 作均匀分割，由此得到曲 线上一 批离散 样本点及其依次相连而成的平面或 空间多边形，从而转化为多边形变形问题。类似地，自山曲面的变形也可转化为 多面体的变形来实现，因为可以用空间四边形网格或三角网格来逼近曲面。当然 也 可直接对自 由曲线曲 面作 变形， 比如， 若曲 线曲面已经表示为n u r b s 形式， 可 通过插值它们的特征网格得到中间曲线曲面的特征网格，从而获得对应的中间自 由 曲 线曲 面。 1 9 9 8 年 ， s a m o llo v 和 e lb e r 18 1给出 了 一 种 可 避免自 交 的 二 维自 由 曲 线 的 变 形 算 法， 具 有 较 好的 变 形效 果 。 2 0 0 2 年 .s u ra z h s k y 和 e lb e r 19 又 提出 了 对 平 面 参 数曲线的曲 率插值来实现变形的一 种方 法。该方法基于微分几何理论，即一 条 以弧长为参数的平面曲 线，它的形状完全由 其曲 率函数所决定，只 是所在位置顶 多差一个刚体运动变换。该方法利用曲 线的内 在量曲率变形，效果良 好。 但对于 一般的非弧长参数曲线，若用该方法变形需重新弧长参数化，这不仅增加了运算 量，而且 一 般情况下可能没有解析解，无法继续施行，故该方法通用性较差。 ，2 . 4 其他二维物体的变形 山于许多平面图形无法用单一的多边形或 自由曲线来描述，因此不少学昔对 西北下业大学硕 卜 学位论文 和角 度代替 直接插值m e a n v a l u e 重心坐标来实现变形。此类方法由于同时考虑了 多边形的边界和内部，因此变形效果较好， 但山于参与变形的量较多，又需解相 关的 线性方 程组， 故算法复杂度较大， 较为耗时。 2 0 0 5 年， 浙江大学的杨文武等 1 7 1 提出一种基子视觉 特征分解的多边形变形方法，由 用户交互地对多 边形进行同构 地特征分 解建立初始多 边形和目 标多边形间的 特征对应， 通过对对应特征子多 边 形的光 滑过渡与控制来实现变形。该方 法直观、简单，计算量较小，能实现多 边 形的特征保留，但用户手工劳动量较多，且不能避免边界自交现象。 1 . 2 . 3 自由曲线曲面的变形 自由曲 线曲面 造型是计算机辅助设计与制造 ( c a d / c a m) 的主要研究内 容， 研究自 由曲线曲 面的变形 对几何 造型、曲 面重建等均具有重要意义。 一般来说 , 对自由曲 线作变形，首先须对曲 线做分 段线 性逼近。最简单的方法是在曲线的参 数域内 作均匀分割，由此得到曲 线上一 批离散 样本点及其依次相连而成的平面或 空间多边形，从而转化为多边形变形问题。类似地，自山曲面的变形也可转化为 多面体的变形来实现，因为可以用空间四边形网格或三角网格来逼近曲面。当然 也 可直接对自 由曲线曲 面作 变形， 比如， 若曲 线曲面已经表示为n u r b s 形式， 可 通过插值它们的特征网格得到中间曲线曲面的特征网格，从而获得对应的中间自 由 曲 线曲 面。 1 9 9 8 年 ， s a m o llo v 和 e lb e r 18 1给出 了 一 种 可 避免自 交 的 二 维自 由 曲 线 的 变 形 算 法， 具 有 较 好的 变 形效 果 。 2 0 0 2 年 .s u ra z h s k y 和 e lb e r 19 又 提出 了 对 平 面 参 数曲线的曲 率插值来实现变形的一 种方 法。该方法基于微分几何理论，即一 条 以弧长为参数的平面曲 线，它的形状完全由 其曲 率函数所决定，只 是所在位置顶 多差一个刚体运动变换。该方法利用曲 线的内 在量曲率变形，效果良 好。 但对于 一般的非弧长参数曲线，若用该方法变形需重新弧长参数化，这不仅增加了运算 量，而且 一 般情况下可能没有解析解，无法继续施行，故该方法通用性较差。 ，2 . 4 其他二维物体的变形 山于许多平面图形无法用单一的多边形或 自由曲线来描述，因此不少学昔对 西北下业大学硕 卜 学位论文 和角 度代替 直接插值m e a n v a l u e 重心坐标来实现变形。此类方法由于同时考虑了 多边形的边界和内部，因此变形效果较好， 但山于参与变形的量较多，又需解相 关的 线性方 程组， 故算法复杂度较大， 较为耗时。 2 0 0 5 年， 浙江大学的杨文武等 1 7 1 提出一种基子视觉 特征分解的多边形变形方法，由 用户交互地对多 边形进行同构 地特征分 解建立初始多 边形和目 标多边形间的 特征对应， 通过对对应特征子多 边 形的光 滑过渡与控制来实现变形。该方 法直观、简单，计算量较小，能实现多 边 形的特征保留，但用户手工劳动量较多，且不能避免边界自交现象。 1 . 2 . 3 自由曲线曲面的变形 自由曲 线曲面 造型是计算机辅助设计与制造 ( c a d / c a m) 的主要研究内 容， 研究自 由曲线曲 面的变形 对几何 造型、曲 面重建等均具有重要意义。 一般来说 , 对自由曲 线作变形，首先须对曲 线做分 段线 性逼近。最简单的方法是在曲线的参 数域内 作均匀分割，由此得到曲 线上一 批离散 样本点及其依次相连而成的平面或 空间多边形，从而转化为多边形变形问题。类似地，自山曲面的变形也可转化为 多面体的变形来实现，因为可以用空间四边形网格或三角网格来逼近曲面。当然 也 可直接对自 由曲线曲 面作 变形， 比如， 若曲 线曲面已经表示为n u r b s 形式， 可 通过插值它们的特征网格得到中间曲线曲面的特征网格，从而获得对应的中间自 由 曲 线曲 面。 1 9 9 8 年 ， s a m o llo v 和 e lb e r 18 1给出 了 一 种 可 避免自 交 的 二 维自 由 曲 线 的 变 形 算 法， 具 有 较 好的 变 形效 果 。 2 0 0 2 年 .s u ra z h s k y 和 e lb e r 19 又 提出 了 对 平 面 参 数曲线的曲 率插值来实现变形的一 种方 法。该方法基于微分几何理论，即一 条 以弧长为参数的平面曲 线，它的形状完全由 其曲 率函数所决定，只 是所在位置顶 多差一个刚体运动变换。该方法利用曲 线的内 在量曲率变形，效果良 好。 但对于 一般的非弧长参数曲线，若用该方法变形需重新弧长参数化，这不仅增加了运算 量，而且 一 般情况下可能没有解析解，无法继续施行，故该方法通用性较差。 ，2 . 4 其他二维物体的变形 山于许多平面图形无法用单一的多边形或 自由曲线来描述，因此不少学昔对 西北工业大学硕 卜 学位论文 较为复杂的二维图 形的变形问 题作了 研究。1 9 9 7 年， b u r c h 和h a r t 对基于i f s 的 二维分形图形的变形作了研究，并提出了一种快速实现算法。s u r a z h s k y 和 g o ts m a n 2 1 】于 加 0 1 年 将基 于 m e a n v a l u e 重 心坐 标的 平 面同 构 三 角网 格 的 变 形 方 法 推广应用于s t i c k f i g u r e 的变形，得到较为自 然的变形效果。2 0 0 3 年， j o h n s t o n e 和 w u z 2 对 两 个 多 边形 到 一 个多 边形 的 变 形 作了 研 究， h e n r y 和 t o m o y u k iz3 1研究 了 关 于多 个多 边形变形的问题， e r t e r 等人 2 4 1 弓 研究了 平面图的变形问题。 1 . 3 三维物体变形 虽然三维物体的 变形技术要比 二维的情况复杂得多， 但其 视觉效果十分逼真、 生动，因此近年来越来越多的 研究者把注意力集中于三维物体变形的 研究上 来， 提出了不少算法，取得了很多成果。由于三维物体的表示一般可归结于基于体元 的表示法 ( v o l u m e - b a s e d )和 基于边界 ( b o u n d a r y - b a s e d