（机械电子工程专业论文）快速成型直接切片技术研究.pdf

硕士论文快速成型直接切片技术研究 摘要 铷 5 3 2 0 5 3 自从快速成型系统出现以来，一直沿用s t l 文件进行切片数据处理。但是s t l 文件错误较多。精度较低，数据量也较大。目前快速成型设备的性能已经有了长足的 进步，曲面加工，微小件的加工要求越来越高。于是研究者们尝试对s t l 文件数据 进行后处理，或提出基于c a d 系统二次开发的直接切片。而本文采取了一种不同的 方式，彻底摒弃了s t l 文件，也不采用c a d 平台二次开发，而是直接实现基于n u r b s 曲面的直接切片求交算法。尝试以这种方式，克服s t l 文件的缺陷。同时，与基于 c a d 系统二次开发的直接切片相比，不依赖c a d 平台，不涉及版权问题，所以更利 于直接切片技术的商品化。 研究了适用于快速成型的曲面，平面求交追踪算法的实现：对追踪算法中所存在 的初始追踪点搜索，追踪方向迷失，步长的确定。边界的赶理等蠲题进行了深入探索， 提出了相应的解决办法。并设计了b 样条曲线曲面求值的快速算法，曲面求极值点 的单纯形算法，醢线，平面求交算法，曲面求交的送代算法，直到曲面的投影算法等 一系列辅助直接切片的算法。采用o b j e c t p a s c a l 语言编写了直接切片软件d i r e c t s l i c e ， 完成了对算法的验证和测试。 还研究了数据交换，交线结果的组织等技术，使得数据能够顺利的输入输出。开 发了基于o p e n g l 的图形显示组件，用于三维模型及运算结果的真实感显示。 直接切片研究尝试了一条新的数据处理的思路。不需要s t l 文件和c a d 平台。 这个思路虽然计算复杂，但是可提高精度，可靠挫，及处理速度，并降低数据传输量。 关键词：快速成型直接切片n u r b s 曲面平面求交数据交换标准 堕主堡壅 堡望盛型皇垄塑生堇查堑窒 a b s t r a c t s i n c er p s y s t e mw a si n v e n t e d ，s t l f i l eh a sb e e nw i d e l yu s e da sd a t ae x c h a n g ef i l e b u t s t lf i l eh a sl o t so f d i s a d v a n t a g e s ，s u c ha se r r o r , l i m i t e dp r e c i s i o n ，a n dl a r g ed a t av o l u m e r e c e n t l y ，r pd e v i c e sp e r f o r m a n c eh a sb e e nh i 曲l yi m p r o v e d r e q u i r e m e n t so fs m a c e m a c h i n i n g ，m i c r o w o r k p i e c em a c h i n i n gb e c o m eh i g h e ra n dh i g h e r , s os o m e r e s e a r c h e r s t r y t op r e p r o c e s ss t lf i l e sf o ri m p r o v i n gi t sp r e c i s i o n o t h e r sd e s i g nt h e i rs l i c ep r o c e s s i n g s o f t w a r eo nc a d p l a t f o r m b u tt h i sp a p e rd o e s n tf l o ws u c hi d e a s n e i t h e rs t l f i l e sn o r c a d p l a t f o r m sa r eu s e d a na l g o r i t h mf o rs u r f a c e p l a n ei n t e r s e c t i o nt h a td i r e c t - s l i c e p r o c e s s i n gb a s e d o ni sd e s i g n e da n di m p l e m e n t e di nt h i sp a p e r d i r e c t s l i c ep r o c e s s i n gi n t h i sp a p e rc a l lg e tr i do fs t l f i l e s d i s a d v a n t a g e s a n dw o r kw i t h o u tc a dp l a t f o r m s oi t h a so w n c o p y r i g h t ，a n d i sm o r e c o m p e t i t i v ei nb u s i n e s sa p p l i c a t i o n s u r f a c e p l a n e i n t e r s e c t i o ni st h e k e yt e c h n o l o g yo fd i r e c ts l i c e p r o c e s s i n g t r a c i n g i n t e r s e c t i o nm e t h o df o r d i r e c t - s l i c i n gp r o c e s s i n gi si m p l e m e n t e di n t h i s p a p e r m a n y p r o b l e m so ft r a c i n gi n t e r s e c t i o f lm e t h o dh a v eb e e nr e s e a r c h e d ，s u c ha so r i g i n a lt r a c i n g p o i n t ss e a r c h i n g ，l o s tt r a c i n go r i e n t a t i o n ，t r a c i n gs t e pc a l c u l a t i n g ，b o u n d a r y sp r o c e s s i n g r e l a t e ds o l u t i o n so ft h o s ep r o b l e m sa r ep u tf o r w a r d f u r t h e r m o r e ，as e r i a lo fa s s i s t a n t a l g o r i t h m sa r ed e v e l o p e df o rd i r e c t - s l i c i n gt o o t e s t i n ga n dv a l i d a t i n go fa l g o r i t h m sa r e c o m p l e t e d ，v i aat e s ts o f t w a r ed i r e c ts l i c e ，w h i c hi sd e s i g n e di no b j c o tp a s c a lc o m p u t e r l a n g u a g e d a t ae x c h a n g i n ga n dt h ei n t e r p o l a t i o no fi n t e r s e c t i o np o i n t sa r er e s e a r c h e dt o o b e c a u s e 3 dm o d e l v i e w i n gi sn e c e s s a r yf o rg r a p h i c ss o f t w a r e ，o p e n g lm o d e ld i s p l a yc o m p o n e n t i sa l s od e s i g n e da n d i m p l e m e n t e d t h i sp a p e ri st r yt of i n dan e w m e t h o df o rr pd a t ap r o c e s s i n g ，w i t h o u ts t l f i l e sa n dc a d p l a t f o r m t h ed i r e c t s l i c ep r o c e s s i n gi nt h i sp a p e ri sac o m p l e xa l g o r i t h m ，b u ts t a b i l i t y , h j i g h e rp r e c i s i o n ，s m a l ld a t av o l u m ea r ea v a i l a b l e k e y w o r d s ：r a p i dp r o t o t y p i n g d i r e c t s l i c i n g n u r b s s u r f a c e p l a n ei n t e r s e c t i o n d a t ae x c h a n g ec r i t e r i o n 1 1 硕士论壅堡垄垡型皇堡塑苎垫查婴塞 一一 _-_jh一一一 1 绪论 1 1 本论文的研究背景 快速成型制造( r a p i d p r o t o t y p i n g m a n u f a c t u r i n g ：r p m r p ) 是8 0 年代末出现的一神 先进加工技术，是近2 0 年来制造技术领域的一次重大突破，引发了制造技术思维方 式和生产效率的变革，受到世界许多国家政府、企业界和学术界的高度重视。越来越 多的人已认识到，r _ p 技术是缩短设计验证和功能测试所需时间的有效手段，这一新 技术可以提高营销、设计、工程、模具制造的操作功能l l 。 r p 技术目前在模具、家用电器、汽车、航空航天、军事装备、材料工程、玩具、 轻工产品、工业造型、建筑模型、医疗器具、人体器官模型、生物材料组织、考古、 电影制作等领域都得到了广泛的应用。 在快速成型技术中，属s l 工艺的加工精度最高，可达到微米级。已经有研究机 构开始使用s l 快速成型设备进行微机械加工的尝试。南京理工大学快速制造研究室 也开始进行了这方面的探索1 2 5 】。进行微机械加工，对精度要求很高，传统的s t l 切 片采用的逼近模型不能满足高精度的数据处理要求，直接切片的研究就是为切片数据 处理的质量而进行的。 1 2 什么是直接切片技术 快速成型系统的原理是离散一堆积。离散过程为三维实体到二维平面片，再由二 维平面片转化为扫描线的数据处理过程；接下来的堆积过程则实现了扫描线加工，粘 连为平面，最后由平面片堆积为三维实体的过程。由实体转化为平面片的变换类似于 现实世界中“切片”的过程，因此将这个数据处理过程称为切片。直接切片是一种精 确的切片处理方法。 按照切片方式的不同，有入将切片处理软件分为两类【6 】： 1 ) s t l 间接法，即将c a d 三维造型文件处理成s t l ( s t e r e ol i t h o g r a p h y ) 文件格式， 然后用独立的切片软件处理s t l 格式的三维实体模型为二维层片模型。s t l 间 接法是一种通用方法，但由于s t l 格式本身的限制，切片数据文件会存在许多缺 陷。 2 ) c a d 直接法，即借助c a d 平台所开发的模块，用于直接处理c a d 中的三维模 型，输出成型机所需要的数据格式。这种方法通用性较差。 堡主笙奎堡望盛型皇堡塑丛堇查翌壅一 本文没有采用上述分类方法。本文提出的概念是：凡是直接对三维曲面模型进行 的切片过程，只要输入数据的表示形式和坐标值能与设计数据保持一致，都称为直接 切片。面将采用逼近模型进行切片的过程称为间接切片。 1 3 为何采用直接切片技术 1 3 1 传统切片方法的缺陷 传统的s t l 切片，使用了一种s t l ( s t e r e o l i t h o g r a p h ) 交换文件，这种文件已成 为r p 技术的一个事实标准，s t l 交换文件采用三角面片逼近三维物体模型。通常描 述一个三维物体将会用到大量的三角面片。在切片运算中，只要对所有三角面的边与 切割平面求交，获得所有的交点，最后将交点恢复为轮廓线，即为所得的切片结果。 很明显，这种切片方法简单易行，在r p 技术发展的初期取得了很大的成功。 由于s t l 交换文件采用的是三角形逼近模型。它带来了一系列问题。 1 ) s t l 文件的三角逼近模型是一种易出错的模型 错误的类型主要有一下几种m 】： a 法向量锗误。 b 不共顶点。 c 顶点分离。 d 违反取向原则。 e 重叠面片。 f 退化的面片。 g 出现裂缝或空洞( c a p 、h o i e ) 。 大量的文献都给出了s t l 文件的错误类型及纠错方法甜。使用s t l 文件几乎 都要酋先进行纠错。 2 ) 无拓扑信息 虽然s t l 文件中包含了大量的三角形，但遗憾的是这些三角形的排列位置是无序 的，散乱分布的。在对其进行切片处理的时候，将要多次遍列s t l 文件中的所有 三角形，这对于一个三角面片数很容易就达到几十万个的s t l 文件来讲，在切片 速度上是满足不了需要的； 3 ) 数据冗余 硕士论文快速成型直接切片技术研究 由于s t l 文件先天的不足，它本身带有了很多无用的信息这将使得在进行数据 处理时，将浪费很多的内存。为了提高数据的处理效率，去除冗余信息以降低对 内存的消耗，必须对s t l 文件进行拓扑关系恢复，以建立霆所有三角形面片之间 的关系。 4 ) 精度损失问题 逼近产生的s t l 三角逼近模型存在负误差，如图1 _ 3 1 所示。虽然可以在生成s t l 文件时指定逼近精度，但是，文件尺寸随精度的增加将快速增加。特别是对于如 图1 3 2 所示的曲面物体，三角形逼近后将得到如图1 3 3 的结果。所以在实际应 用中s t l 文件难以同时兼顾精度和数据量。 图1 3 2 设计数据模型 硕士论文 一 堡垄盛型堕堡塑苎堇查笪窒 _-_-一 图1 3 3 三角形面片逼近模型 1 3 2 直接切片如何解决这些问题 为了解决上述问题，直接切片抛弃了s t l 逼近模型，采用了一种新的精确曲面 模型。在设计，传输，处理的过程中全部采用曲面模型，只涉及表达形式的变换，不 涉及逼近或拟合等近似处理。所以数据精度只受到计算机浮点数有限字长的影响，可 达到很高的精度。由于曲面模型的数据大多是曲面表达式，复杂的物体模型，都可用 相对较少的曲面加以描述，所以复杂曲面模型在数据量上大大低于s t l 文件的三角 形逼近模型。 然而，因为所有的处理都建立在曲面的基础之上，曲面的求交比平面的求交复 杂得多。开发曲面的求交算法将是童接切片技术的关键问题。 目前，曲面求交方面的研究已有相当的发展，特别是n u r b s 方法，以及追踪算 法的出现，为实现直接切片的提供了技术条件。 1 4 直接切片技术的进展 1 4 1 基于二次开发的直接切片 在国内外的文献中，关于直接切片的很少，其中较成功的是：华中科技大学的史 玉升等，借助于c a d 软件p o w e r s h a p e 的二次开发进行的直接切片的研究，以直线、 圆锥曲线和三次b e z i e r 曲线作为直接切片轮廓描述的基本元素，以p i c 文件做为切 片文件的接口标准，通过运行a u t o s e c t i o n 宏获取任意复杂的c a d 模型的直接切片 轮廓描述数据，并以p i c 文件格式进行数据传输与交换。在此基础上，开发了p d s l i c e 软件，用于处理输入、输出以及p i c 模型的重构。 硕士论文快速成型直接切片技术研究 ，_ _ 一一 由于华中科技大学的直接切片软件是在p o w e r s h a p e 软件基础上的二次开发。 所采用的是宏文件的形式，宏文件是指包含p o w e r s h a p e 命令和有关注释的磁盘文 件。p o w e r s h a p e 提供了记录命令序列与利用文本编辑器编写两种产生宏文件的方 法，并提供了单步运行和连续运行宏文件的方法，用户可根据需要来选择。直接切片 的过程为：把设计模型的尺寸控制在可制造范围内，利用系统功能将加工方向调整为 世界坐标系中的z 方向，连续运行a u t o s e c t i o n 宏，即可自动进行直接切片。在宏运 行中，会出现切片厚度s l i c et h i c k n e s s 对话框，操作者应该根据需要输入切片厚度。 完成后，在自动出现的对话框中选择p i c 文件类型存储。 采用宏文件的方式有利有弊。其运行方式是解释型的，故效率较低。系统首先要 读入宏文件，一句一句对命令解释执行，运行完毕结果存储于p i c 文件中。但是，这 种方式的可靠性高，容错性好。通常宏文件提供的功能都比较有限。所以华中科技大 学的a u t o s e c t i o n 宏文件没有实现自适应切片，而是采用的等层厚切片。 1 4 2 求等值线技术 快速成型技术切片的目的就是获得二维轮廓信息，这里所指的轮廓信息为三维物 体表面与切割平面的交线。可以说直接切片技术实际上是一种曲面的求交技术。这里 讨论一篇求等值线的文献。即北京大学计算机科学与技术系的都志辉等人的求 n u r b s 自由曲面的等值线一种基于极值点的追踪方法一文【1 3 1 ，其解决的问题 是：已知二维地理空间上有m n 个离散采样点( x i ，y j ) ，i = 1 ，2 ，m ：j z l ， 2 ，n 。在这些点上都有对某物理量，的取样值。且假设用n u r b s 得到一个光滑 - 的拟合曲面s ( u 。v ) ： - s ( u ，v ) = ( x ( u ，v ) ，v ( u ，v ) ，f ( u ，y ) ) 0 u s l , 0 v 1( 1 4 1 ) 求这个曲面上的等值线。 可以看出这个问题与直接切片的实质是样的，都是曲面与平面的求交问题。这 篇文章中提出了一种较为实用的曲面求交算法，这个方法对s g s a t t e r f i e l d 的求等 值线方法做了重要改进。该算法对n u r b s 曲面片的边界上的极值点及曲面内的极 值点进行了扫描分析，可快速求出全部等值线的切矢追踪始点，从而避免了盲目搜索 和重复追踪。 基于极值点的追踪算法把等值线分为两类：环形等值线，非环形等值线。对于非 环形等值线直接求出边界与切割平面的交点就可得到初始追踪点：而对于环形的等值 线可先求出曲面的极值点，然后求出过该极值点的等参数曲线，并求出其与切割平面 的交点，即为初始追踪点。 硕士论文 一一 堡望盛型皇垄塑苎堇查堑壅 。 利用这种基于极值点的追踪算法解决了初始交点的搜索问题，是一种较为实用的 求交算法。但是，没有给出具体的追踪算法实现，且在极值点的求取问题上没有阐述 清楚；他们提出的极值点算法思路有数值不稳定现象。 1 5 本论文的研究内容 本文的研究首先分析了相关的课题，在此基础上提出了直接切片的三维模型表示 方法，以及建立在该模型表示方法之上的直接切片原理。并对直接切片的实施进行了 深入研究。 本文作者在直接切片的研究中借鉴了基于极值点的求交追踪算法【13 1 ，并将其进一 步完善。在求极值点的策略上提出了更实用的解决方法，并且实现了一个b 样条函 数的快速计算算法，并优化、编写了一系列求交的辅助算法。 本文还研究了直接切片软件与c a d 软件进行数据交换的方式。对本文所采用的 i g e s 标准作了详细的说明，并给出了读取的方法。 在图形的显示方面，本文也作了研究，开发了基于o p e n g l 图形库的三维模型显 示组件，实现了模型的真实感渲染显示。 最后，通过作者制作的一个测试软件，完成了对算法求交精度的分析，及对比分 析。 硕士论文快速成型直接切片技术研究 相关图形学基本理论介绍 在这一章中将对本文用到的一些基本图形学理论作一个介绍。 2 1 n i 瓜b s 曲线、曲面 在c a d c a m 或图形方面，非均匀有理b 样条n u r b s ( n o n u n i f o r mb s p l i n e c u r v e ) 无疑是最有前途的曲线或曲面【1 5 】。它是几何造型的一个十分有用的工具，在 曲线和曲面的几何造型中，在c a d c a m 以及图形领域中都愈来愈得到广泛的重视 和应用。n u r b s 为表示和设计标准的解析曲线或曲面以及任意形式的曲线或曲面提 供了统一的数学形式，通过它可以灵活地设计各种形状的曲线或曲面，并具有计算稳 定，速度快的特性。 n u r b s 曲线为一矢值有理多项式函数，其表达式为【1 5 】： 土 b t t ( ”) w f k p ( u ) = 芒_ 一 ( 2 1 1 ) e ，t ( “) w i i = 0 式中v i 为控制点，w 为权因子，b i 。k 为k 次b 样条基函数。 式中b 样条基函数由d eb o o r - c o x 递推公式 1 6 - 1 8 1 定义： 吣咖苫“+ l b ；i ( ) = 导b ，。一，( “) + ：；- ! ! 二! j ；一b 。一。( “) ，女l ( 2 1 2 ) “，+ 一“i “j + “i 一“i + i = 0 式中k 为幂次：u i ( 1 = 0 ，l ，m ) 为节点，由其形成的节点矢量u ： u = = 【! ：! ：翼，”t + ，“m t 一- ，! ：! ：立】 ( 2 1 3 ) k + l + l n u r b s 曲面是非均匀有理b 样条双参数曲面【1 9 , 2 1 1 ，由下式定义 7 硕士论文快速成型直接切片技术研究 b ( “) b “( v ) w u 。， p ( ”) = 竺# 一 e 。( “) 毋，( v ) w 。 ( 2 1 4 ) 式中v j 为控制顶点，w j j 为权因子，b ( u ) 和b ( v ) 分别为沿u 向的k 次和沿v 向 的1 次b 样条基函数。u 向和v 向的节点矢量分别为： u = 【坠旦0 1 ， 矿= 垒堡二! ，叶+ ， l ，l ，1 ，1 】 “l ，v “- l 1 ，1 ，1 】 ，+ 1 ( 2 1 5 ) ( 2 1 6 ) 式2 1 5 中和式2 1 6 中，沿u 向和沿v 向的节点矢量的节点数分别为( 什1 ) 和 ( s + 1 ) 。其中r = n + k + 1 ，s = m + l + 1 。 2 2 b 样条的性质 下面介绍一下b 样条的性质2 2 1 。因为n u r b s 曲线曲面的特性主要受其基函数 b 样条函数的影响。 2 2 1 b 样条的局部支撑性 局部支撑性是b 样条最重要的性质之一，也是b 样条方法与b e z i e ：r 方法的主要 差别所在，由于局部支撑性，为b 样条用于曲线、曲面设计奠定了良好的基础。 由递推定义式可知 ( 2 2 1 ) 式( 2 2 1 ) 表明，第1 条k 次b 样条仅在节点u 到u i + k + l 的k + 1 各区间内不为0 ，而 其余区间内均为0 。这个性质称为局部支撑性。可以发现，一段b 样条曲线只涉及到 k + 1 个基函数，只由k + 1 个顶点所定义。 所以局部支撑性对于曲面曲线的设计有两方面的影响：首先，修改段曲线只需 修改有关的k + 1 个顶点。第二，修改一个顶点，影响到的曲线只有相关的k + 1 段。 曲线曲面快速求值算法利用了局部支撑性，这可加速曲线曲面的求值运算( 见 8 1j1j + + “ “ ” “ ，p l 兰j 芒 x x o o = ，t、l = 、jg 址 8 硕士论文快速成型直接切片技术研究 4 4 2 n u r b s 曲线曲面快速求值算法) 。 2 2 2 b 样条的凸组合性 b 样条的凸组合性可表示为： b 聃g ) = l ( 2 2 2 ) l - 枷 c l a r k 为了定义b 样条基函数，把凸组合性作为最基本的约束条件。b 样条的凸 组合性保证了b 样条曲线的凸包性，即b 样条曲线必处在控制多边形所形成的凸包 之内。b 样条有较强的凸组合性对于曲线、曲面的设计有重要意义，它使设计人员能 更方便地控制b 样条曲线的形状。利用凸组合性质，可计算曲面模型的大致包围盒， 从而控制模型的显示。同时也可以利用它来初步判断曲面与切割平面是否相交。 2 2 3 b 样条在节点处的连续性 b 样条的连续特性可归纳为如下两点： a 若节点矢量中节点均不相重，则k 次b 样条在节点处为k 1 次连续。 b 当存在重节点时，在重节点处的连续性将相应降低，若节点j 的重复度为 m j ( 共出现m j + 1 次) ，则在该点处，b 样条的连续性将降低m j 阶。 2 3 切矢、法矢 ( 1 ) 曲面上曲线的切矢 曲面上曲线的切矢可按式2 3 1 计算【1 5 】： ，r ：d ，r 。= ( x ( 9 ，y l ( t ) ，z ( t ) ) 应用复合函数求导公式，则曲面上曲线的切矢可表示为： d ud w 2 l i + i 式中l = ( 兰，罢，昙) 和o ：( 要，宴，喜) 分别为甜向和w 向的切矢。 o u 删d 甜o 1 4 , o wo w ( 2 ) 曲面的法矢 ( 2 3 1 ) ( 2 3 2 ) 硕士论文 堡鎏盛型皇鏊翅苎垫查翌窒 - _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ - 一 曲面上任何一条曲线的切矢都处在由切矢 和r w 所张成的平面内，该平面称为 曲面在该点的切平面。并且该切片面的法矢就是曲面在该点的法矢，其方向和大小由 r u ) c 3 w 求得，单位法矢则为： n ：塑 l 0 1 2 4 一般曲面求交方法 f 2 3 | 3 ) 曲面求交是c a d c a m 领域最为重要的问题之一，求交问题包括曲面曲面求交， 曲面，平面求交，曲面曲线求交，曲面直线求交，曲线曲线求交，曲线直线求交等 予问题。其中最重要、难度最大的当属曲面曲面求交的问题，其他的求交问题都可 以用曲面，曲面求交的思想予以解决。 所谓曲面求交就是指给定两张曲面，通过一定的算法求得两张曲面所有交线( 当 相切时，包括切点和切线) 的过程。国外在这方面的研究始于6 0 年代，发表的论文专 著非常丰富。s o u t h 和k e l l y 使用网格法计算双三次曲面片等高线的方法进行求交1 2 ”。 s a b i n 和b a r n h i l l 等人提出根据交线的代数几何性质采取迭代和追踪相结合的方法沿 着交线走向去寻找下一交点，从而得到所有整条交线 2 4 - 2 6 1 。 2 4 1 曲面分割法求交法 分割法是一种离散近似的方法，求交的精度不高。与其他方法相比，分割法的思 想简明，计算速度快，一般与其他求交方法结合使用。分割法的求交过程为：先对两 张曲面的凸包做相交测试，若不相交，则有曲面凸包性质可知，两张曲面不会相交， 如果相交则曲面可能相交，则将曲面分为四块，而后对每一块进行进行上述过程，当 曲面分得足够平坦了，则停止分割。这时，曲面已经可以由分割后的平面片近似代替， 以平面求交，就可获得交线删。 应用分割求交法应注意以下问题： ( 1 ) 分割深度控制。比较常用的是等深度分割和自适应分割两种控制方法。应用 等深度分割时，在算法开始前就指定一个分割深度，一旦达到就停止分割， 自适应分割是指在分割过程中同时检查曲面片的平坦度来决定是否需要继续 分割。一般以凸包的厚度和凸包底面的面积之比来表示平坦度。但是，自适 应分割产生不连续的区域，导致交线断开。一般情况下，采用等深度分割为 堕主鲨奎堡望盛型皇堡塑生垫查堕塞 好。 ( 2 ) 求交测试凸包的构造。对与一般的b 6 z i e r 或b 样条曲面片，理论上凸包是一 个不规则的形体，不便于直接用于求交测试，故必须做某种简化。常用的方 法是取曲面片的包围盒作为简化的凸包。包围盒作为简化凸包的缺点是其形 状与曲面片的真实形状相去甚远，会出现大量包围盒相交，而曲面片不相交 的情况。有人建议用斜凸包的方法加以改进。斜凸包不是在全局坐标系中确 定包围盒，而是在两个曲面片的局部坐标系中确定包围盒，局部坐标系一般 由曲面片的四个角点来构造。这样改善了包围盒与曲面片的接近程度。 ( 3 ) 近似求交方法的选择。曲面被分割到一定深度后，其子曲面片已经足够平坦， 曾有人提议使用双一次曲面近似求交，也就是以子曲面片的四个角点构造双 一次曲面片，运用代数法求得两张益面的交线，近似代替原曲面得交线。该 法得优点是精度比较高，但是该算法得稳定性差，也比较复杂。 2 4 2 曲面迭代求交法 曲面迭代求交法用于求得精确交点。其中n e w t o n r a p h s o n 迭代法得到了广泛得 应用。该法的优点为计算精度高、速度快。在初值选择比较合理的情况下，一般仅需 迭代二至三次，就可使交点的精度从百分之几提高到至万分之几甚至百万分之几的数 量级。只要能获得曲面的几何位置、切矢、法矢等信息，就可应用迭代法。其缺点是 对初值要求比较严格，如果初值选择不当可能导致不收敛。在曲面求交问题中，可分 为三参数迭代法和四参数迭代法两种类型。 ( 1 ) 三参数迭代法【1 5 1 设有两片曲面s l ( u v ) 和s 2 ( s ，f ) ，并已知一交点的初始估计点p o ，p o 点在两张曲 面片上所对应的投影点分别为p l = s l ( u o ，v o ) 和p 2 = s 2 ，t o ) 。设以s o 为固定参数，则 问题就转化为求u + ，v + ，t + ，使两曲面片上的点s l ( “+ ，v + ) 和s 2 ( 印，f + ) 重合。令 霄化v , 0 = s ( 珥1 ：一s 2 ( ，矽= 0( 2 4 1 ) 该式为一个非线性矢量方程，可用n e w t o n r a p h s o n 迭代法求解。当满足迭代终 止条件： 忙似，v 。，t 州5 s 为容差 ( 2 4 2 ) 时，停止迭代，并通过下式得到精确交点： 硕士论文堡垄堕型里堡塑苎垫查竺窒一 ，_ _ _ _ _ _ _ _ * _ - _ 一一 p + ：去晦，( “女，v t ) + 最( ，f ) ( 2 4 - 3 ) ( 2 ) 四参数迭代法【1 s 】 四参数迭代法是一种几何方法，不象三参数迭代法那样需提供固定参数s o ，所以 适应性更好。设已知条件与三参数迭代法相同。其具体方法是：分别作两投影点p 1 和p 2 的切平面，然后计算p 1 和p 2 在两切平面交线上的投影的中点p o 。将p 0 作为 新的估计点，计算投影点p 1 和p 2 重复上述过程。当两投影点间距小于容差时终止 计算，并取两投影点的中点为精确交点。 计算p 0 的公式为： p o = 三 p i + p ：】+ 吉石i - 了：丁j ( p 丑) ( ( m n ) m - - i i ) 一( p m ) ( ( m n ) n m ) 1 ( 2 4 4 ) 式中，m ，n 分别为p 1 ，p 2 的法矢量，a p = p 1 - p 2 利用四参数迭代法时，要求m n 1 ，否则式( 2 4 4 ) 无意义。m n = 1 的几何意义 是两张曲面s l 和s 2 在该点具有相同的单位法矢，即两者相切。因此在两曲面的切点 附近，四参数迭代法会出现数值不稳定性。 2 4 3 曲面追踪求交法 追踪算法的原理：假设两曲面间共有n 个交线环，先通过某种求交方法确定各 交线环上的一个交点，然后以该交点为初始交点，根据交线的几何性质，按照一定的 步长计算该条交线附近的一个近似值，再应用迭代法求得精确得交点。沿交线走向不 断前进，直至遍历整条交线。 追踪法的优点是在求得首交点后搜索其余交点得速度非常快，且适用范围广。只 要曲面不存在非正则点，并可以求得曲面上的坐标位置、切矢、法矢等几何信息，就 可用追踪法求交。追踪法存在的问题是：目前尚无有效方法来求得初始交点。 硕士论文 堡垄壁型皇堡塑笠垫查婴窒 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ - - _ _ - - _ _ _ _ _ _ _ _ _ _ _ 3 直接切片原理 直接切片的实质就是将三维数据离散为二维数据。具体的做法就是用一系列垂直 于z 轴的平面与三维实体的表面求截交线，所得的截交线通常为一个或多个封闭的曲 线环，这些封闭的曲线环所包围的面即为二维的层片。可以得出结论，切片的任务就 是实体表面与平面的求交问题。如何来描述实体表面，如何来描述几何实体? 这两个 问题直接影响到切片的方法及效果。这里先讨论下三维几何模型的描述。 3 1 几何模型的表示 直接切片所需的数据为实体的表面信息，切平面的z 轴坐标。实体的内部信息以 及表面的拓扑关系对于切片来说都是冗余的。所以三维模型的精确描述只要提供了表 面信息就足够了。 实体的表示方法通常分为两大类，边界表示( b o u n d a r yr e p r e s e n t a t i o n ，b r e p s ) 用 一组曲面来表示三维物体【2 7 1 。这些曲面将物体分为内部和外部。边界表示的典型例子 是多边形平面模型和样条曲面模型，如图3 1 1 所示。空间分区( s p a c e p a r t i t i o n ) 表 示用来描述内部性质，将包含物体的空间区域划分为一组小的、非重叠的、连续实体 ( 通常是立方体) 。三维物体的一般空间划分描述是八叉树表示【2 6 1 。对于赢接切片来 说不需要内部信息，所以采用边界表示更为适宜。 本文采用边界表示法描述模型，而边界用什么方式表示呢? 边界的表示方法直接 关系到求交的可行性，易用性。尽管b e z i e r 曲面，孔斯曲面都是可选的曲面，但在本 文中选用了n u r b s 曲面描述边界。这是由于n u r b s 方法用于曲线曲面描述。解决了 自由曲线曲面与初等解析曲线曲面描述的不相容性问题，能够在一个系统中严格地以 统一的数学模型定义产品的几何形状。这样使得系统精简，比如：可采用统一的数据 库，易于数据管理，便于工程人员使用。另外，n u r b s 方法可通过控制点和权因子 来灵活的改变形状，具有优良的局部形状控制能力和几何不变性，以及凸包性，提高 了造型能力。所以，尽管n u r b s 方法在发展中，一些问题有待进一步研究，但它给 实际的工程引用带来了更大的灵活性。国际标准化组织( i s o ) 继美国的p d e s 标准 之后，于1 9 9 1 年颁布了关于工业产品数据交换的s t e p 国际标准，将n u r b s 方法 作为定义工业产品几何形状的唯一数学方法【2 8 j 。 硕士论文 快速成型直接切片技术研究 目一莎 图3 1 1 用曲面b - r e p s 模型表示一个球体的示意图 3 2 直接切片求交方法 直接切片的实质就是求出所有模型曲面与分割平面的相交线。然后将截交线按其 拓扑关系连接起来，构成每一层的轮廓。 比较图3 2 1 和图3 2 4 可以看出s t l 切片与直接切片的原理差别很大，前者是 平面求交，得到的是直线线段集合；后者是曲面求交，得到的是致密的精确交点表。 童接切片的截交线是由精确的关键交点组成。通过插值运算，几乎可恢复真实的 截交线曲线。将所有同一层的截交线按拓扑关系首尾连接，就可得到完整的一个交线 环。 而s t l 的截交线是近似的交线集合，交线的精度不高于s t l 模型的转化精度， 交线集没有拓扑关系，必须靠一定算法恢复交线的拓扑关系。由于模型本身的误差， 即使通过插值拟合，s t l 模型交线环的质量也不会好于s t l 模型的转化精度。 直接切片曲面平面求交算法可借鉴两参数曲面求交的技术解决，其一般方法已 在第2 章中做了介绍。 在直接切片软件中三维模型的表示使用的是b r e p s 表示，并将模型看作是剪切 n u r b s 曲面的集合。所有的面，无论是平面，或是二次、三次曲面，以及自由曲面 都统一描述为剪切n u r b s 曲面。所以，直接切片的求交问题，就是要寻求剪切n u r b s 曲面的求交算法。 硕士论文一一 堡望堕型皇壁塑生垫查婴窒 s t l 三角逼近模 型的一部分 么二一 图3 2 1s t l 切片原理图 3 2 1 基于极值点的曲面求交原理 切割平面 ( 轮廓线) 本文提出的直接切片求交算法借鉴了都志辉等人提出的基于极值点的求交算法。 这种方法较好的解决了初始交点的搜索问题，该方法的核心是追踪算法，求交速度快 ( 以下将这种方法称为极值追踪法) 。 极值追踪法的关键是追踪起始点，因为对于追踪算法来说只要有了初始交点，就 可快速追踪整条交线。实际应用中，曲面与平面的交线可能出现两种情况：一种是封 闭的交线环，种是不封闭的交线段。对于不封闭的交线段，一定与曲面的边界相交， 所以只要求出曲面边界与切割平面的交点，即为初始追踪点。然而对于封闭的交线环， 就不容易求出其初始追踪点了。 为了求出封闭环上的初始交点，首先需求出曲面上的所有极值点。对于每个极值 点都可以找到一条曲面上的等参数线通过该极值点，只要求得等参数线与切割平面的 交点，则这个交点即为初始交点。图3 2 2 ，图3 2 3 ，图3 2 4 说明了极值追踪法的 基本原理。 在初始交点的搜索中，需进行曲线与平面的求交，对于封闭环初始交点的搜索要 计算等参数线与平面的交点，对于非封闭交线段的初始交点的搜索则需要进行边界曲 线与平面的求交计算。曲线与平面的求交同样采用了基于极值点的算法。因为许多典 型算法都要求函数表达式在问题区间内保持单调。例如，曲线与平面求交问题可表达 为： l ：r t j = z 0 ( 3 2 1 ) 1 5 硕士论文快速成型直接切片技术研究 式中l 表示参数曲线，z o 为切割平面的z 轴坐标( 切割平面平行于x o y 平面) 。 于是曲线与平面的求交问题转化为求方程( 3 2 1 ) 的解的问题，如果l z ( t ) 在问题域 内非单调函数，则方程有多个解。利用二分法，弦截法都不能求出其全部解。这时， 如果先求出l z ( t ) 的所有极值，将其划分为若干个单调区间后，再分别进行求解， 则可求出所有解。图3 2 5 说明了基于极值点的曲线平面求交方法。 图3 2 2n u r b s 曲面及其极值点 极值点 图3 2 3 曲面的边界及其极值点 硕士论文快速成型直接切片技术研究 7 x 磊x 、 f1 一 卜 、二!二一， 号踪产点 j 、。、儿一， 图3 2 4 封闭环及非封闭轮廓初始交点与等值线( 俯视图) 交点v 极值点 面 图3 2 5 基于极值点的曲线平面求交方法 注：利用极值点将曲线分为若干单调区间，在单调区间上用二分法或弦截法就可求出交点 3 2 2 追踪算法及追踪步长 在第2 章中已经介绍了一般追踪算法，它具有快速，适应性广的优点。追踪算法 同样可以应用于n u r b s 曲面的求交。在本文作者的直接切片软件中，设计并实现了 一个实用的基于极值点的追踪算法。 该追踪算法的步骤为： a 求出所有初始交点。 b 取初始追踪点p 0 。 硕士论文快速成型直接切片技术研究 c 计算曲面在p 0 点处的法向量n 。 d 计算p 0 处的交线的切矢 t = n z 。 ( 3 2 2 ) 式中z 为指向z 轴正向的单位矢量 e 沿t 的方向前进一个步长，获得估计点p 1 。 f 使用迭代法将p 1 迭代到精确交点上，即p 2 。 g 以p 2 作为新的起点p 0 ，重复执行( c ) ，直到满足条件( h ) 。 h 当遇到下列情况之一时，本条交线追踪完毕。 如果p 2 回到p 0 如果p 2 与另一个初始交点的距离小于步长。 i 当满足条件，进行步长的减半或加倍操作。 j 重复步骤( a ) ，直至追踪完所有的初始交点。 图3 2 6 ，说明了追踪算法的原理，可以看出，追踪算法求得的交点具有严格的拓 扑顺序，与s t l 切片求交的结果不同，后者的交点表是无序的。需进行恢复拓扑信 息的处理。 追踪算法有三个需要解决的问题：1 ) 追踪方向迷失：2 ) 如何确定追踪步长；3 ) 结束判断。 ( 1 ) 追踪方向迷失 对于追踪方向的确定有一个值得注意的问题。当曲面与切割平面相切时，由于在 切点附近曲面法矢量与z 辘向量非常接近，用式( 3 2 2 ) 无法确定遥踪方向，这就是所 谓“迷向”问题。 图3 2 6 追