（计算机应用技术专业论文）基于曲面细分的多分辨率模型表示方法的研究与实现.pdf

北京交通大学硕士学位论文 摘要 细分曲面造型技术是近年来计算机图形学的研究的热点课题，细 分方法的各种优点使其具有广阔的应用前景。 在l e e 等人的论文 “ m u lt i r e s o l u t i o n a d a p t i v e p a r a m e t e r i z a t i o n o f s u r f a c e s ”中，提出了一种ma p s应用框架，将细分方法应用于多分 辨率模型表示与分析。 ma p s应用框架的执行过程大致可分为网格简化与曲面重建两个 步骤。首先通过采用某种网格简化算法，将输入的初始密集网格简化 成一个粗网格，并建立起从粗网格到初始网格的保形映射，这个粗网 格被称为基域网格。然后，对基域网格进行细分，并使用映射关系确 定新插入顶点的位置，这实际上是一个曲面重建的过程，得到是一个 具有细分拓扑结构的参数化模型，并且可以根据需要建立起不同分辨 率的网格模型。参数化的多分辨率模型具有很多优点，比如说可以 根 据不同计算能力的需要进行网格压缩，并且可以方便的对模型进行自 适应编辑，以及对模型应用许多相关领域的研究方法，如小波分析等 i 本文首先介绍了曲面细分技术，重点分析了几种经典细分算法， 并给出了具体的数据结构和实现过程，特别是三角网格细分的实现过 程。然后介绍了曲面简化算法，主要包括各类简化算法的特点，并重 点分析了简化误差的控制问 题。 接着对ma p s 框架中涉及到的技术进 行了详细的分析，设计了 具体的数据结构和实现算法，最后给出了实 验结果。 关键字:细分曲面、网格简化、多分辨率模型表示、细节层次模型 北京交通大学硕士学位论文 ab s t r a c t i n r e c e n t y e a r s , s u b d i v i s i o n s u r f a c e t e c h n o l o g y h a s b e c o m e a h o t s p o t i n t h e r e s e a r c h i n g f i e l d o f c o m p u t e r g r a p h i c s . a n d s u b d i v it i o n s u r f a c e t e c h n o l o g y h a s a v e r y b r o a d p e r s p e c t i v e b e c a u s e o f i t s m a n y a d v a n t a g e s i n l e e s p a p e r m u lt i r e s o l u t i o n a d a p t i v e p a r a m e t e r i z a t i o n o f s u r f a c e s , a n e w a p p l i c a t io n f r a m e w o r k c a l l e d ma p s w a s p r o p o s e d t o a p p l y s u b d i v i s i o n t e c h n o l o g y i n t o t h e p r e s e n t a t i o n a n d a n a l y s i s o f mu l t i r e s o l u t i o n s u r f a c e s . b a s i c a l l y , t h e p r o c e s s o f ma p s f r a m e w o r k c o u l d b e d i v i d e d i n t o t w o s t e p s : m e s h s i m p l i f i c a t i o n a n d s u r f a c e r e s a m p l e . f i r s t , b y i m p l e m e n t in g a m e s h s i m p l i f i c a t i o n m e t h o d , m a p s s i m p l i f y a n i n p u t d e n s e m e s h i n t o a c o a r s e m e s h , a n d s y n c h r o n o u s l y c o n s t r u c t t h e p a r a m e t e r i s a t i o n i n f o r m a t i o n m a p p i n g e a c h r e m o v e d v e rt e x fr o m t h e i n i t i a l d e n s e m e s h t o t h e s i m p l i fi e d c o a r s e m e s h . a n d t h e s i m p l i f i e d c o a r s e m e s h i s c a l l e d b a s e d o ma i n . s e c o n d , ma p s s u b d i v i d e t h e b a s e d o m a i n u s i n g a c e r t a i n s u b d i v i s i o n s c h e me . d u r i n g t h e s u b d i v i s i o n p r o c e s s , t h e p a r a me t e r i s a t i o n i n f o r m a t i o n i s u s e d t o c a l c u l a t e t h e p o s i t i o n o f t h e n e w i n s e r t e d v e rt e x . a c t u a l l y , t h e s u b d i v i s i o n p r o c e s s re c o n s t r u c t t h e i n p u t me s h a n d c h a n g e i t i n t o a s e r i e s o f m u l t i r e s o l u t i o n p a r a m e t e r i z e d m e s h w i t h s u b d i v i s i o n t o p l o g y . i n t h i s p a p e r , s u b d i v i s i o n s u r f a c e t e c h n o l o g y i s p r e s e n t e d , e s p e c a i l l y d e s c r i b e s e v e r a l c l a s s i c a l s u b d i v i s i o n s c h e m e s a n d t h e i m p l e m e n t a t i o n o f s o m e c e rt a i n s c h e m e s . n e x t , m e s h s i m p l i f i c a t i o n m e t h o d i s d e s c r i b e d a n d t h e e r r o r c o n t r o l p r o b l e m in t h e s i m p l i f a t i o n i s a n a l y z e d . i n t h e f o l l o w i n g p a r t o f t h e p a p e r , a l g o r i t h m s e m p l o y e d i n ma p s a r e a n a l y z e d , a n d p r o v i d e t h e d e s i g n o f c o n c r e t e d a t a s t r u c t u r e a n d i m p l e m e n t a t i o n o f ma p s . t h e l a s t s e c t o r o f t h e p a p e r s h o w s t h e re s u l t o f i m p l e m e n t a i o n . k e y w o r d s : s u b d i v i s i o n s u r f a c e s , m e s h s i m p l i f i c a t i o n , m u l t i re s o l u t i o n 北京交通大学硕士研究生毕业论文 第一章绪言 1 1 背景 曲面造型是计算机辅助几何设计和计算机图形学的一项重要内 容，主要研究在计算机图象系统的环境下对曲面的表示、设计、显示 和分析。它起源于汽车、飞机、船舶、叶轮等的外形放样工艺，由c o o n s 、 b e z i e r 等大师于二十世纪六十年代奠定其理论基础。如今经过三十多 年的发展，曲面造型现在已形成了以有理b 样条曲面参数化特征设计 和隐式代数曲面表示这两类方法为主体，以插值( i n t e r p o l a t i o n ) 、拟合 ( f i t t i n g ) 、逼近( a p p r 0 x i m a t i o n ) 这三种手段为骨架的几何理论体系。 n u r b s 尽管早已被国际标准化组织作为定义工业产品数据交换 的s t e p 标准，在工业造型和动画制作中得到了广泛的应用，但仍然 存在着一些固有的缺陷。单一的n u r b s 曲面和其他参数曲面一样， 仅限于表示在拓扑上等价于一张纸、一个圆柱面或一张圆环面的曲面， 较难表示如人的头、手、自然花卉等复杂的任意拓扑结构的曲面。如 果使用补片的形式来实现复杂光滑曲面的构造，则又带来了n u r b s 的修剪和拼接缝合问题。这种修剪和拼接的计算代价是非常高昂的， 而且存在数值误差，要在曲面的接缝处保持光滑，即使是近似的光滑 也是很困难的。如果模型是活动的，那么情况更是如此。 由于传统参数曲面表示法无法处理一般拓扑控制网格，一种由离 散到离散的细分造型方法就应运而生了。细分造型方法由于其计算量 小、算法简单、响应速度高等优点，已经广泛应用于虚拟现实、计算 机动画、计算机辅助几何设计和科学计算可视化等领域，具有广阔的 应用前景。从表示方法来看，以网格细分( s u b d i v i s i o n ) 为特征的离散造 型与传统的连续造型相比，大有后来居上的创新之势。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增 强，随着几何设计对象向着多样性、特殊性和拓扑结构复杂性靠拢的 趋势的曰益明显，随着图形工业和制造工业迈向一体化、集成化和网 络化步伐的日益加快，随着激光测距扫描等三维数据采样技术和硬件 设备的日益完善，曲面造型在近几年来得到了长足的发展。这主要表 现在研究领域的急剧扩展和表示方法的开拓创新。从研究领域来看， 曲面造型技术已从传统的研究曲面表示、曲面求交和曲面拼接，扩充 到曲面变形、曲面重建、曲面简化、曲面转换和曲面位差。而其中的 曲面重建与简化是c a d c a m 等技术在发展过程中向曲面造型研究提 北京交通大学硕士学位论文 出的新课题。 在计算机图形学和曲面造型中，曲面常用多边形网格模型，尤其 是三角网格模型描述。随着图像获取设备、计算机视觉三维数据获取 设备的不断完善，网格模型已成为计算机图形学三维实体的重要表示 方法。 曲面重建要为已存在的曲面建立模型，也就是根据已有的曲面去 构造反映其形状的数学模型。曲面重建需要采集大量的数据，建成的 模型一般都很复杂。如一个飞机模型( 如图1 1 所示) 的重建，采集 7 6 0 2 个点的坐标数据，利用一种曲面熏建的方法得到的模型中就包含 有1 3 ，5 4 6 个三角形片。这样大量的数据给图形的训算机分析、实时显 示及数据的存储与传输都带来了麻烦和困难。为此，需要对重建得到 的复杂的数学模型进行简化，以减少数据量，减少数据模型的复杂程 度。 曲面简化正是解决这个问题的，它是从三维重建所得到的离散曲 面或造型软件所输出的三角网格中，在保证必要精度的前提下去除冗 余信息，以利于图形显示的实时性，数据存储的经济性和数据传输的 快速性。 对于多分辨率曲面模型而言，可以使用曲面简化方法来建立曲面 的细节层次( l o d ) 模型，进行曲面的分层显示、传输和编辑。如图 1 1 ( b ) 所示，经过一步简化之后飞机模型的面片就由原来的1 3 ，5 4 6 个 减少到1 0 0 0 个，图1 1 ( c ) 中模型简化到了只有1 5 0 个面片，这样就大 大地节省了存储的空间和处理的时间。 a 初始网格1 3 5 4 6 个面片b 1 0 0 0 个面片c 1 5 0 个面片 图1 1 飞机三维模型及其简化 2 北京交通大学硕士学位论 文 1 . 2细分曲 面研究及应用现状 近年来，细分曲面造型方法的研究及应用己成为 c a g d领域的研 究热点之一，一些世界顶尖的大学和研究机构都在细分曲面领域开展 了大量的工作。在计算机图形学最权威的学术年会 s i g g r a p h上， 报告了大量关于此方面的研究成果。 加州理工学院的s c h r o d e r、 纽约 大学的z o r i n、 微软研究院的h o p p e 以 及他们各自 的研究组在曲 面细 分算法和基于细分算法的应用等方面取得了令人瞩目的成果。例如， 微软研究院的h o p p e 在1 9 %年提出的渐进网 格算法已 被许多三维图 形算法所借鉴，并且已应用于微软的三维图形库d i r e c t x 8中。著名 的计算机图形学家 t .d e r o s e利用基于细分思想的曲面简化技术制作 了动画片 “ g e r i s g a m e ，并荣获1 9 9 8 年奥斯卡最佳片断奖。 2 0 0 0 年， l e e 等人提出了一种参数化细分曲面应用框架， 即ma p s ( m u lt i r e s o l u t i o n a d a p ti v e p a r a m e t e r i z a t i o n o f s u r f a c e s ) 算法 . m a p s 实际上是一种构造参数化多分辨率曲面的方法，ma p s算法首先使用 某种曲面简化算法简化初始密集模型，然后基于曲面细分技术重建参 数化模型，得到了一个具有细分拓扑结构的参数化模型，可方便的用 于三维模型的实时渲染、传输、存储及自 适应编辑等应用。 1 . 3本文的主要内容及意义 ma p s可以被看作是曲 面细分技术的一种具体应用，与传统多分 辨率表示方法相比具有很多优点。因此本文首先介绍了曲面细分的有 关概念、 算法及实现，然后介绍了m a p s中涉及的另一项重要技术一 网格简化，对相关的网格简化技术进行了重点分析。从第四章开始， 重点分析了ma p s 算法， 并介绍了设计实现过程， 在第五章中给出了 相应的实验结果。 本文对ma p s 算法中涉及到的各种技术及实现过程进行了详细的 阐述和分析，主要包括网格简化算法和网格细分算法及参数化模型的 构造过程，并给出了具体的实验结果。 北京交通大学硕士学位论文 第二章曲面细分技术 2 1 细分曲面造型方法概述 1 细分曲面造型方法产生的背景 当前，曲面生成方法主要基于闭式数学表达式( 如b 6 z i e r 曲线， 样条方法) ，但是这类方法能够生成的曲面类型受到限制。近年来，一 类新的曲面生成方法流行开来。这类方法使用一个多边形网格或一系 列网格来表示曲面。通过这种方法，不仅可以生成各种闭式数学表达 式曲面，还可以生成任意拓扑类型的曲面。这类方法背后的思想主要 起源于均匀b 样条曲线曲面的二元细分思想，因此由这类方法表示的 曲面，被统称为细分曲面。通常，细分曲面被表示为一个初始的多边 形网格和某种细分操作。对于给定的初始多边形网格，细分操作能够 增加网格中的多边形数目，使之趋向于光滑。通过对网格进行多次细 分操作，就产生一组可收敛于理想光滑曲面的网格序列。 2 细分曲面的概念 细分曲面是用多边形网格或网格序列来描述曲面的。在计算机图 形学和曲面造型中，曲面常用多边形网格模型，尤其是三角网格模型 描述。随着图像获取设备、计算机视觉三维数据获取设备的不断完善， 网格模型已成为计算机图形学三维实体的重要表示方法。 图2 1 一个细分曲面的例子 4 北京交通大学硕士学位论文 通常，给定一个初始多边形网 格，利用某种细分操作不断增加初 始网格的顶点和面片，这样使得初始网格不断细化，逐渐的接近所期 望的目标曲面。并且在细分过程中，可以得到一个趋近于目标曲面的 网格序列。实际上，细分曲面就是这个不断细化的网格序列的极限情 况 。 图2 . 1 中给出了一个细分曲面的例子。 最左边是一个初始三角形网 格表示的头像模型，按照一定的细分方案，网格中的每个三角形被分 成四个小三角形 ( 如中间的头像模型)。同样，在中间的模型网格上 再执行一次细分操作，则得到了图中最右边的模型。可以看出，这三 个模型实际上构成了一个逐渐趋近于光滑曲面的网格序列。 在实际应用中，对初始网格执行几次这样的细分操作之后，就可 以得到一个较为理想的光滑曲面，其光滑程度己可以满足人的肉眼及 计算机显示器或激光打印机能够达到的分辨能力。 3 .细分曲面的优点 细分曲面造型方法是一种由离散到离散的细分造型方法， 由于其 计算量小、 算法简单、 响应速度高等优点， 己 经广泛应用于虚拟现实、 计算机动画、计算机辅助几何设计和科学计算可视化等领域，具有广 阔的应用前景。从表示方法来看，以网格细分为特征的离散造型与传 统的连续造型相比，大有后来居上的创新之势。 2 .2细分曲 面造型方法的发展概况及分类 细分思想实际上可以追溯到上世纪4 0 年代末和 5 0年代初的 “ 砍 角” 算法， d e r h a m提出“ 砍角” 算法来生成光滑曲线。1 9 7 8 年发表 的d o o - s a b i n 算法和c a t m u l l - c l a r k 算法是最早的曲 面细分算法。 然而， 1 9 7 8年至 1 9 9 5年之间曲面细分领域几乎没有什么进展， 直到 1 9 9 5 年r e i f 解决了细分曲面奇异点的问 题之后， 曲面细分算法才又迅速的 发展起来。 1 .细分方法的分类标准0 2 1 细分规则的类型:面分裂或点分裂 曲 面网格的类型:三角形或四边形 细分方法是逼近还是插值 能 够产生的 极限曲 面的 光滑度: c l , c z . . 北京交通大学硕士学位论文 2 .下表列出了 对当前几种主流细分方法的分类 1 2 1 表 2 - 1 面分裂 三角形网格四边形网格 逼近型 l o o p ( c )c a t m u l l - c l a r k ( c ) 插值型 m o d i f i e d b u tt e r f l y ( c )k o b b e l t ( c ) 表 2 - 2 点分裂 do o - s a b i n m i d e d g e ( c ) b i q u a r t i c ( c ) 2 .3几种最著名的细分造型方法 如果初始网格是四边形网格， 那么其细分过程实际上是均匀b样 条曲面的二元细分方法的推广。因此，这里我们首先了解一下均匀 b 样条的细分，然后研究它如何推广到非四边形网格的情况。这类算法 属于一类 “ 砍角”算法，也就是说，细分的操作可被看作是切掉多边 形网格的 “ 尖角” ，以达到使网格趋于光滑的目的。二次 b样条曲面 细分方案经推广得到了d o o - s a b i n 细分方案，三次 b样条曲面细分方 案经推广就得到了c a t m u l l - c l a r k 方案.而基于三角形网格的l o o p 细 分方案则是由三角样条曲面细分推广得到的。 2 . 3 . 1 d o o - s a b i n细分方案， ， b样条曲线的细分是通过对d e b o o : 控制多边形不断插入节点， 当 插入的节点足够稠密时得到的d e b o o r 控制多边形便收敛于控制多边 形所包含的b样条曲线， 而这里使用的节点插入算法又是关于b e z i e r 曲线的d e c a s t e lj a u算法的 推 广。 b样条张量积曲 面的细分由b样条曲线的细分推广而来。通过细 化 d e b o o r 控制网格， 使之更好的逼近控制网格所包含的曲面。 但是， b样条张量积曲面的细分规则对网格的拓扑结构有严格的限制，要求 网格中的每个顶点必须是4 阶， 即每个顶点都是四条边的端点。 这样， 北京交通大学硕士学位论文 2 下表列出了对当前几种主流细分方法的分类 表2 1 面分裂 三角形网格f四边形网格 逼近型c a t m u l l c l a r kf c i 】fk o b b e l t ( c j )插值型lm o d i f i e d b 2 3 几种最著名的细分造型方法 如果初始网格是四边形网格，那么其细分过程实际上是均匀b 样 条曲面的二元细分方法的推广。因此，这里我们首先了解一下均匀b 样条的细分，然后研究它如何推广到非四边形网格的情况。这类算法 属于一类“砍角”算法，也就是说，细分的操作可被看作是切掉多边 形网格的“尖角”，以达到使网格趋于光滑的目的。二次b 样条曲面 细分方案经推广得到了d o o s a b i n 细分方案，三次b 样条曲面细分方 案经推广就得到了c a t m u l l c l a r k 方案。而基于三角形网格的l o o p 细 分方案则是由三角样条曲面细分推广得到的。 2 3 1d o o s a b i n 细分方案“3 b 样条曲线的细分是通过对d eb o o r 控制多边形不断插入节点，当 插入的节点足够稠密时得到的d eb o o r 控制多边形便收敛于控制多边 形所包含的b 样条曲线，而这里使用的节点插入算法又是关于b e z i e r 曲线的d ec a s t e l j a u 算法的推广。 b 样条张量积曲面的细分由b 样条曲线的细分推广而来。通过细 化d eb o o r 控制网格，使之更好的逼近控制网格所包含的曲面。但是， b 样条张量积曲面的细分规则对网格的拓扑结构有严格的限制，要求 网格中的每个顶点必须是4 阶，即每个顶点都是四条边的端点。这样， 6 北京交通大学硕士学位论文 细分规则适用的网格只能是矩形网格。这样的限制给曲面设计带来了 很大的困难，因为封闭的曲面网格很少是具有矩形拓扑结构的。 1 9 7 8 年，d a n i e ld o o 和m a l c o l ms a b i n 给出了一种算法消除了上 述限制，从而将双二次均匀b 样条细分规则推广到任意拓扑结构的曲 面网格。d o o 。s a b i n 算法能够由任意控制网格生成光滑曲面。 由于细分的过程实际上是在初始网格上不断增加新的顶点，逐渐 细化初始网格，使之趋近于光滑曲面。因此细分规则就是要定义如何 根据已有网格计算出新的顶点。 在双二次均匀b 样条曲面细分算法中，每次细分需为每个面计算 面控制点( f a c ep o i n t ) ，然后，各面控制点构成新的控制网格。这里 用缩分模版来表示面控制点的计算规则。7 双二次均匀b 样条曲面的细 分模版如图2 1 所示： g 一3 s i i 一33 一g ， l l l i i i il 麝3 10 3 3 一口 1 3 图2 i 双二次均匀b 样条曲面的细分模版由已知四个顶点计算四个面点 d o o s a b i n 发现新顶点只是多边形上四个特定点的加权平均值：对 应的原顶点、原顶点的两个邻边上的边点( 该边两端点的均值) 、对应 的面点( 该面上所有顶点的均值) 。如图2 3 所示： 图2 3 新顶点的计算方法示意图 7 北京交通大学硕士学位论文 从而，均匀b 样条曲面的情况是很简单的，只要对于每个面计算 出这些新顶点即可。新顶点组成了一个四边形网格，新产生的面都有 四个顶点。然后，可以使用同样的规则对这些面继续进行细分。任意 拓扑结构网格的d o o s a b i n 细分过程： 1 ) 各个面上的每个顶点p j ，生成一个新顶点q j ，其值是p ，与两个相 邻边点及面点的平均值。 图2 4 插入新顶点后的网格示意图 2 ) 对于原有各个面，将其新生成的各项点联结起来。 图2 4 连接新顶点 3 ) 对于原有各项点，将与其相邻的各面上的面点联结起来。 北京变通大学硕士学位论文 图2 5 连接新顶点 4 ) 对于原有各边，将与其相邻的两面上的面点联结起来。 将新顶点连接后，就得到了一个新网格，作为下一步细分的初始 网格。 d o o s a b i n 发现，通过上述计算规则得到的面控制点实际上是该面 片各顶点与该面片质心连线的中点。这样，如图2 6 所示，将双二次 均匀b 样条曲面的细分规则推广到任意拓扑结构网格曲面时，计算面 控制点只是求面片各项点与该面片质心连线的中点。而面片的质心可 以简单地通过计算面片各项点的平均值得到。 ( a ) 将面点连接成新控制网格( b ) 根据质心和各顶点连线中点计算面点 图2 6 任意拓扑结构网格的d o o 。s a b i n 细分规刚 9 北京交通大学硕士学位论文 由图2 6 f a ) 可以看出，每一次细分，其效果相当于切去原网格的各 个面、边、角，然后得到了新网格。随着细分的进行，细化后控制网 格上的面片实际上大部分都是四边形，只有部分固定数目的顶点周围 存在非四边形面片，这些顶点就称为奇异点，而这些非四边形面片对 应着初始网格的各个顶点和面片。 图2 7 是一个d o o s a b i n 细分的实例。 图2 7d o o s a b i n 细分示例 0 北京交通大学硕士学位论文 从图2 7 中可以看出，经过第一次细分之后，所有的顶点都变成了 4 阶，这是d o o s a b i n 方案的一个重要特点。还可以注意到，在尖角 处出现了三角面片，这是由尖角处阶数为3 的顶点形成的，这些三角 面片会在随后的细分过程中一直存在，并且会收敛于一个“奇异点”。 双二次b 样条曲面的细分过程实际上是在各个面上定义新顶点， 而这些新顶点则只是完全依赖于原顶点，以及与其相关的面点、边点。 这样就很容易的推出针对任意拓扑结构网格的细分规则。另外，除了 一定数目的控制点处，d o o s a b i n 曲面从局部上看是一种双二次b 样 条曲面。 2 3 2c a t m u l 卜c l a r k 细分方案 几乎是与d o o s a b i n 同时，e dc a t m u l l 和j i mc l a r k 提出了另一种 由任意控制网格生成光滑曲面的算法。与d o o s a b i n 方案不同， c a t m u l l c l a r k 方案是由双三次均匀b 样条曲面细分规则推广而来。 在双三次均匀b 样条曲面细分算法中，每次细分对原有网格的每 条边生成一个边控制点，对每个面生成一个面控制点，另外还要对每 个顶点计算其在细分后网格中的位置。然后，连接所有新控制点就得 到细分后的控制网格。因此，需要三种计算新控制点的细分模版，如 图4 所示， 1 6 1 lli b 一3 8 6 lil 1 6 1 4 - - 一4 ll 2 4 2 4 lib 4 一4 4 2 4 4 ll l 4 - - 2 4 - 一4 图2 8 职三次均匀b 样条曲面细分模版 1 6 - 1 b lf 6 1 6 c 使用模版a 可以生成对应于原有网格各顶点的新顶点 使用模版b 可以生成对应于原有网格各边的边控制点 使用模版c 可以生成对应于原有网格各面的面控制点 对细分模版的分析可以发现，同d o o s a b i n 算法类似，计算面控 l l 北京交通大学硕士学位论文 制点( 模版c ) 的结果实际上就是该面的质心，计算边控制点( 模版 b ) 的结果实际上是与该边相邻的两个面质心的平均值。而计算新顶 点( 模版a ) 的结果相对复杂。c a t m u l l c l a r k 发现对应于原有网格中 顶点s 的新顶点 s - = 百1q 肘去s 其中 q ：所有与顶点s 相接的各面质心的平均值 r ：所有与顶点s 相接的各边中点的平均值 后来为了解决一些任意拓扑结构网格中( 如四面体) 奇异点处的 切面连续性问题，将( 1 ) 式修正为 s - = 专q + 号斛等s 其中n 为顶点的阶数 这样，得出上述关于双三次均匀b 样条曲面细分规则的规律后， e dc a t m u l l 和j i mc l a r k 推广了这些细分规则，使之不仅适用于任意四 边形网格，而且适用于其他任意拓扑结构的网格。并且，从双三次均 匀b 样条曲面的光滑性可推知，c a l m u l l c l a r k 曲面在奇异点之外的区 域具有c z 光滑度。 c a t m u l l - c l a r k 细分规则如下： ( 1 ) 对于网格中的每个面，生成一个面点：为面上各顶点的平 均。 ( 2 ) 对于网格中的每条边，生成一个边点：为此边中点与此边 两相邻面上的面点的平均。 ( 3 ) 对于网格终的每个顶点，计算新顶点：即重新计算原有顶 点的位置。 ( 4 ) 细分后按如下方法联结得到新网格：每个面的面点与该面 各边的边点相连。每条边的边点与该边两顶点对应的新顶 点相连。 以下图所示网格为例，说明细分过程。 北京交通大学硕士学位论文 图2 9 初始网格 首先，构造各个面点。如下图所示，各面点f 是通过求各面顶点 的平均值得到的。 么 夕 图2 1 0 插入面点 接着，构造边点。如下图所示，边点e 是通过求四个点的平均得 到的：该边的两个顶点、该边两个相邻面的面点。( 图中，用浅色标记 北京交通大学硕士学位论文 上一步计算中得到的面点1 图2 1 1 插入边点 然后，构造新项点。( 图2 1 1 中，用浅色标记上一步计算中得到的 面点和边点) 图2 ，1 2 构造新顶点 最后，将生成的点联结成网格：首先将各面的面点与该面各边的 边点联结起来。然后把新顶点与相邻的边点联结起来。 北京交通大学硕士学位论文 j 解辆i | | i 哟拶j j j 图2 1 3 连接各点得到新网格 可以看出，无论初始网格是何种拓扑结构，首次细分使网格中的 各面都成为四边形a 下面给出了一个具体的多边形网格模型经过四次 c a t m u l l c l a r k 细分的情况。 图2 1 3 初始模型 北京交通大学硕士学位论文 图2 1 4 一次c a t m u u c l a r k 细分后 可以看出，新生成的控制网格中所有的面都是四边形。而且，与 原控制点对应的新顶点具有与原控制点相同的阶数( 与此点相接的边 数) 。 图2 1 4 两次c a t m u l l c l a r k 细分后 在细分过程中对应于原控制点的顶点阶数保持不变。例如，模型 顶部的阶数为8 的顶点，经过几次细分后，对应的新顶点阶数仍为8 6 北京交通大学硕士学位论文 图2 1 5 三次c a t m u l l - c l a r k 细分后 c a t m u l l c l a r k 已经证明，三次b 样条细分规则可以推广到任意拓 扑结构的网格。通过这种方式生成的曲面，除了有限的一部分顶点周 围区域，大部分局部区域是双三次均匀b 样条曲面片。 2 3 3l o o p 细分方案“1 d o o s a b i n 方案和c a t m u l l c l a r k 方案都是由均匀b 样条张量积曲 面细分推广而来。对于非张量积b 样条曲面，如三角样条曲面( 又称 四次均匀b o x 样条，三方向的b o x 样条) ，c h a r l sl o o p 在1 9 8 7 年推 广了规则的( 顶点均为6 阶) 三角样条曲面的细分方法，给出了适用 于任意拓扑结构三角网格曲面( 顶点阶数未必是6 ) 的细分算法。 ( 1 ) 细分规则 在规则三角样条曲面细分过程中，每次细分需对原有网格中每条 边计算一个边控制点( 图2 1 7 ，模版b ) ，并且对原有网格的每个顶点 计算新顶点( 图2 1 7 ，模版a ) ，然后连接新顶点和边控制点就得到新 的控制网格。同d o o s a b i n 方案和c a t m u l l c l a r k 方案相似，l o o p 首先 归纳出规则三角样条曲面细分模版的几何特征，然后将其推广到任意 北京交通大学硕士学位论文 三角网格的情况。规则三角样条曲面网格的细分模版如图2 1 6 所示。 图21 6 规则三角样条曲面网格的细分模版 a ：边控制点计算模版 b ：新顶点计算模版，= 专( 1 一a 。) 图2 1 7 任意拓扑结构三角网格的细分模版 因为任意拓扑结构的三角网格中的每条边( 边界除外) 都是与两 个三角面相邻，所以模版b 可之间推广到任意拓扑结构的三角网格。 而模版a 的推广则相对复杂。通过对模版a 的分析可以发现，对应于 原有网格中顶点v 的新顶点 1 v 广8 v + 云q ( 3 其中：q 为原网格中与v 共边的所有顶点的平均值。为了解决奇 异点处切平面的连续性问题，将( 3 ) 式修正为： 北京交通大学硕士学位论文 v 1 = 口v + ( 1 一口) q ( 4 ) r3 12 万、23 其中口”。l i + i c o sj fj + i 随着细分一次一次的进行下去，除了奇异点附近区域外，控制网 格成为规则三角网格。而且奇异点的数目是固定的，对应于初始网格 的顶点数目。 2 4 细分曲面的数据结构 在曲面造型中，通常用多边形网格，尤其是使用三角形网格来表 示曲面。多边形网格的数据结构一般是采用项点表和面表的形式，其 中顶点表保存了网格中各顶点的坐标，而面表则保存网格中各多边形 顶点指针。这种表示结构虽然对于许多应用是方便高效的，然而却不 适用于另外一些应用，如曲面细分和曲面简化。 在许多曲面简化方法中，需要将某条边收缩为一个点。这种操作 要求删除包含此边的面并且更新与此边相关的拓扑结构，因而需要获 取网格中点、边和面的邻接关系。对于曲面细分来说，其实质是根据 已有网格的拓扑信息计算新顶点，这个过程需要获得网格中相关顶点、 边和面的邻接拓扑信息。是否能够方便快速的获取这些信息，是影响 细分效率的关键。这类应用中，对于多边形网格邻接信息的要求可归 纳为： q 1 ：获取与某一项点相接的各个面 q 2 ：获取与某一顶点相接的各条边 q 3 ：获取与某条边相接的各个面 q 4 ：获取某个面包含的各条边 q 5 ：获取与某个面相接的各个面 如果采用简单的点面表数据结构，上述操作的效率必然是极低的， 因为要获取某一局部的邻接关系，必须扫描整个网格的点表或面表， 有的甚至要同时扫描点表和面表。 针对上述问题，已有几种较合理的数据结构被提出，如 册 n g e d - e d g e ，h a l f - e d g e ，o a v l 等。本文以下部分将对这几种结构进行 分析比较。 9 北京交通大学硕士学位论文 v i = a n v + ( i 一 a n ) q ( 4 ) 3-00 + 其中 cos 1-4 十 318 厂ree|1又 -一 n 口 随着细分一次一次的进行下去，除了奇异点附近区域外，控制网 格成为规则三角网格。而且奇异点的数目 是固定的，对应于初始网格 的顶点数目。 2 .4细分曲面的数据结构 在曲面造型中，通常用多边形网格，尤其是使用三角形网格来表 示曲面。多边形网格的数据结构一般是采用顶点表和面表的形式，其 中顶点表保存了网 格中各顶点的坐标，而面表则保存网格中各多边形 顶点指针。 这种表示结构虽然对于许多应用是方便高效的，然而却不 适用于另外一些应用，如曲面细分和曲面简化. 在许多曲面简化方法中，需要将某条边收缩为一个点。这种操作 要求删除包含此边的面并且更新与此边相关的拓扑结构，因而需要获 取网格中点、边和面的邻接关系。对于曲 面细分来说，其实质是根据 己有网格的拓扑信息计算新顶点， 这个过程需要获得网格中相关顶点 边和面的邻接拓扑信息。是否能够方便快速的获取这些信息，是影响 细分效率的关键。这类应用中，对于多边形网格邻接信息的要求可归 纳为: . q l : 获 取与 某一顶点 相接的 各个面 . q 2 : 获 取与 某一 顶点 相接的 各条边 . q 3 : 获 取与某条 边相接的 各个面 . q 4 :获取某个面包含的各条边 . q 5 : 获 取与 某个 面 相 接的 各 个面 如果采用简单的点面表数据结构， 上述操作的效率必然是极低的， 因为要获取某一局部的邻接关系，必须扫描整个网格的点表或面表， 有的甚至要同时扫描点表和面表。 针对上述问题，己有几种较合理的数据结构被提出， 如 w i n g e d - e d g e , h a lf e d g e , o a v l 等。 本文以 下部分将对这几种结构进行 分析比较。 北京交通大学硕士学位论文 2 . 4 . 1 w i n g e d - e d g e 结构 ， ， ， 为了 高效的获取各种邻接信息，出 现了 基于 边界表示 ( b o u n d a r y r e p r e s e n t a t i o n s , b - r e p s ) 数 据结构， 这类结构除了 保存点面 表， 还保 存了边表以 及其他有关的拓扑信息。 b - r e p s结构的最典型代表就是 ti n g e d - e d g 结构。 edge 一 vertices一 l e f t h a v e r s e na 优亡 书 一start e nd left ! r ight pred sacc pred sace 匡 ， 扫 叮 匡f d 厅叮 图2 . 1 一 _ 图2 . 1 9 h a f - e d g e 结 构， 其中b e 边被表示成一对h a lf - e d g e 4 和6 , 面a f e b 是由h a f e d g e 1 2 3 4 按逆时针方向 组成， 面b e d c 是由h a lf - e 电e 5 6 7 8 按逆时 针方向 组成. 每个h a l f - e d g e 中， 包含了 一 个f a c e 指针指向 所属面， 一个v e rt e x 指针指向 所属边的一个端点，一个 h a l f - e d g e指针指向与它成对的 h a l f - e d g e ，一个 h a l f e d g e指针指向 在所属面中的后继 h a l f - e d g e。 h a l f - e d g e 易于处理不封闭的曲 面情况， 如图2 . 1 9 所示， 在网 格边界 处， 将相 关h a l f - e d g e 的 面指 针指向 空即可。 顶点v e r t e x 结构中， 包含 了起始h a l f - e d g e 指针及该顶点的 三维坐标值。 面f a c e 结构中， 只包 含起始h a l f - e d g e 指针。 北京交通大学硕士学位论文 图2 .2 0 h a l f - e d g 。 可以 方便的处 理q l , q 2图2 .2 1 h a lf - e d g e 可以 方便的 处理q 4 , q 5 ( 1 ) 如图2 . 1 9 所示， 通过4 .f a c e 和4 .p a i r . f a c e 即 可直接获得边b e 的 两 个相接面。 ( 2 )如图 2 .2 0所示，假定某一顶点的起始 h a l f - e d g e为 a ， 通过 a 4 a .p a ir 4 b 4 b .p a ir - c - c .p a ir 4 d , 依次 获 得该 顶点的 各相 接 边a , b, c, da 通过a .f a c e , b . f a c e , c . f a c e , d . f a c e ， 可获得该顶点的各相接面。 ( 3 )如图 2 .2 1所示，假定面 a b c d的起始 h a l f - e d g e为 1 ，通过 1 - - 4 43 - - 2 ，可依次获得组成该面的各条边.通过 1 4 l .p a i r . f a c e , 2 4 2 .p a ir f a c e， 3 4 3 .p a ir .f a c e， 4 4 4 .p a ir .f a c e ， 可 获得与 该 面 相接的 各个面。 与wi n g e d - e d g e 相比 ， h a lf - e d g e 对于q 1 - 5 , h a l f - e d g e 在执行时 间和存储空间上具有稳定性，这一特点使之更适用于曲面细分或简化 方面的应用。 2 . 4 . 3 o a v l 结构 ， ， 无论使用何种细分方案， 都要从最顶层网格开始执行。 对于细分， 一般可以假定顶层网格为满足下列要求的网格，这样使得细分规则可 以适用于网格的任何部分。 网格中的每条边最多只属于两个多边形。 这保证了网格中不存在面 北京交通大学硕士学位论文 交叉的情况。 b 对于共有某一顶点的所有多边形， 可以找出一种排列方式， 使得两 相邻多边形必有一条公共边。 过去己经提出了很多方法来表示上述类型的网格，包括 w i n g e d - e d g e , q u a d - e d g e , h a l f - e d g e , s p l i t ed g e , d i r e c t e d - e d g e f a c e t - e d g e 等等。其中最常用的就是