（计算数学专业论文）cagd中近似转化的研究.pdf

2 0 0 3 年中国科学技术大学博士学位论文 摘要 第v 页 摘要 摘要 盐线曲面的近似转化问题是近年来c a g d 领域所讨论的热点问题之一。本文 主要讨论了b 6 z i e r 曲线曲面的降阶逼近和两相邻b 6 z i e r 曲线曲面的合并逼近， 即b 6 z i e r 曲线曲面的近似转化问题。本文所做的工作如下： 系统地综述了曲线曲面近似转化研究的发展历史、现状和研究成果。 根据两b 6 z i e r 曲线在最小二乘范数下的距离函数取最小值，给出b 6 z i e r 曲 线的一种降阶方法；把曲线拟合方法与广义逆矩阵理论相结合，给出b 6 z i e r 曲 线的另一种降阶方法。两种降阶方法均可把给定的n 次b 6 z i e r 曲线一次降为m 次 的b 6 z i e r 曲线。两种方法均考虑了不带端点插值条件和具有端点高阶插值条件 的情形，并给出降阶b 6 z i e r 曲线控制顶点的显示表示式。把b 6 z i e r 曲线一次降 一m 阶的两种方法推广到张量积b 6 z i e r 曲面和三角b 6 z i e r 曲面上，分别得到张 量积b 6 z i e r 曲面和三角b 6 z i e r 曲面的两种降阶方法。张量积b 6 z i e r 曲面的两种 降阶方法均可把 m 阶张量积b 6 z i e r 曲面一次降阶为胛。m ，阶张量积b 6 z i e r 曲 面；三角b 6 z i e r 曲面的两种降阶方法均可把”阶三角b 6 z i e r 曲面一次降阶为m 阶 三角b 6 z i e r 曲面，并给出降阶张量积b 6 z i e r 曲面和降阶三角b 6 z i e r 曲面控制顶 点的显示表示式。在张量积b 6 z i e r 曲面的降阶中，分别考虑了不带角点插值条 件和具有角点高阶插值条件的情形。 给出了把两相邻b 6 z i e r 曲线合并成一条b 6 z i e r 曲线的两种合并方法。一种 方法是利用b 6 z i e r 曲线细分后的矩阵表示，并根据所定义的待合并b 6 z i e r 曲线 与合并b a z i e r 曲线之间的距离函数取最小值得到的：另一种方法是把曲线拟合 方法与广义逆矩阵理论相结合得到的。两种合并方法均给出了在各种合并条件下 的合并b 6 z i e r 曲线控制顶点的显示表示式。另外，两种合并方法还具有以下优 点：( 1 ) 直接给出合并b 6 z i e r 曲线控制顶点的显示表示式，( 2 ) 不论待合并的两相邻 b 6 z i e r 曲线是否同次，都可直接合并，( 3 ) 不需对待合并b 6 z i e r 曲线事先进行升阶 变换，就可直接得到更高次的合并b 6 z i e r 曲线。同样，b 6 z i e r 曲线的两种合并方 法也被成功的推广到张量积b 6 z i e r 曲面上，得到把两片相邻张量积b 6 z i e r 曲面 2 0 0 3 年中国科学技术大学博士学位论文 摘要 第v i 页 摘要 合并成一片张量积b 6 z i e r 曲面的两种合并方法，并给出在各种合并条件下的合 并曲面控制顶点的显示表示式。 文中给出大量的数值实例，来显示所给出的各种方法的效果；同时，在数值 实例中，还把用文中方法所得结果与用已有方法所得结果进行比较。 关键词：计算机辅助几何设计，b 6 z i e r 曲线，b 6 z i e r 曲面，降阶，合并， 曲线拟合方法，端点插值，角点插值，最小二乘范数，显示表示式，细分。 2 0 0 3 年中国科学技术大学博士学位论文 a b s t r a c t 第v i i 页 a b s t r a c t a b s t r a c t i nr e c e n t l yy e a r s ，a p p r o x i m a t ec o n v e r s i o no fc u r v e sa n ds u r f a c e si so n eo fh o t t o p i c si nc a g d t h i sp a p e rd i s c u s s e st h ed e g r e er e d u c t i o no f b a z i e r c u r v e s s u r f a c e s a n da p p r o x i m a t em e r g i n go ft w oa d j a c e n tc u r v e s s u r f a c e s t h a ti st h ea p p r o x i m a t e c o n v e r s i o no f b 6 z i e rc u r v e sa n ds u r f a c e s w ep r e s e n to u rr e s e a r c h e sa sf o l l o w s ： w e s y s t e m a t i c a l l ys u r v e yt h eh i s t o r yo fa p p r o x i m a t ec o n v e r s i o nf o rc u r v e sa n d s u r f a c e s ，a n dt h ep r e s e n ts t a t u sa n dr e s u l t s i nt h em e a n so ft h em i n i m i z i n g l 2n o r m d i s t a n c ef u n c t i o no ft w ob 6 z i e rc u r v e s ， o n em e t h o di s p r o p o s e d ，a n db yc o m b i n i n gt h ef i t t i n gm e t h o do fc u r v e sw i t l lt h e t h e o r yo f t h eg e n e r a li n v e r s em a t r i x ，a n o t h e rm e t h o di sp r e s e n t e d e a c ho ft w oa b o v e m e t h o d sr e d u c e sag i v e nd e g r e e b 6 z i e rc u r v e st oad e g r e emb 6 z i e rc u r v e i n t h e p r o c e s so f d e g r e er e d u c t i o n ，t w o c a s e sa r ec o n s i d e r e dr e s p e c t i v e l y o n ei st h ec a s e w i t h o u tc o n d i t i o n so fe n d p o i n t si n t e r p o l a t i o n s t h eo t h e ri st h ec a s ew i t hc o n d i t i o n s o f e n d p o i n t sh i g h e ro r d e ri n t e r p o l a t i o n s t h ee x p l i c i tf o r m u l a so f c o n t r o lp o i n t so f t h e r e d u c e db 6 z i e rc u r v e sa r eo b t a i n e d t w oa b o v em e t h o d sa r eg e n e r a l i z e dt ot e n s o r p r o d u c tb 6 z i e rs u r f a c e sa n dt r i a n g u l a rb 6 z i e rs u r f a c e s ，w eg i v et w oa p p r o a c h e so f d e g r e er e d u c t i o nf o rt e n s o rp r o d u c tb 6 z i e rs u r f a c e s ，e a c ho fw h i c hr e d u c e sag i v e n d e g r e e 玎xmt e n s o rp r o d u c tb 垂z i e rs u r f a c et oa 疗l m i o n e ，a n dt w om e t h o d so f d e g r e e r e d u c t i o nf o rt r i a n g u l a rb 6 z i e rs u r f a c e s ，w h i c hr e d u c eag i v e nd e g r e e t r i a n g u l a rb 6 z i e rs u r f a c et oad e g r e e mo n e t h ee x p l i c i tf o r m u l a so fc o n t r o lp o i n t s f o rr e d u c e dt e n s o rp r o d u c ta n d t r i a n g u l a rb 6 z i e rs u r f a c e sa r eo b t a i n e dr e s p e c t i v e l y i n t h ep r o c e s so fd e g r e er e d u c t i o nf o rt e n s o rp r o d u c tb 6 z i e rs u r f a c e s ，w ed i s c u s sn o t o n l y t h ec a s ew i t hc o n s t r a i n t so fc o r n e r s i n t e r p o l a t i o n s b u ta l s ot h a tw i t h o u t c o n s t r a i n t so fc o m e r si n t e r p o l a t i o n s t w o a p p r o a c h e st oa p p r o x i m a t i n gt w oa d j a c e n tb 6 z i e rc u r v e sb y a s i n g l eb 6 z i e r c u r v ea r ep r o p o s e d o n ei sp r e s e n t e db y u s i n gt h em a t r i xr e p r e s e n t a t i o no f s u b d i v i d e d b 6 z i e rc u r v ea n db y m i n i m i z i n gt h ed i s t a n c ef u n c t i o nd e f i n e d b e t w e e nt h eo r i g i n a lb 6 z i e rc u r v e sa n dt h em e r g e db 6 z i e rc u r v e ，t h eo t h e ri so b t a i n e d b yc o m b i n i n gt h e f i t t i n gm e t h o do f c u r v e sw i t ht h et h e o r yo ft h eg e n e r mi n v e r s em a t r i x m o r e o v e r , t w o m e r g i n gm e t h o d s h a v et h ef o l l o w i n gt h r e ev i r t u e s ：( 1 ) t h ee x p l i c i tr e p r e s e n t a t i o no f c o n t r o lp o i n t so ft h em e r g e db 6 z i e rc u r v ei so b t a i n e dd i r e c t l y ( 2 ) t h em e r g e db 6 z i e r c u r v ei sa l w a y sp r e s e n t e dd i r e c t l yw h a t e v e rt h ed e g r e e so ft w o a d j a c e n to r i g i n a lb 6 z i e rc u r v e sa r ee q u a lo rn o t ( 3 ) n o tl i k et h eo l dm e t h o d st h a th a v et oe l e v a t et h ed e g r e e 2 0 0 3 年中国科学技术大学博士学位论文 a b s t r a c t 第v i i i 页 a b s t r a c t o ft w oa d j a c e n to r i g i n a lb 6 z i e rc u r v e s ，w eg i v et h eh i g h e ro r d e rm e r g e db 6 z i e rc u r v e d i r e c t l y t w om e r g i n g m e t h o d so fb 6 z i e rc u r v e sa r eg e n e r a l i z e dt ot e n s o rp r o d u c tb 6 z i e rs u r f a c e s ，w ep r o p o s et w om e t h o d st oa p p r o x i m a t et w o p i e c e so fa d j a c e n tt e n s o r p r o d u c tb 6 z i e rs u r f a c e sb yap i e c eo ft e n s o rp r o d u c tb 6 z i e rs u r f a c e w eo f f e rt h e e x p l i c i tf o r m u l a so ft h em e r g e dt e n s o rp r o d u c tb 6 z i e rs u r f a c e sw i t ha l l k i n d so f m e r g i n g c o n d i t i o n s i nt h i sp a p e r , a m a n y o fn u m e r i c a le x a m p l e sa r ep r e s e n t e dt oi l l u s t r a t et h ee f f e c t s o fo u rm e t h o d s w em a k et h ec o m p a r i s o n sb e t w e e nt h er e s u r so b t a i n e db yo u r m e t h o d sa n dt h o s ep r e s e n t e db yc u r r e n tm e t h o d s 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 ( c a g d ) ，b 6 z i e rc u r v e ，b 6 z i e r s u r f a c e ，d e g r e er e d u c t i o n ，m e r g i n g ，t h ef i t t i n g m e t h o do fc u r v e s ，l e a s t s q u a r e s n o r m ( l 2 ) ，e n d p o i n ti n t e r p o l a t i o n ，c o r l l e ri n t e r p o l a t i o n ，e x p l i c i tr e p r e s e n t a t i o n ， s u b d i v i s i o n 致谢 光阴似箭，日月如梭，在科大学习的时光即将成为美好的回忆，这段经历， 令我终身受益，终生难忘。以此文作为总结。 首先，我真诚地感谢我的导师朱功勤教授。感谢他多年来在学业上和生活上 给予的悉心指导和热心帮助。导师以他敏锐的洞察力和丰富的经验，在许多问题 上给我以及时的指导和启迪。本文正是在他的直接指导和鼓励下完成的，从开题、 撰写，到最后定稿，都凝聚了他大量的心血。导师渊博的专业知识，严谨的治学 态度，谦逊的为人和孜孜不倦的探索精神都给我留下了深刻的印象，并深深地影 响了我，这些必将惠及我将来的学习、工作和生活。 在科大几年的学习中，冯玉瑜教授和陈发来教授在学业上给予了大力支持和 帮助，在此，对两位教授表示特别的感谢。另外，两位教授严谨、谦逊的治学态 度和诚实淳朴的作风都是我学习的典范和楷模。同时，黄稚新老师和科大数学系 资料室的各位老师对我的学习也给予了很大的帮助，在此向他们表示深深的谢 意。 此外，还要感谢合肥工业大学理学院的各位领导、信息与计算科学系的各位 领导及同事对我学习的支持和关心。感谢邬弘毅教授，檀结庆教授，林京副教授， 朱晓临副教授和理学院计算中心的各位老师给予的帮助。 我要向我的父母，家人说声谢谢，他们对我的期待和信任是我积极进取、不 断前进的动力源泉，他们浓浓的亲情是我生活中最重要的快乐之源；尤其是我的 妻子和女儿，她们的理解、支持、关爱和鼓励伴随我走到今天，直至永远，愿将 此文献给她们。 最后，要感谢评阅、评议博士论文和出席博士论文答辩会的各位专家学者， 感谢他们在百忙之中所给予的指导。 2 0 0 3 年中国科学技术大学博士学位论文 第一章前言 第1 页 l1 概述 1 1 概述 第一章前言 实际部门提出的问题，往往促使一些理论性学科的诞生i 而理论研究的深入， 又使其应用更加广泛。计算机辅助几何设计( 简称为c a g d ( c o m p u t e r a i d e d g e o m e t r i c d e s i g n ) ) 的发展也体现了这样一个规律。 随着c a g d 理论的不断完善，一些实际应用部门开始针对本部门的特殊需 要，设计一些应用性的c a d 系统。如英国的c o n s u r f 系统( b a l l ，1 9 7 4 ， b a l l ，1 9 7 5 】， 肋，1 9 7 7 ) 和b u i l d 系统( b a u m g a r t ，1 9 7 4 ) ，法国的u n s u r f 系 统( 【b 4 z i e r ，1 9 7 2 ， b 6 z i e r ，1 9 7 4 ， b 6 z i e r ，1 9 8 6 ) 和c a t i a 系统，挪威的 a u t o k o n 系统( m e h l u m ，1 9 7 4 ) ，美国的g e o m o d 系统和p a d l 系统，德国的 c o m p a c 系统，日本的t i p s l 系统，中国清华大学的g e m s 系统等等。不同的 c a d 系统可能采用不同的曲线曲面表示方式，且所允许的曲线曲面的最高次数 的限制范围和要求也不同；而随着c a d 系统应用的不断深入，人们希望各c a d 系统的数据可以通过计算机进行交换，这就是c a d 系统数据通讯的问题。 c a d 系统数据通讯中所涉及到的一些有关c a g d 的问题包括 ( d r j ，2 0 0 1 1 ) ： 1 近似转化。由于不同的c a d 系统所允许的曲线曲面次数不同，有必要研 究曲线曲面的近似转化。近似转化又分降阶逼近和近似合并两种，近年来人们感 兴趣的问题有：b 6 z i e r 曲线曲面的降阶逼近，b 样条曲线曲面的降阶逼近, b 6 z i e r 曲线曲面的近似合并，b a l l 曲线曲面升阶与降阶逼近等。 2 形式转化。由于不同的c a d 系统可能采用不同的曲线曲面表示方式，在 数据交换中，常常要将曲线曲面从一种表示方式转化为另一种表示方式。这方 2 0 0 3 拒 第一章前言 中国科学技术大学博士学位论文第2 页 12 曲线曲孟降阶逼近的发展概况 面的问题包括：b 6 z i e r 曲线曲面与b 样条曲线曲面的互化，b 6 z i e r 曲线曲面与 b a l l 曲线曲面的互化，两类b 6 z i e r 曲面间的互化，h e r m i t e 曲线、c o o n s h e r m i t e 曲面和c o o n s 布尔曲面到b 6 z i e r 曲线曲面的转化、参数曲面的广义离散等。 3 t r i m m e d 曲面的表示与交换。t r i m m e d 曲面在曲面造型中，扮演一个非常 重要的角色。尽管自由曲面的t r i m m e d 曲面的方程还是原来曲面的方程，但它的 定义域只是原参数域的一个子集，因此t r i m m e d 曲面的表示与处理都有其特殊 性。近年来人们感兴趣的问题有：t r i m m e d 曲面的表示，t r i m m e d 曲面的三角化 以及t r i m m e d 曲面的数据交换等问题。 4 数据压缩。这里所谓数据压缩是指，如何减少曲线曲面模型中的几何数据 量，与通常的图象压缩是不同的概念。在c a d 系统数据通讯中，人们希望尽量 减少数据通讯量，即减少曲线曲面表示的冗余度。引起人们浓厚兴趣的问题有： b 样条曲线去节点方法，网格化数据的压缩面片简化，几何插值以及重新参数 化方法等。 由此可见，在c a d 系统数据通讯中与c a g d 相关的研究内容还是非常丰富 的。本文将选择具有一定挑战性和处于当前国际研究热点之中的问题近似转 化展开研究，其研究范围包括： 1 b 6 z i e r 曲线的降多阶逼近： 2 b 6 z i e r 曲面的降多阶逼近i 3 b 6 z i e r 曲线的近似合并逼近： 4 b 6 z i e r 曲面的近似合并逼近； 1 2 曲线曲面降阶逼近的发展概况 曲线曲面的降阶逼近即降阶变换，不仅是c a g d 中升阶公式在数学形式上的 逆变换( f a r i n ，1 9 9 1 ) ，更重要的是它所具有的实际应用背景( d a n n e b e r g ，1 9 8 5 ， 【h o s c h e k ，1 9 8 7 】， w a t k i n s ，1 9 8 8 】， f a r i n ，1 9 9 2 ) 。它的实际应用背景主要体现在 2 0 0 3 燕 第一章前言 中国科学技术大学博士学位论文第3 页 1 2 曲线曲面降阶逼近的发展概况 以下四个方面( c h e n ，2 0 0 1 b ) ： 第一，是c a d 系统之间数据传递与交换的需要。不同的外形设计系统，其 多项式基的最高次数不尽相同，许多系统为了运行的有效性，甚至往往限于低次， 这就要求在数据传递之前把几何曲线曲面作近似的降阶变换，以便对方系统能够 接受。 第二，它是计算机图形中分段( 片) 线性逼近的需要。通过与离散相结合的逐 次降阶，把曲线曲面化为直线平面，便于求交和曲面绘制。 第三，它是外形信息压缩的需要。一条有理曲线的多项式逼近曲线，一条参 数曲线的q 历p ，( 等距) 逼近曲线或一张曲面的t r i m m e d ( 裁剪) 边界曲线常常是高次 曲线，模型设计或外形仿制中对数据点的拟合也常常产生高次曲线曲面，降阶处理 以后可以减少存储的信息量。 第四，曲线曲面的光顺处理过程中，也经常需要进行降阶处理。 近年来，曲线曲面的降阶问题已成为计算机辅助几何设计领域中的热点问题 之一，下面我们先简要介绍一下该问题的研究现状。 由于b 6 z i e r 曲线曲面使用的广范性和代表性，人们把它们作为降阶逼近的 研究原型。在此，首先综述一下b 6 z i e r 曲线曲面降阶逼近的研究现状。 b 6 z i e r 曲线是参数多项式曲线，由于它采用了一组独特的多项式基函数，即 b e r n s t e i n 基函数，而b e r n s t e i n 基函数具有许多优良的性质( c h a n g ，1 9 8 4 a ，1 9 8 4 b 1 ， c h a n g ，1 9 9 5 ，【l o r e n t z ，1 9 5 3 ) ，从而使b 6z i e r 曲线也具有许多优良的性质 ( b e z i e r ，1 9 7 2 ， g u a n ，1 9 9 9 】， c h a n g ，1 9 8 0 】， f a u x ，1 9 7 9 1 ) ；b 6 z i e r 曲面是b 6 z i e r 曲 线的推广，分张量积的b 6 z i e r 曲面和三角b 6 z i e r 曲面。自b 6 z i e r 曲线曲面问世 以来，人们从未间断过对它们本身及应用的研究，取得了一系列的研究成果 ( 勋，1 9 8 0 1 ， l i u ，1 9 8 1 ， l i u ，1 9 8 2 ， c h u ，2 0 0 2 ， s h i ，1 9 8 2 ， l i u ，1 9 8 7 ， h u ，2 0 0 1 a 】 ， r i d a ，2 0 0 1 ， j e n a ，2 0 0 1 ，【p r z e m y ，2 0 0 1 】，【c h e n ，2 0 0 3 】， g e r a l d ，2 0 0 1 】， 2 0 0 3 矩 第一章前言 中国科学技术大学博士学位论文第4 页 12 曲线曲面降阶逼近的发展概况 w a n g ，1 9 8 4 】， z h a o ，2 0 0 3 ) 。在有理b 6 z i e r 曲线曲面及应用方面的研究也取得了 丰硕的成果( l i u ，1 9 8 5 ， w a n g ，1 9 8 5 】， l i u ，2 0 0 3 a ， w a n g ，2 0 0 0 ， x u ，1 9 9 2 【w a n g ，1 9 8 6 】， f o r r e s t ，1 9 8 0 ，【e i e g t ，1 9 8 5 ， c h e n ，2 0 0 1 c ， k a n g ，1 9 8 7 ) 。从b 6 z i e r 曲线曲面的降阶逼近被提出以来至今，国内外的学者和研究人员通过不懈的努 力，给出了许多降阶方法，这些方法大致可分为以下两大类( w a n g2 0 0 1 ) 。 ( 一) 控制顶点逼近的几何方法：1 9 7 2 年f o r e s t 把降阶看作是升阶的反过 程( f o r r e s t ，1 9 7 2 ) ，给出了一种b 6 z i e r 曲线降阶方法，该方法可使降阶曲线与原 曲线在首末端点达到高阶插值。f a r i n 用同样的思想也给出了b 6 z i e r 曲线降阶的 一种方( f a r i n ，1 9 8 3 1 ) 。以上两种降阶方法的误差估计由_ p d 船等( p a r k ，1 9 9 4 ) 给出：但由于降阶精度低，并不实用。d a n n e b e r g ( d a n n e b e r g ，1 9 8 5 ) 利用原曲 线采样点的位矢和导矢，用分段插值曲线进行降阶逼近。 h o s c h e k ( h o s c h e k ，1 9 8 7 】， h o s c h e k ，1 9 9 2 ) 用低次样条曲线y 插值原曲线x ，利用 一与y 的一、二阶几何连续条件。= a y 。以及x “= 刀y ”+ “j ，通过求离散点采 样的f i x l ，i f 的最小二乘解，求得五，t 之值和y 的控制顶点。由于逼近曲线段数 过多且需递归调整离散点参数，这一方法存储量大又费时。m o o r e ( m o o r e ，1 9 9 1 ) 以新旧曲线所夹面积极小为条件反求降阶曲线的控制顶点。 l o d h a ( l o d h a ，1 9 9 4 ) 以低次b 6 z i e r 单形的凸线性组合来几何逼近高次b 6 z i e r 单 形。这两种方法比较繁琐，且效率也不高。胡事民( h u ，1 9 9 6 a ， h u ，1 9 9 8 a ) 考 虑了b 6 z i e r 曲线的退化条件，利用扰动控制顶点和约束最小二乘方法来实现b 6 z i e r 曲线的降阶，该方法称为b 网扰动和约束优化法。b 网扰动和约束优化法， 具有明显的几何直观性，可同时适于曲线曲面的降阶( 协，1 9 9 7 ， h u ，1 9 9 8 b 1 ) 。 2 0 0 3 年 第一章前言 中国科学技术大学博士学位论文第5 页 1 2 曲线曲面降阶逼近的发展概况 用于曲线降阶时，给出显示格式和误差估计，结合离散算法可达到商精度，且保 持g 1 连续：用于b 6 z i e r 矩形片( h u ，1 9 9 7 1 ) 矛f i z n 片( 胁，1 9 9 8 b ) 降阶时，把降 阶问题转化为求解线性方程组，而降阶的误差同样取决原曲面的一些内在几何不 变量。陈国栋( i c h e n2 0 0 1 a ) 基于广义逆矩阵理论给出b o n e r 曲线降阶方法，该 方法将b 6 z i e r 曲线的升阶与广义逆矩阵的最d , - - 乘理论巧妙地结合起来，只要 求解一个线性方程组就可次降多阶，且可使原b 6 z i e r 曲线与降阶b 6 z i e r 曲线 在首末端点达到高阶插值。 ( 二) 基于基转换的代数方法：利用 p 鱼班 p v 多项式 日，( r ) 礁。构成月次 多项式空间的基以及门次多项式q 曩( ，) 的”一1 次最佳一致逼近恰是 j = o 月一1 q h ，( f ) 的性质，w a t k i n s 和w o r s e y ( w a t k i n s ，1 9 8 8 ) 通过把b e r n s t e i n 基变为 f = 0 c h e b y s h e v 基，降阶，再变为b e r n s t e i n 基，得到b o z i e r 曲线高精度降阶逼近算 法。但为保端点插值而使用l a g r a n g e 插值，就失去了最佳逼近性。 l a c h a n c e ( l a c h a n c e ，1 9 8 8 ) 提出约束c h e b y s h e v 多项式的概念来保端点，阶插 值，但r 0 时无显示解。e c k ( e c k ，1 9 9 3 ) 结合运用f o r r e s t 和l a c h a n c e 两人的 技术，首先取降阶曲线只f ) 的顶点互= ( 1 一五她7 + 只“，再利用降阶逼近误差 的公式p ( f ) 一声( ，) = 2 4 ”1 h 。( 2 t 一1 ) 硝“r 来求五，其中h 。( 2 t 1 ) 为【o ，1 】上的 ”+ 1 次c h e b y s h e v 多项式。b r u n n e t t ( b r u n n e t t ，1 9 9 6 ) 探讨了这种逼近的几何意 义a 以上方法都是。空间内最佳一致的逼近。在：空间内的研究，有 e c k ( e c k ，1 9 9 5 ) 用约束多项式所给出的最, j , - - 乘逼近，但为保端点r 0 阶插值 仍无显示解；另外还有l u t t e r k o r t ( l u t t e r k o r t ，1 9 9 9 ) 给出的一种降阶逼近方法。 2 0 0 3 熊 第一章前言 中国科学技术大学博士学位论文第6 页 1 2 曲线曲面降阶逼近的发展概况 以上b 6 z i e r 曲线的降阶方法的局限性在于：( 1 ) 有的计算较繁，有的精度较低。 ( 2 ) 绝大多数降阶方法每次只能降一阶，若需降多阶，则需采用逐次降阶，而 且当逼近曲线要满足端点r ( r o ) 阶插值时，均无显示解，只能数值求解，这不 仅导致计算耗时，而且误差很大。( 3 ) 由于多变量c h e b y s h e v 理论还不完善 ( w a n g ，1 9 8 8 ) ，这一理论推广到解决参数b 6 z l e r 曲面降阶，尤其是非张量积b e z i e r 曲面降阶有一定的困难。1 9 9 5 年，l p i e g l ( p i e g l ，1 9 9 5 1 ) 利用升阶的反过程 对n 次曲线降阶，可保端点( w 2 1 1 ) 阶插值，但其同样每次只能降一阶且误差较 大。同年，b o g a c k i ( b o g a c k i ，1 9 9 5 ) 通过基的转换并舍去多项式中多个高次项， 终于实现了b 6 z i e r 曲线的一次降多阶逼近，但在端点只能达到位矢插值，无法 满足r 0 阶导矢插值。陈国栋和王国瑾利用b e r n s t e i n 基与c 塘e b y s h e v 基和 b e r n s t e i n 基与j a c o b i 基的转换。分别给出了带端点插值条件的b 6 z i e r 益线的近 似最佳一致降多阶逼近 ( c h e n ，2 0 0 0 a ) 和最佳最小二乘降多阶逼近 ( c h e n ，2 0 0 2 a ) ，两种方法均可一次降多阶，又可在曲线首末端点分别达到 r ，s ( r ，s 0 ) 阶插值，且给出了降阶曲线控制顶点的显示表示式，计算简单稳定， 易于实现，还可结合分割算法达到更快速的收敛。l e eb y u n g g o o k ( l e e ，2 0 0 2 ) 利用l e g e n d r e 基和b e t w s t e i n 基的转换给出了b 6 z i e r 曲线升阶和降阶的一个算 法。侯晓辉( h o u ，2 0 0 3 ) 弓i 入了约束l e g e n d r e 多项式，在最小平方模的意义下， 解决了用n 一1 次b 6 z i e r 曲线逼近n 次b 6 z i e r 曲线的问题。 至于有理曲线的降阶，有s e d e r b e r g 和常庚哲( s e d e r b e r g ，1 9 9 3 】利用最佳线 性公因子，给出的平面有理b 6 z i e r 曲线的一个降阶方法；陈发来( c h e n ，1 9 9 3 ) 利用移位的c h e b y s h e v 多项式进一步实现了保端点插值的有理曲线降阶逼近；曾 2 0 0 3 盔 第一章前言 中国科学技术大学博士学位论文第7 页 12 曲线曲面降阶逼近的发展概况 芳玲( 盈昭，2 0 0 2 1 ) 采用最优逼近，结合曲线的基对有理参数曲线进行降阶。 另外陈发来和娄文平( c h e n ，2 0 0 0 b ) 采用最优逼近作为降阶手段，实现了区间b 6 z i e r 曲线的降阶逼近，取得了很好的效果。胡事民( h u ，1 9 9 6 b ) 利用扰动控制顶 点和约束最小二乘方法来实现b a l l 曲线的降阶逼近。b 样条曲线，既拥有b e z i e r 曲线的几何特性，又拥有形状局部可调及连续阶数可调等b 6 z i e r 曲线所没有的 特性( z h u ，2 0 0 0 ， s h i ，2 0 0 1 ， z h o u ，1 9 9 4 ) 。国外的p r a u t z s c h ( p r a u t z s c h ，1 9 9 1 ) ， e c k ( e c k ，19 9 5 b 1 ) ，d eb o o r ( b o o r ，19 7 2 1 ， b o o r ，19 7 6 ) ，c o h e n ( c o h e n ，19 8 0 ) c o x ( c o x ，1 9 7 1 ) ，b o e h m ( b o e h m ，1 9 8 4 ， b o e h m ，1 9 8 5 a ， b o e h m ，1 9 8 5 b ) 和国内 的梁友栋( l i a n g ，1 9 8 2 1 ) ，吕伟( l v ，1 9 9 0 ，汪嘉业( w a n g ，1 9 8 4 b ) 等都对b 样 条的理论作出了积极的贡献。近年来，国内外的研究者在b 样条曲线的理论和 应用方面，特别是非均匀有理b 样条的理论和应用方面又取得了一些令人瞩目 的成果( l i ，2 0 0 3 a 】， l i ，2 0 0 3 b ， f a n ，1 9 9 7 】， q 帆1 9 9 5 1 ， p a n ，2 0 0 1 1 ， p a n ，2 0 0 3 ， m e e k ，2 0 0 3 ， l i u ，2 0 0 3 b ， l i ，1 9 9 9 】， c h e ，2 0 0 2 ，【h u ，2 0 0 2 】，【d j o r d j e ，2 0 0 2 ， p i e g l ，2 0 0 2 ) 。在b 样条曲线降阶方面，p i e g l 和t i l l e r ( p i p ，1 9 9 5 ) 分解原曲线 为一系列b 6 z i e r 曲线段，再用升阶反过程来降阶：w o l t e r s ( w o l 据r ，1 9 9 8 1 ) 运用了 基于b 样条曲线升阶的b l o s s o m i n g 法，给出了b 样条曲线的降阶逼近方法； y o n g ，2 0 0 1 、 y o n g ，2 0 0 0 】和【q i n ，2 0 0 0 】也给出了b 样条曲线的降阶逼近。潘日晶 ( d y j ，2 0 0 2 ) 给出了b 样条曲线最小二乘降阶方法。陈发来( c h e n ，2 0 0 2 b ) 研究了 区间b 样条曲线的降阶逼近。 在参数曲面降阶逼近方面的研究，主要集中在b 6 z i e r 曲面方面，目前的工作 2 0 0 3 盘 第一章前言 中国科学技术大学博士学位论文第8 页 1 3 曲线曲面合并逼近的发展概况 有( d a n n e b e r g ，1 9 8 5 ， h o s c h e k ，1 9 8 7 ， l a c h a n c e ，2 9 8 8 1 ， 七，1 9 9 5 ) ， h u ，1 9 9 8 a ) 等中曲线降阶方法的推广，以及 c h e n ，2 0 0 2 c 矛1 1 z h o u ，2 0 0 2 所给出的方法。另外 孙红兵( s u n ，2 0 0 2 ) 给出了区间b 6 z i e r 曲面的降阶方法：胡事民把 h u ，1 9 9 8 a 中 的b 6 z i e r 曲线降阶方法应用到三角b 6 z i e r 曲面上，给出了三角b 6 z i e r 曲面的降 阶逼近方法。 1 3 曲线曲面合并逼近的发展概况 h o s c h e k ( h o s c h e k ，1 9 8 7 ) 提出并研究了参数曲线合并逼近的问题，2 0 0 1 年， 胡事民等( h u ，2 0 0 1 b ) 根据两相邻n 次b z i e r 曲线能够精确合并成一条昨次b 6 z i e r 曲线的条件，利用控制顶点扰动法，给出两种范数度量下的两相邻九次b 6 z i e r 曲 线合并成一条h 次b 6 z i e r 蓝线的方法。该方法首先通过求解线性方程组，得原越 线控制顶点的扰动量；然后利用外插法，得到合并曲线的控制顶点。在合并过程 中既考虑了合并曲线与原曲线在端点插值及高阶导矢插值的情形，又考虑了合并 曲线插值于原曲线上的某些点的情形：另外还指出，若要减小合并误差，改善合 并曲线对原曲线的逼近效果，必需先对原曲线进行升阶，然后再把升阶后的曲线 合并成相应阶数的曲线。杨霄峰( 场馏，2 0 0 1 ) 考虑了区间b 6 z i e r 曲线的合并问 题；杨武( r a n g ，2 0 0 3 1 ) 研究了圆域b 6z i e r 曲线的合并问题。c h i e w - l a n t a i ( t a i ，2 0 0 3 1 ) 根据两相邻n 次b 样条曲线能够精确合并成条n 次b 样条曲线的 条件，利用控制顶点扰动法，给出把两相邻”次b 样条蓝线合并成一条n 次b 样 条曲线的方法，为使所得合并b 样条曲线没有多余的节点，利用了在不改变原b 样条形状的情形下的节点调整方法，在合并过程中，还考虑了合并b 样条曲线与 原b 样条曲线在端点插值的情形。关于相邻参数衄面合并逼近的研究，迄今为止， 作者还没有看到有关的文献。 2 0 0 3 年 第一章前言 中国科学技术大学博士学位论文第9 页 1 4 本文所做工作的概述 1 4 本文所做工作的概述 本文对b 6 z i e r 曲线曲面的降阶逼近问题和两相邻b 6 z i e r 曲线曲面近似合并逼 近问题进行了深入研究。 第一章中我们已经综述了曲线曲面的近似转化( 降阶逼近和合并逼近) 的研 究意义和概况，特别详细地论述了近似转化在c a g d 中的重要地位，分析了国际 图形界对近似转化的研究方法及优缺点，在这个基础上引申出本文的研究课题。 第二章第一节根据原b 6 z i e r 曲线与降阶b 6 z i e r 曲线间的在最小二乘范数下的 距离函数取最小值，给出b 6 z i e r 曲线的