（机械制造及其自动化专业论文）散乱数据曲面重构技术的研究.pdf

华中理工大学博士学位论文 摘要 反求工程是从对已知对象的测量出发，对测量数据进行分割、组织、几何建模 求出对象的几何模型，它被广泛地应用于航天、航空、造船、汽车、模具制造业、 医学等领域。为了解决反求工程中任意三维散乱数据的曲面建模、重建、产品的二 次开发等方面的问题，本文对相关的理论和实践进行了深入的研究。 、 假求工程中的关键问题是曲面重建问题，重建曲面的拓扑模型有两个，即三角 域模型和矩形域模型，在三角域的反求问题中，首先根据应用领域数据的分布特点， 提出了完全自动产生基于三角域拓扑结构的方法。另外，针对医学领域全身伽玛刀 治疗规划系统( t p s ) 的实际问题，列产生的模型进行操作，实现了反求的意义。 在分析了三角片法优缺点的基础上，本文重点研究了矩形域的反求问题。 根据曲面测量数据量庞大、密集、无序的任意性特点，提出了用任意拓扑结构 的名个自m 曲而耋日织数据的方法。存对任意数据分割过程中，创造性地提出用多个 丛山进 分削的力法，l ! i ：兜服r 舣反求一1 f ，! | _ 究一l - 埘测挝数据的种利- 似改，也儿 服了数目巨大的三角片对计算机性能的要求，建立起了反求工程与通用c a d c a m 系统之间的桥梁。 提出了将任意拓扑结构视为规整和非规整拓扑结构统一体的概念。针对规整拓 扑结构提出了一个保证曲面片间具有精确g k 。连续性的方法，将曲面间连续性的研 究从一般的g 1 连续性提高到更高阶。对于非规整拓扑结构中曲面间连续性问题， ：创造性地提出一种保证多个曲面角点处g 1 连续的数值约束方法，避免了非线性约 束问题对计算机性能提出的苛刻要求。 独特地提出保证曲面间同时具有精确g “2 ，精确g ，近似g 1 三种连续性的重 _ 建方法，充分发掘曲面问的连续特性，满足了人们对尽可能高的连续性的追求。在 实现叶i 综合了日i j 曲面重建的两大方法：曲面构造方法和曲面拟合方法的优点，以 约束条件构造保证曲面问精确的连续性，又在整体上进行多个曲面的拟合。 最后，针对曲面重构中的实际问题提出了一系列优化算法，包括b s p l i n e 曲面 快速投影算法，测量点各步骤的简化算法，曲面拟合的两种分步计算法等。上述研 究成果在任意散乱数据曲面重构系统c td e s i g n1 o 中得到实现。卜一 关键词：散乱数据，反求工程，几何建模，拓扑结构，曲面重建，高阶连续性 华中理工大学博士学位论文 a b s t r a c t n l t i j i c l ii j i i il l l 。i i i 。- i ：- i c i i i c l i ii i c 、i ：，i i “g i u c 。i ，i c v 。i ：；。”8 i l i c u i i “g ；。8 l 。l i i ：- l l i c n l e a s u r e dd a l a ，g e n e r a 【e sl o p o j o g ) a n d 】n a k c sj t sg c o n l e c r j c a jm o d e 】i ti sw i d e l yu s e dj n a “a t i o n ，s h i p b u i l d i n 昏a u t o m o b i l e ，m o u l dt e c h n 0 1 0 9 y ，a l l dc l i n i ca f e a f o c u s i n go nm e p r o b l e m so f s u r f a c em o d e l i n g ，s u r f a c er e c o n s t n j c t i o na 1 1 dp r o d u c t i o n r e d e s i g nf r o md a t a c l o u d s ，t h i st h e s i ss t u d i e dt h er e l a t i o nt h e o r i e s ，a n dd e v e l o p e das e r i e so fa l g o r i t h m s r t h ek e yp r o b l e mi nr e v e r s ee n g i n e e r i n gi ss u r f a c er e c o n s t m c t i o n t h e r ea r et w o t y p e so ft o p o l o g ys t r u c t u r ef - o rs u r f h c e so r g a n i z a t i o n ：t “a n g l em o d e la n dr e c t a n g l em o d e l t od e a lw i t ht h et r i a n g l em o d e lr e v e r s ep r o b l e m ，a na u t o m a t i cc o n s t r u c t i o nm e t h o di s p r o v i d e di n c i i l l i ca r e a i nt h ec l i n i c a p p l l c a t i o no fw h o l eb o d yg a m m ar a yr a d i a t i o n t r e a t m e n t p l a n n i n gs y s t e m ( t p s ) ，t w oa l g o r i t h m s a r ea l s o p r e s e n t e dt oo p e r a t e t h e g e n e r a t e dm o d e l ，w h i c h r e a l l z et h es i g n i f i c a n c eo fr e v e r s ee n g i n e e r i n g b a s e do nt h es h o r t c o m i n ga 1 1 a i y s i so f 砸a 1 1 9 i em o d e i ，t h er e v e r s ep r o b i e mi n r e c t a n g l et o p o l o g ys t r u c t u r ei se s p e c i a u ys t u d i e di nt l i st 1 1 e s i s t od e a lw i t ht 1 1 e1 1l l g e ，d e n s ea n du n o r g a n i z e dr a n d o mm e a s u r e dp o i n t s ，an e x i b l e t o p o l o g ym o d e l i sp r e s e n t e dt oo r g a n i z ed a t ac l o u d si n t om u l t i p l ef k e f o h l ls u r f a c e s t h e， m e t h o do fu s i n gs e v e r a lb a s es u r f a c e si s c r e a t i v e l yp r o m p t e di nm es e g m e n t a t i o no f r a n d o md a t ac i o u d s t h i sc a nn o to n l yo v e r c o m et h el i m i t a t i o n so fr e v e r s ee n g i n e e r i n g s t u d i e sb e f o r e ，s u c ha st h el i m i t a t i o no fm e a s u r e dd o i n t sw h i c hh a v eu n i q u ev a l u ei nx y p l a n e ，a l s oa v o i dt h eh i g hp e r f o r m a n c er e q u e s to fc o m p u t e rs y s t e mf o rc a l c u l a t i n gt h e h u 2 en u m b e ro f2 e n e r a t e dt r i a n 9 1 e s m o r e o v e r ，t h i sm e t h o dm a k e sab r i d g eb e t w e e nt h e c o m m e r c i a lc a d c a ms y s t e ma n dr e v e r s ee n g i n e e r i n g f o rt h ec o l n p l e x i t yo ft o p o l o g ys t r u c t u r e ，an e wi d e ao fr e g a r d i n gn e x i b l et o p o l o g y a st h eu n i o no fr e g u l a 工t o p o l o g ya 1 1 di r r e g u l a rt o p o l o g yi sg i v e n i nt h ec a s eo fr e g u l a r ，。 t o p o l o gy t h i st h e s i sp r e s e n t san e wm u i t i s u r f a c e sr e c o n s t m c t i o nm e t h o dt 王1 a tc a ne n s u r e p e r f e c tg n 2c o n t j n u i t ya m o n gs u r f a c e s t h i si m p r o v e st h en o r m a is t u d yo fg 2 c o n t i n u i t y f t og “2c o n t i n u i t y i nt h ec a s ei r r e g u l a rt o p o l o g y ，a nu n i q u en u m e r i c a lc o n s t r a i n e dm e t h o d i sp r e s e n t e dt oe n s u r eg 1c o n t i n u i t yi nt h ec o r n e rp o s i t i o na m o n gs u r f a c e s ，w h i c ha v o i d t h ed j s a d v a n t a g eo fs o l v j n gn o n j i n e a rc o n s n a j n e de q u a f i o n si ns u r f h c e sf j t f i n 譬 ， a n o t h e rc o n t r i b u t i o ni nt h i st h e s i si st h es t u d yo ft h r e et y p e so fc o n t i n u i t ye x i s t e di n o n er e v e r s eo b i e c t t h o s ea r ep e r f e c tg “! c o n t i n u i t y ，p e r f e c tg c o n t i n u i t ya n dn t t i n gg 1 c o n t i n u i t y t h i s m a k e st h e c o n t i n u i t ya m o n gs u r f a c e s c a nb ea s h i g ha sp o s s i b l e i n 1 1 i l s r l l l 1 1 1 r ir ：c1 w ( 1n l a i o rs i l r 翻c e sl c c o ns t n l c t i o nm e t h o d s ，s u r f h c e sc o n s t r u c t i o na n d s u l 1 u c c s l i 【t l l l 耸j i l 【| l cp 1 o c c s s u ls l i ll u c c sr c c u l l s “l i cl l u l l ，“i i i c “l u d 【i i a 【c u i i i b 儿l c sl i l c a d v a n t a g e so ft h et w om e t h o d si sp r e s e n t e d t h a ti sc o n s 咖c t i n gs u r f a c e st oe n s u r et h e i l 华中理工大学博士学位论文 1 1 c r f e c tc o n t m l l i t ya m o n g 趴1 r f a c e s ，a n dm u l t i p l es l l r f a c e sf i t t i n gt oe n s u r ee n t i r e l ye f f e c t t om a k et h et h e o r yr e s e a r c hb eu s e di np r a c t i c e ，s e r i e so fa 1 2 0 r i t st h a to v e r c o m e t h el i l l l i t a t i o n so fi t l e m o r ya n dt h ec p u s p e e do fc o n l p u t e ra r ep r e s e n t e d i n c l u d er a 口i d p r o j e c t i o na l g o “t h mo fb s p l i n es u r f a c e ，m e a s u r e dp o i n t sf l l t e r i n ga l g o r i m mi ne v e r y d i h 色r e n ts t e p ，t w ot y p e so fp i e c e w i s ef i t t i n ga l g o r i t h n s ，e t c t h e s er e s e a r c hr e s u l t sa r e a l s ou s e di naf r e e f o r ms u r f a c e sr e c o n s t n l c t i o n s y s t e mf r o mr a n d o md a t ac l o u d sf c t d e s 适n1 o ) k e y w o r d ：s c a t t e r e dd a t a ，r e v e r s ee n g i n e e r i n g ，g e o m e t r i c a lm o d e l i n g ，t o p o l o g ys t m c t u r e s u r f a c e sr e c o n s t r u c t i o n ，h i 曲c o n t i n u i t y i j l 华中理工大学博士学位论文 第一章绪论 1 1 论文的研究背景 随着2 0 0 0 年新年的钟声，人类已步入了新的千年二十一世纪，在2 0 0 0 年 到来之际，从全世界的新年狂欢到令人紧张“千年虫”的问题，都显示出当今世界 的全球化现状，计算机已经成为人类生活中不可缺少的一部分。随着计算机技术的 飞速发展，c a d c a m 技术已经发展到一个相当的水平，逐渐渗透到飞机、汽车、 机械、电子、医学、建筑、服装、艺术等领域。几何造型作为c a d 的基础技术， 经过几十年的研究已经在工业生产中得到广泛的应用。传统的工程设计是先将人类 的设想通过c a d 几何造型，再由c a m 制造出实际的物体。而在生产实践中，有 许多产品并非先有c a d 模型描述，而是先有实物样件。为了适应先进制造技术的 发展，需要通过一定途径，将这些实物转化为c a d 模型，以利用c a d c a m 、r _ p m 、 p d m 及c i m s 等先进技术对其进行处理或管理。目前，与这种从实物样件获取产 品数学模型技术相关的技术，已发展为c a d ，c a m 中一个相对独立的范畴，称反求 工程( r e v e r s ee n g i n e e r i n g ) ”。 反求工程就是将实际的物体转换为工程模型，有了模型之后就能够使用已有的 c a d c a m 系统进行设计生产也可以利用快速原型f 9 ，2 l 2 4 1 ( r p ) 技术得到一个实 体，在诸如航天、航空、造船、汽车、模具、人体康复等很多领域n ”1 “1 ) 中具有十 分广泛的需求。概括起来，反求工程可以在以下诸多方面发挥重要作用： ( 1 ) 一些产品的设计工作难以直接用计算机进行某些物体的三维几何设计， 只能从实物开始，用黏土、木材或泡沫塑料进行初始外形设计。例如，在飞机机翼 设计过程中，必须首先制作机翼的实物模型，再通过风洞试验，反复对模型进行修 改，直到得到最佳的设计效果。另外，在一些对美学效果有特别要求的产品设计中， 必须首先做出相同大小的木模或黏土模1 4 ”，这是因为对于设计师来说，仅仅通过观 察计算机中缩小的二维或三维投影来看设计的效果是不够的，需要看实际物体的形 状。这就需要最终通过反求工程将实物模型转化为三维c a d 模型。 ( 2 ) 由于工艺、美观、使用效果等方面的原因，人们经常要对已有的构件做 局部修改。在原始设计没有三维c a d 模型的情况下，若能将实物构件通过数据测 量与处理产生与实际相符的c a d 模型，再对c a d 模型进行修改以后进行生产， 华中理工大学博士学位论文 将显著地提高生产效率。因此，反求工程在改型设计方面可以发挥不可替代的作用。 ( 3 ) 以已有产品为基准点进行设计( b e n c l l l l l a r k i n g ) 已经成为当今的一条设计理 念。目前，我国在设计制造方面距发达国家还有一定的差距，利用反求工程技术可 以充分吸收国外先进的设计制造成果，使我国的产品设计立于更高的起点，同时加 速某些产品的国产化速度。 ( 4 ) 某些大型设备，如航空发动机、汽轮机组等常会因为某一零部件的损坏 而停止运行，通过反向工程手段，可以快速生产这些零部件的替代件，从而提高设 备的利用率和使用寿命。 ( 5 ) 借助于层析x 射线摄影法及相关技术4 。”1 ( c t 技术，c o m p u t 耐z e d t 0 m o g r a p h y ) ，反求工程不仅可以产生物体的外部形态，而且可以快速发现、度量、 定位物体的内部缺陷，从而成为工业产品无损探伤的重要手段。同样在医学领域， 用c t 对病人体内的病灶组织进行诊断时，通过对c t 图片的图像处理可以得到一 系列感兴趣的轮廓线，需要对一系列并行的二维轮廓线进行重构得到三维的几何形 状，这就是“轮廓重构( s u 如c e s 舶mc o n t o u r s ) ”的问题。这在诸如放射治疗规划， 剂量计算，定制式人体髋关节设计，服装( 如合身的头盔、太空服) 等方面具有重 要的意义。 ( 6 ) 利用反求工程手段，可以方便地产生基于模型的计算机视觉，在诸如虚 拟现实( s u a lr e a l n y ) 、临床医学的计算机手术过程模拟f 3 3 】等具有重要意义。 ( 7 ) 通过对实物模型反求出其c a d 模型，可以使产品设计充分利用现有c a d 技术的优势，并适应智能化、集成化的产品设计制造过程中的信息交换，为快速产 品设计、快速原型制造等提供关键技术支持。在商品市场中，反求工程可以迅速将 实物模型转化为产品，节省实物模型的测量、绘制、设计全过程的时间，缩短产品 开发周期，适应市场的快速变化。 总之，为了大大提高制造效率，方便、迅速、精确地构造复杂曲面数学模型， 并使产生的数学模型能够通过通用的c a d c a m 系统进行设计、开发、制造，必须 对反求工程进行深入研究。随着c a d 技术和测量技术的发展，反求工程将有着广 阔的应用价值。 本文围绕反求工程中的关键问题：任意三维散乱数据曲面重构展开工作，研究 了其中的理论方法、一系列关键技术，并在两个具体的应用领域：临床医学放射治 疗的全身伽玛刀治疗规划系统( t r e a t m e n tp l a l l t l i n gs y s t e m ) 和任意散乱数据曲面重 构系统( c td e s i g n1 o ) 中得到应用。前者为放疗剂量计算提供了可靠模型，后者 可以得到具有任意拓扑结构的复杂自由曲面的几何模型。该几何模型可以输出给通 用c a d 系统进行二次开发，或直接交快速原型机( r p ) 或具有直接曲面插补算法 华中理工大学博士学位论文 ( s d i ) 的数控系统加工制造。 1 2 反求工程概述 反求工程是综合性很强的术语，它是以设计方法学为指导，以现代设计理论、 方法、技术为基础，运用各种专业人员的工程设计经验、知识和创新思维，对已有 产品进行解剖、深化和再创造，是已有设计的设计，特别强调再创造是反求的灵魂。 简单地说反求工程的根本目的就是实现智能的三维扫描，通过对已有物体的测量， 建立其表面或实体模型，结果要求可以应用于已有的c a d ，c a m 系统中。 反求工程与三维仿型具有本质的区别。仿型技术已经是一个广泛使用的成熟技 术，就象复印机能够复印出与原来内容完全相同的一页纸一样，三维仿型能够制造 出与原来物体形状完全相同的实体。而二维的扫描技术，不仅仅将一页纸输入计算 机，而且能够自动识别纸上的文字、图形，给出文字和图形的结果文件。反求工程 可以认为是一种智能的三维扫描系统，通过对物体的扫描得到物体形状的几何描 述，由此可以进行分析、评估、修改和重新设计。反求工程的着眼点在于对原有实 物进行修改和再设计后而制造出新的产品，这不仅避免了“侵权”的法律问题，而 且满足了现代社会的实际需求，而仿型的着眼点只在于制造出和原有实物相同的产 品。 反求工程的设计过程与传统的设计过程是完全不同的，二者的比较如图1 1 所 示。传统设计过程是在市场调研的基础上，根据功能和用途来设计产品，得到图纸 或c a d 模型，经检查满意后制造出产品来。而反求工程是从一存在的零件或原型 入手，首先对其进行数字化处理( 即将整个零件用一个庞大的三维点的数据集合来 表示) ，然后是构造c a d 模型，使得能利用c a d c a m 、对，m 、p d m 及c i m s 等 先进技术对其进行处理或管理。简单说来，传统设计和制造是从图纸到零件( 产品) ， ( a ) 传统设计过程 最终 产品 ( b ) 反求工程设计过程 图11 传统设计制造工程与反求工程的区别 最终 产品 华中理工大学博士学位论文 而反求工程的设计是从零件( 或原型) 到图纸， 反求工程在近年来发展的很快，其一般 的处理过程如图1 2 所示，其中几个过程是相 互相关的，并且可能包含几个循环的子过程。 数据获取又称对象数字化，是指采用某种测 量方法和设备测出实物感兴趣部分的点集的 几何坐标( 包括物体表面和内部) 。曲面重构 包括：拓扑结构及数据分割和曲面重建两个 步骤，前者是对测量的大量数据进行组织， 后者是对曲面进行拟合、光顺、拼接，产生 c a d 模型。拓扑结构及数据分割和曲面重建 是相互联系、相互影响、相互作用的两个步 再经过制造过程到零件( 产品) 。 数据获取 0 i曲面重构 | 1 数据分割，拓扑结构建立 1 2 曲面重建 上 c a d 模型 图1 2 一个典型反求过程 骤，也是反求工程中最困难、最复杂部分，目前仍没有一种能够自动的方法产生整 体、连续的c a d 模型。本文主要对这方面进行研究，由于曲面构造与对象数字化 技术密切相关，因而首先对对象数字化问题作一分析。 数宇测量技术 近十年来，随着传感技术、控制技术、制造技术等相关技术的发展，出现了各 种各样的对象数字化方法1 5 l “l ，其分类方法见图1 3 ，总体上可以分为非接触式方 法( n o n c o n t a c tm e c l l o d s ) 和接触式方法( t a c t i l em e t l l o d s ) 。非接触式方法不接触待 测物体的表面，而接触式方法通过机械装置用探针接触被测对象的表面，两种方法 都需要对数据进行分析以获得测量点的坐标，每种方法各有优缺点【5 1 】。 数 据 测 量 方 法 非 接 触 式 接 触 式 光学 亩 电磁 触发式 扫描式 图i 3 数据测量方法 接触式的方法的优点有：1 成本低。2 很稳定( 低噪声、精确、可以重复测 量等) ，采用数控测量系统可以编程决定在物体表面的测量路径，可以得到几乎没 有噪声的数据。其缺点也是显然的：1 测量速度很慢。2 对于具有凹面的物体很 一一一一一一一一一 华中理工大学博士学位论文 难测量。3 尽管测量时测头与被测物体之间的压力很小，但仍然存在一定的接触 压力，对于某些质地柔软的物品必然产生测量误差。4 由于测头的半径而存在三 维补偿问题。随着科学技术的发展，接触式的方法除在某些特定的领域仍在使用外， 而逐渐被非接触式方法取代。 非接触式方法具有三大优点：1 对被测表面没有任何干扰，不会在测量过程 中划伤表面；2 对被测表面的硬度要求很低，可直接对高弹性、柔软物体( 甚至 液体) 表面进行测量；3 没有测头半径三维补偿问题；4 测量速度快，可以相当 密集地对产品表面进行测量，形成所谓的“点云”数据。目前非接触式方法普遍受 到各国科学家的极大重视，从测量的介质上来说可分为光学、声学、电磁学三大类。 光学测量是最常用的一种测量方法，主要有三角法、距离测量法、干涉测量法 ( i m e 疵m m e 仃ym e t l l o d s ) 、结构光法、图象分析法几类：( 1 ) 三角法【5 2 “1 是近年来 研究较多、发展比较成熟的一种测量方法。通过向被测物体表面发射一聚集光束， 感光设备( 通常用摄像机) 检测到反射光的信息，用光源与感光设备之间的位置和 角度计算测量点的三维坐标值。光源和感光设备在平台上运动可以得到表面的多重 扫描信息。激光是最常用的高能量光源，根据接触部分的形状可分为点激光测量机、 线激光测量机和面激光测量机。三角法的测量速度很快，其精度决定于感光设备的 敏感程度、与被测表面的距离、被测对象表面的光学特性等。( 2 ) 距离测量法瞰5 6 1 ( r a n g i n gm e t l l o d s ) 用飞行时间测量距离，通常用激光和脉冲光束。利用光速在空 气中恒速的原理，由测距器主动发出光、电脉冲，在遇到物体表面时反射回来，根 据脉冲在测距器与物体之间的飞行时间测出距离。( 3 ) 干涉测量法( i n t e r f e r o m e t r y m e t h o d s ) 用光波的干涉条纹图像测量距离，由于可见光的波长为纳米级，而测量 的范围比这大的多，所以这种方法能够得到很好的测量精度。( 4 ) 结构光法将一个 光学光栅投影到物体表面上，得到从物体表面反射的光栅图像，通过分析图像得到 测量点的坐标，投影莫尔轮廓术是一种最常见的结构光的方法。结构光法可以通过 一幅图像获得很多点的信息，一幅图像的大小可以从1 2 8 1 2 8 到5 0 0 0 + 5 0 0 0 ，但分 析图像而得到点的坐标是一个复杂的工作。w i l l 和p e r u l i n g t o n i ”】将网格投影到表面 上以得到点的坐标，w 抽g 和a g g a 州a l 【5 8 1 用斑纹投影并对多幅图像进行分析。( 5 ) 图象分析法也是对图像进行分析，但不用结构光投影到表面上。通过立体的检测设 备得到足够的信息来确定表面的高度和坐标信息。这种方法是一种被动获取方法 ( p a s s i v em e t h o d ) ，图像之间的匹配和界限区分是这种方法的最大难点。这类 获取技术精度差，主要应用于早期的图像识别，做三维场景识别之类。其中的代表 是立体视觉法，根据双目成像原理，从不同角度获取同一景物的两幅或多幅图像， 通过图像匹配技术，分析并计算出景物的坐标信息。 华中理工大学博士学位论文 声学方法在很早就被用来测量距离，如声纳探测技术，某些自动聚焦的照相机 就是采用声学方法测定距离。这种方法类似于时间飞行法，通过测量声源与物体反 射回的声波的时间间隔确定距离，声音干涉和噪声是这种方法的一个难点。m i u 磁 共震( m a 辨e t i cr e s o n a n c e ) 通过激活待测对象的原子，测量其反应程度。声学方法 和电磁方法与其他方法相比一个显著的特性是：它不仅仅能够得到物体的表面形 状，而且可以得到物体的材料、内部形状的信息，这对于无损检测以及测量没有备 件和复制品的复杂形体实物非常重要。工业用c t 或医用c t 机都能够得到待测对 象内部的信息。 各种数据获取的手段各具有其优缺点，分别适用于不同的要求，在实际使用中 根据应用的领域、对测量精度、速度的要求以及被测对象的特性加以选择。另外， 在某些情况下，单一的扫描过程可能不能够获得所有的数据，可能需要进行多个扫 描数据的融合( c o m b i n i n gm u l t i p l ev i e w s ) 。 1 3 三维散乱数据曲面重构现状及关键技术 反求工程开始于对已有对象的数字化测量，对象可以是一个简单机械零件的表 面，也可以是一个复杂的模型( 如一只兔子的模型) ，甚至人体内的肿瘤、组织、 骨头等。根据不同应用领域的要求，不能对测量出的数据进行假设，如要求测出的 数据云为有规律的，或要求测量出的数据是在x o y 平面上投影为单值的数据。测 量出的数据可以是任意的三维数据，甚至图像信息。如何以这些任意的散乱数据作 为输入，通过曲面重构，输出c a d 模型是反求工程中的关键。 目前已经有一些反求工程的软件系统：生产坐标测量仪的厂家d e a 为自己的 测量仪开发的基于b 6 z i e r 曲面模型的系统s u 7 e r ”，德国c m m ( c o o r d i n a t e m e a s u 咖gm a c i l i n e ) 生产厂家z e i s s 的h o l o s l 6 4 】同样是基于b z i e r 曲面，美国 i m a g e w a r e 公司的s u r j 认c e r i “l 可以将数据云转换为b s p l i n e 曲面，但只能从 一些散乱点集拟合出单个b s p l i n e 曲面。比利时的 ：m t l l i l 6 1 自行开发的s h a p i d 系 统包括测量、造型、快速原型的一套系统，在曲面造型上虽然支持b z i e r b s 口l i n e 曲线曲面，但系统采用线框模型，对于曲面间的连续性没有进一步保证。另外s a l ( a r 和m e n 矿6 l 对直接从离散点拟合b s p l i n e 曲面做了研究，但他处理的数据是假设投 影到x o y 平面上其z 值是单值的情况，另外同样只能处理单张b s 口l i n e 曲面【”- 6 9 l 。 目前，许多通用的c a d c a m 系统，如u g i i ，p r o e 等也都增加了测量造型模块。 山东工程学院汽车工程系亦已研制成这类软件，并在汽车外形设计和反求中应用， 但三维曲面的光顺问题还未妥善解决，一般按人为方法去处理，具有一定误差。 作为曲面重构入口的测量数据，对曲面重构的方法具有重要影响。为了重建方 6 华中理工大学博士学位论文 便，目前很多曲面重构的研究工作都对测量数据做了一些假设，只能处理某些特殊 分布的测量数据，第一小节将对这些假设进行讨论。 曲面重构过程可以分为两个步骤：对测量数据和曲面的拓扑组织，曲面的重建。 这两个部分是相互影响、彼此依赖的，拓扑结构的组织形式决定了曲面的重建方法， 曲面重建的结果反过来又对拓扑结构的组织形式提出要求。第二、三小节分别对这 两部分加以介绍。 1 3 1 对测量数据的隐含约束。 目前一些曲面重构研究工作对测量数据的假设主要有下列三个方面： 1 数据是基于三坐标测量仪在单一的方向测出的，例如从z 方向向下测量， 所测出的数据在z 方向为单值，即将所有的数据投影到x o y 平面上不会有两个点 投影到x o y 平面的同一点上，曲面的数学表示z = 厂( x ，y ) 为单值的。国内许多曲 面重建算法口“”4 】大多基于这种假设，实际上，由五坐标测量仪或c t 扫描仪测出 的数据不具有这种特性，是多值曲面，测量的数据是任意的。 2 被测对象是简单的、单个曲面1 6 “。实际中，这种简单的测量对象只占反求 工程应用的很小比例，而大量的是曲面复杂的对象，如在汽车、轮船、航空等领域 中的复杂物体，一个米老鼠的模具，人体内部的组织等。这些对象是无法用单一的 曲面所能表示的，需要用多个曲面表示，曲面的类型也不仅仅是简单的诸如平面、 圆柱面等，而是任意的不知道的自由曲面。 3 利用了测出的数据隐含有数据间相邻关系的特性。根据采集数据所采用的 机械驱动装置和数据采集原理的不同，采集到的数据分布有完全散乱和呈一定规则 分布( 如以图像形式、轮廓线及截面线形式等) 两种类型。完全散乱数据是指数据 没有任何规律、随意的，如随意地用坐标测量仪测出的数据。呈一定规则分布的数 据是指其测量过程是按照一定的路径测量的，其测量点之间的相邻信息也是显然 的，如按照轮廓或层面进行测量将得到一系列扫描线，每个扫描线包含一系列的点。 激光测量仪可以按照指定的网格扫描，c t 机是一层层地对测量对象进行扫描得到 图像，再从图像经过图像处理可以得到一系列的轮廓线。有些算法中利用了这种测 量数据有规律的特性，虽然在一个实际的应用领域中，这种假设可以提高反求过程 的效率，具有实际的应用意义，但对于完全散乱的数据则不能处理。 所有基于这些假设的反求方法，都具有一定的局限性。 1 3 2 数据组织的拓扑结构 在c a d 系统中，拓扑结构用来表示几何对象在逻辑意义上的组成及其位置关 华中理工大学博士学位论文 系。反求工程中拓扑结构用于将测量数据组织起来，为下一步的曲面重建准备。 对象数字化得到的散乱数据云通常没有点的相邻信息，所获取的数据可以是无 序的数据云，必须按照一定规则将这些数据组织起来，建立数据的拓扑关系，使得 每个数据将归属于拓扑结构中的一个曲面。常用的拓扑结构表示有两种：基于三角 域的表示和基于矩形域参数曲面的表示。 1 基于三角域结构 三角模型是一种常用的数学模型，特别是在计算机图形学和动画领域尤为重 要，受到人们的普遍重视，并且得到了长足的发展。这种模型是用一系列三角域的 曲面彼此相连将整个区域封闭起来，三角曲面包括三角形的b 6 z i e r 曲面、平面三角 形等。三角化过程实质上是用多面体模型来逼近和插值原始的散乱数据。三角形网 格生成技术发展到现在，已经出现了大量的不同实现方法。 d e l a u n a y 或改进的d e l a 岫a y 三角化算法，该类三角化算法是目前最常用的三 角化算法。d e l a u n a y 三角化技术发展到现在，已经出现了大量的不同算法。一般可 以将其分为三大类：( 1 ) 以b o w y e r 和g r e e n 、s i b s o n s 为代表的计算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 一7 7 】利用分治( d i v i d e - a 1 1 d - c o n q u a r ) 技术也提出了一种直接 计算v o r o n o i 图的方法。( 2 ) 以l a w s o n n ”9 】为代表的对角线交换算法的理论根据是 d e i a u n a y 三角化的空外接圆特性。该方法是步进的( i n c r e m e n t a l ) ，每引入一新点， 立即将其插入三角形中，并恢复d e l 籼a y 特性。( 3 ) w j t s o n 算法【“”，其理论基 础同样是基于d e l a 吼a y 三角化的空外接圆特性。虽然d e la _ u n a y 三角化方法在二维 平面区域问题中取得了相当大的成功，但在3 d 网格自动生成中却遇到了巨大困 难。在2 dd e l 蚴a y 三角化中，最大一最小角判据处处适用。但在3 d 情形，基于最 大一最小角判据的对角线交换规则不再成立，而基于外接圆判据的d e l 跏a y 三角化 一般也不再能保证生成的网格质量。遗憾的是，这是d e l a u n a y 三角化的本质弱点， 它贯穿于网格生成全过程，除非对d e l a u n a y 三角化概念本身予以修改队”j 。 另外s c l l r o e d e r 【8 8 】，h o p p e 【8 9 9 ”，r o s s i g n a c 【9 4 】，e c k ，v e r o l l l l e 和l e o n 【9 6 】 等人 在数据的三角化及优化方面做了很有意义的工作。h o p p e 提出用微切平面逼近三维 敞乱数据的三角形网格生成算法。该算法基于曲面形状信息反映在三维散乱点集 中，用三维点集中某点的邻域点集构造微切平面来近似表示该点处的局部形状，所 有点的微切平面集合则构成了待构曲面的近似表示。最后通过欧几里德最小生成树 对微切平面法矢方向进行调整使其达到整体致性。该算法从线性逼近的方向进行 了探索，即用三角形网格来近似表示三维散乱数据所表示的曲面，但并不要求散乱 华中理工大学博士学位论文 点为三角形网格中三角片的顶点。g u o l ”删在进行曲面拟合之前用q s h 印e s i ”1 的理 论获得近似多面体的拓扑结构。 可以看出，三角片的方法是一种“自底向上”的方法，如何自动得到三角片的 划分是拓扑结构产生的难点。这种模型首先侧重于对离散点的分割，试图通过对离 散数据的自动组织得到其拓扑结构，具有构造灵活、边界适应性好等特点，因此一 直受到广泛重视，在某些领域具有不可替代的作用。三角片的方法也具有一些缺点， 例如所产生的三角片的数目巨大、几何连续性差、与通用c a d c a m 系统接口不兼 容等问题。本文第二章将对三角片的方法进行更加深入的讨论。 2 基于矩形域参数曲面结构 目前，绝大多数c a d c m 系统都采用的是矩形拓扑结构的自由参数曲面， 因而三角曲面测量造型模块与普通曲面造型模块难以做到方法学上的统一，从而导 致两者不兼容。已有的c a d c m 系统已经发展了很长的时间，具有通用性好、可 靠性高等优点，已经为人们所普遍接受，它能够提供大量的现成的部件，对于提高 产品设计的质量和效率具有重要意义。采用基于矩形域参数曲面的拓扑结构重建出 的曲面与通用c a d c a m 系统兼容，可以直接输入到已有的c a d c a m 系统中， 进行二次设计和生产，达到真正意义的反求。 在c a d 领域，系统的高层几何模型主要有三种。”】，即线框模型、表面模型、 实体模型，另外还有特征造型、参数造型。而目前在通用、商业化的c a d 系统中， 具体实现中最典型的有二种表示方式：边界表示法b r e p ( b o l l l l d a r yr e p r e s e n t a t i o n ) 和几何体素构造法c s g ( c o n s t m c t i v es 0 1 i dg e o m e 仃y ) ，两种方法各有优缺点。一 般而言，c s g 模型被看作一个数学模型，主要解决工程中的许多数值计算问题， 而b - r e p 模型被看作一个拓扑模型，它正确地描述了物体边界上的面、环、边、点 的关系，在图形处理方面有明显的优势，支持对象的局部修改。目前，如何从大量、 任意、无规律的散乱点自动产生任意矩形拓扑结构是反求工程的难点，大多数关 于多个矩形拓扑结构曲面重建的研究工作都是由人工勾画产生散乱点的拓扑结构 【”3 。1 ，e c k l ”5 】和g u o 【”1 在这方面进行了一些研究工作。为了充分利用现有的 c a d c a m 技术，本文后续章节着重研究基于矩形域拓扑结构的自由曲面的重建问 题。在表示多个自由曲面的边界时，制定了一定的规则以保证拓扑结构的正确性。 1 3 3 曲面重建方法 根据拓扑结构的不同，曲面的重建方法也有所区别。 在三角域的结构中，曲面的重建主要为简单的三角形平面重建方法和三角域上 华中理工大学博士学位论文 b e z i e r 曲面重建方法。三角形平面重建中每个曲面都采用平面三角形，其解析表达 方法具有计算显示方便、快速的特点，被广泛应用于计算机可视化、动画、及医学 的某些领域。它的重建过程只需将产生的每个三角域用平面三角形覆盖，但重建出 的表面在三角片之间只有g o 连续，片内为一平面，不能满足人们对重建表面光滑 连续性的要求。 参数曲面具有能够表示任意曲面的特性，并且能够保证边界处一定的连续性， 国内外对三角域上b e z i e r 曲面进行了很多研究工作，1 9 7 7 年s a b i n 【1 首次给出了三 角域上b 6 z i e r 三角曲面的矢量形式。对于曲面片间的连续性问题，参数连续性对于 曲面的光滑性来说是过份的限制，几何连续性则是对参数连续性过份限制的松弛。 b a m h i l l 和f a r i n 用h e n n i t e 插值构造了九参数的三次b e z i e r 三角曲面，这种曲面 在整体上只能达到c ”连续【”7 。”】，后来a