（机械电子工程专业论文）基于散乱点的三维重构研究.pdf

中国科学技术大学硬士学位论文 摘要 随着工业设计的发展，逆向工程已经成为现代产品设计的一个重要方法，它 也逐渐成为c a d 中一个比较独立的研究领域。逆向工程主要包含两个研究领域： 一是数据获取，研究如何通过各种方法获取物体表面点的精确数据；二是三维重 构，研究如何通过这些点重构出物体。随着传感器等一些硬件的发展，数据获取 已经不再是个制约逆向工程发展的关键因素，如何通过计算机程序重构出物体的 c a d 模型就是亟待解决的问题。 三维重构又包含两个步骤，一是将离散点云转换成有序点云，即：如何得到 点云中每个点的邻接拓扑关系；二是如何用c a g d 的方法对这些点云进行自由 曲线曲面拟合，本文研究的研究重点就是如何得到点云中每个点的邻接拓扑关 系。 对于一些简单实体，本文利用p a r a s o l i d 造型系统进行重构。首先基于关键点 求出该实体的造型参数，然后输入p a r a s o l i d 造型函数，即可得出重构结果。对 于大规模离散点云数据，本文主要利用计算几何中一些算法和数据结构进行重 构，如：d e l a u n a y 三角剖分、a l p h a 图等。v o r o n o i 图是计算几何中最为常用的 数据结构，更是其他数据结构和算法的基础，在很多领域都有着极其重要的作用， 本文介绍了作者自己独立完成的v o r o n o i 图数据结构的设计和构造算法的实现， 这也为将来进一步研究打下了良好的基础。此外本文最后介绍了b e z i e r 曲线、曲 面生成算法的实现，三角b e z i e r 曲面及b 样条曲线、曲面生成算法的实现。 关键词：逆向工程三维重构点云d e l a u n a y 三角剖分a l p h a 图 中国科学技术大学硕士学位论文 a b s t r a c t a l o n g w i t ht h ed e v e l o p m e n to f i n d u s t r yd e s i g n , r e v e r s ee n g i n e e r i n gh a sb e c o m e o n eo ft h em o s ti m p o r t a n tw a y st od e s i g np r o d u c t i ti se v o l v i n gi n t oa ni n d e p e n d e n t r e s e a r c hd o m a i n r e v e r s ee n g i n e e r i n gc o m p r i s e st w oa s p e c t s ：f i r s to n ei st h ed a t a g a t h e r i n g , r e s e a r c h i n gh o wt og a t h e r i n gt h em o d e l s3 dd a t a ；t h es e c o n do n ei s r e c o n s t r u c t i o n ：h o wt or e c o n s t r u c tt h eo r i g i n a l a st h ed e v e l o p m e n to ft h e5 e 加t s o r , d a t ag a t h e r i n gi sn o tt h eb l o c kf o rr e v e r s ee n g i n e e r i n ga n ym o r e s os o l v i n gt h e p r o b l e mo f 3 dr e c o n s t r u c t i o ni st h en u m b e ro n e t h e r ea r et w os t e p st or e c o n s t r u c t3 dm o d e l s ，t h ef i r s ts t e pi st oc o n v e r tt h e o u t - o f - o r d e rp o i n t sc 1 0 u dt op o i n t sc l o u di no r d e r , w h i c hm e a n st og e tt h e n e i g h b o u r h o o do fe a c hp o i n t , t h es e c o n ds t e pi st h ef r e e f o r mc u r v e & s u r f a c ef i t t i n g t h ek e y p o i n t si nt h i sp a p e r a r ea b o u tt h ef i r s ts t e p ：g e t t i n gt h en e i g h b o u r h o o do f e a c h p o i n t b a s e do np a r a s o l i d ，s i m p l ee n t i t i e sa r ec o n s t r u c t e df r o mt h e i rk e yp o i n t s ，f i r s tw e c a r tc a l c u l a t et h ee n t i t i e s m o d e l i n gd a t af r o mt h ek e yp o i n t s ，a n dt h e nc a l lt h e m o d e l i n gf u n c t i o n sw i t ht h em o d e l i n gd a t aa st h ei n p u tp a r a m e t e r s ，t h er e s u l tw i l lb e g i v e no u tb yp a r a s o l i d d i s c r e t ep o i n t sc l o u di sc o n s l r u c t e db yd a t as t r u c t u r ea n da l g o r i t h mo f c o m p u t a t i o n a lg e o m e t r y , s u c ha s ：d e l a u n a yt r i a n g u l a t i o n sa n da l p h as h a p e v o r o n o i d i a g r a mi st h em o s ti m p o r t a n tc o n c e p ti n3 dr e c o n s t r u c t i o na n dc o m p u m t i o n a l g e o m e t r y , s oi tt a k e so n ec h a p t e rt on a r r a t et h ed e s i g no fd a t ab ；缸 u c t u r eo fv o r o n o i d i a g r a ma n d i t sc o n s t r u c t i n ga l g o r i t h m b e s i d e s ，t h el a s tc h a p t e rt e l l ss o m ea l g o r i t h m o f b i z i e rc u r v ea n ds u r f a c e ，b - s p l i n ec u r v ea n ds u r f a c 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 ，3 dr e c o n s t r u c t i o n , p o i n t sc l o u d , d e a l a u n a y t r i a n g u l m i o n ，a l p h as h a p e 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：号云袖并 作者签名：! ! ! ：! 墨： 功9 年, e jj 叩日 中舀科学技束大学硕士学位论文 第一章绪论 三维重构属于逆向工程的范畴，本章首先介绍逆向工程的概念，应用及其现 状，然后介绍三维重构的研究现状，国内在这一领域中所存在空缺的领域，最后 介绍本论文的主要研究工作、章节安排。 1 1 逆向工程现状与发展趋势 1 1 1 什么是逆向工程 “逆向工程”( r e v e r e n g i n e e r i n g ，r e ) ，也称反求工程、反向工程等。逆向 工程起源于精密测量和质量检验，它是设计下游向设计上游反馈信息的问路。 圈1 - 1 逆向工程流程图 传统的产品实现通常是从概念设计到图样，再制造出产品，我们称之为正向 工程( 或顺向工程) ，而产品的逆向工程是根据零件( 或原型) 生成图样，再制造产 品。它是一种以先进产品设备的实物、样件、软件( 包括图样、程序、技术文件 等) 或影像( 图像、照片等) 作为研究对象，应用现代设计方法学、生产工程学、材 料学和有关专业知识进行系统分析和研究、探索掌握其关键技术，进而开发出同 类的，更为先进的产品的技术，是针对消化吸收先进技术采取的一系列分析方法 和应用技术的结合。广义的逆向工程包括形状( 几何) 逆向、工艺逆向、材料逆向 等诸多方蘧。是一个复杂的系统工程。 中国科学技术大学硕士学位论文 1 1 2 逆向工程的应用 ( 1 ) 在对产品外形的美学有特殊要求的领域，设计师往往广泛利用油泥、黏土 或木头等材料进行快速且大量的模型制作，快速建立其三维的数字立体模型，就 必须引入逆向工程的技术。 ( 2 ) 在没有设计图纸或者设计图纸不完整以及没有c a d 模型时，通常采用逆 向工程的方法复制相同的零件。 ( 3 ) 对于国外的商品，要生产同类产品，由于其不适合国内的使用习惯需要修 改时，我们通过逆向工程形成完整的图纸或者模型，再作进一步改进。 ( 4 ) 模具行业。模具制造中经常反复试冲和修改模具型面方可得到最终符合要 求的模具。若将最终符合要求的模具测量并反求出其c a d 模型，这样建立或修 图i - 2 人脸曲面重构 改变更过的设计模型，就可以大大减少修模量，提高模具生产效率，降低模具制 造成本。 ( 5 ) 在新产品开发、创新设计上有相当高的应用价值。 ( 6 ) 艺术品、考古文物的复制。 人体中的器官、骨头和关节等的复制、假肢制造( 图1 2 为人脸的重构) 。 2 中国科学技术大学硕士学位论文 1 1 3 逆向工程中的关键技术 ( 1 ) 数据获取 数据采集是逆向工程的首要环节，是反求建模的理论依据。因此，准确、快 速、完各地获取产品实体的三维几何数据，即对产品实体的三维几何形面进行三 维离散数字化处理，是逆向工程的一项关键技术。 c m m 是数据采集中首要的测量手段。使用中必须注意以下三点：一、首先 要对被测件的结构、特性、工作原理有一定的了解，确定其关键尺寸；二、根据 待测对象的形状特点选择测头。对于表面比较规则且不太复杂的工件，采用接触 式测头能方便地完成数据的采集；对于具有复杂自由表面的工件则采用扫描式测 头或非接触式测头。扫描式测头一般运用三向电感式原理，可连续采样而获得大 量数据，尤其适合于曲线和曲面；齿形和齿向误差的测量、对于小型复杂工件、 塑性或脆性表面、薄壁件等，可采用非接触式测头。三、测量要进行合理的测量 规划。为使实物全体表面数字化，必须尽量保证测量数据的必要性和充分性，用 最少的数据点重建出满足精度要求的数据模型。但实践中往往很难做到使测量数 据严格满足必要性和充分性，只能通过适当的规划，选取合理的测点和方位，尽 可能地减少测量工作。数据采集规划的一般原则是：1 顺着特征方向走；沿着 法线方向采。2 重要部位精确多采，次要部位适当取点。3 复杂部位密集取点， 简单部位稀疏取点。4 先采外廓数据，后采内部数据。 ( 2 ) 数据预处理 测量数据测头半径补偿：微平面法、三点共圆法、拟和补偿法、直接计算 法、三角网格法。 数据平滑 数据平滑通常采用高斯( g a u s s i a n ) 、平均( a v e r a g i n g ) 或中值( m e d i a n ) 滤波算 法，高斯滤波器在指定城内的权重为高斯分布，其平均效果较小，故在滤波的同 时能较好地保持原数据的形貌。平均滤波器是指采样点的值取滤波窗u 内各数据 点的统计平均值。而中值滤波器采样点的值取滤波窗门内各数据点的统计中值， 这种滤波器消除数据毛刺的效果较好。实际使用时，可根据“点云”质量和后序 建模要求灵活选择滤波算法。在过滤操作中，通常选择操作距离( o p e r a t i n g d i s t a n c e ) 为过滤的尺度，操作距离是指顺序点之间的最大间距。而高斯过滤被用 3 中国科学技术大学硕士学位论文 来修正操作距离，应用高斯过滤时，那些远大于操作距离的点被处理成固定的端 点，这有助于识别间隙和端点。 数据精简 对于高密度“点云”。由于存在大量的冗余数据，有时需要按一定要求减少 测量点的数量。不同类型的“点云”可采用不同的精简方式，散乱“点云”可通 过随机采样的方法来精简；对于扫描线“点云”和多边形“点云”可采用等间距 缩减、倍率缩减、等量缩减、弦偏差等方法；网格化“点云”可采用答分布密度 池和最小包匿区域法进行数据缩减。数据精简操作只是简单地对原始“点云”中 的点进行删减，不产生新点。 特征提取 特征抽取也是滤波的一种，方法是根据给定的曲率变化梯度域值，推断和寻 找点云的边界、棱边、坑、孔等突变特征，以方便后续建模时的区域划分。 多组数据对齐 在逆向工程实际过程中，对实物样件实行数字化时，往往不能在同一坐标系 下将产品的几何数据一次测出。其原因一是产品尺寸超出测量机的行程，二是在 部分区域测量探头受被测实物几何形状的干涉阻碍以及不能触及，因此在几何模 型构建时必须将这些不同坐标系下的数据变换或统一到个坐标系中。 ( 3 ) 曲面重构 点云网格化 逆向工程中，获取的数据点多为离散的、无规律的海量数据，经过前面的数 据预处理之后，就需要进一步得出每个点之间的邻接关系，对于较为简单的自由 曲面实体，多数采用d e l a u n a y 三角剖分对这些点进行网格化，而对于各个方向 外形都非常复杂的实体则采用其他形式多样的网格剖分方法。 点云的自由曲线曲面拟和 曲线是构建自由凸面的基础，在逆向工程中，一种常用的模型重建方法是， 先将数据点通过插值( i n t e r p o l a t i o n ) 或逼( a p p r o x i m a t i o n ) 拟合成样条曲线( 或参 数曲线) ，再利用造型工具，如s w e e p 、b l e n d 、l o f t i n g 、四边曲面( b o u n d a r y ) 等， 完成曲面片造型，再通过延伸、剪裁和过渡等物面编辑，得到完整的曲而模型。 4 中屠科学技术大学硕士学位论文 1 2 三维重构技术 三维重构就是给出物体原始的数据点，通过计算机程序，在满足一定的精度 要求下，重构出原始物体，并且重构的结果满足一定的要求，如：输入c a d ，a m 系统中做下一步处理。 三维重构分为两大块领域： ( 1 ) 有序点云重构，这一类重构主要是对于有序点云的重构，这类点云按行、 列或者云层有序，重构时不用考虑点的邻接关系，当前的重点在于如何用c a g d 的方法对这些点进行高质量的曲线曲面拟合，目前国内研究机构很多，而且也取 得了很好的结果。 ( 2 ) 无序点云重构，这类重构主要针对杂乱无序点云的重构，输入的点云数 据是杂乱的，毫无规律的，重构时首先就要把这些无序点重构成有序的结果，其 余的步骤就是类似于有序点云的重构方法，这类重构的重点与有序点云的重构不 一样，这类重构研究的是如何把无序点变成有序点，主要利用计算几何中一些算 法实现，如：d e l a u n a y 三角剖分、a l p h a 图等等。目前国内对这类问题的专门研 究机构不多，尤其是对些比较新的概念研究更少。如：a p o l l o 图，目前在这一块 国内开展的研究较国外研究要迟缓很多，尤其是国外一些研究机构已经做出了一 些功能强大、而且比较成熟( 有些已经投入商业软件的使用中 开原程序库，如： c g a l 等，而国内还没有形成一个有一定人数、知识积累的研究团队。 图1 3 是本文对整个重构流程的整体思路，不仅适用于无序点云的重构，同 样适用于有序点云重构，图1 3 中提出了三次重构的概念，一次重构就是将无序 点云变有序的过程，是上面所提到的( 2 ) 类重构的研究重点。二次重构、三次重 构就是自由曲线曲面的拟和，是( 1 ) 类重构的研究重点。 首先由测量仪器获取模型点云数据，由于客观存在的原因要对这些点云进行 预处理，主要是修整输入点数据，以利于后续步骤的操作。由于要重构的模型局 部特征较为复杂，或者数据获取要通过多次在不同坐标系下测量，所以要首先对 这些数据进行分块处理，将同一模型的数据按照特征或者数据点获取区域分为多 块，然后处理。由于处理的是离散的无规则的空间三维点云，所以首先要在步骤 4 中找到点的邻接关系，对于某些应用领域，到这一步就可以达到目的，如：大 区域地形地貌的粗略复现等，因为这些领域没有必要做特别精细的迸一步拟合。 中国科学技术大学硕士学位论文 而对于要求严格的工程制造领域，这一步还远远不够的，因为工程制造领域要求 的是可以用于输入c a m 系统的模型。步骤5 的主要任务就是用c a g d 现有的理 论和算法进行曲面拟和。步骤6 中将5 中重构曲面的边界用一定的条件( 一次光 顺、二次光顺) 进行拼接。步骤7 输出结果。 1 、模型获取数据 j 2 、点云数据预处理 i 3 、局部小区域划分 i 4 、点云的三角面片重构( 一次重构) j 5 、小区域自由曲线曲面拟合( 二次重构) i 6 、整个模型的区域光顺拼接( 三次重构) i 7 、重构结果输出 田i - 3 三维重构流程图 1 3 本文研究内容 本文主要研究如何由物体上采集到的点数据重构出原始物体，主要有四部分 内容： ( 1 ) 简单模型的重构：如直线、样条曲线、圆锥、圆柱，用p a r a s o l i d 造型系 统来完成，重构过程只需输入模型上若干个关键点，即可构造出相应的实体，其 中主要部分就是利用关键点求取p a r a s o l i d 的造型参数。 ( 2 ) 无序点云数据的三角网格重构：本文又将这类重构分成两种情况：面模 型重构和体模型重构，对于面模型，利用d e l a u n a y 三角剖分的数据结构和算法 6 中国科学技术大学硕士学位论文 来实现面模型的网格重构，主要方法是将空间点云投影到一个平面上( 也就是取 其转化后的二维坐标) ，在该平面内进行d d a u n a y 三角割分。对于体模型，利用 三维a l p h a 图实现其重构，a l p h a 图可以识别出物体内部的空洞和物体表面的凹 坑，所以在三维复杂模型重构中有着很重要的作用。 ( 3 ) v o r o n o i 图数据结构的设计和重构算法的实现：v o r o n o i 图是计算几何中最 关键最核心的数据结构，也是其他数据结构的基础，在三维重构中有着极其重要 的作用。该算法首先基于v o r o n o i 图的组成结构分析，抽象出若干组件，如：s i t e ， p o i n t , e d g e ，c e l l 等，分别设计成一个类，在实现其相应函数的同时不断修改该类 的定义，从而使v o r o n o i 图的整个构造过程更加简练。主要采用s t l 的一些容器 作为基础数据结构，在此基础上封装成更加复杂的类，诸如：v o r o n o i c c h2 d 、 v o r o n o i d i a g r a m 等，除此之外还设计了许多辅助性的数据结构。在重构算法中采 用了许多新颖的算法，如：循环查找待处理单元、插入剔除算法等。 ( 4 ) 研究了自由曲线曲面的理论、相关的算法，用c + + 语言实现了这些算法， 如：b e z i e r 曲线曲面、b 样条曲线曲面、三角b e z i e r 曲面等曲面上点的生成算法。 具体章节安排如下： 第一章：主要介绍逆向工程的概况及其关键技术和本论文内容章节安排； 第二章：简要介绍p a r a s o l i d 内核以及在此基础上的简单模型重构； 第三章 第四章 第五章 第六章 介绍c g a l 库，及基于该库的面模型和体模型的三角面片重构 v o r o n o i 图的数据的设计及构造算的实现； 自由曲线曲面的研究及相关算法的实现； 总结。 7 年馐科学技术丈擎硕士学位论文 第二章基于p a r a s o l i d 内核的简单实体模 型重构 p a r a s o l i d 是当前世界上两个最著名的实体造型系统之一( 另外一个a c i s ) 。 本章首先总体介绍p a r a s o l i d ，然后介绍如何利用p a r a s o l i d 重构一些简单的模型。 2 1p a r a s o l i d 内核 p a r a s o l i d 是用c 语言开发的，其前身是r o m u | u s 。为了在实体造型系统中支 持精确的曲面表示，1 9 8 5 年，s h a p ed a t a 公司开始了p a r a s o l i d 的开发。 2 1 1p a r a s o l i d 的主要功能 p a r a s o l i d 有较强的造型功能，但是，只能支持正则实体造型。主要功能包括： 1 p a r a s o l i d 采用自由曲面和解析曲面的混合表示，共提供了l o 种标准的曲 面类型和7 种标准的曲线类型，并且是完全集成的，应用程序操作模型时，无须 关心它们的几何结构。l o 种曲面类型分别是：平面、圆柱、圆锥、圆环、球、 精确过渡面、扫描面、旋转面和n u r b s 面。7 种曲线类型分别是：直线、圆、 椭圆、遗面与盘面的交线、n u r b s 艘线、凿面的裁剪线和等参数线。 2 p a r a s o l i d 可用简单的方法生成复杂的实体，实体之间可有多种方式的操作。 p a r a s o l i d 实体创建方法包括：块创建、圆柱创建、球创建、圆环创建、棱柱创建、 扫描轮薅剑建、旋转轮廓创建、缝合裁剪曲面趔建及b 娜模型剑建。 3 对于早期的实体造型系统，需要用户理解与造型技术密切相关的全局和局 部操作的概念- 当前，用户可用自己理解的工程特征进行设计，即实体模型根据 工程特征建立。p a r a s o | i d 提供了特征酌御建和编辑功能。特征可以是一组拓於面、 边、顶点，或几何曲面、曲线、点，或它们的组合。 4 为了能够将实体模型转化为产品定义模型，p a r a s o l i d 能够了提供非拓扑和 非几何数据，称为属性( a t t r i b u t e s ) ，如加工容差、表面粗糙度、表面反射率、 实体透明度和实体密度等。属性包括系统定义的属性和用户定义的属性两种，且 依附于模型实体( e n t i t i e s ) 。 5 p a r a s o l i d 支持局部操作，由于完全集成了几何实体( e n t i c e s ) ，所以对任何 中国科学拄术大学硕士学位论文 模型进行局部操作时，无须关心模型的几何结构。p a r a s o l i d 的局部操作包括：改 变面几何、变换面几何、使面成锥形、摆动面、扫描面及删除面。提供了多半径、 变半径的过渡功能。 2 1 2p a r a s o l i d 的模型结构 p a r a s o l i d 创建的模型实体( e n t r i e s ) 包括三种：拓扑、几何和相关数据，它们 之间的关系如图2 - 1 所示。 1 拓扑实体( e n t i t i e s ) 拓扑实体( e n t i t i e s ) 包括构造模型结构的所有实体，共有l o 种，它们分别是： ( 1 ) 体( b o d y ) ：p a r a s o l i d 模型通常包括一个或多个体( b o d i e s ) ，体包括顶点 ( v e r t i c e s ) 、边( e d g e s ) 、翼( f i n s ) 、环( l o o p s ) 、i 面( f a c e s ) 、壳( s h e l l s ) 。 ( 2 ) 壳( s h e l l ) ：壳是实体( s o l i d ) 和空气之间封闭的边界，每一个壳是面( f a c e s ) 、 边( e d g e s ) 和顶点( v e r t i c e s ) 的集合。 。 几何拓扑 相* 数据 图2 - 1p a r a s o l i d 模型结构 ( 3 ) i 面( r a c e ) 、边( e d g e ) 和顶点( v b t e x ) ：i 面( f a c e s ) 、边d g e s ) 和顶点( 吼i c e s ) 9 中国科学技术大学硕士学位论文 通常有几何实体，分别对应曲面( s u r f a c e s ) 、曲线( c u r v e s ) 和点& o h m ) 。 ( 4 ) 翼( f i n ) ：翼( f i n s ) 表示一条边的一侧，可能依附有一条曲线，每一条边 有一个左翼和一个右翼。 ( 5 ) 环( l o o p ) ：环属- 于n ( f a c e s ) ，环是由一个面上封闭的翼组成的。 ( 6 ) 装配件( a s s e m b l y ) 和实例( i n s t a n c e ) ：一个装配件是一个对其它装配件或 体的指针的集合。每一个指针( 被称为一个实例) 有一个变换与之相关，以控制被 引用的零件相对于装配件中的其它零件的位置和方向。 ( 7 ) 世界( w o r l d ) ：世界是一个独特的实体( e n t i t y ) ，它包含模型中的所有的 体( b o d i e s ) 和装配件( a s s e m b l i e s ) 。 2 几何实体( e n t i t i e s ) 几何实体( e n t i t i e s ) 有四种：变换( t r a n s f o r m a t i o n ) 、点( p o i n t ) 、曲线( c u r v e ) 和曲 面( s u r f a c e ) 。 ( 1 ) 点( p o i n t ) ：点( p o i n t s ) 主要依附于n n ( v e r t i c e s ) ，它们也依附于体( b o m e s ) 和装配件( a s s e m b l i e s ) 作为构造点( c o n s t r u c t i o np o i n t s ) 。 ( 2 ) 曲线( c u r v e ) ：曲线( c u r v e s ) 主要依附于面( f a c e s ) ，但也依附于体( b o d i e s ) 和装配件( a s s e m b l i e s ) 作为构造几何元素( c o n s t r u c t i o ng e o m e t r y ) 。 ( 3 ) 曲面( s u r f a c e ) ：曲面( s u r f a c e s ) 主要依附于模型的边( e d g e s ) 或翼( e i n s ) ，但 也依附于体( b o d i e s ) 和装配件( a s s e m b l i e s ) 作为构造几何元素( c o n s t r u c t i o n g e o m e t r y ) 。 ( 4 ) 变换( t r a n s f o r m ) ：变换( t r a n s f o r m s ) 表示几何操作：平移、修剪等，主要 依附于实例。 3 相关的数据实体( e n t i t i e s ) 相关的数据实体( e n t i t i e s ) 允许附加的数据能被操作或依附于模型，共有三种： ( 1 ) 特征( f e a t u r e ) ：特征( f e a t u r e s ) 是实体( e n t i t i e s ) 的集合，依附于体( b o d i e s ) 和装配件( a s s e m b l i e s ) 。 ( 2 ) 表( l i s t ) ：表( l i s t s ) 提供了结构化数据的方法，它们一般独立使用，也可 依附于体( b o d i e s ) 和装配件( a s s e m b l i e s ) 。表有三种：整数表( i n t e g e r ) 、实数表( r e a l ) 和标志表( t a g ) 。 ( 3 ) 属性( a t t r i b u t e ) ：属性( a t t r i b u t e s ) 是用于附着信息到实体( e n t i t i e s ) 的数据 l o 中国科学技术大学硕士学位论文 结构。 2 1 3p a r a s o l i d 的界面 如图2 - 2 所示，p a x a s o l i d 有两个界面，一个在造型器项部，称为核心界面( k i ) 。 通过，用户可以造型、操作对象和控制造型器。另一个在造型器下部，它包 括三个部分：f r u s t r u m 、g o ( g r a p h i c so u t p u t ) 和f o f f o r e i g ng e o m e t r y ) 函数集( f r u s 觚) ：f r u s t r u m 是用户写的函数集，当数据被存储、提取，或进 行内存分配时，它们被核心调用。 图形输出( g o ) ：图形输出( g o ) 函数也是被用户写的。不过与f r u s t n a n 不同， 从这些函数输出的通常不是数据文件，而是要求核- 5 , ( k e r n e l ) 绘图的指令。 外部几何( f g ) ：p a r a s o l i d 称外部定义的曲线、曲面为外部几何口g ) 。f g 功能 允许p a r a s o l i d 通过f g 模块界面访问用户定义的曲线、曲面，使得用户可以使用 p a r a s o l i d 造型出的曲线、曲面及标准的p a r a s o l i d 曲线、曲面类型( 参见p a r a s o l i d 功能介绍l 图2 - 2p a r a s o l i d 界面 2 2 简单模型重构 2 2 1 直线重构 输入：起始点、终止点 输出：直线( 线段、射线、直线) 中国科学技术大学硕士学位论文 调用函数：p k _ l i n e _ c r e a t e ( c o n s tp k _ l i n e _ s f _ t * l i n e _ s f , p k _ l i n e _ t * c o n s t l i n e ) 其中p k _ l i n es f _ t 是一个结构体，包含一个位置( 1 0 c a t i o n ) 和一个方向， 具体定义如下： s t r u c tp k a x i s 1 s f p k _ v e c t o r tl o c a d o n ac a r t e s i a np o i n t p k _ v e c t o r l ja x i s ad i r e e t i o m ； s t r u e tp k _ a x i s 1 s f s p k _ v e c t o rtl o c a t i o n ；ac a r t e s i a np o i n t p kv e c t o r l ja x i s ；ad i r e c t i o n ) ； t y p e d e f s t r u e tp ka x i s ls fsp k _ a x i s l _ s f _ t ； s t r u e tp k _ l i n es fs p k _ a x i s l s f tb a s i s _ s e t ；ac a r t e s i a np o i n ta n dad i r e c t i o n ， ) ； t y p e d e f s t r u c tp k _ l i n e _ s f _ sp kl i n e _ s f _ t ； 这就是一条通过指定点和方向的直线的标准形式的参数，直线参数方程如下： p = b a s i s _ s e t 1 0 c a t i o n v = b a s i s _ _ s e t d i r e c t i o n p ( t ) = p + t + v 1 2 中国科学技术大学硕士学位论文 2 2 2 圆弧重构 图2 3 基于两点的直线重构 输入：圆上3 点 输出：圆，圆心，半径 函数： b o o lg e t c e n t e r p o i n t ( d o u b l ep 【3 】 3 】，d o u b l ee e n t l ，d o u b l ez v e c t o r 口) p k _ c i r c l e _ e r e a t e ( c o n s tp k _ c i r c l 即u ，p kc i r c l e _ t + c o a s t ) 其中函数g e t c e n t e r p o i n t 作用是由圆上三点：求出其圆心坐标和半径 p kc i r c l ec r e a t e 用于创建圆。 由空间三个点坐标求取其圆心、半径的方法如下： 么( ，m ，毛) ，b ( x 2 ，y 2 , 9 2 ) ，c ( x ，, y 3 , z 3 ) ，圆心为p ( x ，y ，z ) 删2 圃 【i 葡l = 冽 b ( 2 - 1 ) 【o ( x 一- 妇x 0 ) ：2 + + ( y 一- 乃y , ) ) ：+ + ( 。z - 一z z t 3 ) ) 2 2 = ：( o x - 一x 而。2 ) ) 2 2 + + ( ( y y - 一y 咒2 ) ) 2 2 + + ( 乜z - 一z 乞2 ) ) 2 2 ( 2 - 2 )【o 一妇) 2 + 一乃) 2 + 0 一z 3 ) 2 = o 一而) 2 + ( y 一咒) 2 + 乜一乞) 2 卅 化简： 卿砂y ( m 训叫弭) = 盟监幺蛐 x 如一毛) + ) ，( 乃一n ) + z 瓴一毛) = ( x 2 2 + y + z 2 2 ) - _ ( x + y 3 2 一+ z ) 中田科学技木大学硕士学位论文 平面法向量： j 4 b = ( 而一毛，m 一乃，：i 一毛) 【b c = ( x 2 一而，儿一朋，z , 2 7 , 1 ) = k 三三羔三兰兰三三 令。 口：j m 一乃毛一毛l6 ：一卜一屯毛一毛lc ：i 毛一而m 一乃 i 儿一乃乃一毛ii x 2 一五乃一毛ii x 2 一儿一m 所以2 口i + b j + c k 且点p 位于a b c 三点确定的平面上得出p a n = o 即： o 一而) d + 一m ) 6 + 0 一z 1 ) c = 0 化简得：口x + 6 j ，+ f z = 而4 + y l 扫+ z 1 c ( 2 - 5 ) ( 2 7 ) x ( 而一而) + y ( m 一耽) + z ( 毛一乞) = 兰j ! 芝i 垒：笔兰幽 x ( x 3 - - ) + 灭乃一) + z ( 毛一乞) = 垒垒：2 1 ：兰上；苎幽( 2 - s ) 口x + b y + c z = 而口+ m 6 + 毛c 令 月4；(x22+y22+z22)_(x2 + y 2 + z z 2 ) 2 以：(x22+y22l-z22)-(x32-i-732-i-h2) 2 。= p ：i 羔；羔三j 乏 而一而 d 2 = i 而- x 2 聊五一乃 拧 毛一乞 口zc 解出圆心坐标： d l = my l y 2 z l z 2 栉y 3 一y 2 毛一2 2 1 4 儿n 一 一6 m 儿 6 h 而 一 一 口 ， 而黾 = b 中国科学技术大学硕士学位论文 重构结果如图2 - 5 所示。 x ：旦 d y = 告 ：堡 d ( 2 9 ) 田2 - 5 基于三点的圆( 弧) 重构 2 2 3 圆锥重构 输入：4 点( 三点位于底面圆上，另外一点在圆锥侧面上) 输出：圆锥轴线，底面圆心，锥高 函数： g e t c o n e d a t a ( d o u b l ep t 4 1 1 3 1 ，c o n e d a t a + c o n e v a l u e ) p k _ b o d y _ e r e a t e _ s o l i d _ c o n e ( d o u b l e ，d o u b l e ，d o u b l e ，p k _ a x i s 2s ft * ， p k _ b o d y _ t + ) 函数g c t c o n e d a t a 用于求取圆锥关键参数：底面圆和锥高，其中底面圆的圆 心半径可用上节函数求出。 由上节讨论可知： 底面圆所在平面f 方程为： 口。x + b 。y + c z = 而口+ m - 6 + 毛c 点p ( x ，y ，z ) 为锥面上的关键点，则它到f 距离为： p b = 又： 国：垦 i 船li 彳尸1 l ( 2 l o 中图科学技术大学硕士学位论文 其中网= 网一网，网= 厩相茸 所以： c太 图2 - 6 圆锥信息 网= 蹁l 丽i 图2 7 圆锥重构结果 a 2 2 4 其他几何体重构 这里就不做详细介绍，仅给出重构结果及主要步骤。 ( 1 ) 圆柱重构 输入：底面圆边界上的三点，另外一个底面上一点 通过底面圆上三点通过2 3 2 节公式求得圆心半径，圆柱高度通过点到面的距 离可以求得。 ( 2 ) b 样条曲线重构 为直观起见，这里首先给出主干程序源代码： c r e a t e s p l i n e ( d o u b l ep t 1 1 3 1 ，h a tp t n u m ) p k _ b c u r v e _ s p l i n e w i s e _ s f _ to p t ； i f 【! f i l l s p l i n e o p t i o n s ( p t , p t n u m ，& o p t ) ) 1 6 中国科学技术大学硕士学位论文 r c t l l r t lf a l s e ； p k _ b c u r v etb c u r v e ； p k _ e r r o r _ c o d e _ t e r r2p kb c u r v e _ c r e a t es p l i n e w i s e ( & o p t , & b c u r v e ) ； i f ( e r r ! = p k _ e r r o rn oe r r o r s ) f o a l l 1 1f a l s e ； p ki n t e r v a l _ tr a n g e ； e r r = p kc u r v ea s ki n t e r v a l ( b c u r v e ，& r a n g e ) ； i f ( p ke r r o rn oe r r o r s ! = 口订 r e t u r ne r r ； p kb o d yt b o d y ； i f ( p ke r r o rn oe r r o r s p k _ c u r v e _ m a k ew i r eb o d y ( b c u r v e ，r a n g e ， & b o d y ) ) r e t u r nt r u e ； r e t u r nf a l s e ； 。 ) 其中函数f i l l s p l i n e o p t i o n s 是用来填充p kb c u r v e _ s p l i n e w i s e s ft 类型的参 数的，这个参数用来表明如何构造样条曲线。本程序通过向构造函数提供初始和 结束点出导矢和中间点来构造b 样条。 ( 3 ) 构造b 曲面 同上，先给出主干程序源代码： c r e a t e b s u r f ( d o u b l ep t 口 3 】，i n tu _ v a l u e ，i mv _ v a l u e ，h a tp t n u m ) p k _ b s u r f _ s p l i n e w i s e _ s f _ ts u r f d a t a ； p k _ b s u r ft b s u r f ； p ks u r f _ t s u r f ； p k _ u v b o x _ tu v _ b o u n d ； p k _ b o d y _ tb o d yt ； c r e a t e b s u r f f r a m e ( p t , uv a l u e ，vv a l u e ，p t n u m ) ； f i l l b s u r f o p t i o n s ( p t , 酗j a l