（机械工程专业论文）移动最小二乘散点曲线曲面拟合与插值的研究.pdf

浙江大学硕士学位论文 摘要 摘要 逆向工程是c a d c a m 领域的重要研究内容之一，而曲面重构又是逆向工程的 关键技术。数十年来，曲面重构的研究方法获得了很大的发展，相关基础算法与 技术取得了不少成果。随着计算机技术和测量技术的发展，近十年来，散乱数据 的曲线、曲面重构技术受到关注。其中移动最小二乘法( m l s ) ，因其无需网格划 化、对散点适应性强、具备局部拟合或插值特点以及精度高等优点成为近年来的 研究热点。本论文重点计算研究了曲线与曲面的移动最小二乘法散点拟合和插值。 论文主要研究了当基函数取常数、线性基和平方基时的移动最小二乘法的曲 线与曲面的拟合和插值。针对散点模型，引入描述散乱程度的因子和紧支撑域大 小的影响系数，通过选择恰当的权函数，对均匀、轻度、中度和高度等不同程度 的散乱数据进行了拟合和插值，计算比较了各种情况下的拟合和插值精度。为减 少基于高次基函数的m l s 的计算量，且避免病态矩阵出现，进行了基函数的正交 变换研究。论文还重点研究了基于紧支撑奇异权函数的m l s 曲线插值和m l s 曲面 插值，并进行了如何在计算中消除奇异性的算法研究，获得了理想的曲线、曲面 插值精度。同时也对拟合和插值计算中在边界附近出现较大误差的问题进行了改 进处理。 论文通过大量算例成功地进行了移动最小二乘法的曲线、曲面拟合和插值， 并取得了很好的效果。表明m l s 方法具有对散点数据适应性强、精度高以及局部 性等特点，是一个在实际曲线、曲面重构中具有前景的有效方法。 关键词：移动最小二乘法，散点模型，曲线曲面拟合与插值，s c h m i d t 正 交化，曲面重构 浙江大学硕士学位论文a b s 仃a c t a b s t r a c t r e v e r s ee n g i n e e r i n g ( r e ) i si m p o n a n tr e s e a r c ha r e a si nc a d c a m s u r f a c e r e c o n s 缸u c t i o ni s 也ek e yp r o b l e l no fr e f o rs e v e r a ld e c a d e so fy e a r ，r e s e a rc _ hm e t h o d s o ns u m c er e c o n s 缸1 l c t i o nm a k ea 野e a ts t 印w i t hm ed e v e l o p m e n to fc o m p u t e r t e c l l l l 0 1 0 9 ya n dm e a s u r e m e n tt ec _ l l i l 0 1 0 9 y ，s c a t t e r e dp o i n tm e t l l o dh a sb e e ng ，e a n y i m p r o v e di 1 1r e c e n ty e a r s m o v i n gl e a s ts q u a r e ( m l s ) m e t h o d ，d u et ot h ea d v a l l t a g e s o fm e s h l e s s ，1 0 c a lf i t t i n g ( o ri n t 即o l a t i o n ) a n dh i g ha c c u r a c yc h a r a c t e r s ，i ss u i t a b l ef b r s c a t t e r e dp o i n td a t 巩a n dh a sb e c o m ea ni n c r e a s i n gh o ts l l b i e c to fr e s e a r c h 1 1 1t h i sp a p e r ，m o v i n gl e a s ts q u a r e ( m l s ) m e t h o df o rt h ec a s e so fl i l l e a ra n d q u a d r i cb a s i s 缸c t i o n sa r eg 七i l d i e da n da ：p p l i e dt oc u r v e ( o rs u r f a c 曲f i t t e d ( o r i n t e r p o l a t i o n ) b a s e do ns c a t t e i e dp o i n t sd a t a i nm i sp a p e r ，t h e “s c a t t e r e df a c t o r w a si 1 1 n o d u c e dt od e s 矾b em es c a t t e r e dp o i n t m o d e l f o rv a r i o u sc h o i c eo fs c a t t e r e df a c t o r 、s u p p o r t e dd o m a i ns i z e 、c o m p a c t l v s u l ) p o r t e dw e i 曲t e d 如n c t i o na n db a s i s 如n c t i o n ，w em a i n l vs t l l d i e dm e i ri m p a c to n c o m p u t a t i o n a la c c u r a c yi n 伽l r v e ( o rs 1 1 r f a c e ) 6 t t i n g ( o ri n t e r p o l a t i o 曲i na d m t i o n o n h o g o n a lp r o c e s so nb a s i sn m c t i o n sw a su s e di no r d e rt oa v o i dt h ei u c o n d i t i o n e d ma ：嘶xp r o b l e ma n ds a v ec o m p u t a t i o n a lt i m e m l sm e m o dn o to n l vc a nb ea p p l i e df b r 廿1 ep 1 1 】巾o s eo fc u r v e ( o rs u r f h c e ) f i t t i ng b u ta l s oc u r v e ( o rs u f f a c e ) i n t e r p 0 1 a t i o n 、= h e nc o m p a c t l ys u p p o r t e ds i n 霉舛1 a rw e i 妫t e d 缸n c t i o nw a su s e d t h ee f ! e i e 以v em e a s u i ch a sb e e na p p l i e dt oe l i m i n a t es i n g u l a r i t yi n m l si n t e r p o l a t i o n i i la d d i 廿o n t h eb a df i t t i l l go ri n t e r p o l a t i o na c 饥i r a c vn e a u rt h e b o u n d a r yw a si m p r o v e d 1 a n vn u l n e d c a le x a l n p l e so fc u e ( o rs u i f a c e ) f i t t i i l g ( o ri m e r p 0 1 a d o n ) w e r e g i v e ni nt h i sp a p e r t h en u m 缸c a lr e s u l t ss h o wt h a tm l si so fg o o da d a p ta ：b i h t yt o d i s t r i b u t i o n锄ds h a p eo fs c a 钍e r e dp o i n t sd a t a ，a n dt h ep r o p e n i e so fn e x i b l e a d i u s t a ：b i l i t yo np 猢e t e r ss uc _ ha sw e i 曲t 劬c t i o na n db a s i sf u n c t i o nw h ic _ hc o u l db e i m p r o v eh i 曲n u m e r i c a lp r e c i s i o na n ds m o o t h n e s si nt 1 1 ec o m p l e x 饥l i v e ( o rs u r f a c e ) m o d e l i n g i na d d i 缸o n ，i t sl o c a lf i t t i n go ri n t e r p o l a t i o ni sv e r yp o t e n t i a lc o m p a r e dw i t h t h eo m e rt o t a lm e t h o d 1 1 1aw o r d ，m l sm e m o di sap o t e n 缸a 1m e t l l o di nc u e ( o r s u r f l a c e ) 6 t t i n gf o ri n t e r p 0 1 a t i o n ) i nt l l e 向t u r e k e yw o r d s ： m o v i n gl e a s ts q u a r e ( m l s ) ，s c a t t e r e dp o i n tm o d e l ，s 删e 6 仕i n ga 1 1 di n t e 印o l a t i o n ，s u r f a c em o d e l i n g ，s u r f a c e r e c o n s t r u c t i o n 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 曲面造型技术发展历史 曲面造型是计算机辅助几何设计( c o m p u t e r - a i d e dg e o m e t r i cd e s i 蹲，c a g d ) 和计算机图形学( c o m p u t e rg r a p h i c s ，c g ) 研究的重要内容。其主要研究在计算 机图形图像系统中对曲线曲面的描述、显示、设计和分析。它起源于汽车、飞机、 船舶、叶轮等的外形放样工艺，由c o o n s 、b e z i e r 等大师于二十世纪六十年代奠 定其理论基础。如今经过四十余年的发展，曲面造型现在已形成了以有理b 样 条( r a t i o n a lb s p l i n e ，r b s ) 曲面参数化特征设计和隐式代数( h p l i c i t 灿g e b r a i c ) 曲面表示这两类方法为主体，以插值( n e r p o l a t i o n ) 、拟合( f i g ) 、逼近 ( a p p r o x i m a t i o n ) 这三种手段为骨架的几何理论体系瞳3 。 曲线曲面一般分为可以用数学方程式表示的规则曲线曲面和不能表示的非 规则曲线曲面。规则曲线曲面如圆锥截线、柱面、锥面等一般用二次函数或隐函 数表示，一般的工业产品或机械零件通常都是由这些线面组合而成；非规则曲线 曲面也称为自由曲线曲面，如汽车或飞机外壳、家用电器和艺术品等，简单的数 学描述难以表达其形状，因此如何建立其数学模型是曲面造型研究的核心内容和 难点。1 9 6 3 年美国波音飞机公司的f e r g u s o n p j 首次用参数矢量函数形式，构造了 f e 哪s o n 双三次曲面片，从此曲线曲面参数化成为形状数学描述的标准形式。这 种参数化形式不受坐标变换的影响，保持了曲线曲面的几何不变性。但f e r j 弭s o n 曲线中间形状不易控制。1 9 6 4 年美国麻省理工学院的c o o n s 【4 悯用四条边界曲线 围成的封闭曲线来定义一张曲面，c o o n s 曲面特点是插值，即构造的曲面满足给 定的边界条件，但这种方法也存在形状控制和连接问题。1 9 7 1 年法国雷诺公司的 b 6 z i e r 提出了用控制多边形定义b 6 z i e r 曲线曲面的方法【6 j ，这种方法不仅简单易 用，而且解决了曲线曲面凸包性、保型性等整体形状控制问题，将曲线曲面设计 向前推进了一大步，为曲面造型的进一步发展奠定了坚实的基础。b 6 z i e r 曲面不 通过给定点，是近似拟合曲面。但b 6 z i e r 曲线曲面也存在以下缺点：1 、缺少局 浙江大学硕士学位论文 第1 章绪论 部性，不能局部修改；2 、曲线特征多边形顶点越多，逼近效果越差；3 、不易表 示复杂曲面形状；4 、存在曲面片间的连接问题。1 9 7 2 年d eb o o r 和c o x 提出了b 样条的标准计算方澍7 】 8 。1 9 7 4 年美国通用汽车公司的g o r d o n 和融e s e n f e l d 将b 样条理论用于几何形状描述，提出了b 样条曲线曲面 9 】 1 0 】。这种方法继承了b 6 z i e r 的直观性和凸包性优点，克服了b 6 z i e r 方法的缺点，较成功地解决了局部控制和 连接问题，提高了拟合精度。但b 样条不能精确表示圆锥截线和初等解析曲面， 而产品设计中圆锥截线和初等解析曲面是常见的几何形状，这个缺陷不仅缩小了 b 样条曲线曲面使用范围，而且造成曲线曲面数学描述不统一，容易引起管理混 乱。1 9 7 5 年v s p m l e 发表了关于非均匀有理b 样条方法( n o n u n i f o n n e dr a t i o n a l b s p l i n e ，n u r b s ) 的博士论文【1 1 】，8 0 年代后期p i e g l 和t i l l e r 对n u r b s 进行了 深入研究，使其在理论和应用上趋于成剿1 2 1 8 】。n u i 也s 方法不仅继承b 样条的 优点，而且可以精确表示二次规则曲线曲面，具有影响曲线曲面形状的权因子， 使形状控制更易实现，并且计算稳定迅速。1 9 9 1 年国际标准化组织( i s o ) 颁布 了关于工业产品数据交换的s t e p 国际标准，将n i 瓜b s 方法作为定义工业产品 几何形状的唯一数学描述方法，从而使n l 7 i m s 方法成为监面造型技术发展趋势 中最重要的基础【1 9 】【2 0 】。 1 2 曲面造型技术现状及发展趋势 近十几年来，随着计算机技术和图形技术的进步，曲面造型技术也得到了迅 速发展，主要表现在研究领域的拓展和表示方法的创新。从研究领域上看，曲面 造型从传统的曲面表示、求交、拼接研究，拓展到曲面重构、变形、转换和等距 性等方面，表示方法也由传统的连续造型发展到离散造型。 曲面重构是曲面造型的核心，自由曲面重构是曲面重构研究的关键。特别是 随着激光测距扫描仪、医学成像仪、接触探测数字转换器和雷达地震探测仪等精 密测量仪器的出现，基于数据测量的离散型曲面重构技术在复杂几何体建模方面 得到了广泛的应用。其过程就是首先通过先进的三维数据获取技术，得到精度较 高的物体表面三维数据，再从这些均匀或散乱分布的离散数据点云来建立真实物 2 浙江大掌硕士学位论文 第1 章绪论 体数字模型。曲面重构技术涉及计算机、图形学、神经网络、计算数学、测量技 术和数控加工技术等众多学科和领域，是近年来国际学术界的一个重要研究课题， 并在理论和应用上都取得了巨大成功。已广泛应用于逆向工程( r e v e r s e e n g i n e 甜n g ) 中的产品设计和制造、物体识别、医学图像重现或人工骨骼定制、 地形地貌描述、地矿资源勘探、气象信息处理及科学研究等领域。 曲面变形是因应计算机动画业和实体造型业的发展需要而发展起来的，传统 的方法主要有扫掠法( s w e 印i 1 1 9 ) 、蒙皮法( s l ( i 强i n g ) 、旋转法、拉伸法以及通 过调整n u r b s 曲面控制顶点或权因子、利用层次细化模型在曲面特定点直接操 作等来改变形状。较新的方法有自由变形、基于弹性变形或热弹性力学物理模型 的变形法、基于求解约束的变形法、基于几何约束的变形法以及基于多面体对应 关系或基于图像形态学中的m i n k o w s k 和操作的曲面形状调配技术。 曲面转换要求同一张曲面可以在不同的数学形式间转换，这不仅具有理论意 义，也具有工业应用的现实意义。近几年来，国际图学界相应的研究工作主要集 中在：n u r b s 曲面用多项式曲面来逼近的算法及收敛性；b 6 z i c r 曲线曲面的隐 式化及反问题；c o n s u r f 飞机设计系统的b a i l 曲线向高维推广的各种形式比较 及相互转化；有弹b 6 z i e r 曲线曲面的降价逼近算法及误差估计；n u i m s 曲面在 三角域上的互相快速转换。 曲面等距性在计算机图形学和加工中有广泛的应用。一般而言，一条平面曲 线的等距曲线不再是有理曲线，这种情况超越了n u i 啦s 系统的使用范围，造成 软件设计的复杂性和计算的不稳定性。为解决这一问题，国际图学界提出了用简 单曲线逼近等距曲线的种种算法，但存在收敛性和控制问题。直到1 9 9 0 年f a r o u k i 首次找到p h 曲线。1 9 9 3 年浙江大学的吕伟利用复分析法、重新参数化和代数几 何技术，完整地给出了0 r 多项式和有理参数曲线的一般形式，彻底解决了平面 曲线的等距线的有理化问题 1 9 】 2 0 1 。 1 3 曲面重构主要方法综述 对于具有复杂曲面的产品，传统方法通常是利用三座标测量机对模型或已有 浙江大学硕士学位论文 第l 章绪论 产品进行测量，根据得到的数据加工制造出成品。但是由于测量误差的不可避免 和加工能力的局限性，因此往往生成曲面质量不高且生产效率低下。随着 c a d c a m 技术的目臻成熟和造型技术的日益提高，现在通常采用测量和造型相 结合的形式，运用适当的曲面造型技术对测量数据进行处理，建立产品曲面的数 学模型，进而实现产品的快速设计和制造。 根据应用场合不同，曲面重构通过插值、拟合或逼近三种手段生成曲面。插 值指生成的曲线曲面通过给定型值点，拟合或逼近一般不通过型值点，而是满足 一定的条件使曲线曲面逼近数据点云或给定函数。插值技术在工程实践和科学实 验中有着广泛而又十分重要的应用。例如在图像重建或放大过程中为避免图像失 真或扭曲而增加的插值补点，试验数据分析，地理信息数据处理，社会经济现象 的统计分析等方面，插值技术的应用是不可或缺的。拟合通常用在需要考虑测量 和加工误差，或对形状要求比精度要求高如日用品的外观设计等场合。按曲面是 否能部分修改来分，曲面重构方法分为整体插值( 拟合) 和局部插值( 拟合) 两 种。整体插值( 拟合) 方法在构造曲面时需要用到全部数据，增加、删除或修改 一个点，曲面就会整体改变，相应地曲面数据必须重新计算，不仅不能对曲面进 行局部修改调整，而且大大增加计算工作量。并且整体插值一般需要求系数是高 阶满阵的线形方程组，容易造成求解困难或不稳定。局部插值( 拟合) 避免了这 些缺陷，删除、增加或修改数据点时，只需修改此数据点附近局部区域即可。在 数据量较大时，即便要求解线性系统，由于其系数矩阵一般呈带状，所以不会造 成条件数过大出现求解困难。局部插值的这些优点使其在实际应用中相较整体插 值( 拟合) 更为常用【2 1 | 。 曲面重构的数据源通常是物理量测量数据、试验结果或科学计算结果。采样 方式不同，得到的数据点云类型也不同。采用三座标测量机得到的数据通常是均 匀分布的数据点云，激光测距扫描仪得到的数据通常是随机分布的散乱数据点云， 医学成像仪得到的是二维轮廓线集等。曲面重构就是基于这些数据点云构造曲面， 使目标曲面或通过或逼近这些数据点云。显然，均匀分布数据在模拟曲率变化较 为平坦的曲面时具有优势，不仅精度可以保证，而且可以节约计算时间。但对于 4 浙江大学硕士学位论文 第1 章绪论 曲率变化较为剧烈的曲面，则需要在变化剧烈局部密集采样，而在较平坦部分采 样可以稀疏，因此，散乱分布的数据点云更能准确反映复杂曲面的细节形状。 迄今为止，自由曲线曲面重构方法已有很多，按其表示方法不同，主要有： b 样条曲面 作为矩形域参数曲面的代表，b 样条具有表达自由曲面形状的强大功能。主 要做法是在矩形定义区域内，选择基本反映曲面形状的一些散乱数据点生成一个 初始基曲面，然后将数据点按最小距离条件映射到初始基曲面上，将影射点对应 的参数值赋予相应的数据点，建立b 样条曲面方程，b 样条基函数通过d e b o o r - c o x 递推公式得到。利用最小二乘法反求得到控制顶点，进而得到b 样条 曲面，再以此曲面为初始基曲面，重复迭代过程，直到满足迭代条件，生成最终 b 样条曲面。初始基曲面可以是双c o o n s 曲面、s h 印a r d 曲面或b 样条曲面。b 样条曲面插值因为要根据给定数据点反求控制顶点，失去了b 样条局部插值和保 凸性的优点，因此使得最终曲面既不易修改也可能与要求的曲面形状凸性不一致 2 2 彩】。另外，由于b 样条控制多边形边数对曲面插值精度影响较大的特点，b 样 条在处理大规模数据时必须生成多个曲面片，这也存在曲面片的连接问题。 n u r b s 曲面 和b 样条相同，m 瓜b s 也用于矩形域场合，并且具有和b 样条相同的性质。 但是n u i 心s 比b 样条增加了权因子，因此曲线灵活性更大，效率和简洁度更高， 具有在形状定义方面的强大功能和在设计方面的巨大潜在灵活性。8 0 年代后期 p i e 西和t i l l e r 对n u r b s 进行了深入研究，提出用调整控制点与改变权因子的方 法进行n u i 国s 曲面插值【2 6 】【2 7 】【2 8 】，i nk y up a r k 等提出先根据四边形网格和测量数 据点进行插值，然后对插值点进行拟合获得n u i 啦s 曲面。该方法计算量小，1 旦 是所得曲面的精度很难控制，因为其所拟合的数据是插值数据，而非直接拟合测 量数据，但是这种曲面能精确表示解析实体和自由曲面。 三角b e z i e r 曲面 三角b e z i e r 曲面插值法可以处理非规则域散乱数据。参数曲面通常首先利用 d e l a 吼a y 三角化法、网格前沿法或h o p p e 微切平面法建立离散数据的三角形网格， 浙江大学硕士学位论文第1 章绪论 接着用b e z i e r 曲面片分片插值三角形网格，得到具有一定参数连续性或几何连续 性的拼接曲面。 其优点在于三角形曲面在表现形状方面最为灵活，能构造各种 复杂的形状。但三角b e z i e r 曲面模型不符合产品形状描述标准，并且它与其它 c a d c a m 的通信困难2 9 3 们。 径向基函数插值 径向基函数插值法采用径向基函数线性组合的方式得到插值曲面函数。常用 的径向基函数有高斯( g a u s s ) 函数、多二次( m u l t i q u 枷c ) 函数和薄板样条( t h i n p l a t es p l i n e ) 函数。径向基函数插值法属于整体插值，不能局部修改。当数据量不 大时插值较准确，数据量相对较大时则会出现计算不稳定、计算耗时的情况 2 i 】 3 1 】。 后来发展的紧支撑径向基函数可以实现局部插值。 s h e p a r d 方法 s h 印a r d 方法【2 1 【3 2 】【3 3 1 以距离的倒数为权的方式生成s h e p a r d 插值曲面，这种 方法计算简单，插值灵活，修改方便，易于应用。但是s h 印砌方法是整体插值， 增加或删除数据点影响整个曲面，不能局部修改。另外曲面光顺度低，在插值点 附近有平台现象。f 啪k e 和n i e l s o n 对s h 印莉方法进行了修正，提出了 m q s ( m o d i 6 e dq l u a d r a d i cs h e p a r d sm e t l l o d ) 方法，但由于计算量大，通常用于小 规模散乱点插值场合，并且边界处效果不理想。 最小二乘法 考虑到已知散乱数据点的测量和实验误差时，采用插值方法生成曲线曲面就 显得既不妥当也不必要。此时拟合方法就更为适用。最小二乘法作为一个逼近原 则常用于曲线曲面拟合，通过使散乱数据点与生成的曲线曲面误差的平方和最小 得到一个线性方程组，解此方程组便得到拟合曲线曲面。这种方法的缺陷是整体 拟合，不能局部修改，拟合选用的多项式次数一般不少于数据点的数目，次数太 少则精度不够，次数过多容易产生过拟合，造成求解困难，因此适用于小规模散 乱数据。对于复杂形状或数据量较大，通常需要分段拟合。 t a y l o r 方法 t a y l o r 方法通常先根据给定数据点分布状况，将矩形定义区域作适当的网格 浙江大学硕士学位论文 第1 章绪论 化。在任意一个网格点最邻近处取大于或等于6 个的数据点，曲面在网格点附近 的微小区域内可以近似看作二次曲面。将数据点的数值在网格点处作t a y l o r 展开， 得到包含最少6 个方程的矛盾方程组，用最小二乘法解方程组，从而确定拟合函 数f ( x ，y ) 在每个网格点处的位置信息、斜率信息和扭曲信息。然后在每个网格 点周围的微小矩形片上，利用上一步得到的矩形四个角点的几何信息构造双三次 多项式曲面片。这些双三次曲面片之间是c 1 连续的，这样便得到了整个区域上 的拟合曲面。t a y l o r 方法的逼近精度取决于曲面的多项式次数，次数越高，则精 度越好，但精度提高的同时也带来了计算量的增大【3 2 。 移动最小二乘法 移动最小二乘法( m o v i n g l e 2 l s ts q u a r e s ，m l s ) ，8 0 年代初由p l a n c a s t e r 和 k s a l k a u s k a s 比较系统地提出 3 4 ，最先应用于曲线与曲面的拟合。近十年来，被 计算力学研究者成功地用于求解偏微分方程的新一代数值方法“无网格方法【3 9 中。m l s 方法对最小二乘法作了较大的改进，使生成的曲面更光滑，精度更高。 其特点是不需对拟合域进行划分，只需散点模型。m l s 还引入了具有紧支撑性质 的权函数，使函数值只受其附近节点的影响，这使其有能力处理复杂形状曲面的 重构，并可对曲面进行局部修改。此外通过改变m l s 中的权函数和基函数可以 控制拟合和插值曲线与曲面的光滑度和精度。权函数在整个区域取常数，就是普 通的最小二乘法。因此移动最小二乘法是最小二乘法更一般性的推广。 另外，随着交叉学科的出现，许多力学、物理、数学等领域中的科学方法被 引入到曲面造型方法中，如基于力密度曲面造型、基于物理模型优化曲面造型、 基于偏微分方程曲面造型和小波曲面造型等。 1 4 课题的提出及研究意义 在人们日益注重产品外在观感、求新求异和追求个性化舒适化的现代社会， 产品仅仅满足使用功能远远不够，产品外在是否美观新颖、使用时是否感觉舒适 往往决定了消费者的最终消费欲望。那些包含有自由曲面的流线型产品( 如摩托 车外壳、汽车车身和鼠标壳等日用产品) 因其具有外观漂亮、造型别致新颖、更 浙江大学硕士学位论文第1 章绪论 符合人机工程学和体现人机关怀等诸多优点通常更受消费者青睐。另一方面，在 一些对机械产品或零件的某些数学特征有特殊要求的高精尖科技领域，有许多零 件外形复杂，如飞机外壳、动车车头、叶片等，其型面必须严格按照要求进行设 计和制造，才能保证产品满足较高的使用要求，具有较高的动力性和经济性。因 此随着市场对产品个性化和高性能需求的增长，产品更新换代的速度必然加快， 复杂曲面产品有广泛的应用前景，其重要性也越来越突出。 随着计算机技术、网络技术、造型技术和现代制造技术的日益进步，计算机 业、图形业和制造业逐渐结合为一体，生产集成化和网络化的步伐日益加快， c a d c a m 技术也日臻成熟。复杂曲面产品生产过程中，曲面造型已经是必不可 少的重要组成部分，并且贯穿于产品设计及优化、模具制作及数控加工等生产环 节，曲面造型生成的曲面不仅为后续环节提供信息和数学模型支持，而且曲面质 量如精度、光滑度或光顺度等指标往往起着关键作用，其重要性甚至决定了产品 性能和最终决策。另外随着计算机图形显示越来越要求具有真实性、交互性和实 时性的特点，如何快速逼真地对曲面进行重构和实现人机交互功能，越来越具有 理论研究价值和实际意义。现有的曲面生成方法存在诸多如曲面精度低、不能进 行局部修改、相邻曲面片连接效果差、对取样点的选取有网格限制等缺陷和限制， 因此对基于散乱数据的离散型曲面重构技术和基础算法进行深入研究，避免产生 以上缺陷，提高重构曲面的生成质量及曲面生成速度，提高产品质量，在要求产 品个性化和产品结构功能趋于复杂化的现代社会，符合现代工业精细化个性化的 要求，对于加快我国产品创新设计的发展步伐，增强产品设计与制造中的高新技 术含量，提升民用和国防产品快速设计和制造水平，提高企业创新能力和市场竞 争力，提高科学研究水平，更具有实际意义和经济价值。 基于散乱数据的自由曲面重构技术不仅被用于以追求美观和特殊功能为目 的的个性化产品设计中，也被广泛应用于对产品精度要求很高的航空航天领域、 军事装备领域和医疗器械等领域。此外，曲面重构技术的提高也极大拓宽其应用 范围，如地形地貌、矿藏资源分布的描述，山川、动物等自然景物的模拟，人体 内部器官、骨骼的三维重现和定制，化学分子模型构造，气象信息分析，物体识 浙江大学硕士学位论文 第1 章绪论 别，科学计算中的应力、应变、速度、温度场等物理量的直观显示等场合，所有 带有自由曲面的形体，其几何表示都离不开曲面重构技术。 1 5 本文的研究工作 散乱数据的移动最小二乘法，近年来出现了越来越多的研究，成为新的曲面 重构算法的研究热点。本论文重点计算研究了散乱数据的移动最小二乘法曲线曲 面拟合和插值，对如何提高计算精度提出了改进措施，并进行了算例计算分析。 本文首先对移动最小二乘法原理进行了归纳，推导了其相关公式。并解释了 m l s 中重要的紧支撑权函数，以及局部紧支撑域的生成算法。同时较详细地推导 了为了避免矩阵求逆计算费时或病态矩阵的基函数的正交化变换。然后重点计算 研究了曲线曲面的m l s 拟合和插值。针对散点模型，引入描述散点散乱程度的散 乱因子仅和描述节点紧支撑域大小的影响系数p ，计算研究了在均匀、轻度、中度 和高度等不同程度散乱数据模型下的曲线曲面的拟合和插值精度。并研究了权函 数和基函数的选取对计算精度的影响，着重研究了选取奇异权函数计算中奇异性 消除的技术处理以及m l s 插值精度。论文通过算例验证移动最小二乘法在散乱数 据的曲线曲面拟合和插值计算效果，尤其对曲面拟合和插值计算中在边界附近出 现较大误差的问题进行了改进后，获得了很好的精度。 1 6 本章小结 本章介绍了曲面造型的发展历史及其现状和发展趋势，简单介绍了曲面重构、 曲面变形、曲面转换和曲面等距性等研究领域内容，阅读文献资料后整理并介绍 了曲面重构的主要方法及其特点，最后说明了课题的研究内容和意义。 9 浙江大学硕士学位论文第2 章移动最小二乘法 第2 章移动最小二乘法 移动最小二乘法( m o v i n gl e a s ts q u a r c ，m l s ) ，8 0 年代初由p l a n c a s t e r 和 k s a l k a u s k a l s 比较系统地提出。3 4 j ，主要应用于曲线与曲面拟合。近1 0 余年来，被 计算力学研究者成功用于求解偏微分方程的新一代数值分析方法“无网格法”陋钔 中。m l s 方法基于紧支撑加权函数( 即函数值只在有限大小的封闭域中定义大于 零，而在域外则定义为零) 和多项式基函数，通过加权最小二乘法建立适合散点 ( s c a 戗e r e dp o i n t s ) 模型的拟合函数。这种方法对最小二乘法作了较大的改进，重构 的曲线和曲面具有更好精度和光滑度。其主要特点是：1 ) 不需对拟合和插值区 域进行划分，只需散点模型；2 ) 由于m l s 引入了紧支撑权函数，因此具有局部 拟合或插值特点。3 ) 改变基函数的多项式次数可以方便地控制曲线曲面拟合或 插值精度，改变权函数可以改变曲线曲面的光滑度。本章比较详细地描述了m l s 的概念和思想，并推导了相关公式。 2 1 移动最小二乘法原理 曲线与曲面拟合是寻找一个相对简单的函数来逼近一个数据集的过程。数据 集主要来源于物理量的测量数据、试验结果以及科学计算等，可能存在误差，可以 采用逼近的方法来拟合数据。通过按距离加权的方法计算近似函数值和给定数据 值的差的平方和来度量拟合的性能，这就是加权最小二乘法的基本思想。移动最 小二乘法的提出是对传统加权最小二乘方法更一般性的推广。并特别强调加权函 数的紧支撑性，因此具有局部数值分析的特点。 在拟合区域的一个局部子域上，假设需要拟合的函数f ( x ) 的近似函数p ( x ) 可 表达为 p ( x ) = b j ( x ) a j ( x ) = b t ( x ) a ( x ) ( 2 1 ) j 1 这里m 是基函数的项数，b j ( x ) 是基函数，a j ( x ) 是其系数。假定基函数b j ( x ) 是 浙江大学硕士学位论文一 兰! 童鳖塾垦! ：三墨婆 _ - _ - _ - _ _ - - _ _ _ - - _ _ - 一一 多项式，则具有如下形式： 一次多项式( 线性基) f b t = ( 1 ，x ) 1 一d 【b t = ( 1 ，ky ) 2 一d 二次多项式( 二次基) f b t = ( 1 ，x ，x 2 ) 1 一d b t = ( 1 ，x ，y ，x 2 ，珂，y 2 ) 2 一d 立方基 m t = ( 1 ，x jx 2 ，x 3 ) 1 一d l b t = ( 1 ，x jy j x 2 ，x y j y 2 ，x 3 ，x 2 弘珂2 ，y 3 ) 2 一d 由( 2 1 ) 式，利用加权最小二乘方法构成二次形式 这里n 是x 附近的影响节点数。w ( x x i ) 是节点x i 具有紧支撑性质的光滑连 续权函数，在x ；紧支撑域内部，w i = w ( x x i ) 0 ，在其边界和外部w i = 0 。毛是 x ；节点值。 式( 2 2 ) 对系数a ( x ) 求导得 芸= 2 b k ( x ，) w ( x 咱) 匹b 删a j ( x ) - 铲。 ( 2 3 ) l = 1l = 1 j ，k = 1 m 上式写成 a ( x ) a ( x ) = d ( x ) f( 2 4 ) 则 a ( x ) = a 一1 ( x ) d ( x ) f( 2 。s ) 其中 a = b t w ( x ) b( 2 6 ) d = b t w ( x )( 2 7 ) 其中 22 f q 一 对 毛 、 x 阢 m 匹阻 d x一 伍 w n缸 = 浙江大学硕士学位论文第2 章移动最小二乘法 b = 受 b m ( x 1 ) 1 山m 蚴i ( 2 8 ) b m ( x n ) j y v c x ，= 【w x 喜x 1 w ( x x 2 ) 三w 。x 呈x n ，】 c 2 9 ， w ( x ) ：i ?w ( x _ x 2 ? ? l ( 2 9 ) i： 。 ：i l o0 w ( x x n ) j 将( 2 5 ) 式代入( 2 1 ) 式，p ( x ) 可表达为： p ( x ) = b t a 一1 ( x ) d ( x ) f 特别地当基函数为常数基即b = 1 时， j = w ( x x i ) a 1 一f i 】2 弋1 j _ - 一 i = 1 j 对a 】求导得： 昙：2y w ( x x i ) 【a 1 一f i 】= o 瓦5z 乙w l x x i 儿a 1 叫i j = u 墨1w ( x x i ) f i 钆2 葛5 币j 万 所以 e ，、 墨1w ( x x i ) f i 就x ) - 锃羔等 ( 2 1 3 ) 实际上就是s h e p a r d 插值。 2 2 紧支撑权函数 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 移动最小二乘法曲线曲面拟合或插值计算中，权函数在其中具有非常重要的 作用。这里的权函数必须具有紧支撑性，使其有能力在处理大规模曲线与曲面拟 合时局部修改更容易。紧支撑权函数的选择应遵循几个原则： 每点的权函数值在紧支撑域内是大于零的正数，而在该点紧支撑域边界 和外部为零； 必须具有单位分解性； 1 2 浙江大学硕士学位论文 第2 章移动最小二乘法 权函数必须光滑连续可导； 在支撑域内愈远离该点，权值愈小，即保证权值与距离成反比关系。 立方样条函数和高斯函数是常见也是本论文采用的加权函数，详见第三、四 章和第五章。 此外，要特别提到的是如果权函数具有奇异性可导致过点的拟合，即插值。 在本论文第四章和第五章有具体的计算研究。 2 2 1 紧支撑域及生成算法 紧支撑权函数的引入导致移动最少二乘法具有局部拟合或插值性质，大大提 高了计算效率和规模。m l s 进行局部拟合或插值时，参与局部拟合或插值的相邻 节点对“计算点”的影响是由给定拟合或插值节点的局部紧支撑域决定。 m l s 近似计算之前先要生成每个节点的局部紧支撑域，一个节点的局部紧支 撑域形状可以是“圆”， “椭圆”或“矩形”等，如图2 1 所示。其中以“圆” 形式最常用。下面以“圆”紧支撑域为例，说明如何由离散节点模型自动形成各 节点的紧支撑域。该算法确定n 个节点的离散模型的紧支撑域。 紧支撑域形成算法： 1 ) 赋n 个节点的每一个“圆”紧支撑域的大小h ；= 0 ； 2 )以每个节点为原点，确定各象限与该点距离最近的点，其自动计算得到 的4 个象限内的距离分别为h 订、h i 。、h i 。、h i 。确定h i = m a x h mh 。：，h 渤h 。) ；保 证紧支撑域包含各个方向合适的节点，如图2 2 a 所示。 循环n 个节点； 3 ) 引入紧支撑域大小的影响系数p ，每个节点h i 乘系数p ，根据实际情况适 当扩大紧支撑域大小以提高拟合或插值精度，一般取p = 1 2 2 5 ，如图2 3 b 所 示。 上面算法称为四象限法则，每个节点支撑域的大小由该法则确定，详见专著 3 9 浙江大学硕士学位论文第2 章移动最小二乘法 图2 1 ：节点局部紧支撑域示意图町 ，一 队 | 厂 l y ， m 。 、 ( a ) 四象限法则示意图( b ) 扩大紧支撑域范围 图2 。2 节点的紧支撑域确定明 移动最小二乘法中，权函数紧支撑域大小选取要合适，既要保证所有离散节 点的支撑域形成对拟合或插值全域的覆盖，又要使域内需拟合或插值“计算点” 有足够多的邻近节点覆盖以保证精度和使a 矩阵可逆从而使m l s 算法可行。当选 取线性基函数时，曲线拟合影响节点不得小于2 个，曲面拟合影响节点不得少于 不在同直线上的3 个节点。 2 2 2 “计算点 的影响节点确定 拟合( 或插值) 域内任意一点往往同时处于好几个节点的支撑域相交部分。 如图2 3 所示，x 。，x 。，x 。，x 。，x 。的支撑域均覆盖住“计算点x ”，即计算“计算 点”时需考虑x ，一x 。五个节点的影响( 通常称为“计算点x 的影响节点) ，该 “计算点”的函数值及其导数值的计算皆需以此作为依据进行拟合或插值。图中 1 4 浙江大学硕士学位论文第2 章移动最小二乘法 x 。点的支撑域大小( 图2 3 中“虚线圆”) 不能盖住“计算点x ”，因此不参与 “计算点x ”的相关计算。 图2 3 “计算点x ”的影响节点图示阳鲫 2 3 基函数的正交化 多项式基函数的项数选取越多，( 2 。4 ) 中的矩阵a 阶数越高，其求逆就越费 时。随着“计算点”的增多，每点的a 矩阵不同，皆需求逆，计算量很大。因此， 为了避免方程中a 的求逆，减少计算量，可以利用s c h m i d t 正交化过程由基函数 b j ( x ) ，j = 1 ，m 构造正交形式的基函数q j ( x ) ，j = 1 ，m ，由此得到的a 矩阵将是 对角阵。基函数的正交化不仅避免了矩阵a 的求逆，而且可以避免可能出现的病 态矩阵。 s c h m id t 正交化过程 首先因为基函数系数a ( x ) 的x 和b ( x ) 中的x 意义不同，所以在正交化过程和 最小二乘法中区分两个x 非常必要。以下将a ( x ) 的x 记为又，b ( x ) 中的x 记为x 。 对给定的多项式基函数b j ( x ) ，j = 1 ，m ，存在正交形式的基函数q j ( x ，又) ，j = 1 ，m ，并且 q 1 ( x ，叉) = b 1 ( x ) j 一1 q j ( x j 一) = b j ( x ) 一仅j j ( 习q j ( 墨- ) ，j = 2 m ( 2 。1 4 ) l = 1 其中 浙江大学硕士学位论文笙! 主鳌垫墨尘三垩鳖 二一。 。r 扪一圣垒! ! ! 型皇匹兰立! ! ! 兰! ：型 (