（计算机应用技术专业论文）基于hermite细分曲面算法的交互设计模块的研究与实现.pdf

y 5 8 g, 1 9 1 北方交通大学硕士学位论文 摘要 曲面造型方法一直以 来都是计算机图形学领域的研究重点和热点 之一，它主要研究在计算机图形系统环境下对曲面的表示、设计、显 示和分析等。网格细分 ( s u b d i v i s i o n )是曲面的一种表示方法，是曲 面造型的一个分支，也是曲 面造型的研究重点之一。曲 面造型方法由 于其局部性好、计算量小、算法简单、响应速度高等优点，已 经广泛 应用于计算机图形学、 c a g d 、计算机动画以及虚拟现实等领域。细 分方法实际上是从一个称为控制网格 ( 绝大多数网格数据可用数字化 仪通过人工模型来输入)的多面体开始，递归地计算新网格上的每个 顶点，这些顶点都是其上一细分级网格上某几个顶点的加权平均。由 于细分造型方法具有执行效率高、数值稳定性好等诸多优越性，展开 对细分算法的研究具有一定的理论和实际意义。本文围绕 h e r m i t e曲 面细分方法进行了以下几个方面的工作: 一、论述了研究曲面造型方法的意义， 分析了国内外曲面造型方 法研究的现状和发展方向，最后就细分曲面方法的优缺点与传统造型 方法进行了比较。 二、介绍了细分曲面的原理和一些基本概念， 并给出了细分模式 的特点和细分曲 面算法的 分类。 三、讨论了h e r m i t e 细分曲 面算法的背景、 定义， 分类， 并详细 介绍了 两 种h e r m i t e 细分算 法。 最后 将h e r m i t e 算法与l o o p 细分算法 和改进的蝶型细分算法进行了比较。 四、介绍了 一种用于实现h e r m i t e 细分曲面算法的数据结构， 并 说明了实现这种数据结构的位置排序算法。最后，在以上分析和研究 的基础上，采用面向对象技术，结合 v c + + 和 o p e n g l技术实现了 h e r m i t e 细分算法。 五、为了方便展开对h e r m i t e 细分算法的进一步研究， 给出了基 于h e r m i t e 细分曲面算法的简单三维形体的交互设计模块，并给出了 具有真实感的绘制结果。 关键词:曲面造型 网格细分 i i e r m i te 细分 交互设计 北方交通大学硕士学位论文 a b s t r a c t s u r f a c e m o d e l i n g m e t h o d i s o n e o f t h e r e s e a r c h e m p h a s e s a n d h o t s p o t a l l t h e w h i l e , a n d w h a t i t f o c u s e s o n i s t h e d e n o t a t i o n , d e s i g n , d i s p l a y , a n a l y s i s o f s u r f a c e u n d e r t h e e n v i r o n m e n t o f c o m p u t e r g r a p h i c s s y s t e m . s u b d i v i s i o n i s o n e m e t h o d t o d e n o t e s u r f a c e , a b r a n c h o n e o f t h e r e s e a r c h e m p h a s e s o f s u r f a c e m o d e l i n g . s u r f a c e m o d e l i n g m e t h o d s h a v e f o u n d t h e i r w a y i n t o w i d e r a p p l i c a t i o n in c o m p u t e r g r a p h i c s , c o m p u t e r a s s i s t e d g e o m e t r i c d e s i g n ( c a g d ) , c o m p u t e r a n i m a t i o n , a n d v i r t u a l r e a l i t y ( v r ) e t c . b e c a u s e o f t h e g o o d l o c a l i t y , s m a l l c o m p u t a t i o n , s i m p l i c i t y , h i g h s p e e d i n f a c t , s u b d i v i s i o n i s a m e t h o d t h a t r e c u r s i v e l y c o m p u t e s t h e n e w v e r t i c e s , w h i c h a r e a v e r a g e d w i t h w e i g h t b y o l d v e rt i c e s in p r e v i o u s l e v e l , f r o m t h e i n i t i a l p o l y h e d r o n n a m e d c o n t r o l m e s h e s w h o s e d a t a c a n b e a c h i e v e d fr o m t h e d e v ic e s s u c h a s d i g it i z e r . b e c a u s e o f i t s a d v a n t a g e in g o o d e x e c u t i o n e f f ic i e n c y a n d d a t a s s t a b i l i t y , i t i s s i g n i f i c a n t i n t h e o ry a n d p r a c t i c e f o r u s t o r e s e a r c h i n t o s u b d i v i s i o n a l g o r i t h m s . t h e f o l l o w i n g w o r k o n h e r m i t e s u b d i v i s i o n i s c a r r i e d t h r o u g h i n t h i s p a p e r : 1 . d e m o n s t r a t e t h e s i 加fi c a n c e t o r e s e a r c h s u r f a c e m o d e l i n g m e t h o d , a n d a n a l y z e t h e s t a t u s a n d d e v e l o p m e n t , t h e n c o m p a re s u b d iv i s i o n m e t h o d w i t h t r a d i t i o n a l s u r f a c e m o d e l i n g m e t h o d . 2 . i n t r o d u c e t h e t h e o ry a n d s o m e b a s i c c o n c e p t i o n s , a n d t h e n a d v a n t a g e a n d c l a s s i f i c a t i o n o f s u r f a c e s u b d i v i s i o n a l g o r i t h m. 3 . d i s c u s s t h e b a c k g r o u n d , d e f in i t i o n , c l a s s i fi c a t i o n o f h e r m i t e s u r f a c e s u b d i v i s i o n a l g o r i t h m , a n d i n t r o d u c e t w o s u b d i v i s i o n a l g o r i t h m s i n d e t a i l . a t l a s t , c o m p a r e h e r m it e a l g o r i t h m w i t h l o o p s c h e m e a n d mo d i f i e d b u tt e r fl y s c h e m e . 4 . i n t r o d u c e a d a t a s t r u c t u r e f o r i m p l e me n t i n g h e r m i t e s u b d i v i s i o n a l g o r it h m , a n d p o s i t i o n s o r t a l g o r i t h m w h i c h u s e d f o r i m p l e m e n t i n g t h e d a t a s t r u c t u r e . b a s e d o n a n a l y s i s a n d r e s e a r c h a b o v e , t h r o u g h o o p , v c + + a n d o p e n g l t e c h n o l o g y , i m p l e m e n t h e r m i t e s u b d i v i s i o n a l g o r i t h m . 5 . f o r f u r t h e r r e s e a r c h t o h e r m i t e s u r f a c e s u b d i v i s i o n a l g o r i t h m , a n i n t e r a c t i v e d e s i g n m o d u l e f o r s i m p l e 3 d o b j e c t s i s p r o v i d e d , a n d r e n d e r i n g r e s u l t s w i t h re a l i t y a r e s h o w n . k e y wo r d s : s u r f a c e mo d e l i n g , me s h s u b d i v i s i o n , h e r m i t e s u b d i v i s i o n i n t e r a c t i v e d e s i g n 北方交通大学硕士学位论文 第一章绪论 本章首先介绍了细分造型方法的背景和展开研究的目的， 紧接着 介绍了细分造型方法的产生与发展，以及细分造型方法的基本概念， 并将细分造型方法与传统样条、代数方法、变分法等造型方法进行了 比较。然后概述了细分造型方法在曲线曲面造型中最新进展，在本章 的最后说明了本论文的内容安排。 芬 1 . 1研究细分造型方法的背景和目的 夸 1 . 1 . 1 研究背景 1 9 9 9 年a c m s i g g r a p h 成 就 奖 授 予t o n y d e r o s e 12 6 1 ， 原因 之一 是为表彰他把细分方法创造性地应用于解决图形学中的实际问 题所做 的贡献。 这标志 着细分方法作为 计算机图 形学(3 7 和c a g d ( 8 1 (3 8 1 的 造型 方法之一，并得到计算机图 形学界的一致公认。 在c a d / c g中，曲面造型是一个有着较长历史的领域，早在6 0 年代 初 期就已 诞生。 1 9 6 3 年， f u g e r s o n 提出 将曲 线曲 面 表示 为 参 数向 量函数形式，在此之前曲线曲面都是采用普通的函数表示形式 y = f ( x ) 和z = f ( x , y ) 或它 们的隐 式 方 程表示形式。 1 9 6 4 年， c o o n s 提出了一种由四条边界曲线确定的参数曲面，即c o o n s 曲面片，从而 使分片表示完整曲面成为可能。 b d z i e r 于1 9 7 1 年提出的利用控制多边 形定义曲线的方法，则可以很方便地控制曲线的形状，但曲线上任一 点都与多边形的所有顶点相关，因此对控制多边形作任何调整都会影 响到曲线的整体形状。7 0 年代初d e b o o r g o r d o n 和r i e s e n f e l d 等人 发展了b 样条曲 线曲 面的 理论 和算法 (4 1 ， 保留了b e z i e : 曲 线的 大部分 优点的同时，由于是分段多项式，可以实现局部控制。但是上述各种 方法的缺点是不能表示圆锥截线和球面椭球面等初等解析曲面，为此 v e r s p r i l le 于1 9 7 5 年提出 有理b 样条方法。 最后在p i g e i 和t i l l e r 等人 北方交通大学硕士学位论文 的努力下，终于在8 0 年代后期发展起来非均匀有理b样条( n u r b s ) 方法， 把有理和非有理b e z i e r 曲线和b样条曲线曲面及圆锥曲线和初 等解析曲面统一在一种表示之中， 最终使n u r b s 成为c a d / c a m行 业 的 工 业 标 准 ， 。 上述各种曲面都是定义在矩形参数域上，是矩形曲面片，无法有 效地表示任意拓扑形状的曲面。通常采用逐片构造方法表示复杂物体 表面，这时候需要对曲面片进行剪裁( t r i m m in g ) 或直接在非规则的四 边形网格上构造曲面片，无论哪种情况都要考虑片与片之间的光滑连 接。 尽管也有三角形域上的b e z ie r 曲 面9 ， 但表示复杂物体时同 样需 要拼接，这是一个相当困难的工作。 细分曲面( s u b d i v i s i o n s u r f a c e s ) 是一个网 格序列的极限，网格序列 则是通过采用一组规则( 一般是加权平均) 在给定初始网格中插入新顶 点并不断重复此过程而获得。这种方法克服了参数曲面处理任意拓扑 网 格( a r b i t r a r y t o p o l o g y m e s h e s ) 存在的困 难， 这是因 为在不 规则拓扑处 只须采用特殊的细分规则就可以了，不存在拼接的问题。 另一方面，由 于三维扫描仪( 3 d s c a n n e r ) ,测距仪( r a n g e f i n d e r ) 和 c t等三维数据获取设备的日益完善，为几何形状不能或难于用分析 曲面表示的对象建模提供了有力的工具，离散曲面逐渐成为一种重要 的几何表示方法。作为从给定规则产生离散曲面的方法， 细分模式统 一了传统的参数曲 面与多边形两种实体表面的表示。另外，由于实验 获取的三维数据量一般都非常大，多分辨率分析 m u l t i re s o lu t i o n a n a l y s i s ) 成为有效地处理这类数据的重要手段。细分方法与多分辨率 分析、 小波变换( w a v e l e t t r a n s f o r m a t i o n ) 之间的深刻联系也是目 前细分 模式倍受关注的一个重要原因之一。 签 1 . 1 . 2 研究目的 由于细分方法不受控制网格拓扑的限制， 可以对任意拓扑网格进 行曲面造型，而且其递归结构与小波和多分辨率分析有着密切联系， 使得细分方法在图形学领域得到深入的研究和广泛的应用。但是，要 进一步拓广细分方法的应用范围 ( 尤其是在 c a d领域的应用)还有 北方交通大学硕士学位论文 很多工作要做。例如，高阶连续细分模式的构造、细分方法与解析方 法的溶合、细分曲面的光顺、细分曲面间的逻辑运算、数学工具的改 善以及满足各种应用要求的新模式的发展等等。这里高阶连续细分模 式是指生成的极限曲面整体连续次数都大于或等于 2 的模式。因此， 对细分造型方法展开研究的目 的是找到一些行之有效的造型方法，以 进一步提高细分曲面的造型能力，同时探讨细分方法的应用。 夸 1 . 2 细分造型方法的产生、发展及意义 细分思想最早可以追溯到二十世纪 4 0年代末 5 0年代初，当时 g d e r h a m通过对折线角点进行切割( c o r n e r c u t ) 来生成光滑曲 线的思 想，即所谓的“ 砍角算法” 。 7 0 年代中期， c h a ik i n 生成曲线的细分方 法2 l 正是该砍角算法思想的具体实现。 稍后c a t m u l l 和c l a r k 提出了递 归细分四 边形网格生成双二次与双三次b 样条曲 面片的方法d ，并推 广到任意拓扑网格，标志着细分方法正式成为曲面建模的手段。当矩 形网格没有奇异点 ( 共享顶点的边数，称为顶点的价。对于四边形网 格，价不等于4 的顶点称为奇异点或非正规点，在后面将进一步给出 明确定义)时， c a t m u l l - c l a r k 模式生成三次b样条曲面: 对于存在奇 异点的网格，生成的曲面除有限个点外，具有二阶光滑，可以说是一 张“ 几乎处处连续”的三次b样条曲 面。 与此同时， d o o 和 s 的i n 5 1 采用离散f o u r i e r 变换的方法，对c a t m u l l - c l a r k 模式的收敛性进行了 分析，开创了细分模式收敛性矩阵特征分析的先河。大致可以把细分 方法的发展历史分成如下三个阶段: ( 1 ) 7 0 年代后期c a t m u l l - c l a r k 细分模式以 及d o o - s a b i n 关于非正 规点处行为的分析理论标志着细分方法正式成为曲 线曲面造型的一种 手段。 ( 2 ) 8 0 年代末到9 0 年代初的 形成期。 在这一时期， 提出了 很多著 名的细分方法，对旧方法也有许多改进以适应不同要求，规则情形的 收敛性和连续分析理论也逐渐完善。不过，各种模式之间仍然缺乏联 系， 一般情形的收敛性分析方法也是“ 随身定做” ， 缺乏一般的理论指 导。 ( 3 ) 9 0 年代中期到现在的发展期。 这一时期开始建立系统的收敛 性理论，提出了多变元模式任意拓扑情形下收敛性分析的理论框架。 这些理论反过来指导细分模式的构造，尤其是二阶以上连续曲面的构 北方交通大学硕十学位论文 造。此外，各种细分模式的内 在联系也逐渐被揭示出 来，例如 z o r in 和 s c h r o d e r 为初始 ( p r i m a l )四边形网格细分模式和对偶 ( d u a l )四 边形网格细分模式建立了 统一的 框架3 i 。 更为重要的是， 在这一时期， 细分方法得到了广泛应用，尤其是复杂网格曲面的多分辨率分析的研 究取得了大量成果。 从上面的分析可以看出， 细分方法早在上世纪中后期就己应用于 曲面造型的研究。但直到近年来，细分造型方法才在计算机图形学和 计算机辅助几何设计中得以广泛应用。其中一个重要原因是由于多分 辨率技术成为解决复杂几何中问题的关键技术之一，而细分造型方法 与多分辨率技术以及传统工具 ( 例如小波技术)密切相关。 细分曲面造型方法的意义在于， 它对计算机图形学的发展起到了 重大的推动作用。利用细分方法可以很好地解决计算机图形学曲面造 型领域的很多难题: ( 1 )任意拓扑结构:在计算机辅助几何造型中，许多自由曲面 是定义在三角形、四边形或任意拓扑结构上。定义在任意拓扑结构上 的复杂曲面通常不能由n u r b s . b样条或 b e z i e r 曲面表示出来，而 细分造型方法可以生成任意拓扑结构的光滑曲面，从而避免了复杂且 难于处理的参数曲面片的光滑拼接问题。 ( 2 )可扩展性:由于细分方法基于不断细化，很自然地解决分 层细化控制以 及自 适应逼近等问 题，可以 充分利用有限的硬件资源， 在p c机上很容易实现。 ( 3 )表示方法的一致性:传统方法使用多边形网格或者样条面 片中的一种表示法进行曲面造型， 而细分方法将两种表示法统一起来， 细分曲面既可以看作是由面片造型而来，也可以 看作是由很多小多边 形网格组成的。 ( 4 )数值稳定性:细分网格具有很好的特性，使得细分表示法 非常适于工程上以及计算机动画中常用到的数值模拟运算。 ( 5 )易于实现性:尽管细分理论涉及到很多的数学分析，但是 代码简单容易实现，执行效率很高。 1 . 3 细分造型方法简介 细分造型方法的实质是通过对初始控制点或者初始网格进行一 系列细化的过程，细化的极限生成所需要的曲线或者曲面。 图1 . 1 是细分曲线的一个例子， 初始有4 个点， 用线段直接相连， 北方交通大学硕士学位论文 经过一步细分过程，在初始点之间各增加一个点。可以看出，再经过 二步细分过程后，曲线己经相当光滑。继续细分，即可生成满足所要 求分辨率的细分曲线。 图1 . 1 二维曲 线的细分 图 1 .2是一个细分曲面的例子，细分过程是将初始网格上的每个 三角形分裂为4 个新三角网格，一次细分后的结果如右图。 图1 . 2 细分曲面 细分过程是根据已知的细分规则增加新点，细分曲线曲面的形状 和光滑性都取决于选定的细分规则。 选择细分规则需要满足如下属性: ( 1 )高效性:计算新点位置只需要几步浮点运算; ( 2 )紧致集: 每个点对最后得到的细分曲线的影响区域要很小而 且有限; ( 3 )局部定义: 定义新点只和相邻几个点有关， 而和较远区域的 点无关; ( 4 )仿射变换不变性: 如果对初始点集进行平移、 旋转、 放缩等 仿射变换，细分曲线曲面也会进行相应的变换; 北方交通大学硕士学位论文 ( 5 )简单性:细分规则要简单而且规则的数目要少; ( 6 ) 连续性: 细分曲 线曲 面的c k 连续性。 互 1 . 4 细分造型方法与传统造型方法比较 细分造型方法与传统样条、代数方法、变分造型等方法相比，在 执行效率、任意拓扑结构、细分曲 面特征以 及复杂几何形状等方面都 有其独特的优势: ( 1 )执行效率 计算量是造型方法中需要考虑的一个重要因素。 在细分造型方法 中，计算新点只与相邻的几个点有关，因而很容易实现而且计算效率 很高。 这和传统样条造型方法中的节点插入 ( k n o t i n s e r t i o n ) 方法很 类似，实际上，很多细分方法是节点插入方法的推广。代数方法的计 算量很大，而变分方法的计算量最大，例如曲面造型中每次曲面改变 时都需要解决全局优化问 题。 ( 2 ) 任意拓扑结构 对任意拓扑结构进行造型是代数方法的长处， 代数方法甚至可以 处理造型过程中拓扑结构改变的情况，但代数方法对拓扑网格、精确 位置以及细分曲面的连续性很难控制。传统样条方法很难处理任意拓 扑结构造型，当采用矩形样条面片时，很难保证细分曲面在奇异点处 的高阶连续性，而且表达式也更加复杂。相对于其他造型方法，变分 方法对于任意拓扑结构造型要更好，但计算量相当大。而细分造型方 法既可以很好地处理任意拓扑结构造型，又不失高效性。实际上，细 分造型方法就是研究人员在解决样条造型方法中所遇到的任意拓扑结 构造型问题时发展起来的。 ( 3 )细分曲面特征 在曲 面造型中经常需要控制皱折、 凹槽或者尖点等特征的形状和 大小。变分方法在处理这些特征时显示了很大的灵活性，而且可以精 确的控制。代数方法由于造型不直接，很难控制这些特征的造型。样 条方法可以精确地控制特征造型，但计算量很大，而且很难把这些特 征融入到曲面中的任意位置。细分造型方法比样条方法控制更灵活， 不仅可以选择控制点的位置，而且可以通过改变细分参数来进行特征 北方交通大学硕士学位论文 造型或者控制边界曲 线。 ( 4 )复杂儿何形状 在交互式应用中， 执行效率是最关心的问题。由于细分方法基于 不断细化，可以很容易地解决分层细化控制以及互联网上传输中的压 缩问题。 当然细分造型方法自 身也有许多急待解决的问题， 如非正规点处 的格式不能统一、 光滑性降低、 复杂形体的交互设计难以实现等问题。 本论文讨论的 h e r m i t e 型细分方法具有双重控制的特点，能够将插值 控制和切向控制相结合，还可消除非正规点的特殊性，而且具有更灵 活的交互性。本文的目 的是在前面研究的基础上提供基于h e r m i t e 细 分曲面算法的交互设计模块，以对h e r m i t e 细分算法展开进一步的研 究。 1 . 5 本论文的内容安排 本论文首先介绍了细分曲 面造型方法的基本概念、 细分模式的特 点，并对细分曲面算法按不同标准进行了分类，然后在此基础上引出 了h e r m i t e 细分算法。 h e r m i t e 细分曲面算法是一种基于h e r m i t e 型的六边形细分算法， 它结合了逼近性细分算法和插值型细分算法的优点， 在第三章介绍了 h e r m i t e 细分曲面算法的定义和分类，并详细介绍了6 - 3 对偶型和3 - 6 对偶型两种 h e r m i t e 细分曲 面， 然后对h e r m i t 。 细分算法的光滑性进 行了 分 析， 并同 逼 近 型 的l o o p 算 法 15 1 3 0 1和 插 值 型 的 改 进 的 蝶 型 细 分 算法( m o d i f ie d b u tt e r fl y ) 7 1 3 1 !进 行了比 较. 本文在第四章详细介绍了一种有效的数据结构一一有序邻接表 ( o r d e r e d a d j a c e n c y l i s t , o a l ) 。 开始给出了 有序邻接表的定 义和结 构， 然后介绍了 一种实现有序邻接表的位置排序算法，并说明了 如何 利用这种排序算法快速稳定地建立有序邻接表。后面介绍了如何利用 有序邻接表这种数据结构实现h e r m i t e 细分曲 面算法。 在第五章给出了基于h e r m i t e 细分曲面算法的交互设计模块。在 这一章的开始对交互设计进行了简单介绍，然后介绍如何在v c环境 下进行o p e n g l 环境配置， 和如何对o p e n g l 进行初始化。 在交互设 计模块部分先介绍了几种基本交互功能，然后介绍了如何实现对象的 选择和拾取，以及利用h e r m i t e 算法对生成曲面进行局部修改。 北方交通大学硕士学位论文 第二章细分曲 面的概念与原理 在本章开始全面地分析细分方法中的理论和应用技术问题， 并介 绍了计算机图形学以及细分方法中的几个常用概念与术语。为了便于 后续各章的叙述，本章先给出网格的形式化表示和细分曲面的形式化 定义，然后在 2 . 2 节介绍了细分模式的特点。2 . 3 节按不同标准对细 分曲面造型方法的进行了简单的分类，并在此基础上引出了 h e r m i t e 细分曲面算法。 怪 2 . 1 网格表示和细分曲面定义 细分曲面是多边形网格的极限状态， 在实现时也只能把它当作某 一细分层次的多面体来处理。也就是说，细分方法处理的对象就是多 边形网格， 因此有必要对多边形网格的有关概念作较为形式化的处理。 ; 2 . 1 . 1 广义单纯复形 粗略地讲，多边形网格就是一个多面体的表面，是由顶点 ( v e r te x ) 、 边 ( e d g e ) 和面( f a c e ) 构 成的 一个 集 合。 如 果 忽略网 格 顶点的几何位置信息， 只考虑网格的拓扑关系，那么得到一种抽象的 多边形网格，称之为广义单纯复形 g e n e r a li z e d s im p li c i a l c o m p l e x e s ) 。 对于给定集合v记v .v = ( i , j ) : v i , j 6 v ) ， 参考 z o r i n d . 关于 抽象单纯复形的 概念2 9 给出 如下广义单纯复形的 定义: 定义 2 . 1广义单纯复形是满足条件 ( 1 ) 一 ( 6 ) 的集合三元组 k = ( v , e , f ) ， 这里v cz ( z是整数 集合)的 元素称为顶点; e二 ( i , j ) e v.v 的 元素 称为 边;f为 顶点 组成的多元组集合: f 二 u ivk 1 3 ( v v .。v ) 其中， v】 表示顶点 个数， f的 元素 称为 面。 规定相对顺序 相同 北方交通大学硕士学位论文 的 顶 点 多 元 组 表 示 同 一 条 边 或 面 ( i , 2 i 0 ) = ( 1 2 ， 二 ， 11 , 1 1 ) 等 等。 如 ( i , j ) = ( j , i ) ( 1 ) 每 个面中 的 所有 边 都 属 于e ; iv ( il 几, . , i k ) e f, ( i, , z(1 m o d k )+ i ) e ( 1 j ) 二 e; ( 4 ) 一条边最多属于两个面; ( 5 ) 对于以i e v 为 端点 的 任意 两 条 边e , ,几 点的 多 边 形面 序列关二， 人， 使 得e , 、 ，一定存在一个以i 为顶 e 2 分 别为多边形面石和 人的 边 ， 且.f r .f l+ l ( 1 =二 ， k 一 1 ) 共 有一 条 边。 九=l， ( 6 ) 两个面最多共有一条边 .骨 图 2 . 1上面的图都不是合格的广义单纯复形。从左到右分别不满足条件( 2 ) , ( 3 ) . ( 4 ) , ( 5 ) . ( 6 ) e 定义2 . 2如果广义单纯复形的一条边只属于一个面，称这条边为边界 边 ( b o u n d a ry e d g e ) ; 如果 一 个顶点 属于边界 边则 称此顶点为边界点 或边 界 顶点( b o u n d a ry v e r te x ) : 至少 包 含一 个 边界 顶点 的面， 称 为 边 界面( b o u n d a r y f a c e ) 。 非 边界的 边、 顶点 和面分别 称为内 部边( i n t e r n a l e d g e ) 、内 部点或内 部顶点( i n t e rn a l v e r t e x ) 和内 部面( i n t e r n a l f a c e ) , 本文主要用到三角形和四边形面的网格，这里也先对四边形和三 角形广义单纯复形给予形式定义 定义2 . 3 对于 单纯 复 形k= ( v , e , f ) 如果f中的 所有面都 是 三角 形，则k为三角单纯复形;如果所有面都是四边形，则称k为四边 形单纯复形。 北方交通大学硕士学位论文 2 . 1 . 2 邻接关系 本小节描述顶点、边和面之间的邻接关系，记单纯复形为 k= ( v , e , f ) 定义2 . 4 对于顶点i e v , 如果 存 在j e v， 使得e = ( i , 力e e， 称 e 为 顶点i 的 邻边， j 称为 顶点i 的 相邻顶点， j 和i 称为e 的 端点。顶 点i 的邻边数，称为i 的价( v a l e n c e ) ， 记为 i l l 。如果存在顶点 i i , . . . , i k _ 1 e v， 使 得f = ( , i i . . . , i k _ 1 ) e f， 称厂 为 顶点i 的 邻面 ， 顶 点i 的 邻面 个数 记为 i if 。 图2 . 2 给出了定义2 . 4 中的图 例说明。 印 图 2 . 2 ( b ) 中 心顶点 ( a )中实心顶点i s 的 价v a l e n c e ( i , ) 二 i a i f = 6 ， 所以顶点i ， 为内 部点; 空心顶点ib 的 价v a le n c e ( i b ) = 6 ， 而 i. 1 f 二 5 , v a l e n c e ( ib ) 9 -0 i i , i f , 因 此空 i 6 为边界点。 定义 2 . 5由 所有边界顶点构成的多边形称为边界多边形( b o u n d a r y p o l y g o n ) ，由所有边界顶点及其相邻内 部边、 边界面、边界边所组成 的形状称为轮廓( s k i rt ) 。 2 . 1 . 3 多边形网格 前面只给出了网格拓扑即单纯复形的基本概念，并没有涉及顶点 在空间中的几何位置。下面给出三维空间中多边形网格的定义: 定义2 . 6 m 二 ( k, (d ) 称为 多 边 形网 格( 简 称为网 格) ， 其中k为 单纯 北方交通大学硕士学位论文 复 形 ，中: v - r 3 是顶 点 到 三维 空间的 单 射。 如果k为 三角单 纯复 形， 称m 为三角网格; k为四边形单纯复形， 则称m 为四边形网格。 k的顶点、边或面仍分别称为m 的顶点、边或面。两个多边形网格 m, = ( k 0 , ) 和m: 二 ( k , o , ) 称 为 拓扑 同 构 的 ， 当 且 仅当 k ， 和k z 是拓扑同构的。 以 后在不引 起混淆的 情 况下， v i cz v也 称中 ( 0 为m的 ( 带位置 坐 标的) 顶点 并 且用 黑 体 字 母( 加 下 标表 示 ) ， 如v , u , v 3 , u ;j 均 可 用来表示网格m的 ( 带位置坐标的)顶点。 定 义2 . 7已 知单纯 复 形k= ( v , e , f ) 和网 格m= ( k, ( d ) , i 二 yo 如果m是三角网格，i 为内部顶点且价不等于6或i 为边界顶点且价 不等于4 或2 ， 则称i 为奇异点 ( e x t r a o r d in a ry v e rt e x ) ， 否则称为正规 点( r e g u l a r v e r t e x ) 。 如果m是四 边形网 格，i 为内 部 顶点且价不 等于 4 或i 为边界顶点且价不等于 3 或 2 ，则称i 为奇异点，否则称为正规 点( r e g u l a r v e r t e x ) 。 不存在奇异点的网格称为正则网格( r e g u l a r m e s h ) 或称为规则网格。 2 . 1 . 4 细分模式 有了关于网格的定义，现在可以 考虑多边形网格上的细分模式。 一般地，细分模式的每次细分可分解成两步操作。首先，通过增加新 顶点 形成新的网 格拓扑， 称为网 格分裂( s p l i tt i n g ) ， 所用的 方法 称为 拓 扑规则( t o p o l o g i c a l r u l e s ) ， 分裂操作可在在单纯复形上进行;其次， 计算所有顶点的 位置， 这一过 程称为 平均( a v e r a g i n g ) ，相应的 方 法称 为几何规则( g e o m e tr i c r u l e s ) o 典型的分裂方法有两种:顶点分裂和面分裂。在常用的细分模式 中， 给 定 顶点i ， 点 分 裂 是 把 顶 点i 分 裂 成 i 1; 个 新 顶 点 ， 每 个 顶点 与 其中一个邻面对应，如果i 为内部顶点则把这些复制顶点依次相连形 成 一 个 i 1; 边 形， 称 此 i 1; 边 形 称 为 新网 格的v 一 面。 对 于内 部 边( i , 力， 一 定 有两 个 相邻面( 记 为厂和人) ， 假 设i , j 分 裂的 与关和人相对 应的 北方交通大学硕_ 上学位论文 复形，q ：v f r 3 是顶点到三维空间的单射。如果k 为三角单纯复 形，称m 为三角网格：k 为四边形单纯复形，则称m 为四边形网格。 k 的顶点、边或面仍分别称为m 的顶点、边或面。两个多边形网格 m = ( k 。，中) 和m = ( k 。，m 。) 称为拓扑同构的，当且仅当k ，和k ： 是拓扑同构的。 以后在不引起混淆的情况下，v f v 也称巾( f ) 为肘的( 带位置 坐标的) 顶点并且用黑体字母( 加下标表示) ，如v ，i i ，v 3 ，u i j 均可 用来表示网格肘的( 带位置坐标的) 顶点。 定义2 7 已知单纯复形k = ( y ，e ，f ) 和网格m = ( 彤，) ，f v 。 如果m 是三角网格，f 为内部顶点且价不等于6 或f 为边界顶点且价 不等于4 或2 ，则称i 为奇异点( e x t r a o r d i n a r yv e r t e x ) ，否则称为正规 点( r e g u l a r v e r t e x ) 。如果艇是四边形网格，i 为内部顶点且价不等于 4 或f 为边界顶点且价不等于3 或2 ，则称i 为奇异点，否则称为正规 点( r e g u l a rv e r t e x ) 。不存在奇异点的网格称为正则网格( r e g u l a rm e s h ) 或称为规则网格。 2 1 4 细分模式 有了关于网格的定义，现在可以考虑多边形网格上的细分模式。 一般地，细分模式的每次细分可分解成两步操作。首先，通过增加新 顶点形成新的网格拓扑，称为网格分裂( s p l i t t i n g ) ，所用的方法称为拓 扑规则( t o p o l o g i c a lr u l e s ) ，分裂操作可在在单纯复形上进行；其次， 计算所有顶点的位置，这一过程称为平均( a v e r a g i n g ) ，相应的方法称 为几何规则( g e o m e t r i cr u l e s ) 。 典型的分裂方法有两种：顶点分裂和面分裂。在常用的细分模式 中，给定顶点f 。点分裂是把顶点f 分裂成i f l ，个新顶点，每个顶点与 其中一个邻面对应，如果i 为内部顶点则把这些复制顶点依次相连形 成一个，边形，称此。边形称为新网格的v 一面。对于内部边( f ，) ， 一定有两个相邻面( 记为f 和疋) ，假设i ，分裂的与，：和相对应的 北方交通大学硕上学位论文 顶点分别为，i ：和一，j ，那么连接，i 2 ，j ：和_ 形成的四边形面， 称为新网格的e - 面。旧网格多边形面f 的每个顶点都分裂出一个顶点 与之对应r 把这些分裂出来的新顶点依原来的顺序相连得到一个与 边数相同的面，称为f 一面。图2 3 为点分裂示意图。 图2 3 左图：原始网格：右图：顶点f 分裂为三个顶点( 空心圆) ，j 分裂成两 个顶点( 空心正方形) 。虚线网格为分裂得到的新网格。 面分裂是在网格边和面上插入适当的新顶点，然后对每个面进行 剖分，从而得到新网格。如果不对分裂作任何限制，情况可能相当复杂。 这里针对三角网格和四边形网格给出几种以后用到的面分裂形式。 ( 1 ) 1 4 三角形分裂： 在三角网格的每条边上插入一个新顶点，称为边点( e 顶点) 或 奇顶点( o d dv e r t e x ) 。然后把每个三角形面的三条边的e 顶点两两相 连，从而把该三角形面分裂成四个小三角形面，如图2 4 所示。原网格 的顶点则称为顶点点( v - 顶点) 或偶顶点( e v e nv e r t e x ，e 一顶点) 。 北方交通大学硕士学位论史 图2 4 左为初始网格右为l 一4 分裂网格。填充区域为一个三角形面分裂的情 况，右图标有小正方形和小圆的顶点为别是v - 顶点和e 点。 ( 2 ) 1 4 四边形分裂： 思想与( 1 ) 类似，只是这里把一个四边形面分裂成4 个四边形面。 因此除边点外还要在面的中心插入一个新顶点，称之为面顶点( f 一顶 点) ，e 一顶点和v _ 顶点定义同( 1 ) ，如图2 5 为四边形网格的1 4 分裂 示意图。 图2 5 左为初始网格，右为1 4 分裂网格。填充区域为一个四边形面分裂的情 况；标有小三角形、小正方形和小圆的顶点分别是v - 顶点、e 项点和f 顶点。 设从给定网格m o = ( k o ，西o ) 开始，不断作用分裂和平均算子得 到网格m “1 = ( kk - | 巾) 。现在来看利用分裂和平均算子从网格 m 卜。季导到新网格 彳的具体过程。用上述某种分裂算子( 记为s ) 作 用于单纯复形世= ( 矿k - ie k - if h ) 得到k = ( 矿，e k , f ) ，即 北方交通大学硕士学位论文 世= s k 2 。现在需要确定。，从而得到新网格m = ( k 。，) 。 我们希望新顶点是由旧顶点计算得到，假设网格m ”。共有m 个顶 点，顶点标号依次为l ，m h 。一般地，对新顶点f v 。定义函数 a ? ：( r 3 ) “。1 - - - r3 ( r 是实数域) ： 掣( k - 1 ( 1 ) ，“1m k - i ) ) ， 以此作为新顶点i v 。的位置，即 。( f ) = 4 ( m 扛1 ( 1 ) ，m k - i ( 聊k - i ) ) ( 2 1 ) 称彳：为平均算子。特别地，如果爿j 是关于顶点 中“。( 1 ) ，“1 ( 川。) 的线性函数，h 即存在系数日：( ，= 1 ，m ) ， 使得爿：( k - i ( 1 ) ，扣1 ( 掰k - i ) ) = 艺口：“( ) ， ( 2 2 ) 则称4 j 为线性平均算子。下面给出绗分模式的定义。 定义2 ，8 从给定网格m o = ( k 0 o ) 出发，对露= 1 , 2 ，依次采用某 种分裂算子s 和平均算子一? 作用于m 扛1 = ( k ，c i ) 扛1 ) 并重复此 操作从而得到三角网格序列吖”，m 1 ，m 。，这一过程称为细分 模式( s u b d i v i s i o ns c h e m e ) 。网格序列的极限 盯= l i m m “ t 斗0 d 称为细分曲面( s u b d i v i s i o ns u r f a c e s ) ，有时细分曲面称为极限曲面。 称m 8 ( 后 o ) 为细分曲面的控制网格，有时为了区分把