（机械电子工程专业论文）细分曲面软件系统的设计与实现.pdf

南京航空航天大学硕士学位论文 摘要 细分曲面是基于网格的离散曲面造型新技术，它通过定义控制网格和细分规则来 表示造型曲面。它不仅具备b 样条曲面的局部支承性、仿射不变性等良好性质，而 且具有参数曲面所没有的任意拓扑适应性等特点，因而近年来得到广泛的应用。本文 先对基本细分算法及其在c a d 中的自适应细分算法和三角网格模型拟合l o o p 细分 曲面算法进行了比较深入的研究，最后将其集成开发出个基于细分曲面的软件系 统，主要内容包括： ( 1 ) 分析了细分理论和典型细分模式，阐述了细分曲面的极限点、切矢、法矢 等基本几何量的精确计算方法。 ( 2 ) 在正常的曲面细分过程中，控制网格上几何元素( 顶点、边、面) 的数量 是按照几何级数增加的，会产生庞大的冗余数据。本文提出了两种符合要求的自适应 细分模式：一是基于形状精度控制的自适应细分模式；二是基于表面光顺性要求的自 适应细分模式。可以在保证所需细分质量前提下，使得表示细分曲面的控制网格上的 几何元素的数量明显下降，从而为细分曲面的后续处理、存储、传输节约了大量的时 间和空间。 ( 3 ) 模型重建是逆向工程的重要环节，本文提出了从三角网格模型获得l o o p 细分曲面的控制网格，从而实现了任意拓扑密集网格的细分曲面重建算法。 ( 4 ) 改进了适合于曲面细分的的翼边数据结构，并实现了典型的细分算法( l o o p 细分、c a t m u l lc l a r k 细分、d o o s a b i n 细分、混合细分、自适应细分) ：采用o r ，e n g l 技术实现了旋转、缩放、平移、拾取等图形的基本几何操作；最后将本课题组研究成 果加以集成，开发了一个基于细分曲面的原型系统。 关键词：细分曲面、c a d c a m 、细分规则、逆向工程、曲面重构、原型系统 细分曲面软件系统的设计与实现 a b s t r a c t s u b d i v i s i o ns u r f a c ei san e wg e o m e t r i cm o d e l i n gt e c h n o l o g yo fd i s c r e t es u r f a c eb a s e d o nm e s h i tc a ne x p r e s sm o d e l i n gs u r f a c et h r o u g hc o n t r o lm e s ha n ds u b d i v i s i o nr u l e s t h i s t e c h n o l o g yn o to n l yp r e s e r v e st h ep r o p e r t i e so f l o c a l n e s sa n da f f m e - i n v a r i a n c eo f b - s p l i n e s u r f a c e ，b u ta l s oh a ss o m es p e c i a la d v a n t a g e ss u c ha sa d a p t a b i l i t yt oa r b i t r a r yt o p o l o g y w h i c hp a r a m e t e rs u r f a c e sd o n th a v e t h e s eg o o dq u a l i t i e sm a k e ss u b d i v i s i o ns u r f a c eu s e d w i d e l yi nr e c e n ty e a r s i nt h i st h e s i s ，b a s i cs u b d i v i s i o ns c h e m e sa n d i t sa d a p t i v es c h e m e si n c a d ，t o g e t h e rw i t ht h ea l g o r i t h mw h i c hi sa b o u tt r i a n g l em e s hm o d e lf i t t i n gl o o p s u b d i v i s i o ns u r f a c e ，a r es t u d i e di nd e p t h t h e nas o f t w a r es y s t e mb a s e do ns u b d i v i s i o n s u r f a c ei sd e v e l o p e d ，a n dt h e s ea l g o r i t h m sa r ei n t e g r a t e di ni t t h em a i nw o r ki sa s f o l l o w s ： ( 1 ) s u b d i v i s i o nt h e o r i e sa n dt y p i c a ls u b d i v i s i o ns c h e m e sa r ea n a l y z e d t h ea p p r o a c h t oe x a c t l yc a l c u l a t eg e o m e t r i cp a r a m e t e r so fs u b d i v i s i o ns u r f a c e ，s u c ha sl i m i r i n gp o i n t ， t a n g e n tv e c t o ra n dn o r m a lv e c t o r , a r ei l l u s t r a t e d ( 2 ) t h en u m b e ro fg e o m e t r i ce l e m e n t s ( v e r t e x ，e d g e ，f a c e t ) w i t h i nc o n t r o lm e s hg r o w s e x p o n e n t i a l l ya st h ei n c r e a s eo fs u b d i v i s i o nl e v e l si ng e n e r a ls u b d i v i s i o ns c h e m e s t h i s r e s u l t si ne n o r m o u sa n dr e d u n d a n td a t a t w oa d a p t i v es u b d i v i s i o ns c h e m e s ，w h i c hc a n s a r i s f ye n g i n e e r i n gr e q u i r e m e n t s ，a r ep r o p o s e di nt h i st h e s i s o n ei sb a s e do ns h a p e p r e c i s i o nc o n t r o l ，a n o t h e ro ns u r f a c ef a i m e s sc r i t e r i o n b o t ho ft h e md e c r e a s et h es i z eo f c o n t r o lm e s he v i d e n t l y , a n dm e a n w h i l et h eq u a l i t yo fs u b d i v i s i o ns u r f a c ei sg u a r a n t e e d a l lt h e s es a v el o t so f t i m ea n ds p a c ef o rs u c c e s s i v es t o r a g e ，t r a n s m i s s i o na n dm o d i f i c a t i o n ( 3 ) m o d e lr e c o n s t r u c t i o ni sak e ys t e pi nr e v e r s ee n g i n e e r i n g t h ea c q u i s i t i o no f c o n t r o lm e s hf o rl o o ps u b d i v i s i o ns u r f a c ef r o mg e n e r a lt r i a n g l em e s hi sr e s e a r c h e d ，a n da n a l g o r i t h mi sp r o p o s e dt o f u l f i l lt h er e c o n s t r u c t i o no fs u b d i v i s i o ns u r f a c ef r o ma r b i t r a r y d e n s em e s hi nt o p o l o g y ( 4 ) a ni m p r o v e dw 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 s o m et y p i c a ls c h e m e sa r ei m p l e m e n t e dv i at h i sd a t a s t r u c t u r e ( l o o ps u b d i v i s i o n , c a t m u l l c l a r k s u b d i v i s i o n , d o s a b i n s u b d i v i s i o n ，h y b r i ds u b d i v i s i o n ，a d a p t i v e s u b d i v i s i o n ) t h et e c h n i q u eo fo p e n g li su t i l i z e dt oa c c o m p l i s hs o m eb a s i co p e r a t i o n s ， s u c ha sr o t a t i o n ，z o o m ，p a n ，p i c ka n ds oo n f i n a l l yt h ea l g o r i t h m ss t u d i e db yo i u r e s e a r c h g r o u pa r ei n t e g r a t e d ，a n dap r o t o t y p es y s t e mb a s e do ns u b d i v i s i o ns u r f a c ei sd e v e l o p e d k e yw o r d s ：s u b d i v i s i o ns u r f a c e ，c a d c a m ，s u b d i v i s i o nf o r m u l a , r e v e r s ee n g i n e e r i n g ， s u r f a c er e c o n s t r u c t i o n ，p r o t o t y p e s y s t e m 南京航空航天大学硕十学位论文 第一章绪论 1 1 细分曲面的国内外研究与应用情况 1 1 1 细分曲面的国内外研究现状 细分方法可以追溯到1 9 5 6 年g d er a h m 1 埯过对多边形角点进行切割( c o m e rc u t ) 来生成离散形式光滑曲线的思想。真正把细分概念引入到图形学，是1 9 7 4 年c h a i k i n 【2 】 提出一种曲线的快速生成方法，也正是这种角切割思想的具体实现。在1 9 7 8 年第6 期 c o m p u t e r a i d e dd e s i g n 杂志上，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 3j ，将此细分曲面视为双三次均匀b 样条曲面在任意拓扑结构下的推广。在同一 期杂志t ，d o o 和s a b i n 4 1 首先提出了利用离散f o u r i e r 变换，通过对细分矩阵特征分 析束研究细分曲面的连续性，从此拉开了对细分曲面进行广泛深入研究的序幕。 细分方法发展历史大致可分成如下几个阶段： 上世纪5 0 年代中期到7 0 年代末是细分方法的孕育期。c a t m u l l c l a r k 细分模式以 及d o o s a b i n 关于奇异点处行为的分析理论标志着细分方法正式成为曲面造型的一种 手段。 8 0 年代初到9 0 年代初是细分方法的发展期。在这一时期，新的细分方法不断涌 现。1 9 8 7 年，l o o p 5 1 在其硕士论文中提出了一种基于三角网格的细分方法。1 9 9 0 年， d y n 等人则提出了基于三角网格的蝶形细分曲面( b u t t e r f l ys u r f a c e ) 1 6 】。规则网格的细分 曲面收敛性和连续分析理论也逐步形成，如1 9 9 3 年c a v a r e t t a 给出了单变元细分模式达 到任意阶光滑的充分必要条件1 7 l 。在这期间，虽然已经出现了许多细分方法，但是它 们之间缺乏联系，各自的收敛性分析方法与具体的细分模式密切相关，没有形成统一 的细分分析理论。由于细分过程后控制网格的几何元素呈几何级数增长，受当时硬件 实现条件的限制，所以在这一时期细分方法的应用并未得到充分的重视。 9 0 年代中期到现在是细分理论的完善期和细分方法应用的深入期。这一时期开始 建立系统的收敛性理论，提出了多变元模式任意拓扑情形下收敛性分析的理论框架 8 ， 。这些理论反过来指导细分模式的构造，尤其是二阶以上连续曲面的构造。此外，各 种细分模式的内在联系也逐渐被揭示出来【1 “。同时发现了细分方法与多分辨率分析 ( m u l t i r e s o l u t i o n a n a l y s i s ) 、小波( w a v e l e t ) t 里论之间的深刻联系，也是细分方法备受关 注的重要原因之一。 国内对于细分曲面的研究起步比较晚，最早在2 0 0 0 年见到相关文献t 1 ”，近两年， 国内细分曲面的研究开始逐渐增多，其研究方向主要集中在基本算法1 2 1 3 j 4 1 和工程、 图形学领域的应用i l j ”。 近几年来，南京航空航天大学c a d c m 工程研究中心细分曲面课题组在细分曲 塑坌堕画堡竺墨丝塑壁盐量壅堡 面的理论研究与工程应用方面作了大量的工作，并且取得了许多成果。主要集中在以 下几个方面： ( 1 ) 等距曲面生成在c a d 及数控加工编程中是不可缺少的功能，因此我们对l 0 0 d 细分曲面等距面生成算法进行了研究； ( 2 ) 数控加工是目前c a d c a m 系统中最能明显发挥效益的环节之一，从细分 曲面生成n c 刀轨是必不可少的环节，我们在这一领域作了一些有益的尝试与探索： ( 3 ) 针对有序数据细分曲线重建算法，提出了一种有序数据测量方法及有序数据 细分曲线重建算法； ( 4 ) 为了满足工程实际造型中在细分曲面上产生不光滑特征需求，我们研究了细 分曲面的特征生成与控制算法； ( 5 ) 运用细分方法解决样条曲面中的混合( 填充) 问题，这是我们在研究过程中发 现的一种新的思路。 在对以上研究成果进行总结的基础上，作者开发了这个细分曲面的软件系统。 但是，还有许多问题有待进一步研究。例如，为了更好的解决细分过程中几何元 素增氐过快的问题，克服多次细分时的计算时间和存储空间方面的缺陷，很有必要对 自适应细分进行研究。另外，要将细分曲面真正应用于工程实践，实现从测量数据到 可以用于数控加工的c a d 模型的转化，细分曲面模型重建是必不可少的。最后，无论 是理论研究还是工程应用，所有的算法都需要一个软件平台作为桥梁，才能使研究成 果转化为生产力。 1 1 2 细分曲面关键技术与应用 细分曲面具有n u r b s 曲面所具有的所有优点：简单高效、局部性、连续性、仿 射不变性等，同时还具有自身一些特性：1 ) 任意拓扑性，这是n u r b s 曲面一直不能 克服的关键问题。2 ) 一致表示性，细分曲面既可以看作是网格定义的连续曲面，又可 以看做是离散网格曲面。3 ) 多分辨率，细分曲面的多分辨率性质使得它可以在图形编 辑、显示、传输方面具有明显的优势。正是细分曲面具有以上一些良好特性，所以近 年来在以下领域获得了广泛的应用。 ( 1 ) 细分曲面在动画中的应用 在动画中，用m 瓜b s 表示复杂形状，如人的头、手和服饰等，一般通过n i 瓜b s 的裁剪拼接来实现，但裁剪代价昂贵，有数值误差，而且要在曲面的接缝处保持光滑， 既使是近似的光滑也很困难。细分曲面克服了以上缺陷，它无须裁剪，模型的连续性 由细分规则自动保证。1 9 9 8 年s i g g r a p h 大会上同时有8 篇关于细分的论文发表【1 ”，以 及同年p i x a r 公司的一部完全使用细分曲面造型技术的动画短片( ( g e r i sg a m e ) ) 获得奥 斯卡最佳动画短片奖。1 9 9 9 年a c ms i g g r a p h 的成就奖授予t o n y d e r o s e ，就是为了 表彰他在用细分方法创造性地解决几何造型问题中所做出的突出贡献【l ”。 一 南京航空航天大学硕士学位论文 一一 ( 2 ) 细分曲面在游戏中的应用 由于游戏对显示速度要求比较高，因此游戏的几何引擎采用何种曲面表示非常重 要，细分曲面以其绝对优势成为酋选，首先，l o o p 纫5 + 面不但显示速度炔。历且显 示质量非常高，还不需要使用高速缓存19 1 。其次，如果数据量很大，就需要维护一个 庞大的数据结构以保存邻接信息，还要不断地随机读取内存，这对于只有很少几何处 理器指令的控制台来讲是不现实的。而用细分曲面和显式的三角网格模型表示同样的 光顺曲面相比，细分曲面占用的内存资源要少得多。 ( j ) 细分曲面多分辨率应用 由于细分曲面具有多分辨率性质，因此可用于：( 1 ) 数据压缩与简化。用基于小 波的技术，网格模型可以被压缩。压缩不仅减少了存贮空间和处理时间，而且如果去 掉小波系数较小的项，会同时起到简化的作用。( 2 ) 分细节层次显示。当一个复杂形 体在动面中渲染对，一个完全的缨节模型表示要比视觉上的显示包含更多的信息。用 复杂形体的小波表示，根据需要( 如距离远近) 显示不同的细节水平，在几乎不影响 视觉效果的同时，极大地减少了网格数量，而且即使不优化，细分曲面显示也比n u r b s 曲面显示速度快1 2 。( 3 ) 分层编辑。可以根据需要在不同细节层次上对细分曲面进行 编辑， ( 4 ) 细分曲面在工程中的应用 细分曲面在逆向工程中应用研究比较多，其中文献 2 1 l 的算法曲面重建质量非常高。 至于细分曲面在加工中的应用，文献 2 2 1 给出了一种c a t m u l l c l a r k 细分曲面数控加工刀 轨生成算法。 以上对细分菌面的发展历史和应用作了简要介绍。对于缅分益面理论部分( 如连 续性、收敛性) ，以及细分曲面精确计算等的相关工作将会在本文后续各章节相应部 分作介绍。 1 2 论文的选题依据和主要研究内容 1 2 ，1 研究目的 目前许多造型软件如m a y a 、l i g h t w a v e 、3 d s m a x 、a n i m a t i o nm a s t e r 、p r m a n 、 t m e s p a c e 等都已实现了细分曲面的造型功能。细分曲面在动画造型中主要解决的问题 是尖锐特征、形状保持与纹理映射口”，基于细分曲面的m o r p h i n g 技术与隐函数表示的 结合，是目前此方向上的热点问题。另外地形地貌的生成与绘制也是实时动画与游戏 的重要功能，这与细分曲面的自适应剖分技术密切相关 2 4 】。但是，目前还没有专门针 对细分曲面在c a d 领域应用的软件问世。 由于细分曲面除了继承m 限b s 曲面的优点之外还具备自身特有的良好品质因 此在c a d 系统中引入细分造型技术是未来c a d 系统革新的一个重要方向。作者对几 细分曲面软件系统的设计与实现 种典型的细分算法的基础理论进行了研究，并且结合它们在c a d 领域的应用，开发出 这个细分曲面的原型系统，把细分方法运用到几何造型系统，为将来全面研究细分曲 面在c a d 领域的应用，进一步开发出具有商用价值的纫分曲面软件系统奠定了基础， 1 2 2 论文主要内容 本文首先研究了几种典型的细分算法的基础理论和实现方法，然后针对自适应细 分和逆向工程中缨分曲面的模型重建算法进行了研究，最后，总结以前的研究成果， 开发了一个细分曲面原型系统。其主要内容安排如下： 第一章，绪论。以综述细分方法的形成、发展、特点和细分曲面的应用为切入点， 阐述了目前该领域的发展概况，并在这个基础上引申出本文的研究课题。 第二章，细分曲面的理论和计算。阐述了网格几何拓扑、离散f o u r i e r 分析技术等 一些细分曲面的数学基础，并且给出了细分曲面的极限点、切矢、法矢等基本几何量 的精确计算公式。 第三章，细分曲面自适应细分算法。本文提出了两种符合要求的自适应细分模式： 一是基于形状精度控制的自适应细分模式；二是基于表面光顺性要求的自适应细分模 式。在保证细分精度要求的条件下，使得缅分盘面的控制网格上的几何元素的数量明 显下降，从而为曲面细分节约大量的时间和空间。 第四章，逆向工程中的细分曲面模型重建。提出了从任意拓扑密集三角网格模型 获得l o o p 细分曲面控制网格算法，通过对控制网格顶点的循环修正、网格形状优化、 局部自适应细分来求解拟合控制网格的顶点位置。根据给定的拟合精度重建出反映物 体细节特征的、分片光滑的( 片内除奇异点c 1 外其余c2 连续) 待构物体l o o p 细分曲面模 型，实现了逆向工程中细分曲面模型重建。 第五章，细分曲面原型系统的开发。该系统以改进的翼边结构为基础，采用面向 对象的软件技术。在v c + + 6 0 平台上利用o p e ng 作为几何引擎进行开发。它具有几种 典型的缅分功能以及曲面重建、益面等距、曲面求交等功能。 第六章，对论文工作进行了总结，并对将来细分曲面及其应用软件的发展方向作 了展望。 南京航空航天太学硕土学位论文 本章参考文献 【l 】gd er a h m s ur u n ec o u r b ep l a n e ，d em a t hp u r e s a p p l ，1 9 8 7 ，3 5 ：2 5 4 2 ， 2 】c h a i k i na n dg m e r r i l l a na l g o r i t h mf o rh i 曲s p e e dc u r v eg e n e r a t i o n c o m p u t e r g r a p h i c sa n di m a g ep r o c e s s i n g ，1 9 7 4 ，( 3 ) ：3 4 6 3 4 9 3 】e c a t m u l la n djc l a r kr e c u r s i v e l yg e n e r a t e db - s p l i n es u r f a c e so na r b i t r a r yt o p o l o g i c a l m e s h e sc o m p u t e r a i d e dd e s i g n ，1 9 7 8 ，1 0 ( 6 ) ：3 5 0 3 5 5 f 4 1dd o oa n dms a b i nb e h a v i o u ro fr e c u r s i v ed i v i s i o ns u r f a c e sn e a re x t r a o r d i n a r yp o i n t s c o m p u t e r - a i d e dd e s i g n ，1 9 7 8 ，1 0 ( 6 ) ：3 5 6 3 6 0 5 1c l o o ps m o o t hs u b d i v i s i o ns u r f a c e sb a s e do nt r i a n g l e s m a s t e r st h e s i s u t a h ： u n i v e r s i t yo fu t a h ，d e p a r t m e n to f m a t h e m a t i c s ，1 9 8 7 6 nd y n ，dl e v i na n djg r e g o r y ab u t t e r f l ys u b d i v i s i o ns c h e m ef o rs u r f a c e i n t c r p o l a t o r yw i t ht e n s i o nc o n t r o la c mt r a n s a c t i o n so ng r a p h i c s ，1 9 9 0 ，9 ( 2 ) 1 6 0 1 6 9 7 ac a v a r e u a ，w d a e n ，a n dcm i c c h e l l is t a t i o n a r ys u b d i v i s i o n m e m o i r so ft l e a m s ，p r o v i d e n c e 1 9 9 i ，( 9 3 ) 1 - 1 8 6 【8 jw a r r e ns u b d i v i s i o nm e t h o d sf o rg e o m e t r i cd e s i g n u n p u b l i s h e dm a n u s c r i p t ： h t t p ：w w w c s r i c e e d u - w a r r e n d l o o k , 19 9 5 9 ur e i f au n i f i e da p p r o a c ht o s u b d i v i s i o na l g o r i t h m si l e a re x t r a o r d i n a r yv e r t i c e s c o m p u t e r a i d e dg e o m e t r i cd e s i g n ，1 9 9 5 ，j 2 ( 2 ) ：1 5 3 1 7 4 f 10 1dz o f i n s t a t i o n a r ys u b d i v i s i o na n dm u l t i r e s 0 1 u t i o ns u r f a c er e p r e s e n t a t i o np hd t h e s i s ，c a l i f o r n i ai n s t i t u t eo f t e c h n o l o g y , p a s a d e n a ，c a l i f o r n i a , 1 9 9 8 11 】秦开怀，王华维非均匀细分曲面造型及其连续性分析中国科学e 辑2 0 0 0 年0 3 期 r 1 2 】李桂清，卢冰、李现民等子分曲面尖锐特征生成软件学报2 0 0 0 ，1 l ( 9 ) 13 】g u o - f uw i l ，f u - l a ic h e ns h a r pf e a t u r e s o fs u b d i v i s i o ns u r f a c e so v e rt r i a n g u l a r m e s h c s 中国科学技术大学学报2 0 0 2 ，3 2 ( 2 ) 1 4 0 1 4 6 1 4 1 刘伟中，旌锡泉，宋根旺l o o p 细分曲面上的交互切分算法河北理工学院学报 2 0 0 2 ，2 4 ( 2 ) ：4 2 - 5 3 1 5 】邓军民，宾鸿赞，区士颀等细分造型技术在c a d 系统中的应用研究光学精密 工程2 0 0 2 ，1 0 f 2 ) ：2 2 6 2 3 0 【1 6 李桂清细分曲面造型及应用学位论文北京：中国科学院计算技术研究 所2 0 0 1 【1 7 s u b d i v i s i o nf o rm o d e h n ga n da n i m a t i o n ，s i g g r a p h l 9 8 c o u r s en o r e s ， h t t p ：w w wm u l t i r e s c a l t e c h e d u l t e a c h i n g c o u r s e s s u b d i v i s i o n ，1 9 9 8 【1 8 】王国瑾，曲面造型技术的现状和发展趋势 h t t p ：w w wc a d z j u e d u c r d c h i n a g r a p h c h i n e s e s p e c i a l t o p i c c a g d i n d e x h u n f 1 9 1b r i c k i - - i 也ldp r a c t i c a li m p l e m e n t a t i o nt e c h n i q u e sf o rm u l t i r o s o l u t i o ns u b d i v i s i - o hs u r f a c e s i ng a m ed e v e l o p e r sc o n f e r e n c e 2 0 0 1 2 0 p u l l ik ，s e g a lmf a s t r e n d e r i n g o fs u b d i v i s i o ns u r f a c e st h ea r ta n d i n t e r d i s c i p l i n a r yp r o g r a m so f s i g g r a p h 9 6o ns i g g r a p h 9 6v i s u a lp r o c e e d i n g s ，p a g e 塑坌鱼亘竺壁墨笙塑堡生兰塞墨 1 4 4 ( p a r , # 6 ，0 7 8 ，3 31 ，a s s i g n e ei ss g i ) 2 1 c m a n d a l ，hq i na n dbv e m u r i d y n a m i cm o d e l i n go f b u t t 盯n ys u b d i v i s i o ns u r f a c e s i e e et r a n s a c t i o n so nv i s u a l i z a t i o na n dc o m p u t e rg r a p h i c s ，2 0 0 0 6 ( 3 ) ：2 6 5 2 8 7 【2 2 k u r g a n oj g e n e r a t i o no f n ct o o lp a t hf o rs u b d i v i s i o ns u r f a c e sh a p ：v c w wc i m m u t o k y oa c j p - j o e m o m h l y r e p o 刚g e n e r a t i o n _ o fn c - f o rs u b d i v i s i o n _ 2 3 t d e r o s e ，k a s sma n dt m o n gt s u b d i v i s i o ns u r f a c e si nc h a r a c t e ra n i m a t i o n i n c o m p u t e rg r a p h i c sp r o c e e d i n g s ，a n n u a lc o n f e r e n c es e r i e s ，a c ms i g g r a p h ， 1 9 9 8 ：8 5 9 6 【2 4 d r o s e ，mk a d a ，t e n lo n t h e f l ya d a p t i v es u b d i v i s i o nt e m a i n t h e6 t h i n t e m a t i o n a lf a l lw o r k s h o p ，h t t p ：w w w v i su n i s t u t t g a r td e v m v o l d y p a p e r s 6 p d f ，2 0 0 1 堕塞堕至堕墨茎兰堡主兰焦堡茎 一 _ 。- _ _ _ _ 。_ 。_ _ _ - - - _ _ _ _ _ _ _ 。- 。f 1 。_ 。 2 1 概述 第二章细分曲面的理论和计算 本章首先介绍与细分方法密切相关的数学基础，主要有网格几何拓扑、离散f o u r i e r 分析技术，并对细分中的一些重要概念进行明确的数学定义。详细阐述几种典型的细 分算法，并用v c ”6 o 实现了l o o p 缅分算法、c a t m u l l c l a r k 细分算法、d o o s a b i n 缅 分算法、混合细分算法、自适应细分算法，并说明了它们的优缺点。 2 2 细分理论基础 2 2 i网格拓扑 简单浣细分曲面就是多边形网格的极限状态，在实现时也只能把它当作某一细分 层次的多面体来考虑，细分方法所处理的就是多边形网格，因此有必要对多边形网格 的有关拓扑概念 乍较为明确的定义。 ( 1 ) 广义单纯复形 定义2 1 广义单纯复形是满足下列条件1 ) 6 ) 的三元组集合k = ( 矿，e ，f ) ，这里 v 是由顶点构成的集合；记矿 v ； ( f j ) ：v i ，= ，矿) ，e 仁 ( f ) v y 的元索 称为边；f 为顶点构成的多元组集合，f 的元素称为面： ! 1 一 f 。_ 1 。l l v k ：l3 矿o v 矿) ，其中，l v i 表示顶点个数。 i ) 每个面的所有边属于占。即可瓴，之，蠢) f ，( 矗，& ，m o d t + l e ( 1 j d ： 2 ) 没有孤立的顶点，即v 的每个顶点一定属于某条边，即v f 矿，可便得 ( i ，j ) e 3 1 没有悬空边即e 的每条边定属于某个面，即v ( f ，j ) e e ，x 一，i ，。，f ； 4 1 一条边最多属于两个面： 5 1 两个面最多有一条公共边： 6 ) 对于以j v 为端点的任意两条边白、b 2 , - - 定存在一个以j 为顶点的多边彤面 序列 ，a ， ，使得g l 、e 2 分别为多边形面z 和 的边，且_ ，i , + t ( ，= 1 ，一1 ) 共 墅坌些亘鏊堡墨丝塑堡盐量壅垫 有条边。 满足定义2 1 的2 ) 6 ) 条件，则保证网格具有二维流形 2 1 不满足定义2 i 的2 ) 6 ) 条件之一，则称为非流形。 图21 是不满足定义2 1 中的条件2 ) 、3 ) 、4 ) 、5 ) 、6 ) 的一些非流形的例子。 套渔澄 跽 ( d ) 两个面有两条公挟边( e ) 不满足条件6 ) 的平面情形( f ) 不满足条科：6 ) 的空间情形 图2 1 不满足单纯复形条件的非流形 定义2 2 如果广义单纯复形的一条边只属于一个面，称这条边为边界边 ( b o u n d a r ye d g e ) ：如果个顶点属于边界边则称此顶点为边界顶点( 或边界 点，b o u n d a r yv e r t e x ) ；至少包含一个边界顶点的面称为边界面( b o u n d a r v f a c e ) 。非边界 的边、顶点和面分别称为内部边( i n t e r n a le d g e ) 、内部顶点( i n t e r n a lv e r t e x ) 和内部面 ( i n t e r n a lf a c e ) 。 ( 2 ) 拓扑关系 定义2 3 对于顶点f v ，如果存在j v ，使得e = ( f ，- ，) e ，称e 为顶点i 的 邻边，歹称为顶点f 的相邻顶点，歹和i 称为e 的端点。顶点i 的邻接边的数量称为i 的 f f i ( v a l e n c e ) ，记为n a 如果存在顶点“，f 女一l v ，使得厂= ( f ，“，i k 。1 ) f ，称， 为顶点f 的邻面。 定义2 4 任给顶点f v ，记矿7 = j ：d ( i ，) 忌一i ，f = ( 厂：3 i ，厂与i 相 邻 ，再记e = e ：可f ，已是厂的边 ，n k = ( v te7 ，f7 ) 称为f 的k 邻域。 ( 3 ) 多边形网格 有了网格拓扑的基本概念，再引入顶点在空间中的几何位置，就可形成三维空间 中多边形网格的定义， 定义2 5 己知单纯复形k = ，e ，f ) 和网格m = ( k ，中) ，i v 。如果m 是三 角网格，i 为内部顶点且价不等于6 或i 为边界顶点且价不等于4 ，则称f 为奇异顶点 南京航空航天大学硕士学位论文 ( e x t r a o r d i n a r yv e r t e x ) ，否则称为正则顶点( r e g u l a rv e r t e x ) 。如果m 是四边形网格，i 为内部顶点且价不等于4 或j 为边界顶点且价不等于3 ，则称f 为奇异顶点。非奇异顶 点称为正则顶点( r e g u i a r v e r t e x ) 。不存在奇异顶点的网格称为正则网格( r c g u l a r m e s h ) ， 或称为规则网格。 图2 2 是三角形网格正则顶点和奇异顶点的示意图。 ( a ) 正则内部顶点( b ) 奇异内部顶点( c ) 正则边界顶点( d ) 奇异边界顶点 图2 2 三危形网格正则顶点和奇异顶点示意图 ( 4 ) 细分模式 细分方法有两种典型的拓扑分裂方式：顶点分裂( 对偶型) 和面分裂( 基本型) 。 本文所有算法都建立在面分裂的基础上。 面分裂是在网格边和面上插入一定数量的新顶点，然后对每个面进行剖分，从而得 到新网格。比如在三角形网格或者四边形网格的每条边上，等份地插入r 1 个新顶点， 称为边顶点( e 一顶点) ，在每个面上则相应地插入( r 1 ) p 一2 ) 2 个面顶点( f 一顶点) ， 把网格的每个三角形分裂成，2 个三角形，或者每个四边形分裂成，2 个四边形，图23 ( b ) 是r = 2 的4 倍分裂( 4 一f o l ds p l i t t i n g ) ；图2 3 ( c ) 是，= 3 的9 倍分裂：图24 ( d ) 是r = 4 的 1 6 倍分裂。 ( a ) 初始网格( b ) 4 倍分裂( c ) 9 倍分裂 ( d ) 1 6 倍分裂 图2 。3 控制网格厦分裂示意图 定义2 , 6 从给定网格m o = ( k o ，o o ) 开始，对其依次采用某种拓扑分裂算子s 和 几何平均算子作用于m “1 = ( 丘k - i ，o “1 ) ，从而得到新网格m = ( k ，中) ，其中， k = j k “1 。o ( f ) = 群( m “1 ( 1 ) ，中。1 。) ) ，k = 1 , 2 并重复此操作从而得到网 格序列m o ，m ，m ，这一过程称为细分模式( s u b d i v i s i o ns c h e m e ) 。网格序列的极 o 细分曲面软件系统的设计与实现 限坠i m 。m 称为细分曲面( s u b d i v i s i o ns u r f a c e s ) 。m 2 ( 七 o ) 称为细分曲面的控制网格 ( c o n t r o lm e s h ) ，m 。称为细分曲面的初始控制网格( 1 1 1 i t i a 】c o n t r o l m e s h ) 。 2 2 2 细分方法的收敛性、连续性分析 由于细分曲线( 曲面) 没有整体解析表示形式，细分方法是运用细分规则对控制 网格不断细化的过程，因此它是一个迭代算法。对于任何迭代算法，一个基本问题是 该算法是否收敛。 另一方面，曲面的连续性在曲面设计中占有重要的地位，n u r b s 曲面正是由于在 任意拓扑情况下难以保证一定的连续性，从而使其应用受到一定限制，所以细分曲线 ( 曲面) 的连续性分析无论从理论还是应用角度来说都显得很重要。由于细分曲线控 制多边形的拓扑结构相对要简单得多，因此单变元细分模式的收敛性和连续性分析已 形成较完整的框架体系口1 。对于曲面( 双变元) 细分模