（计算数学专业论文）基于拟插值的b样条曲面拟合方法.pdf

大连理工大学硕士学位论文 摘要 、散乱数据点的曲面拟合问题是函数逼近论中的一个重要内容，在很多领域内有着 重要的意义与使用价值。& 样条方法是计算机辅助几何设计( c a g d ) 的一类重要方 法。本文对散乱数据点的b 样条曲面拟合方法进行了一些讨论与研究。 第一章引入了散乱数据点的曲面拟合问题，并介绍了该领域内的几种重要的研究 方法。 第二章简单介绍了b 样条曲线曲面及其基本性质。 第三章主要介绍了基于拟插值的层次b 样条曲面重构方法，并对层次逼近方法及 一类由拟插值方法派生出的局部样条逼近方法作了简单的阐述。 第四章讨论了一类基于拟插值的层次非张量积型b 样条曲面拟合方法。该算法利 用均匀2 型三角剖分上的二元2 次b 样条通过拟插值方法构造出非张量积型的& 样 条曲面，在此基础上，应用层次逼近算法来逐步逼近给定的散乱数据点集。数值实验 显示了这种方法是可行的，而且对散乱数据点拟合的效果也是比较好的。 最后总结全文并提出了一些有待于进一步研究的问题。 关键词：散乱数据；b - 样条；曲面拟合；拟插值；层次逼近 一i - 基于拟插值的b 样条曲面拟合方法 b s p l i n es u r f a c ef i t t i n gb a s e do nq u a s i - i n t e r p o l a t i o n a b s t r a c t t h ep r o b l e mo fs u r f a c ef i t t i n gf r o ms c a t t e r e dd a t ai sa ni m p o r t a n ta r e ai na p - p r o x i m a t i o nt h e o r y i ti so fg r e a ts i g n i f i c a n c ea n de x t e n s i v ea p p l i c a t i o n si nm a n yf i e l d s b - s p l i n em e t h o dp l a y sa l li m p o r t a n tp a r ti nc o m p u t e ra i d e dg e o m e t r yd e s i g n ( c a g d ) s o m ea n a l y s i sa n dd i s c u s s i o n so nt h em e t h o do fb - s p l i n es u r f a c ef i t t i n gf r o ms c a t t e r e d d a t aa r ep r e s e n t e di nt h i sd i s s e r t a t i o n t h ep r o b l e mo fs u r f a c ef i t t i n gf r o ms c a t t e r e dd a t ai si n t r o d u c e di nc h a p t e r1 ，a n d a l s os e v e r a li m p o r t a n tm e t h o d sa r ep r e s e n t e d b - s p l i n ec u r v e sa n ds u r f a c e sa n dt h e i rm a i np r o p e r t i e sa r ed e s c r i b e di nc h a p t e r2 ak i n do fs u r f a c er e c o n s t r u c t i o nm e t h o df r o ms c a t t e r e dd a t ai sp r e s e n t e di nc h a p t e r 3 i ti sb a s e do nm u l t i l e v e lb - s p l i n ea p p r o x i m a t i o na l g o r i t h ma n dq u a s i - i n t e r p o l a t i o n i nc h a p t e r4 ，as u r f a c ef i t t i n gm e t h o db a s e do nq u a s i - i n t e r p o l a t i o nf r o ms c a t t e r e d d a t ai sd i s c u s s e d u s i n gt h i sm e t h o d ，n o n - t e n s o rp r o d u c tb s p l i n es u r f a c ei sc o n s t r u c t e d w i t hb i n a r yq u a d r a t i cb - s p i n eo nu n i f o r mt y p e - 2t r i a n g u l a t i o n t h e nm u l t i l e v e lb - s p l i n ea p p r o x i m a t i o na l g o r i t h mi su s e dt oc i r c u m v e n tt h et r a d e o f fb e t w e e nt h es h a p e s m o o t h n e s sa n da c c u r a c yo ft h ea p p r o x i m a t i o n e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a t t h i sm e t h o di sf e a s i b l ea n dh a sg o o dp e r f o r m a n c eo ns u r f a c ef i t t 沁f r o ms c a t t e r e dd a t a f i n a l l yas u m m a r yo ft h i sd i s s e r t a t i o ni sg i v e na n ds e v e r a lp r o b l e m sw h i c ha w a i t f u r t h e rd i s c u s s i o na r ep r o p o s e d k e yw o r d s ：s c a t t e r e dd a t a ；b - s p l i n e ；s u r f a c ef i t t i n g ；q u a s i - i n t e r p o l a t i o n ；m 止 t i l e v e la p p r o x i m a t i o n i i 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：基于拟插值的b 一样条曲面拟合方法 作者签名：二塑 二丽_ 二迈二二z z 五二 导 师签 名：毒玉垒址日期：j 止年正月卫日 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方 外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已 申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的 贡献均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：基于拟插值的b 一样条曲面拟合方法 作者签名：趁垒 日期：坦堡年型月五日 大连理工大学硕士学位论文 1 绪论 1 1问题引入 本节内容主要来自参考文献 1 】。 1 1 1问题的来源及应用背景 ( 1 ) 来自应用的问题。 天气预报中需要地面气温的等值线图，这是通过一些地面温度测量点得到的一些 散乱的数据来描述温度对于地面坐标的两个变量的函数，这是一个散乱数据的拟合问 题。如果还要给出气温变化的趋势图，那么我们还要通过譬如风向、地形等使温度变 化的信息来描述未来的温度分布，这是一个更加复杂的散乱数据的拟合问题。 在临摹、仿制及考古的古生物复原问题中，人们经常要通过临摹、仿制对象的一 些测量值来绘制该对象的外形，从而制模。由于临摹、仿制对象的形状的复杂性，所 以这也是一个散乱数据的拟合问题。 ( 2 ) 数学本身要求解决的问题。 有很多复杂的函数很难用数学公式来描述，如果还要求对这类函数积分、微分或 者求与这类函数有关的微积分方程的解，那么只能采用数值的方法，也就是说要用简 单的函数来描述、逼近复杂函数，然后由对简单函数的运算来模拟、逼近对复杂函数 的运算。计算机的发展也对我们提出了这样的研究课题：如何用简单的离散的函数表 示复杂的连续函数，这实际上都是散乱数据的拟合问题。 1 1 2 问题的描述 众所周知，现实世界是由连续曲面而非离散点所构成的。我们的目的是构造出光 滑的三维曲面来逼近散乱数据点集，而且要使逼近的误差控制在一定范围内。散乱数 据指的是在二维平面域或三维空间中随机分布的采样数据点。拟合可分为插值和逼近 两种方法。插值就是拟合出来的目标曲线或曲面必须通过所有的采样点；逼近只是对 采样点进行有权逼近，不一定要求所有的采样点都落在目标曲线或曲面上，而只需要 满足用户的反求设计要求即可1 2 1 。拟合问题的基础是插值问题： f - - l 题1 1 【1 】给定巧掣，乃r ，j = 1 ，n ，寻找函数，( z ) ，满足，( 巧) = i ，j = 1 ，。n 1 - 基于拟插值的b 一样条曲面拟合方法 进一步地，我们可以讨论更一般的问题。 问题1 2 【1 】是c ( r d ) 上的线性泛函，给定数据乃r ，歹= 1 ，n ，希望寻找 c ( r d ) 中的函数，( z ) ，满足，( z ) = 乃，j = 1 ，n 这个问题依赖于很多方面的因素【3 】，包括：数据是精确的还是有测量误差或是噪 声的；数据是否具有统计上的分布规律；拟合函数，需要具有哪些性质，例如光滑性 等。这个问题太庞大，太复杂了。我们希望找到的函数与研究对象函数有很好的相似 性质，这包括误差小这个逼近性质以及形状相似这个几何性质。另一方面，如果找到 的函数不能很好地或很快地用计算机数值描述，也偏离了我们的目标。所以在讨论上 述问题时，我们还要分析在哪个函数类里寻找函数f ( x ) ，还要分析解的存在性、唯一 性及寻找求解的算法和讨论算法稳定性等问题。 1 1 3 插值问题的h a a r 条件 在单变量的插值问题中，如果 ) o = 1 ，n ) 是一系列函数( 基函数) ，对任何 两两不同的点的集合 巧) 冬l ，矩阵( ( z 七) ) 都是非奇异的，那么就可以通过解一个线 性方程组 幻( = ，七= 1 ，n j = l 得到一个形式为 ，+ ( z ) = 口j b j ( x ) j = l 的插值函数，满足广( x j ) = f j 。这样的插值方法统称为e u l e r 插值方法，对任何两两 不同的数据点都存在e u l e r 插值的函数系称为t s c h e b y s c h e f f 系。 为了解决多元散乱数据的插值问题，我们首先想到的是e u l e r 插值方法，即选择 一组函数向( z ) ( 最好是多项式，但也- 7 p a 是其他的函数，称为基函数) ，令 ，( z ) = 幻( z ) ， j = l 然后通过待定系数方程 ，( 砜) = 叻( 孤) = ，k = 1 ，n j = l 来决定系数口，。用这样的方法，要使线性方程组对任意选定的两两不同的测量点都有 解，则要求其系数矩阵的行列式对任何两两不同的测量点都不为零。这导出了我们必 须考虑的对任何的两两不同的数据点插值问题解的存在唯一性条件一h a 8 r 条件。 一2 - 大连理工大学硕士学位论文 定义1 1 【1 】称函数族6 j ( z ) c ( r d ) ，ji1 ，n 满足h a a r 条件，如果对任何两 两不同的点巧r d ，歹= 1 ，n ，矩阵( b 七) ) 都是非奇异的。 固定维数的空间表现函数的能力总是有限的。如果我们要利用某个函数空间逼近 任何的函数，或者希望对任何多个数据点插值问题都有解，那么就需要一个函数系。 定义1 2 【1 】函数系 ( z ) ) c ( 刺) ，j = 1 ，对任何n 都满足h a a r 条件，那 么我们称这个函数系是一个t s c h e b y s c h e f f 系 只有当函数系满足这样的条件时，对任何位置、任何个数的数据点z f ，及测量值 厅，e u l e r 方程有解且解是唯一的，否则可能对某些测量值方程无解，而对另一些数据 可能是多解的。即函数系伯f ( z ) c ( r d ) 对任何的两两不同的数据点e u l e r 方法插值 存在唯一的充分必要条件是：函数系 6 ，( 茁) c ( r d ) 是一个t s c h e b y s c h e f f 系。 在一元曲线情形有很多这样的函数系，譬如单项式系，指数函数系，三角多项式 系，这样就可以导出很多类型的e u l e r 插值公式。可是在多变量情形却有如下定理。 定理1 1 【1 】在多变量情形，任何给定的函数族都不满足h a a r 条件当然更不可能 存在t s c h e b y r s c h e f f 系。 上述定理表明多于两个变量的散乱数据插值问题与单变量插值问题有本质上的不 同。在一元情形得到的各种插值方法一般都不能直接推广到多元情形，这也就是为什 么要把多元散乱数据的拟合作为一个独立的课题研究的原因。 1 1 4 多元散乱数据的多项式插值 单变量情形的多项式空间满足h a a r 条件，所以多项式的l a g r a n g e 插值是可以实 现的，反观多变量情形，多项式函数空间已不满足h a a r 条件，所以l a g r a n g e 插值不 一定存在。多变量函数中我们最熟悉的函数类还是多项式，多项式函数具有微分、积 分、计算机表示简单等优点。本小节我们讨论用多项式对多变量函数散乱数据插值的 可能性。为了描述方便，我们只讨论两个变量的情形。 定理1 2 【1 】给定两两不同的测量点 ( 奶，协) ) 器o r 2 及在测量点相应的函数测量 值 乃) 饕o ，至少存在一个关于各分量次数都不超过n 的多项式 nn p ( z ，秒) = 咖一矿， j = ok - - - - 0 满足p ( q ，协) = 力 一3 _ 基于拟插值的b 一样条曲面拟合方法 此时空间是( n + 1 ) 2 维的，而约束条件只有m + 1 ) 个，所以解的唯一性就不能保 证了。 定理1 3 1 1 】任给两两不同的测量点 x j j = o r d 及在测量点相应的函数测量值 【办】各o ，那么至少存在一个次数和不超过n 的d 元多项式p ( z ) ，满j z p ( x j ) = 乃 1 2 曲面拟合算法介绍 有关散乱数据的蓝面拟合问题国内外已经有了一系列的研究成果。文献【4 】对上世 纪8 0 年代初期的一些方法从时间复杂度、空间复杂度、计算精度、视觉满意度及算法 实现的难易度等方面做出了一系列的比较。本节内容主要来自参考文献 5 】和【6 】。 ( 1 ) d e l a u n a y 法 散乱数据曲面拟合最直接的方法是应用v o r o n o i 图对散乱数据点集进行d e l a u n a y 三角化。1 9 7 2 年，l a w s o n 提出了三角化的最大角最小原则，符合这一原则的三角形 是局部最优的。这种方法简单、易行，但它仅仅能达到伊连续，而且，对大规模散 乱数据进行三角划分时速度也是一个问题。 ( 2 ) s h e p a r d 法 这一方法首先由气象学及地质学工作者提出【7 8 】，后来由于d s h e p a r d 的工作被 称为s h e p a x d 方法【9 1 。其基本思想是将插值函数定义为各数据点函数值的加权平均， 这是一种与距离成反比的加权方法，插值结果只能是伊连续的。而且，当增加、删 除或改变一个数据点时，需要重新计算所有的权值，因而该方法是一个全局插值算 法。 为了克服s h e p a r d 方法的缺陷，f r a n k e 及n i e l s o n 提出了m q s 方法 x 0 ( m o d i f i e d q u a d r a t i cs h e p a r d ，sm e t h o d l 并产生了c 1 连续插值，它仍然是一个与距离成反比的 加权方法。由于m q s 方法消除了s h e p a r d 方法的一些缺陷，因此在散乱点插值中得 到了广泛的应用，但由于多次求解线性方程组，计算量大，因此，一般只适用于中、 小规模散乱点的插值运算。 ( 3 ) m u l t i q u a d r i c 法 1 9 7 1 年h a r d y 用径向基函数m u l t i q u a d r i c 1 1 】来处理飞机外形设计曲面拟合问题， 是最早提出且应用得最为成功的一种径向基函数插值法。一般来说，这种方法不具有 多项式精度，但只要稍加改进，即可获得具有多项式精度的插值公式。这一方法提出 后的近2 0 年间，在水文测量、大地测量、地质及采矿、地球物理等领域得到了广泛应 用，效果良好。在数据点不太大的情况下，计算也较简单，但是，对其解的存在性等 4 大连理工大学硕士学位论文 问题却一直没有数学上的证明，直到1 9 8 6 年，才由m i c c h e u i 【1 2 】对这一方法为什么能 工作得很好给出一些解释。 ( 4 ) 有限元法 这是一种与上述方法完全不同的散乱点插值法。由于其基本原理与求解偏微 分方程的有限元法相同，因而被称为散乱点插值的有限元法。这种方法首先解决 二维点集的三角剖分问题，之后讨论如何构造插值于各点的函数的问题。主要有 c l o u g h - t o c h e r 插值法【1 3 】、h e r r o n 插值法 1 4 1 、最小模网络法 t s i ( m n n 法) 等。 ( 5 ) 层次b 样条法 近年来，一种基于多层次b 样条曲面插值的散乱数据插值法得到了广泛的应用。 1 9 8 8 年和1 9 9 5 年，f o r s e y 和b a v t e l s 首次提出了层次b 样条的概念【1 6 】并将其应 用于规则网格上的数据逼近【1 7 l 。文【1 8 1 将该方法应用于三维散乱数据点的插值与逼 近。这种方法能提供很好的连续性，并且具有修改方便的优点。该算法使用一个层次 结构的控制点网格，一步一步地从一个较粗糙的网格到一个较精细的网格来提高逼近 的精度，但是它的应用仅限于规则网格。 1 9 9 7 年s e u n g y o n gl e e 【1 9 】等人从图象变形技术出发，提出了散乱数据的多层次 & 样条插值方法。该方法对给定的一组散乱数据，通过求解一个不定方程的伪逆矩阵 来求解一组控制点，通过最小二乘法来最终得到控制网格，它也是全局细化的过程。 国内在这一方面也开展了一些卓有成效的工作。张伟强【2 0 】在上述工作的基础上， 对层次化的过程作了限制，用一种自适应算法自动对某些需要细化的区域进行细化， 提高了计算效率。 - 5 - 基于拟插值的b 样条曲面拟合方法 2 b 一样条曲线曲面简介 多项式插值具有形式简单、计算方便、光滑性好等特点，借助于多项式来逼近， 虽然有很多优点，但由于多项式乃幂级数的特例，其在一点附近的性质足以决定它的 整体性质f 2 1 】。另一方面，在多项式插值理论中，具有佗个插值节点的一元多项式是一 个佗一1 次多项式，它可能有n 一3 个拐点，这对于比较平滑的函数来说就不那么理想 了。当插值多项式的次数逐步增高时，常有数值不稳定的现象( r u n g e 现象) 。因此， 在用多项式插值时不宜选取高次多项式，常用分段多项式或分段函数。本文使用的样 条( 函数) 就是一种分段多项式，各相邻段上的多项式之间又具有某种连接性质。因而 它既保持了多项式的简单性和逼近的可行性，又在各段之间保持了相对独立的局部性 质。样条函数方法是散乱数据拟合的一种有效的逼近方法，本章简单介绍样条函数方 法中的一种重要的方法一b 样条方法，它具有很强的局部修改性质。 本章内容主要来自参考文献【2 2 】。 2 1 一元b 一样条基函数 b 一样条有不同的定义方式，在应用上较为简便的& 样条定义是由如下递推公式给 出的。 牌l 鳞釜一一毗p 扎仁1 ， im 护( u ) = 五嚣m 护一- ( u ) + 蒜妻詈兰焘m + l 扩1 ( “) ， 1 ， 、 i 规定2 = 0 ( 2 1 ) 式称为d eb o o r c o x 公式，u 称为节点序列或节点向量，地称为节点 ( k n o t ) 。若哟一1 = 嘶+ l = = 吻+ l 一1 吻+ l ，则称吻，+ l ，“一l 为u 的z 重节点。 以下列出b 样条基函数的若干重要性质，它们在刻画b 样条曲线和曲面的几何 特征时很有用。 6 大连理工大学硕士学位论文 性质2 1 【2 2 】局部支集性。每个样条基函数只在局部的区间上非零，在实轴其余 的部分为0 即 m 巾( u ) = 0 ，u 譬h ，牡t 埘1 ) 因此，区间心，+ 舛1 ) 称为批，p ( u ) 的支集。 性质2 2 f 2 2 】在任意给定的心，+ 1 ) 内，最多有p + 1 个p 是非零的，它们分别 是v ：f _ p p ，肌伊 性质2 3 2 2 1 非负性 批，p ( u ) 0 ，对一切i ，p 和让 性质2 4 2 2 】单位分解性。 t p ( 让) = 1 ，让【他，地+ 1 ) j = i - l 性质2 5 【2 2 l 重节点连续阶性质。在每一个节点区间( 呦，呦+ 1 ) 内部，批 p ( u ) 为多 项式函数，因此所有导数存在在一个节点嘶处，廖( u ) 是p 一次连续可微的， 此处哪是该节点的重数。所以增加次数，则增加连续性，而增加节点的重数，则降 低连续性通常，为了保证连续性，肌p ( u ) 的支集内的节点呦( t t ，斜1 ) 的最高重 数为p 性质2 6 【2 2 】均匀b - 样条基函数的平移性质。当节点向量u = 讹) 孥o o 为均匀节 点时，即啦= u o + i h ，同次的b 样条基函数可由其中一个& 样条基函数平移得到， 即m ，p ( u ) = a 岛，p ( u i ) 不妨取吨= i ( i = ，一1 ，0 ，1 ，) ，我们就可以得到均匀3 次b 样条基函数： i t 3 ， u 【0 l ( 4 1 2 u + 1 2 u 2 3 u 3 ) ， t 1 0 ，3 ( u ) = ( 一4 4 + 6 0 u 一2 4 u 2 + 3 u 3 ) ，u 2 l ( 4 一心) 3 ， u 3 【0 ， 其他； m 3 ( ) = 0 ，3 ( u i ) ，i = ，一1 ，0 ，1 ， 关于一元b 样条基函数的其它一些性质，详见参考文1 缺 2 2 】。 一7 基于拟插值的& 样条曲面拟合方法 2 2b 一样条曲线 定义2 2 2 2 】设有n + 1 个空间向量【只) 墨o r 3 ，m p ( 让) 是定义在节点向量 u = 咖，让l ，u n + p - i - 1 ) 地+ l ，i = 0 ，1 ，n + p ) 上的p 次& 样条基函数 p ) ，则称 l r i p ( u ) = 只m 巾( ) ，u 【u p 胁+ 1 】 ( 2 2 ) i = 0 为相应于节点向量u 的p 次非均匀( n o n - u n i f o r m ) 的b 样条曲线，称只为控制顶点， 折线r r 为控制多边形。 因为b 一样条基函数的性质，使得b 样条曲线( 2 2 ) 式具有如下的性质。 性质2 7 2 2 几何不变性并口仿射不变性由b 一样奈基函数的单位分解性质易知 性质2 8 2 2 分段光滑的参数多项式曲线。b 样条曲线( 2 2 ) 在每一节点区间 h ，u i + 1 】上是关于参数让的p 次多项式曲线 t p ( u ) = 马，p ( 让) ，让陬，饥+ - 1 j = i - p 因此b 样条曲线是一条分段多项式曲线，它的次数p ，控制顶点数n + l 和节点数 m + 1 满足关系式 m = n + p + 1 每增加一个控制顶点，相应增加一个节点，从而增加一段曲线 性质2 9 2 2 局部调整性由于b 样条基函数的局部支集性质，每个控制顶点只 只对相应基函数m ，p 的支集 u ，+ p + l 】内的曲线有贡献。换句话说，对只的调整，只 会影响b 样条曲线在心，t t 阱l 】的对应部分这就大大增强了& 样条曲线的灵活性 性质2 1 0 2 2 强凸包性由b 一样条基函数的非负性、单位分解性和局部支集性可 以得到 性质2 1 1 2 2 连续阶性质当某节点u j 的重数为r n j 1 ，则以哟为内点的支 集所对应的p 次b 样条基函数批护在吻的连续阶降低为p 一叻，因此相应的b - 样 条曲线( 2 2 ) 在的连续阶为p 一而整条曲线的连续阶c p r n f l , x 乜p s 嘶s + ， 节点吻的重数叻 - 8 一 大连理工大学硕士学位论文 和低次b 样条相比，高次& 样条曲线的光滑性提高了，但是曲线与特征多边形 的逼近程度较差，而且，由于高次& 样条曲线的局部支集的扩大，局部性的优点就逐 渐减弱了，幂次增加也使得计算量加大了。所以实际工作中，人们只要求所构造的曲 线能满意地逼近足够复杂的外形，保证一定的光滑性，并且希望计算量尽可能小。在 多数情况下，2 次和3 次b 样条曲线就能满足工程的实际需求，因而获得了广泛的应 用【2 3 】。 2 3b 一样条曲面 2 3 1 张量积型b 一样条曲面 为了得到张量积型的二元b 样条基函数，我们需要对矩形区域d = a ，6 】 c ，d 】 进行剖分，并使得a = u o ，b = u m ；c = v 0 ，d = 。则由& 样条基函数的局部支集性 质，对d 有贡献的是如下( 仇+ p ) ( 几+ q ) 个b 样条基函数： 魁 p ( u ) ，口 ) ，i = p ，p + 1 ，仇一1 ，j = - - q ，- - q + 1 ，住一1 事实上，若记d 的矩形剖分为仇n ，则其上满足g p l , q - 1 连续的二元p q 次样条空 间即为s 暑- 1 , 口- 1 ( m n ) ，其中伊_ 1 口_ 1 表示沿u 方向p l 阶连续，沿口方向q 一1 阶连 续。利用光滑余因子协调法 2 4 1 ，容易得到艘p , _ 1 q ，口一1 ( m n ) 的维数为 d i m 1 q 一1 ( ) = ( m + p ) ( n + p ) 为了使这( m + p ) + p ) 个基函数有定义，我们需要将节点扩展为 jt 一p t 正一升l u o u r n u m + p ， 【u 一口u 一口+ 1 v 0 v n + g 定义2 3 1 2 2 】给定( m 十p ) x ( n + q ) 个空间向量只j r 3 ( i = 一p ，一舛1 ，m - 1 ，j = - q ，- q + l ，n - 1 ) ，m ，p ( u ) 和，口( 口) 分别为定义在节点向量u = 乱- p ，t 一p + ”一，+ p ) 和v = 口一g ， - q + l ，+ 口) 上的一元p 次和g 次b 样条基函数，则与其相应的张量 积曲面 m 一1n - - 1 p ( 钍，t ，) = 只j m ，p ( u ) n j ，。( 秒) ，( u ，口) ，u m 】，】 ( 2 3 ) t = 一pf f - - - - = - - q 称为一个p q 次b 样条曲面只j 称为控制点，依次用直线段连接同行同列相邻两 个控制点所得的折线网格称为控制网格 张量积型的b 样条曲面具有一些与& 样条曲线相似的性质。 - 9 基于拟插值的b 样条曲面拟合方法 性质2 1 2 】几何不变性和仿射不变性由张量积型的b 样条基函数的单位分解 性可知 性质2 1 3 2 2 j 分片多项式曲面。b 一样条曲面( 2 3 ) 在每个胞腔心，札件1 】xb ，+ 1 】 上为关于参数u 和 的p q 次多项式曲面 t j p ( u ，口) = r ，z 肌，p ( u ) m ，。( u ) ，( u ，口) 心，地+ - 】鸭，吻+ 】 k = i - pl - - - j - q 因此，b - 样条曲面是一个分片多项式曲面。 性质2 1 4 2 2 边界性质。b 样条曲面的四条边界曲线即为b 一样条曲线，它们的控 制顶点分别由控制网格的相应线性组合而成 性质2 1 5 2 2 强凸包性质。由张量积型的b 一样条基函数的非负性，单位分解性和 局部支集性质，& 样条曲面的每一片多项式曲面分别位于其相应的控制网格的凸包 内。 性质2 1 6 2 2 连续阶性质。由二元b 一样条基函数的连续阶性质，当u 方向的某节 点啦的重数砜1 ，则昏样条曲面( 2 3 ) 在等参线u = 讹上的连续阶为p m i 同 样，当u 方向的某节点的重数叻1 ，则良样条曲面( 2 3 ) 在等参线 = 上的连 续阶为q 一哪 若在式( 2 3 ) 中取p = q = 3 ，我们就得到双3 次b 样条曲面： m - - 1n - - 1 p ( u ，t ，) = 只j m ，3 ( 让) ，3 ( 口) ，( u ，钉) ，】，】 ( 2 4 ) = - - 3j = 一3 当节点向量u 和v 均为均匀节点时，式( 2 4 ) 即为均匀双3 次b 样条曲面。 2 3 2 非张量积型b 一样条曲面 非张量积型的b 样条曲面较为复杂，我们将在第四章第一节作简要介绍。 一1 0 大连理工大学硕士学位论文 3 基于拟插值的层次b 一样条曲面拟合方法 第一章中，我们对散乱数据点的层次b - 样条曲面拟合方法的发展作了简单的介 绍，本章重点介绍一类基于拟插值的层次b 样条曲面拟舍方法。 3 1 层次逼近方法 本节我们介绍文献 1 剀中所采用的层次逼近方法，此算法用来解决重构曲面的光 滑度和逼近精确度选取之间的矛盾，利用一列层次控制阿格 饥 坠。来生成一列对应 的函数 k 。，而，= ：；o 就是我们得到的逼近函数。我们从初始网格得到一个 比较粗糙的逼近函数，通过对这个网格的逐步。加细”来得到更精确的逼近函数。 设0 = ( 。，g ) iosz ：q 晟 ( 3 2 ) t = 1 是，的一个合理的逼近。 我们可以采用如下拟插值形式的逼近函数： ( 3 3 ) 其中九，是依赖于，的一个实数，九是v i a ，6 】上的连续线性泛函。 特别地，我们可以取 竹“ 入，= m 巧) ， ( 3 4 ) j = l 其中， ) 凳l 取位于某局部区间j ( 例如鼠的局部支集) 内的点。 c 南= k ，= w 七j f ( x k j ) 来得到系数。 m 2 5 ，权系数w k = 叫幻) 盟可以通过以下方程组得到： 盈，七= 入知( b t ) = 加j 鼠( z 七j ) ， 其中 。l 1 ，若k = i ； 仉 21 0 ，若忌 即我们可以通过 ( 3 5 ) ( 3 6 ) 若对于任意的i ，此方程组都有解，那么这种逼近方法就是能够再生样条空间s d r 的：否则，我们可以通过最小二乘法求解，这样我们得到的p ，就是，的一个逼近。 总之，我们得到了 口，6 】上连续函数，在鼠，中的一个逼近p ，。这是一种由拟插值方 法派生出的局部样条逼近方法，求得的& 样条系数只依赖于局部数据点的信息。 1 3 一 反n n 汹 = 反q n 汹 i l ，j p 基于拟插值的b 样条曲面拟合方法 以下给出了两个例子，其中样条函数空间均已给定。 例3 1 2 s 对3 次样条函数，即d = 3 时，为了确定系数c k ，我们选择区间 ，= ，t 七+ 4 】，那么 f = s p a n b k 一3 ，b k 一2 ，玩+ 3 ) 数据点 p k ，i ) 蝥，最j = ( x k ，t ，y k ，t ) r 2 的z 一轴坐标位于区间j 内，见图3 2 方程组系数矩阵如下： 巨 z k z 七 图3 2i = ，t k + 4 】 f i g 3 2i = 如，亡七+ 4 】 b k 一3 b k 2 b 知+ 3 z k 2 z 七2 z 七2 b k 一3 b k 2 b k + 3 z k ，m k z k ，m k x k ，r t l k 对张量积型& 样条函数空间，我们考虑如下形式的逼近函数： ( p 似刎) = c t j b , ( x ) b j ( y ) ， ( 3 7 ) b lj = l 其中鼠( z ) 和s j ( y ) 分别是以- r = = 岛) 芍d + 1 和勺= 勺) 葛“1 为节点向量的b 一样条 基函数。 例3 2 2 6 对张量积型的双3 次b 样条函数，为了确定系数，我们选择胞腔 f = 慨，氐+ 4 1xb ，s j + 4 】那么， 鼠，r ，r = s p a n b i 一3 岛_ 3 ，巩3 岛+ 3 ) 数据点 r ，七) 普，七= ( z 吼七，忌，龟七) r 3 的z - 轴、驴轴坐标位于胞腔j = 陬，气+ 4 】x s 1 ，s j + 4 1 内，见图3 3 1 4 大连理工大学硕士学位论文 33 数值实验 f - 目3 3i = o b ，+ “ f i g3 3 = 陬，t 4 k ，+ 4 】 在利用上节的方法来进行曲面拟合时，会产生曲面光滑性与精确度之间选取的矛 盾，也就是说，当剖分比较租糙时，即网格间距很大时，生成的拟合曲面会比较平 滑但是拟合精度差反之当剖分很细时，叩网格间距很小时，生成的拟合曲面光 顺性比较差容易产生平点、尖点和谷点，但是精度高。在文献 2 6 1 中，给出了一类 层次b - 样条曲面拟台方法，该方法解决了曲面光滑性与精度选取之间的矛盾。该算法 利用层次b 样条逼近算法每层都采用上节所述的方法来生成一个双3 次的b 样条 函数，最后得到的这些函数的和叩为我们所求的逼近函数。此算法是一种局部逼近方 法，目标函数的每个b 样条基函数的系数都由对应b - 样条基函数局部支集内部的点 通过计算得到，所以运算速度比较快。 、lj 唧 蜥 蜥 一 一 + 冯冯 冯 m m n q 一 一 + 最臣 巩 蛳蜥 蜥 一 一 + 岛马马 q q 一 一 + 阵且鼠 鼠 矩， 数 糸 程、万 基于拟插值的b 样条曲面拟合方法 以下是该方法的一些数值实验结果1 2 6 】。 对给定的测试函数g ( x ，箩) ，对这个函数进行采样得到数据点集p ，然后利用上述 曲面重构方法得到逼近函数，( z ，y ) 。误差用，与g 在一个均匀网格上函数值的标准 r m s 误差( n o r m a l i z e dr o o tl l l e a l ls q u a r ee r r o r ) ，即r m s 误差除以g 在测试区域上最 大值与最小值的差来表示。 r m s = mn ( 9 ( 协) 一m t ，协) ) 2 兰! ! 三! ( m + 1 ) ( + 1 ) 其中x i = i m ，协= j n ，m = n = 5 0 。 测试函数为： “刎) _ o 7 5 唧 一堕型# 型】+ 0 7 5 唧 一与竽一等】 + 0 5e x p 一丝型盟型卜0 2 唧卜( 9 x - - 4 ) 2 一( 9 一1 ) 2 】， 9 2 ( x ，可) = ( t a n h ( 9 9 z 一9 翟) + 1 ) 9 ， 夕3 ，y ) = ( 1 2 5 + c o s ( 5 4 y ) ) ( 6 + 6 ( 3 x 一1 ) 2 ) ， 夕4 ，y ) = ( p 一莩( ( z o 5 ) 2 + ( y o 5 ) 2 ) 3 ， 夕5 ( z ，y ) = 6 4 8 1 ( ( z o 5 ) 2 + ( y o 5 ) 2 ) 9 一o 5 ， 测试区域为q = ( z ，秒) f0 z 1 ，0 y 1 ) 。 对每个测试函数，用三种点集来进行实验：m 1 0 0 、m 5 0 0 与r 5 0 0 。其中点集 m 1 0 0 是在区域q 上均匀选取的7x7 个点与随机选取的5 1 个点，m 5 0 0 是均匀选取 的1 5 1 5 个点与随机选取的2 7 5 个点，r 5 0 0 是完全随机选取的5 0 0 个点。 图3 4 为实验选取的5 个测试函数。 表3 1 为前几层的标准r m s 误差，在初始层选用的是7x7 的控制点。 - 1 6 大连理工大学硕士学位论文 图3 4 测试函数 f 培3 4t e s th m c t i o n s 表31 测试函数与逼近函数间的标准r m s 误差 t a b l e31n o r m a l i z e dr m se o 砧b e t w e e nt e s tf u n c t i o n sa n dt h e i ra p p r o x i m a t i o n s m 1 0 0 g l啦弧甄驰 1 丽磊广_ 石丽丽丽丽f 1 砸西丽面r 20 1 1 7 40 3 3 4 50 0 5 1 50 0 8 3 00 0 0 2 4 80 0 9 0 20 2 8 0 00 0 “7 0 0 5 4 00 0 0 2 2 m s 0 0 g l啦缸9 4弧 1 面丽丁砸丽f _ i 而面r _ 石丽丽面百矿 20 0 4 1 60 0 7 7 60 0 0 4 50 0 1 4 80 0 0 0 2 30 0 0 4 70 0 1 1 50 0 0 1 70 0 0 2 40 0 0 0 2 r s 0 0 9 1卯 9 3 f 4g s 1 0 1 8 2 80 3 0 9 8 0 0 6 2 70 0 1 8 90 0 0 2 1 20 0 6 8 90 1 3 6 70 0 0 7 90 0 1 6 60 0 0 0 6 30 0 2 4 4 0 0 8 0 10 0 0 3 40 0 0 5 30 0 0 0 5 图3 5 为9 1 在初始层的逼近曲面和误差曲面及第二层的逼近曲面，图中的黑色点 表示采样点。 1 7 基于拟插值的b 样条眭面拟合方法 藏 ( a ) n 在初始层的通近曲面 ( b ) 韧始层误差曲面，1 4 = a 一o ( x , * c c l 第二层的逼近曲面 图3 59 1 的逼近结果 f i g3 5a p p r o x l m a t i o nr 皤1 l l 拈o f 9 l 由此可见，逼近效果较好，而且当采样点选取的越多、分布越均匀时，算法的拟 合效果越好。 一1 8 大连理工大学硕士学位论文 4 一类基于拟插值的层次非张量积型b 一样条曲面拟合方法 虽然张量积形式的b 一样条方法在曲面造型中获得了很大的成功，但是它也存在一 些不足【2 7 】。其一，由于基函数是一元b 样条基的张量积，使得其参数域只能是矩形 区域，对于非规则的参数域，只能由矩形域上的& 样条曲面经过裁剪和拼接得到。其 二，张量积的基函数使得曲面的次数升高，代数次数较高的曲面使得与之相关的运算 变得复杂，甚至影响曲面的几何性质，例如出现多余的拐点等。为了解决这个问题， 我们采用具有局部支集的二元2 次b 样条基函数通过上一章所述的拟插值方法构造非 张量积型的b 一样条曲面，再利用层次逼近方法对散乱数据点集进行曲面拟合。 4 12 一型三角剖分上的多元样条函数 样条函数就是具有一定光滑性的分段或分片定义的多项式函数。1 9 4 6 年，数学 家i j s c h o e n b e r g _ 【2 s 较为系统的建立了一元样条函数的理论基础。2 0 世纪6 0 年代至 7 0 年代初，g b i r k h o f f ，h l g a r a b e d i a n 和c a r ld eb o o r 等研究并建立了一系列关 于c a r t e s i a n 乘积型的多元样条理论。1 9 7 5 年，王仁宏采用函数论与代数几何的方法 【2 4 l ，建立了任意剖分下多元样条函数的基本理论框架，提出了光滑余因子协调法，从 这种基本观点出发，多元样条函数的任