（计算数学专业论文）同构三角网格的变形研究.pdf

西北 j _ 业大学硕士学位论文 摘要 随着计算机图形学和硬件技术的高速发展，计算机动画作为一种新兴的产 业，已经渗透到了 人们生活的各个角落， 如娱乐、 广告、 模拟等领域，作为计算 机动画的主要手段，变形 ( m o r p h i n g ) 技术近年来得到了 大量的研究。变形 ( 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 ) 、 形状 平均 ( s h a p e a v e r a g i n g ) 等， 是指从一 个 物体 ( 源物体) 到另一个物体 目 标物 体) 的连续、 光滑、自 然的过渡， 这里的物体可以是数字图像、多边形、 多面体 等。 伴随着电影和电视的介绍， 现在变形己经为计算机图形学领域之外的观众所 熟知， 同时， 变形也己 成为了一个热点的 研究领域。 变形技术除了应用于计算机 动画外，在许多领域都有着十分广泛的 应用， 如计算机图形学、 工业造型设计、 虚拟现实、科学计算可视化、电影特技制作等领域。 本文主要从两个方面对网 格变形做了 研究， 一种是基于凸组合的平面三角网 格变形算法， 该方法首先对平面同构三角网格做最大凸 剖分， 然后对每一对对应 的子凸网格做凸组合变形， 再对各子凸网格进行合成， 从而完成整个网格的变形。 由于本方法对原网格做了剖分， 在变形过程中 所解的线性方程组的阶数大大降 低， 故算法复杂度较低; 同时又保持了凸组合算法不自 交的优良性 质。 另一种是 基于角度插值的三角网格变形算法， 这是一种仅通过插值角度来实现任意网 格变 形的方法。 该算法首先给出了描述任意三角网格各顶点相对位置的内在角度集， 其中给出的角度变量相对于欧氏 变换是不变的， 并且由 角度变量可唯一的确定三 角网 格的形状和大小。 通过插值角度变量， 给出中间网格变形序列。 本文算法计 算速度快， 可以 达到实时变形的要求， 而且插值网 格的形状与首末网格的 位置和 朝向 无关。 该 算 法 通过 三角网 格的 一 组内 在的 角 度定 义， 实 现 三角网 格间的 变形。 由 于本算法不涉及局部直角坐标系的定义. 而是直接通过相邻三角形 之间的内在 角 度来确定与己 知三角 形有公 共边的 三角形的 另一顶点 的 位置， 从而 避免了内 在 解算法 ms i 的不稳定问题。 关键词: 变 形， 网 格， 同 构， 凸 组 合， 凸 剖 分， 多 边 形， 内 在 集 ， 内 在 角 度 变 量，插值 西北下业大学硕士学位论文 a b s t r a c t wi t h t h e r a p i d d e v e l o p m e n t o f c o m p u t e r g r a p h i c s a n d t h e t e c h n o l o g y o f h a r d w a r e , a s a n e w i n d u s t ry , c o m p u t e r a n i m a t i o n h a s i n f i l t r a t e d i n to e v e ry c o rn e r o f p e o p l e s l i f e , s u c h a s e n t e r ta i n m e n t , a d v e rt i s e m e n t , s i m u l a t i o n e t c . a s t h e m a i n m e a n s o f c o m p u t e r a n i m a t i o n , m o r p h i n g h a s b e e n i n v e s t i g a t e d in m a n y c o n t e x t s . mo r p h i n g , a l s o k n o w n a s 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 o r s h a p e a v e r a g i n g , i s t h e g r a d u a l t r a n s f o r m a t io n o f o n e o b j e c t ( t h e s o u r c e ) i n t o a n o t h e r ( t h e t a r g e t ) . h e r e , o b j e c t c a n b e a n d i g i t a l i m a g e , a p o l y g o n o r a p o l y h e d r a l e t c . wi t h t h e i n t r o d u c t i o n i n t v a n d m o v i e s , e v e r y a u d i e n c e b e y o n d t h e c o m p u t e r s g r a p h i c s c o m m u n it y n o w a d a y s k n o w s m o r p h i n g . a t t h e s a m e t i m e , m o r p h i n g h as e s t a b l i s h e d i t s e l f a s i n t e r e s t i n g r e s e a r c h a r e a s . b e s i d e s c o m p u t e r a n i m a t i o n , m o r p h i n g t e c h n i q u e h a s w i d e s p r e a d a p p l i c a t i o n s i n m a n y o t h e r a r e as, 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 i a l d e s i g n , v i r t u a l r e a l i t y , s c i e n t i f i c v i s u a l i z a t i o n e t c . t h i s p a p e r s t u d i e s t h e m e s h m o r p h in g i n t w o a s p e c t s , o n e i s t h e m o r p h i n g a l g o r i t h m o f p l a n a r t r i a n g u la r m e s h b as e d o n t h e c o n v e x c o m b i n a t i o n . f i r s t , w e d e c o m p o s e t w o m e s h e s i n t o s e t s o f c o n v e x m e s h e s i n a c o m p a t i b l e w a y ; t h e n , a c c o r d i n g t o t h e c o r r e s p o n d e n c e , m o r p h i n g t h e s u b - m e s h u s i n g t h e c o n v e x c o m b in a t i o n m o r p h i n g a l g o r i th m ; t h e n c o m p o s e t h e s u b - m e s h . t h e o t h e r i s t h e m o r p h i n g a l g o r i t h m o f t r i a n g u l a r m e s h b as e d o n a n g l e v a r i a b l e . r a t h e r t h a n c o n s i d e r i n g a t r i a n g u l a r m e s h a s a s e t o f i n d e p e n d e n t p o i n t s , t h e s o l u t i o n t r e a t s a t r i a n g u l a r m e s h as a s e t o f a n g u l a r v a r i a b l e s , w h i c h d e s c r i b e s t h e b a s i c g e o m e t r i c n a t u r e o f t h e t r i a n g u l a r m e s h . t h e c o r r e s p o n d e n t a n g u l a r v a r i a b l e s o f t h e i n i t i a l a n d t h e f i n a l m e s h e s a r e in t e r p o l a t e d t o d e t e r m i n e t h e i n t e r m e d i a t e m e s h . t h i s a p p r o a c h i s e a s y a n d f a s t e n o u g h i n f u l l y i n t e r a c t i v e t im e . o u r a l g o r i t h m i s r o b u s t a n d p r o d u c e s s a t i s f a c t o ry r e s u l t s . k e y w o r d s : m o r p h i n g , m e s h , c o m p a t i b l e , c o n v e x c o m b i n a t i o n , c o n v e x d e c o m p o s i t i o n , p o l y g o n , i n t r in s i c s e t , in tr i n s i c a n g l e v a r ia b l e , i n t e r p o l a t i o n 西北工业大学硕士学位论文 第一章 绪论 1 . 1 变形概述 随着计算机图形学和硬件技术的高速发展，计算机动画作为一种新兴的产 业，已经渗透到了人们生活的各个角落， 如娱乐、 广告、 模拟等领域， 作为计算 机动画的主要手段， 变形 ( m o r p h i n g ) 技术 近年来得到了 大量的 研究。 变形 ( m o r p h in g 或m e t a m o r p h o s i s ) ， 也 称为 形 状调 配或 融 合( s h a p e b l e n d in g ) 、 形 状 平均 ( s h a p e a v e r a g i n g ) 等， 是 指从一 个物体 ( 源物体) 到另一个物体 ( 目 标 物 体) 的连续、 光滑、自 然的过渡， 这里的 物体可以是数字图象、 多边形、 多面体 等。 伴随着电影和电视的介绍， 现在变形已 经为计算机图形学领域之外的观众所 熟知， 同时， 变形也己 成为了 一个热点的 研究领域。 变形技术除了 应用与计算机 动画外，在许多领域都有着十分广泛的应用，如计算机图形学、工业造型设计、 虚拟现实、科学计算可视化、电影特技制作等领域。最近，利用己建立的方法， 如主元素分析， 的分析己引起广泛的兴趣。 变形应用于计算机动画， 可以 减轻美 工师的手工劳动;在产品造型设计中，应用变形可以把不同造型特征相互交融， 产生新的系列造型; 变形应用于电影制作， 可以产生奇特的电影特技效果， 给人 以 美的 视觉享受。 随着现代信息社会和变形技术的不断发展， 变形将会有更加广 泛的用途。 变形通常包含两个要解决两个主要问 题， 第一个问题就是要建立首末两物体 的 元 素( 如 顶点， 边等) 之间 的 对 应关 系， 即 对 应问 题( c o r r e s p o n d e n c e p r o b l e m ) , 这其实是一个参数化问题，参数化问题是许多处理网格的领域中的一个基本问 题; 第二个问题就是建立首末两物体的 对应元素在变形过程中所走过的路径， 即 路径问 题 ( t r a j e c t o ry p r o b l e m ) 。 这一部 分带 有很大的主 观成分， 因为 它与各 人的 审美标准是密切相关的， 或者说这是一个审美问题。 遗憾的是， 对于怎样才算是 一个比 较成功的对应， 到目 前为止， 并不存在一个正式的定义; 同样， 对于路径 问 题也没有一个比较成功的解决方案的定义。 尽管如此， 对观察者来说， 变形的 中间序列还是应该看起来比较 “ 自 然” 。 关于 “ 自 然”的理解，国内外有各种各 样的观点，但一般认为，一个令人满意的变形，至少应该满足以下三个准则: 西北工业大学硕士学位论文 第一章 绪论 1 . 1 变形概述 随着计算机图形学和硬件技术的高速发展，计算机动画作为一种新兴的产 业，已经渗透到了人们生活的各个角落， 如娱乐、 广告、 模拟等领域， 作为计算 机动画的主要手段， 变形 ( m o r p h i n g ) 技术 近年来得到了 大量的 研究。 变形 ( m o r p h in g 或m e t a m o r p h o s i s ) ， 也 称为 形 状调 配或 融 合( s h a p e b l e n d in g ) 、 形 状 平均 ( s h a p e a v e r a g i n g ) 等， 是 指从一 个物体 ( 源物体) 到另一个物体 ( 目 标 物 体) 的连续、 光滑、自 然的过渡， 这里的 物体可以是数字图象、 多边形、 多面体 等。 伴随着电影和电视的介绍， 现在变形已 经为计算机图形学领域之外的观众所 熟知， 同时， 变形也己 成为了 一个热点的 研究领域。 变形技术除了 应用与计算机 动画外，在许多领域都有着十分广泛的应用，如计算机图形学、工业造型设计、 虚拟现实、科学计算可视化、电影特技制作等领域。最近，利用己建立的方法， 如主元素分析， 的分析己引起广泛的兴趣。 变形应用于计算机动画， 可以 减轻美 工师的手工劳动;在产品造型设计中，应用变形可以把不同造型特征相互交融， 产生新的系列造型; 变形应用于电影制作， 可以产生奇特的电影特技效果， 给人 以 美的 视觉享受。 随着现代信息社会和变形技术的不断发展， 变形将会有更加广 泛的用途。 变形通常包含两个要解决两个主要问 题， 第一个问题就是要建立首末两物体 的 元 素( 如 顶点， 边等) 之间 的 对 应关 系， 即 对 应问 题( c o r r e s p o n d e n c e p r o b l e m ) , 这其实是一个参数化问题，参数化问题是许多处理网格的领域中的一个基本问 题; 第二个问题就是建立首末两物体的 对应元素在变形过程中所走过的路径， 即 路径问 题 ( t r a j e c t o ry p r o b l e m ) 。 这一部 分带 有很大的主 观成分， 因为 它与各 人的 审美标准是密切相关的， 或者说这是一个审美问题。 遗憾的是， 对于怎样才算是 一个比 较成功的对应， 到目 前为止， 并不存在一个正式的定义; 同样， 对于路径 问 题也没有一个比较成功的解决方案的定义。 尽管如此， 对观察者来说， 变形的 中间序列还是应该看起来比较 “ 自 然” 。 关于 “ 自 然”的理解，国内外有各种各 样的观点，但一般认为，一个令人满意的变形，至少应该满足以下三个准则: 西北工业大学硕十学位论文 1 变形过程中产生的中间状态的一些特征， 如边长、 夹角、 面积等应保持单 调平滑的变化。 2 中间状态的边界曲线或曲面应尽量保持光滑。 3 首末物体所共有的一些特征在变形过程中应该保留。 因此， 令人满意的变形应该是平滑的， 变形过程中尽量体现出初始物体特征 的渐渐消失和目 标物体特征的逐步出现， 且不出现病态的中间状态， 如自 交、 塌 陷等。 传统上讲， 变形是应用到两个图形上的: 一个源图形和一个目 标图形。 两个 以上图形间的变形可以看作是在图形空间上的推广。 最近， 变形研究的焦点正从处理表示空间 图像、 体) 转换到应用显式的边 界表示来插值或混合物体的形状。 本文主要研究深受大众喜爱的分段线性边界表 示，即网格。 在变形中， 混合图形而不是它们所嵌入的空间， 可以得到更好的结果， 但也 需要更多的人工参与， 这是因为需要在两图形之间建立一个正确的映射; 定义这 样一个映射并不是可有可无的， 这主要有两个原因:一是边界表示需要参数化; 二是映射可能包含不同拓扑结构的图形。 1 . 2 术语和框架 网格变形技术包括几何性质和连通性的计算。 在变形领域中， 应用一项变形 技术之前， 先将多边形网格三角化己经被广泛接受。 因此本文研究集中于三角网 格的 变形。 为 便于 分类和理解 变形技术， 这里介绍广泛应用的s p a n i e r 的 术语。 网 格m用( k , v ) 表示， 其中k是表示网 格点、 边、 面之间 连通性的一个单纯复 形，v = ( v , , v z ， 二 ，w n ) 表 示r 0 空 间 中 点 的 几 何 位 置 ， 典 型 的 d = 3 a 抽 象 复 形k 将 顶 点 、 边 、 面 描 述 为 0 , 1 , 2 单 纯 形 ， 也 就 是 说 ， 边 是 一 个 顶 点 对 i , j ! 面 是 顶点 的 一 个 三 元 组 i , j , k 。 拓 扑 实 现( t o p o l o g i c a l r e a li z a t i o n ) 将k 映 射 为 r 中 的 单 纯 复 形 川: 顶 点 视 为 r 的 规 范 基 ， 且 每 一 个 单 纯 形 : 二 k 描 述 为 点 e , 卜r , i e : 的 凸 包， 这 样， 每 一 个0 一 单 纯 形 就 是r 中 的 一 个 点， 每 西北工业大学硕十学位论文 1 变形过程中产生的中间状态的一些特征， 如边长、 夹角、 面积等应保持单 调平滑的变化。 2 中间状态的边界曲线或曲面应尽量保持光滑。 3 首末物体所共有的一些特征在变形过程中应该保留。 因此， 令人满意的变形应该是平滑的， 变形过程中尽量体现出初始物体特征 的渐渐消失和目 标物体特征的逐步出现， 且不出现病态的中间状态， 如自 交、 塌 陷等。 传统上讲， 变形是应用到两个图形上的: 一个源图形和一个目 标图形。 两个 以上图形间的变形可以看作是在图形空间上的推广。 最近， 变形研究的焦点正从处理表示空间 图像、 体) 转换到应用显式的边 界表示来插值或混合物体的形状。 本文主要研究深受大众喜爱的分段线性边界表 示，即网格。 在变形中， 混合图形而不是它们所嵌入的空间， 可以得到更好的结果， 但也 需要更多的人工参与， 这是因为需要在两图形之间建立一个正确的映射; 定义这 样一个映射并不是可有可无的， 这主要有两个原因:一是边界表示需要参数化; 二是映射可能包含不同拓扑结构的图形。 1 . 2 术语和框架 网格变形技术包括几何性质和连通性的计算。 在变形领域中， 应用一项变形 技术之前， 先将多边形网格三角化己经被广泛接受。 因此本文研究集中于三角网 格的 变形。 为 便于 分类和理解 变形技术， 这里介绍广泛应用的s p a n i e r 的 术语。 网 格m用( k , v ) 表示， 其中k是表示网 格点、 边、 面之间 连通性的一个单纯复 形，v = ( v , , v z ， 二 ，w n ) 表 示r 0 空 间 中 点 的 几 何 位 置 ， 典 型 的 d = 3 a 抽 象 复 形k 将 顶 点 、 边 、 面 描 述 为 0 , 1 , 2 单 纯 形 ， 也 就 是 说 ， 边 是 一 个 顶 点 对 i , j ! 面 是 顶点 的 一 个 三 元 组 i , j , k 。 拓 扑 实 现( t o p o l o g i c a l r e a li z a t i o n ) 将k 映 射 为 r 中 的 单 纯 复 形 川: 顶 点 视 为 r 的 规 范 基 ， 且 每 一 个 单 纯 形 : 二 k 描 述 为 点 e , 卜r , i e : 的 凸 包， 这 样， 每 一 个0 一 单 纯 形 就 是r 中 的 一 个 点， 每 西北工 业大学硕士学位论文 一个 卜 单纯形是r 中的一条线段，每一个2 一 单纯形是r 中的一个三角形。 几 何 实 现( g e o m e t r i c r e a l iz a t io n ) 0 , ( ik i) 是 单 纯 复 形 k 到r 的 线 性 映 射 ， 该 映射是通过 将r 中的 基向 量e ; 与v ; 任 v 联系起来来定义的。 如果0 1 是双射， 那 么 映 射叭就是 个 嵌入( e m b e d d i n g ) ， 嵌 入的 重要 性 就在于 网 格 上的 每一 个点p 均 可以由 一个重 心坐标唯 一表示， 如p = 4 ( b ) 。 这样的重心 坐标最多 有三个非 零分 量，并且可确定一个点相对于一个单纯形的位置。如果这个点与某一顶点重合， 那么重心坐标就是一个规范基向量; 如果这点落在一条边上， 那么重心坐标就有 两个非零分量;否则它就位于某个面上，重心坐标有三个非零分量。 某 一 顶 点 i 的 相 邻 环 是 相 邻 顶 点 的 集 合 n ( i) 二 川 i, j e k ， 它 的 星 形 是 相 关 的 单 纯 形 的 集 合 s ( i) 二 u - ,- k s 。 两个平面三角网格m , = ( k v , ) 和峡 二 ( 凡， k ) 同构( i s o m o r p h i c ) 或相容 ( c o m p a t i b l e ) ，是指它们是拓扑等价的。图1 . 1 给出了 平面三角网格同构和不 同构的例子。 图1 . 1 平面上9 个点的三角网 格， 对应的顶点用相同的 颜色表示， 其中 ( a ) 与( b ) 不是同构的，( a ) 与( c ) 是同构的。 给定两个平面三角网格， 检验其是否同构是比 较容易的， 但是， 对于给定的 两组顶点要寻找其同构三角网格则是比较困难的， 甚至有时是不存在的。 己 有研 究者证明出 其同构三角网 格的存在性是一个n p 问 题， 有时需要添加一定数量的 额外顶点才能构成同构三角网格。 在 传 统 的 网 格 变 形 的 假 设 中， 给 定 两 个 网 格m o = ( k u , v o ) 和m , = ( kv , ) , 我 们 的目 标 是 产 生 一 族 中 间 网 格m ( t ) = ( k , v ( t ) ) , t e 0 , 1 ， 使 得 由 新 的 连 通 性k 西北工业大学硕士学位论文 以 及 v ( 0 ) 和 v ( 1) 表 示 的 图 形 跟 原 来 给 定 的 图 形 是 相 同 的 ， 即 0 1 ,o ) ( ik i) = 0 , , ) (1k . 1) 且 o v o )( i川 ) = ov ,) (ik ,i) . 在 多 数 情 况 下 ， v ( t ) 的 路 径 要 求 是 光 滑 的 。 产 生 这 一 族 中间网格的典型做法一般包含以下三个步骤: 1 、寻找网格间的对应关系。具体的说就是计算一个网格位于另一个网格中 的 坐 标 w o , w , ， 例 如 ， w a e o v ,)( ik , i) , w , . o v (o) ( ik o j) . w ， w 中 的 每 一 个 坐 标 都 被 描 述 为 关 于 另 一 个 网 格 中 的 一 个 单 纯 形 的 重 心 坐 标 。 值 得 注 意 的 是 ， o w . 并 不 将 k o 映 射 到 0 v (.) ( ik , i) ， 反 之 亦 然 ， 因 为 仅 仅 是 将 顶 点 映 射 到 另 一 个 网 格 上 ， 而 不是边和面。 在这一步骤中， 特别重要的是，自 动识别或用户指定的网格特征的 对齐。 2 、 产生 一个新的、 相容的网 格连通性k 和 所有顶点的 几何位置v ( 0 ) 和v ( 1 ) , 使得原来的网格可以 被重建出来。 在传统的变形方法中， 这一问 题是通过构造单 纯复 形k 。 和k , 的 超 集 来 解决的 。 然而， 在多 分 辨率 技术中 常 用的 重 新网 格 化 技 术也是一个比 较有吸引力的解决方案。 3 、 为 每 一 个 顶 点 构 造 路 径v ( t ) , t e 0 , 1 尽 管 如 前 所 述， 这 是 一 个 审 美 问 题， 但是 1 . 1 中所述的三个合理的准则对我们的设计过程是有帮助的。 在第二章中， 我们将分别详细的讨论上述所提到的几个问 题的一般理论与方 法，范围也同样仅限于网格变形方面，但如果我们认为有益时，一些多边形变形 的技术也将讨论。 1 . 3 国内外相关研究现状 针对变形所要解决的两个主要问题， 绝大多数的文献都只研究其中的一个问 题， 要么只研究对应问题， 对应点路径则取直线， 即线性插值; 要么假定对应关 系已 经给定， 只研究路径问题; 而我们所见到的同时解决这两个问题的 文献仅有 k a u l 和ft i o s s i g n a c 提出的 基于m i n k o w s k i 和的算法， 但效果并不理想， 因为 它 很容易混淆物体的相似部分。 这里只介绍相关的工作及其优缺点分析， 变形的一 般理论我们将在第二章做详细的介绍; 西北工业大学硕士学位论文 以 及 v ( 0 ) 和 v ( 1) 表 示 的 图 形 跟 原 来 给 定 的 图 形 是 相 同 的 ， 即 0 1 ,o ) ( ik i) = 0 , , ) (1k . 1) 且 o v o )( i川 ) = ov ,) (ik ,i) . 在 多 数 情 况 下 ， v ( t ) 的 路 径 要 求 是 光 滑 的 。 产 生 这 一 族 中间网格的典型做法一般包含以下三个步骤: 1 、寻找网格间的对应关系。具体的说就是计算一个网格位于另一个网格中 的 坐 标 w o , w , ， 例 如 ， w a e o v ,)( ik , i) , w , . o v (o) ( ik o j) . w ， w 中 的 每 一 个 坐 标 都 被 描 述 为 关 于 另 一 个 网 格 中 的 一 个 单 纯 形 的 重 心 坐 标 。 值 得 注 意 的 是 ， o w . 并 不 将 k o 映 射 到 0 v (.) ( ik , i) ， 反 之 亦 然 ， 因 为 仅 仅 是 将 顶 点 映 射 到 另 一 个 网 格 上 ， 而 不是边和面。 在这一步骤中， 特别重要的是，自 动识别或用户指定的网格特征的 对齐。 2 、 产生 一个新的、 相容的网 格连通性k 和 所有顶点的 几何位置v ( 0 ) 和v ( 1 ) , 使得原来的网格可以 被重建出来。 在传统的变形方法中， 这一问 题是通过构造单 纯复 形k 。 和k , 的 超 集 来 解决的 。 然而， 在多 分 辨率 技术中 常 用的 重 新网 格 化 技 术也是一个比 较有吸引力的解决方案。 3 、 为 每 一 个 顶 点 构 造 路 径v ( t ) , t e 0 , 1 尽 管 如 前 所 述， 这 是 一 个 审 美 问 题， 但是 1 . 1 中所述的三个合理的准则对我们的设计过程是有帮助的。 在第二章中， 我们将分别详细的讨论上述所提到的几个问 题的一般理论与方 法，范围也同样仅限于网格变形方面，但如果我们认为有益时，一些多边形变形 的技术也将讨论。 1 . 3 国内外相关研究现状 针对变形所要解决的两个主要问题， 绝大多数的文献都只研究其中的一个问 题， 要么只研究对应问题， 对应点路径则取直线， 即线性插值; 要么假定对应关 系已 经给定， 只研究路径问题; 而我们所见到的同时解决这两个问题的 文献仅有 k a u l 和ft i o s s i g n a c 提出的 基于m i n k o w s k i 和的算法， 但效果并不理想， 因为 它 很容易混淆物体的相似部分。 这里只介绍相关的工作及其优缺点分析， 变形的一 般理论我们将在第二章做详细的介绍; 西北工业大学硕士学位论文 邵.3 . 1 有关 对 应问 题的 研究 在变形对应问 题的 研究中， 每一种算法都各有其适用范围。 1 中 s e d e r b e r g 基于一种物理模型，把平面多边形的边看作金属丝，通过使得初始多边形由弯曲 或者伸缩变为目 标多边形时所作的功最小，来建立初末多边形顶点的对应关系， 该 方 法适用于两个相似的 平面多 边形; k a n a i 在其文献 2 中 利用h a r m o n i c 映 照使 得初始和目 标多面体网 格和相应的平面网 格对应， 并将这两个平面网格重叠进而 建立初末多面体的对应关系， 这种方法适用于两个同胚于3 d球或2 d圆盘的可以 不相似的多面体; 3 中g r e g o r y 用特征点把多面体网格对应分片， 通过对分片的 对应，建立两多面体的对应关系，该方法适用于两个不相似的同胚的简单 ( 或非 简单)的多面体; 4 中d e c a r l o 利用初末曲 面上的 稀疏控制网格建立亏格不同的 曲面的对应关系，该方法适用于拓扑结构不相同的曲面。 那 .3 .2 有关 插值问 题的 研究 对变形 插值问 题的 研究常 常 是在假设 对应关系己 经确立的前 提下进 行的。 5 中b e ie : 和n e e ly 提出 一 种图 象 变形的 方 法， 该 方 法 基于 一 种影响 场， 通过 在初 末图象中使用若干条对应的辅助线来完成图象的对应和插值，从而实现图象变 形， 是一种较成功的图象变形方法， 但在有些情况下会出 现病态，即某些时刻的 中间图像产生重叠、相交。 在解决多边形、多面体、曲线和曲面的插值问题的方 法中，一个最简单的方法是顶点线性插值法，这种方法生成速度快， 但变形中可 能引起边界的非正常萎缩，产生自 交，一些简单的几何特征如长度、角度等不能 一致的 变化， 原因 是各个顶点 在 变形 过程中 缺乏联 系， 其路径是相互 独立的。 6 中 k a u l 和 r i o s s ig n a 。同时研究变形的对应问题和插值问题，提出了基于 m i n k o w s k i s u m的 算法，使得这两个问 题同时得到解决， 但该方法很容易混淆物 体的 相 似部分。 1 9 9 3 年s e d e r b e r g 和王国 瑾等在 7 中 提出 关于平面多 边 形变形的 一个内在解算法，1 9 9 8年建立了用于空间多边形或多面体变形的新算法 ms i ( m o v i n g s p h e r i c a l c o o r d i n a t e i n t e r p o l a t i o n ) ( 见 8 ) ， 该方法首先找出 初末多边 形或多面体的顶点在局部直角坐标系中的极坐标或者球面坐标，即内在集，通过 线性插值其内在变量，重构出中间状态。该方法能够体现多边形或多面体的内在 西 七 _ 业大学硕士学位论文 结构特征， 且生成速度快， 取得了很好的变形效果。 但是由于边界的各个部分之 间缺乏联系， 没有明确的考虑到多边形或多面体的内部， 所以许多情况下边界容 易自 交，内部面积 ( 体积) 在变形中易 产生扭曲。 基于这种考虑， s h a p i r a和 r a p p o p o r t 9 利用多边形的星骨架 s t a r s k e l e t o n )表示方法得出一种插值方法， 该方法首先构造初末多边形的同构的星骨架，然后线性插值相应的元素如边长、 角度等得出中间多边形。由于它既考虑到了多边形的边界，也考虑到了其内部， 故减少了变形过程中 产生自 交的可能性。 a l e x a 1 0 将初末物体分解成同 构的单纯 复形， 在两个对应单纯形之间定义仿射变换， 并将其表示成旋转变换和伸展变换 的复合， 将这两种变换线性插值得到期望的仿射变换， 然后通过使得中间 物体在 最小二乘的意义下逼近该期望的仿射变换， 从而达到扭曲 最小的效果。 该方法考 虑了物体的内部，且变形具有刚性，因而变形过程比较自 然，且不易产生自 交。 1 1 提出了一种平面参 数曲 线的 变形方 法， 该 方法基于曲 线微分 几何的 有关理论， 即以弧长为参数的平面曲 线除了一个刚体运动变换外，由 其曲 率完全决定。 通过 线性插值初末曲 线的曲率，重构出中间曲 线， 并以分段插值建立对应关系。该方 法产生的变形过程不仅光滑， 而且利用了内 在曲率形状特征，因而变形效果是令 人满意的。 但是， 这种方法仅适用于以 弧长为参数的曲线变形， 一般参数曲线须 重新参数化为弧长参数， 而且其中重构曲线的积分表达式对于一般的曲率没有解 析解，故变形复杂度大，实 现比 较困难。 f l o a t e r 和g o t s m a n 1 2 基于平面三角网 格的内顶点的凸组合表示方法， 提出了具有相同凸边界的同构三角网格的变形方 法，称为凸组合变形，该方法能够使得中间三角网格始终与初末网格同构，不产 生自 交， 且变 形过 程连 续 光 滑。 受 1 2 方法 的 启 发， g o t s m a n和s u r a z h s k y 1 3 给 出了可避免自 交的平面简单多边形的变形方法， 它将初末多边形分别嵌入到两个 具有相同凸 边界的同 构 平面三角网 格中， 通过采用【 1 2 的 方法对这两个三角网 格 进行变形，以此实现多边形的变形。 该方法首次彻底的解决了平面多边形的变形 中产生自 交的问题，并且应用于图象变形，也可以保证中间图象不产生折叠。 g o t s m a n 和 s u r a z h s k y 在后来的研究中 提出了 可控制的同 构平面三角网 格的变形 方 法【 1 4 , s t i c k f ig u r e s 的 变 形 方法 巧 ， 同 构 三角 网 格的内 在 变形 1 6 ， 使 得这 种基于同构三角网 格变形的方法得到了 进一步完善。 但是这种嵌入相同凸 边界的 同构平面三角网格的变形方法，没有考虑初始和目 标多边形或更一般的 s t ic k 西北工业大学硕士学位论文 f i g u r e的 几何形 状，因 而变形效 果未必 令人满意， 而且在同 构 剖分时 使用的 额 外 顶点较多，故算法的复杂度较大。 1 . 4 论文内 容及主要研究成果 第一章对变形技术做了总的介绍，并对国内外有关变形的研究现状、主 流、趋势做了总的概述，简要分析了主要变形技术的思想、方法以及它们的优缺 点和适用范围，阐明了本人的主要研究成果 ( 详见第三、四章) 。 第二章对变形的基本理论与方法做了详细的介绍。 第三章介绍了基于凸组合的平面同构三角网格的变形算法，对于非凸边 界的三角网格，文中提出了凸组合变形的改进算法。 第四章介绍了 基于内在变量的网格变形算法， 分析了m s t 算法的优缺点， 并在此基础上提出了基于角度插值的网格变形算法。 第五章论文工作总结及进一步工作展望。 西北工业大学硕士学位论文 f i g u r e的 几何形 状，因 而变形效 果未必 令人满意， 而且在同 构 剖分时 使用的 额 外 顶点较多，故算法的复杂度较大。 1 . 4 论文内 容及主要研究成果 第一章对变形技术做了总的介绍，并对国内外有关变形的研究现状、主 流、趋势做了总的概述，简要分析了主要变形技术的思想、方法以及它们的优缺 点和适用范围，阐明了本人的主要研究成果 ( 详见第三、四章) 。 第二章对变形的基本理论与方法做了详细的介绍。 第三章介绍了基于凸组合的平面同构三角网格的变形算法，对于非凸边 界的三角网格，文中提出了凸组合变形的改进算法。 第四章介绍了 基于内在变量的网格变形算法， 分析了m s t 算法的优缺点， 并在此基础上提出了基于角度插值的网格变形算法。 第五章论文工作总结及进一步工作展望。 西北工业大学硕十学位论文 第二章 变形的基本理论与方法 针对第一章中 所提到的 变形的 两个主要问 题， 本章对变形的基本理论及方法 做详细的讨论。 2 . 1 图形的对应问题 本节我们的目的在于寻找两个或多个图形上对应的顶点位置。 给定两个网格 m 。 和m ， ， 这 一 过 程的 结 果 是 一 个 重 心 坐 标的 集 合风， 使得域上这 些重 心 坐标 的 几 何 体 w o 。 残 b o ) 是 m o 在 m . 网格的顶点映射到另一个网格上， 上 的 一 个 嵌 入戍， 反 之 亦 然 想 法 就 是 将一 个 以 完 成m o 和私之间 双 射的 主要 部分， 经过 这 一步，仅有边和面需要做相应的调整。 这一步骤的典型做法是为曲面寻找一个公共的参数域d。 通过将每一个曲面 可逆的映射到参数域上， 图 形间的映射就被建立起来了。 在变形的情况下， 网 格 的典型参数域是球5 2( 在网格是一拓扑球的情况下)或者是一个由分段线性参 数域描述的拓扑圆盘的集合。 在圆盘情况下， 网格必须分解成圆盘的同构结构( 这 要求原网格是同构的) 。一个主要的约束的要考虑用户指定或自 动生成的特征的 对应 ( 如点一 点对应) 。 依赖于所选的方法，决定是通过重新参数化还是按照特征 对应分解网格来完成这一步骤。 在 映 射 到 球 面 的 情 况 下 ， 需 要 计 算 嵌 入 人 ， s = i s o , s . .i ， s . e 矿 ,s ;! 一 i . 球 面上的嵌入由 一个球面到球面的 双射.f 按照 特征对应对齐。 i) ; k 。 wo0残 b o ) d so t 叹 5 ，一 芍 汁5 ， 这 个方 法 里的主 要问 题是 计 算 球 面上 的 顶点 坐 标s o , 尽以 及 重 新参 数 化 映 射f。 分解方法是更普遍也更困难的方法。 除了要产生拓扑圆盘的嵌入外， 还必须 西北工业大学硕十学位论文 第二章 变形的基本理论与方法 针对第一章中 所提到的 变形的 两个主要问 题， 本章对变形的基本理论及方法 做详细的讨论。 2 . 1 图形的对应问题 本节我们的目的在于寻找两个或多个图形上对应的顶点位置。 给定两个网格 m 。 和m ， ， 这 一 过 程的 结 果 是 一 个 重 心 坐 标的 集 合风， 使得域上这 些重 心 坐标 的 几 何 体 w o 。 残 b o ) 是 m o 在 m . 网格的顶点映射到另一个网格上， 上 的 一 个 嵌 入戍， 反 之 亦 然 想 法 就 是 将一 个 以 完 成m o 和私之间 双 射的 主要 部分， 经过 这 一步，仅有边和面需要做相应的调整。 这一步骤的典型做法是为曲面寻找一个公共的参数域d。 通过将每一个曲面 可逆的映射到参数域上， 图 形间的映射就被建立起来了。 在变形的情况下， 网 格 的典型参数域是球5 2( 在网格是一拓扑球的情况下)或者是一个由分段线性参 数域描述的拓扑圆盘的集合。 在圆盘情况下， 网格必须分解成圆盘的同构结构( 这 要求原网格是同构的) 。一个主要的约束的要考虑用户指定或自 动生成的特征的 对应 ( 如点一 点对应) 。 依赖于所选的方法，决定是通过重新参数化还是按照特征 对应分解网格来完成这一步骤。 在 映 射 到 球 面 的 情 况 下 ， 需 要 计 算 嵌 入 人 ， s = i s o , s . .i ， s . e 矿 ,s ;! 一 i . 球 面上的嵌入由 一个球面到球面的 双射.f 按照 特征对应对齐。 i) ; k 。 wo0残 b o ) d so t 叹 5 ，一 芍 汁5 ， 这 个方 法 里的主 要问 题是 计 算 球 面上 的 顶点 坐 标s o , 尽以 及 重 新参 数 化 映 射f。 分解方法是更普遍也更困难的方法。 除了要产生拓扑圆盘的嵌入外， 还必须 西北工业大学硕士学位论文 在考虑可能的特征对应的情况下， 将网格按同构方式分解。 形式上， 我们要用一 个包含k o 和k ， 子 集的 抽象单 纯复形l 来 粗略的 逼近两个网 格: 0 , o ( il i) - 0 , ,o ,(i k o l) 一且 v, (i l i) - 0v, (ik ,i) 。 典 型 的 ， l 是 k o 和 k . 的 子 式 ， 如 它 是网