（机械电子工程专业论文）多层次单元整体划分的曲面重构算法研究.pdf

多层次单元整体划分的曲面重构算法研究 张淑芹( 机械电子工程) 指导教师：牛文杰( 副教授) 綦耀光( 教授) 中文摘要 逆向工程技术是随着计算机技术的发展和成熟，以及数据测量技术的 进步而迅速发展起来的一种多学科的综合性技术。该技术已经广泛的应用 于计算机辅助设计、虚拟制造、生物医学、电影特效、非破坏性测试以及 教育等众多领域。在逆向工程技术中，模型的数字化和曲面重构是其关键 环节。 数据预处理是模型的数字化后必备的环节。本文在数据的预处理部分 主要研究了数据的平滑滤波、精减处理。以及数据的几种插值和拟合方法， 包括克里金插值法、距离反比加权法、薄板样条法、基函数法和最小二乘 拟合法：然后用程序实现上述几种数据插值和拟合的方法，经分析比较， 认为最小二乘拟合法是比较适合本课题的方法。 曲面重构算法是逆向工程中的另一个关键内容，本文研究了多层次单 元整体划分的曲面重构算法( 简称m p u 算法) 。针对该算法在编程实现时 需要采样点法矢的问题进行了分析研究，提出了采样点法矢计算和法矢一 致化调整算法；然后运用数据插值和拟合两种思路分别实现了曲面的重构， 并将插值和拟合后的重构结果进行了比较。 最后，本文给出了算法实现平台，运用v c 十+ 编程语言，建立了实现曲 面重构的软件系统，通过实验分析，得出该系统的可靠性。 关键词：逆向工程，数据处理，曲面重构，m p u 算法 t h er e s e a r c ho ns u r f a c er e c o n s t r u c t i o na l g o r i t h m o fm u l t i l e v e lp a r t i t i o no fu n i t y z h a n gs h u q i n ( m e c h a n i c a le l e c t r o n i ce n g i n e e r i n g ) d i r e c t e db ya s s o c i a t ep r o f e s s o rn i u w e n - j i ep r o f e s s o rq iy a o - g u a n g a b s t r a c t r e v e r s ee n g i n e e r i n gi san e ws u b j e c tc o m i n gu pw i t ht h ed e v e l o p m e n to f c o m p u t e rs c i e n c ea n dt h et e c h n o l o g yo fd a t am e a s u r e m e m a tp r e s e n t ，i th a s b e e nw i d e l yu s e di nc o m p u t e ra i d e dd e s i g n & m a n u f a c t u r e b i o l o g y & m e d i c a l e n g i n e e r i n g , f i l li n d u s t r yw i t l la n i m a t i o n , v i r t u a lm a n u f a c t u r i n g & e d u c a t i o n , n o n d e s t r u c t i v ed e t e c t ，a n ds oo n t h i sp a p e rb e g i n sw i ms o m eb a s i cc o n c e p t sa b o u tr e v e r s ee n g i n e e r i n g i t i n c l u d e sr e v e r s ee n g i n e e r i n g sr e s e a r c hi n t e r e s t s ，a p p l i c a t i o n s ，e t c i th a st w o i m p o r t a n tp a r t sw h i c ha r ec a l l e d t h e d i g i t i z a t i o n o fm o d e la n ds u r f a c e r e c o n s t r u c t i o n t h i sp a p e rm a i n l ys t u d i e st h e s et w oi s s u e s t h e r ei sa ni m p o r t a n ts t e pw h i c hi sc a l l e dd a t ap r e p r o c e s s i n g i ti st h ef i r s t s t e po fs u r f a c er e c o n s t r u c t i o n s od a t as m o o t hd e a l i n ga n dt h es i m p l i f y i n ga r e r e s e a r c h e di nt h es e c o n dc h a p t e r i n t e r p o l a t i o na n d f i t t i n gm e t h o d sa r ec o m p a r e d ， a n dc o n c l u d e st h eb e s to n ef i t t i n gf o rt h i ss u b j e c t a n o t h e ri m p o r t a n tc o g e n ti nr e v e r ee n 百n e e r i n gi ss u r f a c er e c o n s t r u c t i o n i tm a i n l yr e s e a r c h e st h ea l g o r i t h mo fm u l t i l e v e lp a r t i t i o no fu n i t yi nt h ef o r t h c h a p t e rs e c t i o n i ti sa l s oc a l l e dt h ea l g o r i t h mo fm p u i nt h i s s e c t i o ni th a s r a i s e dt w oa l g o r i t h m s o n ea l g o r i t h mi st h ec o m p u t a t i o no fn o r m a lv e c t o r , a n o t h e ri sa d j u s t i n gn o r m a lv e c t o rw h i c hi sb a s e dt y p i c a lp o i n t a tl a s t ，t w o m e t h o d sw h i c ha r ei n t e r p o l a t i o na n da p p r o x i m a t i o na l ea p p l i e dt oa c c o m p l i s h t h es u r f a c er e c o n s t r u c t i o n t h es o f t w a r es y s t e mi si n t r o d u c e da tt h ee n do ft h i s p a p e r ，w h i c hi s c o m p o s e db yv c + + i ti sc a l l e ds u r f a c er e c o n s t r u c t i o ns y s t e m i ti sp r o v e d r e a s o n a b l eb ye x p e r i m e n t s k e y w o r d s ：r e v e r s ee n g i n e e r i n g ，d a t ap r o c e s s i n g ，s u r f a c er e c o n s t r u c t i o n ， a l g o r i t h m o fm p u 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国石油大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 如1 年年月沙日 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： 妒7 年4 月日 毒二7 年尹月彦日 中国石油大学( 华东) 硕士学位论文 第1 章引言 笛1 童引言 1 1 课题来源和研究意义 当今世界已经进入信息时代，全球统一市场初步形成，国际竞争也愈 演愈烈：而制造业竞争尤为激烈，这就使得产品的更新换代越来越频繁， 以前的那种大批量、单一品种的生产方式已不能满足用户的需求。为了适 应快速多变的市场，需要在原有产品的基础上进行再设计和再创新，由此 逆向工程技术便逐渐发展壮大起来。 众所周知，日本经济在二战结束后几乎处于瘫痪状态，但是在随后的 三十年里，以惊人的速度一跃成为仅次于美国的世界第二大经济强国。究 其原因，在于他们采用了旨在引进国外先进技术的“吸收性战略”，即在 消化、吸收引进技术的基础上，采用移植、组合、改造等多种方法开发出 新产品，这样为日本节省了9 1 0 的研究经费和2 3 的研究时间，为只本赶超 其他国家提供了条件。 除了日本，世界其他各国7 0 左右的技术都是来自国外，他们运用逆向 工程技术，复现实物的c a d 模型，然后在此技术上进行再设计和再创新， 从而制造出新产品。总而言之，逆向工程技术不仅能够快速准确的复制原 实物，而且在逆向基础上进行的设计起点高，在较短的时间内就能创造新 的产品，由此得到了企业的青睐以及国家的重视。 在竞争愈烈的今天，针对我国企业在加入w t o 后参于国际竞争，对企 业的挑战不仅是成本低的产品，更重要的是更快的抢占市场的高质量产品， 逆向工程技术在此可以起到非常重要的作用。通过采用逆向工程技术，不 但可以极大地缩短产品开发周期，更重要的是可以快速赶上或超过世界先 进生产技术水平，揭开国外先进产品和设备的技术秘密，并找到原型产品 的缺点加以改进，加上c a d c a e c a m 以及r p m ( 快速成型制造) 的综合运 用，设计生产出更优质的产品，从而快速的抢占市场；同时，运用逆向工 程技术，为产品的仿制和改进提供了方便、快捷的工具，从而对缩短我国 与发达国家的产品设计、制造之间的差距也具有非常大的促进作用。 为此，本文对逆向工程技术进行了研究，重点研究了曲面重构算法。 该算法是逆向工程技术的核心内容，对逆向工程技术的发展有着重大的影 中国石油大学( 华东) 硕士学位论文 第1 章引言 响。曲面重构的概念自从9 0 年代被提出后，逐渐成为学者研究的热点，许 多专家在此方面也做出了卓有成效的贡献；但是应该看到，曲面重构算法 并没有形成一个系统的理论体系，许多算法中还存在着一些问题。例如算 法本身不成熟，算法的速度和精度在很多情况下达不到要求，以及没有系 统的重构软件等问题。这些问题的存在大大制约了曲面重构的发展，从而 制约了逆向工程技术的发展。因此加快对曲面重构算法的研究在当前很有 必要。 1 2 逆向工程应用概述 1 2 1 逆向工程含义 逆向工程技术( r e v e r s ee n g i n e e r i n g ，简称r e ) 是随着计算机技术的普及 和进步，以及计算机辅助设计与制造技术( c a d c a m ) 的迅猛发展而发展起 来的。它是一个多学科综合性的术语，是以设计方法学为指导，以现代设 计理论、方法、技术为基础，运用各种专业人员的工程设计经验、知识和 创造思维，对已有新产品进行解剖、深化和再创造，是已有设计的设计【l 】脚。 在制造业，逆向技术是根据实物模型和样件测量数据，建立数学模型，得 到其设计思想，从而进一步修改原有设计，然后将这些模型和表征用于产 品分析、制造和加工生产的技术1 3 】。随着数控测量技术的发展，这种技术己 被广泛应用于机械、轻工、航空、航天、造船、汽车和模具等现代制造业 的各个领域1 4 】。 从逆向工程的流程来看，它与传统的正向设计正好相反。传统的正向 设计过程首先是来源于一个设计思想，然后根据该思想建立几何模型，并 最终生产出产品的过程：而在逆向工程中，首先拥有的是一个物理或实物 模型，通过对它进行数据采集、曲面重构，最后得到它的几何模型。它们 的开发流程，如下图1 - 1 所示，从中可以具体的看到传统的正向设计和逆向 设计在产品开发流程上的不同。 2 中国石油大学( 华东) 硕士学位论文第1 章引言 ( a ) 逆向设计过程( b ) 正向设计过程 图1 i 逆向设计和传统的正向设计过程 1 2 2 逆向工程的分类 从工程技术角度看，逆向工程可以概括为实物反求、软件反求和影像 反求三类： ( 1 ) 实物反求 ， 它是在已有实物条件下，通过试验、测绘和详细分析，是再创造的关 键，其中包括功能反求，性能反求、方案、结构、材质、精度、使用规范 等众多方面的反求。实物反求对象可以是整机、部件组件和零件。 ( 2 ) 软件反求 产品样本、技术文件、设计书、使用说明书、图纸有关规范和标准、 管理规范和质量保证手册等均被称为技术软件。软件反求有三类情况：一 中国石油大学( 华东) 硕士学位论文第1 章引言 是既有实物，又有全套软件；二是有实物而无技术软件；三是无实物，仅 有全套或部分技术软件。 ( 3 ) 影像反求 既无实物，又无技术软件，仅有产品像片、图片、广告介绍、参观印 象和影视画面等，要从中去构思、想象来反求，称为影像反求。这是反求 中难度最大的。影像反求本身就是创新过程。目前还未形成成熟的技术， 一般要利用透视变幻和透视投影，形成不同透视图，从外形、尺寸、比例 和专业知识等很多方面去捉摸其功能和性能，从而分析其内部可能的结构。 1 2 3 逆向工程的组成模块 在机械制造业，逆向工程可谓是项浩大的工程，涉及到数据测量、数 据的预处理、曲线曲面的拟合、曲面的光顺等许多环节，其中有两个关键 的环节是任何一次逆向的过程中所不能缺少的，这就是数字化测量和曲面 重构。数字化测量是指样件表面的数据获取，通过一定的测量设备和测量 方法去获取实物表面离散点的几何坐标信息；而曲面重构是计算机的逆向 建模，指利用测量数据进行曲面和实体造型，以获得最接近于实物原型的 c a d 模型。 1 、数字测量 近十年来，随着传感技术、控制技术等相关技术的发展，出现了各种 各样的样件表面数字化方法。数据的采集方式主要有两种【5 】【6 】【7 1 ：一是传统 的接触式测量法，如三坐标测量机；二是非接触式测量法，如激光三角法、 图像法、距离法等。 接触式测量有点位触发式数据采集和连续式数据采集两种。其中触发 式数据采集以三坐标测量机( c m m ) 为主。采用该方法可以达到很高的测量 精度( ：t - o 5 m ) ，对被测物体的材质和色泽一般无特殊要求；连续式数据采集 采用了一个模拟量开关采样头，这种方法采样速度快，最高可达8 m m i n ， 数字化速度最高可达每秒5 0 0 点，精度可达3 叽m ，可连续采集数据，因而也 可用来采集大规模的数据，但由于同样是接触式测量，所以也具有触发式 测量方法的缺点。 非接触式数据采集，其测头不接触待测物体的表面，传递介质有激光、 声波、电磁场等，常见的是以激光为媒介的激光三角形法和激光成像法。 4 中国石油大学( 华东) 硕士学位论文 第1 章引言 它的特点是测量速度快，因而可以相当密集地对产品表面进行测量，形成 点云数据。工业中常用的非接触式数字化设备由激光扫描仪( l a s e r s c a n n e r ) 、激光三角测量仪、工业c t ( c o m p u t e dt o m o g r a p h y ) 、计算机断层 摄像和自动切层扫描仪等。 上述的各种数据测量手段都各有优缺点，分别适用于不用的场合，在 实际使用中可根据应用的领域、对测量精度、速度的要求以及被测对象的 特性加以选择。在一些情况下，一种扫描手段不能获得所需的所有数据， 可以辅以多种扫描手段。 2 、曲面重构 ( 1 ) 曲面重构的含义 曲面重构( 亦称曲面建模、曲面重建) 是实现逆向工程的另一个重要模 块。一般而言指从曲面上的部分采样信息恢复原始曲面的几何形状。具体 的说就是根据光学或机械数字点文件，准确生成模型的数学曲面模型的过 程，也称为曲面反演【8 】。这就意味着它有两方面的含义。第一，原有的曲面 是曲面重构的依据；第二，原有的曲面是衡量重构所得曲面质量好坏的标 准，要求所建的模型能够较好的表现原来的形状【9 j 。从它的这两方面含义我 们也可以看出，曲面重构的基本要求是准确易行。所谓准确：就是要求建 立起来的数学模型比较准确的反映原来曲面的形状，或者说能较好的逼近 原来的曲面：易行：要求对所建立的数学模型易于进行各种操作，或者说 较方便的适用于计算进行曲面的存储、分析、计算和绘制等。该项技术是 c a d 建立数学模型的一种不可缺少的部分，即通过对实物进行测量，产生 大量点测三维数据，利用c a d 软件对点测数据进行一定的运算处理，最后 生成曲面模型，保证曲面模型达到实物各方面的要求，使曲面模型成为实 物的设计与制造的最终依据。 近几年来，由于计算机辅助设计与图形学的发展，曲面重构得到了更 广泛的研究和应用，几乎涉及自然科学与工程技术的一切领域。如汽车、 飞机、轮船等工业领域；基于地震勘探数据或测井数据的地质勘探领域： 依据大量数据计算和计算结果分析的气象领域：分子模型构造领域：需要 实现形体的网格划分及结果数据的显示、优化的有限元分析；根据测量数 据建立人体以及骨骼和器官的计算机模型在医学、定制生产等许多方面都 中国石油大学( 华东) 硕士学位论文第1 章引言 有重要意义和实用价值【l o l 。 ( 2 ) 曲面重构的分类 曲面重构的方法很多，每年举行一次的国际图形学会议都有此方面的 新算法推出，在计算机图形学的刊物上也有新方法与算法的介绍，并且随 着研究的深入，曲面重构算法逐步走向完善。本文总结了目前世界上存在 的曲面重构算法，将它们归纳并分类。 根据重构曲面与数据点集之间的关系可分为插值法和逼近法。前者得 到的重建曲面完全通过原始数据点，属于计算机图形学的领域；而后者则 使用分片线性曲面或其他形式的曲面来逼近原始数据点，属于计算几何的 领域。根据重构曲面的表现形式不同又可以将它分为五种j ：分片线性曲 面重构、参数曲面重构、隐式曲面重构、变形曲面重构和细分曲面重构。 我们就这五类曲面重构方法作一下总结。 a 分片线性曲面重构：分片线性的曲面又称为网格曲面，随着计算机技术 的发展，越来越多的工程应用的数据输入输出采用多边形表示模型：另一 方面，网格曲面也更加有利于曲面的计算机显示。因此，在曲面重构领域 中，网格曲面方法即三角片曲面重构方法正成为研究的一大热点。其中， 基于v o r o n o i 图和d e l a u n a y = 角化的方法是由散乱点重构三维网格曲面的主 流算法。 b 参数曲面熏构：长期以来，参数曲线曲面一直是描述几何形状的主要工 具，基于参数曲面的重建方法也是曲面重建中常用的方法。它是通过定义 函数厂将二维参数域dcr2 映射到三维空间r3 ；参数化表示具有许多优 点。如计算曲线曲面的几何量简单，曲线曲面的显示方便，具有离散性等 优良性质。 c 隐式曲面重构：参数化曲面重构有如上所述的优点，但也有缺点，如判 断一个点是否在曲线或曲面上以及在哪一侧时，参数表示曲面极为不便； 但隐式化表示给这些操作带来了极大的方便，它是通过定义函数厂： r 3 寸r ，以保证离散点集v = v 以 逼近函数的零集z ( 门；同时隐式化 表示在曲线曲面求交方面也有极其重要的应用。因此，在曲面重建中，也 越来越多地使用曲线曲面地隐式化表示。 6 中国石油大学( 华东) 硕士学位论文第1 章引言 d 变形曲面重构：许多复杂曲面都是由多张曲面拼接而成，无法用一张参 数曲面或隐式曲面将其重构出来，变形曲面重构技术通过事先确定一个初 始拓扑结构，构造一个初始曲面，让它沿着一定的方向进行形变，得到最 终的重构曲面。 e 细分曲面重构：为了解决具有复杂拓扑形状的曲面重构问题，学者提出 并发展了细分曲面重构方法。细分曲面是一类采用组成曲面的多边形网格 的点、线、面及拓扑信息完整地描述的曲面。它从初始多面体网格开始， 按照某种规则，递归地计算出网格上的每个顶点。这些顶点都是原网格上 相邻的几个顶点的加权平均。随着细分的不断进行，控制网格被逐渐磨光， 在一定条件( 一定的细分规则) 下，细分无穷多次之后多边形网格将收敛到 一张光滑曲面。 1 3 国内外研究现状及分析 逆向工程技术的方法在产品设计中早有应用，只是近年来随着计算机 辅助设计和辅助制造的发展，以及数字化快速测量和快速制造设备的发展， 逆向工程技术的应用领域越来越广，特别是在工程领域内有着广泛的应用。 除了在汽车、造船、航空、模具制造等行业广泛应用外，也涉及到了娱乐 方面、电影特效与计算机动画、虚拟现实与教育等，当然逆向工程在生物 医学领域的应用价值日益增大，比如人体的骨骼、关节的复制，以及假肢 的制作等等【1 2 】【1 3 1 。 1 3 国外研究现状与分析 逆向工程技术最初是在2 0 世纪8 0 年代分别由美国的3 m 公司、日本的名 古屋工业研究所，以及美国u v p 公司提出并研制开发的。进入2 0 世纪9 0 年 代后。逆向工程得到了大幅度的发展，在全国建立了集测量、设计、快速 成型、快速模具、数控加工于一体的逆向工程系统应用中心，为中小企业 提供技术服务，有效地提高了中小企业的竞争力，促进了生产力的发展。 在现代产品设计与制造中发挥越来越重要的作用。 不仅如此，逆向工程也得到了国际学术界的高度重视，一些重要的国 际学术会议都将逆向工程及相关技术讨论作为了一个重要的会议专题。例 如面向逆向工程的国际会议w c r e ( t h ew o r k i n gc o n f e r e n c eo i lr e v e r s e e n g i n e e r i n g ) 、i w p c ( t h ei n t e r n a t i o n a lw o r k s h o po np r o g r a mc o m p r e h e n s i o n ) 7 中国石油大学( 华东) 硕士学位论文第1 章引言 和p s a t e ( t h ew o r k s h o po np r o g r a ma n a l y s i s f o rs o f t w a r et o o l sa n d e n g i n e e r i n g ) ，这些会议都是每年举行一次【1 4 l 。卡内基梅隆大学软件工程研 究所成立了专门的逆向工程中心，致力于逆向工程的研究。i b m 研究中心 ( i b m r e s e a r c h ) 设立了“软件工程中关注点的多维分解”研究项目，研究工 作已经进行了多年。 由于逆向工程相应设备和研发中心的建立，一些专门的逆向软件也相 继出现，如美国的i m a g e w a r e 公司开发的产品s u r f a c e1 0 5 、英国d e l c a m 公 司的产品c o p y c a d 。当然在一些流行的c a d c a m 软件中也开始集成了这 样类似的模块，如u n i g r a p h i c s 中的p o i n t c l o u d 功能、p r o e n g i n e e r i n g 的 p r o s c a n 功能。日本开发了从m r j 、c l 重构三维实体的软件；英法等国将 扫描数据在数控设备上复制；美国开发了c i 可视化的可转成i g e s 的软件。 总之，作为一种现代产品开发手段，逆岛工程己经越来越多地受到各 国的重视。目前，在美国、英国、德国、日本、以色列、法国、意大利、 韩国等国家和地区都已经建立了商品化的逆向工程设备和软件系统。 1 3 2 国内研究现状与分析 与国外的逆向工程发展现状相比，国内的逆向工程起步比较晚，起初 只是在几所学校和科研所进行研究，创新性的研究不多且多数处在实验 阶段，很少用于实际生产中。例如浙江大学开发的逆向工程c a d 软件 r e s o f t 和西北工业大学的实物测量造型系统n p u s r m s ，都属于单向的集 成系统，即通过模块化的方式把逆向工程中涉及的一些主要技术予以实现， 上述系统的先天不足是把实现数字化的过程作为一个独立的过程，没有考 虑以后的数据处理和曲面重建等要求，同时也缺乏自主的c a d c a m 软件的 支撵和上游测试设备的驱动支持。所以这些软件只能应用于一些简单的设 计。 进入9 0 年代中后期，随着逆向工程在中国的迅速发展和推广，一些科 研成果也随之诞生，参与逆向工程研究的大学也比以前增多，如清华大学、 天津大学、华中理工大学、浙江大学、同济大学、西安交通大学等都建立 了逆向工程相关实验室，弓i 迸了逆向工程相应设备，并取得了一定的科研 成果，且大部分应用到了实践当中。其中较有代表性的有西安交通大学 c i m s 中心的面向c m m 的逆向工程测量方法和基于线结构光视觉传感器的 中国石油大学( 华东) 硕士学位论文第1 章引言 光学坐标测量机的研科1 5 】 16 】：上海交通大学国家工程模具中心的集成系统 和自动建模技术：浙江大学化工机械研究所的c m u c a d 数据交换技术 f l 】【17 】【1 8 】；南京航空航天大学c a d c a m i 程研究中心的基于海量散乱点三角 网格面重建和自动建模方法【2 0 】；华中科技大学的曲面测量与重建和西北 工业大学的数据点处理、建模等技术剐 2 2 】。 总而言之，逆向工程技术在我国研究和开发正如雨后春笋般地发展开 来。当然，我们也得看到，逆向工程技术在我国还没有真正形成集开发和 生产于一体的经济实体。因此，如何将逆向工程技术应用于创新设计，还 有待于我们的继续努力。 1 4 本文所研究的内容 逆向工程技术中的两个关键环节是数字化测量和曲面重构，本文在充 分分析这个两个关键环节的研究现状的基础上，重点研究了以下内容：一、 数据的预处理，在数字化测量后得到的数据往往不能直接进行曲面重构， 本文针对数据中含有噪声或误差，研究了数据的平滑滤波处理；针对数据 的稠密与稀疏，研究了数据的精减和插值与拟合处理，并将这几种数据处 理方法分别用程序实现，在分析比较结果的基础上得到最适合本论文的一 种方法；二、研究了多层次单元整体划分的曲面重构算法( 简称为m p u 算 法) 。给出了采样点法矢的计算方法和法向一致化算法，并运用m p u 算法， 编程实现模型的重构，编写了相应的曲面重构软件。本论文结构如下： 第一章：引言。 第二章：逆向工程中点云数据的处理。 第三章：曲面重构的算法，重点是隐式曲面的重构算法。 第四章：多层次单元整体划分的曲面重构算法。 第五章：结论与展望。 1 5 本章小结 本章主要论述了本课题的来源和研究意义，以及逆向工程的含义、产 生以及发展状况：重点研究了逆向工程的组成模块，主要是数据测量和曲 面重构；从而进一步引出本文的研究重点，即数据预处理和曲面重构算法 研究；最后给出了本文的结构。 9 中国石油大学( 华东) 硕士学位论文第2 章逆向工程中点云数据的处理 第2 章逆向工程中点云数据的处理 2 1 引言 无论哪一种数据测量方法，对模型测量后都会得到大批的点云，而且 任何一种测量方法都不可避免地会出现一些误差，所得到的采样点集并非 会完全落在原始物体上；此外，由于众多测量设备的局限性，要获得物体 的完整采样，单纯的固定物体和设备，从一个方向进行采样是不可能的， 这就需要在扫描过程中，调整物体位置或者旋转激光头的角度，得到多张 视图数据，然后通过点的聚合，对它进行拼接，从而得到完整的采样数据 点集。由于上述几种情况的存在，需要对数据点进行平滑滤波、精减，以 及插值与拟合等预处理，以便于后面进行三维物体的曲面重构。 2 2 点云数据的处理方法 2 2 1 数据的平滑滤波 在测量数据的过程中，由于受外界因素的影响，所得数据不可避免的 带有噪声；同时也受人为或者一些其它因素的影响，数据中也会带有一些 误差，尤其是在尖锐边和曲率变化比较大的区域所测得数据。所以为了使 后面的曲面重构结果比较真实地反映原模型，需要对原始采样数据进行平 滑滤波处理。 1 、平滑处理方法 平滑处理方法主要有：平均法、五点三次平滑法和样条函数法。常用 的是平均法，它包含以下三类： ( 1 ) 简单平均法，其计算公式为： p 2 赤罾( 喇叫 ) 当n = i 时，为三点简单平均；当n = 2 时，为五点简单平均。 ( 2 ) 加权平均法，取滤波因子为h ( i ) = | l l ( 一) ，旃( 0 ) ，_ l l ( ) 】，要求 乏：厅( 甩) = l ( 2 2 ) h ：= 知 ( 3 ) 线滑动平均法，利用最i b - - 乘法原理对离散数据进行线性平滑的方法， 即为直线滑动平均法。其三点滑动平均的计算公式为： 中国石油大学( 华东) 硕士学位论文第2 章逆向工程中点云数据的处理 p = ；( p h + p ，+ p 川) ( f = 1 ，2 ，m 一1 ) 1 只2 言( 5 岛+ 2 p l p 2 ) ( 2 3 ) 只= ( p ，一2 + 2 p ，一l + 5 p 。) o 其中尸的滤波因子为： ( f ) = 【 ( 一1 ) ， ( o ) ，而( 1 ) 】= ( 0 3 3 3 ，0 3 3 3 ，0 3 3 3 )( 2 4 ) 2 、点云的滤波 点云的滤波主要有如下三种方式： ( 1 ) 中值滤波法，这种方法是将相邻的三个点取平均值来取代原始点，实现 滤波。假设相邻的三个点分别为，墨和x ：，那么通过中值滤波法平滑得到 的新点x l = ( x 。+ x 4 - x ：) 3 。因为这种滤波方式是对采样点的值取滤波窗 口内各数据点的统计中值，因此其消除数据毛刺的效果较好，但是会跟原 始数据差距较大，所以本文不选用这种滤波方法。 ( 2 ) 平均值滤波法，这种方法是将采样点的值取滤波窗1 ：3 内各数据点的统计 平均值来取代原始点，改变点云的位置，使点云平滑。 ( 3 ) 高斯滤波法，这种方法是以高斯滤波器在指定域内将高频的噪声滤除。 高斯滤波法在指定域内的权重为高斯分布，其平均效果小，在滤波的同时， 能较好的保持原数据的形貌，因而这种方法被常用。 图2 1 表示三种滤波方法各自的效果。其中四幅图分别代表原始点集， 中值滤波的效果图，平均值滤波的效果图，以及高斯滤波的效果图。本论 文采用的方法是高斯滤波法。 ( a ) 原始点集( b ) 中值滤波 中国石油大学( 华东) 硕士学位论文第2 章逆向工程中点云数据的处理 ( c ) 平均滤波( d ) 高斯滤波 图2 1 各种滤波方法比较 2 2 2 数据的精减 在数据的测量过程中，由于人为的操作，往往会造成大量的冗余数据。 这样对后面的重建工作带来了困难，所以需要按一定要求去除重复数据； 同时将一些对重建结果影响不大的数据点，也要相应的去除。 对于数据精减的研究，有很多处理方法。如f u j i m o t o 和k a r i y a 于1 9 9 3 年 提出了一种保证减少数据点的误差范围处于给定的角度和距离公差范围内 的精减方法；m a r t i n 等人于1 9 9 6 年提出了一种均匀网格减少数据的方法，这 种方法是选择广泛用于图像的处理过程的中值滤波来实现数据的精减。这 种方法克服了均值和样条曲线简化的阻滞，但是其不足在于所用的均匀化 网格对捕捉产品的外形形状不敏感；v e r o n p 和l e o n j c 于1 9 9 7 年提出用误 差带( e r r o rz o n e s ) 减少多面体的数据点的方法田】：c h e n y h 于1 9 9 9 年则提出 了一种通过减少多边形和三角形，从而达到减少数据点的目的口j 。 上述这几种方法都有个缺陷，就是没有考虑扫描设备的特性。其实不 同类型的点云可采取不同的精减方式。对于扫描线点云，其中使用较多的 有取样法、弦差分法、包围盒法等。取样法根据统计概率的方法随机决定 数据去留，其简化程度小，随机误差大；弦差分法利用最大偏差值和最大 点间距构成的圆柱形“管道”进行数据筛选，适合于空间散乱数据点的精 减；包围盒法用选定的一个四边形或正方形构成一个包围盒，来筛选盒内、 外平面或空间数据，其简化速度快，算法简单，但适用于曲面的曲率变化 较平缓、附加特征少的情况。 激光扫描测量得到的数据通常都是按扫描线进行存储的，这些点在扫 描线上的分布密度很大，但每条扫描线之间的间距较大，因而如果单独用 角度阀值来进行数据精减，当两个相邻点相距较远时，即使夹角很小，弦 高也可能很大，这时不能单凭角度小就将其剔除：另外，当两个相邻点相 中国石油大学( 华东) 硕十学位论文第2 章逆向工程中点云数据的处理 距较近时，弦高很小也可能有较大夹角，这时也不能由于夹角大而将其保 留。因此，采用给定的角度误差和弦高误差两个方面的限制，可以克服上 述缺陷，快速有效的精减数据。 2 3 数据的插值与拟合处理 由于在数据测量过程中会造成部分数据的缺失或者稀疏，如果不对这 些缺失数据的部分进行处理，则会影响后面曲面的重构。本文从缺失数据 所在部位与周围曲面之间存在连续性出发，根据周围的采样点来对缺失数 据进行插值。在本文中，主要运用了克里金插值法；而对于数据比较稀疏 的部分，可以采用数据插值法，也可采样拟合的方法。由此本文运用了几 种数据拟合的方法，主要运用了距离反比加权法、薄板样条法、基函数法， 以及最小二乘拟合法，将这几种方法分别用程序实现，并通过实例比较得 出它们各自的优缺点，以及它们分别所适应的情况。 2 3 1 插值与拟合算法的实现思想 1 、克里金插值：此方法是建立在变异函数理论及结构分析基础之上的。通 过引进以距离为自变量的变异函数来计算权值，这既能反映变量的空间结 构特性，又能反映变量的随机分布特性。从统计意义上讲，它是从变量相 关性和变异性出发，在有限区域内对区域化变量的取值进行无偏、最优估 计的一种方法；从插值角度来讲，它是对空间分布的数据求线性最优估计 的一种方法。当变异函数和相关分析的结果表明区域化变量存在空间相关 性时，则可以运用克里金法对空间未采样点或未采样区域进行插值估计。 本文所用的是方法是普通克里金插值法。其思想是，设研究区域为a ， 区域化变量( 即研究的物理属性变量) z c x ) a ，x 表示空间位置，z ( x ) 在采 样点x i ( i = l 2 n ) 处的属性值( 或称为区域化变量的一次实现) 为 z ( x i ) ( i = l 2 n ) ，则根据普通克里金插值原理，为采样点x o 处的属性值z ( x o ) 估计值是n 个已知采样点属性值的加权和，即： z ( x o ) = 4 z ( _ ) ( f = l ，2 ，：册) 为待求权系数 ( 2 5 ) i - 1 假设区域化变量z ( x ) 在整个研究区域内满足二阶平稳假设： ( 1 ) z ( x ) 的数学期望存在且等于常数：e z ( z ) 】= 肌( 历是常数) ； 中国石油大学( 华东) 硕士学位论文第2 章逆向工程中点云数据的处理 ( 2 ) z ( x ) 的协方差c o v ( x 。，x ，) 存在且只与两点之间的相对位置有关； ( 3 ) e z c x ，) 一z ( x ，) 】= 0 ； ( 4 ) 增量的方差存在且平稳：v a r z ( x ，) - z ( x 川= e z ( x ，) 一z ( x 埘2 。依据无 偏性要求：研z + ( x 。) 】- e z ( x o ) 】经推导可得：a ，= 1 ，在无偏条件下使 f t i 估计方差达到最小，即： m i n v a r z + ( x o ) 一z ( x o ) 卜2 ( 丑一1 ) ) ，其中：为拉格朗日乘 j - l 子。 可求解权系数 ( f _ 1 , 2 ，坍) 的方程组： ，善，) 一声= c o v ( x o ，t ) i = 1 , 2 ，疗 ( 2 6 ) 求出诸权系数 ( f = 1 , 2 ，”) 后，就可求出为采样点x o 处的属性值z + ( x 0 ) 。 2 、距离反比加权法：此方法是曲线拟合的重要方法，其基本思想是设空间 散乱点q i ( x i ，y i ，z o ( i = l ，2 ，n ) ，待求点的属性值是其邻域内已知散乱点属 性值的加权平均，权的大小与待求点与邻域内散乱点之间的距离有关，是 距离的k ( o k 2 ) ( k 一般取2 ) 次方的倒数。即： z e = ( 2 7 ) 其中：4 = 舨i j 历f 夏而表示待求点与其邻域内第i 个点之间的 距离；k 是距离的幂，幂越高，拟合结果就越具有平滑的效果。 3 、薄板样条法：这种方法是将拟合过程形象地模拟为一个很薄的金属薄板 在点的约束下扭曲变形，并且该板具有最小的弯曲能量，即使下面的泛函 表达式具有最小值： 1 4 中国石油大学( 华东) 硕士学位论文第2 章逆向工程中点云数据的处理 舻) = l ：略) 2 + 2 酝) 2 + 等) 2 蚴 ( 2 8 ) 此概念首先是由j d u e h o n 在1 9 7 6 年提出，薄板样条函数要求是，在散乱 数据的所有拟合函数中，要求函数的曲率积分在整个定义域上最小，而二 维薄板样条函数进行光滑曲面拟合次数较低，局部性好。 薄板样条函数可以用来表示多维空间曲面，现在已被广泛的应用于地 球物理科学中的重力场分析、指纹模型研究、医学研究、等高线拟合等。 本文中对它的定义如下： 设t i ，t 2 t 3 t n 为r z 上的节点，引入一个非线性函数： f1，r 0 叩( ，) ： 而r 1 0 9 r( 2 9 ) 【0 ，：0 另外，r 2 上有节点t i 的坐标( x ，y ) ，在心上定义三个函数： 磊( f ) = l ，政( ，) = x ，4 3 ( t ) = y ，这样定义之后，任意线性函数都能表示为矿的 线性组合。 设有三行n 列的矩阵t ，其元素为乃= 力以) ；即： r * 沿吲 用00 表示二维空间的欧氏范数，即1 i t l l 2 = ，t 。 j = 【4 ，8 2 ，吒】7 ，及a = 【a ，a 2 ，a 3 】7 ( 2 1 0 ) 选择合适的常数 ( 2 1 1 ) ，( 0 = f ( x ，y ) = 最玎锥一f ) + 巳丸( f ) ( 2 1 2 ) i = 1 j = l j 2 n 2 1 2 式称为点集 f ，”上的薄板样条函数。要计算2 1 1 式的待定常 数，则需要定义矩阵e ， e v2 ，7 啡- - i s d = 击0 l ，- - t s l 2 毗o , l l - t s r ( 2 1 3 ) 然后由下面2 1 4 式线性方程组解得： 中国石油大学( 华东) 硕士学位论文第2 章逆向工程中点云数据的处理 e r 丁0 7 j l a 占j = ； ，其中z = c z ，z ：，z 。r 4 、基函数法： f ( x ，y ) = a k h k ( x ，y ) + b k q 。( x ，) ，) 式中，q k ( x ，力是一个多项式基，对于上式的系数吼，b k ， 程组的解来确定： 口，h j ( x y ) + 6 ，q ，( ，y ，) = z i = l n ( 2 1 4 ) ( 2 1 5 ) 应由下列方 ( 2 1 6 ) q q ，( x ，m ) = oj = l n( 2 1 7 ) i = l 5 、最d x - 乘拟合法：最小二乘法是曲线拟合的重要方法。其基本思想如下： n 次参数( n 1 ) 多项式曲线，( f ) = 口m a t ) ，其中纯( f ) ( f _ o ，l ，疗) 是n 次多项 ，1 0 式空间的一组基，a ，= k ，y ，z 】( f = 0 , 1 ，1 ) 为待定的系数矢量，设给定的数 据点为只= k ，y k ，气】( 七= o ，1 ，肌) ，而相应的参数是f o t l 。作为拟合 函数，有下列线性方程组口，纯( “) = 只( 七= 0 , 1 ，脚) ，写成矩阵形式为： t - o 削= p 其中系数矩阵为： 西= q o o ( t o ) 仍( t o ) ( 岛) ( a o ( t 1 ) 纯( ，i ) 纯( f 1 ) 吒) 仍( t 。) ( f 。) 为沏+ 1 ) 0 + 1 ) 阶矩阵 a =p = 只 只 p 册 6 ( 2 1 8 ) ( 2 1 9 ) 中国石油大学( 华东) 硕士学位论文第2 章逆向工程中点云数据的处理 这里矢量方程个数m + l 超过了位置矢量个数n + 1 ，这样的方程组称为矛 盾方程组，在一般情况下解是不存在，即不存在严格依次通过这些数据点 的插值曲线p ( t ) 。这时，只能寻求在某种意义下最接近这些数据点的参数多 项式曲线p ( t ) 作为逼近曲线。我们要求p ( t ) 上具有参数值t k