（计算机软件与理论专业论文）基于任意拓扑网的细分改进算法研究.pdf

摘要 摘要 细分造型方法的实质是通过对初始控制点或者初始网格进行一系列的细化过程，细 化的极限生成所需要的曲线或者曲面。细分是生成任意拓扑曲面强有力的方法。细分算 法的最大优点是它能够从任意的初始网格出发产生光滑的曲面。关于任意拓扑网格的细 分算法，主要有三个方面：逼近细分算法、插值细分算法和混合细分算法。逼近技术是 一种收缩方法，不能对曲面进行有效的控制，而对曲面进行有效的控制是曲面设计与特 征动画的关键问题。相比较而言，插值技术保持初始网格顶点不变，但曲面的光顺性很 难控制。用控制顶点的调节能力来增强细分算法的生命力是一个挑战性的研究课题。 本文针对细分曲面造型技术进行了深入研究，主要研究内容和成果如下： 1 分析了常用曲面细分方法的特点，建立了适合于曲面细分的改进的翼边数据结 构，提出了工程应用中选用曲面细分方法的主要原则。 2 研究了细分曲面的基本理论，阐述了曲线细分的产生方法和矩阵描述，分析了细 分和b 样条之间的关系，以及细分曲线的收敛性、连续性等特性；研究和比较了细分曲 面的不同规则，分析了细分曲面的性质和特征。 3 在改进任意拓扑网构造光滑表面时，初始控制网格确定的情况下，生成的曲面 形状惟一确定，最终的物体造型也随之确定，不具有可调性。因而在曲面细分过程中引 入了控制参数和摄动。通过引入控制参数，调节一个参数值，使得所得的细分曲面的表 达度可控，可以得到一系列的细分曲面。引入摄动是为了改进了空间位置，允许局部地 调控约束曲面的形状。最后给出了曲面设计的实例，表明这种算法简单、有效。 关键词：网格；曲面；c a t m u l l - c l a r k 算法；实体造型；二次细分。 a b s t r a c t a b s t r a c t t h e k e yi d e ao fs u b d i v i s i o nm o d e l i n g i st op r o c e s sas e r i e so fs u b d i v i s i o n so nt h ei n i t i a l c o n t r o lv e r t e x e so ri n i t i a lc o n t r o l sm e s h e s ，a n dg e n e r a t et h en e e d e dc u r v eo rs u r f a c ea f t e rt h e s u b d i v i s i o n t h eb i g g e s ta d v a n t a g eo fs u b d i v i s i o nm e t h o di st h a ti tc a ng e n e r a t es m o o t h s u r f a c ef r o ma r b i t r a r yi n i t i a lm e s h t h e r ea r et h r e et y p e so fa l g o r i t h m sf o rt h em e s h e sw i t h a r b i t r a r yt o p o l o g y ：a p p r o x i m a t i o ns u b d i v i s i o na l g o r i t h m ，i n t e r p o l a t i o ns u b d i v i s i o na l g o r i t h m a n dm i x e ds u b d i v i s i o na l g o r i t h m m o s ts u r f a c em o d e l i n gm e t h o d su s eo n l ya p p r o x i m a t i o n a l g o r i t h m o r i n t e r p o l a t i o na l g o r i t h ms o l e l y a p p r o x i m a t i n gs u b d i v i s i o nt e c h n i q u e si s a c o n t r a c t i v em e t h o d ，a n dw ec a n tc o n t r o lt h es u r f a c ee f e c t i v e l y b u tt h ee f f e c t i v ec o n t r o lt ot h e s u r f a c ei st h ek e yi ns u r f a c ed e s i g na n dc h a r a c t e r i s t i ca n i m a t i o n b yc o m p a r i s o n ，i n t e r p o l a t i n g s u b d i v i s i o nt e c h n i q u e sr e m a i n si n i t i a lm e s hv e r t i c e sc h a n g e l e s s ，b u ti ti sd i f f i c u l tf o rt h e f a i r i n go ft h es u r f a c et ob ec o n t r o l l e d t h em a i nf o c u so ft h i sp a p e ri st h ef u r t h e rs t u d yo fm o d e l i n gt e c h n o l o g yi ns u b d i v i s i o n s u r f a c e i t sm a i nc o n t e n t sa n dc o n w i b u t i o n sa r ea sf o l l o w s ： 1 b a s e do nt h ea n a l y s e so fs u b d i v i s i o ns c h e m e si nc o m m o nu s e ，a ni m p r o v e d w i n g e d e d g ed a t as t r u c t u r es u i t a b l ef o rs u b d i v i s i o ni sd e v e l o p e d t h ep r i n c i p l et oc h o o s e s u b d i v i s i o ns c h e m e si np r a c t i c ei sp r e s e n t e d 2 b a s i ct h e o r i e so fs u b d i v i s i o ns u r f a c e sa r e s t u d i e d d e r i v i n gm e t h o d ，m a t r i x r e p r e s e n t a t i o na n de i g e na n a l y s i so fs u b d i v i s i o na r ep r e s e n t e d r e l a t i o n s h i p sb e t w e e ns p l i n e a n ds u b d i v i s i o n ，a n d c o n v e r g e n c ea n dc o n t i n u i t yo fs u b d i v i s i o na r ea n a l y z e d s o m eo f w e l l k n o w ns t a t i o n a r ys u b d i v i s i o ns c h e m e sa r ei n t r o d u c e da n dd i s c u s s e d 3 t h es h a p eo ft h es u b d i v i s i o ns u r f a c ea n dt h ef i n a lo b j e c tm o d e la r ed e t e r m i n e db yt h e i n i t i a lc o n t r o lm e s hg i v e nw h e ni m p r o v i n ga r b i t r a r yt o p o l o g i c a lm e s h e st oc o n s t r u c ts m o o t h m e s h e s ，i t su n a d j u s t a b l e s o ，c o n t r o lp a r a m e t e r sa n dp e r t u r b a t i o ni sp r e s e n t e dd u r i n gt h e m e s hs u b d i v i s i o n b e c a u s eo ft h ep a r a m e t e r , t h es u b d i v i s i o no v e ra r b i t r a r yt o p o l o g i c a lm e s h e s i su n d e rc o n t r o lb yc h a n g i n gt h ep a r a m e t e r k i n d so fs u b d i v i s i o ns u r f a c e sc a nb ec r e a t e d t h e s h a p eo ft h em e s h e sc a nb el o c a l l ya d j u s t e du s i n gp e r t u r b a t i o nw h i c hi sd e v e l o p e dt om o d i f y t h es p a t i a lp o s i t i o n ss o m ee x a m p l e so ft h es u b d i v i s i o ns u r f a c e sg i v e nd e m o n s t r a t et h e s i m p l e n e s s ，f l e x i b i l i t ya n de f f i c i e n c yo ft h ea l g o r i t h m k e y w o r d s ：m e s h ；s u r f a c e ；c a m u l1 - c l a r ks u b d i v i s i o n ；o b j e c tm o d e l i n g ；t w o p h a s es u b d i v i s i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 第一章绪论 第一章绪论 1 1 课题研究的背景与现状 1 1 1 研究背景 随着计算机技术的发展普及和高新技术领域对于计算机辅助设计与计算机辅助制 造( c a d c a m ) 技术、计算机图形学( c g ) 的同益广泛深入的需要，c a d c a m 高新技术 得到了迅猛的发展，他们推进了许多领域的设计革命。c a d c a m 高新技术的发展和应 用水平己经成为衡量一个国家科技现代化水平的重要标志之一，c a d c a m 技术把人和 机器的各自优点结合起来，具有应用范围广、直观、优质、高效的特点，经过十几年的 发展和更新换代，从最初的c a d 系统只能用于绘图，已经发展到c a d c a m 系统的可 视化、集成化、智能化、网络化的阶段，其中计算机辅助几何设计( c o m p u t e ra i d e d g e o m e t r i cd e s i g n ，缩写为c a g d ) 是它的理论基础和关键技术，c a g d 的产生和发展极 大地影响着c a d c a m 技术的水平。新的几何造型技术一出现，往往很快就会反映到实 用的c a d c a m 系统中去。近二十年发展起来的，且现在还在迅速发展的细分造型方法， 正是在c a d c a m 系统中日益受到青睐和应用的新的有效的几何造型技术。 1 1 2 研究现状 细分曲面近年来一直是一个研究热点，对均匀和非均匀细分曲面造型技术展开的持 续的研究，解决了该领域中多个理论性和应用性问题，主要研究成果包括： ( 1 ) 通过引入等价节点距的概念，提出了用于n u r s s ( 非均匀递归细分曲面) 的特 征分析、收敛性及连续性分析的新方法，并通过反例澄清了s e d e r b e r g 等人的错误推测。 这具有重要意义，因为把n u r s s 应用到自由曲面模型以及关于曲面建模、计算机辅助 几何造型和c a d 系统的工业标准中去的主要障碍，是缺乏这些理论上对细分曲面收敛 性和连续性的证明。 ( 2 ) 提出了均匀和非均匀d o o s a b i n 曲面以及非均匀c a t m u l l c l a r k 曲面的非递归计 算方法，使得将参数曲面的许多算法和分析技术扩展到细分曲面成为可能，这对曲面设 计、有限元分析、数控代码生成等等应用方面非常重要。 ( 3 ) 改进了曲线上的三分插值细分方法，解决了三分曲线的拼接问题，并进一步提 出了用于任意拓扑四边形网格的新的插值细分格式，能统一处理网格中的奇异点和奇异 面。在计算机辅助几何造型中，插值数据点是一个极具吸引力的造型特征，因而该方法 具有非常重要的应用价值。 ( 4 ) 提出了均匀细分曲面中控制多面体到极限曲面的逼近误差的估计方法，由此可 以根据给定容差来预测递归细分的深度。这是一项很重要的实用技术，在曲面求交、网 格生成、数控加工和曲面绘制等方面都有着广泛的应用。 江南入学硕十学位论文 1 2 曲面细分概述 1 2 1 细分方法的构造思想 细分方法是曲线曲面的离散化构造方法，从初始数据出发，根据预先设计的细分迭 代规则直接生成曲线曲面或其它几何形体。 它的构造思想是：从一个控制多边形或控制网格( 网格多半可用激光从手工模型上 输入) 开始，先按照适当选取的细分规则( 一般是加权平均) ，在给定初始控制多边形或控 制网格中插入新顶点( 这些新顶点是初始控制多边形或控制网格上某几个顶点的加权平 均) ，再连接这些新顶点得到新控制多边形或控制网格，所得新控制多边形或控制网格 是初始控制多边形或控制网格的加细。不断重复上述过程，随着细分的不断进行，控制 多边形或控制网格就被逐渐细化，其极限状态就是一条曲线或一张曲面，称为递归细分 曲线或递归细分曲面。细分方法用不断细分的多边形和多边形网格在允许的误差范围内 来代替曲线曲面。 1 2 2 细分方法及细分曲面的特点 曲线曲面设计的经典参数化方法，总要将用户给定的离散控制顶点和其他信息输入 计算机，通过插值、逼近或者拟合的方法转化为连续表示，然后在显示和其他处理环节 再次转换回离散形式。这是一个“离散转连续转离散”的过程而且当形体变得复杂后， 以上处理往往随之复杂，造成计算代价的明显增加。多边形网格表示的直接方法虽然避 免了当中的连续转换环节，但其存储代价高、冗余表示多，不利于统一处理。而细分方 法只须存储离散点列，是一个从离散直接到离散的过程，可以大大加快计算和生成显示 的速度，更适合于显示、加工和求计算等，也更适合于外形设计。 传统曲面造型方法遇到复杂物体造型时往往束手无策。复杂物体的控制顶点具有复 杂的网格拓扑，这对于利用张量积方法构造的参数曲面而言，拼接或剪裁( t r i m m i n g ) 的 困难是显而易见的。细分曲面则可以定义在任意拓扑网格上，因为不规则拓扑处只须采 用特殊的细分规则就可以了。曲面的光滑性也由细分法的极限性质自动保证，因此细分 曲面不存在拼接和剪裁的问题，能很好地产生拓扑结构复杂的曲面，为几何形状不能或 难于用分析曲面表示的对象建模提供了有力的工具。 细分方法有效地处理了传统方法难以解决的问题，其主要特点可归纳为：对任意拓 扑的适应性( a r b i t r a r yt o p o l o g y ) ；可伸缩性( s c a l a b i l i t y ) ；表示的一致性( u n i f o r m i t yo f r e p r e s e n t a t i o n ) ；数值稳定性( n u m e r i c a ls t a b i l i t y ) ；实现简单性( c o d e s i m p l i c i t y ) 。基于上述 的特点，细分方法作为一种形体表示和绘制技术，具有很强的生命力和广泛的应用前景。 1 2 3 细分方法的发展历史 细分方法可以追溯到5 0 年代g r h a m 通过对折线角点进行切害- o ( c o m e rc u t ) 生成光滑 曲线的思想。7 0 年代中期，c h a i k i n 生成光滑曲线的细分方法正是这种角切割思想的具 体实现。细分方法与参数曲线曲面特别是b 样条的离散绘制存在着密切联系。现在用的 2 第一章绪论 大多数细分法是基于样条的，是对样条的推广。而张量积曲面是从含一元变量的曲线扩 展到含二元变量的曲面的一种主要构造形式。细分曲面可视为张量积曲面在任意拓扑结 构下的推广。 细分方法的发展历史大致可以分成如下三个阶段： 第一阶段：1 9 8 0 前后，提出并初步发展时期1 9 7 4 年，c h a i k i n 研究曲线的快速绘制， 用割角法产生曲线，把离散细分的概念引入到图形学界。1 9 7 8 年，c a t m u l l 和c l a r k 旧。 开创性地提出了迭代细分四边形网格生成双三次b 样条曲面片的方法，并推广到任意拓 扑网格的情形，d o o 和s a b i n b l 也开创性地提出了迭代细分四边形网格生成双二次b 样 条曲面片的方法，并推广到了任意拓扑网格的情形。c a t m u l l c l a r k 细分法以及d o o s a b i n 关于奇异点处行为的分析理论标志着细分方法正式成为曲线曲面造型的一种手段。由于 c a t m u l l c l a r k 细分法能用较少的控制顶点迅速生成具有任意形状的光滑曲面( 除奇异点 ( e x t r a o r d i n a r yp o i n t ) 处为c 1 连续外，曲面处处为c 2 连续) ，该方法很快在造型和动画领域 付诸应用，从此离散细分曲面造型得到了广泛的研究。 第二阶段：8 0 年代末到9 0 年代初的形成时期。在这个阶段，提出了很多著名的细 分方法，包括四点插值曲线细分法及六点插值曲线细分法h 1 , b i n a r y 细分曲线法喵1 ，稳定细 分法阳3 ，l o o p 细分法口，b u t e r f l y 细分法等，对旧方法也有许多改进以适应不同要求，在 细分曲线造型方面，引入均差细分、生成多项式、生成函数等概念描述细分过程，关于 细分法的收敛性、连续性分析己有了系统的研究成果。在细分曲面造型方面，引入细分 矩阵用于描述细分过程，引入离散f o u r i e r 方法、矩阵特征根法、矩阵逼近理论等方法 对多种细分曲面进行特征分析及收敛性连续性分析：在简单细分规则情形，己有了较成 熟的结论。 第三阶段：9 0 年代中期到现在的发展时期在这一阶段，不断有新的细分方法提出， 对旧方法也有许多新的适应不同要求的改进。其中，在细分曲线造型方面，蔡志杰哺。对 非均匀有序控制顶点时的四点法及变参数四点法的收敛性和连续性进行了分析；骆岩林 1 研究了生成曲线的有理稳定细分方法；k u i j t u 们提出了非线性四点插值细分法；金建荣 n 门提出了非均匀四点插值细分法，生成的曲线可达到g 连续。h a s s a n 等副提出了t e r n a r y 四点插值细分法，生成的曲线可达到d 连续。在细分曲面造型方面，p e t e r s 和r e 提出 了一类最简单的中边( m i d e d g e ) 细分法：q i n n 鲫等人将“物理”性质引入c a t m u l l c l a r k 曲面，开发出动态细分曲面模型，允许通过施加外力交互地使之变形；s e d e r b e r g 等刮 参照非均匀b 样条的构造方法，在任意拓扑网格上引入非均匀节点区间的概念，推广得 到非均匀细分曲面( 简称n u r s s ) ；d e r o s e n j l 将细分曲面造型方法用于人物动画的设计； k o b b e l t 们提出了基于三角网格的石细分法；v e l h o 和z o r i n n 7 1 提出了基于三角四边网格的 4 8 细分法；李桂清等n 8 3 提出了基于四边形网格的2 细分法，网格的分裂速度更慢。这 些都是逼近的造型。z o r i n 等提出了改进的b u t e r f l y 细分算法以得到更好的光滑性质； k o b b e l t 则提出了适合四边形网格的插值算法：l a b s i k 提出了插值2 细分法；李桂清提 江南大学硕士学位论文 出了插值f 细分法；李桂清和王华维等还分别提出了基于任意四边形网格的t e r n a r y 曲面 细分法，d o d g s o n 等则提出了基于三角形网格的t e r n a r y 曲面细分法9 ，它们都是h a s s a n 四点t e r n a r y 插值细分法在二维情形下的推广。这些都是插值的造型。此外，基于混合 网格的细分法的研究也取得了一些进展啪2 副。 这一时期丌始建立较为系统的收敛性理论，提出了多变儿任意拓扑情形下收敛性分 析的理论框架。这些理论反过来指导细分法的构造，尤其是二阶以上连续曲面的构造， 此外，各种细分法的内在联系也逐渐被揭示出来，例如z o f i n 和s c h r b d e r 将基本( p r i m a l ) 四边形网格细分法和对偶( d u a l ) l 四边形网格细分法建立了统一的框架，o s w a l d 等在2 细分法的基础上，找到了一类三角网格的统一细分形式，并由其对偶形式导出了一类新 颖的基于六边形网格的细分方法3 ，更为重要的是，细分方法与小波理论和多分辨率分析 之间的密切联系也被揭示了出来，利用已有的细分法的逆细分法生成多分辨率分析的算 法己被提出，复杂网格曲面的多分辨率分析的研究取得了不少的成果。在这一时期，细 分方法得到t 广泛应用由于细分方法应用范围的不断扩展，细分方法并不局限于曲线和 曲面的离散构造，高维细分法如实体细分法等成为了新的研究内容。 1 2 4 细分方法的分类 可以从多个角度对细分方法进行分类： ( 1 ) 按极限曲线曲面是否过初始控制顶点，细分法可分为插值细分法( i n t e r p o l a t o r y s u b d i v i s i o ns c h e m e s ) 和逼近细分法( a p p r o x i m a t i n gs u b d i v i s i o ns c h e m e s ) 。 典型的插值曲线细分法有四点b i n a r y 插值细分法、六点b i n a r y 插值细分法、三点 t e r n a r y 插值细分法、四点t e r n a r y 插值细分法等；典型的逼近细分曲线法有c h a i k i n 割角 法等。典型的插值细分曲面法有b u t e r f l y 细分法、k o b b e l t 细分法、3 插值细分法、插 值2 细分法等；典型的逼近曲面细分法有c a t m u l l c l a r k 细分法、d o o s a b i n 细分法、 l o o p 细分法、m i d e d g e 细分法、3 细分法等。本文主要研究插值细分法。 ( 2 ) 按控制点列加细规则的特点，细分法可分为顶点插入细分法( 如常见的曲线细分 法、c a t m u l l c l a r k 细分法、l o o p 细分法、b u t t e r f l y 细分法、k o b b e l t 细分法、3 细分法 等) 和割角细分法( 如c h a i k i n 割角法、d o o s a b i n 细分法、m i d e d g e 细分法等) 。 ( 3 ) 按网格拓扑分裂的方式，细分法可以分为基本细分法( 采用面分裂( f a c es p l i t ) ， 如c a t m u l l c l a r k 细分法、l o o p 细分法、b u t e r f l y 细分法、k o b b e l t 细分法等) 和对偶细分 法( 采用顶点分裂( v e r t e xs p l i t ) ，如d o o s a b i n 细分法、m i d e d g e 细分法等) 。 ( 4 ) 按不同层细分规则的特点，细分法可分为静态细分法( s t a t i o n a r ys c h e m e s ) 和非静 态细分法( n o n s t a t i o n a r ys c h e m e s ) 。不同细分层次采用相同细分规则的细分法称为静态 细分法，否则称为非静态细分法。 ( 5 ) 按同一层细分规则的特点，细分法可分为均匀细分法( u n i f o r ms c h e m e s ) 和非均 匀细分法( n o n u n i f o r ms c h e m e s ) 。每一层细分中网格的不同部分采用相同细分规则的细 分法称为均匀细分法，否则称为非均匀细分法。 4 第一章绪论 ( 6 ) 按初始控制网格的类型，细分曲面法可分为基于三角形网格的细分法( 如l o o p 细分法、b u t e r f l y 细分法、3 细分法等) 、基于四边形网格的细分法( 如c a t m u l l c l a r k 细 分法、d o o s a b i n 细分法、k o b b e l t 细分法等) 、基于六边形网格的细分法( 如张宏鑫的蜂 窝细分法等) 、基于混合网格的细分法( 如s t a m 细分法 s t a r e2 0 0 3 等) 等。 ( 7 ) 按新生成的控制点的数目，细分法可分为b i n a r y 细分法( 如c h a i k i n 割角法、四 点b i n a r y 插值细分法、六点b i n a r y 插值细分法、c a t m u l l c l a r k 细分法、d o o s a b i n 细分 法、l o o p 细分法、b u t e r f l y 细分法、k o b b e l t 细分细分法、m i d e d g e 细分法等) 、t e r n a r y 细分法( 如三点t e r n a r y 插值细分法、四点t e r n a r y 插值细分法等) 等。 ( 8 ) 按生成的极限曲线曲面在规则部分的连续性，细分法可分为c 。细分法。 c 1 细分法如c h a i k i n 割角法、四点b i n a r y 插值细分法、三点t e r n a r y 插值细分法、 d o o s a b i n 细分法、b u t e r f l y 细分法等，c 2 细分法如四点t e r n a r y 插值细分法、c a t m u l l c l a r k 细分法等) 和g 细分法( g 1 细分法如金建荣的非均匀四点插值细分法等。 细分法还可按是否线性，是否适用于非流形网格等来分类。现有的细分法，大多数 是有局部支撑、静态的线性细分法，且只适合于流形网格，关于非静态、非线性细分法 及非流形网格上的细分法己有了一些结果3 。 1 2 5 细分方法的应用 伴随着计算机图形技术的发展，几何造型技术不仅可应用于原有的外形设计，还可 广泛应用于机械制造、医学可视化、虚拟场景生成等众多领域。几何造型技术的发展促 进了它的应用领域的扩大，反过来应用领域的扩大又丰富了几何的表现形式，促进了造 型手段及造型技术的发展。由于细分曲面具有良好特性，近年来在以下领域获得了广泛 的应用。 ( 1 ) 细分曲面在动画中的应用 在动画中，用n u r b s 表示复杂形状，如人的头、手和服饰等，一般通过n u r b s 的裁剪拼接来实现，但裁剪代价昂贵，有数值误差，而且要在曲面的接缝处保持光滑， 既使是近似的光滑也很困难。细分曲面克服了以上缺陷，它无须裁剪，模型的连续性由 细分规则自动保证。 ( 2 ) 细分曲面在游戏中的应用 由于游戏对显示速度要求比较高，因此游戏的几何引擎采用何种曲面表示非常重 要，细分曲面以其绝对优势成为首选首先，l o o p 细分陆面不但显示速度快而且显示质 量非常高，还不需要使用高速缓存涵3 。其次，如果数据量很大就需要维护一个庞大的数 据结构以保存邻接信息，还要不断地随机读取内存，这对于只有很少几何处理器指令的 控制台来讲是不现实的。而用细分曲面和显式的三角网格模型表示同样的光顺曲面相 比，细分曲面占用的内存资源要少得多。 ( 3 ) 细分曲面多分辨率应用 由于细分曲面具有多分辨率性质，因此可用于： 江南大学硕+ 学位论文 ( a ) 数据压缩与简化。用基于小波的技术，网格模型可以被压缩。压缩不仅减少了 存贮空间和处理时间，而且如果去掉小波系数较小的项，会同时起到简化的作用。 ( b ) 分细节层次显示。一个复杂形体在动画中渲染时，一个完全的细节模型表示要 比视觉上的显示包含更多的信息。用复杂形体的小波表示，根据需要( 如距离远近) 显示 不同的细节水平，在几乎不影响视觉效果的同时，极大地减少了网格数量，而且即使不 优化，细分曲面显示也比n u r 正i s 曲面显示速度快啪1 。 ( c ) 分层编辑。可以根据需要在不同细节层次上对细分曲面进行编辑。 ( 4 ) 细分曲面在工程中的应用 细分曲面在逆向工程中应用研究比较多，其中文献乜7 3 的算法曲面重建质量非常高。 至于细分曲面在加工中的应用，文献晗刚给出了一种c a t m u l l c l a r k 细分曲面数控加工刀轨 生成算法。以上对细分曲面的发展历史和应用作了简要介绍。对于细分曲面理论部分( 如 连续性、收敛性) ，以及细分曲面精确计算等的相关工作将会在本文后续各章节相应部 分作介绍。 1 3 主要完成的工作 本文给出了一种任意拓扑网格细分的改进方法，它使用二次细分的方法对任意拓扑 网进行细分。在c a t m u l l c l a r k 算法的基础上进行二次改进，即在迭代法计算出初始控 制网砑。后，进行第一个阶段细分。然后用c a t m u l l - c l a r k 算法来产生约束曲面，改进确 定的顶点和切面。本人所做的工作和创新点主要包括以下几个方面的内容： 1 在c a t m u l l - c l a r k 算法的基础上进行二次改进，即在迭代法计算出初始控制网肪。 后，第一个阶段细分。然后用c a t m u l l - c l a r k 算法来产生约束曲面，改进确定的顶点和 切面。 2 在创建加细网的过程中，提出了对顶点的摄动，从改进了顶点的空间位置。 1 4 本文内容组织 第一章绪论，主要介绍了本研究课题范围内，国内外已有文献的情况综述，论文的 实用价值和理论意义；本论文解决的主要问题。 第二章介绍了细分的相关问题。包括细分的概念、分类，特点，以及常见细分，最 后对细分曲面的连续性进行了简单的分析。 第三章研究了任意拓扑网的细分方法。包括三种方法，即：逼近细分算法，插值细 分算法和混合细分算法。对每一种方法都进行了分类介绍，为第四章的深入研究进行了 基础准备。 第四章研究了任意拓扑网格的改进算法，提出了基于一个二次细分过程，给定一个 改进多面体，用迭代法计算出初始控制网力o 。然后对进行第一个阶段细分，创建一个加 细网肪1 。为了改进空间位置，提出了摄动方法。最后用c a t m u l i - c l a r k 算法来产生约 束曲面，改进确定的顶点和切面。 6 第一章绪论 第五章结论，同时介绍了今后需要进一步完善的工作。 7 江南人学硕士学位论文 第二章细分造型基础 本章介绍了细分的基本概念及常用细分。包括细分曲面的特点、分类、性质，并详细 介绍几种基本的细分方法，包括c a t m u l l c l a r k 细分、d o o s a b i n 细分、l o o p 细分、改进 的b u t t e r f l y 细分、3 细分等。最后简要分析了细分曲面的连续性。 2 1 细分造型基础 细分曲面是多边形网格的极限状态，在实现时其实它也是细分的某个层次。 2 1 1 基本概念 网格( m e s h ) ：由顶点，边和面构成的多面体表面。如果所有网格面均为三角( 四边) 形，则称其为三角( 四边) 形网格；如果网格面中包含有不同类型的多边形，则称为任意多 边形网格。 边界边：如果网格的某一条边只属于一个面，则称为边界边。 边界点：如果一个顶点在边界边上则称为边界点。 边界面：至少包含一条边界边的面称为边界面。 开网格：至少含有一条边界边的网格称为开网格。 顶点价：对于一个顶点，与其直接相连的边数，称为该顶点的价。 k 一邻域：对于网格中的一个顶点矿，以矿为中心，所有到矿的距离小于k 的顶点所构 成的网格，称为顶点y 的k 一邻域。 2 1 2 细分模式分类 通常有两种最基本的分裂方法：顶点分裂和面分裂。 顶点分裂是对于给定度数为刀的顶点，将其分裂成竹个新顶点，每个顶点对应着它的 一个邻面，使用该方式的细分方法称为对偶型。如果，为内部顶点，则把这些复制顶点依次 相连，形成一个，z 边形，称此刀边形称为新网格的v 一面；对于内部边两个端点分裂构成 的新网格称为e 一面，旧网格多边形每个顶点分裂构成的新网格面与原来的网格具有相同 的拓扑结构，称之为p 一面。图2 1 ( 上) 为顶点分裂的示意图。 面分裂是在网格边和面上插入新的顶点，然后对每个面进行剖分，从而得到新的网格， 如图2 - 1 ( 下) ，使用此方式的细分方法称为基本型。根据新生成的面的数量分裂也可以有 不同种类的划分。 第二章细分造型基础 e 面 蕈面 v 蕾 口一强 图2 - 1 顶点分裂和面分裂 f i g2 - 1v e r t e xa n df a c es u b d i v i s i o i l 除此之外，根据不同的角度，细分模式还有很多种不同的分类方式。根据几何规则和 细分层次之间的关系，若几何规则在不同的分层之间采取相同的系数，称之为静态细分模 式，否则称之为动态细分模式。根据控制网格的类型，可以分为四边形网格细分和三角形 网格细分。根据细分极限曲面与初始控制网格的关系，又可分为插值细分和逼近细分，其 主要区别在于前者y 一顶点的位置在细分后保持不变。根据表述细分规则的方程类型，又可 分为隐式细分模式和显式细分模式。另外，细分模式还有局部、全局，均匀、非均匀等之 分。 2 1 3 细分方法的特点 同传统的参数样条曲面相比，细分方法具有如下特点： ( 1 ) 拓扑结构的任意性：传统的曲面造型方法很难处理任意拓扑结构的网格，对于利 用张量积方法构造的参数曲面来讲，拼接或裁剪的难度是显而易见的。而细分方法以其本 身为参数空间，在控制拓扑结构的同时又不失高效性，这正是它最显著的特点。 ( 2 ) 在进行局部特征调控的同时，能够保证曲面整体的光滑性。虽然样条曲面也具有 同样的功能，但细分曲面对局部细节的控制要比它更加的灵活和方便，同时运算量也要节 省很多。 ( 3 ) 高效性：细分方法算法实现简单，数值稳定，由于新点的计算是线性且局部的， 所以相对隐式曲面等来讲计算的效率很高。 细分造型是联系连续模型和离散表示的桥梁，它通过对离散的控制网格不断应用细分 规则而得到连续极限曲面。 2 2c h aiki 1 1 算法 细分曲面的基本思想可追溯到c h a i n k i n 1 1 的算法，该算法通过削角可从一个多边形生 成一个二次b 一样条曲线。每次细分在多边形的每条边上都生成两个新的顶点。参考图 2 2 ，对个有刀个顶点k ( 1 i 5 ) = 高，而。：= 一击，( 七= 3 )2 西，而。2 一西，【尼2 功 s 。= i 3 ，毛，3 = 。，s 2 = 一虿1 ，( 后= 4 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) ( a ) 端点价为6 的内部边的e 一顶点( b ) 端点价不为6 的内部边的e 一顶点( c ) 边界e 一顶点 图3 - 2 改进的b u t t e r f l y 算法细分模板 f i g3 2m o d i f i e db u t t e r f l ys u b d i v is i o ni l i as k 要把b u t e r f l y 算法的细分规则扩展到任意网格是有些复杂性的，这是