（计算机软件与理论专业论文）三角形域上的超限插值.pdf

山东大学硕士学位论文 摘要 本文对曲面造型中三角形域上的超限插值曲面问题进行了研究。构造三角形 域上的超限插值曲面技术在c a d 、计算机图形学、气象和勘探等各类科学研究 和工程设计中有广泛的应用。 通过曲线边界插值构造三角曲面片的方法是由b a r n h i l l ，b i “h o f f 和 g 0 r d o n “”首先提出来的，该方法采用布尔和算子构造三角曲面片。g r e 9 0 r y 使用 凸组合的方法构造三角曲面片，其思想在文献嘶中得到了进一步的发展。所构 造的三角曲面片由三个插值算子的凸组合构成，每个插值算子均满足三角形两条 边上的插值条件。n i e l s o n 提出的边点法也使用三个插值算子的组合构造三角 曲面片，每个算子都满足一个点及其对边上的插值条件。h a g e n 进一步发展了 边点法，并用来构造几何三角曲面片。文献提出了用于散乱数据点插值的方法， 该方法也用于构造三角曲面片。最近文献提出了一个由四个插值算子的组合构 造插值三角曲面片的新方法，包括一个内部插值算子和三个边点算子。文献1 提出了由基本逼近算子加上附加算子构造三角曲面片的方法。n i e l s o n 洲提出的 九参数构造曲面片是利用给定顶点的法向和函数值求出顶点的单位切矢量，然后 利用边点法求出边界曲线及边界单位法向，最后利用边点法构造三角曲面片。 对于三角形区域上进行多项式插值的很多解决方法都各有其缺点，如 n i e l s o n “0 1 提出的九参数构造曲面片是利用给定顶点的法向和函数值求出顶点的 单位切矢量，然后利用边点法求出边界曲线及边界单位法向，最后利用边点法构 造三角曲面片，对参数要求过多，并且会因为a 和口无法确定而造成的误差较大 的问题等。 针对上述问题，本文提出了一种使用六个参数构造三角曲面片的新方法。该 方法利用具有公共边的两个三角形区域的四个顶点的函数值及外法向量来构造 一个二次曲面片，通过该二次曲面片求出共用边界曲线及跨界切矢量；同样可以 求出另外两条边的边界条件，然后利用求出的边界条件进行边点插值求出该三角 曲面片。对于只属于一个三角曲面片的边界，即边界三角片进行了特殊处理。 和现有方法相比，新方法的优点是：利用六参数构造三角曲面片，相对以前 的九参数( 顶点值和两个参数方向的切矢量) ，对条件的要求更少，并避免了 山东大学硕士学位论文 n i e l s o n 方法中由于a 和口无法确定而造成的误差较大的问题；该方法简单易用， 在一定程度上避免了以前方法中，计算复杂性高、特殊情况误差大等问题。 最后，实验给出了新方法的结果，并和n i e l s o n 方法的结果进行了比较。 关键词三角曲面片：二次多项式；六参数：插值；二次曲线参数化 山东大学硕士学位论文 a b s t r a c t 1 1 1 ew o r ks t 砌e sm ep r o b l e mo fn 郇o l a d o nt 0s c a t t 盯蛔p o i n 协i l ls u 如 m o d e l i n g t h et 即h i l i q u eo fc o n s t m 幽gi n t e q p o l a t et os c 毗汀p o i n 乜i s 璐e d 谢d e l yi i im 锄yf i e l d so f s d 腼cr 鼯e 盯c h 锄d 舀n e e 血曙d e s i g l i ，s u c h 雒c a d ，t l l e c o l l l p u t e rg r a p i l i 岱，m em 咖r o l o 汀趾dm e 唧l o 枷o na i l ds oo n c o 船饥l c t i i l g 仃i 锄g l l l 盯p 眦h e st i l r i o u 曲b o u n d a r yi i 她q o l 撕w 舔f i r s t i n 仃0 d u c e db yb 袖i l l ，b i r i 【1 1 0 置g o r d o n “帕，砌c hc o n s 仇l c t 砸锄g l d a rp a t c h 豁嘴i n g b 0 0 l 咖s 啪o p e r 栅g r e g o r y 啪s 仃u c t e dt f i 锄g i l l 盯p 疵h 嚣血r o u g hc o i e x c o f n b i n 撕，w h i c l lw 豁f u r l h 盯d e v e l o p e di n p a p e r 陆枷t h e 仃i 锄g l l i a rp a 女c h e sm 锣 c o n s t r u c t e dw e r ec o m p o s e do ft i l ec o n v e 】【c o n l b i n 撕o no ft t l l i i l t e t p o l 舳g o p e r 咖培，e a c ho fw h i c hs 撕s 每t h ei n t 印o l a t i c o n 越i o n s b o t l le d g 嚣o ft h e 伍卸百e ，n i e l s o n 啪1p r o p o s e dm ee d g e p o i n tm e t h o dw h i c ha l b ef i l l f i l l e dt 1 1 i d u 曲 1 l l | i n t e i p o l a t i o no p e r a t o r s ，e ho f w i l i c hs a t i s f i 鼯m ei n t e r p o l a l i o nc o n d i t i 傩o f e p o i i l t 锄dt l l eo p p o s i t ee 电e h e g 髓嘲f h n l l e rd e 、，e l o p e d1 h ee d g e - p o i n tm e l l l o d ，锄d u d “t dc o n s 仃i l c tg e o m 硎c 埘肌g i l l a rp 砒c h e s h lp 印e r 口们t l l ea l l i 】吣fp r o p o s e d i n t e r p o l a t i m r o u 曲s c a t t e ”dd a t a ，w h i c ha l s o b el l s e di i i 缸a 1 1 9 u l a rp a t c h e s c o n s 饥l c t i o n r e c 锄t l yi np 印e r “1w h i c hp r o p o s ec o n s 饥l c t i o n 仃i 锄9 1 1 l 盯p a t c h e s t l l i d u 曲f o u ri m e r p o l a t i o no p e r 咖培，i n c l u d i n g 缸血e ri n t e r p o l 撕o no p e f a t o ra n d i r e ee 电e p o i n t0 p 锄幻硌h lp 印e r 啪1t l l e yp r o p o s e dm em e t l o do fb 撕ca p p r o a c h 0 p e r a 时趴da d d i 6 0 n a lo p 懿岫rf o rc o n s t r u c 石n gm 锄g u l a rp a t c h 嚣n i e l s o n “0 1 p r o p o s e d1 1 i n e p 黜蝴c o n s 仉l 锄gp a c c h e sw h i c he v a l m 由et h e i l i tt a 】n g tv e c t o r 璐i n gt i l e 萄v v e n e xn o m l a l 锄df 缸c t i o nv a l u e ，血c o m p u t e1 l l eb o l 】l l d a qc u e 肌db o m d a r yl l i tn o m a lv e c t o r 惦i n gt i l ee d g e _ p o mm e t l l o d ，a tl a s t n s 仃u c 矗n gm e 伍锄g l i l 孤p a t c h 鹤u s i n ge d g e p o i n tm e t l l o d t h e r ea r em a 町m e t i l o d st oc o n s 仃1 l c tp o 驷o i l l i a li i l _ t e 叩o l a l e 仃i 锄西部，尚c h h a v ed i f f b r e n ts h o n c o l i l i n g f o re x a m p l e ，n i e l s o n p r o p o s e dc s 虮l c 血gs u 慨e p a t c h 谢t hn i g b p a r 锄e t 盱，w i l i c hc o i n p u t 船吼“v e c t o ro f t 量i e 萄v e nv e 巾懿璐i i 唱1 l l e 山东大学硕士学位论文 n 伽【1 1 a l 肌df u n c 石v a l u e ，t h e ng e t sb o l l i l d a r yc u r v ea l l du n i t m l a il l s i n g 面d e v e r c e xm e 山o d ，f i n a l l yc o n 鲫n l c t s 仃i a n g i l l a rs u r f 缸ep a t c h 惦i n gs i d e - v e r t e x m e t l l o d ，b u t1 量l e r ee ) 【i s tp r o b l e n 璐s u c h1 l l a tt i l ef e q u e s to f p a r a m e t e ri st 0 0m u c h ，锄d t 1 1 e 啪rc a u s e d b y l l l e u n c o n f i 加e d o f口a n d a i i l l i n ga tm ea b o v ep r o b l e l i l s ，an e wm e t l l o df o rc o 咖c t h l gs u 嘞c ep a c c h 仃i a n 掣鼯w i ms i x p a r 锄e t e fi sp r 舒e n t e di i lm i sp a p e r t h en e w m e t l l o dd e f ，m e sa p a t c ho fq i l a 嘶cp o l y n o i i l i a lo n “v ot f i 觚9 1 e sw h i c hh a v eac o m n l l i i l e b o 吼d a r y w i t l l t l l e 百v e n f l m c 矗o n a n d o m w 孤d s f h c e m a l o f f o u r v e n i c e s o f l l l e 咖t l j a n 百船，w ec 肌g e t1 h eb o l l n d a i y 柑ca n d t l l ec r o s s j b 0 吼d a 可s l o p e ，i nt l l e s 黜w a y ，w ec 趾g e t1 l l eo t l l e r s s ow eg e tt h ei i l t e r p o l a 石o nc o n d i 缸o n so n 也e b o m d a r yo f t l l e 埘锄翻e ，t l l e i lw ec 锄c s t n l c tt l i e 缸锄g i l l a rp 锄c h 舒b ys i d e - v e r t 既 m e l l l o df o rt l l eb o m d a r yo n l yb e l o n 垂n gt o e 伍锄甜e w ed 0i ts p e c i a l l y c o m p a r i n gw i t l le ) 【i t e dm e t l l o d s ，m ea d v 锄t a g eo f n e wm e t l l o di s ：n 曲m c t i n g s u m p a t c h 谢t hs i x p 猢e t e “e q u e s 怡l 韶sp a r 锄e t e r 锄da v o i d s1 l l ee n d rc a u s e d b y l h e 硼c f i 加e d o f 口锄d 卢；t l l i s m e m o d i ss i r n p l e 幻憾e 锄d a v o i d s l l i 曲 c o m p u t ec o m p l e ) ( i t y 锄dg r e a 士e r r o ro f s p e c i a li n s t a i l c ea tac e n a i l le ) ( t 肌t t h r o u 曲e 冲e r i m e 鸭w es h o w t l l er 韶讪bi nt l l e 胁do f l l l i sp a p e r 锄dc o 唧a r e d 谢t 1 1也er e s u l t so f n i e l s o n s l ( e yw o r d s s c a n e m dd a 协p o i n 鹕h t e r p o l a t i 叫；p o i y n o m i 蚰s u r f a c e ； t r i 卸g k 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：芝茑辫 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 _ f 女， ( 保密论文孟解讧! _ 铬应遵守此规定) 论文作者签名：遣瀚师签名： 期：迎p 坐 山东大学硕士学位论文 1 1 研究背景和意义 第一章引言 曲面造型( s u m m o d e l i n 曲是计算机辅助几何设计 i n p m i 盯a i d e d g e o m e m cd 韶i g l l ，c a g d ) “”和计算机图形学“”( c o m p u t e rg r a p l l i c s ) 的一项重要 内容，主要研究在计算机图像系统的环境下对曲面的表示、设计、显示和分析。 它起源于汽车、飞机、船舶、叶轮等的外形放样工艺，由c o s 、b 6 五盯等大师 于二十世纪六十年代奠定其理论基础。如今经过四十多年的发展，曲面造型现在 已形成了以有理b 样条曲面( r 觚伽a lb s p l i n es u 舭e ) “”参数化特征设计和隐式 代数曲面m n p l i d ta l g e b r a i cs u 妇e ) 睁圳表示这两类方法为主体，以插值 血由e q ) o l 撕o n ) ，拟合( f i 砸n 蓟、逼近( a p p r o ) i m a l i o n ) 这三种手段1 “1 为骨架的几何 理论体系。 但在曲面造型的实际的应用中，人们经常会碰到下面的问题：给定一组数据 点，这些点可以是从某个形状上测量得到的，也可以是设计员给出的，且的是根 据这些点的特征，得到通过这些数据点或者是在某种意义下最为接近给定数据点 的曲面，前者称为插值曲面，后者称为逼近曲面。给出的这些数据点可以是有序 的也可以是无序的。特别在对复杂型面的测量造型中，需要根据型面上曲率变化 情况测得一系列散乱分布的无序点集。常规的几何造型技术无法解决这类数据的 重建问题。散乱数据造型技术正是由此被引入到c a d ，c j m 中。散乱数据造型 研究根据给定的散乱数据点构造整体光滑曲面的理论与方法。而其中散乱数据插 值曲面的构造，又由于它的精确性在c a g d 的实践中有着广泛的应用。目前， 散乱数据插值( s c 甜e r e dd a t ai n t 印o l 撕o n ) 技术已广泛的应用于各类科学研究和工 程技术中，如气象，勘探，医学，环保，可视化以及测量造型等。 正如摘要中所说，在运用散乱数据插值技术进行曲面构造时，单一的数学形 式不足以表达不规则的工程曲面，因此构造曲面一般采用分片( 三边曲面片或四 边曲面片) 构造的方法，然后根据一定的连续性进行光滑拼接得到完整曲面。对 于四边形曲面片，所采用的数学模型基本上的都是以矩形参数域为主的张量积曲 面，如b 样条曲面或m 瓜b s 曲面。有关四边形曲面的研究已经比较成熟，其应 山东大学硕士学位论文 用也比较广泛了。然而，构造曲面时通常要求造型数据具有严格的拓扑关系，特 别是对于无明确分布规律的散乱数据，一般无法利用四边形曲面来完成曲面建 模。而三角插值方法的几何意义明显，便于调整，因此三角域上插值曲面的构造 方法渐渐受到更多的重视。 三角域上的插值方法分为有理插值和多项式插值两种方法。多项式插值的结 构简单，易于计算，不但能方便地用于函数值计算，也能方便地用于微分积分， 所以应用尤为广泛。有理插值比多项式复杂，一般也称其为非线性插值。它的理 论研究和数值计算相对于多项式要困难一些，并且在某些情况下三角域上的多项 式插值是可以确定的，但是有理函数却未必存在。 正是由于三角形区域上的曲面插值技术的广泛应用，本篇论文将对其进行详 细讨论。对于三角域上的二次多项式插值技术将作为本篇的重点内容。 1 2 研究现状及本文主要贡献 在c a g d 、c g 和自由曲面造型中，三角曲面片的构造具有重要的地位。在曲 面造型过程中，构造一张曲面光滑地连接三张曲面，从而形成整体曲面是经常遇 到的一个问题。由于所连接的曲面可以是任意曲面，因此所要构造的曲面的边界 是任意形式的曲线。对这种任意边界条件的插值称为超限插值。本文对现有三角 形域上的超限插值方法进行综述。一个插值方法被称为具有n 次多项式的插值精 度，如果给定的插值条件取自一张n 次多项式曲面，插值方法构造的插值曲面就 是该n 次多项式曲面。 1 9 6 4 年，美国工程师c 0 0 n s 提出了在矩形域上由边界曲线构造插值曲面的方 法，被称之为c o o n s 曲面方法。该方法和b e z i e r 曲线曲面方法一起为c a g d 和 c g 的形成和发展奠定了坚实的基础。b a r n h 订l ，b i r k h o f f 和g o r d o n “”推广了 c 0 0 n s 曲面构造方法的思想，提出了在三角形域上由边界曲线构造插值三角曲面 片的方法，该方法和c o o n s 曲面构造方法一样，采用布尔和算子构造三角曲面片， 并且要求给定的插值条件满足相容性。如果给定的插值条件不满足相容性，所构 造的三角曲面片上还需加上一修整项以去掉不相容性m 。1 。 g r e g o r y 臼2 删使用凸组合的方法构造三角曲面片，所构造的三角曲面片由三 个插值算子的凸组合构成，每个插值算子均满足三角形两条边上的插值条件。“ 山东大学硕士学位论文 “中的思想在文献“中进行了推广，并得到了构造四边形和五边形曲面的方法。 对于构造五边形曲面，有兴趣的作者还可参阅文献“”，关于一边形曲面的构造 请参阅文献“。n i e l s o n 提出的点边法也使用三个插值算子的组合构造三角 曲面片，每个算子满足一个点及其对边上的插值条件。方法“都具有三次多 项式插值精度。h a g e n 进一步发展了点边法，提出了构造几何三角曲面片的方 法，但该方法没有讨论在一般情况下如何确定跨界切矢长度。文献“中的结果 已被一般化为构造具有一阶或二阶几何连续的三角曲面片的方法。文章伽中的 方法将三角形细分为两个子三角形，在每个子三角形上各构造一张曲面片，两张 曲面在公共边界上满足c 1 连续，所生成的三角曲面片具有四次多项式插值精度。 文献也对构造三角曲面片问题进行了研究，但文献。”不是对任意边界曲线插 值，该方法是由在三角形项点处给定的插值条件构造边界曲线，然后构造对边界 曲线插值的曲面。 文献删提出了移动三角形的插值方法，该方法具有三次多项式插值精度。文 献呻1 提出了一个由四个插值算子的组合构造插值三角曲面片的新方法，其中一个 内部插值算子和三个点边算子嘲，内部插值算子和传统的插值算子的区别是，它 不仅考虑了三角形边界，而且考虑了三角形内部的曲面形状，所生成的三角曲面 片具有四次多项式插值精度。文献1 对方法做了改进，把点边算子b 5 1 改成四次 插值曲线，从而提高了曲面的插值精度。最近，文章1 提出了一个构造三角曲面 片的新方法，三角曲面片由基本逼近算子加上附加算子形成，该曲面也可以看作 是由基本逼近算子和n e i l s o n 算子的布尔和生成，其中基本算子是一个五次多项 式曲面，而n e i l s o n 算子是由点边法产生的。基本算子使三角曲面片有五次多项 式的逼近精度，n e i l s o n 算子使三角曲面片满足给定的插值条件，从而使构造的 三角曲面片在满足给定的c 1 边界条件下具有五次多项式插值精度。 需要注意，对于三角形区域上进行多项式插值的很多解决方法都各有其缺 点，如n i e l s o n 提出的九参数构造曲面片是利用给定顶点的法向和函数值求出 顶点的单位切矢量，然后利用边点法求出边界曲线及边界单位法向，最后利用边 点法构造三角曲面片，对参数要求过多，并且会因为a 和口无法确定而造成的误 差较大的问题等。 针对上述问题，本文提出了一种利用六参数构造三角形曲面片的新方法。利 山东大学硕士学位论文 用具有公共边的两个三角形区域的四个顶点值及外法向量来构造一个二次曲面 片，利用该二次曲面片求出两个三角形区域共用的边界曲线及其跨界切矢量，同 样可以求出另外两条边界曲线及其跨界切矢量：对于只属于一个三角形区域的边 界，进行了特殊处理。然后利用得到的边界条件进行边点插值，得到三角形曲面 片。 和现有方法相比，新方法的优点是：利用六参数构造三角曲面片，相对以前 的九参数( 顶点值和两个参数方向的切矢量) ，对条件的要求更少，并避免了 n i e l s o n 方法中由于a 和卢无法确定而造成的误差较大的问题：该方法简单易用， 在一定程度上避免了以前方法中，计算复杂性高、特殊情况误差大等问题。 1 3 各章安排 本文主要分为五个部分，各章内容安排如下： 第一章为引言，对论文的意义及论文整体的安排进行了介绍。 第二章对超限插值曲面的构造方法进行了概述。给定一组有序点 n ( 一，以，z ，) ( f = 0 ，l ，2 ) ，这些点可以是从某个形状上测量得到的，也可以是设 计员给出的。要求构造一个曲面通过这些数据点，称为对这些数据点进行插值 ( i n t e r p o l 甜0 1 1 ) ，所构造的曲面称为插值曲面。该部分将简单介绍散乱数据插值 所涉及的基本知识，并且对基本的散乱数据插值曲面的构造原理及基本方法、过 程进行概述。 第三章主要介绍了已有的几种超限插值方法。 本章从插值曲面精度上分为三节，第一节介绍了三种构造三次精度插值曲面 的方法。分别为：文献中介绍的点边插值法、文献1 中介绍的边边插值法和文 献删中介绍的移动三角形插值法。 第二节介绍了三种构造四次精度插值曲面的方法，分别为：文献中介绍的 边边四次精度方法、文献中介绍的四算子插值方法和文献1 中提出的对四算子 插值方法改进的算法。 第三节介绍了两种构造五次精度插值曲面的方法，分别为：文献“”中提出的 布尔和插值算法和文献提出的基本曲面加附加曲面方法。 4 山东大学硕士学位论文 第四章研究了用六个参数构造二次多项式边界条件进行插值构造曲面的问 题。针对第三章中讲到的i p 如鲫【柚1 方法的缺点，提出了一种构造插值曲面的新 方法。新方法利用具有公共边的两个三角形区域的四个顶点值及外法向量来构造 一个二次曲面片，利用该二次曲面片求出两个三角形区域共用的边界曲线及其跨 界切矢量，同样可以求出另外两条边界曲线及其跨界切矢量：对于只属于一个三 角形区域的边界，我们可以只用该三角形区域的三个顶点的值及其外法向量求出 相应的二次曲面片。然后利用得到的边界条件进行边点插值，得到三角形曲面片。 最后用实例同其他方法所构造的插值曲面形状进行了比较。 在第五章做出结论，对上述插值方法给出了总体评价，展望以后的工作方向， 表达了在实践中推广的愿望。 山东大学硕士学位论文 第二章三角形区域上的超限插值曲面概述 在介绍超限插值曲面的构造方法之前，我们有必要先了解一些具有基础 性质与普遍意义的基本概念以及思路和研究方法。 2 1 基础知识 2 1 1 插值与逼近 给定一组有序点p ，( 工，y ，z ，) o = o ，1 ，2 ) ，这些点可以是从某个形状上测量 得到的，也可以是设计员给出的。要求构造一个曲面通过这些数据点，称为对这 些数据点进行插值( i m e r p o l 撕0 n ) ，所构造的曲面称为插值曲面。这些数据点若 原来位于某曲面上，则称该曲面为被插曲面。构造插值啦面所采用的数学方法称 为曲面插值法。插值法在c a g d 的实践中有着广泛的应用。 在某些情况下，测量所得或设计员给出的数据点本身就很粗糙，要求构造一 个曲面严格通过给定的一组数据点就没有什么意义。比较合理的提法是构造一个 曲面使之能在某种意义下最为接近给定的数据点，称之为对这些数据点进行逼近 ( a p p r o d m 撕o n ) ，所构造的曲面称为逼近曲面。这些数据点若原来位于某曲面 上，则称该曲面为被逼曲面。构造逼近曲面所采用的数学方法称为曲面逼近。 插值与逼近统称为拟合( f i 仕i n g ) 。在该篇论文中仅就插值问题进行讨论。 2 1 2 多项式基 在c a g d 中，参数形式已成为形状数学描述的标准形式。而参数曲线曲面方 程一般地又都写成为基表示式。这样就面临一个问题，应该选择怎样一类函数作 为基函数呢? 这仍然由形状数学描述要求所决定。人们首先注意到在各类函数 中，多项式函数能较好地满足要求。它表示形式简单，又无穷次可微，因而足够 光滑，且容易计算函数值及各阶导数值。采用多项式函数作为基函数即多项式基， 就得到相应的多项式曲线曲面。 捍次多项式的全体构成一次多项式空间。一次多项式空间中任一组月+ 1 个线 山东大学硕士学位论文 性无关的多项式都可以作为一组基，其中最简单的基是幂基。 幂( 又称单项式n 啪o m i a l ) 基：f ，= o ，1 ，刀是最简单的多项式基。相应 的参数多项式曲线方程为 n p = a 7 | 曲 其中吩= ( 弓，乃，乃) 为系数矢量，f 是参数。同理可推广到曲面，在后面的章节中 会进行详细讲解。 一次多项式空间中有无穷多组基，不同组基之间仅仅相差一个线性变换。同 一条参数多项式曲线或一张参数多项式曲面片可以采用不同的基表示，由此决定 了它们具有不同的性质，因而具有不同的优缺点。这就提出了一个问题，应该选 择怎样的多项式基才最适合c a g d 关于形状数学描述的要求。在后面的章节中 会看到，为了计算方便选择了另外一种多项式基，使表达及计算大大简化了。 2 1 3 三边曲面片 近年来，三角形网格上曲面片的构造受到越来越多的重视。三边曲面片“。1 受到较多注意的原因在于它适应不规则与散乱数据几何造型和避免出现退化的 需要，及适合于有限元分析中广泛应用的三边形元素的需要。由于它具有构造复 杂形状的潜力，在将来会获得较广泛的应用。下面的讨论都是建立在三边形网格 的基础上的。先来看一下三边曲面片的基本知识。 1 三边曲面片的表示 首先遇到的问题是三角域内一点怎样表示，显然它只应与三顶点的相对位置 有关，直角坐标在这里不再适用。下面介绍三角形内一点的面积坐标与重心坐标。 平面内一个矢量可以表示为另外两个线性无关的矢量的线性组合。于是，对 于三角形动c 内一点p ( 如图2 1 ) ，就有 p c = ”( 口一c ) + v ( 6 一d p = 蝴+ 1 ，6 + ( 1 一一1 ，) c 于是可给出 p = 蝴+ 他+ 1 j c 山东大学硕士学位论文 其中”+ v + w = l 。，v ，w 就是p 点在三角形西c 内关于口，6 ，c 三顶点的 重心坐标。又分别可看作配置在该三点的重量，p 就是它们的重心。 图2 一l 重心坐标定义 当p 点在平行于幻边的直线上移动时，它的坐标不变。类似地，当p 点 分别沿边与曲边移动时，分别有v 坐标与w 坐标不变。 重心坐标与面积坐标是一致的，即有 三角形矽c 的面积 _ 三角形p 的面积 三葡历丽丽三前历面丽 三角形脚的面积 w 2 三葡磊功丽 逆时针旋转为负。若口= 陋，口，】，6 = 【6 ，6 y 】，c = 【c ，。，】，则 涧呜褂；i 假设给定三维空间不共线三点n ，p 2 ，扔，则由下式表示的p 点 恒位于由p l ，p 2 ，儿三点张成的平面内。这里既可以把，y ，i j 解释为p 点相对于p l ，p 2 ，儿三点的重心坐标。也可以把“，v ，解释为在二维域平面 山东大学硕士学位论文 示我们仅做简要介绍，多项式陆面片我们在下一小节将进行详细介绍。 使一个基函数联系一个控制顶点，一张一次三边贝齐尔曲面片必须由构成三 角阵列的伽+ 1 ) 印+ 2 ) ，2 个控制顶点6 “j ( f + ，+ 膏= 一) o ，_ ，七o ) 定义。因此，立 即可写出曲面片的方程 hh p ，忉= 吒肚曰0 以，v ，w ) o ，v w l( 2 2 ) _ 0 o 、 _ ：j w 干 图2 - 2 三次三边贝齐尔曲面片 按下标顺序用直线连接控制顶点就形成了曲面的控制网格，它由三角形组 成，网梅顶点与三角域的节点一一对应。图2 - 2 是三次三边贝齐尔曲面片的一个 例子。 2 三边曲面片的连续性 工业产品形状的数学描述重在解决曲面的数学描述。由于实际形状的复杂 性，用单一曲面片往往是难以实现的，必须采用组合曲面。在许多场合下，要求 曲面片间达到某种程度的光滑连接。曲面间连接的光滑度的度量方法有两种，一 是参数连续性，一是几何连续性啪。曲面问题远比衄线问题复杂，首先在拓 扑结构上增加了复杂性，除了由张量积曲面片来组合曲面，更为常用的是曲面由 定义在非矩形网格上的离散的矩形曲面片拼接而成，或者由定义在三角域上的三 角形曲面片拼接而成。而正是由于前面提到的三边曲面片的优势，非常适合用三 边曲面片来拼合构造复杂的曲面。因此，三角曲面片的连续性问题就成为非常重 要的一个问题。 先来讨论三边曲面片的参数连续性。若两相邻曲面片具有公共边界，且次 数相同，两曲面片此时具有位置连续性，或是c o 的，即具有零阶参数连续性。 定义：当且仅当两曲面沿它们的公共连接线处处具有直到一阶的连续偏导 矢，则称它们沿该连接线具有n 阶参数连续性( 即c ”连续性) 或是c ”的。 9 山东大学硕士学位论文 图2 - 3c 1 连续的例子 对应于两相邻多项式三角曲面片沿公共边界c 1 连续在这里可以采用要求 沿公共边界方向导矢连续。 同样，可以得到两相邻三边贝齐尔曲面片跨公共边界c 1 连续的充要条件： 若两相邻三边贝齐尔曲面片以公共控制多边形的边为公共边的所有对网格三边 形都是参数平面内它们那对域三角形的仿射像，如图2 3 所示，则它们沿该公共 边界方向导矢是c 1 连续的，称它们沿该公共边界是c 1 连续的。二阶与高阶参数 连续性分别与邻接公共控制多边形的两排与多排网格三边形有关。 同样的，来看一下曲面片的几何连续性。两参数曲面的零阶几何连续性即g o 连续性是与c o 连续性一致的。两参数曲面的g 1 连续性又称为切平面连续性，其 定义为：两曲面沿它们的公共连接线具有g 1 连续性或是g 1 的，当且仅当它们沿 该公共连接线处处具有公共的切平面或公共的曲面法线。g 2 连续性又称曲率连 续性。g 2 连续性要求沿公共连接线处处在所有方向都具有公共的法曲率。因此 有定义：两曲面沿它们的公共连接线具有g 2 连续性或是g 2 的，当且仅当它们沿 该公共连接线处处具有公共切平面外，又具有公共的主曲率，及在两个主曲率不 相等时具有公共的主方向。 几何连续性是对参数连续性的松弛，也是对参数化的松弛，但不是对光滑度 的松弛。推广到一 2 的g ”连续性，此时几何量少了或根本用不上了，难以看出 g ”连续性有什么实际意义。 1 0 山东大学硕士学位论文 2 2 超限插值曲面的构造 设空间给定了一个散乱分布的数据点只= ( 而，咒，曩) ，f _ 1 2 ，栉，目标是构 造一张分片定义的多项式曲面f o ，y ) ，满足f ( x ，y ，) = 只，扛l ，2 ，丹。目前根 据给定的散乱数据点构造插值眭面的一般过程如下： 。 1 ) 对给定的散乱数据点进行三角剖分，并作必要的修正； 2 ) 计算三角网格边界条件，构造初始三角曲面； 3 ) 构造整体连续的散乱数据插值曲面。 首先，三角剖分( 或称三角化) 是实现散乱数据插值必要的前置处理。三 角剖分可分为对三维散乱数据投影域的剖分和在空间直接剖分两种类型。散乱数 据的投影域包括平面域和球面域。直接三角剖分方法研究如何直接将三维散乱数 据点在空间中连接成一个最优的三角网格。本课题将采用对散乱数据投影域的剖 分。由于该部分不是重点，本篇论文不进行详细介绍。 在三角形上构造的曲面片表达形式常用的是三角b e m s t e i n - b 6 五日曲面嘲参 数表达式或多项式表达式。下面讨论两种表达方式下进行散乱数据点的插值的基 本原理和过程。 1 g 1 连续插值曲面 构造散乱数据插值曲面是指散乱数据点经三角剖分后，在网格的每个三角形 上构造插值于三顶点的三角b b 曲面片，并使各曲面片间满足一定的连续性要 求( 在工程中常要求达到g 1 连续) ，插值于给定散乱数据点的曲面有无穷多个。 在三角网格上构造g 1 连续散乱数据插值曲面至少需采用四次三角b b 曲面 片，并用反例说明了三次三角b b 曲面片并不总能构造出g 1 连续的散乱数据插 值曲面。用三角b b 曲面片构造插值曲面的原理和步骤如下。 1 ) 原理 用四次三角b b 曲面片构造散乱数据插值曲面的原理是：根据边界条件在 三角网格上构造初次的三次三角b - b 曲面片；调整与各顶点相邻的控制顶点， 使各顶点处满足g 1 拼接的相容性要求：将曲面片由三次升阶到四次；为了给曲 山东大学硕士学位论文 面片沿边界拼接提供足够的自由度，对曲面片进行c t 分割，将个曲面片分 割为三个子曲面片1 ；调整各子曲面片的控制顶点，保证各子曲面片间g 1 连续。 2 ) 算法步骤 构造g 1 连续散乱数据插值曲面的算法如下： 在具有边界条件的子三角网格上构造初始三次三角b b 曲面片； 根据顶点相容性调整方法及计算公式，调整与各顶点相邻的控制顶点， 使各项点处满足连续性相容条件； 曲面片由三次升阶到四次； 对曲面片进行c t 分割，将一个曲面片分割成为三个子曲面片； 调整各子曲面片的控制顶点，保证其父曲面片沿边界g 1 连续； 调整该三个子面片的控制顶点，使相互间沿边界达到g 1 连续。 2 散乱数据点的多项式插值曲面 构造散乱数据点的多项式插值曲面的基本做法是：把点( 五，m ) ，f - l ，2 ，n 在叫平面上根据某种标准做三角形划分，在每个三角形丁上构造多项式曲面片 弓似力。所有曲面片拼合起来形成摧体曲面f “力。 图2 - 4 设三角形r 的三顶点坐标是毋= ( 而，弘) ，= f ，七，如图2 4 ，其面积为 三边中点处的一阶外法向导数记为( 川， 1 ) ，而面积坐标心，以) 则 定义如下： l l 缸，n 2 u y k x k y f + t y i y k + 心k x j 、巩| 2 s 山东大学硕士学位论文 上( 五力= 【y f x ，儿+ o ，i n 如+ ( 为一以) y 】，2 s ( 2 3 ) 囔缸，n = u i y j x j y t + o i yj + q | 一x 0 矾 2 s 下面讨论如何构造不同次数的多项式曲面。 1 1 构造线形插值曲面 ， 给定的插值条件是三个顶点处的函数值，f ，和疋。则三角形上线形插值曲 面是： 日( 五y ) = 三i ( t 力e + 三( y ) 乃+ 三i ( ) ，) 最 2 1 构造二次多项式曲面 给定的插值条件是：三个顶点处的函数值e ，f ，和以，三边中点处的函数值 e ，乃j 和匠，i 三角形上的二次多项式插值曲面乃o ，j ，) 是 昂( 为y ) = 4 l x 2 + 口2 】y + 口3 _ ) ，2 + 口4 z + 口5 y + 口6 其中口i ，4 2 ，d 3 ，是待定系数。在面积坐标下，f ( x ，力可写成如下形式 酏力i ，淼名舞麓黧篓一瓴腿缸仁4 ， 工，“) ，弘，( x ，力4 ，+ 厶( x ，力k y ) 以，i + 0 ( z ，y k o ，_ ) ，) a 肚 其中a f 。i = 4 f q f t f j ，a “= 4 f h f k f l ，a 进= 4 f 律一f i f k 。 构造的曲面f ，y ) 是c o 连续的。 3 1 构造三次多项式曲面 要构造连续的曲面，需要1 2 个插值条件。这些条件是；各项点处给出函 数值巧和一阶偏导数值( e ) i 和( q ) ，= f ，工j | ，在三边中点处( ，y p ) ， ( ，) ，( 勺，蛳) 的一阶法向导数值a f ( ，巧 ) 锄，a f ( ，y 船) ，锄，和 a f ( 勺，巧) 锄 。三次曲面片 日( 艺y ) = 4 1 x 3 + 口2 x 2 y + 码习，2 + 口4 y 3 + 4 5 x 2 + 口6 】吵+ 口7 y 2 + d 8 x + 口9 y + 口1 0 在面积坐标下可写成如下一般形式 山东大学硕士学位论文 而似力= 4 霉+ 4 ：譬+ 坞4 + 以霹0 + 4 置k + 以厶巧+ 4 巧厶 + 4 厶群+ 4 上，+ 4 0 厶工，上骨 如果要求露( 工，y ) 满足各顶点处给定的函数值巧和一阶偏导数值胪：) j 和( e ) ， ，= f ，七，则日y ) 可写成 昂( x ，y ) = 【( 3 2 ，) 只+ ( x 一一) ( c ) ，+ ( y j ，) ( ) ，】葺 + 【( 3 2 0 巧+ o 一0 ) ( 只) + ( y y ，) ( 0 ) ，】巧 ( 2 5 ) + ( 3 2 4 ) 五+ o 一) ( 只) + 0 一儿) ( ) t 】瑶+ 4 0 厶三，k 如果增加一个插值条件，比如边弓最中点处的法向导数a 品( z 母， ，毋) 锄，则如 可被唯一确定。 其余次数的多项式曲面可通过类似于上述的过程进行构造。通常在实际的应 用中能够给出的插值条件只有位置的信息，即只= ( 薯，只，e ) ，f _ l ，2 ，胛，也就 是只有散乱点的位置和函数值。而如果不细分三角形，则在三角形上构造c 1 多 项式曲面需给出2 1 个插值条件( 三角形顶点处的函数值巧、一阶偏导数值( e ) ， 和( 巧) ，、二阶混合偏导数值( e ) ，、( 嘭) ，和( 巧) ，= f ，| | ，三边中点处的外法 向a f ( ，y 肛) 劫，a f ( ，y 材) 锄和a f ( 勺，均) 钆) ，这就需要找到解决的方 法以得到三角形顶点处的偏导数及其他条件，从而构造出c 1 连续的插值盐面。 这也正是下面章节中所要讨论的中心问题。 1 4 山东大学硕士学位论文 第三章三角形区域上的超限插值 在本章将根据插值曲面精度来讨论已有的几种三角形区域上的超限插值的 方法。 3 1 三次精度插值方法 本节介绍的三种方法的插值精度均为三次多项式。 3 1 1 点边插值方法 圈3 - l 交点吼( 卢l ，2 3 ) 点边法便用三个擂值算于的组合构造三角曲向片，买中每个算于满足一个 点及其对边上的插值条件。方法简述如下。对于r 上的任一点叮= ( 厶，厶，厶) ，设 毋= ( 夏，歹；) 是吁和口的连线与边墨的交点，f = l ，2 3 ，从q 到毋的单位向量记为 f i f = 1 ，2 ，3 ，如图3 - l 所示。由直接计算得吼2 墨笔芋，吼= 刍詈等和 仍2 等等。 在点哆和吼处给定的边界函数值和沿着方向f i 的跨界导数值分别是f ( q ) 和 垦掣，f ( 吼) 和掣，f ：1 ，2 ，3 。设q 到口和吼的距离分别是f 和吐。对q 和 o t o t 。 玑处给定的边界函数值和沿着方向t 的跨界导数值插值的三次h 【i l i t e 曲线 山东大学硕士学位论文 ，( f ) 定义如下 哪m c 扣咖啊酗掣+ 岛印删十蜀印掣( 3 - ， 其中 ( f ) = 1 3 f 2 + 2 一 啊( f ) = 3 f 2 2 ，3 ， g o o ) = f 一2 f 2 + f 3 ， g l ( r ) = f 3 一f