（运筹学与控制论专业论文）关于细分曲面造型的研究.pdf

中文摘要 近二十年来，随着三维数据采样设备的长足进步与复杂拓扑结构的曲面造型 日益普及，细分曲面己成为计算机辅助几何设计( c a g d ) 和计算机图形学( c g ) 领域 内的一个国际性研究热点之一。 细分曲面是用低分辨率的控制网格和定义在该控制网格上的细分规则来表 示自由光滑曲面的。由于细分曲面不但解决了计算机图形学中遇到的任意拓扑和 一致性表示问题，而且还保留了传统n u r b s 曲面表示所具有的局部性、仿射不变 性等良好性质，因而近年来得到广泛的应用。本文主要对历细分曲面及其扩展 进行了研究，内容包括： ( 1 ) 较全面的介绍了细分曲面造型技术及其在图形学中的应用。并列出了三 个基于三角形网格的细分模式：l o o p 细分、改进的b u t t e r f l y 细分和怕细分。 ( 2 ) 介绍了几种典型的尖特征生成方法，并再此基础上提出了一种能够重建 模型尖锐特征的怕细分算法。首先根据预设的阈值口自动标记网格中的尖锐特 征边，并计算出各个顶点的尖特征度；然后根据顶点尖特征度的不同修改原压细 分方法的几何规则，设计出相应的权值掩模( m a s k ) ；最后通过在奇数次细分时不 翻转特征边，在偶数次细分时插入边点的方法来实现尖锐特征的重建。实验结果 表明，与原撕细分方法相比i 本算法能够更好的保持模型的尖锐特征。 ( 3 ) 为了减少运算量和节省存储资源，提出了一种重建模型尖锐特征的局部 怕细分算法。在预处理过程中，只选取面向视点的网格作为能够被进一步自适 应细分的网格；在自适应细分过程中，用相邻面片的法向夹角作为控制误差来反 映细分的逼近程度是否足够；并根据预设的阈值口自动标记网格中的尖锐特征 边，重新设计尖锐特征处的权值掩模( m a s k ) 。 关键词：i 细分，尖锐特征，尖特征度，边翻转，自适应细分 a b s t r a c t a l o n gw i t ht h eg r e a tp r o g r e s s i n3 dd a mm e a s u r o m e n td e v i c ea n dt h e p o p u l a r i z a t i o no fc o m p l e x8 u r f a o gm o d e l i n g , r e c u r s i v es u b d i v i s i o nh a sb e e na r e s e a r c hf o c u si nt h ew o r l do v e rt h ep a s t2 0y e a r si nc o m p u t e ra i d e dg e o m e t r i cd e s i g n a n dc o m p u t e rg r a p h i c s s u b d i v i s i o n $ u f f a c oc a ne x p r e s sf r e es m o o t hs u r f a c et h r o u g hl o wr e s o l u t i o n c 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 i th a sb e e nw i d e l yu s e di nr e c e n ty e a r s ，f o ri tn o t o n l ys o l v e ss o m ep r o b l e m si nc o m p u t e rg r a p h i c s ，s u c ha sa r b i t r a r yt o p o l o g ya n d c o m p a t i b i l i t y ，b u ta l s or e t a i n ss e v e r a la d v a n t a g e so f t r a d i t i o n a ln u r b s ，i n c l u d i n gt h e p r o p e r t i e so fl o e a i n e s sa n da f e - i n v a r i a n c e t h i sp a p e rd e a l s 谢t l l 压- s u b d i v i s i o n a n di t se x t e n s i o n , t h em a i nw o r ki sa sf o l l o w s ： ( 1 ) t h i st h e s i ss t u d i e st h em o d e l i n ga n da p p l i c a t i o no fs u b d i v i s i o ns u r f a c e s s u b d i v i s i o nm e t h o dh a sb e c o m ea l li m p o r t a n tt o o li nc o m p u t e rg r a p h i c se s p e c i a l l yi n 3 dm o d e l i n ga n da n i m a t i o nf i e l d s t h r e ei m p o r t a n ts u b d i v i s i o ns c h e m e sb a s e do n t r i a n g u l a rm e s h e s ( l o o ps u b d i v i s i o n , m o d i f i e db u t t e r f l ys u b d i v i s i o na n d 压- s u b d i v i s i o n ) a r el i s t e di nt h ee n d ( 2 ) t h i st h e s i si n t r o d u c e sa 万一s u b d i v i s i o na l g o r i t h mt or e b u i l ds h a r pf e a t u r e s f i r s ts h a r pe d g e sa r ea u t o m a t i c a l l yt a g g e da c c o r d i n gt ot h eg i v e nt h r e s h o l d0a n d t h es h a r pd e g r e eo f e a c hv i i e xi sc o m p u t e d t h e n , b a s e do nd i f f e r e n ts h a r pd e g r e e s ， g e o m e t r i cr u l e so f 压- s u b d i v i s i o ns c h e m ea r em o d i f i e da n ds u b d i v i s i o nm a s k sa r e d e s i g n e d f i n a l l ys h a r pf e a t u r e s a r e c o n s t r u c t e d b yk e e p i n gs h a r pe d g e s n o n - f l i p p i n gi no d dr e f i n e m e n ts t e p sa n di n s e r t i n ge d g ep o i n t si ne v e nr e f i n e m e n t s t e p s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sa l g o r i t h mk e e p ss h a r pf e a t u r e sb e t t e rt h a n o r i g i n a l 压一s u b d i v i s i o nm e t h o dd o e s ( 3 ) f o rt h e + p u r p o s eo fr e d u c i n gt h ec o m p u t a t i o na n dh o l d i n gs h a r pf e a t u r e s , t h i st h e s i s p r e s e n t s al o c a l 压- s u b d i v i s i o n a l g o r i t h mt or e b u i l ds h a 叩f e a t u r e s a d a p t i v e s u b d i v i s i o ni sp e r f o r m e do n l yi nt h ea r e a sf a c i n gt ot h ev i e w p o i n ti n 吐把p r e - p r o c e s s a n di nt h ee a c ha d a p t i v es u b d i v i s i o n , w ec h o o s et h en o r m a la n g l eo ft h ea d j a c e n t f a c e sa st h ec o n t r o le r r o rt od e t e c tw h e t h e rt h ea p p r o x i m a t i o ni s s u f f i c i e n t s h a r p e d g e sa r ea u t o m a t i c a l l yt a g g e da c c o r d i n gt ot h eg i v e nt h r e s h o l d 口a n ds u b d i v i s i o n m a s k sa l - ed e s i g n e db a s e do nd i f f e r e n ts h a r pd e g r e e s k e yw o r d s ：压s u b d i v i s i o n , s h a r pf e a t u r e ，s h a r pd e g r e e 。e d g ef l i p p i n g , a d a p t i v cs u b d i v i s i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：参1 叛签字日期： b o6 年f , e l2 ，oe t 学位论文版权使用授权书 本学位论文作者完全了解叁盗盘茎有关保留、使用学位论文的规定。 特授权盘鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存，汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：毒i 飘 签字日期：l o ，年1 月加日 导师签名： 刻物j 私 j 签字日期：歹纱筇年f 月加日 天津大学硕士学位论文 第一章绪论 i i 细分方法发展概况 第一章绪论 计算机辅助设计与制造技术( c o m p u t e r a i d e dd e s i g n & c o m p u t e r a i d e d m a n u f a c t u r e ) 简称c a d c a m 技术，是计算机应用最重要的领域之一，系指利用 计算机技术完成设计过程中的信息检索、分析、计算、综合、修改及文件编制工 作。它是先进制造技术的重要组成部分，曾被美国国家工程科学院评为当代十项 最杰出的工程技术成就之一。而c a d c a m 技术的重要理论基础之_ 计算机辅助 几何设计( 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 ，简称c a g d ) 作为- - f - i 独立的学 科，研究的是计算机表示以及用计算机控制有关形状信息的问题。随着航空、造 船、机械设计和制造等现代工业的蓬勃发展，随着图形工业和制造工业迈向一体 化、集成化和网络化，随着激光测距扫描等三维数据采样技术和硬件设备的日益 完善，c a g d 学科迅速发展并越来越重要。 在c a g d 中一项重要内容就是曲面( 曲线) 造型技术，主要研究在计算机图 形系统的环境下对曲面( 曲线) 的表示、设计、显示和分析。经三十多年发展， 目前曲面造型中的曲面主要有多边形网格、隐式曲面和参数曲面等表示方法。 多边形网格模型表示方法，是最直接的表示方法，在计算机图形学诞生之时 就已开始使用，其最大优点是数学模型简单，它直接使用点，直线段和平面片来 逼近真实的形体，因此容易理解，适于绘制。但该方法表示的曲面精度、曲面光 顺性及可修改性不及参数曲面方法，从而限制了它的应用范围。 隐式曲面是通过隐函数定义的曲面，隐式曲面的表达形式比较紧凑，隐式曲 面之间的求交运算结果仍然可以用隐式表示【1 】。经过b l i n n 2 、n i s h m u r a 3 等人 的努力，隐式曲面造型技术已在一些动画造型软件、人体建模等软件中得到应用。 虽然隐式曲面具有很好的光滑性，一但是表示复杂拓扑形体时，需要用到大量基本 体素，用户对此难以有效控制，这就给交互设计带来一定的困难，所以难以进行 形体的细节造型设计。 参数曲线曲面表示是目前c a d 系统中曲面的主要表示方法，尤其是在8 0 年代后期形成的非均匀有理b 样条( n o n - u n i f o r mr a t i o n a lb s p l i n e ，简称 n u p 疆s ) 4 的理论，把有理和非有理b d z i e r 5 及非有理b 样条曲线曲面统一在 n u r b s 标准之中，使得n u r b s 成为曲线曲面描述中的最为流行的技术 6 】。1 9 9 1 天津大学硕士学位论文 第一章绪论 年国际标准组织( i s 0 ) 颁布的工业数据交换标准s t e p ，将n u r b s 作为定义工业 产品几何形状的唯一数学标准吲。 随着被设计的几何对象不断朝着多样化、特殊化、拓扑结构复杂化方向发展， 参数曲面的局限性也越来越明显。由于单一的参数曲面仅限于表示拓扑上等价于 一张纸或一张圆柱面的曲面【8 】，难以表示复杂拓扑结构的自由曲面。通常参数 曲面采用逐片构造方法来表示复杂拓扑结构的物体表面，这时候需要对曲面片进 行裁剪或直接在非规则的四边形网格上构造曲面片，无论哪种情况都要考虑片与 片之间的光滑拼接，这种裁剪或者拼接计算不仅非常费时，而且有数值误差，另 外要在曲面的接缝处保持光滑，即使是近似的光滑也是困难的【9 】。对于影视动 画领域的活动模型，则情况更是如此。这时需要一种新的曲面表示方法来有效地 表示具有任意拓扑( a r b i t r a r yt o p o l o g y ) 结构曲面。 细分( s u b d i v i s i o n ) 方法 1 0 i r e 式在这种需求推动下快速发展起来的，细分方法 是基于网格细化的离散曲面表示方法，它可以从任意拓扑网格构造光滑曲面。其 基本思想是：定义一个网格序列的极限，网格序列是采用一定的细分规则( 一般 是加权平均) ，在给定的初始网格中插入新的顶点，从而不断细化出新的网格， 重复运用细分规则，在极限时，该网格收敛于一个光滑曲线( 或者曲面) 。可以通 过下面的两个例子来具体说明。 图1 1 是对依次连接的四个顶点形成的折线进行细分，最终得到细分曲线的 过程。图1 1 ( a ) 是初始给定的控制多边形，图1 1 ( b ) 是细分一次后的多边形，在细 分过程中原有顶点位置保持不变，每相邻两个顶点间插入一个新的点。重复这样 的细分过程，可以看出曲线越来越光滑，图i - 1 ( d ) 是细分三次后的多边形。 ( a ) 初始控制多边形q ) 细分一次后多边形 ( c ) 细分两次次后( d ) 细分三次后 图i - i曲线的细分过程 图1 - 2 表示的是网格细分过程。图l - 2 ( a ) 是给定的初始控制三角形网格，图 1 - 2 是细分一次后的三角形网格，在细分过程中，每条边相邻两个顶点问插入 一个新的点，细分后新的顶点位置根据细分几何规则确定，并将原来的一个三角 形面分成四个面，重复这样的细分过程，可以看出曲面越来越光滑，图1 2 ( d ) 是 天津大学硕士学位论文 第一章绪论 细分五次后的网格光照效果图。简单地说，细分曲面( s u b d i v i s i o ns u r f a c e s ) 是不 断细化的网格极限。 ( a ) 初始控制网格细分一次后的网格( c ) 细分五次后的网格 图1 - 2 三角网格的细分过程 细分方法是把参数曲面的逐片构造方法推广到任意拓扑结构的网格模型，即 使模型是活动的，其光滑连接也能被自动地保证。因为在不规则拓扑处置需采用 特殊的细分规则就可以了【9 】，它克服了参数曲面处理任意拓扑曲面时存在的困 难。 与现有其它造型方法相比，细分方法具有如下显著特点 1 1 】； ( 1 ) 任意拓 b ( a r b i u a r yt o p o l o g y ) ：传统曲面造型方法遇到复杂物体造型时往 往束手无策，因为其控制顶点往往具有复杂的网格拓扑，这对于利用张量积方法 构造的参数曲面而言，拼接或剪裁( t r i m m i n g ) 的困难是显而易见的。但是细分方 法不存在这样的问题，部分原因是它的参数空间是初始网格本身。 ( 2 ) 可伸缩性( s e a l a b i l i t y ) ：由于细分曲面递归生成，是一个不断细化的过程， 其多分辨率分析有坚实的数学基础，特别适合于层次细节( l o d ) 技术，从而可充 分利用有限的硬件资源。 ( 3 ) 表示的一致性( 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 ) ：这里所说的一致性是指细分 法把曲面片与多面体表示统一起来，使得造型系统有了统一处理曲面和多面体表 示的手段。 ( 4 ) 数值稳定性( n u m e r i c a lm b i l i t y ) ：线性细分方法是一个迭代过程，有很 好的数值稳定性，可用于有限元方法。 ( 5 ) 简单性( c o d es i m p l i c i t y ) ：易于实现，效率也很高： 1 2 细分曲面的应用及发展趋势 随着对细分理论研究不断深入，针对细分曲面的应用研究也在多分辨分析、 计算机动画、计算机图形学、科学计算可视化、数值计算、医学图像处理以及去 曲面造型等领域逐步展开，细分曲面应用技术研究现状及发展趋势主要表现在如 天津大学硕士学位论文 第一章绪论 下几个方面： ( 1 ) 基于细分的多分辨率分析 多分辨率分析的基本思想是把信号表示成低分辨率信号，同时生成一些能在 不同尺度上反映该信号的细节【1 2 】。多分辨率模型( m u l t i r e s o l u f i o nm o d e l ) 也是一 种曲面表示方法，它支持物体表面从粗糙到细致的各个层次的模型重构 1 3 1 。基 于细分的多分辨率分析，是把网格曲面看作是某一细分方法进行若干次细分后得 到的结果，那么该庞大的网格曲面就可以用一个简单的初始网格和若干细分规则 来表示1 1 4 。细分方法通过拓扑规则提供了合理的加密采样模式，通过几何规则 提供了合理的预测函数。每次采样与预测之间存在误差，这就是多分辨率分析需 要被保存的细节。这种扩展的细分曲面，称为多分辨率曲面( m u l t i r e s o l u t i o n s u r 骶) 。 在多分辨模型上可以根据需要在不同分辨率的控制网格上对控制顶点进行 修改，能够在局部修改曲面形状和全局修改曲面形状之间进行折衷选择，从而达 到不同的形状效果，这种曲面修改方式称为细分曲面多分辨编辑 1 5 1 。 与计算机网络的结合，将是基于细分的多分辨率曲面的一个重要研究方向。 ( 2 ) 三维动画造型 目前细分方法在影视动画、游戏等行业中的应用已相当普遍。这主要是因为， 用v o r b s 等参数曲面表示人的手、头和衣服皱褶等复杂拓扑对象时，需要由多片 曲面拼成，因此需要求解复杂的相容关系，当对象运动时原来的相容条件被破坏， 需要重新求解相容条件或者采用大量的手工操作以消除片之间的缝隙。对细分曲 面来说，由于细分曲面定义在任意拓扑网格上，所以不存在上述问题。曲面的光 滑性也由细分方法自动保证。 目前许多三维造型软件如m a y a 、l i g h t w a v e 、a n i m a t i o nm a s t e r 、p r m a n 、 t r u e s p a c e 等都将细分曲面作为一种曲面表示方法。在动画造型中需要解决的主要 问题是特征生成、形状保持以及纹理映射。基于细分的变形( m o r p h i n g ) 技术是该 方向上的研究热点，地形地貌的生成与绘制也是实时动画中重要研究内容 1 6 。 随着可编程图形加速硬件的出现 1 7 ，细分曲面的硬件实现 1 8 将进一步提 高细分速度，同时也为细分曲面在三维动画与游戏中的应用提供更好的技术支 持。 ( 3 ) 医学图像重建与模拟 q i nh o n g 等人提出将动态细分曲面( d y n a m i cs u b d i v i s i o ns u r f a c e ) 造型方 法用于医学图像重建与受力变形模拟 1 9 3 。首先从三维核磁共振切片数据拟合小 脑的c a t m u l l - c l a r k 细分曲面初始控制网格，然后建立拉格朗日动态力学模型， 在此模型的适当部位施加外力，通过计算模拟出不同外力下的的脑组织的变形结 天津大学硕士学位论文 第一章绪论 果。该方法结合了细分方法对任意拓扑结构形体建模的灵活性与直观交互动态模 拟曲面变形的两方面优点。k a i h u a iq i n 也研究了类似的其它医学组织的细分曲 面图像重建和模拟方法 2 0 。 ( 4 ) 工程曲面造型 虽然细分曲面在动画造型系统中已经获得了广泛的应用，但是在工程曲面造 型中的应用才刚刚起步，这是因为两种应用领域所追求的目标曲面要求不一样， 动画造型希望模型具有较好的光顺性等视觉效果；工程曲面造型要求模型具有较 高的几何精度和连续性等内在质量。这方面的应用研究主要包括：细分曲面的拟 合、布尔运算以及用细分方法解决参数曲面造型问题。 在c a d 领域中，常通过插值和逼近手段建立目标曲面。在细分曲面插值方面， 已有的细分曲面插值方法可以分为两类：一种是构造新的细分规则或修改已有的 几何规则，使得细分曲面经过初始控制网格的部分或全部顶点；另一种则是利用 已有细分方法，通过构造适当的初始控制网格使细分曲面满足插值条件。虽然插 值型细分曲面( 如蝶形细分) 具有天生的插值能力，但是插值细分曲面的光顺性并 不理想。h a l s t e a d 等人也对逼近型的c a t m u l c l a r k 细分曲面上的光顺插值进行 了研究 2 1 ，不过该方法所求出的能量在奇异点处不收敛。n a s r i 提出插值于 d o o s a b i n 细分曲面顶点法向量的细分曲面插值方法 2 2 ，l e v i n 通过组合细分 ( c o m b i n e ds u b d i v i s i o n ) 2 3 构造了能插值任意曲线的细分方法 2 4 ，并将其应 用于n 边孔洞的修补问题 2 5 。 在细分曲面逼近方面，多数细分曲面逼近方法与多分辨率分析方法类似，其 局限性是初始控制网格的生成还没有能够做到完全自动化，其中h o p p e 2 6 和 s u z u k i 2 7 对点云数据的细分衄面逼近进行了一些有益的探索，但是拟合的细分 曲面不能准确反映模型的细节特征。 2 8 研究t c a t m u l l - c l a r k 细分的点云数 据b 样条曲面逼近方法。 为了与实体造型系统相融合，细分曲面的求交和裁剪一直是有待于解决的难 题。仿造参数衄面的离散求交方法，n a s r 曾提出一种基于d o o s a b i n 细分曲面边 界生成方法的d o o - s a b i n 曲面求交算法 2 9 ，只是获得近似的细分曲面交线。利 用细分曲面的多分辨率特性，b i e r m a n n 等人对细分曲面的逻辑运算作了尝试性研 究 3 0 。 由于传统细分方法起源均匀样条，所以无法精确表示工业设计中常用的旋转 曲面和二次曲面。s e d e r b e r g 等人提出的非均匀有理细分方法虽然可解决以上表 示问题，不过非均匀有理细分方法始终存在实现复杂以及数值计算的不稳定性问 题，文献 3 1 对其进行了连续性分析。虽然m a i l l o t 3 2 和z h a n g 3 3 提出了能生 成旋转曲面的细分方法，但是细分算法都相当复杂。用细分曲面精确表示几何模 天津大学硕士学位论文第一章绪论 型仍然是细分曲面应用研究的重要内容。 用细分方法解决其它曲面造型方法中的问题，也是一个值得关注的应用方 向，l i 用c a t m u l l - c l a r k 细分较方便地解决了双三次b 样条曲面片的混合与填充问 题。 1 3 本文的研究内容和论文的组织 根据前面的讨论可以看出，三角网格模型的表示在曲面造型技术中非常有价 值。本文主要就三角网格模型的细分及其在三维造型中的应用作了详细论述。主 要内容包括： 1 介绍了曲面细分技术的发展及其国内外的相关工作；对各种曲面细分算法做 了较为详细的论述。 2 提出了一个保持尖锐特征的3 细分算法。其特点是：在原3 细分算法的基 础上，引入尖特征度，根据顶点尖特征度的不同修改原压细分方法的几何规 则，设计出相应的权值掩模( m a s k ) ；最后通过在奇数次细分时不翻转特征边， 在偶数次细分时插入边点的方法来实现尖锐特征的重建。与原压细分方法相 比，本算法能够更好的保持模型的尖锐特征。 3 提出了一种重建模型尖锐特征的局部怕细分算法。在保持尖锐特征的3 细 分算法的基础上，只选取面向视点的网格作为被进一步自适应细分的网格， 这种方法能够用较少的存储量有效保持模型的尖锐特征。 本文中的组织结构如下：第二章对曲面细分及其方法作了系统的总结，分析 了目前研究的热点和存在的问题；第三章给出了一种保持尖锐特征的3 细分算 法；第四章介绍了局部自适应细分，并提出了一种重建模型尖锐特征的局部3 细 分算法；第五章是本文的结束语。 天津大学硕士学位论文 第二章细分曲砸造型 2 1 细分理论基础 2 1 1 基本概念 第二章细分曲面造型 细分曲面是多边形网格的极限状态，在实现时也只能把它当作某一细分层次 的多面体来处理，可以说细分方法处理的就是多边形网格，因此有必要对多边形 网格的有关概念作较为形式化的处理【3 4 】。 ( 1 ) 与网格相关的基本概念 定义2 1 由顶点、边和面构成的整个或部分多面体表面称为网格( m e s h ) 。 如果所有网格面均为三角形，称其为三角网格( t r i a n g u l a rm e s h ) ；如果所有网 格面均为四边形，称其为四边形网格( q u a d r i l a t e r a lm e s h ) ；如果网格面中包含 有不同类型的多边形面，则称为任意多边形网格( a r b i t r a r i l yp o l y g o n a lm e s h ) 。 定义2 2 如果网格的某一条边只属于一个面，称这条边为边界边( b o u n d a r y e d g e ) ；如果一个顶点处在边界边上则称此顶点为边界点( b o u n d a r yv e r t e x ) ；至 少包含一条边界边的面称为边界面( b o u n d a r yf a c e ) 。非边界的顶点、边和面分 别称为内部顶点( i n t e r n a lv e r t e x ) 、内部边( i n t e r n a le d g e ) 和内部面( i n t e r n a l f a c e ) 。 定义2 3 含有边界边的网格称为开网格( o p e nm e s h ) ，否则称之为闭网格 ( c l o s em e s h ) 。 定义2 4 3 5 对于网格中的任意一个顶点所，与其直接相连的边的数量称 为顶点髀的价( v a l e n c e ) ，记为。在图2 一l ( a ) 中，顶点2 的价为5 。 定义2 5 3 6 对于网格中的任意两个顶点形和，如果存在最小的整数以， 使得边序列岛，易，e 满足： 巧，巧分别与蜀和e 相连；。 易与甄i 相连，其中1s ，s 疗一】。 则称珂为顶点巧与之间的距离。在图2 - 1 ( a ) 中，顶点2 与顶点5 之间的距离为3 定义2 6 对于网格中的任意一个顶点k ，以k 为中心，所有到k 的距离小 于k 的顶点所构成的子网格，称为顶点矿的k 一邻域( k - n e i g h b o r h o o d ) 。图2 1 ( b ) 所示的是图2 - 1 ( a ) 中顶点3 的卜邻域。 定义2 7 对于网格中的任意一个多边形r ，以丁为中心，所有到多边形r 的 天津大学硕士学位论文第二章细分曲面造型 距离小于k 的顶点所构成的子网格，称为多边形r 的七一邻域。图2 1 ( e ) 所示的是 图2 _ l ( a ) 中三角形r 的卜邻域。 ( a ) 顶点的份( b ) 顶点的l 一邻域c ) 多边形的1 - 邻域 图2 1 定义2 4 2 3 的示意图 定义2 8 对于三角网格m ，如果k 为内部顶点且价不等于6 或巧为边界点 且价不等于4 ，则称k 为奇异顶点( 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 ，如果k 为内部顶点且价不等于4 或k 为边界顶点且价 不等于3 ，则称k 为奇异顶点，否则称为正则顶点。 不存在奇异顶点的网格称为正则网格( r e g u l a rm e s h ) ，或称为规则网格。 图2 - 2 是三角网格正则顶点和奇异顶点的示意图。 镫1 愈由旬 ( a ) 正则内部顶点( b ) 奇异内部顶点( c ) 正则边界顶点( 由奇异边界顶点 图2 - 2 三角网格正则顶点和奇异顶点示意图 ( 2 ) 拓扑分裂算子 细分方法有两种典型的拓扑分裂( s p l i t t i n g ) 方式 加) ：基于顶点的拓扑分裂规 则，称为对偶分裂算子( d u a ls p l i t t i n go p e r a t o r ) ；基于面的拓扑分裂规则，称为基 本分裂算子( p r i m a ls p l i t t i n go p e r a t o r ) 。 基于顶点的拓扑分裂，是在原网格顶点处拓扑分裂后，生成一个新的多边形 面。对于价为的内部顶点巧，如图2 _ 3 所示，将顶点巧分裂出一1 个顶点， 并依次连成一个边多边形( 如图2 - 3 ( b ) 所示，此处为三角形) ，此边形称为 新网格的顶点面( 矿- 面) 。对于内部边e ( e ，巧) ，一定有两个相邻面( 记为互和 天津大学硕士学位论文第二章细分曲面造型 e ) ，假设k 、巧分裂的与e 和e 相对应的顶点分别为、圪和、， 那么连接、和形成的四边形面称为新网格的边面( e 一面) 。原 网格膨中的多边形面f 上的每个顶点都分裂出一个新顶点与之对应，把这些分 裂出来的新顶点依原来的顺序相连，就生成一个与面f 边数相同的新的面，该面 称为面面( f 一面) 。 ( a ) 初始网格( b ) 细分后的控制网格 图2 - 3 三角网格正则顶点和奇异顶点示意图 与基于顶点的拓扑分裂不同，基于面的拓扑分裂是在原网格的边和面上插入 一定数量的新顶点，然后对每个面进行拓扑剖分，从而得到新网格。比如在三角 网格或者四边形网格的每条边上，插入，一1 个新顶点，称为边点( e 一顶点) ，同 时在每个面上相应地插入( r 一1 x r 一2 ) 2 个面点( f 一顶点) ，从而把网格的每个三 角形分裂成，2 个三角形，或者每个四边形分裂成，2 个四边形。 图2 - 4 ( b ) 是，= 2 的4 倍分裂；图2 - 4 ( c ) 是r = 3 的9 倍分裂；图2 4 ( d ) 是 ，= 4 的1 6 倍分裂。 图2 - 4 ( a ) 初始网格c o ) 4 倍分裂( c ) 9 倍分裂( d ) 1 6 倍分裂 天津大学硕士学位论文第二章细分曲面造型 定义2 9 3 6 从网格m ( o 开始，对其依次采用某种拓扑分裂规则和几何平 均规则对其进行细化，从而得到系列网格m ( “，m ( 1 ) ，膨n ，。网格序列的极 限j i m m ( t 称为细分曲面( s u b d i v i s i s u r f a c e ) 。m ( 七 o ) 称为细分曲面的控制 x - - h o 网格( c o n t r o lm e s h ) ，m ( o 称为细分曲面的初始控制网格( h i t i a lc o n t r o lm e s h ) 。 拓扑分裂规则( t o p o l o g i c a ls p l i t t i n gr u l e s ) 和几何平均规则( g e o m e t r i c a v e r a g i n gr u l e s ) 的集合称为细分方法( s u b d i v i s i o ns c h e m e ) 。本文在表示与细 分层次有关的控制网格m 、控制顶点矿耻等符号中，用带括号的上标( 七) 来表 示细分层次，以便与幂次相区别。 ( 3 ) 细分方法的分类 在上述概念的基础上，可以对众多的曲面细分方法归类j 因为细分过程就是 网格不断细化( r e f i n e m e n t ) 的过程，它有两个操作步骤：一是拓扑分裂，所对应 的方法称为拓扑规则。二是计算所有顶点的新位置，这一过程称为几何位置平均 ( a v e r a g i n g ) ，所对应的方法称为几何规则。拓扑规则决定了细分后网格的几何 元素的数量呈几何级数增加的幂次。几何规则决定了细分后曲线、曲面的极限性 质。所以，构成一种细分方法的三个基本要素是：拓扑规则、几何规则和控制网 格。 根据三个基本要素的不同，细分方法有许多种分类，下面就其中几种重要的 分类方法简单说明如下： 根据拓扑分裂规则的不同，细分方法可以分为基本型( p r i m a l ) 细分和对偶型 ( d u a l ) 细分 3 7 。 根据几何规则是否与细分层次相关，细分方法可分为静态( s t a t i o n a r y ) 细分 和动态( d y n a m i c ) 细分 3 s 。 根据极限细分曲面是否插值初始控制顶点( 与几何规则有关) ，细分方法可以 分为插值细分( i n t e r p o l a t o r ys u b d i v i s i o n ) 和逼近细分( a p p r o x i m a t i n g s u b d i v i s i o n ) 3 9 。 按照细分所生成的控制网格的形状，细分方法可区分为基于三角网格的细 分、基于四边形网格的细分、基于三角形和四边形网格的混合细分( h y b r i d s u b d i v i s i o n ) 4 0 等等。 基于上述分类方法，下表列出了目前常见的几种曲面细分方法所属类别及其 主要特性。随着细分理论研究的不断深入，还会有新的细分类型出现。 天津大学硕士学位论文 第二章细分曲面造型 表2 - 1 常见曲面细分方法及其主要特性 细分方法类别控制静态顶点基本逼近连续性提出 网格 倍数 ，时间 形状 动态速度对偶插值( 年) c a t m u l l - c l a r k四边形 静态 2 基本逼近正则点处 1 9 7 8 为主的c 2 ( 奇异 多边形点处c 1 ) d o o s a b i n 四边形静态 2 对偶逼近 1 9 7 8 为主的 多边形c 1 割角细分四边形动态 2 对偶逼近 c 21 9 8 7 l o o p 三角形静态 2基本逼近 c 2 ( c 1 ) 1 9 8 7 碟形细分三角形静态2基本插值c 11 9 9 1 m i d p o i n t 四边形静态 2 对偶逼近 c 11 9 9 3 n u r s s 四边形动态 2 基本根据 c 2 ( c ) 1 9 9 8 权值 括细分三角形静态压基本逼近 c -2 0 0 0 插值i 细分 三角形静态互基本插值 c -2 0 0 0 禾8 细分 特殊三静态互基本逼近 c 4 ( c - ) 2 0 0 0 角网格 蜂窝细分六边形静态订对偶逼近 c 1 2 0 0 2 混合细分三角形静态 2 基本逼近 c 12 0 0 2 四边形 三重细分三角形静态 3 基本逼近 c 2 ( c ) 2 0 0 2 天津大学硕士学位论文第二章细分曲面造型 2 1 2 细分方法的收敛性、连续性分析 由于细分曲线( 曲面) 没有整体解析表示形式 2 ，细分方法是运用细分规 则对控制网格不断进行细化，因此它是一个迭代算法。对于任何迭代算法，一个 基本问题是该算法是否收敛。 而连续性在几何造型中占有重要的位置，n u r b s 正是由于在任意拓扑情况下 难以保证一定的连续性，从而使其应用受到一定限制，所以细分曲线( 曲面) 的连 续性分析无论从理论还是从应用角度来说都是非常重要的。由于细分曲线控制多 边形的拓扑结构相对于细分曲面来说要简单得多，因此曲线( 单变元) 细分方法的 收敛性和连续性分析己形成比较完整的体系。对于曲面( 双变元) 细分方法，当控 制网格为正则情形时。细分曲面通常是样条曲面的推广，其收敛性和连续性分析 已基本解决，所以细分曲面在奇异顶点处的收敛性和连续性成为研究的重点。对 于线性的静态细分方法，从迭代细分得到的局部细分矩阵可用来对极限行为进行 分析。大多数情况下得到的细分矩阵具有轮换矩阵【4 l 】结构，运用离散f o u r i e r 变换可以简化细分矩阵特征值的求解，从而可以方便地进行细分迭代收敛性分析 和细分曲面几何量计算。下面首先简要介绍轮换矩阵和离散f o u r i e r 变换。 ( 1 ) 轮换矩阵 定义2 1 0 1 4 1 设，o ，。c ，这里c 表示复数域，则下面的矩阵 上= f of if ： 如矗 l m | “i q l l1 21 ， 称为数组瞩，一1 ) 的轮换矩阵( c i r c u l a n tm a t r i x ) ，记为a ，c 瓯，) 。 矩阵中的每一行由上一行的元素右移一个位置，并将溢出的元素移到左边第一列 位置而组成。 定义2 1 1 4 1 轮换矩阵 ，= 0l0 o o 0l 0 o 0o l loo o 称为循环置换矩阵或基本轮换矩阵或移位矩阵( s h i f tm a t r i x ) 。 定理2 1 4 1 设p e r 是基本轮换矩阵，则有 p = i ，其中，为单位矩阵 1 2 ，。，。l o k o ；乇 天津大学硕士学位论文 第二章细分曲面造型 p 的特征值为以= p4 ，其中i = 4 ：i ，七= 1 ，栉 p 与任一拧阶轮换矩阵工可交换，即 p l = l p n 阶矩阵工为轮换矩阵的充要条件是 三可表示为三= i k p ，其中p o = j 定理2 2 设轮换矩阵三= c i r c ( 1 0 ，i i ，) ，l a j l 的特征值是 以= 厂( 以) | j = l ，厅 而且属于丑的特征向量r k 可取为 r k = ( 1 ，i ，露，卢，) k = 1 ，撑 其中，厂( f ) = 1 0 + l i t + l ：t 2 + + 厶一l t ”1 ( 2 ) 离散f o u r i e r 变换 对于离散函数，z ，) ，其f o u r i e r 变换定义为 4 2 一n - i 丝堕 g j = a e ”，j = 0 ，”一1 ( 2 1 ) k = 0 如果( g 。，9 1 ，一，g 。_ 1 ) 是离散函数饼，石，z i ) 的f o u r i e r 变换，则 ，k 一i 2 z 茸 乃= 去即下，歹= o ，“ ( 2 哪 这就是离散函数( g o ，蜀，g 。) 的逆f o u r i e r 变换。 把式( 2 2 ) 代入下面的轮换矩阵 s = 兀工q l 。氛 j nl 盹 s = u d 扩7 1 0 ) n - i ： m o , - t ) 2 d = a d g ( g o ，g l ，岛- 1 ) ； 驴7 是u 的共轭转置。 刭 t 2 x ，它是关于国= e ”的v a n d e r m o n d e 矩阵： 。毽：矿 一| 打 = u 中 得 其 天津大学硕士学位论文 第二章细分曲面造型 由于u u 7 = i ，即s 与d 是相似矩阵，它们有相同的特征值。 ( 3 ) 线性静态细分方法的细分矩阵 设初始控制网格m ( o 的某个控制顶点子集为 ，( o ) = ( ”，婵，皤，p p ，k