（计算数学专业论文）反向工程中旋转面重建的算法研究.pdf

摘要 反向工程是计算机辅助几何设计中的一个重要课题，其在传统工业及制造 科技发展中也发挥着巨大的作用。旋转面是工业产品中常见的一种外形。进行 旋转面的重建，是反向工程中的一个必不可少的课题。旋转面的特殊性以及现 代计算机辅助几何设计技术的发展，为针对这个课题进行研究提供了较好的先 决条件。本文以旋转面重建算法为主要研究对象，应用三角剖分、曲率的定义 以及b 样条理论提出了一种由点云数据构造旋转面的方法，主要工作如下： 计算机辅助几何设计以及反向工程是本文的理论基础，因此论文的第一章 对其进行了简短的回顾和综述，并给出了旋转面重建算法目前的研究状况。 本文的算法是建立在三角剖分、自由曲面中曲率的定义以及b 样条理论的 基础之上的，因此在第二章着重介绍了这些理论的主要内容。 论文的第三章详细阐述了本文所提出的旋转面重建算法，给出计算旋转轴 和反求母线的步骤，并在最后给出了两个算例。 关键词：计算机辅助几何设计，反向工程，旋转面，母线，曲率，点云，旋转 轴，三角剖分 a b s t r a c t r e v e r s e e n g i n e e r i n g i s b e c o m i n g a n i m p o r t a n t f i e l di n c o m p u t e r a i d e d g e o m e t r i cd e s i g n i ta l s oh a sp r o f o u n di m p a c to nt r a d i t i o n a l i n d u s t r ya n d t h e d e v e l o p m e n to fm a n u f a c t u r et e c h n o l o g y s u r f a c eo fr e v o l u t i o ni sv e r yc o m m o ni n i n d u s t r y m o d e l s ，s ot h er e c o n s t r u c t i o no fs u r f a c eo fr e v o l u t i o nb e c o m e s a n e c e s s a r y t a s ki nr e v e r s e e n g i n e e r i n g t h es p e c i a l i t y o fs u c hs u r f a c e sa n dt h e d e v e l o p m e n t o ft h en e wt h e o r ya n d t e c h n i q u e i n c o m p u t e r a i d e dg e o m e t r i c d e s i g nm a k ei te a s y f o r t h es o l u t i o nt ot h i st a s k i n t h i s p a p e r ，w et a k et h e r e c o n s t r u c t i o no fs u r f a c eo fr e v o l u t i o na so u rm a i na i m ，a n db yu s i n gt h ed e l a u n a y t r i a n g u l a t i o n ，t h ed e f i n i t i o no f c u r v a t u r ea n dt h et h e o r yo f b - s p l i n e ，w ep r e s e n ta w a yo fr e c o n s t r u c t i n gs u r f a c eo fr e v o l u t i o nf r o mp o i n tc l o u d t h em a i nc o n t e n to f t h i sp a p e ri s g i v e ni nt h ef o l l o w i n g c o m p u t e ra i d e dg e o m e t r i cd e s i g na n dr e v e r s ee n g i n e e r i n ga r et h eb a s i so f t h i sa r t i c l e s oab r i e fr e v i e wo nt h e s et w os u b j e c t si s g i v e ni nt h ef i r s tc h a p t e r a l s ot h e r ei sas h o r tr e p o r to nt h es t a t u so fr e s e a r c h e so nt h e r e c o n s t r u c t i o n0 f s u r f a e e so fr e v o l u t i o n a st h ea l g o r i t h mi 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 yt r i a n g u l a t i o n ，t h e d e f i n i t i o no fc u r v a t u r ei nf l e e f o r ms u r f a c e sa n d b s p l i n e ，t h es e c o n de h a p t e r c o n c e n t r a t e so nt h ei n t r o d u c t i o no ft h e s et h e o r i e s t h er e c o n s t r u c t i o n a l g o r i t h m i s p r e s e n t e d i nd e t a i li nt h et h i r d c h a p t e r i n c l u d i n gt h ec o m p u t i n go fa x i sa n dt h er e c o n s t r u c t i o no fg e n e r a t r i x t h e nt w o e x a m p l e s a r eg i v e nt os h o wt h ee f f e c t i v e n e s sa n dv e r a c i t yo f t h ea l g o r i t h m k e y w o r d s ：c o m p u t e raid e dg e o m e t ricd e si g n ，r e v e r s e e n g in e eri n g s ur f a c eo fr e v o iu t i o n g e n e r a tr ix c u r v a t u r e ，p o in t c lo u d r o t a t i n g a x is d e i a u n a yt ri a n g u ia t i o n 1综述 c a g d ，即计算机辅助几何设计，是一门迅速发展的新兴学科，它的出现和发展 足现代工业发展的要求，又对现代工业的发展起到了巨大的促进性作用。而反向工程又 是c a g d 中一个比较活跃的课题。多年来，国内外学者在c a g d 以及反向工程领域进 行了广泛深入的研究，耿得了很多重要的理论与实际成果，并有大量著作和文献面世。 1 1c a g d 的概况 11 1c 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 ) 在美国犹他( u t a h ) 大学 的一次国际会议上提出，以描述计算机辅助殴计( c o m p u t e r a i d e dd e s i g n ) 的更多的数 学方面，为此加上“几何”的修饰词。在当时，其含义包括曲线、曲面和实体的表示， 及其在实时显示条件下的设计，也扩展到其他方面，例如四维曲面的表示与显示。自此 以后，计算机辅助几何设计开始以一门独立的学科出现川。 c a g d 主要研究在计算机图象系统的环境下对曲面信息的表示、逼近、分析和综 合。它起源于飞机、船舶的外形放样( l o f t i n g ) 工艺，由c o o n s ( 1 9 1 2 1 9 7 9 ) 、b e z i e r ( 1 9 1 0 一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 dc h a r a c t e r i s t i c d e s i g n ) 和隐式代数曲面表示( i m p l i c i ta l g e b r a i cs u r f a c er 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 ) 、逼近( a p p r o x i m a t i o n ) 这三种手段为骨架 的几何理论体系1 4 i ”1j 。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着几何设计对 象向着多样性、特殊性、和拓扑结构复杂性靠拢这种趋势的日益明显，随着图形工业和 制造工业迈向一体化、信息化和网络化步伐的日益加快，随着激光测距扫描等三维数据 采样技术和硬件设备的日益完善，c a g d 在近年来得到了长足的发展。这主要表现在研 究领域的急剧扩展和表示方法的开拓创新。 从研究领域来看，c a g d 技术已从传统的研究曲面表示、曲面求交和曲面拼接，扩 充到曲面变形、曲面重建、曲面简化、曲面转换和曲面位差；从表示方法来看，以网格 细分( s u b d i v i s i o n ) 为特征的离散造型与传统的连续造型相比，大有后来居上的创新之 势。而且，这种曲面造型方法在生动逼真的特征动画和雕塑曲面的设计加工中如鱼得 水，得到了高度的运用。 1 1 2c a g d 的研究对象与核心问题j 反向工程中旋转向重建的算法研究 计算机辅助几何设计是随着航空、汽牟等现代工业的发展与计算机的出现而产 生与发展起来的一门新兴学科。尽管研究对象扩展到四维曲面的表示与显示等，但其主 要研究对象仍是工业产品的几何形状。工业产品的形状大致上可分为两类：一类是仅由 初等解析曲面( 例如平面、圆柱面、圆锥面、球面、圆环面等) 组成，大多数机械零件 属于这一类，可以用画法几何与机械制图的方法完全清楚表达和传递所包含的全部形状 信息；第二类是不能由初等解析曲面组成，而以复杂方式自由变化的曲线曲面即所谓自 由型曲线曲面组成，例如飞机、汽车、船舶的外形零件。显然，后一类形状单纯用画法 儿何与机械制图是不能表达清楚的。 在制造飞机和船舶的工厂里，传统上采用模线样板法表示和传递自由型曲线曲 面的形状。模线员与绘图员用均匀的带弹性的细木条、有机玻璃条或金属条通过一系列 点绘制所需要的曲线即模线，依此制成样板作为生产和检验的依据。在曲面上没有模线 控制的部分取成光滑过渡。这种采用模拟量传递信息的设计制造方法所表示与传递的几 何形状因人而异，要求设计与制造人员付出繁重的体力劳动，设计制造周期长，制造精 度低，互换协调性差，不能适应现代航空、汽车等工业的发展。人们一直在寻求用数学 方法唯一地定义自由型曲线曲面地形状，将形状信息从模拟量改变为数值量。由此而来 的大量计算工作手工无法完成，只能由计算机来完成。随着计算机的出现，采用数学方 法定义自由型曲线曲面才达到实际应用的地步。这导致了本学学科的产生与发展。依据 定义形状的几何信息，应用本学科所提供的方法，就可建立相应的曲线曲面方程即数学 模型，并通过在计算机上执行计算和处理程序，计算出曲线曲面上大量的点及其它信 息。其间，通过分析与综合就可了解所定义形状具有的局部和整体的几何特征，这里实 时显示与交互修改工作几乎同步进行。形状的几何定义所有的后置处理( 如数控加工、 物性计算、有限元分析等) 提供了必要的先决条件。 在形状信息的计算机表示、分析与综合中，核心的问题是计算机表示，即要找 到既适合计算机处理且有效的满足形状表示与几何设计要求，又便于形状信息传递和产 品数据交换的形状描述的数学方法。 关于实体造型的理论的发展落后于曲线曲面，虽然近几年来已取得很大进展并 进入实际应用，但仍不及曲线曲面理论那样成熟。 1 2 曲面造型技术的发展阶段m 】 伴随着计算机图形技术的发展，几何造型技术不仅可应用于原有的外形设计，还广 泛应用于机械制造、医学可视化、虚拟场景生成、铁路勘察设计与环境工程、地形地貌 描述、矿藏储量图示、气象、影视等众多领域。几何造型技术的发展促进了它的应用领 域的扩大，反过来应用领域的扩大又丰富了几何的表示形式，促进了造型手段和造型方 法的发展。在c a d c a g 中，曲面造型是一个有着较长历史的领域，6 0 年代初期就已 经诞生。1 9 6 3 年f u g e r s o n l l 3 1 提出将蓝线曲面表示为参数向量函数形式，并引入参数三 次曲线，构造了组合曲线和由四个角点的位置矢量及两个方向的切矢定义的f u 2 e r s o n 双三次曲面片。在此之前曲线曲面都是采用普通的函数表示形式y ：厂0 ) 和：，“，v 1 反向工程中旋转面重建的算法研究 或它们的隐式方程表示形式。1 9 6 4 年，c o o n s 发表了一个更具一般性的曲面描述方 法，即一种由四条边界曲线确定的参数曲面积c o o n s 曲面片，从而使分片表示完整曲面 成为可能。但这两种曲面都存在形状控制和光滑拼接问题。s c h o e n b e r g 利用样条函数i l 6 j 成功解决了曲面片之间的拼接问题，并解决了插值问题。但插值样条曲线曲面的自由度 较少，所以难以用于自由型曲线曲面的设计。b 6 z i e r 7 l 于1 9 7 1 年发表的由控制多边形 定义曲线的方法，并将其成功的用在自由型曲线曲面设计系统u n l s u r f 中。后来 f o r r e s t l l 8 i 对最初的b 0 z i e f 陷线形式作了从新处理，得到了当前常用的基于控制顶点 b e r n s t e i n 基表示的b d z j e r 曲线曲面的形式。 b 6 z i e r 方法是一种由控制多边形( 网格) 定义曲线曲面的方法，从几何变换的角度来 说，即是把b 6 z i e r 控制网格变换为b 6 z i e r 曲线曲面，是一种映射关系这种曲线曲面 具有一系列如几何与仿射不变性、凸包性、保凸性、对称性、端点插值性等优良性质； 且具有如d ec a s t e l j a u 求值、离散、升阶、插值、包络生成算法等简单易用的计算方 法，很好地解决了整体形状控制问题 1 9 1 ”1 b d z i e r 方法仍存在拼接问题和局部修改问 题 b 6 z j e f 曲线的优点在于，曲线曲面的形状的改变只需简单的移动控制顶点就可实 现，因而具有良好的交互性。在这个基础上人们又陆续提出三角域上的张量积曲面和 b e r n sl e i l 3 曲面( 即b b 曲面) 。 b d z i e f 曲线曲面的不足之处在于他缺少局部性，而且在处理曲面片之间的光滑拼 接方面也存在困难。曲线上任一点都与多边形的所有顶点相关因此对控制多边形的任何 修改都会影响到曲线的整体形状，7 0 年代初期d eb o o p l 和c o x p 2 1 分别独立提出了b 样 条的d eb 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 【2 驯首次将b 样条理论应用于外形设计，较好的克服了b o z i e r 曲线曲面在局 部控制方面的不足。但是上述方法不能精确表示圆锥截面和球面椭球面等初等解析曲 面，为此v e r s p r i l l e 于1 9 7 5 年提出有理b 样条方法来克服上述缺陷。有理b 6 z i e f 曲线 曲面不但能表示自由曲线、曲面，而且能精确表示圆锥曲线、二次曲面与旋转曲面，因 而获得广泛的应用。最后在p i g e l 和t i l l e r 等许多学者的努力下，在8 0 年代后期形成了 丰富的非均匀有理b 样条( n o n - u n i f o r mr a t i o n a lb s p l i n e 缩写为n u r b s ) l 2 4 1 1 2 5 1 的一整 套理论和方法，因为它在外形表示方面的强大功能与潜力，n u r b s 已被作为工业产品 数据交换的s t e p 标准，也被作为描述工业产品几何形状的唯一数学方法。把有理和非 有理b 6 z i e r 曲线和b 样条曲线曲面及圆锥曲线和初等解析曲面统一在一种表示之中， 最终使n u r b s 成为c a d c a m 行业的工业标准。 在数学和计算机科学中，通常也用隐函数来定义几何物体。不等式f ( x ，y ，z ) 0 描 述了空间中的半空间( 即实体) ，等式s ( x ，y ，z ) = 0 可定义该半空间的边界( 即隐式曲 面) ，这种曲面表示方法在几何造型和图形学中也得到了诸多的应用。参数化表示具有 许多优点，如计算曲线曲面的几何量较简单，曲线曲面的显示方便，具有离散等优良性 质。然而，在另外一些几何操作，如判断一个点是否在曲线或曲面上以及在那一侧时， 参数化表示又极为不便。与之相反，隐式化表示给这些操作带来了极大的方便。同时， 反商工程中旋转面重建的算法研究 隐式化表示在曲线曲面求交方面也有极其重要的应用。因此，在c a g d 中，也越来越多 的使用曲线曲面的隐式化表示。 为了解决任意拓扑上的曲面造型，人们提出并发展了细分曲面( s u b d i v i s i o n s u r l h c e ) 造型方法。细分曲面是类采用组成曲面的多边形网格点、线、面及其拓扑信 息完整地描述的曲面1 2 6 】1 2 7 】，这个多边形网格可以从手工模型上输入，也可以从激光扫 描输入，他与连续函数所描述的皓面再方法和数据结构上有着本质的区别。其基本方法 是：从初始多面体网格开始，按某种规则，递归的计算新网格的每个顶点，这些顶点都 是原网格上相邻的几个顶点的加权平均。随着细分的不断进行，控制网格就被逐渐磨 光。在一定条件下( 一定的细分规则) 下，细分无穷多次之后多边形网格将收敛到一张 光滑曲面。细分曲面的最大优点就是算法简单，几乎可以描述任意复杂曲面，显著地压 缩了设计和建立一个原始模型的时问。而且，这种曲面造型方法在生动逼真的特征东化 和雕塑曲面的设计加工中如鱼得水，得到了高度运用。 人们在发展了曲线曲面的多种表现形式的同时也创造出了曲线曲面的各种构造技术 和方法，包括变形曲面构造技术、散乱点拟合造型技术、蒙皮( s k i n n i n g ) 造型技术、 广义s w e e p i n g 造型技术、基于变分原理的造型技术以及分形造型技术等许多方法。随 着应用领域的扩大和对造型质量要求的提高，人们还是不断地发展新的造型方法。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着集合设计 对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的日益明显，随着图形工业和制 造工业迈向一体化、集成化和网络化步伐的日益加快，随着激光测距扫描等三位数据采 样技术和硬件设备的日益完善，曲面造型在近几年来得到了长足的发展。 1 3 反向工程的概述【2 8 i - 【3 0 随着科技的发展和市场的需要，工业产品越来越注重品种多样化、造型美观化，同 时也对产品的更新周期提出了更快的要求。在产品的开发及制造过程中，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 ) 的概念。反向工程是在 没有设计图纸或者设计图纸不完整以及没有c a d 模型的情况下，按照现有的实物模 型，利用各种数字化技术以及c a d 技术重新构造样本产品的c a d 模型，并进行修改 和更新，并最终输出产品模型的过程。目前，反向工程已发展成为c a d c a m 中的一个 相对独立的范畴，与传统的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 = e ( u ，v ) ，常用的 有c o o n s 曲面、b e z i e r 曲面、b 样条盐面和n u r b s 曲面，它们都是由一些基本函数和控 制点定义的。就反向工程目前的发展情况而言，模型的重建算法仍然是各类技术方案的 核心和关键所在。 重建模型的分析：将重建的模型通过各类技术分析，并将分析结果存储起来，以备 其他模块调用。存储的结果即是可以进行机械加工的n c 代码。进行对象分析的最大目 的，就是要获取该模型的几何特征，如曲率变化较大的点，线，以及可以供其它c a d 模型加工使用的标准几何区域。 重建模型的加s e ：根据分析结果生成n c 加工代码，并在具体的n c 设备上将对象加 工出来。 反向工程主要涉及以下的关键技术：数据获取技术、产品建模技术。 数据获取技术 反向工程中旋转威重建的算法研究 反向工程通常使用测量仪器获得既有产品的坐标数据。数据点有一般两种类 型，机械三坐标测量机测量得到的是有序点数据；激光、数字成像测量得到的三坐标测 量数据是大批量、无序的点云数据。测量得到的数据必须经过处理才能用于曲面重构和 三维建模。由于仪器测量受诸多因素的影响，会产生一些不准确点和无效点，这些点统 称为噪声点，数据获取的过程就是有效点的抽取和噪声点剔除的过程。 产品建模技术 产品建模就是在数据获取的基础上，应用计算机辅助几何设计的有关技术，根 据物件的三维坐标数据，构造零件原形的c a d 模型。通常对于含有自由曲面的复杂型 物体，用一张曲面来拟合所有的数据点是不行的，一般首先按照原形所具有的特征，将 测量数据点分割成不同的区域，各个区域分别拟合出不同的曲面，然后应用曲面求交或 曲面问过渡的方法将不同的曲面连接起来构成一个体。有效的三位数据分割和拟合技术 是反向工程中的重要内容。 作为c a d 工业的最新技术，反向工程的应用领域大致可以分为以下几种情况： 在没有设计图纸或者设计图纸不完整以及没有c a d 模型的情况下，在对零件 原形进行测量的基础上形成零件的设计图纸和c a d 模型，并以此为依据生成数控加工 的相应代码，加工复制出一个相同的零件。 当要设计需要通过实验测试才能定型的工件模型时，通常采用反向工程的方 法。比如航空航天领域，为了满足产品对空气动力学等要求，首先要求在初始设计模型 的基础上经过各种性能测试( 如风洞实验等) 建立符合要求的产品模型，这类零件般 具有复杂的自由曲面外型，最终的实验模型将成为设计这类零件及反求其模具的依据。 在美学设计特别重要的领域，例如汽车外型设计广泛采用真实比例的木质或 泥塑模型来评估设计的美学效果，而不采用在计算机屏幕上缩小比例的物体透视图的方 法，此时需用反向工程的设计方法。 另一个重要的应用如修复破损的艺术品或缺乏某些损坏零件等，此时不需要对 整个零件原形进行复制，而是借助反向工程技术抽取零件原形的设计思想，指导新的设 计。 总之，反向工程技术可以应用在机械制造、航空航天、国防军事等c a d 行业所 触及的每一个领域，并发挥其迅速、准确和机械化的特长，推动了c a d 行业新的制作 手段和方式。 国际上较早提出反向工程方法的有h h o p p e ( 微软公司) 、k r i s h n a m u r t h v ( s u mf o r d 大学) 、e d e l s b r u n n e r ( d u k e 大学) 等。反向工程方法的出发点是对物理 实体进行三维扫描得到的数据点云，再对点云进行初步处理，首先转化成多边形模型。 在多边形模型的基础上，形成四边形剖分，再进行适当的参数化。然后，用n u r b s ( 非 均匀有理b 样条) 拟合的方法，实现最终目标生成光滑的数字模型。 美国首先意识到反向工程的极端重要性及其广阔的市场前景，不仅率先开展了反向 工程的研究，而且出现了p a r a j ? o r m ( 由k r is h n a m u r t h y 创建) 和r a i n d r o pg e o m a g ic 反向工程中旋转面重建的算法研究 ( 以e d e ls b r u n n e r 的方法为基础) 这两家从事反向工程软件商业性开发的高科技公 司。1 9 9 9 年韩国也成立了一个类似的r a p i d f o r m 公司。 我国浙江大学、中国科技大学、北京航空航天大学、吉林大学、大连理工大学等单 位对多元样条、b e z ie f 曲面、隐式代数曲面、单个n u r b s 曲面等进行了多年富有成果 的研究；清华大学、上海医科大学、广州军医大学等单位在医学图像三维重建等方面做 了很多工作。 目前，反向工程技术的发展趋势，是形成一套独立的软件系统，并在此基础上 建立一种机械化、智能化的c a d 制作模式，从而带动整个c a d 行业的转变。由于我 国的技术发展仍大幅度的落后于世界，更应该紧抓住反向工程技术能够缩短高新技术丌 发周期的特点，充分的进行该技术的研究，以更好的为国家的经济技术发展服务。 反向工程中的曲面重构可以采用以下几个步骤： 1 建立采样点集( 点云) 。点云通常是有误差的，而且除了点的位置信息外没有几何 信息被预先得知( 如图1 3 1 ) 。 图1 3 1 点云模型 f i g u r e1 3 1p o i n tc l o u dm o d e l 2 建立多边形模型( 通常是三角形网格) 。有的设备能直接得到多边形模型。这一步 的主要目的是建立点云的拓扑信息以及给出最终曲面模型的一个初始估计( 如图 1 3 2 1 。 反向工程中旋转面重建的算法研究 图1 3 2 多边形模型 f i g u r e1 3 ，2p o l y g o n a lm o d e l 3 建立多边形模型的四边形剖分。这一步的i i 的是将多边形模型分割成一些小的面 片，每一个面片都将利用一个n u r b s ( b 样条) 曲面片来拟合，因此这些面片就被赋 予了“张量积”的结构，整个剖分也被称为“四边形剖分”，这一步可以手工完 成，也可以通过一定的算法自动实现( 如图1 3 3 1 。 图1 3 3 四边形模型 f i g u r e1 3 3q u a d r a n g l em o d e l 4 根据设计要求对n u r b s ( b 样条) 曲面进行再处理。这主要包括连续性拼接，光顺 处理等。( 如图1 3 4 ) 垦塑三堡主堑堑堕重堡堕簦垄竺塑 图1 3 4 f i g u r e1 3 , 4 使用上述步骤完成反向工程的完整过程如图1 3 5 所示 1 4 旋转面的重建 图t 3 ，5 反向工程的一种实现过程 f i g u r e1 3 5p r o c e s so f r e v e r s ee n g i n e e r i n g 一条曲线r 绕一条固定直线口旋转而产生的曲面叫做旋转面( 回转面) 。在机械 加工、航空航天、考古研究等等领域中，很多零器件都是由一个或多个旋转面构成。在 很多情况下，为了更好的对此类零件进行修改，需要将其在计算机中重新表示出来。此 时就需要从现实中的零件模型，获取相应的实体数据，利用反向工程的思想，使用相应 的步骤，在计算机中实现模型的表示，并给出旋转面的旋转轴以及母线，即旋转面的重 建。 反向工程中旋转面重建的算法研究 关于旋转面重建的算法，目前国内外有过一定的研究。h p o t u 1 a n ”u j ”“等人曾就 旋转面和螺旋面的重建提出过一系列算法，但此类算法在确定母线时使用的方法在实际 应用中偏差较大。i n k w o nl e e 等【32 j 后来就如何确定母线给出了一个比较好的方案。 hj ( ；ib l i n 【3 3 1 1 3 4 1 等人也曾于9 0 年代中期讨论过旋转面重建的问题。近几年，随着几何 设计理论和算法的发展，旋转面重建已经不是一个很困难的问题。在本文中，就给出一 种反求旋转面旋转轴和母线的方法，并通过数值实验，给出了相应的运算例子。由于散 乱数据插值曲面的算法已经比较成熟，如经典的d e l a u n a y 三角剖分和h o o p i e l 3 5j 等提出 的方法，因此本文的算法直接建立在多边形模型的基础之上，确定旋转轴时，利用了自 由曲面中曲率的定义；在给出母线方程时，还利用到了b 样条曲线的理论。在本文的第 二章，将对这几个方面作一定的介绍。在第三章中对本文所提出的旋转面重建算法进行 详细的讨论。 o 反向工程中旋转面重建的算法研究 2计算几何中的相关算法 2 1 直角坐标变换 2 1 1 底矢变换 设已给两个直角坐标系仃= j oe , e 2】，盯= 【d ，e ： e ：，e ij ，并假定它们是右手 系。 由于盯的底矢是两两垂直的幺矢( 空间中任意一个具有单位长的矢量叫做幺 矢) ，则 印q = 吒= l i = 1 4 ( i = j = 1 , 2 ，3 ) z ， 其中6 , 叫做k r o n e c k e r 符号。 同理，由于盯的底矢是两两垂直的幺矢，则 。“：j 1 。 0 此外，因为口和盯+ 是右手系，则 ( e i ，e 2 e 3 ) = 1 ，( p l ，p 2 ，巳) = 1 注意到：对于矢量d i ：( 一，咒，z 。) ，口2 ：( 工2 ，y 2 ，z ：) ， 显然， l xo ( q “2 ，a 3 ) = l x 2 l b 8 l2 口i 一十a i 2 e 2 - i - a 1 3 e 3 e 22 a 2 1 e l + a 2 2 e 2 + 口2 3 e 3 e 32 1 2 3 1 e i - i - a 3 2 e 2 + a ”巳 暑( 吲= l ，2 ，3 ) 其中，= p j q ( 2 1 4 a ) 它是p ：和e ，之间的角的余弦，在盯里，e ：的方向余弦是 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 毛乇m 儿乃 反向工程中旋转面革建的算法研究 ( a “，3 )( i = 1 , 2 ，3 ) 可将口和口+ 的底矢之间的关系列成一个表 利用( 2 1 ，2 ) 式可得出 口j + 口：+ 口：= 1 ， “2 2 l + d 2 2 2 + “2 2 3 = 1 ， d i + 2 + d 三= 1 ， f 口1 1 日2 l + d 1 2 d 2 2 + 口1 3 口2 3 = 0 ， i i “，i + h 1 2 3 2 + a 1 3 3 3 = 0 ， 【a 2 t 口3 l + c 1 2 2 a 3 1 + “2 3 “= 0 或 吼= 以 ( 2 ，1 7 ) ( 2 1 5 ) ( 2 1 6 ) 口1 2d 1 31 日z z z ，l ，由( 2 1 7 ) 可得爿爿= ，而且，由( 2 1 3 ) 式易知h = 1 ，因 ( 3 2 a 3 3 i a l 0 ，有逆矩阵爿，于是 a 。= a l a a = a 一，= 4 一。 其中，爿= ( a 。) ( f ，j = 1 , 2 ，3 ) ，可见 爿。= 爿一1 于是，a 是正交方阵，且测= 1 。 ( 2 1 4 ) 式称为盯到盯的底矢变换公式， 于1 的正交方阵。 同理，也有 e i = b l e 1 + b 1 2 e ；+ 6 1 3 e 3 ， e 2 = b 2 1 e ：+ 6 2 2 e ；+ 6 2 3 e 3 ， e 3 = b 3 1 p ：+ 6 3 2 c ；+ 6 ”e i ( 2 1 8 ) ( 2 1 9 ) 而且盯到盯。的底矢变换矩阵a 是行列式等 ( 2 1 1 0 ) “ 盯 口 ，。l = d令 反向工程中旋转面奏建的算法研究 其中，b 。= e ，p ， f 2 1 1 0 a ) 它是p ，和p i 之间的角的余弦，在盯。里，p ，的方向余弦是 ( 。6 m b , 3 ) ( f = 1 , 2 ，3 ) 显然6 。和盯，都表示e ，。于是6 。= “系数方阵b = 爿，即 b=c。，=c“，=。口a，l，l。(,。21。，3：1 p l = 甜1 l e l + ( 2 1 e 2 + a 3 i e 3 ， e 2 2 a 1 2 e i + c f 2 2 e 2 + a ”e 3 e 3 2 a l3 e 1 4 - ( 1 2 3 e 3 + a 3 3 e 3 利用( 2 1 1 ) 式，可得出 口j + 口；i + a j = 1 ， 口己+ 日杰+ “船2 = 1 ， 日j + ( f 2 2 3 + 口”2 = 1 i 口i i 口1 2 + 口2 1 口1 2 + a 3 1 口，2 = 0 ， i a t l a 1 3 - + i - a 。2 ：1 a 。2 ：3 ，+ + a 。3 。1 ：a 。3 。3 = ：o 。, ( 2 1 11 ) ( 2 1 ，1 2 ) ( 2 1 13 ) ( 2 1 1 4 ) 或 a m = 艿止( j ，k ，i = 1 , 2 ，3 ) ( 2 1 1 5 ) 此外，由i a = 1 知l = l ，4 是正交方阵，a 。也是正交方阵。 ( 2 1 1 2 ) 式称为盯。到盯的底矢变换( 公式) ，而且盯。到盯的底矢变换方阵爿。也是行列 式等于1 的正交方阵。 2 1 2 点的坐标变换 q = 4时 = 爿 见可 得 生h = 6 出 眇d 反向1 二程中旋转面重建的算法研究 设p 是空间任意一点，它在直角坐标系盯和盯下的坐标依次是( x ，y ，z ) 和 ( x ，j j 。，= 。) ，而盯。的原点0 。在盯下的坐标是( x o ，y o ，z o ) 。 山( 1 1 ) 式及坐标平移的基本原理， 即 p2 x + y + a 一3 z + x j ， y = “2 】x + 仃2 2 y + a 2 3 z + y 。， 1 z = a 3 1 x + a 3 2 y + a ”：+ ：j 其中， 工o = 一( 珂i l x o + 日】2j ，o + a l3 z o ) y o = 一( 日2 l 工o + a 2 2 y o + a d z o ) 二o = 一( d 3 l x 0 + 盯1 2 少o + d ”二o ) 蛞 ( 2 1 1 6 ) ( 2 1 1 7 1 ( 2 1 1 6 ) 式称为盯到盯的( 点的) 直角坐标变换( 公式) ，其中( x j ，y j ，) 是盯的原 点0 在盯下的坐标。 同样， 石= a l i x + a 2 1 y + a 3 1 z + x o ， y 2 a 1 2 x + a 2 2 y + ( 3 2 z + y o ，( 2 1 1 8 ) z 2 ( 1 3 x + a 2 3 y + a 3 3 z + z o 工。p 口，：y 。l | y d z 。l l2 0 1 j1 ( 2 1 1 9 ) ( 2 1 1 0 ) 蒯j o 到盯的( 点的) 直角坐标变换( 公式) ，其中( ，乩，z 0 ) 是仃的原点o 在盯下 的坐标。 2 2 散乱数据的三角剖分【s 散乱数据的三角剖分是构造散乱数据插值曲面时必不可少的前置处理。三角剖 分可分为对三维散乱数据投影域的剖分和在空间直接剖分两种类型，散乱数据的投影域 4 蜘白 o 反向工程中旋转商重建的算法研究 包括平面域和球面域。直接三角剖分法研究如何直接将三维散乱数据点在空间中连接成 一个最优的三角网格。 2 21 与三角剖分有关的若干定义 先给出与三角剖份有关的一些基本概念。 ( 1 ) 域分割 给定平面上( 或空间中) 1 1 个不相重的散乱数据点，对每个散乱点构造一个域， 使该域内的任一点离此散乱点比离其他散乱点更近，这种域分割成为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 1 d i r i c h l e t 域分割( 粗线) 和d e l a u n a y 三角剖分( 细线) f i g u r e2 2 1d i r i c h l e 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 三角化。 2 2 2 三角剖分优化准则 在三角剖分过程中，我们往往用一种比较简单的方法构造散乱数据点的初始三 角剖分，然后对其进行优化以获得d e l a u n a y 三角剖分。优化的方法和效果取决于所采 用的优化准则。常用的优化准则有t h i e s s e n 区域准则、最小内角最大准则、圆准则、球 面准则、a b n 准则、p l c 准则、多面体表面积最小准则，多面体体积最大准则及空间 光顺准则等。前三者为平面三角剖分优化准则，s i b s o n 证明了这三个准则的等价性，并 指出符合这三个准则的三角剖分只有一个，即d e l a u n a y 三角化，其余各准则可视为空 蒯三角网格的优化准则。 反向工程中旋转面重建的算法研究 ( 1 ) 最小内角最大准则 对一个严格凸的四边形进行三角化时，有两种