（计算数学专业论文）基于三维散乱点的曲面重建和边界检测问题研究.pdf

基于三维散乱点的曲面重建和边界检测 摘要 近年来随着激光和结构光等三维数据采样技术和硬件设备的日益完善，随着 计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着c a d c a m 或者其它快速成型技术的需求，三角形网格生成成为三维重建这一研究领域的热 点之。 三角形网格生成的基本思想是对从三维测量得到的离散数据或造型软件的 输出结果进行处理，形成规范和通用的数据格式，去除冗余信息而又保证模型的 准确度，以利于图形显示的实时性、数据存储的经济性和数据传输的快速性。 本文在总结了国内外一些经典的由海量离散数据点进行曲面重建的算法的 基础上，对一类曲面重建的算法中具有一般性边界检测问题进行了研究，提出了 两个边界检测算法。本文的内容是这样安排的： 第一章：绪论，对曲面重建的一般背景和应用作了简介。 第二章：计算机辅助几何设计和反向工程理论基础。 第三章：本文的算法是建立在三角剖分、自由曲面的理论基础之上的，本 章重点介绍了这些理论。 第四章：对国内外一些经典的由海量离散数据点进行曲面重建的算法进行 了总结和阐述。 第五章：基于a l g o r r i s c h m i t t 曲面重建方法，提出了两个边界检测算法。 关键词：计算机辅助几何设计，反向工程，曲面重建，边界检测， 三角剖分 大连理工大学硕士学位论文 a h s t r a c t w i t ht h er e c e n t d e v e l o p m e n t o f3 dd a t ac o l l e c t i o n t e c h n o l o g i e s a n d h a r d w a r e f a c i l i t i e s ( e g 1 a s e r a n ds t r u c t u r e d l i g h t ) ，t h eh i g h e rr e q u i r e m e n t s o f a u t h e n t i c i t y , r e a lt i m ea n di n t e r a c t i o no fc o m p u t e rg r a p h i cv i s u a l i z a t i o n ，t h ed e m a n d s o fc a d c a ma n do t h e r q u i c km o l d i n gt e c h n o l o g i e s ，t h et e c h n o l o g yo f t r i a n g l em e s h g e n e r a t i o nh a v eb e c o m e o n eo f t h eh o t s p o t si nt h ef i e l do f 3 dr e c o n s t r u c t i o n t h eb a s i ct h o u g h to ft r i a n g l em e s hg e n e r a t i o ni st op r o c e s sd i s p e r s ed a t a p o i n t so b t a i n e db y3 d m e a s u r e m e n to rt h eo u t p u tr e s u l t sf r o mm o l d i n gs o t h , v a r et o g e n e r a t ed a t ai na s t a n d a r da n dc o m m o nf o r m a t ，w i p eo f f t h er e d u n d a n ti n f o r m a t i o n w h i l ea tt h es a m et i m eb yk e e p i n gt h ea c c u r a c yo ft h em o d e lt og u a r a n t e et h er e a l t i m e g r a p h i cv i s u a l i z a t i o n ，t h e e f f i c i e n to fd a t a s t o r a g e a n d q u i c k n e s s o fd a t a t r a n s m i s s i o n t h i st h e s i ss u m su ps o m ec l a s s i c a la l g o r i t h m so fs u r f a c er e c o n s t r u c t i o nw i t h v a s td i s p e r s ed a t a ，f o rt h eg e n e r a lp r o b l e mo fs u r f a c er e c o n s t r u c t i o n ，w ep r e s e n tt w o b o u n d a r yd e t e c ta l g o r i t h m s a n da p p l yi na l g o r r ia n ds c h m i t t 担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 t h em a i n c o n t e n to f t h i sp a p e ri sg i v e ni nt h ef o l l o w i n g ： t h ef i r s tc h a p t e r ：i n t r o d u c t i o no f s u r f a c er e c o n s t r u c t i o na n di t sa p p l i c a t i o n t h es e c o n dc h a p t e r ：c a g da n dr e v e r s e e n g i n e e r i n g t h et h i r dc h a p t e r ：a st h ea l g o r i t h m si n t r o d u c e dh e r ed e p e n d so nt h ed e l a u n a y t r i a n g u l a t i o n 、f l e e f o r ms u r f a c e ，t h i sc h a p t e rc o n c e n t r a t e do nt h ei n t r o d u c t i o n o f t h e s et h e o r i e s t h ef o u r t hc h a p t e r ：s o m ec l a s s i c a la l g o r i t h m so fs u r f a c er e c o n s t r u c t i o nw i t h v a s td i s p e r s ed a t aa r es u m s u p t h ef i f t hc h a p t e r ：w ep r e s e n tt w ob o u n d a r yd e t e c ta l g o r i t h m s ，a n da p p l yi nt h e a l g o r r i s c h m i t t 担s u r f a c er e c o n s t r u c t i o ns c h e m e k e y w o r d ：c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，r e s e r v ee n g i n e e r i n g ，s u r f a c e r e c o n s t r u c t i o n ，d e l a u n a yt r i a n g u l a t i o n 3 大连理工大学硕士学位论文 第一章绪论 近年来，随着相关技术的进步，光学三维传感的研究重心正在向实现复杂、 大面形物体和非实验室环境下的测量转移。相应地提出了多次测量的视点规划、 多幅测量数据的融合、被测物体曲面重建和海量数据的存储、压缩与显示等问题。 这些问题的出现使得光学三维面形测量已不再仅仅是光学工程中的一个研究方 向，它需要借助计算机图形学( c g ) 、计算机辅助设计( c a d ) 和计算机视觉( c v ) 等 学科领域内的原理与方法。三维物体形状的数字化是计算机图形学、计算机视觉、 虚拟实现等领域的关键技术，在机械制造( c a d c a m 、反向工程、快速成型) 、虚 拟现实、生物医学、影视特技等行业有着广泛的应用。一般情况下，三维物体形 状的数据都是通过物体形状测量设备获得，这些数据点点集可分为两种形式：即 散乱数据和结构数据。散乱数据仅包含点在空间的位置信息，有时也称为“点云”， e h - - 维测量仪等得到，重构时没有任何附加信息可以利用，是一种最通用的数据 形式；结构数据除了含有点在空间的位置信息以外，还含有其它附加信息，如由 c t 、m r i 等采集的数据，数据点之间在重构时有邻接关系等拓扑信息可以利用。 从离散点点集重构曲顽网格的任务是找到物体的一种描述，这种描述不仅要包含 曲面上的点，而且还要包含点与点之间连接关系之类的拓扑信息。在选择重构算 法时应该考虑以下几个问题：1 ) 数据形式；2 ) 网格是逼近数据点，还是插值于数 据点：3 ) 网格的拓扑要求；4 ) 算法是基于体的方法，还是基于面的方法。 1 1 应用领域 光学三维面形测量在许多领域如：反向工程、工业检测、虚拟仿真、文化遗 产保护、医疗和面向个体消费者的量身定做服装和量脚制鞋等领域都已经得到应 用下面对这些应用作简单介绍。 反向工程 一 反向工程( r e v e r s ee n g i n e e r i n g ) 的出现出于以下两种需要：( 1 ) 某些产品采 用手工设计即可满足实际需要，或在计算机出现以前相关的工艺和技术就己成 熟出于降低人力成本和缩短产品周期考虑，需要引入c a d c a m 技术但产品设 计并不是全部用c a d 软件来完成，而是在现有的产品模型基础上做一些局部修 改例如：在制楦业中，新款式楦型的开发和设计基本上都是采用手工方式完成 的，一种可行的c a d 应用方案是：先对已有的各种款式鞋楦进行数字化，然后用 基于三维散乱点的曲面重建和边界检测 c a d 软件完成进一步的细节调整，直至最后用数控刻楦机加工出母檀( 2 ) 某些根 据人体工学原理设计的产品，先用手工方式设计出一个模型后，根据实际使用时 的舒适度对模型进行修改如此反复，直到得到满意的模型然后将模型数字化， 再用c a d 软件进行后续设计和分析，整个过程比完全采用c a d 软件设计更为有效 工业检测 计算机辅助制造( c a m ) 是实现大规模部件生产的有效途径，部件模型数据的 获得可以采用c a d 软件设计或对已有模型进行数字化得到最终生产出的部件和 原始模型之间的差异必须控制在允许的范围之内，差异发生的位置和大小的精确 确定需要对实际生产部件进行数字化处理对汽车车身的检测是光学三维面形测 量的一个成功应用 虚拟现实 影视特技中需要生成逼真的三维效果，而且随着硬件和互联网技术的不断发 展，游戏和虚拟现实在向交互式三维场景发展对于人体和复杂物体，现有的三 维c a d 软件缺乏有效的自由曲面设计手段，获得更为逼真的三维效果和三维场景 的一种可行的方法是对真实物体数字化。进行曲面重建处理后，通过纹理绘制生 成所需要的三维效果。 文化遗产保护 博物馆中的器物和野外的石刻是不可再生的历史文化资源，研究人员和爱好 者不得不到馆藏地和文物所在地才能对它们进行研究和欣赏而随着时间流逝和 社会的变迁，部分文物将不可避免地永远消失对这些文物进行数字化处理以后， 人们可以通过互联网欣赏到所喜爱的文物，研究人员通过计算机可以进行远程协 作研究。 医疗、整形 在医疗修复术中，在获取病人待修复部位的精确三维面形数据的基础上，医 生可以做到针对每个不同病人和不同的修复部位外形选择最佳的修复方案人体 整形手术中，通过对待填充部位的数字化，病人在手术前就可以观察到手术后的 效果此外，进行放射性治疗时，肿瘤部位的外形数据可以帮助医生制定合适的 治疗方案 量身定做服装和量脚制鞋 面向特定个体消费群体的量身定做和量脚定做是光学三维面形测量的一个 大连理工大学硕士学位论文 典型应用出于设计出更为适合每个人的服装和鞋考虑，设计时必须要考虑到每 个人的形体和脚型之间的不同现有的光学测量方法已经能满足服装设计和制鞋 设计对人体和脚型数据的要求，随着计算机图形学和c a d 技术的不断进步，量身 定做和量脚制鞋会不断走向普及。 基于三维散乱点的韭面重建和边界检测 第二章c a g d 的历史和现状 c a g d ，即计算机辅助几何设计，是一门迅速发展的新兴学科，它的出现和 发展是现代工业发展的要求，又对现代工业的发展起到了巨大的促进性作用。而 反向工程又是c a g d 中一个比较活跃的课题。多年来，国内外学者在c a g d 以及 反向工程领域进行了广泛深入的研究，取得了很多重要的理论与实际成果，并有 大量著作和文献面世。 计算机辅助几何设计( 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 ，简称c a g d ) 这一术 语1 9 7 4 年由巴恩希尔( b a r n h i l l ) 与里森费尔德( r i s e n f e l d ) 在美国犹他0 j m i a ) 大学的 一次国际会议上提出，以描述计算机辅助设计( c o m p u t e ra i d e dd e s i g n ) 的更多的 数学方面，为此加上“几何”的修饰词。在当时，其含义包括曲线、曲面和实体 的表示，及其在实时显示条件下的设计，也扩展到其他方面，例如四维曲面的表 示与显示。自此以后，计算机辅助几何设计开始以一门独立的学科出现。 c a g d 主要研究在计算机图像系统的环境下对曲面信息的表示、逼近、分析 和综合。它起源于飞机、船舶的外形放样( l o f i i l l g ) 工艺，由c o o n s ( 1 9 1 2 - - 1 9 7 9 ) 、 b e z i 4 1 9 l o 1 9 9 9 ) 等大师于2 0 世纪6 0 年代奠定理论基础。典型的曲面表示，2 0 世纪6 0 年代是c o o n s 技术和b e z i e r 技术，2 0 世纪7 0 年代是b 样条技术，2 0 世纪8 0 年 代是有理b 样条技术。现在，曲面表示和造型已经形成了以非均匀有理b 样条 ( n u r b s ：n o n - - u n i f o r mr a t i o n a lb - s p l i n e ) 、参数化特征设计( p a r a m e t e r i z e da n d c h a r a c t e d s t i e d e s i g n ) 和隐式代数曲面表示( i m p l i c i ta l g e b r a i c s u r f a c e r e p r e s e n t a t i o n ) 这_ 两类方法为主体，以插值( i n t e r p o l a t i o n ) 、拟合( f i t t i n g ) 、逼近 f a p p r o x i m a t i o n ) 这= 种手段为骨架的几何理论体系。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着几 何设计对象向着多样性、特殊性、和拓扑结构复杂性靠拢这种趋势的日益明显， 随着图形工业和制造工业迈向一体化、信息化和网络化步伐的日益加快，随着激 光测距扫描等三维数据采样技术和硬件设备的日益完善，c a g d 在近年来得到了 长足的发展。这主要表现在研究领域的急剧扩展和表示方法的开拓创新。 从研究领域来看，c a g d 技术已从传统的研究曲面表示、曲面求交和曲面拼 接。扩展到曲面变形、曲面重建、曲面简化、曲面转换和曲面位差：从表示方法 来看，以网格细分( s u b d i v i s i o n ) 为特征的离散造型与传统的连续造型相比，大有 大连理工大学硕士学位论文 后来居上的创新之势。而且，这种曲面造型方法在生动逼真的特征动画和雕塑曲 面的设计加工中如鱼得水，得到了高度的运用。 2 1 1c a g d 的研究对象与核心问题 计算机辅助几何设计是随着航空、汽车等现代工业的发展与计算机的出现雨 产生与发展起来的一门新兴学科。尽管研究对象扩展到四维曲面的表示与显示 等，但其主要研究对象仍是工业产品的几何形状。工业产品的形状大致上可分为 两类；一类是仅由初等解析曲面( 例如平面、圆柱面、圆锥面、球面、圆环面等) 组成，大多数机械零件属于这一类。可以用画法几何与机械制图的方法完全清楚 表达和传递所包含的全部形状信息；第二类是不能由初等解析曲面组成，而以复 杂方式自由变化的曲线曲面即所谓自由型曲线曲面组成例如飞机、汽车、船舶 的外形零件。显然，后一类形状单纯用画法几何与机械制图是不能表达清楚的。 在制造飞机和船舶的工厂里，传统上采用模线样板法表示和传递自由型曲线 曲面的形状。模线员与绘图员用均匀的带弹性的细木条、有机玻璃条或金属条通 过一系列点绘制所需要的曲线即模线，依此制成样板作为生产和检验的依据。在 曲面上没有模线控制的部分取成光滑过渡。这种采用模拟量传递信息的设计制造 方法所表示与传递的几何形状因人而异，要求设计与制造人员付出繁重的体力劳 动，设计制造周期长，制造精度低，互换协调性差，不能适应现代航空、汽车等 工业的发展。人们一直在寻求用数学方法唯一地定义自由型曲线曲面地形状，将 形状信息从模拟量改变为数值量。由此而来的大量计算工作手工无法完成，只能 由计算机来完成。随着计算机的出现，采用数学方法定义自由型曲线曲面才达到 实际应用的地步。这导致了本学学科的产生与发展。依据定义形状的几何信息， 应用本学科所提供的方法，就可建立相应的曲线曲面方程即数学模型，并通过在 计算机上执行计算和处理程序。计算出曲线曲面上大量的点及其它信息。其间， 通过分析与综合就可了解所定义形状具有的局部和整体的几何特征，这里实时显 示与交互修改工作几乎同步进行。形状的几何定义所有的后置处理( 如数控加工、 物性计算、有限元分析等) 提供了必要的先决条件。 在形状信息的计算机表示、分析与综合中，核心的问题是计算机表示，即要 找到既适合计算机处理且有效的满足形状表示与几何设计要求，又便于形状信息 传递和产品数据交换的形状描述的数学方法。 关于寓体造型的理论的发展落后于曲线曲面，虽然近几年来已取得很大进展 9 基于三维敞乱点的曲面重建和边界检测 并进入实际应用，仍不及曲线曲面理论那么成熟。 2 1 2 曲面造型技术的发展阶段 伴随着计算机图形技术的发展，几何造型技术不仅可应用于原有的外形设 计，还广泛应用于机械制造、医学可视化、虚拟场景生成、铁路勘察设计与环境 工程、地形地貌描述、矿藏储量图示、气象、影视等众多领域。几何造型技术的 发展促进了它的应用领域的扩大，反过来应用领域的扩大又丰富了几何的表示形 式，促进了造型手段和造型方法的发展。在c a d c a g d 中，曲面造型是一个有 着较长历史的领域，6 0 年代初期就已经诞生。1 9 6 3 年f u g e r s o n 提出将曲线曲面表 示为参数向量函数形式，并引入参数三次曲线，构造了组合曲线和由四个角点的 位置矢量及两个方向的切矢定义的f u g c r s o n 双三次曲面片。在此之前曲线曲面都 是采用普通的函数表示形式y = f ( x ) 和z = f ( x ，y ) 或它们的隐式方程表示形式。 1 9 6 4 年，c o o n s 发表了一个更具一般性的曲面描述方法，即一种由四条边界曲线 确定的参数曲面积c o o n s 曲面片，从而使分片表示完整曲面成为可能。但这两种 曲面都存在形状控制和光滑拼接问题。s c h o e n b e r g 利用样条函数成功解决了曲面 片之间的拼接问题，并解决了插值问题。但插值样条曲线曲面的自由度较少，所 以难以用子自由型曲线曲面的设计。b e z i e r 于1 9 7 1 年发表的由控制多边形定义曲 线的方法，并将其成功的用在自由型曲线曲面设计系统u n i s u r f 中。后来f o r r e s t 对最初的b e z i e r 曲线形式作了从新处理，得到了当前常用的基于控制顶点 b e m s t e i n 基表示的b e z i e r 曲线曲面的形式。 b e z i e r 方法是一种由控制多边形( 网格) 定义曲线曲面的方法，从几何变换的 角度来说，即是把b e z i e r 控制网格变换为b e z i e r 曲线曲面，是一种映射关系这 种曲线曲面具有一系列如几何与仿射不变性、凸包性、保凸性、对称性、端点插 值性等优良性质；且具有如d e c a s t e l j a u 求值、离散、升阶、插值、包络生成算法 等简单易用的计算方法，很好地解决了整体形状控制问题b e z i e r 方法仍存在拼 接问题和局部修改问题。 b e 王i e r 曲线的优点在于，曲线曲面的形状的改变只需简单的移动控制顶点就 可实现，因而具有良好的交互性。在这个基础上人们又陆续提出三角域上的张量 积曲面和b e m s t e i n l 曲面( 即b b 曲面) 。 b e z i e r 曲线曲面的不足之处在于他缺少局部性，而且在处理曲面片之间的光 滑拼接方面也存在困难。曲线上任一点都与多边形的所有顶点相关因此对控制多 大连理工大学硕士学位论文 边形的任何修改都会影响到曲线的整体形状，7 0 年代初期d e b o o r 和c o x 分别独立 提出了b 样条的d e b o o r - c o x 递推公式，使b 样条曲线曲面得以广泛的应用。1 9 7 4 年g o r d o n 和r i e s e n f e l d 首次将b 样条理论应用于外形设计，较好的克服t b e z i e r 曲 线曲面在局部控制方面的不足。但是上述方法不能精确表示圆锥截面和球面椭球 面等初等解析曲面，为此v e r s p r i l l e 于1 9 7 5 年提出有理b 样条方法来克服上述缺陷。 有理b e z i e r 曲线曲面不但能表示自由曲线、曲面，而且能精确表示圆锥曲线、二 次曲面与旋转曲面，因而获得广泛的应用。最后在p i g e l 和t i l l e r 等许多学者的努 力下，在8 0 年代后期形成了丰富的非均匀有理b 样条o n u n i f o r mr a t i o n a l b - s p l i n e 缩写为n u r b s ) 的一整套理论和方法，因为它在外形表示方面的强大功 能与潜力，n u r b s 已被作为工业产品数据交换的s t e p 标准，也被作为描述工业 产品几何形状的唯数学方法。把有理和非有理b e z i e r 曲线和b 样条曲线曲面及 圆锥曲线和初等解析曲面统一在一种表示之中，最终使n u r b s 成为c a d c a m 行业的工业标准。 在数学和计算机科学中，通常也用隐函数来定义几何物体。不等式 f ( x ，y ，z ) 0 描述了空间中的半空间( 即实体) ，等式，0 ，y ，。) = 0 可定义该半空间 的边界( 即隐式曲面) ，这种曲面表示方法在几何造型和图形学中也得到了诸多的 应用。参数化表示具有许多优点，如计算曲线曲面的几何量较简单，曲线曲面的 显示方便，具有离散等优良性质。然而，在另外一些几何操作，如判断一个点是 否在曲线或曲面上以及在那一侧时，参数化表示又极为不便。与之相反，隐式化 表示给这些操作带来了极大的方便。同时，隐式化表示在曲线曲面求交方面也有 极其重要的应用。因此，在c a g d 中，也越来越多的使用曲线曲面的隐式化表示。 为了解决任意拓扑上的曲面造型，人们提出并发展了细分曲面( s u b d i v i s i o n s u f a c e ) 造型方法。细分曲面是一类采用组成曲面的多边形网格点、线、面及其拓 扑信息完整地描述的曲面，这个多边形网格可以从手工模型上输入，也可以从激 光扫描输入。他与连续函数所描述的曲面在方法和数据结构上有着本质的区别。 其基本方法是：从初始多面体网格开始，按某种规则，递归的计算新网格的每个 顶点，这些顶点都是原网格上相邻的几个顶点的加权平均。随着细分的不断进行， 控制网格就被逐渐磨光。在一定条件下( 一定的细分规则) 下，细分无穷多次之后 多边形网格将收敛到一张光滑曲面。细分曲面的最大优点就是算法简单，几乎可 以描述任意复杂曲面，显著地压缩了设计和建立一个原始模型的时间。而且，这 基于三维散乱点的曲面重建和边界检测 种曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加工中如鱼得水，得到 了高度运用。 人们在发展了曲线曲面的多种表现形式的同的也创造出了曲线曲面的各种 构造技术和方法，包括变形曲面构造技术、散乱点拟合造型技术、蒙皮( s k i n n i n g ) 造型技术、广义s w e e p i n g 造型技术、基于变分原理的造型技术以及分形造型技术 等许多方法。随着应用领域的扩大和对造型质量要求的提高，人们还是不断地发 展新的造型方法。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着集 合设计对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的日益明显，随着 图形工业和制造工业迈向一体化、集成化和网络化步伐的日益加快，随着激光测 距扫描等三维数据采样技术和硬件设备的日益完善，曲面造型在近几年来得到了 长足的发展。 2 1 3 反向工程概述 随着科技的发展和市场的需要，工业产品越来越注重品种多样化、造型美观 化，同时也对产品的更新周期提出了更快的要求。在产品的开发及制造过程中， c a d 技术已使用得相当广泛，但是，由于种种原因，仍有许多产品并非由c a d 模型描述，设计和制造者面对的是实物样件，有时，甚至可能连一张可以参考的 图纸也不存在，这就为我们在后续的工作中采用先进的设计手段和先进的制造技 术带来了很大的障碍。为了适应先进制造技术发展，需要通过一定的技术手段， 将现有的实物( 产品原型或油泥模型) 转化为相应的c a d 模型，使其能够利用现有 的先进制造技术进行修改和分析，以生产出高质量的产品。由此，产生了反向工 程( r e v e r s ee n g i n e e r i n g ) i 拘概念。反向工程是在没有没汁图纸或者设计图纸不完整 以及没有c a d 模型的情况下，按照现有的实物模型，利用各种数字化技术以及 c a d 技术重新构造样本产品的c a d 模型，并进行修改和更新，并最终输出产品 模型的过程。耳前，反向工程己发展成为c a d c a m q b 的一个相对独立的范畴， 与传统的c a d c a m 互相补充，协调发展。 反向工程的具体应用可以分为以下几类：1 ) 起源于物理模型的新零件的设 计；2 ) 对无法得到图纸的现有零件的复制：3 ) 磨损或损坏物体的还原；4 ) 对现有 产品的局部修改：5 ) 产品的检测。 反向工程是缩短产品开发周期的一种有效途径，特别是形状复杂的物体或自 大连理工大学硕士学位论文 由曲面组成的物体，例如：流线型物体、人体器官、雕塑品、模具等无法用传统 c a d 技术描述的物体。世界各国都在其经济技术发展中，应用反向工程消化吸收 先进的技术经验，给人们有益的启示。作为一种技术手段，反向工程可使产品研 制周期缩短百分之四十以上，极大提高了生产率。因此，研究反向工程技术，对 我国国民经济的发展和科学技术水平的提高，具有重大的意义。 反向工程具有与传统设计制造过程截然不同的设计流程。在反向工程中，按 照现有的零件原形进行设计生产，零件所具有几何特征与技术要求都包含在原形 中；在传统的设计制造中，按照零件最终所要承担的功能以及各方面的影响因素， 进行从无到有的设计。此外，从概念设计出发到最终形成c a d 模型的传统设计是 一个确定的过程，而通过对现有零件原形数字化后在形成c a d 模型的反向工程是 一个推理、逼近的过程。 反向工程一般分为四个阶段： 模型的数字化：采用各种数字化测量设备和测量手段，获取模型的空间离散 点数据表示，并将测量结果以文件等方式存储起来，以便以后的使用。测量的工 具和方法根据实物的情况，通常可分为接触式和非接触式两种。三维数字扫描仪 是目前使用最广泛的一种测量工具，它属于非接触式的测量工具。模型的数字化 是反向工程的基础，通常由于测量仪器的精度和测量手段的粗糙，造成很多测量 数据之中存在很多噪音，这对于以后模型的重建有很大的影响。因此，往往还要 对刚刚获得的数字化信息进行一定的过滤，过滤的方法很多，比如程序判断滤波、 n 点平均滤波以及预测误差递推辨识与卡尔曼滤波相结合的自适应滤波法等等。 模型的重建：根据已经获取的模型空间散乱点数据反求出原来的三维c a d 模型并在产品对象分析和插值检测后，对模型进行逼近调整和优化。目前，最 - 常用的重建方法，是基于特征数据的曲面拟合方法，即由散乱点数据，重建其空 问几何关系。由于模型的复杂性，其表面往往是由一些以复杂方式自由地变化的 曲面，即所谓自由曲面组成。对自由曲面进行描述，通常要采用矢函数形式的参 数曲面方程p = p ( u ，v ) ，常用的有c o o n s 曲面、b e z i e r 曲面、b 样条曲面和n u r b s 曲面，它们都是由一些基本函数和控制点定义的。就反向工程目前的发展情况而 言，模型的重建算法仍然是各类技术方案的核心和关键所在。 重建模型的分析：将重建的模型通过各类技术分析，并将分析结果存储起来， 以备其他模块调用。存储的结果即是可以进行机械加工的n c 代码。进行对象分 基于三维散乱点的曲面重建和边界检测 析的最大目的，就是要获取该模型的几何特征，如曲率变化较大的点、线，以及 可以供其它c a d 模型加工使用的标准几何区域。 重建模型的加工：根据分析结果生成n c n i 代码，并在具体的n c 设备上将 对象加工出来。 反向工程主要涉及以下的关键技术：数据获取技术、产品建模技术。 数据获取技术 反向工程通常使用测量仪器获得既有产品的坐标数据。数据点有一般两种类 型，机械三坐标测量机测量得到的是有序点数据：激光、数字成像测量得到的三 坐标测量数据是大批量、无序的点云数据。测量得到的数据必须经过处理才能用 于曲面重构和三维建模。由于仪器测量受诸多因素的影响，会产生一些不准确点 和无效点，这些点统称为噪声点，数据获取的过程就是有效点的抽取和噪声点剔 除的过程。 产品建模技术 产品建模就是在数据获取的基础上，应用计算机辅助几何设计的有关技术， 根据物件的三维坐标数据，构造零件原形的c a d 模型。通常对于含有自由曲面的 复杂型物体，用一张曲面来拟合所有的数据点是不行的，一般首先按照原形所具 有的特征，将测量数据点分割成不同的区域，各个区域分别拟合出不同的曲面， 然后应用曲面求交或曲面间过渡的方法将不同的曲面连接起来构成一个体。有效 的三位数据分割和拟合技术是反向工程中的重要内容。 作为c a d i 业的最新技术，反向工程的应用领域大致可以分为以下几种情 况： 1 在没有设计图纸或者设计图纸不完整以及没有c a d 模型的情况下，在对零 件原形进行测量的基础上形成零件的设计图纸和c a d 模型，并以此为依据生成数 控加工的相应代码，加工复制出一个相同的零件。 2 当要设计需要通过实验测试才能定型的工件模型时，通常采用反向工程的 方法。比如航空航天领域，为了满足产品对空气动力学等要求，首先要求在初始 设计模型的基础上经过各种性能测试( 如风洞实验等) 建立符合要求的产品模型， 这类零件一般具有复杂的自由曲面外型，最终的实验模型将成为设计这类零件及 反求其模具的依据。 在美学设计特别重要的领域，例如汽车外型设计广泛采用真实比例的木质或 大连理工大学硕士学位论文 泥塑模型宋评估设计的美学效果，而不采用在计算机屏幕上缩小比例的物体透视 图的方法，此时需用反向工程的设计方法。 另一个重要的应用如修复破损的艺术品或缺乏某些损坏零件等，此时不需要 对整个零件原形进行复制，而是借助反向工程技术抽取零件原形的设计思想，指 导新的设计。 总之，反向工程技术可以应用在机械制造、航空航天、国防军事等c a d 行业 所触及的每一个领域，并发挥其迅速、准确和机械化的特长，推动t c a d 行业新 的制作手段和方式。 国际上较早提出反向工程方法的有比h o p p c ( 微软公司) 、 k r i s h n a m u r t h y ( s t a n f o r d 大学) 、e d e l s b r u n n e r ( d u k e 大学) 等。反向工程方法的出发 点是对物理实体进行三维扫描得到的数据点云，再对点云进行初步处理，首先转 化成多边形模型。在多边形模型的基础上，形成四边形剖分，再进行适当的参数 化。然后，用n u m 3 s ( 非均匀有理b 样条) 拟合的方法。实现最终目标生成光滑的 数字模型。 美国首先意识到反向工程的极端重要性及其广阔的市场前景，不仅率先开展 了反向工程的研究，而且出现了p a r a f o r m ( 由k r i s h n a m u r t h y 创建) 和r a i n d r o p g e o m a g i c ( 以e d e l s b r u n n e r 的方法为基础) 这两家从事反向工程软件商业性开发 的高科技公司。1 9 9 9 年韩国也成立了一个类似的r a p i d f o r m 公司。 我国浙江大学、中国科学技术大学、北京航空航天大学、吉林大学、大连理 工大学等单位对多元样条、b e z i e r 曲面、隐式代数曲面、单个n u r b s 曲面等进行 了多年富有成果的研究；清华大学、上海科技大学、广州军医大学等单位在医学 图像重建方面傲了许多工作。 目前，反向工程技术的发展趋势，是形成一套独立的软件系统，并在此基础 上建立了一种机械化、智能化的c a d 制作模式。从而带动了整个c a d 行业的转 变。由于我国的技术发展仍大幅落后于世界，更应该紧抓住反向工程技术能够缩 短高新技术开发周期的特点，充分地进行该技术的研究，以更好的为国家的经济 发展服务。 反向工程中的曲面重构可以采用以下几个步骤： 1 建立采样点集( 点云) 。点云通常是有误差的，而且除了点的位置信息以外 没有几何信息被预知。 基于三维散乱点的盐面重建和边界检测 眈1 点云梗墨 i i g u r e 2 ip 。i n tc l o u dm o a 1 2 建立多边形模型( 通常是三角形网格) 。有的设备能直接得到多边形模型。 这一步的主要目的是建立点云的拓扑信息以及给出最终模型的一个初步估计。 酿z 多边形棋型 f i g 口e2 ，2p d y p n dm o d e l 3 建立多边形模型的四边形剖分。这一步的目的是将多边形模型分割一些小的 面片，每一个面片都将利用一个n u r b s ( b 样条) 曲面片拟合，因此这些面片都 被赋予了“张量积”的结构，整个剖分也被称为“四边形剖分”，这一步可以手 工完成。也可以通过一定的算法实现。 大连理工大学硕士学位论文 固23 四边弗梗型 p i 口23q u 扛n d tm o i * l 4 根据设计要求对n l t r b s ( b 样条) 曲面进行再处理。这主要包括连续性拼接 光顺处理等。 图24 f i c 叮e2 t 使用上述步骤完成反向工程的完整过程如图2 5 所示。 基于三维散乱点的曲面重建和边界检测 圈2 s 反自工程的一种实现j 窭程 f i # u r e 25 _ y o c e s so fr e v e r s ee n i t e e r i t | 1 8 大连理工大学硕士学位论文 第三章计算几何中的相关算法 3 1 散乱数据的三角剖分 散乱数据的三角剖分是构造散乱数据插值曲面时必不可少的前置处理。三角 剖分可分为对三维散乱数据投影域的割分和在空间直接剖分两种类型，散乱数据 的投影域包括平面域和球面域。直接三角剖分法研究如何直接将三维散乱数据点 在空间中连接成个最优的三角网格。 3 1 1 与三角剖分有关的若干定义 先给出与三角剖分有关的一些基本概念。 ( 1 ) 域分割 给定平面上( 或空间中) n 个不相重的散乱数据点，对每个散乱点构造一个域， 使该域内的任一点离此散乱点比离其他散乱点更近，这种域分割成为d i r i c h l e t 域 分割，又称v o r o n o i 图，由定义可知，域边界是连接两相邻散乱点的直线的垂直 平分线( 或面) 。 ( 2 ) d e l a u n a y - 三角化 对平面上( 或空间中) 的散乱数据点进行域分割后，将具有公共域边界的散乱 点对相连形成的三角剖分成为d e l a u n a y - 一角剖分，如图2 2 1 所示，l a w s o n 曾 给出一个n 维d e l a u n a y - 一角剖分的定义。 对于给定的一组散乱数据点，可获得无限种不同的三角剖分，其中d e l a u n a y 三角剖分为最优，二维的d e l a u n a y 三角剖分由满足最小内角最大准则的三角形组 成，三维的d e l a u n a y 三角剖分由满足球面准则的四面体组成。 图2 2 1d i r i c h 妇域分割( 糕线) 和d e l a u n a y 三角削分( 细线) f i g u r e2 2 1 d i r i c h l c tp a r t i t i o na n dd e l a u n a yt r i a n g u l a t i o n ( 3 ) 优化 对三角网格进行优化，就是要使三角网格整体上尽量均匀，避免出现狭长三 角形，亦即获得d e l a u n a y 三- 角化。 基于三维敞乱点的曲面重建和边界检测 3 1 2 三角剖分优化准则 在三角剖分过程中，我们往往用一种比较简单的方法构造散乱数据点的初始 三角剖分，然后对其进行优化以获得d e l a t m a y _ 三角剖分。优化的方法和效果取决 于所采用的优化准则。常用的优化准则有t h i e s s e n 区域准则、最小内角最大准则、 圆准则、球面准则、a b n 准则、p l c 准则、多面体表面积最小准则、多面体体积 最大准则及空间光顺准则等。前三者为平面三角剖分优化准则，s i b s o n 证明了这 三个准则的等价性，并指出符合这三个准则的三角剖分只有一个，r d e l a u n a y 三 角化，其余各准则可视为空间三角网格的优化准则。 ( 1 ) 最小内角最大准则 对一个严格凸的四边形进行三角化时，有两种选择。最小内角最大准则就是 保证对角线两侧两个三角形中的最小内角为最大，如图2 2 2 5 n 图2 2 3 所示： 一一令 隧2 2 , 2 最小内角最大准则 圈2 2 3 蹰罐则 f i g u r e 2 2 ，2g m 嚣】l e s ta n g l er u l e f i g u r e 2 2 3c i r c l er u l e ( 2 ) 圆准则和球面准则 严格凸四边形中的三个顶点确定一囡，如果第四个顶点落在圆内，则将第四 个顶点与其相对的顶点相连，否则将另两个顶点相连，称为圆准则，如上图所示， 球面准则可表述为：对于两共面的四面体a 和b ，若a 的不属于b 的顶点位于b 的 外接球内，则需对两四面体的拓扑关系进行变换；若位于b 的外接球外，则两四 面体不做变换，保持其拓扑关系不变。 ( 3 ) a b n 准月, l j ( a n g l e sb e t w e e nn o r m a l 设t 是散乱数据点集只( 扛1 , 2 ，h ) 的三角剖分。定义每一条内边e 的权值c ( e ) 为与之相邻的两个三角面法矢的夹角。若两三角面处于同一平面上，则c ( e ) = o 。 对一个严格凸的四边形三角化时，有两种选择。设这两种对角线连接分别为e 和 e 。a b n 准则就是要选择c ( e ) 和c ( p ) 中权值较小的一种三角化结果。 f 4 ) 光顺准则 对个严格凸的四边形三角化时，有两种选择。设这两种对角线连接分别为 太连理工大学硕士学位论文 e 和e ，c ( e ) 为连接对角线e 时，四边形四条边上三角形对的夹角中的最小值，c 0 ) 为连接对角线e 时，四边形四条边上三角形对的夹角中的最小值，光顺准则就是 要选择c ( e ) 和c ( e ) 中数值较小的一种三角化。 ( 5 ) 优化与退化 1 ) 局部优化与全局优化 局部优化指的是对任意一个凸四边形的对角线，依据某种优化准则作交换测 试后所得到的三角剖分。全局优化则指三角剖分t 中每一条内边上的两三角形所 形成的凸四边形都满足局部优化的三角剖分结果。 2 ) 退化 当n + 1 个以上的点同处于一个1 1 维超球面时，即为退化。构造平面d e l a u n a y 三 角剖分时，若四个或四个以上的散乱数据点共圆，则退化。对于三维情况，当五 个或五个以上的散乱数据点位于同一球面上时，出现退化情况。导致退化的共圆 点或共球点称为退化点。 真正的退化情况并不多见，它不影响剖分结果。但由于浮点计算误差而引起 的近似退化却有可能发生。近似退化会引起优化过程中的交换测试判断发生错 误，从而导致非法的剖分结果。近似退化造成的算法失败主要表现在退化点附近 的散乱数据点邻接关系记录混乱。解决这一问题的方法是轻微扰动退化点，对其 位置做出确切判断，e d e l s b r u n n e r 等提出了消除退化情况的s o s 扰动方法。 退化也泛指散乱数据点中有重合投影点及四边形四个顶点近似共线等情况。 3 1 3 平面和开曲面散乱数据的三角剖分 由于三维散乱数据点之间拓扑关系的复杂性，对其直接剖分的理论和方法尚 不完善，一般仍以投影域三角剖分为主，投影域分为平面域和