（机械设计及理论专业论文）三维密集散乱数据的曲面重构.pdf

华中理工大学博士学位论文 摘要 反求工程是设计与加工复杂曲面零件的一种行之有效的手段，被广泛地应用于 航天、航空、造船、汽车和模具制造业。随着三维测量技术的迅速发展，密集散乱 数据云的曲面反求建模方法与技术成为反求工程中的“瓶颈”。为了解决“反求工程” 中的密集三维散乱数据曲面建模、仿真和数控加工等方面的问题，本文对相关的理 论和实践进行了深入的研究。 ， 潸先，根据曲面测量数据量庞大、密集、无序的特点，提出了基于八叉树空间 分割策略的曲面三维重建方法。在分析曲面数据云的测量方式和三维点群分布特点 的基础上，建立了恰当的数据结构表示散乱点群，从而解决了密集散乱数据云在曲 面三维重建过程中所遇到的数据处理速度慢的困难，提高了几何建模速度；在用空 间三角形网格逼近曲面密集三维散乱数据时，为了提高散乱点群曲面建模逼近精度， 提出了基于距离加权最小二乘空间插值算法以及基于万有引力定律的空间插值算 法。 其次，针对网格逼近散乱点精度问题，本文提出了空间三角形网格的两种整体 优化算法：刚性和柔性优化算法。两种优化算法在不改变网格的拓扑结构和三角片 数量的前提下，通过优化三角形网格顶点位置，提高了三角形网格整体逼近散乱点 精度。同时，本文还提出了三角形网格局部优化算法。三角形网格局部优化算法能 有效地使网格达到逼近精度的要求，同时减少三角片数量并剔除狭长三角片。 本文提出了在直边三角形网格模型上构造出曲边三角形网格模型的方法，并在 此基础上进一步构造一种显式b e z i e r 曲面，使曲面片之间达到近似的c 连续。 最后，本文提出了基于曲面散乱数据的三角形网格模型的凸、凹模数控编程方 法，实现了复杂曲面测量模型的凸、凹模数控加工。 本文以上述研究为基础，完成了面向数控加工的密集三维散乱点曲面重构系统 s d s c a d l 0 研制与开发工作。厂 关键词：三维散乱点，数据云，几何建模，反求工程，曲面逼近 华中理工大学博士学位论文 a b s t r a c t a sa ne m c i e n tw a yo fd e s i g n i n ga n dm a r t u f a c t u r i n gc o m p l i c a t e d s u r f a c e 1 e v e r s e e n g i n e e r i n g i sw i d e l yu s e di na v i a t i o n ，s h i p b u i l d i n g a u t o m o b i l ea n dm o u l di n d u s t r y w i t h t h ed e v e l o p m e n to fr a p i d3 dm e a s u r e m e n tt e c h n i q u e ，s u r f a c er e c o n s t r u c t i o nf r o md e n s e s c a t t e r e dp o i n t s ( d a t ac l o u d ) h a sb e c o m eab o t t l e n e c ko fr e v e r s ee n g i n e e r i n g f o c u s i n go n t h ep r o b l e mo f s u r f a c em o d e l i n g ，s i m u l a t i n ga n dn c m a c h i n i n go f c u r v e ds u r f a c ef r o m3 d d a t ac l o u d ，t h i st h e s i sh a ss t u d i e da n dd e v e l o p e dm e t h o d sf o rt o p o l o g i c a ld e s c r i p t i o no f3 d d a t ac l o u d ，g l o b a lm e s ho p t i m i z a t i o na n dc o r r e s p o n d i n gn c p r o g r a m m i n ga l g o r i t h m t od e a lw i t ht h e h u g e ，d e n s ea n du n e r g a n i z e d m e a s u r e dp o i n t s ，ag e o m e t r i c a l m o d e l i n g s t r u c t u r eb a s e do no c t r e eh a sb e e np r e s e n t e d b ya n a l y z i n gt h ed i s t r i b u t i o nw a y o ft h eu n o r g a n i z e d3 dd a t ac l o u do n t h es u r f a c e a ne f f i c i e n ta l g o r i t h mh a sb e e n d e v e l o p e d t oe s t a b l i s ht h eo c t r e et o p o l o g i c a ls t r u c t u r e ，w h i c hs i g n i f i c a n t l yi m p r o v e st h es p e e do ft h e p o s t - p r o c e s s i n g m o r e o v e r , w h i l ea p p r o x i m a t i n gd e n s e s c a t t e r e d p o i n t s o i lt h ec u r v e d s u r f a c ew i t hs p a t i a lt r i a n g u l a rm e s h e s ，an e wa l g o r i t h mb a s e do ns p a t i a l l e a s t s q u a r e s i n t e r p o l a t i o nw i t h t h ew e i g h to fd i s t a n c ea n dt h eg r a v i t a t i o nl a wh a sb e e ng i v e nt oi m p r o v e a c c u r a c y o fs u r f a c em o d e l i n g i no r d e r t o i m p r o v e t h e a c c u r a c y o f a p p r o x i m a t i o nm e s h ，t w og l o b a l m e s h o p t i m i z a t i o nm e t h o d s ：r i g i da n df l e x i b l ea p p r o a c h e sh a v eb e e np r e s e n t e d b yo p t i m i z i n g t h ep o s i t i o no ft r i a n g u l a rm e s h sv e r t e x ，t h eg l o b a la c c u r a c yo fa p p r o x i m a t i o nm e s hh a s b e e n i m p r o v e d w i t h o u tp e r t u r bm e s h st o p o l o g ya n dq u a n t i t yo f t r i a n g l e s i nt h em e a n t i m e ， al o c a lo p t i m i z a t i o na l g o r i t h mh a sb e e nd e v e l o p e dt oi m p r o v ea c c u r a c yo fa p p r o x i m a t i o n m e s h ，m i n i m i z et h en u m b e ro ft r i a n g l e s a n dr e m o v el o n g - n a r r o ws h a p e d 虹b n g k s e f f e c t i v e l y am e t h o do fc o n s t r u c t i n gc u r v e dm e s hf r o mi r i a n g l em e s hh a sa l s ob e e np r e s e n t e d t h u sa na p p r o x i m a t ec 1c o n t i n u o u sb e z i e rp a t c h e sc a l lb ec o n s t r u c t e d an c p r o g r a m m i n ga l g o r i t h mt h a td i r e c t l ye m p l o y s t h et r i a n g u l a rm e s hr e c o n s t m c t e d f r o ms c a t t e r e dd a t ac l o u dh a sb e e nd e v e l o p e da n dp r a c t i c e df o rm a n u f a c t u r i n gm a l ea n d f e m a l ed i eo ff l e e f o r ms u r f a c e a sa l l a p p l i c a t i o n o ft h ea b o v er e s e a r c h ，an co r i e n t e dd a t a c l o u ds u r f a c e r e c o n s t r u c t i o ns o f t w a r es y s t e m s d s c a d 1 0h a sb e e na c c o m p l i s h e d k e y w o r d s ：3 ds c a t t e r e dd a t a ，d a t ac l o u d ，g e o m e t r i c a lm o d e l i n g ，r e v e r s ee n g i n e e r i n g ， s u r f a c e a p p r o x i m a t i o n _ _ 一h _ _ i i 华中理工大学博士学位论文 1 1 论文的研究背景 第一章绪论 随着计算机技术的飞速发展，c a d 技术逐渐渗透到飞机、汽车、机械、电子、 建筑、服装、艺术等领域。几何造型作为c a d 的基础技术，经过几十年的研究已经 在工业生产中得到广泛的应用。目前，几何造型的研究方向主要是扩大造型覆盖领 域和提高稳定性。因此，如何构造具有复杂外形的几何形体是当前研究的一个重要 方向。 随着航天、航空、造船、汽车和模具工业的发展，越来越多的零件的外形由复 杂曲面构成。这类零件的设计和加工是制造过程中的重点，在整个产品开发、生产 过程起着举足轻重的作用。目前，在使用c a d 过程中，设计前通常需要给出模型的 理论数据，以理论值作为设计的依据。但是在实际设计过程中，复杂曲面零件的设 计有时并不是从己知的理论数据开始，而是根据实物模型来进行的。例如，在飞机 机翼设计过程中，设计工作是首先制作机翼的实物模型，再通过风洞试验，反复对 模型进行修改，直到得到具有最佳的设计效果。这种在实物模型上直接修改和试验 的设计方法，常常导致部分理论数据失效，最后的设计数据必须从实物模型的风洞 实验中得到。这种模型化设计方法的结果不是理论数据而是实物模型。又如在模其 制造业中，也常常要求从测量实物模型出发，建立复杂曲面模具的数学模型，以实 现模具的数控加工。由此可以看出：为了方便、迅速、精确地构造复杂曲面数学模 型，我们迫切需要将复杂曲面的测量引入到设计造型与加工过程中，将测量系统与 造型系统结合起来，构成测量几何造型系统，以实现复杂曲面的仿型、放大、缩小 和示教数控编程，这将大大提高制造效率。随着c a d 技术和测量技术的发展，测量 几何造型即所谓的反求工程，将有着广阔的应用价值。 测量几何造型系统与目前广泛使用的计算机辅助几何造型系统出发点不完全相 同，它是用测量系统对实物模型进行三维测量，即对实物模型三维采样，得到物体 表面的三维散乱数据，输入到c a d c a m 系统，并应用数学方法进行曲面拟合、光 顺及拼接处理；应用三维散乱数据曲面重构技术，建立实物模型的数学模型，进而 编制数控加工程序，从而实现复杂曲面的数控加工。三维散乱数据曲面重构技术是 联系测量系统数学模型和数控加工的纽带，是测量几何造型系统的关键技术之一。 华中理工大学博士学位论文 三维散乱数据曲面重构技术极大地方便了c a d 系统中曲面概念设计。设计人员 在c a d 系统中对产品进行概念设计时，往往只能设计出自由曲面的大致形状，对于 某些精度要求很高的表面形状根本无法定量保证。即使输入一些数据点以保证精度， 如果用一般的造型方法进行插值，虽然能生成经过给定点的曲面，但是由于数据的 疏密不一，会产生曲面扭曲，也很难达到实用的目的。如果对这些数据分片插值并 保证曲面片之间一定的连续性，就会产生既满足精度要求又光顺满意的曲面形状。 三维散乱数据曲面重构技术在艺术领域也有广泛的应用。在计算机制作三维动 画时，要构造出高度逼真的形体，那么用通常的造型方法是很难实现的，可行的方 法是用粘土等材料制成原始模型，通过三维测量装置测量出模型表面的大量数据， 再通过曲面重构技术获得该实物的数学模型。然后，在计算机上进行局部修改、移 动、放大、缩小和形体夸张变形等操作，实现各种复杂动作，达到逼真的艺术效果。 这种方法目前在电影、电视制作中越来越广泛地实用，对于制作以假乱真的科幻影 片，具有极其光明的应用前景。 总之，这种将测量系统与造型系统结合起来的曲面重构方法为设计者设计复杂 形状提供了极大的方便，在工程实际中具有广阔的应用前景。因此，开发实用的测 量一建模一加工一体化系统，可迅速将实物模型转化为产品，大大节省实物模型的 测量、绘制、设计全过程的时间及各种工装夹具的费用，最大限度地扩展数控加工 中心的用途，实现一机多用。测量一造型一加工的集成化与一体化将大大提高复杂 曲面零件的设计、制造效率。 由此，本文围绕测量几何造型系统的关键技术：密集三维散乱数据曲面重构展 开工作，开发三维散乱数据曲面重构软件系统，得到复杂曲面测量几何模型。根据 该几何模型，生成数控加工标准g 代码。然后进行曲面数控编程与数控加工。本课 题获得了国家自然科学基金的资助( 项目号5 9 5 7 5 0 9 0 ) 。 1 2 几何造型技术概述 计算机辅助几何设计( c o m p u t e r a i d e dg e o m e t r i cd e s i g n ) 是一门研究在计算机 上逼近和描述物体几何外形的学科。作为一门新兴的学科，它综合了微分几何、函 数逼近、样条函数及计算机科学等学科的最新成果。近年来发展很快，在理论和应 用上都取得了长足的进展。目前几何造型的常用方法有以下几种。 华中理工大学博士学位论文 1 21 曲面造型( s u r f a c em o d e l i n g ) 曲面造型又称为表面造型，它通过顶点、边和表面三种几何元素及其相互间的 拓扑关系来描述三维物体的形状。曲面造型提供了三维物体的表面信息，能够进行 隐藏线消除和真实感图形显示，能够支持产品的数控加工，因此曲面造型技术有着 广阔的应用范围。 从六十年代以来，曲面造型技术随着数学方法的发展不断完善。由于边界插值 曲面，尤其是c o o n s 方法的出现，曲面的构造多以边界控制即确定曲面的边界和某 些边界条件来构造曲面。b e n e r 于1 9 7 1 年提出了种基于b e r n s t e i n 基函数，由控 制多边形定义的曲线模型，并将该模型推广到曲面的定义上，形成了著名的b e z i e r 曲面模型。b e z i e r 曲面模型采用多边形控制顶点来描述曲面，该曲面模型直接面向 几何而不是代数，设计人员可以很直观地控制曲面形状，经问世，就受到学术界 的广泛重视，在实践中表现出强大的生命力。但是b e n e r 方法不具有局部特性，在 设计复杂曲面的过程中，存在着拼接方面的困难。为解决b e z i e r 方法局部修改的问 题，g o r d o n 和p d e s e n f e l d t 2 2 】对b e z i e r 方法进行了改进，用b 样条函数代替b e r n s t e i n 基函数，b 样条方法不但继承了b e z i e r 方法的优点，而且还具有独特的局部特性， 使得设计者能方便地对b 样条曲线曲面进行局部修改。b 样条方法兼具了b e n e r 方 法的一切优点，具有表示与设计自由型曲线曲面的强大功能，b 样条方法自产生以 来便得到了广泛的应用，目前，b 样条曲线、曲面已成为c a g d 中的重要几何造型 方法之一。但是b 样条方法也存在着不足，b 样条方法虽然能方便地对自由曲线和 曲面进行表达，但它无法对常用的二次曲线曲面进行统一的精确表达，因而在对二 次曲线盐面的处理上极为不方便。为此，人们展开了对有理b 样条特别是非均匀有 理b 样条( n u r b s ) 方法的研究。1 9 7 5 年，美国s y r a c u s e 大学的v e r s p r i l l e l 2 ”首先 开始系统地研究有理b 样条方法，t i l l e r t 2 4 - z s l 和p i e g l t 2 6 - 2 8 1 等许多专家对有理b 样条方 法做了进一步地研究，使这一方法在理论与实用上逐步趋向成熟，为其在工程中的 应用打下了坚实的理论基础。有理b 样条曲线曲面模型不但保留了普通b 样条曲线 曲面模型的优点，而且还能对常用的二次曲线曲面进行统一的精确表达。迄今为止， 非均匀有理b 样条是最强有力的曲线曲面表达模型，国际标准化组织( i s o ) 正式 颁布的工业产品数据表达及交换标准( s t e p ) 中，选用n u r b s 表达方式作为产品 几何描述的主要方法。 以上这些曲面造型的方法虽已被广泛地应用于工业设计中，但却有一定的局限 性，即它们仅限于四边域网格上的曲面构造，为了突破这种限制，人们又发展7 - - - - 华中理工大学博士学位论文 角域上的曲面插值”，关于三角形网格上的曲面造型问题，将在后面章节中进一 步讨论。 1 2 2 实体造型( s o l i dm o d e l i n 9 1 实体造型主要研究空间三维实体的几何描述。实体造型方法提供了物体的顶点、 边界、表面和实体部分几乎所有的几何和拓朴信息，因此它可以支持对表达形体的 消隐、真实感图形显示、有限元分析、数控加工、剖切操作及各种物性计算等多种 处理。正是由于实体造型方法具有如此强大的功能，自实体造型方法产生以来，在 较短的时闾内就得到了迅速的发展。目前，实体造型系统中对实体的表达方式主要 有三种：( 1 ) 基于体素分解的表达方法；( 2 ) 构造实体几何( c s g ) 方法：( 3 ) 边界表达 方法( b r e p ) ，其中以c s g 表达及基于b r e p 表达方法占主导地位。 体素分解的表达方法的基本思想是：将复杂的几何形体层层分解，并将其逼近 表示成为一簇基本体素的集合，分解后的复杂形体表示成一棵八叉树。该方法简单 易行，但对形体的表达是近似，因而很难反映出形体的宏观几何特点，且该表达方 法需要较大的计算机内存，在实际应用中会受到很大的限制。构造实体几何方法是 通过体素之间的布尔运算定义三维实体，该方法能够无二义地表达正则实体，能够 清晰地表达复杂系统的构造过程。边界表达方法是通过边界元素及其拓扑关系来描 述三维空间中的正则实体。 目前，国外己推出了不少优秀的实体造型系统，如美国的p r o 甩n g i n e e r ，c v ， u g i i ，i n t e r g r a p h ，法国的e u c h d ，c a a ，英国的d u c t ，m e d u s a ，日本 的t i p s 以及德国的c o m a c 系统，国内清华大学推出的g e m s 4 0 ，北京航空航天 大学的p a n d a ，浙江大学的m e s s a g e 以及华中理工大学推出的f m t 2 0 系统。 1 2 3 曲面+ 实体造型( s u r f a c em d s o l i dm o d e l i n g ) 在实际应用中，绝大多数的设计都是实体造型和曲面造型的有机结合。传统的 将两者严格分开的思想已不能很好地适应这种设计要求。将曲面造型与实体造型融 为一体己成为发展的必然趋势。曲面造型方法由于没有明确定义三维形体的实心部 分，因此曲面造型方法不能无二义性地表达三维形体，不能够进行剖面操作，也不 能进行物体的重心、质量、体积、转动惯量等物性计算。目前，曲面造型方法作为 华中理工大学博士学位论文 一种独立的造型方法仅用于一些小型专用的曲面造型系统中，在大型的通用c a d 系 统中则多采用曲面与实体混台表达的几何造型方法。但是由于算法和数据结构的巨 大差异，使得连续曲面所描述的曲面很难与实体造型有机地统一起来。前者是连续 函数的解析表示，后者则是点、线、面表示的离散拓扑结构。目前有些商品化系统 如c a t i a ，e u c l i d ，m e d u s a 己将曲面和实体统一在多面体模型上，睡面在迸 入实体系统时，首先要离散化。这神方法要经过许多中间转换环节，并大大增加数 据库的存储量。 实现曲面造型和实体造型的统一，近年来国际上有一个共同的发展趋势，那就 是从线框模型着手，使用n u r b s ( 非均匀有理b 样条) 作为统一的几何表示，由线框 生成曲面，再由裁剪曲面( t r i m m e ds u r f a c e ) 力【l 上拓扑关系变成实体，真正做到线框、 曲面和实体三种模型的统一。这种统一模式要求建立一个比较庞大的参数化标准件 库。以体为基础的传统拼合运算方法要改成以裁剪面及环为基础，采用面与面缝合 的方法。高级曲面功能如求交、裁剪、过渡、延伸等是曲面造型中的难点，实现曲 面和实体的统一，这些高级曲面功能成了系统拼合，运算高效、可靠的必要前提。 因此在实现曲面和实体的这种统一上还有许多难点要攻破，要求人们从新的角度来 考虑系统的数据结构和算法。 1 2 4 特征造型( f e a t u r em o d e l i n g ) c a d c a m 技术的发展要求不断完善产品几何模型的表示方法。从线框模型到 实体模型，这些模型都仅仅是围绕着如何完整表达零件的几何信息这问题。但是 产品信息除包括零部件的几何信息外，还应有特征信息，装配信息以及功能信息等 等。因此，传统的实体造型在产品信息的完备性方面严重不足，无法满足c a d c a m 集成的要求，在实际工程应用中受到很大的限制。人们为了解决这个问题，提出了 特征模型这一概念，特征造型技术由此应运而生。近年来，许多专家学者针对特征 造型进行了大量研究。目前，已经有一些商用系统提供了特征功能，如a p t 的 c i m p l e x 系统，s d r c 的卜一d e a s 系统以及p a r a m e t r i ct e c h n o l o g y 公司的 p r 0 e n g i n e e r 系统等等。这些系统都可利用特征进行操作和设计。目前，就如何 有效地表达特征，不同环境下的特征映射机制，特征造型的体系结构等有关问题仍 有待于进一步地研究。 华中理工大学博士学位论文 1 2 5 参数化造型( p a r a m e t r i cm o d e l i n g ) 参数化造型的主体思想是用几何约束说明产品模型的形状特性，从而达到设计 一簇在形状或功能上具有相似性的设计方案，并获得支持c a d 各种决策和分析活动 的能力。 在参数化造型中，对几何约束的表达是一个重要的环节。目前主要有两类几何 约束表达方法。一类是面向人工智能的知识表达方法，该类方法采用符号形式表达 几何形体中各种类型的数据，因此非常直观，易于理解，但该方法难与几何造型系 统进行衔接。另一类几何约束表达方法是面向几何造型的数据结构表达方法，该类 方法将几何要素的几何信息，拓朴信息以及它们之间的约束关系，用数据结构的形 式表达于一个统一的数据模型中，该方法结构紧凑，非常适合于在交互式几何造型 系统中采用。目前，基于约束的参数化技术主要应用在相似零件族的快速生成和修 改，公差分析和设计优化等方面。 参数化造型作为一种新的几何造型发展方向，受到越来越多的重视，在许多大 型通用的c a d 系统中都体现了参数化造型的思想。 1 3 三维散乱数据曲面重构技术综述 在曲面造型的研究领域，存在许多的造型方法，但是传统的曲面生成方法难以 产生复杂的曲面，即使能够构造出来，往往不能达到给定的精度。因此，复杂曲面 的造型一般采用测量和造型相结合的方法，即首先制作待构曲面的实物模型，再通 过测量系统得到待构曲面上的密集散乱点群，最后对这些散乱点进行曲面重构得到 待构曲面的数学模型。这种将测量系统与造型系统结合起来的曲面重构方法为设计 者设计复杂形状提供了极大的方便，在工程实际中具有广阔的应用前景，是各国学 者研究的热门方向。国内外专家学者在这方面做了大量理论研究和实际探索，取得 丰硕成果。 v e l t k a m p 将散乱数据曲面重构问题归类于广义上的计算几何( c o m p u t a t i o n a l g e o m e t r y ) 研究范畴。计算几何可分为处理离散数据的离散计算几何( d i s c r e t e c o m p u t a t i o n a lg e o m e t r y ) 和处理曲线表示及生成的连续计算几何( c o n t i n u o u s c o m p n t i o n a lg e o m e t r y ) 。虽然不同的研究者对计算几何的研究领域有着不同的定义， 本文认为v e l t k a m p 的分类方法将散乱数据曲面重构的研究统一在计算几何领域，不 6 华中理5 - 大学博士学位论文 仅扩宽了计算几何的研究领域。而且有机地将离散数据的研究结合到传统的计算几 何研究巾来。按曲面重构方式来分，三维散乱数据曲面重构方法分为整体拟合和局 部拟合。下面就这两种方法分别加以介绍。 1 3 1 三维散乱数据的整体拟合 三维散乱数据的整体拟合按曲面拟合方程的表达形式来分，可分为隐式重构和 显式重构，隐式重构( i m p l i c i tr e c o n s t m c t i o n ) j l 匝过定义函数，：r 3 寸r ，以保证离散点 集p = 扣肌) 逼近函数的零集z 。p r a t t 3 6 1 和t a u b i n 用最d , - - 乘法逼近多项式来构 造函数- ，m u r a k i ”1 在构造函数- ，后，用评估函数评价离散点集逼近精度及法矢的 逼近精度。m o o r e 和w a r r e n 用分片多项式递归地拟合曲面，并且用自由曲面的 b l e n d i n g 方法来保证连续性。参数重构( p a r a m e t r i cr e c o n s t r u c t i o n ) 方法作为隐式重构 方法的特殊情况也得到深入的研究。参数重构方法定义函数厂将二维参数域d e n z 映 射到三维空问r 3h a s t i e 和s t u e t z l e i ”】以及v e m u r i i ”讨论了参数域为平面区域的情 况，s c h u d y 和b a l l a r d 以及b r i n k l y l 40 1 则分别讨论了封闭曲面的重构方法，他们将参 数域定义在球形区域上。 显式重构( e x p l i c i tr e c o n s t r u c t i o n ) 通过给定2 d 或3 d 点群p = a 一p 。 及其对应 标量值e ，构造函数f ：r 2 或r 3 - 只，使他j = e 或儿曲“e ( 以上两式分别对应插值 和逼近) 。显式重构最经典的方法是s h e p a r d 方法。这种方法用距离的倒数作为权值 来构造加权的插值函数。s h e p a r d 方法简单，但是最大的缺点是不能保证曲面的局部 形状。f r a n k e 和n i e l s o n t 4 l 】对s h e p a r d 方法进行了修正，提出m o d i f i e dq u a d r a t i c s h e p a r d sm e t h o d ( m q s ) ，m q s 方法利用局部最小二乘逼近来保证曲面的局部形状， 但是在边界处效果并不理想，g o s h t a s h y 和0 n e i l l h 2 1 在1 9 9 3 年对m u l t i q u a d r i c s m q l ， t h i n p l a t e s p l i n e 和s u mo fg a u s s i a n 方法作了详细的比较，三种方法的区别在于插 值函数的构造方式不同。 总而言之，整体拟合诸方法的共同特点在于用个函数的解析式完全表达待构 曲面方程。整体拟合在计算机视觉、模式识别和科学数据可视化等方面有广泛的应 用。但是整体拟合的曲面方程解析表示与通用c a d 系统中曲面方程韵参数表示不兼 容，使得所建立的曲面无法在c a d 系统中进行修改和集合运算，这必将使得复杂曲 面的造型与加工缺乏柔性。基于这一点，对于c a d c a m 方面的应用，采用参数形 式来表示待构曲面具有十分重要的意义。 7 华中理工大学博士学位论文 1 3 2 三维散乱数据的局部拟合 局部拟合通常是从离散数据的三角形网格出发，以三角形为单位分别构造出分 片的插值曲面，这种插值曲面在整体上一般能够达到c 1 或g 1 连续。局部拟合适用 于复杂曲面的造型与加工过程。 1 三角化过程 三角化过程实质上是用多面体模型来逼近和插值原始的散乱数据。三角形网格 生成技术发展到现在，已经出现了大量的不同实现方法。d e l a u n a y 或改进的d e l a u n a y 三角化算法，该类三角化算法是目前最常用的三角化算法。d e l a u n a y 三角化技术发 展到现在，已经出现了大量的不同算法。一般可以将其分为以下三大类： 以b o w y e r t 4 m 和g r e e n 、s i b s o n s “l 为代表的计算v o r o n o i 图方法出现较早，其基本 思想是首先计算点集的v o r o n o i 图，最后再求出其几何对偶d t ，后来l e e 和s c h a c h t e f l 4 q 利用分治( d i v i d e a n d - c o n q u a r ) 技术也提出了一种直接计算v o r o n o i 图的方法。一般来 说，直接计算v o r o n o i 图的方法比较复杂，所需内存大，计算效率低 4 3 - 4 5 1 ，平均计算 时间最快为o ( n l o g n + i v ) 1 4 3 1 。随着直按计算d e l a u n a y _ - 三角化方法的出现，这一类方法 现己很少采用。 以l a w s o n ”4 6 】为代表的对角线交换算法的理论根据是d e l a u n a y ：_ _ 彝1 化的空外接 圆特性。该方法是步进的( i n c r e m e n t a l ) ，每引入一新点，立即将其插入三角形中，并 恢复d e l a u n a y 特性。假设前n 个节点的插入已完成，现在某一三角形中引入第n + 1 个 新点，将新点与该三角形三顶点相连，从而将其一分为三，形成三个新三角形，将 这三个新三角形列入待考察的三角形列表中，逐一考虑每一新三角形与其相邻三角 形( 指与新点相对的三角形) 所形成的凸四边形( 如果四边形非凸，则放弃考虑) ，该凸 四边形以旧三角形的一边为对角线，画出新三角形的外接圆，若该外接圆包含该凸 四边形的四个顶点，则依据d e l a u n a r y 特性，将该凸四边形的对角线交换，从而形 成两新三角形，将这两个新三角形也列入待考察的三角形列表中，重复上述步骤， 直到待考察的三角形列表为空，不再有任何对角线交换为止，此时第n + 1 个点的插 入d e l a u n a r y = 角化即已完成。 另一种最有代表性的d e l a u n a y = 角化方法就是所谓w a t s o n 算法 1 1 - 1 4 l ，其理论基 华中理工大学博士学位论文 础同样足基于d e l a u n a y 三角化的窄外接圆特性。该方法也是步进的。假设已完成前n 个节点的d e l a u n a y 三角化，现引入第( n + 1 ) 个新点p ，首先对每个三角形进行检查。 确定其外接圆包含该新点的所有三角形，这些三角形将构成一个所谓插入多边形f 简 称为i p ) ，删除插入多边形内所有原d e l a u n a y 三角形，将新点与插入多边形所有边界 点相联，则可以形成若干新的三角形，可以证明这些三角形与原有其它未被删除的 三角形一起形成了包含该新点在内的新d e l a u n a y 三角化。 s h e n t o n 和c e n d e s t ”1 利用g r e e n 及s i b s o n l 4 4 l 的思想提出了一种修正w a t s o n 算法，该 法在找到包含新插入点的单元后，建立一包含该单元的单元列表及一包含该单元三 边的边列表，逐- n 试边表中的边，若新点与测试边形成的三角形的外接圆包含与 该测试边相邻的另一三角形的另一顶点，则将该相邻三角形加入到单元列表中，将 该相邻三角形另两边加入到边表中，并从边表中删除该测试边，如此重复下来，直 到不能再找到这样的相邻三角形为止。由单元列表中的所有三角形形成了包含新点 的插入多边形0 p ) ，将新点与i p 顶点相连即得新的d e l a u n a y = 角化。该法克服t w a t s o n 算法要求当前三角化必须是d e l a u n a y = 角化的不足，通过以种子单元为起点，借助 相邻单元将i p 向外扩展，该法后来被很多文献所采用。 l a w s o n 算法特别适用于二维d e l a u n a y 三- 角化j ，它不存在象w a t s o n 算法中出现 的退化现象，对约束情况同样适用，计算效率高，平均计算时间最快为。柙v 5 勺1 3 。1 1 但在三维情况下，对角线交换的推广变成了对角面交换，而对角面交换将可能改变 区域体积和外边界，因此l a w s o n 算法不能直接推广到三维情况1 5 - 1 0 l 【1 5 】。 w a t s o n 算法概念简单，易于编程实现，也能够实现约束三角化，而且通过一些 适当修改，可以将对三角形的搜索局限在新点所在单元的近邻之中，从而大大提高 算法效率，平均计算时间最快为o o v l o g n ) 【1 3 i 。因此该法的应用频度最广。但该法的 不足之处在于：( 1 ) 易出现所谓退化现象1 4 ，”，”- 6 6 1 ；( 2 ) 在3 d 情况下，易产生所谓s l i v e r 单元1 6 5 , 6 7 1 ；( 3 ) 易出现病态插入多边形1 4 t ”。“】。 虽然d e l a u n a y 三角化方法在二维平面区域问题中取得了相当大的成功，但在3 d 网格自动生成中却遇到了巨大困难。在2 dd e l a u n a y 三角化中，最大一最小角判据处 处适用。但在3 d 情形，基于最大一最小角判据的对角线交换规则不再成立，而基于 外接圆判据的d e l a u n a y 三角化一般也不再能保证生成的网格质量。遗憾的是，这是 d e l a u n a y 三角化的本质弱点，它贯穿于网格生成全过程，除非对d e l a u n a y 三角化概 念本身予以修改【7 4 。 华中理工大学博士学位论文 推进波前法( a d v a n c i n gf r o n tm e t i l o d ) 最初是由l o t 6 ”提出并用于平面区域三角形 网格自动生成。后来p e r a i r e l 7 0 1 等将这种方法进一步完善推广。稍后p e r a i r e i ，t 1 及 l o h n e r t 1 几乎同时成功地把这种技术推广到任意形状三维域的四面体网格生成。与 基于d e l a u n a y 概念的各种方法相比，推进波前法对复杂几何形状与边界的二维域( 或 三维域) 中的三角形( 或四面体) 网格生成具有更大的灵活性及可靠性。但该法的最大 缺点是计算时间效率低，l o h n e r t ”2 】和b o n e t t 针对推进波前法存在大量搜索查询操 作的特点提出了一些有用的数据结构及算法，其得到的算法效率均为 o ( n l o g ( n ) ) 。g e o r g e t ”4 】贝0 通过引入控制空间及相邻空间概念，试图对推进波前法 作一些改进。l o h n e r t “5 1 曾将并行计算与推进波前法结合用于网格生成。文献“u 7 1 提 出的法向偏移方法( n o r m a lo f f s e t t i n gt e c h n i q u e ) 可以认为是推进波前法的扩展，在 该法中波前是一层层推进的。 虽然推进波前法相对其它方法发展较晚，但由于其特有的简单、可靠等优点， 吸引了不少研究者对它进行深入研究h ”。2 “。缺点在于当点较多的情况下，计算量非 常大，效率较低。 对于形状非常复杂或局部形状丰实的曲面，常常有大量的密集点群集中于形状 变化大的区域，三角化过程中的插值方法精确通过测量点，插值法必然会造成大量 微细密集三角片，大量微细三角片不仅为蒙面带来困难，而且存在大量的冗余信息， 给后续操作带来极大不便。这正是插值法最大的缺陷所在。 针对上述问题，h o p p e ( h t t p ：w w w c s w a s h i n g t o n e d u ) 提出用微切平面逼近三维散 乱数据的三角形网格生成算法。该算法基于曲面形状信息反映在三维散乱点集中， 用三维点集中某点的邻域点集构造微切平面来近似表示该点处的局部形状，所有点 的微切平面集合则构成了待构曲面的近似表示。最后通过欧几里德最小生成树对微 切平面法矢方向进行调整使其达到整体一致性。该算法从线性逼近的方向进行了探 索，即用三角形网格来近似表示三维散乱数据所表示的曲面，但并不要求散乱点为 三角形网格中三角片的顶点。但该方法的缺陷在于有裂缝现象产生。但这种逼近的 思想为我们解决密集测量三维散乱点的三角形网格逼近打下了良好的基础。 2 三角域上的曲面插值过程 该过程用曲面片分片插值三角形网格，得到具有一定参数连续性或几何连续性 的拼接曲面。 就三角域上的插值而言，b a r n h i l l 。b i v l d m f 和g m g o w 给出了正规三角形上的b b g o 华中理工大学博士学位论文 插值格式，第一次从曲面造型的角度分析了离散数据的曲面插值问题m i ，在三角形 曲面造型中占有非常重要的地位。为了解决这利tb b g 插值格式在三角形顶点的冼调 性问题，g r e g o r y 给出了一种在项点处能够自动达到协调的插值格式，即g r e g o r y 插 值格式。 。 1 9 7 7 年s a b i n t 则首次给出了三角域土b e z i e r 三角曲面的矢量形式。而f a r i n t g u 贝j j 将其推广到任意三角剖分上，大大地提高了三边曲面片的应用范围。对于曲面片间 的连续性问题，一阶参数连续要求两相邻三边b e z i e r 曲面片以公共控制多边形的边 为公共边的所有对网格三角形都是参数平面内它们那对域三角形的仿射像，而二阶 与高阶参数连续性分别与邻接公共控制多边形的两排与多排网格三角形有关。显然 参数连续性对于曲面的光滑性来说是过份的限制，儿何连续性则是对参数连续性过 份限制的松弛。b a m h i ll 和f a f n 用h e r m i t e 插值构造了九参数的三次b e z i e r 三角蘸 面，这种曲面在整体上只能达到c “连续，后来a l f e l d 等人对这种h e r m i t e 局部插 值模型做了进一步的研究为了构造出整体上能够达到c 连续的h e r m i t e 插值曲 面，b a m h i l l ，f a r i n 提出了一种局部五次的b e z i e r 三角曲面模型，这种曲面插值虽 然能够达到整体c 1 连接，但在构造过程中，使用了比生成的曲面连续阶次更高的导 数条件。这在实际应用中是比较困难的。 f a r i n 通过三角形的c l o u 曲t o c h e r 分割，构造了c 连续的插值曲面，构造 这种c l o u g h t o e h e r 插值曲面避免了给定比曲面连续阶次更高的导数条件，相邻 b e z i e r 三角曲面片之间的连续性通过相邻三角形的适当分割和一阶偏导数连续的条 件来保证，这样构造出的b e z i e r 三角曲面，其几何意义非常明确叭”1 。 山东工业大学的汪嘉业教授给出了一种任意三角形上的c 有理插值方法，这种 插值首先在三角形上定义一个局部坐标系，然后在这个局部坐标系上构造出满足条 件的曲面片，从而使曲面片之间达到c 或c