（计算机应用技术专业论文）曲面造型中散乱数据插值曲面问题的研究.pdf

山东大学硕士学位论文 摘要 本文对曲面造型中散乱数据插值曲面问题进行了研究。构造散乱空间数据插 值曲面技术在c a d 、计算机图形学、气象和勘探等各类科学研究和工程设计中 有广泛的应用。 由于工程曲面的不规则性，以及散乱数据的无明确规律和无序性，很难用单 一的数学形式把曲面表达出来，因此一般采用分片的方法设计曲面，最后将各曲 面片光滑的连接起来，形成一个完整的曲面。目前最常用的曲面片是三边曲面片 l l k - 和四边曲面片p , 4 1 。由于三角插值方法的几何意义明显，便于调整，成为重要 的曲面构造方法。构造插值曲面的常用方法之一就是对给定的散乱数据进行三角 剖分，根据边界连续条件构造每个三角形区域上的插值曲面片，整体的插值曲面 由各个曲面片拼合而成。三角域上的插值包括有理插值f 5 】和多项式插值睁1 川两种 方法，其中多项式插值因为其结梅简单，易于计算的优点，应用尤为广泛。 不同的插值方法常会有各自的缺点，大致会有以下几种：构造方法复杂，所 需要的插值条件限制较多插值方法限制给定数据点个数不是太大时是可行的 1 1 0 1 ；对所形成的三角形网格的顶点的某些特性进行限制；在数据点的局部区域上 形成一个整体曲面【s j ，而整体曲面有时很难具有数据点所建议的曲面形状，或者 所构造的整体曲面局部调整性较差；由运算结果得不到唯一的插值曲面等。 针对上述问题，该论文提出了一种构造插值曲面的新方法。新方法把空间数 据点作三角划分，在每个顶点处构造一个二次分片多项式曲面片，每个三角形上 的曲面片由三个顶点处的曲面片加权平均产生。由于在每个顶点处构造的是c 1 连续的二次分片多项式曲面片，所以用新方法构造的插值曲面具有较好的保形性 和局部调整性此外，文章详细分析了由边界连续条件构造的方程组在不同情况 下的求解过程，给出了简单方便的求解方法新方法可有效地构造对空间散乱数 据点进行插值的光滑曲面。所构造的插值曲面具有二次多项式的插值精度。 考虑到不同的应用背景，对构造光顺曲面，文章又提出了一种新的基于能量 最小准则的散乱数据点多项式插值方法。构造局部曲面片所需的求解条件仅从该 区域上获得，根据能量最小准则确定未知量，使构造的曲面具有更为理想的局部 调整性。新方法所构造的曲面具有原始数据点所建议的形状，并且对原数据点褶 山东大学硕士学位论文 皱较大部分的插值曲面具有更好的光顺性。最后还同原有方法进行了比较。 但上述两种方法最终得到的是7 次插值多项式，对c 1 连续的多项式插值来 讲次数太高。在今后的研究中要对权函数进行改进，以降低插值曲面的次数，得 到更为稳定简洁的方法。曲面的光顺性是c a g d 中非常重要的一个研究问题， 在以后研究当中，将依据曲面的光顺性准则进行曲面光顺性的改进。 关键词：散乱数据点；插值；多项式曲面；三角形 山东大学硕士学位论文 a b s t r a c t t h ew o r ks t u d i e st h ep r o b l e mo fi n t e r p o l a t i o nt os c a t t e rd a t ap o i n t si ns u r f a c e m o d e l i n g t h et e c h n i q u eo fc o n s t r u c t i n gi n t e r p o l a n tt os c a r e rd a t ap o i n t si su s e d w i d e l yi nm a n yf i e l d so fs c i e n t i f i cr e s e a r c ha n de n g i n e e r i n gd e s i g n , s u c ha sc a d ，t h e c o m p u t e rg r a p h i c s , t h em e t e o r o l o g ya n dt h ee x p l o r a t i o na n ds oo i l a si r r e g u l a r i t yo fs u r f a c ei np r o j e c ta p p l i c a t i o n , a n d 猫r a n d o m n e s sa n dd i s o r d e r o fs c a t t e rd a t ap o i n t s ，i t sd i f f i c u l tt oe x p r e s st h es u r f a c ew i t has o l em a t h e m a t i c a l f o r m a l i s m t h e r e f o r et h ep i e c e w i s em e t h o di su s e dg e n e r a l l yi nt h es r r f a c ed e s i g n , f u m u ya l lt h es u r f a c ep i e c e sa r cc o r r e c t e ds m o o t h l yt of o r maw h o l es u r f a c e t h e m o s tc o m m o n l yu s e ds u r f a c ep a t c h e sa r et h et r i a n g l ea n dt h eq u a d r a n g l es u r f a c ep a t c h a st h et r i a n g u l a ri 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 ys i g n i f i c a n c e ，a n dt h e s u r f a c ec o n s t r u c t e di se a s yf o rt h ea d j u s t m e n t , m o r ea n dm o r er e s e a e h e r sp a yt h e i r a t t e n t i o nt ot h em e t h o d a tp r e s e n to n eo fc o m m o n l yu s e dm e t h o d so fc o n s t r u c t i n g i n t e r p o l a t e ds u r f a c ec a nb ed e s c r i b e ds i m p l ya sf o l l o w s ：t h eg i v e ns c a t t e r e dd a t a p o i n t sa r et r i a n g u l a t e di n t ot r i a n g l en e t w o r k , t h es u r f a c ep a t c ho v c i e a c ht r i a n g l e r e g i o ni sf o r m e da c c o r d i n gt ob o u n d a r yc o n d i t i o no fc o n t i n u i t y , a n de a c hs u r f a c e p a t c hj o i n st o g e t h e rt of o r mo v e r a l li n t e r p o l a t e ds u r f a c ew i t hc c o n t i n u i t i e s t h e r e a r et w om e t h o d sf o ri n t e r p o l a t i o no nt r i a n g l en e t w o r k , o n ei sr a t i o n a li n t e r p o l a t i o n , a n o t h e rp o l y n o m i a li n t e r p o l a t i o n b e c a u s eo ft h em e r i to fs i m p l es t r u c t u r ea n de a s y c a l c u l a t i n g ，p o l y n o m i a li n t e r p o l a t i o ni su s e dm o r ew i d e l y n o wt h e r ea r em a n y m e t h o d st oc o n s t r u c tp o l y n o m i a ls u r f a c et ot h es c a t t e r e dd a t ap o i n t s d i f f e r e n ti n t e r p o l a t i o nm e t h o d so f t e nh a v et h ed i f f e r e n ts h o r t c o m i n g ，a n di tc a l i b ec l a s s i f i e ds i m p l y 鹪f o l l o w ：t h ep r o c e s so fc o n s t r u c t i n gi st o oc o m p l e xa n dt h e i n t e r p o l a t i o nc o n d i t i o ni s l i m i t e db ym a n yf a c t o r s ；t h em e t h o df o ri n t e r p o l a t i o ni s f e a s i b l ej u s ta tt h ec o n d i t i o no ft h a tt h en u m b e ro ft h eg i v e ns c a t t e r e dd a t ap o i n t si s n o tt o ob i g ；t h et r i a n g l eg r i dv e r t e xm u s th a sc e r t a i nc h a r a c t e r i s t i c st os a t i s f yt h en e e d o fc o n s t r u c t i n g ；j u s tf o r m sa no v e r a l l $ n r f a c eo v e rt h ew h o l ep a r t i a lr e g i o no fe a c h d a t ap o i n t , a n dt h eo v e r a l ls u r f a c es o m e t i m e si sd i f f i c u l tt op o s s e s st h es u r f a c es h a p e s u g g e s t e db yt h eg i v e nd a t ap o i n t s ，o rc a n tb ea d j t r e e de a s i l y ；c a n n o to b t a i nt h eo n l y 山东大学硕士学位论文 i n t e r p o l a t e ds u r f a c eb yt h eo p e r a t i o nr e s u l ta n d s oo n i nv i e wo fa b o v eq u e s t i o n , t h i sa r t i c l ep r e s e n t san e wm e t h o dt oc o n s t r u c t i n t e r p o l a t e ds u r f a c et ot h es c a t t e r e dd a t ap o i n t s n e wm e t h o dt r i a n g u l a t e st h eg i v e n d a t ap o i n t si n t ot r i a n g l en e t w o r k , a n da tt h ea 由a e e n tr e g i o no fe a c hp o i n tac 1 p i e c e w i s eq u a d r i ci n t e r p o l a t i o np a t c hi s c o n s t r u c t e d t h es u r f a c ep a t c ho ne a c h t r i a n g l ei sc o n s t r u c t e db yt h ew e i g h t e dc o m b i n a t i o no f t h et h r e eq u a d r i c p a t c h e sa tt h e v e r t i c e so ft h et r i a n g l e a l lt h et r i a n g l ep a t c h e sa r ep u tt o g e t h e rt of o r mt h ew h o l e 汕- f a c ew i t l lc 1c o n t i n u i t i e s b e c a u s et h es u r f a c ep a t c ha tt h ea d j a c e n tr e g i o no fe a c h p o i n ti sc 1p i e e e w i s eq u a d r i ci n t e r p o l a t i o np a t c h , i th a st h ep r o p e r t yo fk e e p i n gs h a p e a n dc a na d j l l s tt h es h a p ee a s i l yo v e rt h el o c a lr e g i o l li na d d i t i o n , t h es o l u t i o np r o c e s s o fe q u a t i o n sf o r m e db yb o u n d a r yc o n d i t i o no fc o n t i n u i t yi nd i f f e r e n ts i t u a t i o ni s a n a l y z e d , a n dt h es i m p l ea n dc o n v e n i e n c es o l u t i o ni sg i v e n t h en e wm e t h o dc a l l c o n s t r u c ts m o o t hs u r f a c ei n t e r p o l a t i n gt h eg i v e ns c a t t e r e dd a t ap o i n t se f f e c t i v e l y , a n d t h ep o l y n o m i a lp r e c i s i o ns e to f t h em e t h o di n c l u d e sa l lt h ep o l y n o m i a l so f d e g r e et w o c o n s i d e r i n gd i f f e r e n tb a c k g r o u n do fa p p l i c a t i o n , f o rc o n s t r u c t i n gt h ef a i r i n g s u r f a c e ，an e wm e t h o do fi n t e r p o l a t i o nb a s e do nt h ec r i t e r i o no fm i n i n l u n le n e r g yi s p r e s e n t e d t h es o l u t i o nc o n d i t i o n su s e dt oc o n s t r u c tp a r t i a ls u r f a c ei so n l yo b t a i n s f r o mt h i sr e g i o n , t h eu n k n o w np a r a m e t e ri sa c q u i r e da c c o r d i n gt ot h ec r i t e r i o no f m i n i m u me n e r g y , s oi te n a b l et h ec o n s t r u o e as u r f a c et oh a v eam o r ei d e a lp a r t i a l a d j u s t m e n tt h en e ws i n f a c 七h a st h es h a p es u g g e s t e db yt h ep r i m i t i v ed a t ap o i n t s ，a n d i sm o r ef a i r i n go v e l t h er e g i o nw i t hb i g g e rd r a p e a tl a s te x a m p l e sa r eg i v e nt o 凼 c o m p a r i s o nw i 也p r e v i o u sm e t h o d b u tt h ea b o v et w om e t h o d sf i n a l l yc o n s t r u c t st h ep o l y n o m i a li n t e r p o l a t i o n so f d e g r e es e v e n , w h i c hi sh i g h e rf o rc 1i n t e r p o l a t i o nw i t hp o l y n o m i a l i nt h ef o l l o w i n g r e s e a r c hw ew i l lm a k et h ei m p r o v e m e n tt ot h ew e i g h tf u n c t i o nb yr e d u c e si t sd e g r e e i no r d e rt oo b t a i nl o w e rd e g r e ep o l y n o m i a li n t e r p o l a t i o n t h ef a i r n e s so fs u r f a c ei sa l l e x t r e m e l yi m p o r t a n tr e s e a r c hq u e s t i o ni nc a g d ，t h ef a i r n e s so fs u r f a c ec a nh e i m p r o v e db a s e do nc r i t e r i o n so f t h ef a i r n e s si nf u t u r er e s e a r c h k e yw o r d ：s c a t t e r e dd a t ap o i n t s ；i n t e r p o l a t i o n ；p o l y n o m i a ls u r f a c e ；t r i a n g l e 原刨性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：盘避避日期：超生：盟：丛 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：函翊盘导师签名： 山东大学硕士学位论文 1 1 研究背景和意义 第一章引言 曲面造型( s u r f a c em o d e l i n g ) 是计算机辅助几何设计( c o m p u t e ra i d e d g e o m e t r i cd e s i g n , c a g d ) i t 】和计算机图形学旧( c o m p u t e rg r a p h i c s ) 雕j - - 项重要 内容，主要研究在计算机图像系统的环境下对曲面的表示、设计、显示和分析。 它起源于汽车、飞机、船舶、叶轮等的外形放样工艺，由c o o m 、b 6 z i e r 等大师 于二十世纪六十年代奠定其理论基础。如今经过四十多年的发展，曲面造型现在 已形成了以有理b 样条曲面( r a t i o n a lb s p l i n es u r f a c e ) 参数化特征设计和隐式 代数曲面( i m p l i c i tm g e b r a i es u r f a c e ) 睁1 0 】表示这两类方法为主体，以插值 ( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 、逼近( a p p r 溺m 撕o n ) 这三种手段【1 l 14 】为骨架的几何 理论体系。 。 但在曲面造型的实际的应用中，人们经常会碰到下面的问题：给定一组数据 点，这些点可以是从某个形状上测量得到的，也可以是设计员给出的，目的是根 据这些点的特征，得到通过这些数据点或者是在某种意义下最为接近给定数据点 的曲面，前者称为插值曲面，后者称为逼近曲面。给出的这些数据点可以是有序 的也可以是无序的。特别在对复杂型面的测量造型中，需要根据型面上曲率变化 情况测得一系列散乱分布的无序点集。常规的几何造型技术无法解决这类数据的 重建问题。散乱数据造型技术正是由此被引入到c a d c a m 中。散乱数据造型 研究根据给定的散乱数据点构造整体光滑曲面的理论与方法。而其中散乱数据插 值曲面的构造，又由于它的精确性在c a g d 的实践中有着广泛的应用。目前， 散乱数据插值( s c a t t e r e dd a t ai n t e r p o l a t i o n ) 技术已广泛的应用于各类科学研究和工 程技术中，如气象，勘探，医学，环保，可视化以及测量造型等。 正如摘要中所说，在运用散乱数据插值技术进行曲面构造时，单一的数学形 式不足以表达不规则的工程曲面，因此构造曲面一般采用分片( 三边曲面片或四 边曲面片) 构造的方法，然后根据一定的连续性进行光滑拼接得到完整曲面。对 于四边形曲面片，所采用的数学模型基本上的都是以矩形参数域为主的张量积曲 面，如b 样条曲面或n u r b s 曲面。有关四边形曲面的研究已经比较成熟，其应 山东大学硕士学位论文 用也比较广泛了。然而，构造曲面时通常要求造型数据具有严格的拓扑关系，特 别是对于无明确分布规律的散乱数据，一般无法利用四边形曲面来完成曲面建 模。而三角插值方法的几何意义明显，便于调整，因此三角域上插值曲面的构造 方法渐渐受到更多的重视。 三角域上的插值方法分为有理插值和多项式插值两种方法。多项式插值的结 构简单，易于计算，不但能方便地用于函数值计算，也能方便地用于微分积分， 所以应用尤为广泛。有理插值比多项式复杂，一般也称其为非线性插值。它的理 论研究和数值计算相对于多项式要困难一些，并且在某些情况下三角域上的多项 式插值是可以确定的，但是有理函数却未必存在。 正是由于散乱数据插值技术的广泛应用，本篇论文将对其进行详细讨论。而 由于上述的三角面片和多项式的诸多优点，对于三角域上的散乱数据多项式插值 技术将作为本篇的重点内容。 1 2 研究现状及本文主要贡献 散乱数据插值是一个经典的研究领域，其历史可以追溯到上世纪2 0 年代， 迄今为止，与其相关的论著多达近4 0 0 0 项。国内外的学者对于散乱数据插值的 研究从未间断过，提出了许多有效的方法。1 9 6 8 年，s h e p a r d 研究了非规则分布 数据的二维插值函到1 5 】，给出了最j 、- - 乘距离加权插值算法，1 9 7 3 年，b a r a h i l l 等人从曲面造型的角度分析散乱数据插值，给出了三角形上的b b g 格式 ( b a r n h i l l - b i r k h o f f - o o r d o n ) 1 1 6 l 。此后，许多学者从不同角度探索了散乱数据插 值曲面的构造1 7 - 2 0 ，并取得了很多成果，如f a r i n 提出了构造c l 连续曲面三角 b e r n s t e i n - b 6 z i e r 曲面的方法和步骤 2 1 - 2 3 。国内对散乱数据插值曲面的研究始于上 世纪8 0 年代，二十多年来，已取得许多研究成果i s , t 0 1 2 5 - 3 0 ，如汪嘉业教授和张 彩明教授提出的散乱数据点的多项式插值【8 10 t 冽；姜寿山提出的散乱空间数据的 g 1 和g 2 插值嘲，关于散乱数据点的c 1 五次插值【3 0 l ；以及柯映林、朱心雄、周 晓云等人对于散乱数据几何造型技术的研究等阳- 2 9 。 由于四边曲面片在散乱数据插值中的局限性，目前构造散乱数据插值曲面的 基本方法是：对散乱数据进行三角剖分，在三角网格上构造几何连续或参数连续 2 山东大学硕士学位论文 的三角曲面因此，三角曲面是散乱数据插值曲面的基础，而三角域上的散乱数 据插值技术渐渐受到越来越多的重视。三角曲面最初是由d ec a s t e l j a u 于上世纪 5 0 年代末提出的”但其成果直到1 9 7 5 年才被b o e h m 发现【2 1 ，7 0 一8 0 年代，国 外对三角曲面进行了系统深入的研究，代表性的学者有s a b i n 4 1 ，g o r d o n 【1 3 】， b a n l l l i l l 【1 6 1f a r i n 2 , z ! - 2 3 1 以及g e r g o r y l 2 4 1 等人。特别是f a r i n 提出的通过构造特殊 的边界曲线，实现参数三角b e z e i e r 曲面g 1 拼接的方法【捌，以其简单，实用而被 广泛采用。8 0 年代以来，我国学者对三角曲面开展了广泛的研究。如汪嘉业教 授研究了三角域上的c 2 插值方法【2 6 】，柯映林博士提出的准c l 连续三角b 6 z i e r 曲面【3 3 】的构造方法也有一定的实用价值。汪嘉业教授 5 6 ，8 矧，张彩明教授 6 , 8 a 0 , 3 1 】 对三角区域上的多项式插值的研究做出了突出贡献。他们提出的在三角域上构造 多项式函数的曲面的方法，由于其结构简单，易于计算的特点得到了广泛的关注。 需要注意，对于散乱数据进行多项式插值的很多解决方法都各有其缺点，如 文献 6 1 的方法根据三角形顶点函数值和一阶偏导值进行插值构造四次多项式曲 面片，但要求三角形网格各顶点的度是奇数。文献 7 1 的方法除了需要三角形顶点 函数值和一阶偏导值外，还需要在三角形边界的中点处给定一阶法向导数值，共 需要1 2 个插值条件。文章嘲的方法在三角形顶点处只需要函数值作为插值条件， 但在每个数据点的局部区域上形成的是一个整体曲面，这种整体曲面有时很难具 有数据点所建议的曲面形状。在三角形网格上的其他方法p l 】是由边界连续条件建 立方程组，求解方程得到c 1 连续的曲面。文献【lo 】中所提出的解决方法在给定数 据点个数不是太大时是可行的，而当给定的数据点个数较大时此方法并不适用， 所构造的整体曲面局部调整性差。 针对上述问题，本论文将提出一种构造插值曲面的新方法，新方法把空间数 据点做三角划分，在每个顶点处构造一个二次分片多项式曲面片，每个三角形上 的曲面片由三个顶点处的曲面片加权平均产生。新方法可有效地构造对空间散乱 数据点进行插值的光滑曲面。由于在每个顶点处构造是c 1 连续的二次分片多项 式曲面片，用新方法构造的插值曲面将具有较好的保形性和局部调整性。 但上述方法没有考虑曲面的光顺性问题，在给定数据点的褶皱较大的部分所 构造的插值曲面并不具有良好的光顺性。曲面的光顺性与曲面的最小应变能有 关，基于此，提出了一种新的基于能量最小准则的散乱数据点多项式插值方法。 山东大学硕士学位论文 此方法所构造的曲面具有更为理想的局部调整性和光顺性。 1 3 各章安排 本文主要分为六个部分，各章内容安排如下： 第一章为引言，对论文的意义及论文整体的安排进行了介绍。 第二章对散乱数据插值曲面的构造方法进行了概述。给定一组有序点 p ，( x ，y ，z ) ( f = o ，l ，2 ) ，这些点可以是从某个形状上测量得到的，也可以是设 计员给出的。要求构造一个曲面通过这些数据点，称为对这些数据点进行插值 ( i n t e r p o l a t i o n ) ，所构造的曲面称为插值曲面。该部分将简单介绍散乱数据插值 所涉及的基本知识，并且对基本的散乱数据插值曲面的构造原理及基本方法、过 程进行概述。 第三章主要介绍了两种构造散乱数据点多项式插值曲面的方法。 汪嘉业教授提出了用加权平均法构造c 多项式插值曲面，其主要步骤是： 把给定数据点在x y 平面上划分成三角形网格，在每个数据点处构造一个满足该点 插值条件的曲面片，每个三角形上的曲面片由三个顶点处的曲面片加权平均产 生。整体曲面由各三角形上的曲面片拼合而成。 张彩明教授提出一种构造具有较高精度的插值曲面的方法，该方法用分片三 次多项式曲面对散乱分布数据点进行插值。把给定区域划分成三角形网格，在每 个三角形上构造一个三次多项式曲面片，整体的c 1 曲面由各三角形上的曲面片 拼合而成。讨论了整体曲面满足c 1 连续的条件，并讨论了由这些条件组成的方 程组的性质，并给出了求解方程组的方法。插值方法的多项式准确集包括所有三 次和小于三次的多项式。 第四章研究了散乱数据点分片二次多项式加权平均插值的问题。针对第三章 中讲到的两种方法的缺点，提出了一种构造插值曲面的新方法。新方法把空间数 据点做三角划分，在每个顶点处构造一个二次分片多项式曲面片，每个三角形上 的曲面片由三个顶点处的曲面片加权平均产生。由于在每个顶点处构造是c 1 连续 的二次分片多项式曲面片，所以用新方法构造插值曲面具有较好的保形性和局部 4 山东大学硕士学位论文 调整性。首先讨论了在各个数据点邻接区域上三角面片满足c 连续的条件，并 且对由连续条件产生的方程组在不同条件下的解进行了讨论，然后给出了三角形 曲面片的构造方法。最后用实例同其他方法所构造的插值曲面形状进行了比较。 第五章在第四章的基础上提出了一种新的基于能量最小准则的散乱数据点 多项式插值方法。构造局部曲面片所需的求解条件仅从该区域上获得，根据能量 最小准则确定未知量，使构造的曲面具有更为理想的局部调整性。新方法所构造 的曲面具有原始数据点所建议的形状，并且对数据点褶皱较大部分的插值曲面具 有更好的光顺性。文章还同原有方法进行了比较。 在第六章做出结论，对上述插值方法给出了总体评价，展望以后的工作方向， 表达了在实践中推广的愿望。 山东大学硕士学位论文 第二章散乱数据插值曲面概述 在介绍散乱数据插值曲面的构造方法之前，我们有必要先了解一些具有基础 性质与普遍意义的基本概念以及思路和研究方法。 2 1 基础知识 2 1 1 插值与逼近 给定一组有序点p f ( 而，y ，z ，) ( f = o ，l ，2 ) ，这些点可以是从某个形状上测量 得到的，也可以是设计员给出的。要求构造一个曲面通过这些数据点，称为对这 些数据点进行插值( i n t e r p o l a t i o n ) ，所构造的曲面称为插值曲面。这些数据点若 原来位于某曲面上，则称该曲面为被插曲面。构造插值曲面所采用的数学方法称 为曲面插值法。插值法在c a g d 的实践中有着广泛的应用。 在某些情况下，测量所得或设计员给出的数据点本身就很粗糙，要求构造一 个曲面严格通过给定的一组数据点就没有什么意义。比较合理的提法是构造一个 曲面使之能在某种意义下最为接近给定的数据点，称之为对这些数据点进行逼近 ( a p p r o x i m a t i o n ) ，所构造的曲面称为逼近曲面。这些数据点若原来位于某曲面 上，则称该曲面为被逼曲面。构造逼近曲面所采用的数学方法称为曲面逼近。 插值与逼近统称为拟合( f i t t i n g ) 在该篇论文中仅就插值问题进行讨论。 2 1 2 多项式基 在c a g d 中，参数形式已成为形状数学描述的标准形式。而参数曲线曲面方 程一般地又都写成为基表示式。这样就面临一个问题，应该选择怎样一类函数作 为基函数昵? 这仍然由形状数学描述要求所决定。人们首先注意到在各类函数 中，多项式函数能较好地满足要求。它表示形式简单，又无穷次可微，因而足够 光滑，且容易计算函数值及各阶导数值。采用多项式函数作为基函数即多项式基， 就得到相应的多项式曲线曲面。 刀次多项式的全体构成疗次多项式空间。n 次多项式空间中任一组栉+ 1 个线 性无关的多项式都可以作为一组基，其中最简单的基是幂基。 6 山东大学硕士学位论文 幂( 又称单项式m o n o m i a l ) 基：，7 ，j = 0 , 1 ，一是最简单的多项式基。相应 的参数多项式曲线方程为 p ( o = a t 7 j = 0 其中a j - - - ( x , ，y j ，乃) 为系数矢量，f 是参数。同理可推广到曲面，在后面的章节中 会进行详细讲解。 i t 次多项式空间中有无穷多组基，不同组基之间仅仅相差一个线性变换。同 一条参数多项式曲线或一张参数多项式曲面片可以采用不同的基表示，由此决定 了它们具有不同的性质，因而具有不同的优缺点。这就提出了一个问题，应该选 择怎样的多项式基才最适合c a g d 关于形状数学描述的要求。在后面的章节中 会看到，为了计算方便选择了另外一种多项式基，使表达及计算大大简化了 2 1 3 三边曲面片 近年来，三角形网格上曲面片的构造受到越来越多的重视。三边曲面片【1 翻 受到较多注意的原因在于它适应不规则与散乱数据几何造型和避免出现退化的 需要，及适合于有限元分析中广泛应用的三边形元素的需要。由于它具有构造复 杂形状的潜力，在将来会获得较广泛的应用下面的讨论都是建立在三边形网格 的基础上的。先来看一下三边曲面片的基本知识。 1 三边曲面片的表示 首先遇到的问题是三角域内一点怎样表示，显然它只应与三顶点的相对位置 有关，直角坐标在这里不再适用。下面介绍三角形内一点的面积坐标与重心坐标。 平面内一个矢量可以表示为另外两个线性无关的矢量的线性组合。于是，对 于三角形a b c 内一点p ( 如图2 1 ) ，就有 p - c = u ( a c ) + v ( b - c ) p = 撇+ v b + ( 1 一甜一v ) c 于是可给出 p = 凇+ v b + w c 图2 1 其中“+ v + w = l 玎，v ， ，就是p 点在三角形a b c 内关于a ，b ，c 三顶点的重心 山东大学硕士学位论文 坐标。又分别可看作配置在该三点的重量，p 就是它们的重心。 当p 点在平行于抛边的直线上移动时，它的“坐标不变。类似地，当p 点分 别沿边与曲边移动时，分别有v 坐标与w 坐标不变。 重心坐标与面积坐标是一致的，即有 三角形p 6 c 的面积 肛三葡酝秭面爵 三角形p 的面积三角形阳6 的面积 w = ：一 三角形a b c 的面积 时针旋转为负。若口= k ，q 】，6 = 6 ；，b y ，c = 【c 。，c ，】，则 三角形口缸的面积= 丢阵b x ； ， 利用重心坐标不仅可以确定三角形内一点，也可以确定三角形外任意一点。 假设给定三维空间不共线三点见，p 2 ，p 3 ，则由下式表示的p 点 p = 印i + 1 矽2 + w p 3 ， “+ v + w = 1( 2 1 ) 恒位于由p l ，p 2 ，p 3 三点张成的平面内。这里既可以把甜，1 ，解释为p 点相 对于，l ，p 2 ，p 3 三点的重心坐标。也可以把“，1 ，w 解释为在二维域平面内的 点相对于某三角形a b c 的重心坐标。这三角形a b c 称为域三角形，或称为三角域。 它的实际位置与形状恒与2 1 式关于p 点的定义无关，只要求它是非退化的，即 a ，b ，c 三点是不共线的。这个从二维平面到三维空同的映射是个仿射映射。 知道了三角域内一点是如何表示的，那如何来表示三边曲面片呢? 一般有两 种方式：一是三边贝齐尔曲面片，一是多项式曲面片。对三边贝齐尔曲面片的表 示我们仅做简要介绍，多项式曲面片我们在下一小节将进行详细介绍。 使一个基函数联系一个控制顶点，一张r 次三边贝齐尔曲面片必须由构成三 角阵列的0 + 1 ) 0 + 2 ) 2 个控制顶点以。肚( f + _ ，+ k - - - n ) ( i ，工k 2o ) 定义。因此，立 即可写出曲面片的方程 叫 p ( u ，bw ) = 以 b n ( 地v ，w )o u w 2 的g ”连续性，此时几何量少了或根本用不上了，难以看出 g “连续性有什么实际意义。 2 2 散乱数据插值曲面的构造 设空间给定了一个散乱分布的数据点只= “，弗，f ) ，= 1 ，2 ，玎，目标是构 造一张分片定义的多项式曲面f ( x , y ) ，满足f ( x s ，儿) = e ，i = l ，2 ， 目前根 据给定的散乱数据点构造插值曲面的一般过程如下： 1 ) 对给定的散乱数据点进行三角剖分，并作必要的修正； 2 ) 计算三角网格边界条件，构造初始三角曲面； 3 ) 构造整体连续的散乱数据插值曲面。 首先，三角剖分( 或称三角化) 1 3 7 是实现散乱数据插值必要的前置处理。三 角剖分可分为对三维散乱数据投影域的剖分和在空间直接剖分两种类型。散乱数 据的投影域包括平面域和球面域。直接三角剖分方法研究如何直接将三维散乱数 据点在空间中连接成一个最优的三角网格。本课题将采用对散乱数据投影域的剖 分。由于该部分不是重点，本篇论文不进行详细介绍。 1 0 山东大学硕士学位论文 在三角形上构造的曲面片表达形式常用的是三角b e m s t e i n - b 6 z i e r 曲面瞄1 参 数表达式或多项式表达式下面讨论两种表达方式下进行散乱数据点的插值的基 本原理和过程。 1 g 1 连续插值曲面 构造散乱数据插值曲面是指散乱数据点经三角剖分后，在网格的每个三角形 上构造插值于三顶点的三角b b 曲面片，并使各曲面片间满足一定的连续性要 求( 在工程中常要求达到g 1 连续) ，插值于给定散乱数据点的曲面有无穷多个。 p i p e r 【3 8 1 指出，在三角网格上构造g 1 连续散乱数据插值曲面至少需采用四次 三角b - b 曲面片，并用反例说明了三次三角b b 曲面片并不总能构造出g 1 连续 的散乱数据插值曲面。用三角b b 曲面片构造插值曲面的原理和步骤如下。 1 ) 原理 用四次三角b b 曲面片构造散乱数据插值曲面的原理是：根据边界条件在 三角网格上构造初次的三次三角b b 曲面片；调整与各顶点相邻的控制顶点， 使各顶点处满足g 1 拼接的相容性要求；将曲面片由三次升阶到四次；为了给曲 面片沿边界拼接提供足够的自由度，对曲面片进行c t 分割，将个曲面片分割 为三个子曲面片 3 9 1 ；调整各子曲面片的控制顶点，保证各子曲面片问g 1 连续。 2 ) 算法步骤 构造g 1 连续散乱数据插值曲面的算法如下： 在具有边界条件的子三角网格上构造初始三次三角b b 曲面片； 根据顶点相容性调整方法及计算公式，调整与各顶点相邻的控制顶点， 使各顶点处满足连续性相容条件； 曲面片由三次升阶到四次： 对曲面片进行c t 分割，将一个曲面片分割成为三个子曲面片； 调整各子曲面片的控制顶点，保证其父曲面片沿边界g 1 连续； 调整该三个子面片的控制顶点，使相互间沿边界达到g 1 连续。 2 散乱数据点的多项式插值曲面 山东大学硕士学位论文 构造散乱数据点的多项式插值曲面的基本做法是：把点瓴，乃) ，i = 1 , 2 ，l 在拶平面上根据某种标准做三角形划分，在每 个三角形丁上构造多项式曲面片f r ( x , y ) 所有 曲面片拼合起来形成整体曲面f 瓴力。 设三角形丁的三顶点坐标是b = ( x l ，y t ) ， l = f ，j ，k ，如图2 4 ，其面积为& 三边中点处 图2 4 的一阶外法向导数记为( l ，m ，以) ，而面积坐标( 厶，l j ，丘) 则定义如下： l i b ，n = x j y k x k y j + b ，一y k + b k x j ) y 2 $ l j 囊，n = 0 k y l x l y | + 【y i y l + b t x k ) y 2 s q 3 ) l k ( x , y ) = u l y j xj y t + o l y j ) x + ( x t x f ) y 2 8 下面讨论如何构造不同次数的多项式曲面。 1 ) 构造线形插值曲面 给定的插值条件是三个顶点处的函数值鼻，乃和疋。则三角形上线形插值曲 面是： 易( 五力= 厶( x ，y ) 巧+ ( x , y ) f j