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

逆向工程中旋转面重建的算法研究 摘要 在机械加工、航空航天、考古研究等等领域中，很多零器件都是由一个或多个旋转 面构成。在很多情况下，为了更好的对此类零件进行修改，需要将已经制造好的零件在 计算机中重新表示出来。在这种情况下往往没有曲面的代数表达式，这就需要通过逆向 工程将这种旋转面曲面重新描述出来。而且，受到实际应用的环境条件限制，曲面数据 的采样往往是在整个曲面的很小一部分上进行的，这就给重建曲面的表达式带来了新的 问题。 旋转面重建的关键是确定旋转轴和母线。本文提出了反求旋转轴的一种方法，并利 用b 样条曲线对旋转面的母线进行拟合。通过得到的旋转轴和母线撮终重建整个旋转面。 本文共分三个部分，第一部分主要介绍c a g d 的概况、曲面造型的介绍以及逆向工 程与c a g d 曲面造型之间的联系。 第二部分主要将旋转面重建中的一些基础算法加以介绍，包括坐标变换、b 样条曲 线的理论和散乱数据三角剖分的方法介绍 第三部分提出了一种旋转曲面旋转轴反求的方法，利用b 样条曲线拟和旋转面的母 线并给出了算法实例。 关键词：旋转面，样条，旋转轴，母线。逆向工程 逆向工程中旋转面熏建的算法研究 a b s t r a c t m a n y h a r d w a r ec o m p o n e n t sc o n s i s to fo n eo rm a n yr o t a t i o ns u r f a c e s ，a n dt h e s ec o m p o n e n t s a r ew i d e l yu s e di n m a c h i n e r yc u s t o m i z a t i o n ，a e r o s p a c ea n da r c h a e o l o g yr e s e a r c h u s u a l l y , w h e nam o d i f i c a t i o ni s g o i n gt o b ei m p l e m e n t e do nt h i ss o r to fc o m p o n e n t s ，i ti s h i 曲l y r e c o m m e n d e dt od e m o n s t r a t et h i sc o m p o n e n ti naw a yo fc o m p u t e rs c i e u c eu n d e rs u c h c i r c u m s t a n c e s ，t h e r ei sn oe x p r e s s i o no f n g e b r a f o rs u r n c e ，s ot h i sr o t a t i o ns u r f a c en e e d st ob e r e - g e n e r a t e db yr e v e r s ee n g i n e e r i n g f u r t h e r m o r e ，b e c a u s eo f t h el i m i t a t i o no fe n v i r o n m e n t ， s a m p l i n gt h ed a t ao f s u r f a c eh a v et ob ed o n eo nas m a l lp a r to ft h ew h o l es u r f a c e ，a n dt h i s r a i s e san e wi s s u et or e - c o n s t r u c tt h ee x p r e s s i o nf o r ， t h e k e yp o i n tf o rr e c o n s t r u c t i n gr o t a t i o ns u r f a c ei ss a t i n gu pr o t a t i o na x i sa n dg e n e r a t r i x i n t h i se s s a y , am e t h o df o rc a l c u l a t i n gr o t a t i o na x i si s s t a t e d ，w h i c hi sc o m b i n e db s p l i n et o m e 唱eg e n e r a t r i xo f r o t a t i o ns u r f a c e ，f i n a l l y , t h ew h o l er o t a t i o ns u r f a c ec a l lb er e c o n s t r u c t e d b y t h o s er o t a t i o na x i sa n d g e n e r a t r i x t h ew h o l ee s s a yi sd i v i d e dt ot h r e es e c t i o n s t h ef i r s ts e c t i o ni st h ei n t r o d u c t i o no fc a g d ， s u r f a c em o d e l i n ga n dr e l a t i o n sb e t w e e nc a g da n dr e v e r s ee n g i n e e r i n g t h es e c o n ds e c t i o ni n t r o d u c e s a l g o r i t h m s u s e di ns u r f a c e s r e c o n s t m c t i o n ，i n c l u d i n g c o o r d i n a t et r a n s f o r m a t i o n ，b s p l i n ea n ds c a t t e r e dd a t at r i a n g u l a t i o n ， t h et h i r ds e c t i o np u t e m p h a s i s o nh o wt os o l v eg e n e r a t r i xo fr o t a t i o ns u r f a c ea n du s e b s p l i n e t of i tg e n e r a t r i xo f r o t a t i o ns u r f a c e a n da l s oe x a m p l e sa r el i s t e d k e yw o r d s ：r o t a t i o ns u r f a c e ，b - s p l i n e ，r o t a t i o na x i s ，g e n e r a t r i x ，r e v e r s ee u 毋n e e r i n g 3 逆向t 程中旋转面重建的算法硎究 第一章c a g d 与逆向工程的方法和发展 第一节c a g d 的概况 计算机辅助设计的发展简史 现在计算机辅助设计在众多领域中得到了迅速的、日益广泛的应用，在一定意义上 可以说，它是机械与计算机技术发展融合的产物。 1 9 6 2 年，d t r o s s 和机械工程系的s a c o o n s 合作，开始在机械设计方面探索计算机 辅助的可能。c o o n s 在题为计算机辅助设计需求纲要的报告中，对计算机辅助设计作 了如下的描绘：设计者坐在显示器前用光笔操作，从概念设计、生产设计直到制造，都通过 人机对话方式获得计算机的协助。这在当时只是科学家的梦想，但后来这个梦想逐步变 成了现实。与此同时，另一个具有划时代意义的工作由m i t 的林肯研究所完成。 i e s u t h e f l a n d 提出了用光笔在显示器上选取、定位图形要素的s k e t c h - p a d 系统。使用该 系统，设计者可以在控制台上对问题及问题的解决直接通信，实现了人机对话式的交互作 业。通常要花几周时间的一些工作，在这里只要l o 1 5 分钟就能完成。他还提出了用不 同的层来表示某一工程图的轮廓、剖面线和尺寸。这个系统为交互式图形学和计算机辅 助绘图技术奠定了基础。 汽车工业对计算机辅助设计技术的发明首先做出了响应。美国通用汽车公司和m m 公司率先开发了d a c 一1 ( d e s i g n a u g m e n t e d b y c o m p u t e r ) 系统，用来设计汽车外型与结构。 美国洛克希德公司和m m 公司联合开发了基于大型计算机的图形增强设计与制造软件 包c a d a m ，用于设计与绘图，并具有三维结构分析能力。随后计算机辅助绘图、设计、 制造、分析技术在英、日、意等国的汽车公司也都获得了广泛的应用，并逐渐扩展到其它 部门。 由于早期的计算机非常昂贵，最早使用的计算机辅助绘图、设计、制造、分析系统都 是集中式主机型系统。这种系统由一台集中的大型机( 或中、小型机) 与若干图形终端连 接而成，有一个集中的数据库统一管理所有数据。由于各种软件店都存储在主机里，一旦主 机出现故障将影响所有用户的工作。另一方面，当计算量过大时，系统响应变慢，甚至会出 现个别终端等待的现象。为了减少主机的负荷，不久出现了智能终端型( i n t e l l i g e n t t e n n i n a l ) 系统。这种系统的终端设备采用微机控制。大容量的分析计算、数据库的控制 和管理由主机承担。通讯控制、图形处理等由其它处理器承担。 到了2 0 世纪7 0 年代，出现了将硬件与软件配套交付用户使用的“交钥匙系统” ( t u r n k e ys y s t e m ) ，这种系统是在小型机和超级小型机的基础上增加图形处理功能，按分 时处理的原则，一台主机可以带几个到几十个终端。这个时期计算机在机械行业得到了广 泛的应用。中小企业开始采用计算机辅助绘图、设计、制造、分析技术。 8 0 年代初期，随着计算机制造技术的发展，所有配套的软硬件都可以集成到一台工作 站上。再加上计算机网络的迅速发展，工作站很快取代了“交钥匙系统”。工作站系统可 逆向工程中旋转面重矬的算法研究 以作为一个独立的单用户系统，到8 0 年代中后期就成为计算机辅助绘图、设计、制造、 分析的主流系统。 进入9 0 年代以来，随着个人计算机( p c ) 的飞速发展，其性能迅速赶上了l o 年前高档 工作站的性能。由于个人计算机的价格低、使用方便，以个人计算机为硬件平台的计算机 辅助绘图、设计、制造、分析系统迅速崛起，市场逐步扩大。可以预见，在不久的将来个人 计算机将成为计算机辅助设计的主流机型。 因特n ( i n t e m e t ) 起源于6 0 年代末，兴盛于9 0 年代，目前已经把世界上各种类型的计 算机如大、中、小型机、工作站和个人计算机连接成一个有机的整体，实现全球范围的资 源共享、数据共享和设备共享。利用成熟的i n t e r n e t 技术建立企业内部网络( i n t r a n e t ) ，从 而将计算机辅助绘图、设计、分析、制造和管理系统密切地联系在一起相互协作，已经在 各种企业中迅速推广和普及。 计算机辅助设计的现状与发展计算机技术为机械工业带来了革命性的变革，反过来 计算机在机械工业中的应用也推动了计算机技术的迅速发展。新的设备、新的操作系统、 新的软件、新的数据交换标准，正在迅速扩大计算机在工业中的应用范围，掀起一场新技术 革命的浪潮，成为2 0 世纪全球最杰出的工程技术成果。 c a g d 的研究对象与核心问题 计算机辅助几何设计是随着航空、汽车等现代工业的发展与计算机的出现而产生与 发展起来的一门新兴学科。尽管研究对象扩展到四维曲面的表示与显示等，但其主要研 究对象仍是工业产品的几何形状。工业产品的形状大致上可分为两类：一类是仅由初等 解析曲面( 例如平面、圆柱面、圆锥面、球面、圆环面等) 组成，大多数机械零件属于 这一类，可以用画法几何与机械制图的方法完全清楚表达和传递所包含的全部形状信息； 第二类是不能由初等解析曲面组成，而以复杂方式自由变化的曲线曲面即所谓自由型曲 线曲面组成，例如飞机、汽车、船舶的外形零件。显然，后一类形状单纯用画法几何与 机械制图是不能表达清楚的。 在制造飞机和船舶的工厂里，传统上采用模线样板法表示和传递自由型曲线曲面的 形状。模线员与绘图员用均匀的带弹性的细木条、有机玻璃条或金属条通过一系列点绘 制所需要的曲线即模线，依此制成样板作为生产和检验的依据。在曲面上没有模线控制 的部分取成光滑过渡。这种采用模拟量传递信息的设计制造方法所表示与传递的几何形 状因人而异，要求设计与制造人员付出繁重的体力劳动，设计制造周期长，制造精度低， 互换协调性差，不能适应现代航空、汽车等工业的发展。人们一直在寻求用数学方法唯 一地定义自由型曲线曲面地形状，将形状信息从模拟量改变为数值量。由此而来的大量 计算工作手工无法完成，只能由计算机来完成。随着计算机的出现，采用数学方法定义 自由型曲线曲面才达到实际应用的地步。这导致了本学学科的产生与发展。依据定义形 状的几何信息，应用本学科所提供的方法，就可建立相应的曲线曲面方程即数学模型， 并通过在计算机上执行计算和处理程序，计算出曲线曲面上大量的点及其它信息。其间， 通过分析与综合就可了解所定义形状具有的局部和整体的几何特征，这里实时显示与交 互修改工作几乎同步进行。形状的几何定义所有的后置处理( 如数控加工、物性计算、 逆向工程中旋转面重建的算法研究 有限元分析等) 提供了必要的先决条件。 在形状信息的计算机表示、分析与综合中，核心的问题是计算机表示，即要找到既 适合计算机处理且有效的满足形状表示与几何设计要求，又便于形状信息传递和产品数 据交换的形状描述的数学方法。 关于实体造型的理论的发展落后于曲线曲面，虽然近几年来己取得很大进展并进入 实际应用，但仍不及盐线曲面理论那样成熟。 第二节曲面造型技术的发展阶段 伴随着计算机图形技术的发展，几何造型技术不仅可应用于原有的外形设计，还广 泛应用于机械制造、医学可视化、虚拟场景生成、铁路勘察设计与环境工程、地形地貌 描述、矿藏储量图示、气象、影视等众多领域。几何造型技术的发展促进了它的应用领 域的扩大，反过来应用领域的扩大又丰富了几何的表示形式，促进了造型手段和造型方 法的发展。在c a d c a g 中，曲面造型是一个有着较长历史的领域，6 0 年代初期就已经 诞生。1 9 6 3 年f u g e r s o n 提出将曲线曲面表示为参数向量函数形式，并引入参数三次曲 线，构造了组合曲线和由四个角点的位置矢量及两个方向的切矢定义的f u g e r s o n 双三次 曲面片。在此之前曲线曲面都是采用普通的函数表示形式和或它们的隐式方程表示形 式。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 6 z i e r 于1 9 7 1 年发表的由控制多边形定义曲线的方法，并将其成功的用 在自由型曲线衄面设计系统u n i s u r f 中。后来f o r r e n 对最初的b 6 z i e r 曲线形式作了 重新处理，得到了当前常用的基于控制顶点b e m s t e i n 基表示的b e z i 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 求值、离散、升阶、插值、包络生成算法等简单易用的计算方法，很 好地解决了整体形状控制问题b 6 z i e r 方法仍存在拼接问题和局部修改问题 b 6 z i e r 曲线的优点在于，曲线曲面的形状的改变只需简单的移动控制顶点就可实 现，因而具有良好的交互性。在这个基础上人们又陆续提出三角域上的张量积曲面和 b e m s t e i n 曲面( 即b b 曲面) 。 b e z i e r 曲线曲面的不足之处在于他缺少局部性，而且在处理曲面片之间的光滑拼接 方面也存在困难。曲线上任一点都与多边形的所有顶点相关因此对控制多边形的任何修 改都会影响到曲线的整体形状。7 0 年代初期d eb 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 样条理论应用于外形设计，较好的克服了b 6 z i e r 曲线曲面在局部控制方面的不 足。但是上述方法不能精确表示圆锥截面和球面椭球面等初等解析曲面，为此v e r s p r i l l e 于1 9 7 5 年提出有理b 样条方法来克服上述缺陷。有理b f i z i e r 曲线曲面不但能表示自由 7 逆向工程中旋转面重她的算法研究 曲线、曲面，而且能精确表示圆锥曲线、二次曲面与旋转曲面，因而获得广泛的应用。 最后在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 ) 的一整套理论和方法，因为它在 外形表示方面的强大功能与潜力，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 行业的工业标准。 在数学和计算机科学中，通常也用隐函数来定义几何物体。不等式描述了空问中 的半空间( 即实体) ，等式可定义该半空间的边界( 即隐式曲面) ，这种曲面表示方法在 几何造型和图形学中也得到了诸多的应用。参数化表示具有许多优点，如计算曲线曲面 的几何量较简单，曲线曲面的显示方便，具有离散等优良性质。然而，在另外一些几何 操作，如判断一个点是否在曲线或曲面上以及在那一侧时，参数化表示又极为不便。与 之相反，隐式化表示给这些操作带来了极大的方便。同时，隐式化表示在曲线曲面求交 方面也有极其重要的应用。因此，在c a g d 中，也越来越多的使用曲线曲面的隐式化表 不。 为了解决任意拓扑上的曲面造型，人们提出并发展了细分曲面( s u b d i v i s i o ns u r f a c e ) 造型方法。细分曲面是一类采用组成曲面的多边形网格点、线、面及其拓扑信息完整地 描述的曲面，这个多边形网格可以从手工模型上输入，也可以从激光扫描输入。他与连 续函数所描述的曲面再方法和数据结构上有着本质的区别。其基本方法是：从初始多面 体网格开始，按某种规则，递归的计算新网格的每个顶点，这些顶点都是原网格上相邻 的几个顶点的加权平均。随着细分的不断进行，控制网格就被逐渐磨光。在一定条件下 ( 一定的细分规则) 下，细分无穷多次之后多边形网格将收敛到一张光滑曲面。细分曲 面的最大优点就是算法简单，几乎可以描述任意复杂曲面，显著地压缩了设计和建立一 个原始模型的时间。而且，这种曲面造型方法在生动逼真的特征东化和雕塑曲面的设计 加工中如鱼得水，得到了高度运用。 人们在发展了曲线曲面的多种表现形式的同时也创造出了曲线曲面的各种构造技 术和方法，包括变形曲面构造技术、散乱点拟合造型技术、蒙皮( s k i n n i n g ) 造型技术、 广义s w e e p i n g 造型技术、基于变分原理的造型技术以及分形造型技术等许多方法。随着 应用领域的扩大和对造型质量要求的提高，人们还是不断地发展新的造型方法。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，随着集合设计 对象向着多样性、特殊性和拓扑结构复杂性靠拢的趋势的日益明显，随着图形工业和制 造工业迈向一体化、集成化和网络化步伐的日益加快，随着激光测距扫描等三位数据采 样技术和硬件设备的同益完善，曲面造型在近几年来得到了长足的发展。 第三节逆向工程的概述 随着科技的发展和市场的需要，工业产品越来越注重品种多样化、造型美观化，同 时也对产品的更新周期提出了更快的要求。在产品的开发及制造过程中，c a d 技术已使 用得相当广泛，但是，由于种种原因，仍有许产品并非由c a d 模型描述，设计和制造 逆向工程中旋转面重建的算法i i 】 究 者面对的是实物样件，有时，甚至可能连一张可以参考的图纸也不存在，这就为我们在 后续的工作中采用先进的设计手段和先进的制造技术带来了很大的障碍。为了适应先进 制造技术发展，需要通过一定的技术手段，将现有的实物( 产品原型或油泥模型) 转化 为相应的c a d 模型，使其能够利用现有的先进制造技术进行修改和分析，以生产出高 质量的产品。由此，产生了逆向工程( r e v e r s e e 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 = 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 c 设备上将对象加 工出来。 逆向工程主要涉及以下的关键技术：数据获取技术、产品建模技术。 数据获取技术 逆向工程通常使用测量仪器获得既有产品的坐标数据。数据点有一般两种类型，机 械三坐标测量机测量得到的是有序点数据；激光、数字成像测量得到的三坐标测量数据 是大批量、无序的点云数据。测量得到的数据必须经过处理才能用于曲面重构和三维建 模。由于仪器测量受诸多因素的影响，会产生一些不准确点和无效点，这些点统称为噪 声点，数据获取的过程就是有效点的抽取和噪声点剔除的过程。 产品建模技术 产品建模就是在数据获取的基础上，应用计算机辅助几何设计的有关技术，根据物 件的三维坐标数据，构造零件原形的c a d 模型。通常对于含有自由曲面的复杂型物体， 用一张曲面来拟合所有的数据点是不行的，一般首先按照原形所具有的特征，将测量数 据点分割成不同的区域，各个区域分别拟合出不同的曲面，然后应用曲面求交或曲面间 过渡的方法将不同的曲面连接起来构成一个体。有效的三位数据分割和拟合技术是逆向 工程中的重要内容。 作为c a d 工业的最新技术，逆向工程的应用领域大致可以分为以下几种情况： 在没有设计图纸或者设计图纸不完整以及没有c a d 模型的情况下，在对零件原形 进行测量的基础上形成零件的设计图纸和c a d 模型，并以此为依据生成数控加工的相 应代码，加工复制出一个相同的零件。 当要设计需要通过实验测试才能定型的工件模型时，通常采用逆向工程的方法。 比如航空航天领域，为了满足产品对空气动力学等要求，首先要求在初始设计模型的基 础上经过各种性能测试( 如风洞实验等) 建立符合要求的产品模型，这类零件一般具有 复杂的自由曲面外型，最终的实验模型将成为设计这类零件及反求其模具的依据。 在美学设计特别重要的领域，例如汽车外型设计广泛采用真实比例的木质或泥塑 模型来评估设计的美学效果，而不采用在计算机屏幕上缩小比例的物体透视图的方法， 此时需用逆向工程的设计方法。 另一个重要的应用如修复破损的艺术品或缺乏某些损坏零件等，此时不需要对整个 零件原形进行复制，而是借助逆向工程技术抽取零件原形的设计思想，指导新的设计。 总之，逆向工程技术可以应用在机械制造、航空航天、国防军事等c a d 行业所触及 1 0 逆向工程中旋转面重矬的算法研究 的每一个领域，并发挥其迅速、准确和机械化的特长，推动了c a d 行业新的制作手段 和方式。 国际上较早提出逆向工程方法的有h h o p p e ( 微软公司) 、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 大学) 等。逆向工程方法的出发点是对物理实体进行三维 扫描得到的数据点云，再对点云进行初步处理，首先转化成多边形模型【l 】- 【3 i 。在多边形 模型的基础上，形成四边形剖分，再进行适当的参数化。然后，用n u r b 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 pg 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 ) 建立采样点集( 点云) 。点云通常是有误差的，而且除了点的位置信息外没有几何信 息被预先得知( 如图l ，3 1 ) 。 图1 3 1 点云模型 2 1 建立多边形模型( 通常是三角形网格) 。有的设备能直接得到多边形模型。这一步的 逆向工程中旋转面重建的算法 l j f 究 主要目的是建立点云的拓扑信息以及给出最终曲面模型的一个初始估计( 如图1 3 2 ) 。 图1 3 2 多边形模型 3 ) 建立多边形模型的四边形剖分。这一步的目的是将多边形模型分割成一些小的面片， 每一个面片都将利用一个n u r b s ( b 样条) 曲面片来拟合，因此这些面片就被赋予了 “张量积”的结构，整个剖分也被称为“四边形割分”，这一步可以手工完成，也可 以通过一定的算法自动实现( 如图1 , 3 | 3 ) 。 图1 3 3 四边形模型 4 ) 根据设计要求对n u r b s ( b 样条) 曲面进行再处理。这主要包括连续性拼接，光顺 处理等。( 如图1 3 4 ) 逆向工程中旋转面重建的算法研究 图1 3 4 使用上述步骤完成逆向工程的完整过程如图1 3 5 所示 图1 3 5 逆向工程的一种实现过程 第四节旋转面的重建 一条曲线r 绕一条固定直线a 旋转而产生的曲面叫做旋转面( 回转面) 。在机械加 工、航空航天、考古研究等等领域中，很多零器件都是由一个或多个旋转面构成。在很 多情况下，为了更好的对此类零件进行修改，需要将其在计算机中重新表示出来。此时 就需要从现实中的零件模型，获取相应的实体数据，利用逆向工程的思想，使用相应的 步骤，在计算机中实现模型的表示，并给出旋转面的旋转轴以及母线，即旋转面的重建。 关于旋转面重建的算法，目前国内外研究的比较少。p j g i b l i n 等人曾经于9 0 年 逆向工程中旋转面重建的算泫研究 代中期讨论过这个问题，国内则更加缺少此类的讨论。近几年，随着各种新的几何设计理 论和算法的出现，旋转面重建已经不是一个很困难的问题。 在旋转曲面重建问题中，最主要的有两个问题，其一是反求旋转面的旋转轴，其二 是对于母线的平滑拟和，本文中就给出了一种直接针对点云信息求旋转轴，以及利用 n u r b s 拟和母线的方法并给出了数值结果。在本文的第二章，将对这几个方面作一定的 介绍。在第三章中对本文所提出的旋转面重建算法进行详细的讨论。 第二章旋转面的重建 第一节直角坐标变换 底矢变换 设已给两个直角坐标系盯= 【d ，q ，e ：，岛 ，盯。= b + ，e ：，e ；，e ；l ，并假定它们是右手系。 由于盯的底矢是两两垂直的幺矢( 空间中任意一个具有单位长的矢量叫做幺矢) ，则 e ，- 勺= j ，= ：；i ；c r = ，= ，z ，s ， c z t ， 其中占i 叫做k r o n e c k e r 符号。 同理，由于盯1 的底矢是两两垂直的幺矢，则 p ：已j = 占。= f ：i ；。= ，= t ，2 ，3 ， c 2 ，2 ， 此外，因为盯和d 是右手系，则 ( e l ，e 2 ，巳) = 1 ，( e l ，e 2 ，p i ) = 1 注意到：对于矢量a i ：( _ ，y l ，：1 ) ，a 2 ：( 戈2 ，y 2 ，z 2 ) ，a 3 ：( x 3 ，y 3 ，z 3 ) 显然 e l = 口1 1 e 1 + a 】2 e 2 + a l3 e e 22 a 2 1 e i + a 2 2 e 2 + a 2 3 e 3 e 32 n 3 l e l + a 3 2 e 2 + a 3 3 e 3 ( 2 1 3 ) ( 2 1 4 ) z 工 艽 i i )3 口 2 口盯 ( 逆向工程中旋转面重建的算法研究 其中，d f = p j 勺 ( 2 1 4 a ) 它是p ：和8 ，之间的角的余弦，在仃里，e ；的方向余弦是 可将盯和盯。的底矢之间的关系列成一个表 已19 2 已3 _ 盘1 1以1 2 盘1 3 e 】 口2 l以2 2 n ，1 p 2 岛 d 3 l以3 2 a 3 3 利用( 2 1 ，2 ) 式可得出 或 d j + a 之+ a 矗= 1 ， 口；+ 日刍+ 口2 2 3 = i ， 4 ；l + d 墨+ 4 三= 1 ， i 以i i 口2 i + 以1 2 以2 2 + 以1 3 盘2 3 = 0 ， o l l 口3 l + n 1 2 n 3 2 + n 13 口3 3 = 0 ， l a 2 1 a 3 l + a 2 2 0 3 2 + a 2 3 口站= 0 ( 2 1 5 ) ( 2 1 6 ) 口口= 瓦 ( f ，k ，j = 1 ，2 ，3 )( 2 1 7 ) i f 口i ld 1 2口1 3 1 令a = ld ：。d ：n ：，l ，由( 2 1 7 ) 可得a a = ，而且，由( 2 1 3 ) 式易知h = 1 ，因 l d 3 l】2口3 3 0 ，有逆矩阵4 ，于是 a + = a 一1 a a = 一一j = 一一1 其中，a = f ) ( f ，= 1 ，2 ，3 ) ，可见 爿= 4 q 于是，a 是正交方阵，且h = 1 。 ( 2 1 8 ) ( 2 1 9 ) ( 2 1 4 ) 式称为d 到仃的底矢变换公式，而且盯到盯的底矢变换矩阵a 是行列式等 于1 的正交方阵。 逆向工程中旋转面重建的算法研究 同理，也有 其中，b 口= q 口j e 1 2 b 】e 】+ b 1 2 e 2 + b t 3 e 3 ， p 2 = b 2 1 8 ：+ b 2 2 e ：+ 6 2 3 e 3 ， e 3 = b 3 1 8 ：+ 6 3 2 8 ；+ b s 3 e ： 它是e ，和8 7 之间的角的余弦，在盯里，e l 的方向余弦是 ( b b i 2 ，b 1 3 ) ( f - 1 , 2 ，3 ) 显然和口都表示p ，p ，。于是6 f = ，系数方阵口= a ，即 可见h = 1 时，爿= d 得 利用( 2 1 1 ) 式，可得出 a 2 ia 3 l1 a 2 2a 3 2l a 2 3a 3 3 e l = 口l i e i + a 2 l e 2 + 盘3 l e 3 ， e 2 。a 1 2 e i + a 2 2 e 2 + a 3 2 e 3 e 32 a 1 3 e l + a 2 3 e 3 + a 3 3 e 3 口i + 口：+ q 2 l = 1 ， n 三+ a 2 2 2 + d3 2 2 = 1 ， 口j + 嘉+ 口3 3 2 = 1 ( 2 1 1 0 ) f 2 1 i o a ) ( 2 1 1 1 ) r 2 1 1 2 ) ( 2 1 1 3 ) 或 口p 口m = 占n ( ，k ，i = 1 ，2 ，3 ) ( 2 1 1 5 ) f 此外，由i a i ：1 知瞳j ：1 ，a 是正交方阵，a 。也是正交方阵。 ii l ( 2 1 1 2 ) 式称为盯+ 到盯的底矢变换( 公式) ，而且盯1 到仃的底矢变换方阵爿。也是行列式 口 口 口 ，l 1 1 ) ， 口 ( i i ) ( i i b 垒h = 呱 外此 ， q仉q o = i | = 陬呈如q 吩吼 + + + m m 加 + + + m 心埔 以 口 r，、l 逆向工程中旋转面重建的算法珂f 究 等于1 的f 交方阵。 点的坐标变换 设p 是空间任意一点，它在直角坐标系o - 和盯+ 下的坐标依次是( x ，y ，z ) 和( x ，y ，z 。) 而盯的原点0 在盯下的坐标是( x 。，y o , z 。) 。 由( 1 1 ) 式及坐标平移的基本原理， 即 x2 a l l x + a l2 y + a 13 z + x o ， y = a 2 1 x + a 2 2 y + a 2 3 z + y o ， ( 2 1 1 6 ) z = 口3 l x + a 3 2 y + a 3 3 z + z o 其中，x j = 一( 1 1 x o + a t 2 y o + a 1 3 z o ) y o = 一( 口2 i x o + a z 2 y o + a 2 3 z o ) z o = 一( 盘3 l x o + 口3 2 y o + a 3 3 z o ) 戎1 卜 y ：9 y 口，。 d ，： 口，z j l z 0 00 1 几1 ( 2 1 1 7 ) ( 2 1 1 6 ) 式称为仃到仃的( 点的) 直角坐标变换( 公式) ，其中( x ：，y ：，z j ) 是仃的原点 0 在盯+ 下的坐标。 同样， 即 x = a l l z + a 2 1 y + a 3 1 z + x o ， y = a 1 2 x 。+ a 2 2 y + 口3 2 z + y o ，( 2 1 1 8 ) z = a 3 x + a 2 3 y + a b b z + z o ， ( i l l a 2 1 a ，。石。1 f x y 。卜 n ， n ：，” 三。l l z 0 00 1 j 1 1 f 2 1 1 9 ) ( 2 1 1 0 ) 式称为o - + 到盯的( 点的) 直角坐标变换( 公式) ，其中( x 0y 。，z 。) 是盯的原点0 + 在盯下 的坐标。 逆向工程中旋转面重建的算法研究 第二节散乱数据的三角剖分 散乱数据的三角剖分是构造散乱数据插值曲面时必不可少的前置处理。三角剖分为对三 维散乱数据投影域包括平面域和球面域。直接三角剖分法研究如何直接将三维散乱数据 点在空间中连接成一个最优的三角网格。 与三角剖分有关的若干定义 先给出与三角剖份有关的一些基本概念。 ( 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 e h l e t 域分割( 粗线) 和d e l a u n a y 三角剖分( 细线) ( 3 ) 优化 对三角网格进行优化，就是要使三角网格整体上尽量均匀，避免出现狭长三角形 亦即获得d e l a u n a y 三角化。 三角剖分优化准则 在三角剖分过程中，我们往往用一种比较简单的方法构造散乱数据点的初始三角剖 分，然后对其进行优化以获得d e l a u n a y 三角剖分。优化的方法和效果取决于所采用的优 逆向1 = 程中旋转面蘑建的算弦研究 化准则。常用的优化准则有t h i e s s e n 区域准则、最小内角最大准则、圆准则、球面准则、 a b n 准则、p l c 准则、多面体表面积最小准则，多面体体积最大准则及空间光顺准则等。 前三者为平面三角剖分优化准则，s i b s o n 证明了这三个准则的等价性，并指出符合这三 个准则的三角剖分只有一个，即d e z a u n a y 三角化，其余各准则可视为空闫三角网格的优 化准则。 ( 1 ) 最小内角最大准则 对一个严格凸的四边形进行三角化时，有两种选择。最小内角最大准则就是保证对 角线两侧两个三角形中的最小内角为最大，如图2 2 2 和图2 2 _ 3 所示： 一_ 令 图2 2 2 最小内角最大准则图22 3 圆准则 ( 2 ) 圆准则和球面准则 严格凸四边形中的三个顶点确定一圆，如果第四个顶点落在圆内，则将第四个顶点 与其相对的顶点相连，否则将另两个顶点相连，称为圆准则，如上图所示，球面准则可 表述为：列于两共面的四面体a 和b ，若a 的不属于b 的顶点位于b 的外接球内，则 需对两四面体的拓扑关系进行变换；若位于b 的外接球外，则两四面体不做变换，保持 其拓扑关系不变。 ( 3 ) a b n 准则( a n g