（机械制造及其自动化专业论文）细分曲面造型技术及其在cad中的应用.pdf

华中科技大学硕士学位论文 摘要 ( 几何造型是c a d 中的关键技术之一，现代工业产品设计对c a d 系统处理复杂拓 扑形体的能力提出了越来越高的要求。虽然以n u r b s 为代表的造型表示方法已经取 得了非常成功的应用，但它仅适于表示规则拓扑形体( 单个补片) ，拼接和裁剪还 存在很大困难。细分曲面技术是一种基于样条可细化性质基础上的以网格细分为特 征的离散造型方法，具有表示的任意拓扑性，光滑保证性，计算简单性等传统方法 难以比拟的优点，是目前国际上计算机图形学领域的最新技术。y 本文在对细钎曲面理论的研究的基础上，认为细分曲面技术是造型理论从纯代 数f 微积分) 方洼到几何化方法，从传统的准确数学描述到数值离散化描述的重要 转变，是c a d 造型技术革新的重要趋势：本文提出了将细分曲面技术应用到c a d 造 型技术的新思路和新方法。主要研究工作包括： 1 研究了细分曲面的基本理论。阐述了曲线细分的产生方法和矩阵描述，分析 了细分和b 样条之间的关系，以及细分曲线的收敛性、连续性等特性：研究和比较 了细分曲面的不同规则，分析了细分曲面的性质和特征。 2 探讨了细分曲面造型的具体方法，研究了细分曲面的边界控制、角点法线控 制、曲面剪裁、靠尔运算等关键技术。 3 提出了细分曲面和传统造型方法相融合实现造型的策略。结合传统造型的各 种方法，对比了两者的优缺点，探讨了两种方法相融合实现造型的具体方法。 4 分析了细分曲面算法的数据结构特点，解释了细分算法的实现过程，开发了 细分曲面造型的相关软件，实现了网格细分、真实感显示、网格编辑、法线控制等 功能。( 实例验证了细分造型方法在复杂实体造型中的强大优势，以及其与传统造型 方法相结合的应用前景卵 关溉叭a d ，等警箩分秀，细嬲u 域 华中科技大学硕士学位论文 a b s t r a c t g e o m e t r ym o d e l i n gi s o n eo fc o r et e c h n o l o g i e so fc a d ( c o m p u t e ra i d e dd e s i g n ) m o d e mi n d u s t r y p r o d u c td e s i g nr e q u i r e s m o r e p o w e r f u l l c a ds y s t e mt o r e p r e s e n t c o m p l e xt o p o l o g yo b j e c t s a l t h o u 【g h c l a s s i c a ls u r f a c e s r e p r e s e n t a t i o n m e t h o d sl i k e n u r b s ( n o n u n i f o r mr a t i o n a lb s p l i n e ) e t c h a v eg a i n e dg r e a ts u c c e s s ，t h e s em e t h o d s p o s s e s ss o m es h o r t c o m i n g s ，f o re x a m p l e ，t h e ya r en o ta b l et om o d e la r b i t r a r yt o p o l o g y s m o o t hs u r f a c e s ，a n ds u r f a c e st r i m m i n ga n dp a t c h i n ga r ea l s od i f f i c u l t s u b d i v i s i o ni sa d i s c r e t e m o d e l i n gm e t h o d ，w h i c h i sb a s e do n r e f m a b i l i t y o f b s p j i n e a n dh a s c h a r a c t e r i s t i c so fm e s hr e f i n e m e n t a san e wt e c h n o l o g yi n c o m p u t e rg r a p h i c sa n d c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，s u b d i v i s i o ni sc o m p u t a t i o n a l l ye f f i c i e n ta n dh a sa b i l i t y t om o d e la r b i t r a r yt o p o l o g y ( p i e c e w i s e ) s m o o t hs u r f a c e s ，a si s d i f f i c u l t l ya t t a i n e dt h r o u g h t r a d i t i o n a lm e t h o d s b a s e do nr e s e a r c h e so ns u b d i v i s i o ns u r f a c et h e o r y w ec o n s i d e rt h a t s u b d i v i s i o n t e c h n o l o g yi st h et r a n s i t i o no fm o d e l i n gt h e o r i e sf r o mp u r ea l g e b r a i cm e t h o d t og e o m e t r y m e t h o d ，i no t h e rw o r d s ，f r o ma c c u r a t em a t h e m a t i cr e p r e s e n t a t i o nt on u m e r i c a id i s c r e t e r e p r e s e n t a t i o n ，a n di ti sb e c o m i n go n eo fi m p o r t a n tt r e n d so f i n n o v a t i o ni nc a d m o d e l i n g t e c h n o l o g y i nt h i st h e s i s ，s o m en e wi d e a sa n dm e t h o d so na p p l i c a t i o no fs u b d i v i s i o n s u r f a c e si nc a d s y s t e ma r ep r o p o s e d t h e r ea r ea sf e l l o w s ： 1 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 f s 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 n s p l i n e a n ds u b d i v i s i o n ，a n dc 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 2 s o m es u b d i v i s i o nm o d e l i n gm e t h o d sa r ep r e s e n t e d s e v e r a lk e y t e c h n i q u e s ，s u c ha s ， n o r m a lc o n t r o l ，i n t e r p o l a t i n gb o u n d a r i e s ，t r i m m i n ga n db o o l e a n so p e r a t i o no fs u b d i v i s i o n s u r f a c e sa r es t u d i e d 3 an e wm o d e l i n gm e t h o dc o m b i n e ds u b d i v i s i o ns u r f a c e sw i t ht r a d i t i o n a lm o d e l i n g i s d e v e l o p e d n l ea d v a n t a g e sa n dd i s a b v a n t a g e so fe a c ha p p r o a c h a r ee x a m i n e d t h e c o m b i n e d t e c h n i q u e sa r es t u d i e d 4 d a t as t r u c t u r e sf o ri m p l e m e n t i n gs u b d i v i s i o ns u r f a c e sa r ea n a l y z e d ，a l g o r i t h m so f s u b d i v i s i o np r o c e s sa r ei n t r o d u c e d ，a n dap r o t o t y p es o f t w a r es y s t e mf o rs u b d i v i s i o n m o d e l i n g i s d e v e l o p e d ，w h i c hc a r r y s o u ts o m ef u n c t i o n ss u c ha s r e a l i t yr e n d e r i n g ， s u b d i v i s i o ns u r f a c e s ，m e s h e se d i t i n g ，n o r m a lc o n t r o l ，e t c m o d e l i n gp r o c e s s e si nt h e s o f t w a r ep r o v et h a ts u b d i v i s i o nm o d e l i n gh a ss t r e n g t h s0 nm o d e l i n gc o m p l e xo b j e c t s ，a n d w i l lb ew i d e l yu s e di nc a d s y s t e m 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 ，m o d e l i n g ，b s p l i n e , s u b d i v i s i o ns c h e m e , s u b d i v i s i o nr o l e ，b o u n d a r y 卜 ， 华中科技大学硕士学位论文 1 绪论 i 1 引言 随着计算机技术的发展和普及，c a d ( c o m p u t e ra i d e dd e s i g n ) 技术已日渐成为 现代制造、建筑设计等领域中不可或缺的重要工具。而作为c a d 技术核心的几何造 型技术也经历了从简单到复杂的逐渐完善的过程。从最初的二维线框绘图，到三维实 体造型，再到特征建模、变量化建模，现代的造型技术已经可以处理一些相当复杂的 几何模型了。但它也还不是完美无缺的，对于拓扑关系复杂的自由曲面实体，目前的 c a d 系统处理起来仍有一定的困难。 在目前的c a d 系统中，几何模型主要有三种层次的建立方法，即线框、曲面和 实体，它们具有上下兼容的层次关系。线框构成曲面的边界，馥面又构成实体的边界。 常用的产品几何模型一般会兼用线、面、体三种手段。而其中曲面造型又是最重要的 部分，不管是表示传统意义上的四方体、球体等规则曲面形体，还是地形地貌描述、 人体器官造型和c t 图像三维重建，服装设计、制鞋、虚拟视景生成等都要用到曲面 造型技术【”。 经过三十多年的发展，曲面造型现在己形成了以有理b 样条曲面( r a t i o n a l b s p l i n es u r f a c e ) 参数化特征设计和隐式代数曲面( i m p l i c i ta l g e b r a i cs u r f a c e ) 两类方法 为主体，以插值( i n t e r p o l a t i o n ) 、拟合( f i n i n g ) 、逼近( a p p r o x i m a t i o n ) 这三种手段为骨架 的几何理论体系。非均匀有理b 样条( n u r b s ) 方法成为现代曲面造型中最为广泛流 行的技术。它可以精确地表示二次规则曲线曲面，从而能用统一的数学形式表示规则 曲面与自由曲面：具有可影响曲线曲面形状的权因子，使形状更宜于控制和实现。国 际标准化组织o s o ) 于1 9 9 1 年颁布了关于工业产品数据交换的s t e p 国际标准，将 n u r b s 方法作为定义工业产品几何形状的唯一数学描述方法。 n l 承b s 方法虽然在7 - 业造型和动画制作中得到了广泛的应用，但其定义曲面的 方法本身注定了它有些固有的局限性。单一的n q s r b s 曲面与其他参数曲面一样， 仅限于表示在拓扑上等价于一张纸、一张圆柱面或一张圆环面的规则曲面，不能表示 如人的头、手，或服饰、自然花卉等复杂的任意拓扑结构的血面。如果用n u r b s 的补 片柬生成这些复杂曲面，目前确实已经存在一些商用系统如a i i a s - w a v e f r o n t 和 s o f i l m a g e 等可以作到这一点，但是也会遇到以下困难：修剪计算复杂，而且有数值 误差：保持曲面的拼接处的光滑，即使是近似的光滑也是困难的。如果模型是活动的 的话，情况更是如此。 而在现代产品的设计生产中，除了对产品的功能要求以外，还要考虑产品外观的 艺术性和观赏性。这就会经常遇到一些拓扑关系非常复杂又有光滑性要求的形体，如 动物模型、复杂花纹、现代艺术造型等( 类似图1 1 中的例子) 。对于这类具有雕塑 曲面性质的形体，现代数控加工、精密铸造等先进制造技术又有能力将其制造出来， 但由于目前n u r b s 等造型方法的局限性，其设计和修改仍是一个难题。 华中科技大学硕士学位论文 图1 i 复杂拓扑几何形体实例。 近年束，细分曲面( s u b d i v i s i o ns u r f a c e ) 技术的出现引起了广大c a g d ( c o m p u t e r a i d e dg e o g r a p h i cd e s i g n ) 、c a d 研究人员的关注。细分曲面是一种离散性质的造型 方法，与传统的连续造型相比，大有后来居上的创新之势。细分曲面有潜力克服 n u r b s 曲面的两个困难，它们将传统的样条补片推广为任意拓扑的结构，无须修剪 和拼续，模型的平滑度被自动地保证。而且，由于细分是基于递归的结构，可以非常 自然的实现分级渲染和误差范围内的逼近，特别适于多分辨率表示。同时它还具有有 限元分析所要求的良好特性、适于3 d 曲面的数据重建以及计算简单高效等优点口l 。 目前，该技术尚未完全成熟，但其在c a g d 、c a d 领域的发展前景已得到广大 图形工作者的认可，有可能成为造型技术革新的核心技术。各大涉及造型的软件公司 甚至包括m i c r o s o f t 、i n t e l ，i b m 等都对细分造型给以了非常高的重视，细分造型的原 理已经在高端动画软件和许多商业造型软件如p i x a r ，m a y a , m i r a i ，3 ds t u d i om a x ， l i g h t w a v e 等软件中使用”i 。 在c a d 系统中。目前还没有正式的商业版本应用细分曲面技术，但由于细分造 型所具备的优良特性，其在未来三维c a d 系统中的应用是必然的。如果我们的图形 工作者能够抓着现在的有利时机，迅速研究和掌握这一世界领先的技术成果，将能为 我国的c a d 系统改变落后局面、走向世界，创造有利的条件。本文的研究目的就是 想利用细分曲面，这一c a g d 领域的国际先进研究成果，结合目前c a d 系统的技术 现状，探索细分曲面在c a d 系统中的应用方法，丰富c a d 系统造型方法，为我国 的c a d 事业作一定的贡献。 1 2 国内外研究现状 在当前的c a d c a m 系统中，b 样条f b s p l i n e ) 曲线曲面已成为几何造型的核心 部分，其中非均匀有理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 r b s ) 已成为曲 线曲面描述的最广泛的数学方法，而且在各种国际标准中成为了图形交换中描述工业 产品几何形状的唯一数学方法。 一般的非有理方法都采用张量积的参数多项式与分段参数多项式描述曲面的【4 j 。 一般n u r b s 曲面已非张量积曲面，但仍可以看作张量积曲面的推广，这种曲面片在 2 华中科技大学硕士学位论文 实现拼接时通常都非常困难。同时，目前c a d 系统中的曲面几乎都是定义在矩形域 中，这就导致了所谓的n 一边域曲面问题。由于现有c a d 系统中的曲面表达形式和 主要操作( 如求交、过渡面生成等) 大多基于四边域曲面以及构造n 一边域曲面的复 杂性这两个原因，使得n 边域曲面的应用遇到了很大的困难。例如，将一个n 变域 曲面并入基于四边域曲面的c a d c a m 系统中时，必须对基于四边域曲面的求交程 序加以改进以便处理有关n 边域曲面的求交，造成这种局面的原因就在于n 边域曲 面与四边域曲面表达形式的不一致性l l i 。 正是由于n u r b s 等样条曲面对于拓扑复杂形体表示的局限性，人们不断在寻求 表示复杂拓扑关系的方法。在此基础上，三边曲面片的方法由于其满足有限元分析、 散乱数据曲面拟合等要求，而逐级流行起来。与此同时，人们也发现了样条曲线的可 细化性，于是逐渐开始研究所谓的基于结点插入的递归细分曲面。 1 9 7 8 年c a t m u l l ，c l a r k ”，d o o 和s a b i l l l 6 分别提出了迭代细分四边形网格生成双 三次与双二次b 样条曲面片的方法，并将其推广到任意拓扑网格的情况。通过矩阵 逼近l 1 和离散f o u r i e r 变换。1 ”等方法，这种稳定细分的特征结构和连续性分析问题 已经被很好地解决了。根据c a t m u l l c l a r k 细分规则，在四边形网格区域内，极限曲面 变成相应的均匀b 样条双三次曲面，保证了除奇异点( e x t r a o r d i n a r yp o i n t ) # b 曲面处 处p 连续掣，b a l l 等证明了奇异点处的切平面连续条件【7 l 。s a b i n 验证了三次细分曲 面在奇异点处不可能总有c 2 连续性【9 j 。 由于细分能用较少的控制点迅速生成任意形状的光滑曲面，该方法很快在造型和 动画领域应用起来。此后，细分曲面理论得到了广泛的研究，人们已经取得了理论和 实践上的许多新进展。例如，经典的均匀细分格式和算法得到了分析f l o l ，许多新的 过程和算法被提出来了【1 1 1 2 , 1 3 1 4 关于c 1 和c 连续性的一般理论和方法也得到了深 入研究。文献 1 7 1 把c a t m u l l c l a r k 细分格式扩展到曲面的光顺设计【l5 】：文献【”1 探究了插值于控制点的曲线的细分结构：z o f i n 等提出了细分曲面的一个改进格式f ； 另一种用于四边形网格的格式由k o b b e l t 得到i ”l 。1 9 9 8 年，s t a r e t l 7 i 给出了c a r m u l l c l a r k 细分曲面的解析表达式，能够精确计算c a u n u l l c l a r k 细分曲面上任意参数处 的值”。他的计算公式式表明，用于参数曲面的许多算法和分析技术可以扩展到 c a t m u l l c l a r k 曲面，从而为该曲面的进一步发展打下了更加坚实的理论基础。 1 9 8 7 年，l o o p 等【l 卅基于三向箱样条提出了基于三角形网格的细分方法，每次迭 代将一个三角形片剖分成4 个三角形片，最后得到切平面连续的双二次b 样条曲面。 在l o o p 方法的基础上，h o p p e 等i i9 j 提出了分段光滑曲面的生成方法，可拟合离散数 据集，同时还能保持尖点的特征。1 9 9 8 年，k o b b e l t 等人p o 提出了一个用于任意三角 形网的多分辨率细分格式，它放松了对细分的连通性要求。 h a l s t a n d 等i z ”提出了一种插值任意拓扑的网格顶点的细分方法，其基本思想是计 算控制网格，实得c a t m u l l - - c l a r k 细分曲面插值给定的数据，但由于该算法要求初始 网格的顶点数与型值点个数相同，因此无法用于海量数据集的插值。上述方法生成的 曲面都是均匀b 样条曲面，它们无法对极限曲面的形状进行更多的控制。为此， s e d e r b e r g 等仁列参照非均匀b 样条曲面的构造方法，在任意拓扑地网格式插入非均匀 3 华中科技大学硕士学位论文 节点区间的概念，可以自然地获得尖点、褶皱、刺等特征造型效果。我国学者秦开环 等人对这种非均匀节点细分曲面( n u r s s ) 进行了特征分析和收敛性、连性等分析， 并对之作了一定的改进 2 3 】。q i n 等人将物理性质引入均匀c a t m u l l c l a r k 曲面，开发出 动态细分曲面模型，允许通过施加外力交互式地使之变形【2 。从应用角度上看， d e r o s e 等【s 1 向人们展示了细分造型在人物动作、人脸表情、服饰等方面的巨大优势， 显示了改技术的巨大应用前景。 近几年来，除了对细分规则进行进一步研究以外，也开始在基于细分的应用方面 进行更加高层次操作的研究。如n a t h a nl i t k e 口6 1 等人研究了细分曲面中的裁剪问题， h e n n i n gb i e n n a n n 等人研究了边界角点法线的控制，以及布尔运算问题【z 7 】。随着这些 问题的不断解决，细分曲面作为一个新的造型的核心技术的功能逐渐显现出来。 细分曲面理论目前还没在国内引起广泛的注意，从能查到的资料来看，仅有清华 大学的秦开怀【2 3 1 等研究了非均匀细分曲面问题，和浙江大学的陈为、鲍虎军、彭群 生等人研究了c a t m u l l c l a r k 曲面的加权算法】。 目前，细分曲面的研究还多集中在理论方面，很多研究只是针对个别问题，还没 有形成完善的系统。其应用也还主要集中在计算机图形学领域如计算机动画、三维游 戏制作等方面，而且还存在着很多的不足。如m a y a 4 0 中细分曲面是作为很重要的 一个模块推出的，但其功能方面还有很多不足，如它只支持四边形结构的网格，不支 持三角形结构；没有细分规则的选择，只能做逼近细分，没有插值细分；初始形体只 能从四边形和少数的基本体上变形取得，没有布尔运算、剪裁等非常有用的操作；对 于点、线、面的编辑功能也还不够灵活方便等。 细分曲面在c a d 领域的应用研究还是非常少的，原因是目前c a d 系统的对象 多是基于矩形域的规则拓扑结构体。但随着现代产品设计对形状复杂性要求的提高， 必然会增加这类产品的设计需求。显然用传统的造型方法在设计这类产品时会遇到很 大的困难，而细分曲面则在表示复杂拓扑结构且有连续性要求时有着得天独厚的优 势，细分曲面在c a d 造型中的应用也是一种必然趋势。 1 3 本文主要研究工作及研究意义 除了前述中细分造型具有拓扑任意、造型方便、计算简单等诸多优点外，由于细 分曲面使用细分的小平面逼近曲面，因此在曲面的快速真实感显示、数控加工编程中 的刀具干涉检查、形体的有限元分析以至实体拼合运算处理等中都是十分有效的，曲 面的三角形剖分也是c a d 系统内部功能模块间的一种数据接口方式。 细分曲面能克服n u r b s 的缺陷，可以和n u r b s 相辅相成，在雕塑曲面等复杂 形体的造型方面给用户带来非常大的方便，给c a d 系统带来更为强大的功能。因此 在现有c a d 系统中引用细分造型的方法将是未来c a d 系统革新的一个重要方向。 目前，细分造型的理论虽然经过了很大的发展，但仍未完全成熟，还未在c a d 系统中得到真正的应用。本文提出了将细分造型和现有c a d 系统的结合方法，探索 c a d 系统中应用细分曲面造型的可行道路。 本文的主要研究包括： 4 华中科技大学硕士学位论文 1 、细分曲面基本理论的研究： 研究了细分算法的数学原理，细分曲线曲面和样条曲线曲面的关系，细分曲线曲 面的连续性、光滑性等特征的分析，以及各种细分规则的比较。 2 、细分曲面的造型方法： 细分曲面的主要数据是其控制网格，其造型方法除了初始网格的输入外，还可以 通过一些裁剪、布尔运算等方法进行。控制网格的这些操作和传统造型方法的这些操 作有很大的不同，文中对此进行了一定的研究。 3 、细分曲面和传统造型方法的结合方法： 结合传统造型的特点，探讨了细分造型和之相结合的方法，如细分曲面对现有 c a d 系统中点、线、面操作工具的应用，细分曲面与其它类型曲面的互相转换，等。 4 、细分曲面在c a d 系统中应用方法： 提出了在c a d 系统中应用细分曲面造型的实现框架，探讨了应用过程中的技术 问题。 5 、细分曲面理论及方法的软件实现与应用实验 基于v i s u a lc + + 和o p , m g l 开发了细分造型的原型系统，实现了细分的迭代算 法，以及基于细分造型的一些操作，对本文所提的理论进行了实践验证，取得了良好 的实验效果。 细分曲面是一种新的造型技术，还没有完全成熟和完善，但其对于造型技术的革 新和影响已经得到了国外研究人员的认可，如果我国能够抓住机会，在这方面取得突 破，将会给我国的c a d 技术在国际竞争中取得一定的地位。本文的研究工作希望能 够给我国c a d 技术的发展作出一定的贡献。 5 华中科技大学硕士学位论文 2 1 细分曲线与样条 2 细分曲线与曲面 2 1 1 细分的基本概念 对于细分的基本概念，首先从两个简单实例讲起。图2 1 为平面内曲线的插值细 分实例，左边四点用直线连接，其右为一次细分的结果，有三个新点插入在旧点中间， 原来的三条线段变为六条。再其右的两图为两次和三次细分的结果，可以看出原来的 折线已经变得越来越光滑。 图2 1 平面内曲线插值细分的实例。 气 一， j r ，? 。 。 j j 、 ：一j l r l 弋 、， 图2 2 平面内曲线逼近细分的实例。 图2 2 是逼近细分的一个例子，和图2 1 中插值细分不同之处在于在细分过程中 不仅有新点的插入，同时原来的点坐标也要重新计算。 在三维情况下，细分处理的是三维初始网格，网格的多边形在细分时不断拆分， 一个面拆分为几个更精细的面，经过一定的细分步骤，原来的初始网格被越来越精化， 越来越光滑，直到最后得到满足精度要求的曲面。 细分的关键在于新点的插入。插入的规则有很多种，不同的插入规则会产生不同 的最终曲面。但一个好的细分规则应具有以下特性【2 】： 高效性：新点的位置应使用尽量少的浮点运算； 紧凑性：单个点对于曲线或曲面的影响区域是小而有限的： 局部定义形：新点的产生规则不应依赖于远位置的点： 仿射不变性：原始控制点位置发生了改变，最终形状也会发生同样的变化； 简洁性：描述规则应当简洁，易于表示： 6 、 一 ，j 华中科技大学硕士学位论文 连续性：最终曲线或曲面应具有连续性、可微性。 例如图2 1 中，新点的计算规则是由两个左点邻点、两个右点分别按1 1 6 ( - 1 , 9 ，9 ，1 ) 的权值进行加权平均计算的。该规则就具有：1 ) 高效性，对于每个点坐 标只需做4 次乘3 次加：2 ) 紧凑性，仅在每边有两个邻点参与计算；3 ) 局部性，权 值是固定的，不依赖点的排列；4 ) 仿射不变性，权值总和为l ：5 ) 简洁性，仅有一 个规则( 如果要计算边界，还需要更多的规则) ：6 ) 经过重复细分，最终极限曲线 是c 1 光滑的。 2 1 2b 样条与细分曲线 目前使用的细分方法大多是基于样条理论的，甚至是某种样条的概括。因此首先 对于样条作一个回顾，同时探讨样条和细分的联系。 2 1 2 1 分段多项式曲线 样条是一定次数的分段多项式曲线。例如，对于三次样条曲线可以写为 其中，( a ，b ) 为常系数，单项式( t 3 ，t 2 ，t 1 ，t o ) 是基函数。 为了曲线在它的整个长度上具有一定次数的连续性，如对于三次样条想要其保持 c 2 阶连续，就要对( a ，b ) 进行约束。由于直接通过单项式基函数和其系数来求解 约束，实现所要求的形状是比较困难，通常将样条曲线写成移位b 样条的线性组合， 控制点作为其系数。 x 舴( t ) = z y x y , b ( t - b ( t - n i ) ( 2 2 ) y ( r ) = 见 ”一 新的基函数b ( t ) 要保证：1 ) 最终曲线的连续性。由于多项式本身是无限光滑的， 只需保证两段多项式在交点处的导数相匹配。多项式的次数越高，其要匹配的导数也 越多。2 ) 控制点只在局部产生影响。要使控制点在和它距离最近时影响最大。离它 越远影响，到一定距离就会消失。3 ) 基函数应是分段多项式。可以用相关基函数表 示任意给定次数的若干多项式曲线。 这种表示方法的优点是，线段边界的连续性要求已经固化到基函数中，不管如何 移动控制点，样条曲线都可以保持连续。而且移动一个控制点仅对该点附近的曲线产 生巨大影响，而对远点不产生任何影响。b 样条就是严格满足上述的要求的一种典型 ( 如图2 4 为三次b 样条) ，是构建分段多项式曲线的优秀工具。 2 1 2 2 b 样条的定义 b 样条的推导方法有很多种，这里仅选一种重复计算法，可以从中分析细分和样 条的关系。首先从最简单的情况开始：分段常量函数。任何分段常量函数可以写为： 7 u0 瑶k + 卜 印 + 如眇 + + 一一 以 = f 啪肋 华中科技大学硕士学位论文 其中b o 是箱函数 x ( ，) = x ，俄( f ) 洲= j o f o ，每个彤都可写作 彳= q “矿1 ( 2 9 ) ( 2 1 0 ) 也就是说，彤可以写作前一个步骤的控制点 彤- 1 ，只“1 ，磋：) 的线性组合。 其中a 可随j 和k 的不同而不同，为简化起见， 匀方案( u n i f o r ms c h e m e ) ，甚至更简单一些， 为固定方案( s t a t i o n a r ys c h e m e ) 通常的细分方案是a 不随k 变化的均 n 在每个控制点处都是相同的，称之 b 样条有一个显著的特性：它遵守细化等式。这是样条和细分之间联系的关键所 在。对于z 次日样条，有： 驰，= 可1 刍i 十1l f f + l h ， 亿 也就是说，1 次b 样条可以写成其自身经过平移( k ) 和放大( 2 t ) 后的线性组合。 可以被细化对一个函数来说，有这种特性是很特殊的。0 次b 样条可以平移和放大为： 9 嚷 雕 印 带 聍 华中科技大学硕士学位论文 b o ( ，) = b o ( 2 t ) + b ( 2 t 一1 ) 根据叉乘的性质，可以推导出，次b 样条可以细化为： b 心) = o b o ( 2 t ) = o ( 风( 2 f ) + 岛( 2 t 1 ) ) 例如以b l 可写为： b l ( f ) = b o ( r ) 0 b o ( f ) = ( b o ( 2 t ) + 玩( 2 t 1 ) ) o ( b o ( 2 t ) + b o ( 2 t 1 ) ) = b o ( 2 t ) 圆b o ( 2 t ) + b o ( 2 f ) o b o ( 2 t 一1 ) + b o ( 2 t 一1 ) 固b o ( 2 f ) + b o ( 2 t 1 ) b o ( 2 t 1 ) = b l ( 2 f ) + b i ( 2 t 一1 ) + 占l ( 2 f 一1 ) + j ib i ( 2 t 一1 1 ) = ( b l ( 2 t ) + 2 b i ( 2 t 一1 ) + b l ( 2 f 一2 ) ) = 埘酗z ， 图2 4 分别为0 ，1 ，2 次b 样条细分特性的函数显示。 图2 4 从左到右分别为0 ，1 ，2 次b 样条的细分函数图。 2 1 2 4 样条曲线的细分 对于1 次b 样条，其控制点( x 。，咒) 7 = p ，r2 有 ，( ，) = y x 。( t ) j = p 。b 。) ( 2 1 2 ) ( 2 1 3 ) f 2 1 4 ) ( 2 1 5 ) 暂且不考虑边界，不指定i ，并记b ( f ) = b ( t i ) ，同时将次数，作为下标 1 0 一 一 华中科技大学硕士学位论文 r p ，i + 1 】。给定的曲线控制点记为 p = p 一2p 一。p op 。p ：】7 向量b ( t ) 记为： b ( f ) = 【b o + 2 ) b ( t + 1 ) b ( ，) b ( t 一1 ) b ( t 一2 ) 】 则可记曲线为b ( t ) p 。 运用前面推导的细化公式，则b 可有 r 2 1 6 ) ( 2 1 7 ) b ( 2 t ) = 【一- b ( 2 t + 2 ) b ( 2 t + 1 ) b ( 2 t ) b ( 2 t 1 ) b ( 2 t 一2 ) 】( 2 1 8 ) 可用矩阵s 将其表示为： b ( t ) = b ( 2 t ) s ( 2 1 9 ) 由式2 1 1 可知 s ：+ 。，= ：s 。= = 古( 7 ：1 ) c ：z 。， 由此原样条可记为 ，( f ) = b ( t ) p = b ( 2 t ) s p( 2 2 1 ) 可以看到，曲线仍然是原来的曲线，但其控制点已经加密了2 倍。那么如何将旧 的控制点p 改为新的控制点s p 呢? y ( t 1 = b ( t ) p o = b ( y = b ( 2 ) 卵。( 2 2 2 ) = b ( 2 j t ) p i ：b ( 2 i t ) s j p o 由此可知 p ”1 = s p ( 2 2 3 ) 对于其中一段i 有 只川= s 只 ( 2 2 4 ) 对于上式，根据控制点奇偶不同，可有不同的表示： 奇数点：p 盘= s ：。p = s ：。m p ， 华中科技大学硕士学位论文 偶数点：p 2 l = s ：“p ，= j ：。n p f 2 2 6 1 由上述公式可知，在1 次线性细分时，奇数时系数是，；偶数时系数为1 。对 于3 次样条，其奇点系数是 ， ；偶点系数是，i 6 ，；。 还可以看到，在j + 1 层是奇点是新插入的，偶点是直接从j 层对应过来的。对 于一次线性样条，j + l 层的偶点实际上就是i 层的旧点。在细分方案中，这种特性被 称为“插值”，因为一旦一个点已经作了计算就不再移动。对于三次样条，i + l 层 的偶点是其邻点的平均，p 2 。p j 。这种方案被称之为“逼近”法。 前面，我们用矩阵s 乘控制点向量p 对样条曲线进行了细化，如果将此过程进 行多次重复，控制点会逐级收敛于实际样条曲线，其收敛速度是按一定几何级数的， 在一定细分步骤之后就很难区分样条曲线和它的控制点了。 细分的关键思想也就是利用上述的原理，用控制点多边形( 分段线) 去取代实际 的样条曲面( 曲线) ，应用细分矩阵产生分段线性曲线序列来逼近实际样条曲线本身。 2 1 3 曲线细分的离散推导 b 样条细化公式的系数s k 也可以通过离散卷积的方法进行推导。这种方法和连 续b 样条的卷积是非常相似的，利用离散卷积还可以发现细分的很多有用的特性。 序列a l 的发生函数为 4 ( ：) = 吼：2 ( 2 2 7 ) i 这里，a ( z ) 是z 关于序列a i ( 的变换式。该式和限制了z ( z = e x p ( i0 ) ) 的傅立叶 变换密切相关。 对于有两个系数序列a 【和b i ( 的情况，卷积为： c k2 ( 口0 6 ) 女= a k b( 2 2 8 ) n 时间域的卷积是傅立叶域的乘积，用发生式的形式可将其记为： c ( z ) = a ( e ) b ( z ) ，( 2 2 9 ) 在这里我们使用发生式是为了简化系数的乘。 设有两细化函数： 1 2 华中科技大学硕士学位论文 儿) = 吼f ( 2 t 一女) ， g ( f ) = b , g ( 2 t 一七) 其卷积h = f o g 的细化定义为： = c 。h ( 2 t 一) 其系数可以单个的细化系数来决定： 气：要q 6 ( 2 3 0 a ) r 2 3 0 b ) ( 2 3 0 f 2 3 2 ) 因此，通过发生函数的乘积，可以很快得到细分矩阵s 和细化等式对于箱函数 b o ( t ) 有 风( f ) = b o ( 2 t ) + b o ( 2 t 一1 ) ，( 2 3 3 ) 其细化公式的发生函数为a ( z ) = ( 1 + z ) 。由此可得到，次b 样条的定义为 目( f ) 2 窟o b o ( t ) ( 2 3 4 ) 由此其发生函数为 s ( z ) = - 4 1 7 - ( 1 + z ) “。 ( 2 3 5 ) 这样定义细分矩阵的s k 可以通过s ( z ) 得到 跗，专戢1 p 亿，s ， 前厩提到，n 次b 样条是c 光滑的，同样我们可知如果s ( z ) 定义了一个产生 c 。阶连续地极限函数的收敛的细分方案，j i g s , 去( 1 + ：) s ( z ) 定义了一个产生c 阶连 续地极限函数的收敛的细分方案。 该定理可以用柬通过去掉去( 1 + z ) 来分析一个给定的细分方案，同时还可以证明 其收敛性。 前述的细化过程都是基于样条理论考虑的，计算细化的新控制点时，我们所用的 系数是固定不变的且处处相同。这不是非得如此不可的，实际上在细分的不同层次可 以使用不同的细分规则，或者仅在局部使用也可。从这个意义上讲，样条仅是一种曲 1 3 华中科技大学硕士学位论文 线生成的特例，而细分曲线更具有普遍性。 2 1 4 曲线细分特性分析 2 1 4 1 不变邻接数( i n v a r i a n tn e i g h b o r h o o d s ) 如果要研究给定的细分方案在特殊控制点附近的极限曲线，我们不可能需要整个 曲线的无穷多控制点向量和无限细分矩阵。可微性是曲线的局部特性，只需要曲线特 定点附近任意小的一段即可。这也就是控制点对其邻近曲线的影响问题。 首先以三次b 样条为例如图2 5 所示，两段三次曲线段分别位于原点左右邻域 1 ，o 】， o ，1 】内，通过5 个控制点可以得到到极限曲线的任意点，我们称它的不变邻接 数为5 。该数是由细分矩阵的每行的非零个数决定的，其奇点数为2 ，偶点数为3 。 可以看到，这罩需要两个值域外的控制点，一个在一l 左边，一个在l 的右边。 k 麟f 澈l 髟 图2 5 三次b 样条细分的不变邻接数为5 。 另一种方法是看细分方案的基函数。一旦知道了该域上的全部基函数，根据给定 的控制点就可以得到该域的控制点序列。怎样确定全部的基函数呢? 以线性细分为例 p ( f ) = b l ( 2 t ) s p o = b l ( 2 。t ) s i = p ? b 。( 2 。t ) s = p ，0 ”j ( f ) p ? ( t ) 。 ( e 。) o ( 2 3 7 ) 其中e i o 表示除i 点处为l 外其它全为0 。也就是说最终曲线通常是基本解的带 p i o 权的线性组合。 1 4 华中科技大学硕士学位论文 l i m 妒j ( f ) = 妒。( f )r 2 3 8 ) 如果运用同样的细分权系数，很容易看到能( f ) = p ( f f ) ，也就是存在一个简单 的函数妒( f ) 使得从控制点序列p o 产生的最终曲线是妒( f ) 平移后的线性组合。该函数 被称为细分方案的基本解。对于极限曲线的可微性，我们可以通过其基函数来取得。 妒( r ) = l i r as ( e o ) o ( 2 3 9 ) j 由此可以知道一个控制点所能产生的影响，或者说移动一个控制点曲线的形状会 发生怎样的改变。不过，有一点要注意，对于曲面的情况不仅仅简单的依赖基本解， 而要看点的“