（计算机应用技术专业论文）三角形域上超限插值曲面的研究.pdf

原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：h 期：墨! 呈：坐茎 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 埤 毒 山东大学硕士学位论文 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 课题研究背景和意义1 1 2 研究现状及本文贡献2 1 3 章节安排3 第2 章三边曲面片概述5 1 1 插值与逼近5 1 1 1 多项式插值5 1 1 2 最小二乘逼近7 1 2 三边曲面片9 2 。3 1 重心坐标9 2 3 2 三边b 6 z i e r 曲面片1 1 第3 章三角形域上的超限插值方法1 5 3 1 三次精度插值方法1 5 3 1 1 点一边插值方法1 5 3 1 2 边一边插值方法1 6 3 1 3 移动三角插值方法1 8 3 2 四次精度插值方法1 9 3 2 1 四次多项式插值方法1 9 3 2 2 四算子插值方法2 2 3 2 3 四算子插值方法的改进2 4 3 3 五次精度插值2 4 3 2 3 布尔和插值方法2 5 3 2 3 基本曲面加附加曲面方法2 6 第4 章构造c 1 连续的六次三边曲面片2 8 山东大学硕士学位论文 4 1c 1 连续三边曲面片2 8 4 2 逼近算子2 9 4 - 2 1 求解2 4 个未知系数- 3 1 4 2 2 求解a 2 2 。3 2 4 3 插值算子3 5 4 4c 1 连续性3 6 4 5 实验3 9 4 6 结j 沧4 2 第5 章总结及展望4 4 参考文献4 5 致谢4 9 攻读学位期间发表的学术论文目录5 0 攻读学位期间参与的项目5 1 山东大学硕士学位论文 t a b l eo fc o n te n t s 簟a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h 。 c h a p t e r1i n t r o d u c t i o n 1 1 1r e s e a r c hb a c k g r o u n d 1 1 2c u r r e n tr e s e a r c ha n dc o n t r i b u t i o n s 2 1 3a r r a n g e m e n ta n ds t r u c t u r e 3 c h a p t e r2i n t r o d u c t i o no f t r i a n g u l a rp a t c h 5 1 1i n t e r p o l a t i o na n da p p r o x i m a t i o n 5 1 1 1p o l y n o m i a li n t e r p o l a t i o n 5 1 1 2l e a s ts q u a r em e t h o d 。7 1 2t r i a n g u l a rp a t c h 9 2 3 1b a r y c e n t r i cc o o r d i n a t e s 。9 2 3 2t r i a n g u l a rb d z i e rs u r f a c e 11 l c h a p t e r3 i n f i n i t ei n t e r p o l a t i o no nt r i a n g l e 1 5 3 1i n t e r p o l a t i o nm e t h o do f d e g r e et h r e e 15 3 1 1v e r t e x s i d em e t h o d 1 5 3 1 2s i d e s i d em e t h o d 1 6 3 1 3m o b i l et r i a n g l em e t h o d 1 8 3 2i n t e r p o l a t i o nm e t h o do f d e g r e ef o u r 1 9 3 2 1p o l y n o m i a lo f d e g r e ef o u rm e 吐l o d 1 9 3 2 2f o u r - o p e r a t o rm e t h o d 2 2 3 2 3i m p r o v e df o u r - o p e r a t o rm e t h o d 2 4 3 3i n t e r p o l a t i o nm e t h o do f d e g r e ef i v e 一2 4 3 2 3b o o l e a ns u mm e t h o d 2 5 3 2 3b a s i ca n da d d i t i o n a lp a t c h e sm e t h o d 2 6 c h a p t e r4c o n s t r u c t i n gc 1t r i a n g u l a rp a t c ho f d e g r e es i x 2 8 4 1c 1t r i a n g u l a rp a t c h 2 8 山东大学硕十学位论文 4 2a p p r o x i m a t i o no p e r a t o r 2 9 4 2 1d e t e r m i n i n g2 4u n k n o w n s 31 4 2 2d e t e r m i n i n ga 2 2 2 一3 2 4 3i n t e r p o l a t i o no p e r a t o r 3 5 4 4c 1c o n t i n u i t y 3 6 4 5e x p e r i m e n t s 3 9 4 6c o n c l u s i o n s z i ：2 ： c h a p t e r5s u m m a r ya n dp r o s p e c t 4 4 r e f e r e n c e s 4 5 t h a n k s z 1 9 r e l a t e d p a p e r s 5 0 r e l a t e dp r o j e c t s 5 1 一 ， 山东大学硕士学位论文 摘要 在c a g d ( c o m p u t e ra i d e dg e o m e t r yd e s i g n ) ，c g ( c o m p u t e rg r a p h i c s ) 领域 中，如何构造精确度高并且具有一定光顺性的曲面是一个重要问题。 由于工程曲面的不规则性和复杂性，以及散乱数据点没有明确的分布规律， 很难用单一的数学模型表达复杂的曲面，因此一般采用分片的方法设计曲面。先 将曲面的定义域进行细分，在每个子定义域内构造曲面片，最后将各个曲面片光 滑的连接起来，形成一个完整的曲面。目前最常用的曲面片是三边曲面片和四边 曲面片。由于三角插值方法方便灵活，并且几何意义明显，便于调整，已经成为 一种重要的曲面造型方法，得到了广泛的应用。三角域上的插值包括有理插值和 多项式插值两种方法，其中多项式插值因为结构简单，易于计算的优点，应用尤 为广泛。 在曲面造型过程中，如何构造一张曲面，光滑地连接三张曲面，从而形成整 体曲面是经常遇到的一个问题。由于所连接的曲面可以是任意曲面，因此所要构 造的曲面的边界是任意形式的曲线。这种对任意边界条件的插值称为超限插值。 要保证整张曲面的光滑性，相邻的曲面片之间除了边界上有相同的函数值外，还 应当有相同的一阶跨界导数。所以，在三角形域上构造插值给定的边界曲线和一 阶跨界导数的曲面，是c a g d 和c g 领域的一个基本问题。 本文提出了一个由逼近算子和插值算子的布尔和构造六次c 1 连续三角曲面 片的新方法，构造的三角曲面片满足给定的边界曲线和一阶跨界导数。其中，逼 近算子使三角曲面片逼近给定的边界条件，插值算子利用点边插值方法【2 0 】使三 角曲面片插值给定边界条件。由于三角曲面片的精度主要由逼近算子决定，所以 提高逼近算子的逼近精度对于三角曲面片的构造非常重要。若给定的插值条件位 于边界上，现有的方法仅仅考虑了边界上的插值精度，其最大误差一般出现在三 角形的内部，特别是三角形的中心区域。新的方法用一个六次多项式构造逼近算 子，除了在边界上能更好地逼近给定的插值条件，还能提供一个自由度使逼近算 子在三角形内部，特别是误差较大区域有较好的形状。 实验表明，新方法构造的c 1 连续三角曲面片在三角形内部和边界上都具有 山东大学硕士学位论文 更好的准确度和光顺性。在三角曲面片构造过程中，插值算子对三角曲面片的质 量也起到了不可忽视的作用。如何提高插值算子的插值精度，构造更准确更光顺 的三角曲面片，是未来研究工作的重点。 。 关键词：三角曲面片；边界曲线；跨界导数；超限插值 i i ， ， 山东大学硕士学位论文 a b s t r a c t i nt h ef i e l do fc a g d ( c o m p u t e ra i d e dg e o m e t r yd e s i g n ) a n dc g ( c o m p u t e r g r a p h i c s ) ，h o wt oc o n s t r u c ts u r f a c eo fh i g hp r e c i s i o na n ds m o o t h n e s si s a l li m p o r t a n t p r o b l e m b e c a u s et h es u r f a c ef o re n g i n e e r i n gi n d u s t r yi si r r e g u l a ra n dt h es c a t t e r e dd a t a d o e sn o th a v er e g u l a r i t ya n do r d e r , i ti sh a r df o ru st oe x p r e s ss u r f a c eu s i n go n l yo n e m a t h e m a t i ce x p r e s s i o n h e n c e ，d e s i g n i n gt h es u r f a c ep i e c e w i s ei su s u a l l ya d o p t e d f i n a l l y , t h ep a t c h e sw i l lb ec o m b i n e dt of o r maw h o l es u r f a c e a tp r e s e n t ，q u a d r a n g l e p a t c h e sa n dt r i a n g u l a rp a t c h e s a r et h eo n e su s e dw i d e l y b e c a u s et r i a n g u l a r i n t e r p o l a t i o nm e t h o dh a so b v i o u sg e o m e t r i cm e a n i n ga n d i se a s yt oa d j u s t ，i tb e c o m e s a ni m p o r t a n tm e t h o do fc o n s t r u c t i n gs u r f a c e o n eo ft h ec o m m o n e s tm e t h o d so f c o n s t r u c t i n gi n t e r p o l a t i o ns u r f a c ei st ot r i a n g u l a t et h eg i v e ns c a t t e rd a t ap o i n t s ，a n d t h e nc o n s t r u c tt r i a n g u l a rp a t c ho ne a c ht r i a n g u l a rd o m a i n ，a n df i n a l l yc o m b i n ea l lt h e p a t c h e st ob u i l dt h ew h o l es u r f a c e t h ei n t e r p o l a t i o nm e t h o d so nt r i a n g l ei n c l u d e r a t i o n a li n t e r p o l a t i o nm e t h o da n dp o l y n o m i a li n t e r p o l a t i o nm e t h o d t h ep o l y n o m i a l i n t e r p o l a t i o nm e t h o di su s e dw i d e l yi nt h ea p p l i c a t i o n s i nt h ep r o c e s so fs h a p em o d e l i n g ，i ti sac o m m o na n di m p o r t a n tp r o b l e mt h a ta s u r f a c ei sc o n s t r u c t e dt oc o n n e c to t h e rt h r e es u r f a c e ss m o o t h l y b e c a m et h e t h r e e s u r f a c e sm a yb et h eo n e so fa r b i t r a r yf o r m ；h e n c e ，t h es u r f a c ew h i c hi su s e dt o c o n n e c tt h eo t h e rt h r e eo n e si sc o n s t r u c t e dw i mt h eb o u n d a r yo fa r b i t r a r yf o r m t h e i n t e r p o l a t i o nt oa r b i t r a r yb o u n d a r yc o n d i t i o n si sc a l l e di n f i n i t ei n t e r p o l a t i o n i no r d e r t og e tt h es m o o t h n e s so ft h ew h o l es u r f a c e ，t h ea d ja c e n tp a t c h e ss h o u l dh a v et h es a m e f u n c t i o nv a l u e sa n dc r o s s b o t m d a r y s l o p e so nt h eb o u n d a r y s o ，c o n s t r u c t i n g t r i a n g u l a rp a t c hw h i c hi n t e r p o l a t e st h eg i v e nb o u n d a r yc u r v e sa n dc r o s s b o u n d a r y s l o p e so nat r i a n g l ei st h eb a s i cp r o b l e mi nc o m p u t e ra i d e dg e o m e t r yd e s i g na n d c o m p u t e rg r a p h i c s an e wm e t h o do fc o n s t r u c t i n g t r i a n g u l a rp a t c ho fd e g r e es i xb yt h eb o o l e a n i i i 山东大学硕士学位论文 s u mo fa l la p p r o x i m a t i o no p e r a t o ra n da ni n t e r p o l a t i o no p e r a t o ri sp r e s e n t e di n t h i s p a p e r t h et r i a n g u l a rp a t c hs a t i s f i e st h eg i v e nb o u n d a r yc u r v e sa n dc r o s s - b o u n d a r y s l o p e s t h ea p p r o x i m a t i o no p e r a t o rm a k e st h et r i a n g u l a rp a t c ha p p r o x i m a t et h eg i v e n b o u n d a r yc o n d i t i o n s ，w h i l e t h e i n t e r p o l a t i o n o n em a k e st h e t r i a n g u l a rp a t c h i n t e r p o l a t et h et r i a n g u l a rp a t c hu s i n gt h ev e r t e x s i d em e t h o d 【2 们s i n c et h ep r e c i s i o n o ft r i a n g u l a rp a t c hi sm a i n l yd e p e n d e n to nt h ea p p r o x i m a t i o no p e r a t o r , i n c r e a s i n gt h e p r e c i s i o no ft h ea p p r o x i m a t i o no p e r a t o ri sv e r yc r u c i a lf o rb u i l d i n gat r i a n g u l a rp a t c h 、 ，i mb e t t e rp r e c i s i o n t h ee x i s t i n gm e t h o d sm e r e l ym a k eu s eo ft h eg i v e nb o u n d a r y c o n d i t i o n sd i r e c t l y , a n dt h e i rm a x i m u me r r o ri su s u a l l yg e n e r a t e di nt h ei n t e r i o ro ft h e t r i a n g l e ，e s p e c i a l l ya ta n dn e a rt h ec e n t e ro ft h et r i a n g l e t h en e wm e t h o dc o n s t r u c t s t h e a p p r o x i m a t i o no p e r a t o r a sap o l y n o m i a lo fd e g r e es i x ，w h i c hn o t o n l y a p p r o x i m a t e st h eg i v e ni n t e r p o l a t i o nc o n d i t i o n so nt h eb o u n d a r yw i t hab e t t e r p r e c i s i o n ，b u ta l s oh a sab e t t e rs h a p ei nt h ei n t e r i o ro ft h et r i a n g l e ，e s p e c i a l l yi nt h e c e n t r a la r e ao fb i ge r r o r i ti ss h o w nt h a tt h e t r i a n g u l a rp a t c hc o n s t r u c t e du s i n gt h en e wm e t h o dh a s b e t t e rp r e c i s i o na n ds m o o t h n e s s i nt h ec o n s t r u c t i o no ft r i a n g u l a rp a t c h ，i n t e r p o l a t i o n o p e r a t o re x e r t sag r e a ta f f e c to nt h eq u a l i t yo ft h et r i a n g u l a rp a t c h s o ，h o wt oi n c r e a s e t h ei n t e r p o l a t i o np r e c i s i o no ft h ei n t e r p o l a t i o no p e r a t o rt ob u i l dt r i a n g u l a rp a t c ho f b e t t e rp r e c i s i o na n ds m o o t h n e s si st h ek e yp o i n tf o rt h ef u t u r er e s e a r c hw o r k k e yw o r d s ：t r i a n g u l a rp a t c h ；b o u n d a r yc u r v e s ；c r o s s b o u n d a r ys l o p e s ；i n f i n i t e i n t e r p o l a t i o n 一 山东大学硕士学位论文 1 1 课题研究背景和意义 第1 章绪论 在c a g d ( c o m p u t e ra i d e dg e o m e t r yd e s i g n ) ，c g ( c o m p u t e rg r a p h i c s ) 和自 由曲面造型中，三角曲面片的构造占有重要的地位。特别是近几年，如何根据海 量散乱数据点( 如点云数据) 进行曲面重建b - s 引起的广大学者和工程设计人员 的广泛关注和极大兴趣。其中，如何构造更准确更光顺的三角曲面片是曲面造型 的关键问题。而且，随着三维扫描获取技术的快速发展，三维数字几何模型已经 成为一种新兴的数字媒体，在多个领域取得了广泛的应用。数字几何处理，也成 为近年来计算机图形学研究的热点问题。三角曲面片的构造也在这一新兴热点领 域中扮演着重要的角色【6 】。 在实际工程应用中，设计人员往往需要根据给定的散乱数据点设计出复杂性 较高的曲面。如果仅仅使用一个数学函数，难以表达结构复杂的曲面。因此，一 般先构造出三边或四边曲面片，再将这些曲面片光滑地拼接起来，使之满足一定 的连续性要求，最终构造出满足要求的完整曲面。 光滑拼接四边形曲面片构造完整曲面时，一般采用b 样条曲面或n u r b s 曲 面等定义在矩形参数域上的张量积曲面。对于四边形曲面片的构造，已经有比较 成熟的研究成果，也已经在工业设计中得到了广泛的应用。但是，使用四边形曲 面片分片构造插值曲面对给定造型数据的拓扑关系有较为严格的要求。然而散乱 数据点通常并没有明确的分布规律和严格的拓扑关系，所以很难利用四边形曲面 片的光滑拼接来进行曲面建模。相对四边形曲面片，三角插值方法具有较为明显 的几何意义，而且便于调整，能够适应散乱数据点几何造型的需要，因此三角域 上插值曲面的构造逐渐受到更多的重视。 在插值曲面的构造过程中，如何光滑地连接三张曲面，从而形成整体光滑的 曲面是一个经常遇到的问题。由于所连接的曲面可以是任意曲面，因此所要构造 的曲面的边界是任意形式的曲线。这种对任意边界条件的插值称为超限插值。一 种插值方法被称为具有n 次多项式的插值精度，如果给定的插值条件取自一张刀 山东大学硕士学位论文 次多项式曲面，插值方法构造的插值曲面就是该刀次多项式曲面。 三角域上的插值方法分为多项式插值和有理插值两种方法。多项式插值的结 构较为简单，可以方便地用于函数计算和微分积分，所以此类方法具有十分重要 的应用价值。有理插值也称为非线性插值。它的理论研究和数值计算相对于多项 式插值要困难一些，其结构也比较复杂。某些情况下，在三角域上的多项式插值 是可以确定的，但是有理插值却未必存在。在本文中，主要对多项式插值方法进 行了研究。 1 2 研究现状及本文贡献 1 9 6 4 年，美国工程师c o o n s 提出了在矩形域上由边界曲线构造插值三角曲 面片的方法，称为c o o n s 曲面方法。该方法和b e z i e r 曲线曲面方法一起为c a g d 和c g 的形成和发展奠定了坚实的基础。b a m h i l l 等【j 7 】将四边形域上的c o o n s 插 值方法推广到三角形域上，提出了采用布尔和算子在三角形域上根据边界曲线构 造插值三角曲面片的方法，但是该方法中给定的插值条件必须满足相容性要求。 文献 8 ，9 】中提出，如果给定的边界条件不满足相容性要求，则需要在所构造的 三角曲面片上加上一个修正项，以去掉不相容性。文献 1 0 ，1 1 1 提出了采用凸组 合方法在三角形域上构造三角曲面片的方法。文献 1 2 ，1 3 1 推广了【1 0 ，1 1 】的思 想，提出了构造四边形曲面和五边形曲面的方法。文献 1 4 。1 6 给出了构造五边形 曲面的方法。文献 1 7 1 9 1 提出了, 边形曲面的构造方法。n i e l s o n 提出了点边插 值方法【2 0 1 ，该方法使用3 个插值算子的组合构造三角曲面片，其中每个算子满 足一个点及其对边上的插值条件。h a g e n 2 1 1 推广了n i e l s o n 方法2 0 l ，提出了构造 几何三角曲面片的方法。文献 2 2 ，2 3 1 将 2 0 ，2 1 1 提出的方法一般化为构造一阶 或二阶几何连续的三角曲面片的方法。在文献 2 4 1 0 0 ，三角形被细分为两个子三 角形，然后在两个子三角形域上分别构造两张在公共边界上c 1 连续的曲面片， 进而构造完整的三角曲面片，该方法具有四次多项式的插值精度。文献 2 5 3 1 】 首先插值三角形顶点处的插值条件构造边界曲线，然后对边界曲线进行插值，构 造三角曲面片。文献 3 2 】提出了移动三角形的插值方法，尽可能地利用最近的插 值条件来拟合未知点处的函数值。文献 3 3 1 提出用一个四次多项式插值给定的边 2 严 山东大学硕士学位论文 界曲线和一阶跨界导数，构造具有四次多项式插值精度的三角曲面片。文献 3 4 】 提出了一种在给定三角网格模型上构造g 1 连续的参数三角曲面片的方法。文献 【3 5 】利用三个点一边算子【2 0 1 和一个内部插值算子构造三角曲面片，该方法具有四 次多项式的插值精度。文献 3 6 1 改进了文献 3 5 1 0 0 的方法，用四次插值曲线代替 n i e l s o n 算子幽1 ，从而提高了曲面的准确度和光滑度。在3 t r l 3 7 1 0 0 ，三角曲面片 由基本曲面加上误差曲面构成，其形状主要由基本曲面决定。但是由于五次基本 曲面没有足够自由度，因此它在三角域上，特别是三角形域的内部，精度不高， 所以构造的三角曲面片的形状仍然不理想。徐琳等3 8 1 对现有的超限插值方法进 行了综述和比较，并给出了实例。文献 3 9 1 重新定义了边界插值条件，提出了构 造参数三角曲面片的方法。 在本文中，提出了一个构造c 1 连续三角曲面片的新方法。三角曲面片由逼 近算子和插值算子的布尔和构成。其中，逼近算子使三角曲面片逼近给定的边界 条件，插值算子利用点边插值方法【2 0 1 使三角曲面片插值给定边界条件。由于三 角曲面片的精度主要由逼近算子决定，所以本文通过提高逼近算子的逼近精度， 构造具有更高精度的三角曲面片，使分片构造的完整曲面更准确更光顺。如果给 定的边界条件定义在三角形域的边界上，那么现有方法的最大误差一般出现在三 角域的内部，特别是其中心区域。已有方法只是直接插值给定的边界条件，没有 考虑到三角域内部的逼近精度。新的方法不但充分利用了给定的边界条件，还考 虑了三角形内部的逼近精度，使三角曲面片在三角域内部具有较好的形状。逼近 算子表示为一个六次多项式，不但在边界上有更好的逼近精度，还可以提供一个 额外的自由度来提高三角曲面片在误差较大的区域的逼近精度。这样，所构造三 角曲面片在三角形域的边界和内部，都具有较好的形状。 1 3 章节安排 本文主要分为五个部分，各章内容安排如下： 第一章为引言，对论文的意义以及论文整体的安排进行了介绍。 第二章给出了三角曲面片的相关概念和技术。例如常用的拟合算法，重心坐 标等。还介绍了三边b 6 z i e r 曲面片的相关概念和构造过程。 山东大学硕士学位论文 第三章主要介绍了已有的几种超限插值方法。第一节介绍了三种三次精度插 值方法，分别是点边插值方法【2 0 1 ，边边插值方法和移动三角形插值方法吲。 第二节介绍了三种四次精度插值方法，分别是四次多项式插值方法p 4 ，四算子 插值方法【3 5 1 以及四算子插值改进方法【3 6 1 。第三节介绍了两种五次精度插值方法， 分别为布尔和插值方法【刀，基本曲面加附加曲面方法【3 r l 。 第四章主要介绍一种利用逼近算子和插值算子的布尔和构造c 1 连续的六次 三角曲面片的新方法。第一节介绍了c 1 连续的三角曲面片的基本概念；第二节 介绍了六次逼近算子的构造；第三节介绍了插值算子的构造过程；第四节给出三 角曲面片c 1 连续性的证明；第五节对新方法与四算子插值方法3 5 1 以及基本曲面 加附加曲面方法【3 7 1 进行了比较；第六节给出了新方法的综合评价。 第五章给出了相关结论，对上述插值方法给出了总体评价，展望了以后的工 作方向。 4 一 严 山东大学硕士学位论文 第2 章三边曲面片概述 本章我们将介绍一些曲面造型方面的基本概念以及思路和研究方法。 1 1 插值与逼近 科学和工程问题可以通过诸如采样、实验等方法获得若干离散数据。我们往 往希望构造一个与这些离散数据相吻合的连续的数学函数( 曲线或者曲面) 。这 个过程称为拟合。 给定一组离散数据点 只) ：。，我们构造一条曲线c 顺序通过这些点，即 c ( 见) = 0 ，i = o ，1 ，2 ，门，则称为对数据点进行插值，称曲线c 为插值曲线，构 造插值曲线所采用的数学方法称为曲线插值法。如果给定的离散数据点本身就比 较粗糙，那么构造严格通过这些数据点的曲线就没有什么实际意义。在这种情况 下，更为合理的提法应该构造曲线c ，使之在某种意义下最为接近数据点 见 ：。， 即l c ( 只) 一忍l 万( 万为允许误差) 。这个过程称为对这些数据点进行逼近，所构 造的曲线c 称为逼近曲线，构造逼近曲线所采用的数学方法称之为曲线逼近法。 很明显，当万= 0 时，对给定数据点的逼近问题就转化为插值问题，逼近曲线c 7 也就变成为插值曲线c 。 同理，根据散乱数据点 只) ：。构造曲面时也存在插值和逼近的问题。在实际 应用中，我们应该根据给定数据点的准确程度选用合适的方法。如果数据点比较 准确，则用插值法比较好，因为插值算法本身比较稳定可靠。如果数据点本身比 较粗糙或者带有一定的误差，则逼近法更为合适。 插值和逼近统称为拟合，在曲面造型技术中有着广泛的应用。在本节中，将 以曲线为例，介绍常用的拟合方法。这些方法也可以简单地推广到曲面构造上。 1 1 1 多项式插值 在c a g d 中，一般采用基表示的参数矢函数形式。由于多项式函数表示形 山东大学硕士学位论文 式简单，又无穷次可微，因而足够光滑，且容易计算函数值以及各阶导数值，因 此应用中多采用多项式函数作为基函数，即多项式基。多项式插值，就是用多项 式对一组给定数据进行插值的过程。换句话说就是，对于一组给定的数据点( 如 来自于采样数据) ，寻找一个恰好通过这些数据点的多项式。 ，z 次多项式的全体构成”次多项式空间。力次多项式空间中任一组刀+ 1 个线 一 性无关的多项式都可以作为一组基，因此有无穷多组基。不同组基之间可以通过 一个线性变换相互转换。 幂基t ( j = 0 ，1 ，刀) 是最简单的多项式基。相应的参数多项式曲线方程为 p = 哆7 j = 0 其中a j = ( ，y j ，z j ) 为系数矢量，f 是参数。 高次的插值多项式很容易在数据点之间出现震荡，即曲线会出现过多的扭 摆。同时，高次曲线的计算过程要更加复杂，代价也更高。由于高次多项式插值 曲线的构造有许多缺点，所以在实际应用中很难得到推广。而单一的低次多项式 曲线又难以用来描述形状复杂的曲线。因此，比较合理的选择是分段构造低次多 项式曲线，再将这些低次曲线逐段拼接起来，并使其满足一定的连续性要求。这 样以分段方式定义的曲线称为组合曲线。设计人员不希望一条组合曲线包含太多 段，而且又并非次数越低越好。因为参数三次曲线是既可以用来生成带有拐点的 平面曲线，又可以在空间内构造次数最低的参数多项式曲线，所以在三次是一个 很好的折中，大多数形状设计与表示都是用三次参数化来实现的。 在某些情况下，不但要求构造的曲线在节点上函数值相等，而且还要求它的 导数值也相等( 即要求在节点上具有一阶光滑度) ，甚至要求其高阶导数也相等， 满足这种要求的插值多项式就是埃尔米特( h e r m i t e ) 插值多项式。给定两个数 据点e o 和e , ，及其相应的参数t o 和t 1 。对圪，置及其直到k 阶导矢磅7 ) 和暑”， ，= 1 ，2 ，k ，进行埃尔米特插值，构造的曲线定义如下： 其中，h “( f ) 满足 七七 p ( f ) = 碍力h r ，。( f ) + h ( f ) 山东大学石贝士学位论文 嘲伊悟；舅或f t _ 二： 在实际应用中，经常需要构造的曲线在数据点处至少满足其一阶导数。因此， 对r ，置及其一阶导数砖1 ) 和置1 ) 进行插值，构造三次h e r m i t e 曲线，得到 尸( f ) = 碍h o ，oo ) + 碍1 骂。o ( ，) + 墨们h o ，1p ) + # n - 1 ，lo ) 其中， n o , o 咿搿一等扎哪卜搿+ 等 啪，= 器一等伽= 器+ 警伽 称为三次埃尔米特某函数，并日满枣 凰，。( 乇) = 1 ，日器( 岛) = h o ，。( ) = 磁d 州( t ) = 0 日船( 岛) = 1 ，q ，。( 岛) = 日。，。( 矗) _ h 。o ) t 、t 。，= 0 风，。( ) = l ，日0 l ( 岛) = 磁1 7 ( 岛) = 磁? ( ) = 0 匝：( ) = 1 ，q ，( 岛) = 础( ) = q ，( ) = o 若参数f 是定义在【o ，1 】上的，则三次埃尔米特基函数可定义为： 风o ( ，) = 2 t 3 - 3 t 2 + 1 ， h o 1 ( f ) = 3 t 2 2 t 3 ， 1 1 2 最