（应用数学专业论文）cagd中细分与拟合的造型方法研究.pdf

摘要 本文围绕计算机辅助几何设计( 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 ，简称 c a g d ) 中细分和拟合的造型方法进行了深入的研究，主要获得了以下一些成 果： 首先，从理论上证明了b 样条曲线的升阶是割角过程，并指出了割角过程 中辅助控制顶点的几何意义 给定一条b 样条曲线，我们在每一步只增加一个节点的重数，相应地也只 升高一个节点区问内的阶数这样每一个步骤中老基函数最多用2 个新基函数 来表示，从而新控制顶点最多只用2 个老控制顶点来表示，也就是说新控制多边 形是由老控制多边形割角得到的这样依次增加每个节点的重数，当所有节点 区间上的阶数都升高时，我们用割角过程得到了升阶曲线的控制顶点为了在 每一步只升高一个节点区问的次数，我们引入了双次b 样条基函数的概念，并 利用双次b 样条基函数之间的变换公式证明了b 样条曲线的升阶是割角过程 而割角过程中出现的辅助控制顶点则是由双次b 样条基函数所定义的双次b 样条曲线的控制顶点 其次，提出了一种把平面光滑曲线转换为b 样条曲线的局部算法 我们的局部算法有三个主要步骤：首先从待转换的曲线上采样足够多的点 及其切向，然后用g 1 连续的b 6 z i e r 样条去拟合采样数据，最后再把g 1 连续的 b d z i e r 样条拼接为c 2b 样条曲线由于在第二步拟合与第三步拼接中都符合了 保形及误差要求，所以最后的拟合曲线也达到了保形及误差要求而且，由于我 们每次用固定端点及端点切向的b 6 z i e r 曲线拟合点列时根据数据点的局部特性 自适应确定节点及控制顶点，所以所得拟合曲线的控制顶点数要少于传统的最 t b - - 乘法等拟合方法数值算例表明我们的局部算法在保形及减少数据量等方 面均优于传统的最小二乘法 再次，提出了曲线插值的内心细分法 内心细分法因为每边对应的新点是由边、边两端顶点切线所围成的三角形 的内心而得名它有两个主要步骤：加入新点，调整切向给定一个初始点列及 其切向，用内心细分法得到的极限曲线曲率连续且保形给定两点两切向，配以 c a g d 巾细分和拟合的造璎方法研究 基于相邻五点的切向调整方法，内心细分法可以得到捅值两点两切向的螺线用 内心细分法还可以在极限曲线中光滑地插入直线段另外，内心细分法还具有 还圆性的特点，即如果所有的初始点及其切向均取自同一圆弧段，则极限曲线就 是该网弧段我们对极限曲线的收敛性与连续性给出了严格的证明，并用数值 算例验证了内心细分方法 最后，提出了一种用逼近型细分算法插值网格的方法 利用逼近型细分方法顶点对应的极限点公式，我们给出了一种极其简单高 效的插值方法我们以l o o p 细分方法为例给出了新边点及新顶点的显式表达 式新方法的优点有：( 1 ) 局部性：改变一个点的位置时，只影响其附近插值曲面 的形状( 2 ) 计算简单：新点直接由显式公式给出，不用解线性方程组( 3 ) 易于 实现：只改变第一步细分规则中的几何规则，其它步骤不做任何修改( 4 ) 适用 广：几乎适用于任何逼近型细分方法，对逼近型细分方法的唯一要求是：顶点处 对应的极限点公式显式给出( 5 ) 自由度多：有足够的自由度调节插值曲面的形 状 关键词：计算机辅助几何设计，局部方法，b 样条，升阶，双次b 样条，误差要 求，曲线转换，保形，曲线拟合，插值型细分方法，非线性细分方法，几何细分方 法，g 2 连续，细分曲面，逼近型细分方法，l o o p 曲面，曲面插值 a b s t r a c t i nt h i sp a p e r ，w eh a v em a d eas y s t e m i ct h e o r e t i cr e s e a r c ho nm o d e l l i n g m e t h o d so fs u b d i v i s i o na n df i t t i n gi nc a g d t h ec r e a t i v ep r o d u c t i o n sa r eg i v e n a sf o l l o w s a tf i r s t ，w ep r o v et h a tt h ed e g r e ee l e v a t i o no fb s p l i n ec u r v e si sc o r n e r c u t t i n ga n dp o i n to u tt h eg e o m e t r i cm e a n i n g o ft h ea u x i l i a r yc o n t r o lp o i n t sd u r i n g t h ec o m e rc u t t i n g g i v e nab s p l i n ec u r v e ，i ne a c hs t e pw eo n l yi n c r e a s et h em u l t i p l i c i t yo f o n ek n o ta n de l e v a t et h ed e g r e eo n l yi nt h i sk n o ti n t e r v a l t h e nt h eo l db a s i s f u n c t i o n sc a nb er e p r e s e n t e db yn om o r et h a n2n e wb a s i sf u n c t i o n s ，s ot h en e w c o n t r o lp o i n t sc a nb er e p r e s e n t e db yn om o r et h a n2o l dc o n t r o lp o i n t s ，i e ，t h e n e wc o n t r o lp o i n t sa r ed e r i v e df r o mt h eo l dc o n t r o lp o i n t sb yc o r n e rc u t t i n g w h e nt h em u l t i p l i c i t i e so fa l lt h ek n o t sa r ei n c r e a s e d ，w eo b t a i nt h ec o n t r o l p o i n t so ft h ed e g r e e - e l e v a t i o nc u r v eb yc o m e rc u t t i n g t oe l e v a t et h ed e g r e eo f b - s p l i n ec a l v e sj u s ti no n ek n o ti n t e r v a lp e rs t e p ，w ed e f i n et h eb i - d e g r e eb - s p l i n e b a s i sf u n c t i o n sb yt h ei n t e g e rd e f i n i t i o n so fs p h n ef u n c t i o n s t h et r a n s f o r m a t i o n f o r m u l a sb e t w e e nu s u a la n db i d e g r e eb - s p l i n eb a s i sf u n c t i o n sl e ! a dt ot h ec o r n e r c u t t i n gf o rd e g r e ee l e v a t i o no fb s p l i n ec u l w e s t h ea u x i l i a r yc o n t r o lp o i n t s d u r i n gt h ec o r n e rc u t t i n g a r et h ec o n t r o lp o i n t so ft h eb i - d e g r e ec u r v e s s e c o n d l y , w ep r o p o s eal o c a lf i t t i n ga l g o r i t h mf o rc o n v e r t i n gs m o o t hp l a n a r c u r v e st ob - s p l i n e s f o ras m o o t hp l a n a rc u r v eas e to fp o i n t st o g e t h e rw i t ht h e i rt a n g e n tv e c t o r s a r ef i r s ts a m p l e df r o mt h ec u r v es u c ht h a tt h ec o n n e c t e dp o l y g o na p p r o x i m a t e s t h ec u r v ew i t hh i g ha c c u r a c ya n di n _ f l e x i o n sa r ed e t e c t e db yt h es a m p l e dd a t a e f f i c i e n t l y t h e n ，ag 1c o n t i n u o u sb d z i e rs p u n ec u r v ei so b t a i n e db yf i t t i n gt h e s a m p l e dd a t aw i t hs h a p ep r e s e r v a t i o n 够w e l la sw i t h i nap r e s c r i b e da c c u r a c y f i n a l l y , t h eb d z i e rs p l i n ei sm e r g e di n t oa 伊c o n t i n u o u sb - s p l i n ec u r v eb ys u b - d i v i s i o na n dc o n t r o lp o i n t sa d j u s t m e n t t h em e r g i n gi sg u a r a n t e e dt ob ew i t h i n a n o t h e re r r o rb o u n da n dw i t hn om o r ei n f l e x i o n st h a nt h eb 6 z i e rs p l i n e i na d d i - t i o nt os h a p ep r e s e r v i n ga n d e r r o rc o n t r o l ，t h i sc o n v e r s i o na l g o r i t h ma l s ob e n e f i t s t h a tt h ek n o t sa r es e l e c t e da u t o m a t i c a l l ya n da d a p t i v e l ya c c o r d i n gt ol o c a ls h a p e a n de r r o rb o u n d af e we x p e r i m e n t a lr e s u l t sa r ei n c l u d e dt od e m o n s t r a t et h e v a l i d 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 t h i r d l y w ep r o p o s eai n c e n t r e ss u b d i v i s i o ns c h e m ef o rc u r v ei n t e r p o l a t i o n t h es c h e m ei ss a i dt ob ei n c e n t r e ss u b d i v i s i o ns c h e m ed u et ot h ef a c tt h a t t h en e wa d d e dv e r t e xc o r r e s p o n d i n gt oa ne d g ei st h ei n c e n t r e so fat r i a n g l e w h i c hi sd e f i n e db yt h ee d g ea n dt w ot a n g e n tl i n e so fi t se n dp o i n t s g i v e na s e q u e n c eo fv e r t i c e sa n dt h e i rt a n g e n tv e c t o r s ，u s i n gat h r e e - v e r t e xb a s e dt a n g e n t a d j u s t i n gm e t h o d ag 2c o n t i n u o u sa n ds h a p ep r e s e r v i n gc u r v ei s o b t a i n e db y t h ei n c e n t r e ss u b d i v i s i o ns c h e m e w i t haf i v e - v e r t e xb a s e dt a n g e n ta d j u s t i n g m e t h o d ，t h ei n c e n t r e ss u b d i v i s i o ns c h e m ec a ng e n e r a t eas p i r a lf r o mat w o - p o i n t g 1h e r m i t ed a t a b yt h ei n c e n t r e ss u b d i v i s i o ns c h e m e ，s e p a r a t el i n es e g m e n t s c a nb ei n s e r t e di n t oas u b d i v i s i o nc u r v ew i t hc u r v a t u r ec o n t i n u i t y i fa l lt h e i n i t i a lv e r t i c e sa n dt h e i ri n i t i a lt a n g e n tv e c t o r sa r es a m p l e df r o mac i r c u l a ra r c s e g m e n t ，t h ea r cs e g m e n tw i l lb er e p r o d u c e d t h ec o n v e r g e n c ea n d s m o o t h n e s s a n a l y s i so ft h i sn e ws c h e m ea r ea l s op r o v i d e d s e v e r a le x a m p l e sa r eg i v e nt o d e m o n s t r a t et h ee x c e l l e n tp r o p e r t i e so ft h es c h e m e a tl a s t ，w ep r o p o s eam e t h o df o ri n t e r p o l a t i n ga r b i t r a r yt o p o l o g ym e s h e s u s i n gt h ea p p r o x i m a t i o ns u b d i v i s i o ns c h e m e f o ra p p r o x i m a t i o ns u b d i v i s i o ns c h e m es u c ha sl o o ps u b d i v i s i o ns c h e m e ， t h el i m i tp o i n t so fav e r t e xc a nb ec o m p u t e db ye x p l i c i tf o r m u l a u s i n gt h e f o r m u l aw ep r o p o s eav e r ys i m p l ea n de f f i c i e n tm e t h o dt oi n t e r p o l a t em e s h e s b ya p p r o x i m a t i o ns u b d i v i s i o ns c h e m e w eg i v et h ee x p l i c i tf o r m u l ao ft h en e w v e r t i c e sc o r r e s p o n d i n gt h ee d g e sa n dv e r t i c e s t h o u g hw eo n l yd i s c u s st h el o o p s u b d i v i s i o ns c h e m ei nt h i sp a p e r ，t h em e t h o dc a l lb eu s e dt oo t h e rs u b d i v i s i o n s c h e m e ss u c ha sc a t m u l l - c l a r ks u b d i v i s i o ns c h e m e ， 3s u b d i v i s i o ns c h e m ea n d s 0o n k e y w o r d s ：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 ，l o c a lm e t h o d ，b - s p l i n e ，d e g r e e e l e v a t i o n ，b i - d e g r e eb - s p l i n e ，c u r v ec o n v e r s i o n ，s h a p ep r e s e r v i n g ，c u l w ef i t t i n g ，i n - t e r p o l a t i n gs u b d i v i s i o ns c h e m e ，n o n - l i n e a rs u b d i v i s i o ns c h e m e ，g e o m e t r i c b a s e d a b s t r a c t v s u b d i v i s i o ns c h e m e ，g 2c o n t i n u o u s ，s u b d i v i s i o ns u r f a c e ，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 ，l o o ps u b d i v i s i o ns c h e m e ，s u r f a c ei n t e r p o l a t i n g 插图 1 1 五次p 泡z i e r 曲线的升阶。： 1 2 细分曲线举例 2 1 双次b 样条初始基函数 y i 0 1 ( t ) ) 和 心o ( ) ) 2 2 b 样条曲线升阶的割角过程 2 3b 样条曲线升阶的实例 4 8 1 8 2 2 2 3 3 1 a 与a + 1 问的拐点榆测 2 8 3 2 把两条g 1 连续的三次b 6 z i e r 曲线拼接为条c 2 的b 样条曲 线( a ) 连接点处凸( b ) 连接点处有拐点 3 l 3 3 把曲线c l 转换为三次b 样条f h l 线：( a ) 局部拟合算法；( b ) 局部 拟合算法且优化a ；( c ) 最小二乘法3 8 3 4 原曲线( 监) 与拟合曲线( 红) 的曲率图：( a ) 局部拟合算法( 优化a ) ； ( b ) 最小二乘法3 9 3 5 用三次b 样条曲线拟合细分曲线：( a ) 局部拟合算法；( b ) 局部拟 合算法且优化入；( c ) 最小二乘法4 0 3 6 原曲线( 监) 与拟合曲线( 红) 的曲率图：( a ) 局部拟合算法( 优化a ) ； ( b ) 最小二乘法，4 1 4 1 初始切向的范围4 5 4 2 边的分类( a ) 凸边( b ) 凹边( c ) 直边 4 5 4 3 新点加入规则4 6 4 4 计算新切向( a ) 凸点( b ) 拐点 4 8 4 5 确定直边切向( a ) y j 始t ) j h j ( b ) 切向调整方法5 0 4 6 初始多边形凸的细分曲线：( a ) e 1 = o 5 ；( b ) e l = o 2 5 ；( c ) 三进制 四点法5 4 c a g dr f l 细分和拟合的造型方法研究 4 7 苹果形细分曲线：( a ) e 1 = e 2 = o 5 ；( b ) e 1 = 0 5 ，e 2 = 0 2 5 ；( c ) 三 进制四点法5 6 4 8 s 形细分曲线，l = 0 5 ，2 = o 2 5 5 7 4 9 d 形细分曲线：( a ) e 1 = e 2 = 0 5 ；( b ) 龟= 0 5 ，e 2 = 0 2 5 ， 5 7 4 1 0 端点角度度数不同的六条细分螺线：例5 1 ：s o = 4 0 0 ，储= 1 0 0 ； 例5 2 ：s o = 7 0 0 ，藤= 2 0 0 ；例5 3 ：q 3 = 9 0 0 ，罐= 3 0 0 ；例5 4 ： 4 0 = 1 2 0 0 , 藤= 4 0 0 ；例5 5 ：q 3 = 1 2 0 0 ，藤= 5 0 0 ；例5 6 ：口3 = 8 0 0 ，臃= 6 0 0 5 8 5 1 l o o p 细分方法( a ) 新顶点( b ) 新边点( c ) 拓扑规| l l 7 7 5 2 极限点计算公式 7 8 5 3 确定新边点和新项点( a ) 新边点( b ) 新顶点 8 0 5 4 细分实例1 ( a ) 初始网格( b ) l o o p 细分( c ) 蝶形细分( d ) l o o p 插值 细分入= 1 ( e ) l o o p 插值细分入= 2 ( f ) l o o p 插值细分入= 3 8 1 5 5 细分实例2 ( a ) 初始网格( b ) l o o p 细分( c ) 蝶形细分( d ) l o o p 插值 细分a = 1 ( e ) l o o p 插值细分a = 2 ( f ) l o o p 插值细分a = 3 。8 2 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝鎏盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文储躲叩嗲咖签字隰埘年扩日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂 有权保留并向国家有关部门或机构送交席 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权迸姿盘堂可以将学位论文能 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手嚣 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：叩匆勾桫 签字日期：卅年c 月厂日 导师签名： 胁伺7 吒 期：碱够矽日 第一章绪论 计算机辅助几何设计( 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 ，缩写为c a g d ) 这 一术语1 9 7 4 年由b a r n h i l l 与r i e s e n f e l d 提出，其含义包括曲线、曲面和实体的 表示及其在实时显示条件下的设计4 1 我国著名数学家苏步青则指出c a g d 是 代数几何、微分几何、函数逼近论、计算数学和数控技术的边缘学科 1 6 1 它 肇源于飞机、船舶的外形放样( l o f t i n g ) - f 艺，由c o o n s ( 1 9 1 2 - 1 9 7 9 ) 、b 6 z i e r ( 1 9 1 0 - 1 9 9 9 ) 等大师于2 0 世纪6 0 年代奠定理论基m 8 1 伴随着计算机技术的飞速发展， c a g d 几十年来取得了长足的发展，并广泛应用于计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，缩写为c a d ) 、计算机辅助制造( c o m p u t e ra i d e dm a n u f a c t u r i n g ， 缩写为c a m ) 、计算机辅助工程( c o m p u t e ra i d e de n g i n e e r i n g ，缩写为c a e ) 、 计算机图形学( c o m p u t e rg r a p h i c s ，缩写为c g ) 等各个领域1 1 5 8 c a g d 的主要研究对象是工业产品的几何形状工业产品的形状大致分为 两类：一类仪【1 1 初等解析曲线曲面( 例如直线、圆、圆锥曲线、平面、圆柱面、圆 锥面、球而、圆环面等) 组成，大多数机械零件属于这一类用画法几何与机械制 图的方法可以把这类曲线曲面完全清楚地表达并传递其包含的全部形状信息 第二类是不能由初等解析曲线曲面组成，而是以复杂方式自由变化的曲线曲面 即所谓的自由型曲线曲面组成的例如飞机、汽车、船舶的外形等由于后一类 形状单纯用画法几何与机械制图不能表达清楚，因此，自由曲线曲面的表示、设 计、分析以及规格、处理等问题，是c a g d 的主要研究内容 1 5 3 实际工业中，传统上采用模线样板法表示和传递自由曲线曲面的形状这种 设计制造法所表示与传递的几何形状因人而异，生产周期长，制造精度低，互换 协调性差，设计差错多，改型困难，不能适应现代航空、汽车、船舶等工业的发 展随着计算机技术的发展，采用数学方法定义、表示、分析自由型曲线曲面成 为c a g d 的主要研究对象它主要研究在计算机图像系统的环境下对曲线曲面 的表示、设计、显示和分析 1 5 9 ，1 6 4 1 经过长期的应用实践酝酿与理论发展，参 数法、隐式法、细分法逐渐成为自由曲线曲面造型技术的主流 由于具有显示方便、易于计算曲线曲面上的点等优点，参数曲线曲面一直是 描述几何形状的主要工具特别是，非均匀有理b 样条( n o n - u n i f o r mr a t i o n a l b - s p f i n e ，缩写为n u r b s ) 以其在外形表示方面的强大功能与潜力成为工业产品 2c a g d 中细分和拟合的造犁方法研究 数据交换的s t e p 标准，也被作为描述工业产品几何形状的唯一数学方法 1 2 5 隐式曲线曲面的优势则在于判断点是否在曲线曲面上、在哪一侧等几何操作很 方便，因而也在c a g d 中扮演着重要的角色 1 1 6 算法简单是细分曲线曲面的 最大优点，而且细分曲面几乎可以描述仟意复杂的曲面 1 4 4 本文的研究内容 集中于参数曲线曲面中b 样条升阶与割角、拟合与细分捅值的造型方法上所 以我们下面详细介绍b 样条与细分曲线曲面的相关内容 1 1b 样条曲线 b 样条是最简单的多项式样条，它具有表示和设计自由曲线曲面的强大功 能，是最广泛流行的形状数学描述主流方法之一 i i 1b 样条曲线简史 与b 样条曲线曲面密切相关的是b 6 z i e r 曲线曲面1 9 7 1 年法国雷诺汽车公 司的工程师b 6 z i e r 提出了一种由控制多边形设计曲线的新方法它具有保形、 易于交互等优良性质但b 6 z i e r 最初的定义非常奇特，令人难以理解f o r r e s t 发现处理作为b 包i e r 多边形边的相对矢量不如处理作为顶点的绝对矢量方便， 并发现上述b 6 z i e r 基表示形式能被改写成现在广泛使用的用控制顶点定义的 b e r n s t e i n 基表示形式 4 0 1 从7 0 年代中期开始，国内对b 6 z i e r 方法也作了大量 的研究 1 7 ，1 4 8 ，1 5 4 ，1 5 5 ，1 5 6 ，1 6 0 ，1 6 1 ，1 6 2 ，1 6 3 ，1 6 5 ，1 6 6 ，1 6 7 b 6 z i e r 方法把 参数曲线曲面设计向前推进了一大步，但b 6 z i e r 方法仍然存在光滑拼接问题和 局部修改问题b 样条理论的引入刚好解决了这两个问题 b 样条理论最早在1 9 4 6 年由s c h o e n b e r g 提出1 1 2 1 ，但其论文直到1 9 6 7 年 才发表 1 1 3 1 9 7 2 年，在提出b 样条基函数的递推定义的基础上，d eb o o r 和 c o x 分别独立地给出了关于b 样条计算的标准算法但把b 样条作为c a g d 中的一个形状描述的基本方法，则是i | 1g o r d o n 与r i e s e n f e l df 4 5 1 在研究b 6 z i e r 方法的基础上，把b 样条函数推广到矢值形式而得来的d eb o o r 1 0 ，1 1 ，1 2 ， c o x 2 3 ，1 1 4 ，1 1 5 ，b o e h m 6 ，7 ，8 ，9 1 ，c o h e n 1 9 ，p r a u t z s c h 1 0 4 等都对b 样条曲 线的理论作出了积极的贡献b 样条曲线继承了b 6 z i e r 曲线的所有优良性质，同 时具有局部支撑性等新的性质，而且可以退化成b 6 z i e r 曲线 b 样条曲线的一个缺陷是不能精确表示圆锥曲线，而圆锥曲线，特别是圆在 工业设计等领域是不可回避的解决这个问题现在主要有两个方法： 第一章 绪论 3 一个方法是把b 样条推广到非均匀有理b 样条( n o n - u n i f o r mr a t i o n a l b s p h n e ，简称n u r b s ) 曲线最早提出有理b 样条的是v e r s p r i u e 1 2 6 ，继之研 究的有p i e g l 9 2 ，9 3 ，9 4 ，9 6 ，9 7 ，9 9 ，t i l l e r 1 2 2 ，1 2 3 ，1 2 4 ，w a n g 1 3 1 等 另一个方法是把b 样条推广为代数一三角混合b 样条三角b 样条的概念 在1 9 6 4 年由s c h o e n b e r g 提出，而混合样条函数的思想最早是由p o t t m a n n 【1 0 1 ， 1 0 2 提出来的同时，z h a n g 1 4 1 ，1 4 2 l 也独立地在空间乃= s p a n c o s t ，s i n t ，1 ，) 上构造了3 次c b 6 z i e r 样条与c b 样条2 0 0 2 年，l i i 7 5 把3 次均匀c b 样条 曲线推广到n 次；2 0 0 3 年，w a n g 和c h e n 1 8 ，1 3 3 y 得到了佗次c b 6 z i e r 曲线 与n 次非均匀b 样条曲线w a n g 等在构造代数一三角混合样条基函数的过程中 提出了样条函数的积分定义，把代数，双曲，多项式等样条基函数全部统一了起 来 1 3 4 1 1 2b 样条曲线的升阶与割角 b 样条曲线的升阶是b 样条方法中一个重要的配套技术 1 5 9 1 通过升阶可 以增加b 样条曲线的柔性，或者说可以提高其形状控制的潜在灵活性因为通 过升阶，增加了控制顶点数，也就增加了自由度用升阶方法的主要优势是，不 论怎样移动升阶后生成的新控制顶点，样条曲线的参数连续性将保持不变 1 5 9 b 样条曲线的升阶在表示和设计组合曲线时也是必不可少的手段之一两条或 者若干条不同次的b 样条曲线要顺序连接成为组合b 样条曲线，用一个统一的 方程表示，必须先采用升阶方法，使它们的次数统一起来，才有可能实现这样的 连接b 样条曲线的升阶在生成曲而时，在表示与设计组合曲面时同样有重要的 用途但与b 色z i e r 曲线的升阶相比，b 样条曲线的升阶要复杂得多 p r a u t z s c h 1 0 3 1 首先在1 9 8 4 年给出了b 样条曲线升阶算法他的理论依据 是，用来定义b 样条曲线的b 样条基函数可以升阶p r a u t z s c h 和p i p e r 1 0 4 1 在 1 9 9 1 年对这个算法做了改进，使之运行效率更高c o h e n 2 0 1 则利用离散b 样条 的理论给出了b 样条曲线的升阶算法与以上两种方法相比，p i e g l 和t i l l e r 9 5 】 的方法则较为简单易懂，更切合工程实际他们先通过节点插入算法把b 样条 曲线转换为b 4 z i e r 曲线，然后对b ( r z i e r 曲线进行升阶，最后再通过节点消去算 法把升阶后的b 6 z i e r 样条改写成b 样条曲线的形式完成升阶过程l i u 7 3 1 的 基于开花理论的方法也简单且易于理解，他通过一系列的节点插入与节点消去 来组合出新控制顶点h u a n g 5 8 1 等的方法是效率最高的，他们的理论基础也很 4c a g d 巾细分和拟合的造型方法研究 简单：升阶前后端点处的导数保持不变 c a g d 中的很多基础算法都可以解释为割角过程，即生成折线多边形序 列的过程，其中每个折线多边形由上一个折线多边形割去一个或多个角而得 到f 1 3 】割角实例有d er h a m 1 0 7 】算法，c h a i k i n 1 6 】及其推广 1 5 ，2 8 】，b 6 z i e r 曲 线的升阶【4 0 】，b 样条曲线的节点插x 6 l 等等割角法的魅力主要体现以下几个 方面： ( 1 ) 割角法用几何直观的方式定义曲线【8 7 】 ( 2 ) 在具体应用方面，割角算法具有计算简单稳健的优点【1 5 8 1 ( 3 ) 割角法所得曲线保形1 1 5 8 】 ( 4 ) 在理论上割角法所得极限曲线一定收敛 1 3 1 图1 1 ( 此图摘自【1 5 s ) 是把五次b 6 z i e r 曲线升阶为六次b 6 z i e r 曲线的割角 过程图中只( i = 0 ，1 ，5 ) 是五次b 6 z i e r 曲线的控制顶点，只( 1 = 0 ，1 ，6 ) 则是原五次b 6 z i e r 曲线升阶后对应的六次b 6 z i e r 曲线的控制顶点从图1 1 可 以看出，折线多边形蜀p 1 马b 只r r 由折线多边形r 只马b 只b 割去4 个 角而得到若不断升阶下去，当次数趋向于无穷大时，升阶多边形序列收敛予原 b 6 i z e r 曲线，且收敛阶是一阶 2 1 1 图1 1 ：五次b 6 z i e r 曲线的升阶 用割角法设计曲线也是c a g d 中的一个重要的研究课题，这种方法被形象 地描述为”切割磨光”( c u t t i n ga n dg r i n d i n g ) 法实际上，著名的b 6 z i e r 曲线、b 样条曲线就是割角法生成曲线的特例割角法不但能产生自由曲线曲面，而且 能够产生尖点、直线、折角曲面等，具有保凸性、凸包性和局部可调性等b 样条 方法的优点 1 5 0 ，1 5 7 ，1 6 8 更为重要的是，它可以作用到任意拓扑网格上去，产 生任意拓扑类型的光滑曲而f 7 6 ，7 7 ，1 5 1 最近，关于割角的理论成果也逐渐丰富起来g r e g o r y 和q u 4 6 l 研究了不 均匀割角法产生的曲线的收敛性与光滑性的问题，并给出一些使极限曲线收 筇一章绪论 5 敛、光滑的充分条件a u m a n n 【2 】研究了用比传统割角法更广泛的割角法生成 的曲线的性质，并据此提出了b 6 z i e r 曲线和b 样条曲线的一些新的几何性质 p a l u s z n y 等1 8 7 1 则从射影几何的角度审视割角方法，揭示了割角与平面、球面上 保凸插值细分方、法之间的联系d e l g a d o 和p e f i a 2 4 提出了割角系统的概念并对 割角系统进行了系统的讨论他们提出了割角系统的弱充分条件，并证明了割角 系统肯定是保单调的 由于割角算法在计算机辅助几何设计中的特殊地位，以及因为b 6 z i e r 曲线 的升阶是割角算法，所以b 样条曲线的升阶是否是割角过程是c a g d 中的一 个重要的基础理论问题本文巾我们证明了b 样条曲线的升阶与b 6 z i e r 曲线的 升阶一样，也是割角算法，并指出了割角过程中辅助控制顶点的儿何意义 1 1 3b 样条曲线的拟合 c a g d 中曲线曲面的常用设计方法大致可分为逼j 匠( a p p r o x i m a t i o n ) 、插 值( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 这三大类 1 5 8 所谓逼近就是人机交互地改变 特征网格来得到由网格所控制的理想的曲线曲面插值和拟合与逼近明显不 同，其特征网格根据从产品模型或仿制样品表面测量所得的三维型值点集( d a t a p o i n t s ，也称数据点集) 反求得到的若曲线曲而严格通过型值点，则称为插值； 反之称为拟合当然，插值与拟合的信息除了点的位置外，还可以有法向、导矢、 曲率等一般说来，拟合是比捅值更重要的问题这主要有两个原凶：一方面是 测量数据本身可能有误差，所以有时精确的插值并无必要；另一方面是有时测量 数据太多，用插值方法会导致数据量太大本文关注b 样条曲线的拟合方法 一条b 样条曲线由阶、节点向量、控制多边形共同确定所以b 样条曲线 的拟合就是根据拟合点列确定b 样条曲线的阶、节点向量、控制多边形 在实践中，广泛采用三次( 四阶) b 样条曲线作为拟合曲线这是因为：( 1 ) 它 是次数最低的俨类样条，这里的二阶连续是大多数工程和数学物理问题所需 要的，次数低则带来计算的简便和稳定；( 2 ) 它是能设计拐点的最低次数的多项 式曲线；( 3 ) 它是放样工艺中绘制曲线用的木样条的数学模型的线性近似；( 4 ) 它 在数学上有很强的收敛性质 1 6 3 1 一般确定控制顶点数可以用试验的方法，就是从一个比较小的数( 比如4 ) 开始，逐渐增加到直到符合误差要求为止相比而言，节点的选择是一个更 加困难的问题，因为它对拟合曲线的影响很大 1 4 0 l ，相关的文献也很多其 6c a g d 巾细分和拟合的造型方法研究 方法人致可分为经验型【9 9 1 、优化算法型 1 4 0 1 、迭代型【8 1 ，8 8 】、数据自适应型 等【7 1 ，9 0 ，1 0 6 ，1 1 1 给定一组数据点q ( i = 0 ，l ，m ) ，数据点对应的参数一般用均匀参数 化、累积弦长参数化、向心参数化1 6 z ，修正弦长参数化【3 6 】等参数化方法这几 种方法没有本质上的优劣之分，要根据具体例子才能确定哪一种好一点 定好了拟合曲线的次数、节点向量、数据点处的参数值，就可以用最小二乘 法f 9 9 1 米求拟合曲线的控制多边形但如果节点向量取得不恰当的话可能会导致 无解的情形另外，还可用带权和约束的最小二乘法拟合 拟合的一个重要问题是计算数据点到拟合曲线的误差误差通常是指最大 距离o m 。a x m i i q t p ( 屯) 吣或o m 。a 。x 。 器现l l q p ( t i ) l l 后者称为最大范数距 离，也往往是实践中所需要的，其计算可参见f 9 9 】当然最简单的方法是数值方 法，就是在曲线上取足够多的点，逐个计算它们到数据点的距离，最小距离当作 是这个点到拟合曲线的距离 拟合过程中的形状控制是一个更难的问题，因为曲线的凸性一般认为是 一个非线性的问题，很难融合