（计算机软件与理论专业论文）有序点曲线重构的研究和应用.pdf

山东大学硕士学位论文 摘要 逆向工程技术是随着计算机技术的发展和成熟以及数据测量技术的进步而迅 速发展起束的- - f 7 新兴学科与技术。它的出现，改变了原来c a d 系统中从图纸到实 物的设计模式，为产品的迅速开发以及快速原型化设计提供了一条新的途径。曲线 和曲面的重建是逆向工程中的重要问题，特别是按照计算机图形学中点线面的发展 规律，曲线重构更是其中很重要的一步，它为后面的曲面重构奠定了研究基础。重 构问题是指由已知的采样数据点构造出物体的几何模型。这是对物体进行分析，计 算和绘制的根据，也是研究曲线和曲面性质的重要途径。 本文首先介绍了计算机辅助设计与制造技术的发展历史，从而引出该领域的 一个新的研究热点逆向工程的概念和逆向工程中的曲线重构问题以及一些已 有的解决方法。 第二章丌始介绍对有关有曲线拟合的重要的定义和目前常用的方法的思想。 对于曲线拟合最早可以追溯到曲线的二乘拟合。曲线的最终实现方式由早期的多 项式曲线发展到参数曲线进而发展到现在的一个新热点细分曲线。就参数曲 线而言，数据点的参数化是一个重要步骤。目| ；i 常见的参数化方法有均匀参数化， 累加弦长参数化，向心参数化等。对于细分曲线，现在也提出了很多常用的概念 和方法。 第三章针对参数曲线的常见参数化方法提出了一个改进算法。目前的参数化 方法大多不具有仿射不变的特性，即在进行某个或一系列仿射变换后为了正确反 映曲线的形变而不得不重新参数化，从而效率较低。新的方法改进并证明了 n i e l s o n 仿射不变基函数，后将其应用在参数化过程中，取得了良好的效果。但是 幺方法的数学定义无法处理已知数掘点在一条直线上的情况。 第四章针对第三章的遗留问题提出新的解决方法一细分曲线。这种曲线重 构方法本身不是参数曲线重构，因而不用先做参数化，而是直接根据已知数据点 的位置关系插入新的定点，逐层细化后连成一条曲线。这种方法思路简单，本身 不受任何仿射变换影响。与目前常见的细分方法不同的是，本文提出的方法采用 半静念回插思想。更为有意义的是回插时根掘上层数据点的位置特征和相对偏移 山东大学硕士学位论文 回插，从而尽可能的对曲线保形。同时半静态的思路还使这种方法可被用于计算 机设计中。 最后文章分析了曲线重构问题的困难所在，分析了文中介绍的方法的优点和 缺点。文中提出的新方法都还停留在曲线问题的研究上，将来还可以将它们应用 于曲面重构的研究领域中。 关键词：逆向工程，曲线曲面重构，参数化，细分曲线 山东大学硕士学位论文 c u r v er e c o n a s t r u c t i o nf r o mo r g a n i z e d p o i n t s g r a d u a t es t u d e n t ：p e n gk u n d i r e c t o r ：p r o f z h a n gc a l m i 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 wt e c h n i q u ed e v e l o p i n gw 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 ep r o g r e s so fd a t am e a s u r i n gt e c h n o l o g y i t sa p p e a r a n c eh a s i nf a c tc h a n g e dt h ed e s i g nm o d eo fp r o d u c i n gm a t e r i a lo b j e c t si nc a ds y s t e mf r o m d r a w i n g i td e s i g n sa n do f f e r san e ww a yf o rf a s tp r o d u c t i o na n dr a p i dp r o t o t y p i n g c u r v ea n ds u r f a c er e c o n s t r u c t i o na r et w oi m p o r t a n tp r o b l e m si nr e v e r s ee n g i n e e r i n g r e c o n s t r u c t i n gt h eg e o m e t r i c a lm o d e lo ft h eo b j e c tf r o mt h es a m p l ep o i n t sc a r r i e so n t h ef o u n d a t i o no fa n a l y z i n g ，c a l c u l a t i n ga n dd r a w i n go ft h eo b j e c t i ti sa l s oa n i m p o r t a n tw a y t os t u d yt h en a t u r eo f c u r v e sa n ds u r f a c e s t h i sp a p e rf i r s ti n t r o d u c e st h ed e v e l o p m e n th i s t o r yo fc o m p u t e ra i d e dd e s i g n & c o m p u t e ra i d e dm a n u f a c t u r e ，a n dt h e nd e r i v et h ei d e ao fr e v e r s ee n g i n e e r i n ga n d c u r v er e c o n s t r u c t i o nf r o md a t ap o i n t s s o m ee x i s t i n gm e t h o d sa r ei n t r o d u c e d i nc h a p t e r2 ，s o m ei m p o r t a n td e f i n i t i o n sa n ds o m ec ：0 m m o ni d e a sa b o u tc u r v e f i t t i n ga r ep r o v i d e d i nt h ea r e ao ff i t t i n gac u r v e ，t h ef i t t i n gm e t h o dc a nt r a c eb a c kt o t h el e a s t - s q u a r e sm e t h o d t h ec u r v ef i n a lf o r m a t i o nh a sd e v e l o p e df r o mp o l y n o m i a l c u r v et o p a r a m e t r i cc u l w ea n dt h e nt o t h en e wh o t s p o t _ s u b d i v i s i o nc u r v e t o p a r a m e t r i cc u r v e ，t h ep a r a m e t e r i z a t i o ni sak e ys t e p s o m ec o m m o np a r a m e t e r i z a t i o n m e t h o dh a sb e e ni n t r o d u c e di nt h ep a p e r t os u b d i v i s i o nc u r v e , m a n yc d m m o n c o n c e p t sa n dm e t h o d sa r ep r o v i d e dt o o i nc h a p t e r3 ，an e wa r i t h m e t i co fp a r a m e t e r i z a t i o ni sp r o v i d e di na l l u s i o nt ot h o s e c o m m o nm e t h o d s t h ee o n l l n o nm e t h o d sa l m o s th a sn oa f f i n ei n v a r i a b i l i t y , t h a ti st o s a y , p a r a m e t e r i z a t i o nh a st ob ee x e c u t e da g a i na f t e ra f f i n et r a n s f o r m a t i o n st og e tt h e 山东大学硕士学位论文 r i g h tt r a n s f o r m a t i o nr e s u l t t h e n t h e i re f f i c i e n c yi s c o m p a r a t i v e l yl o w t h i sn e w m e t h o dd e v e l o p sa n dd r o v e st h en i e l s o nb a s i cf u n c t i o n a n dt h e nu s et h en e wf u n c t i o n t op a r a m e t e r i z a t i o na n da b t a i nt h eg o o dr e s u l t b u tb e c a u s eo fi t sm a t h e m a t i c a l d e f i n i t i o n t h em e t h o dc a nn o td e a lw i t l lt h es i t u a t i o nw h e nt h ep o i n t sa r ea l lo i lal i n e c h a p t e r4g i v ean e ws o l u t i o nf o rt h ec a r r y - o v e rq u e s t i o ni nc h a p t e r2 1t i s s u b d i v i s i o nc h i v e t h i sm e t h o di t s e l fi sn o tt h ep a r a m e t r i cc h i v er e c o n s t r u c t i o n , s oi t n e e dn o tp a r a m e t e d z a t i o n an e wp o i n ti si n s e r t e di na c c o r d a n c ew i t ht h ep o s i t i o no f k n o w np o i n t s t h e ni t e r a t i o no ne v e r yl a y e rt og e tac u r v e t h i sm e t h o d sa r i t h m e t i ci s s i m p l e ，a n di t w i l ln o tb ea f f e c t e db ya f f i n et r a n s f o r m a t i o n d i f f e r e n tt oc o m m o n s u b d i v i s i o nm e t h o d ，t h ei d e ao fh a l f - s t a t i ca n dp u s h b a c ki sa d o p t e d w h a ti sm o r e r e a s o n a b l ei st h a t p u s h - b a c k i si m p l e m e n t e da c c o r d i n gt ot h eo f f s e ta n dt h e c h a r a c t e r i s t i co ft h ek n o w np o i n t s a tt h es a m et i m e ，t h em e t h o dc a nb eu s e di n c o m p u t e rd e s i g nf o ri t sh a l f - s t a t i c f i n a l l y , t h ep r o b l e mo fc h i v e r e c o n s t r u c t i o ni s a n a l y z e d ，a n d t h i s p a p e r s u m m a r i z e st h em e r i ta n df l a wo f t h em e t h o dw h i c hi sp r o v i d e di ni t a l lt h en e wi d e a s g i v e ni nt h ep a p e rs t i l ls e t t l eo nr e s e a r c ho fc u r v e ，a n dt h e yc a nb eu s e do i ls u r f a c e r e c o n s t r u c t i o ni nt h ef i l n l r e 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 ，c u r v ea n ds u r f a c er e c o n s t r u c t i o n , p a r a m e t r i c ， s u b d i v i s i o nc u r v e 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个 人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名： 薹! 盈毖 日期： 嫩幺。( 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅：本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：堑圣毙导师签名： 山东大学硕士学位论文 第一章绪论 计算机辅助设计与制造技术( c o m p u t e ra i d e dd e s i g n & c o m p u t e ra i d e d m a n u f a c t u r e ) 简称为c a d c a m 技术，是计算机应用的最重要的领域之一，系指利 用计算机技术完成设计过程中的信息检索、分析、计算、综合、修改及文件编制工 作。它是先进制造技术的重要组成部分，是计算机在工程中最有影响的应用技术之 一，曾被美国国家工程科学院评为当代十项最杰出的工程技术成就之一。 c a d c a m 技术从根本上改变了过去的手工绘图、发图、凭图纸组织整个生产 过程的技术管理方式，将它变为在图形工作站上交互设计、用数据文件发送产品定 义、在统一的数字化产品模型下进行产品设计打样，分析计算。工艺计划、工艺装 备设计、数控加工、质量控制、编印产品维护手册、组织备件订货供应等等。 c a d 技术的迅速发展和推广应用，给古老的制造工业带来了蓬勃生机，使传 统的设计方法与生产组织模式发生了深刻的变化。为企业实现产品设计现代化、缩 短设计周期、提高产品质量、增强市场应变能力和生存能力、参与国际市场竞争提 供了强有力的技术手段。c a d 技术丌发与应用水平已成为衡量一个国家科技现代 化和工业现代化水平的重要标志之一。经过近4 0 年的发展历程，c a d c a m 技术 已r 趋成熟，其应用范围也从早期的军事、航空航天、机械、电子等工业部门扩展 到冶金、建筑、化学、医学、教育，影视、广告等各个专业领域。 作为c a d c a m 技术的理论基础的计算机辅助几何设计( 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 ，缩写为c a g d ) ，最初是在一九七四年在美国召丌的第一届c a g d 国际会议上d ：l b a m h i l l 和r i e s e n f e l d b a m h i l l1 9 7 4 1 提出的。自此以后，计算机辅助 几何设计丌始以一门独立的学科出现。c a g d 是对几何外形信息的计算机表示、分 析和综合，研究的是计算机表示以及用计算机控制有关形状信息的问题。这罩所说 的几何外形信息是指那些定义曲线曲面的点、切矢、扭矢、控制多边形等等。按照 这些几何信息构造曲线曲面的数学模型存贮于计算机中，这就是计算机表示。用计 算机控制就是控制曲线曲面的形状，使构造的曲线曲面符合设计要求。c a g d 是 由函数逼近论、微分几何、代数几何、计算数学，特别是数控技术等形成的边缘学 科。随着现代工业的发展，计算机在几何设计中的应用愈来愈多，有关计算机辅助 山东大学硕士学位论文 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! - _ _ l _ 一 几何设计的数学方法的研究也在不断深化，并逐渐形成了具有自己的独特优点和研 究领域的新学科。它的每一个重大技术突破都会影响着诸如计算机图形学、计算机 视觉、机器人技术、医学图象处理、可视化、多媒体技术等等许多相关领域的进步 与发展。 1 1 曲线重构的应用背景 从日甜的情况柬看曲线雷构的一个非常大的麻用领域就是逆向t 稃。逆向 工程技术在许多工业领域中有着广泛的应用。在仿型设计中，需要克隆某个产品， 然而通常却没有该产品的原始设计草案或文档。在零件的修改与改良设计中，需 要从现存的产品出发，构造出它的几何模型，从而可以利用现有的c a d 系统进 行进一步的分析与优化，进而丌发出新的产品。在汽车工业等领域，车体外壳的美 图1 i 逆向i ：拌体系结构图 学设计尤其重要设计师更喜欢在真实的雕刻或油泥模型上进行设计。因为实物 模型比计算机二维屏幕更能真实的反映物体的形状，更有利于设计师阐释他的设 山东大学硕士学位论文 计思想。在特制的服装、鞋帽等产品定制领域，由于每个人的面部，身体结构不 同，统一的尺码并不一定适合客户的要求，又由于批量小，可能就只生产一件产 品，传统的设计方法冗长费时，在经济上也不合适。逆向工程的体系结构如上图 1 1 所示，它由离散数据获取技术、数据预处理与三维重建以及快速制造三部分 组成。 1 1 1 表面数据获取技术 在逆向工程中，物体的表面数字化是关键的第一步，是逆向工程的基础。只 有获取测量数据，才能进行误差分析和曲面比较，进一步进行曲面重建( c a d 建 模) 。 现有的三维数据的获取方法基本上可分为两大类，即接触式与非接触式。接 触式测量是指利用接触式测量仪器对实物外表面进行测量。在接触式测量方法中， 机械坐标测量机( c 删) 是一种发展较为成熟测量设备，它是利用传感器实现测量头 在工件上移动，将复杂的三维曲面测量转化为二维测量，按曲面曲率的变化不均 匀地布点，从而记录下路径点的坐标值。它具有噪声低，精度高，重复性好等优 点。但测量速度慢、效率低，不易获得连续的坐标点。测量数据的特点是高精度 低密度。 非接触式测量法可分为光学法、工业c t 、超声波法和核磁共振( m p a ) 等。随 着机器视觉技术和光电技术的发展，采用光电方法的非接触测量技术得到迅速发 展。新的测量技术如激光技术、材料转移的光谱技术、三维全息照相显示技术不 断地涌现。相应的测量方法有相位法，深度图象法，全息法，激光三角形法等。 三维坐标测量机和激光快速扫描仪广泛应用于逆向工程中，但是它们有一个相同 的缺陷就是无法测定零件内部的轮廓尺寸，因此在快速原型技术中受到很大的限 制。能实现物体的内轮廓线测量的典型方法有工业c t 和逐层切削照相测量。工 业c t 成本较高，所获得的点以物体的横截面形式绘出，精度较低，但它不损伤 实物，是测量没有备件或复制品的复杂形状实物的唯一方法。逐层切削照相测量 是一种新兴的断层测量技术，它以极小的厚度逐层切削实物，并对每一断面进行 照相，获取截面图像数据。其轮廓测量精度可达0 0 2 5 4 m m ，是目前断层测量精 度最高的方法，而且成本较低，但它的突出缺点就是损坏了实物。从发展趋势看， 3 山东大学硕士学位论文 工业c t 和逐层切削照相测量将占逆向工程测量方法主导地位，应用范围也会更 加广泛。 1 1 2 数据预处理 逆向工程中的一个重要问题也是首先需要解决的问题就是采样数据点。数据 处理过程包括点的精简与光顺处理、点的聚合、数掘点的分块三大部分。 无论是通过三维坐标测量仪还是激光扫描仪，将物体数字化后得到的是一大 批的数据点云，不便于直接进行曲线曲面拟合。由于不可避免的测量误差，得到 的采样点集并非完全落在原物体上。出于激光扫描设备的局限性，固定物体和设 备从一个方向进行采样无法获得物体的完整采样。因此在扫描过程中，要从多个 方向对物体进行扫描，得到多张视图数据，然后通过点的聚合，再对它进行拼接。 此外获取数据的方式不同，得到的初始数据点集也不一样。基于上述原因，需要 对数掘点进行简化，聚合等预处理，以便于进行三维物体的曲面重建。 1 1 3 有序离散点的曲线重建 曲线拟合在逼近论和几何造型中都是一个主要的研究课题。所谓有序离散点的 曲线重建是指给出列依次采样于某条已知曲线上的一系列采样点，如何构造出一条 曲线依次通过或近似通过这些采样点，作为原曲线的逼近。 基于有序点的曲线拟合，最早可以追溯到曲线的二乘拟合。然而在逆向工程中， 对有序点进行凿线拟合，要求得到的重建曲线能够反映出原始点集的形状与特征， 于是越来越多的研究者针对有序数掘点的保形曲线拟合做出了许多有益的研究。 1 9 8 1 年，m c a l l i s t e r 给出了用二次样条曲线进行插值重建的算法【1 】，f d t s c h 和c l a r s o n ，b u t l a n d 等人讨论了用如何分段三次曲线进行插值曲线重建( 【2 】、【3 】) ， 更一般的，p a s s o w 和r o u l i e r 讨论了如何用多项式样条函数进行有序点曲线重建的 问题( 【4 】) 。 随着有理曲线的进一步研究，和对有理曲线性质的掌握，如何运用有理曲线进 行有序数据曲线重建也被越来越多的研究者提出来( 【5 】、【6 】、【7 】) 。 随着多分辨率思想地提出，如何用多尺度样条拟合数据点这一课题摆在众多研 山东大学硕士学位论文 究者面i j i ，2 0 0 0 年l a v e r y 在【8 】文中给出一种用三次光滑l l 样条多尺度地保形拟 合数据点地新方法( 9 ， 1 0 ) 。 1 2 本文所要做的工作 逆向工程中所涉及的具体问题很多，而本文主要是针对其中的有序点曲线重 构问题进行研究。曲线重构是建立在表面数掘获取和数据预处理的基础上，同时 又为后面的曲面研究提供基础的理论依据，所以它是个承上启下的重要工作。在 回顾计算机图形学和计算机辅助几何设计中有关曲线的基础知识的基础上，本文 作者作了如下的工作： ( 1 ) 观察各种目前常用的参数化方法，发现其不具有仿射不变的性质这一弱 点。对此提出一种新的参数化方法，并验证此方法具有仿射不变的特性。( 2 ) 以 b 样条函数编程实现曲线，对新方法的曲线与同样具有仿射不变特性的n i e l s o n 参 数曲线进行比较。( 3 ) 针对文中提出的新参数化方法无法处理数据点共线的情况 进行进一步的改进，采用细分曲线的技术，无须参数化逐步迭代重构出曲线，因 此也不会再受仿射变换的影响了。( 4 ) 以m a t l a b 和几组典型的数据点设计出一个 细分曲线系统。 1 3 各章安排 奉义第一章丌始首先介绍一些有关曲线的基础知识和相关定义，以及目前有 关曲线的许多研究成果。这些内容都是后面进行讨论的基础。第三章介绍仿射变 换的定义，进而提出新的具有仿射不变特性的参数化方法。第四章针对新方法的 弱点采用细分曲线技术进一步改进。 山东大学硕士学位论文 第二章曲线重构综述 在数据处理之后，逆向工程的核心问题便是如何从采样点出发重建出曲线、 曲面模型。传统的曲面重建方法，是按点一线一面的重建顺序柬获得重建曲面 7 。 先由点定义出一组特征线，然后由这些曲线构造曲面。在旋转面，扫成面，螺旋 面等特殊的曲面重建中，需要先分别重建出他们的脊线与母线，然后得到整个曲 面的几何表示模型 8 。因此曲线重构是曲面重构的基础。首先来介绍一下曲线的 几个基本概念。 1 1 插值和逼近 给定一组有序的数据点p ，f = 0 , 1 ，胛，这些点可以是从某个形状上测量得 到的，也可以是设计人员给出的。要求构造一条曲线顺序通过这些数据点，称为 对这些数据点进行插值( i n t e r p o a t i o n ) ，所构造的曲线称为插值曲线，这些数 掘点若原来位于某曲线上，则称该曲线为被插曲线。构造插值曲线所采用的数学 方法称为曲线插值法。同理也可以推广到曲面上。插值法在c a g d 实践中有着广泛 的应用。 然而，在某些情况下，测量所得或设计人员给出的数据点本身就很粗糙，要 求构造一条曲线严格通过给定的一组数据点就没有什么意义。更为合理的方法应 是，构造一条曲线使之在某种意义下最为接近给定的数据点，称之为对这些数据 点进行逼近( a p p r o x i m a t i o n ) ，所构造的曲线称为逼近曲线。这些数据点若原来 位于某曲线上，则称该曲线为被逼曲线。构造逼近曲线所采用的数学方法称为曲 线逼近法。类似地，可将曲线逼近推广到曲面。 插值和逼近统称为拟合( f i t t i n g ) 1 。 最 j 、r - 乘法是曲线拟合的重要方法，是目i j i 比较常用的逼近思想，在这里也作 些介绍。考虑如下的刀次参数 肌) 多项式曲线 尸( f ) = q 仍( f ) j 一0 山东大学硕士学位论文 其中移( 吐i = 0 , i ，玎为n 次多项式空间的一组基，q = 置只乏】，i = 0 , i ，月 为待定的系数矢量。设给定的数据点为只= k 服气】，七= 0 , 1 ，m ，于之相应的参 数是f o t m 。如果当作插值问题处理，将有如下线性方程组 写成矩阵形式 其中系数矩阵 为( m + 1 ) x + 1 ) 阶矩阵 口，仍( 气) = 最， k = 0 , 1 ，垅 j = 0 彳= p a = 仍( 气) 仍( ) 仍( 0 ) 碧乃目 这罩矢量方程个数坍+ 1 超过了未知矢量个数n + 1 这样的方程组称为超定的， 或称为矛霸方程组在一般情况下，解是不存在的即一般地不存在严格依次通过 这些数掘点的插值曲线尸这时，我们只能寻求在某种意义下最接近这些数据点 的参数多项式曲线p ( f ) 作为逼近曲线。 度量逼近的程度最常用的一种方法是取逼近曲线p ( t ) 上具有参数值 的点 j p ( ) 与数掘点只问的距离平方和 ，= l 尸( ) 一层1 2 = 以+ 以+ 也 k = o 达到最小，称之为最小二乘逼近 ( l e a s ts q u a r e a p p r o x i m a t i o n ) ，j = ( 以，。，以) 称为目标函数。其中 魄“心 。l = 山东大学硕士学位论文 以= 【i 纪( 吒) 一黾】2 t = 0 1 = 0 n t ，。= 【只纪( 气) 一儿】2 t = 0 1 = o , q ln 以= 乏够( 气) 一乙】2 欲使，为最小，就应使以，以，以都为最小。为此必须使下列偏导数为零 j = 0 , i ，疗 由上式不难推出高斯( g a u s s i a n ) 正交方程组 矽刚= 矽7 p 又称为法方程其中矽是妒的转置。由于够( f ) ，i = 0 ，1 ，疗线性无关，故妒是满 秩的。彩。妒是朋+ l 阶对称可逆阵，方程存在唯一解。 考虑到实际所给数据点的重要性与可靠性有可能是各不相同的，为此，可对 每个数据点引入相应的权( w e i g h t ，或称因子权) 吃，七= 0 ，l ，脚，使得重要性与 可靠性高的数掘点对形成p ( f ) 的影响大。于是，目标函数相应地变成 ，= 吃| p ( ) 一只f ；o 有多种实用的求解法方程的方法，如j 下交化方法和改进的正交化方法等。解之， 即可求出未知系数矢量矩阵a 。于是，就定义了逼近曲线p ( r ) ，特殊地，如果f h ， 逼近曲线就成为插值曲线。 1 2 参数曲线 参数多项式曲线是c a g d 技术发展的一大进步，在此之前插值法和逼近法就已 被广泛用于科研与生产实践。那时的曲线都采用多项式函数来构造。在做插值时， o o o = i l = 弘一喝笪砺一喝 山东大学硕士学位论文 参数多项式相比多项式函数，更为灵活，参数与数据点问的对应关系使它更具有 一定的意义。 曲线有两种基本的表示形式。在解析几何中，空间曲线上一点p 的每个坐标 被表示成某个参数的函数工= 工( ) ，_ y = y ( z f ) ，z = z ( u ) 。把这三个方程和谐在一起， 三个坐标分量就组成曲线上该点的位置矢量，曲线被表示为参数“的矢函数。 p ( “) = x , y ，2 】= 【工( “) ，y ( “) ，z ( “) 】 它的每个坐标分量都是以“为变量的标量函数。这种表示方法等价于笛卡尔 分量表示：p ( u ) = x ( u ) i + y ( u ) j + z ( u ) k ，其中f ，j ，k 分别为沿工轴、y 轴、z 轴正 向的三个单位矢量。理论讨论时，通常将上述曲线简记为p = p ( u ) ，这种记法就 是曲线的参数表示。这不仅被看作是一种简洁的记法，更重要的在于它把曲线上 表示一个点的位置矢量的各个分量合写在一起当成一个整体。实际应用中真正有 用的诈是整条曲线上各个点之间的相对位置关系而不是它们与所取坐标系之间的 相对位置关系。 在代数学中，存在曲线的非参数形式y = y ( x ) ，它也被称为标量显函数。事 实上，对应这种标量显函数存在如上对应的参数形式。只需将其中的变量x 换成 l ，将函数值v 换成位置矢量p 若在具体方程中遇到标量的系数相应换成为系 数矢量，各阶导数立换成各阶导矢盈。然而这种对应关系和替换不是等 积 c l u 价的。在非参数形式下的隐方程可以转换成等价的参数形式，只需把所含各坐标 都分别表示成某一参数的函数，使它们适合该隐方程。 在杯量显函数中，由各个工的值代入便可得到相应的y ，将这些( x ，y ) 对 应的点相连便可得到曲线。对于参数曲线则要由参数去决定函数值。由于曲线形 状总是有界的，因此参数曲线的范围可以方便的用参数区间定义，即打【阮，甜：】来 表示，这也被称为参数域。 参数曲线中的参数可由数据点的位置关系获得，所以通常情况下，参数往往 具有某种几何意义。例如x o y 平面上第一象限单的圆心位于原点的四分之一单位 9 山东大学硕士学位论文 圆。 p = c o s ( o ) ，s i n ( o ) 】，0 口 其中口就具有明确的几何意义，它表示从圆心到圆上一点的半径矢量对于x 轴诈向的央角。当然参数也可能没有意义，如参数二次多项式p = 编+ 口u + 0 2 1 1 2 中的参数就没有任何几何意义。这被称为一般参数 2 。 给定一个具体的单参数的矢函数，即给定一个具体的参数曲线方程，称之为 给定了一个曲线的参数化。它既决定了所表示曲线的形状，也决定了该曲线上的 点与其参数域内的点之间的一种对应关系。目前有几种常用的参数化方法，这将 在本章第三节中介绍。 1 3 细分曲线技术 由于计算机图形学、计算机动画等领域对任意拓扑结构的光滑曲线曲面造型 的需求变得r 益追切，n u r b s 曲线曲面在表示复杂拓扑结构的物体方面存在着 许多凼难，无法满足这一要求，而细分方法由于能够很好地产生拓扑结构复杂的 曲面，因此，成为近年来曲面造型技术研究的一个热点，得到了越来越多的研究。 在3 d 曲面造型、多分辨率分析和计算机图形学等领域中获得了广泛的应用。尤其 在生动逼真的特征动画和雕塑曲面的设计加工中得到了高度的运用。细分方法受 到普遍欢迎的一个主要原因就在于它能够快速地在任意网格上生成光滑曲面，算 法简单直观。细分曲线作为一种新的曲线生成方法成为上述两种基本方法的补充。 细分方法可以被简单解释如下：将光滑曲线或曲面定义为连续细化过程的极 限。细化就是根掘原有数据点的关系或是某种规则产生新的顶点，这是一个逐层迭 代的过程。对于曲线来说，就是在已知数据点的基础上，加入新点直至点与点之白j 的距离达到一定阀值或是人眼感觉不出来了；对于曲面来说，就是在已知曲面网格 的基础上得到更细的网格，直至网格接近一个像素的大小。当然，这是一个相当不 精确的描述，许多细节仍未解释清楚，但是它却抓住了细分的本质。 事实上，细分的基本思想很早就出现了，它可以追溯到上世纪四十年代晚期和 五十年代早期。其创始人可以追溯至t j s 0 年代的d er h a m 3 ，当时d e r h a m 就已经 使j f 】对多边形割角( c o m e r c u t ) 的方式柬描述一条光滑的曲线。但最初引起c a g d 领 山东大学硕士学位论文 域注意的，是在1 9 7 4 年美国u t a h 大学举行的c a g d 国际会议上，图形艺术家 c h a i k i n 提出的一种与众不同的曲线的快速生成方法。它以直观的几何构造为摹础， 由一个闭合的2 d 多边形开始，通过重复的割角操作，来得到一条光滑的极限曲 线 4 。随后r i e s e n f e l d 5 和f o r r e s t 6 从理论上证明了这种极限曲线其数学本质即是 均匀二次b 样条曲线。c a t m u l l 和c l a r k 7 ，d o o 和s a b i n 8 贝l j 分别提出了将双三次 和双二次b 样条曲面推广到任意拓扑网格上的细分算法，标志着细分曲面应用于曲 面造型的丌始。在近二十年来，新的细分方法不断涌现。1 9 8 7 年，l o o p 在其硕士 论文中首次提出了一种基于三角网格的逼近细分 9 。该方法是在b o e h m 1 0 和 p r a u t z s c h 11 1 的箱样条( b o xs p l i n e ) 细分算法的基础上提出的，将四次三向箱样条 ( q u a r t i c 3 一d i r e c t i o n b o xs p l i n e ) 推广到任意的三角网格上。d y n 等人则提出了一种四 点插值的曲线细分规则 1 2 ，并据此给出了基于三角网格的插值型细分方法，生成 所谓的蝶形曲面( b u t t e r f l ys u r f a c e ) 1 3 】【1 4 ，该曲面能够插值初始控制网格的所有顶 点以及细分过程中所产生的新点。但是，这种细分方法要求初始网格是正则的三角 网格，即每个顶点的共点三角形数均为6 ，如此才能保证极限细分曲面是c 1 连续的。 以上四种基本的细分方法是细分方法发展早期阶段的重要研究成果，为后来新的细 分方法提供了可兹借鉴的构造途径，且在实际应用中，仍发挥着重要作用。图1 2 中给出了这几种主要细分方法的实例比较 臼两国 釉扣 d o e s a b i n 纷分方法 山东大学硕士学位论文 臼圆国 铷扫 c a t m u u c l a r k 鳃分方滚 臼胁叁 铷_ l o o p 组分方泣 臼国秘 参加 b u t t e r f l y 细分方法 幽1 2 各种细分方法举例 山东大学硕士学位论文 细分方法的优点可总结如下：能够处理任意拓扑的控制网格：在进行局部特征 调控的同时，能够保证曲面整体的光滑性；是联系连续模型和离散表示的桥梁；算 法实现简单。以下从几个方面给出细分方法常用的几个术语： 点的度是指网格中以该点为端点的网格边的个数或以该点为一个顶点的网格 面的个数。这些共点网格边和网格面分别称为点的邻接边和邻接面。定义在三角形 网格上的细分方法在网格内部生成的点的度是6 ，边界上生成的点的度是4 。类似地， 定义在四边形网格上的细分方法在网格内部生成的点的度是4 ，边界上生成的点的 度是3 。因此，经过数次细化后，对于三角形网格，大多数网格点的度就是6 ( 内部) 或4 ( 边界) ，对于四边形网格则是4 ( 内部) 或3 ( 边界) 。这种点就称为规则点( r e g u l a r v e r t e x ) ，否则称为奇异点( e x t r a o r d i n a r yv e r t e x ) 对于面分裂型( 基本型) 细分方法， 从上一层网格继承的点称为偶数点，新生成的点称为奇数点。对于基于三角形网格 的细分方法( l o o p 方法和改进的b u t t e r f l y 方法) ，只有一种类型的奇数点。对于四 边形网格，细分时，相对于上一层网格的边和面都有新点插入，这两种奇数点分别 称为边点和面点。 边界与折痕：一般对于网格的边界需要指定特殊的细分规则，这些规则使得极 限曲面的边界曲线不依赖于内部的控制点，且曲线是光滑的或分段光滑的( r 或 c 2 连续) 。同样的规则可用于在曲面上引入尖锐特征：将些内部边标记为折边 ( c r e a s ee d g e ) ，然后对这些边应用边界的细分规则。 模板( m a s k ) ：我们经常通过模板来说明一种细分规则模板就是显示 用于生成新点的控制点的图。 细分规则通常由两部分组成。一是拓扑分裂规贝j j ( t o p o l o g i c a ls p l i t r u l e ) ，用于描述网格细分一次后的所有顶点之问的连接关系；另一个是几何规则 ( g e o m e t r i cr u l e ) ，用于计算细分后产生的新点的几何位置信息 根据几何规则与细分层次的关系分类。若几何规则在细分过程中保持不变，则 称为静态细分方法( s t a t i o n a r ys u b d i v i s i o n ) ：反之，称为动态细分方法( d y n a m i c s u b d i v i s i o n ) 。 根掘网格类型分类。已有的细分方法多是由应用于规则网格上的传统样条方法 推广而来，如b 样条和箱样条。b 样条用于由四边形组成的网格，箱样条用于由 三角形组成的网格。因此细分方法还可根掘其拓扑规则分为基于四边形网格和三 山东大学硕士学位论文 角形网格的细分。还有一种网格是由六边形组成的，但并不常在实际中应用。 根掘拓扑分裂类型分类。生成细化后网格的拓扑分裂主要有两种方式，一个是 面分裂( f a c es p l i t ) ，另一个就是点分裂( v e r t e xs p l i t ) 。使用第一种方式的细分方法称 为基本型( p r i m a l ) ，使用第二种的称为对偶型( d u a l ) 。对于第一种类型，在细分过程 中，组成网格的每一个面被分裂为四个，旧点拓扑位置保持不变，自每条网格边上 插入一个新点，对四边形网格，每一个网格面中也要插入一个新点。对于第二种类 型，对应于每一个旧点，有多个新点产生，每个点对应一个与这个旧点相邻的网格 面；对应于每一条网格边，生成一个新面；旧的网格面保持不变( 图1 3 ) 。 根掘细分极限曲面与初始控制网格的位置关系分类已有的细分方法可分为逼近型 细分方法( a p p r o x i m a t i n gs u b d i v i s i o n ) 和插值型细分方法( i n t e r p o l a t o r ys u b d i v i s i o n ) 。面 分裂类型可以是插值的，也可以是逼近的。对于初始网格中的任一个控制顶点，在 不同的细分层次上均有一个控制点与其对应。如果这些点均相同，则这种细分方法 称为插值型的，否则称为逼近型的。对于插值型细分方法，定义曲面的初始控制点 也是极限曲面上的点，这使得我们可以更加直观的控制曲面。但是这类曲面的光顺 度不如逼近型细分的极限曲面，收敛速度也比逼近型细分方法慢。 i j i 点q ! 艇鳓舱瓤铮旋翅姐形蜘l 的点待袋 蒸一黼 t 怒拜j h ；勺i f i j 分袋 幽1 3 不同的细分规则 1 4 各种参数化方法介绍 根捌已知采样点集的性质可以将曲线重建的方法分为有序离散点集的曲线重 山东大学硕士学位论文 建和无序散乱点集的曲线重建。本文中主要研究的就是前者。 有序离散点的曲线重建是指给出依次采样于某条已知曲线上的一系列采样 点，如何构造出一条曲线依次通过或近似通过这些采样点，作为原曲线的逼近 基于有序点的曲线拟合，最早可以追溯到曲线的二乘拟合。在逆向工程中，对有 序点进行曲线拟合，要求得到的重建曲线能够反映出原始点集的形状与特征，于 是越来越多的研究者针对有序数掘点的保形曲线拟合做出了许多有益的研究。 1 9 8 1 年，m c a l l i s t e r 给出了用二次样条曲线进行插值重建的算法 1 5 ，f r i t s c h 和c l a r s o n ，b u t l a n d 等人讨论了用如何分