（材料加工工程专业论文）fdm、sla快速原型系统数据处理.pdf

华中科技大学硕士学位论文 摘要 本文对f d m 、s l a 快速原型数据处理的若干关键算法进行了研究，针对f d m 、 s l a 快速原型系统的特点，设计了快速原型数据处理软件。 路径填充算法是多数快速原型系统通用的算法，其中路径填充又分为扫描线路径 填充与偏置路径填充两种。本文针对以往扫描线填充算法把分区与生成填充路径分离 出来的缺点，提出了一种速度快、分区效果好的扫描线路径填充算法基于拓扑信 息的扫描线路径填充算法。l 这种扫描线填充算法对拓扑信息要求严格，还可以应用到 偏置路径填充之中，作为处理轮廓环的自交、相交的处理器。一3 快速原型软件一般都是从读入s t l 实体模型开始工作的。由于s t l 造型本身固 有的复杂性，三维c a d 造型软件输出的s t l 实体模型往往会出现错误。对于依赖于 s t l 提供的实体信息进行加工的快速原型系统来说，必须能纠正这些s t l 模型错误 才能正确工作。岫于s t l 模型错误出现的复杂性，自动纠正s t l 实体模型错误的软 件往往只能纠正某些方面的错误。因此有必要发展s t l 模型的手动纠错算法作为对 s t l 模型自动纠错软件的补充。你文利用o p e n g l 的特性以及w m d o w s 的鼠标消息 处理机制与m f c 的文档、视图结构，实现了轮廓环手动纠错的算法及其所用到的缩 放、平移、捕捉技术。 f d m 、s l a 快速原型系统均需要添加支撑的操作，它们的上层数据处理模块均 涉及大规模的数据存储，开发一种适用于这两种快速原型系统的离线快速原型数据处 理软件很有必要本文采用了面相对象的“起草法”，对数据处理软件进行规划，并 设计出一种具有友好界面的f d m 、s l a 数据处理软件。 关键词：快速原型j 数据处鼍葑扫描线填充算法?手动纠错j 起草法 面向对象义s t l 8 泄， 华中科技大学硕士学位论文 a b s t r a c t t h i sa r t i c l ei sa b o u ts o m er e s e a r c hw o r k si n k e yd a t a - p r o c e s s i n ga l g o r i t h m so f f d m s l a r a p i dp r o t o t y p i n gs y s t e m sa n dl a y so u tt h ed a t a - p r o c e s s i n gs o f t w a r ea c c o r d i n g t ot h e s es y s t e m s r o a d f i l l i n gw h o s ea l g o r i t h mi su n i v e r s a lt om o s to f r a p i dp r o t o t y p i n gs y s t e m sc a nb e c l a s s i f i e di n t os c a nf i l l i n ga n do f f s e tf i l l i n g c o n u a p o s i n gt h es e p a r a t i o no f d i s t r i c t i n ga n d f i l l i n go fp r e v i o u ss c a n n i n gf i l l i n ga l g o r i t h m s ，t h i sa r t i c l eb r i n gf o r w a r dt h es c a nf i l l i n g a l g o r i t h mb a s e do nt o p o l o g i c a lw h i c hc a nc r e a t i n gt h ed i s t r i c t e dp e r f e c t l ys c a nf i l l i n g r o a dq u i c k l y a n db e c a u s eo fi t ss t r i c t r e q u i r e m e n to ft o p o l o g i c a lr e l a t i o n sa m o n gt h e o u t l i n er i n g s ，i tc a na l s ob eu s e dt op r o c e s st h ep r o b l e m so f t h e i n t e r s e c t i n go f r i n g - s e l f a n d t h ei n t e r s e c t i n gb e t w e e n t i n g s ，w h i c hw i l lc o m e f o r t hi nt h eo f f s e tf i l l i n g r a p i dp r o t o t y p i n gs 0 1 a r ea l w a y s s t a r t sf r o mp u t t i n gi n t os t lm o d e l a st h e c o m p l e x i t yo f s t l m o d e l i n g t h e r ea l w a y s 黜m a n ym i s t a k e si nt h es t l m o d e l o u t p u t t e d b y3 dc a d s o f t w a r e d e p e n d i n go n t h ec o r r e e n t a s so fs t l m o d e l ，t h ep r o t o t y p i n gs y s t e m w i l ln o tw o r k c o r r e c t l yu n t i lt h em i s t a k e si sp u tr i g h t a st h em i s t a k e so f s t lm o d e la r e v e r yc o m p l e xa n d t h ea u t oc o r r e c t i n gp r o g r a m s o n l yc a np u tr i g h t s o m ek i n d so f m i s t a k e s ， i ti sn e c e s s a r yt od e v e l o pt h em a n u a l c o r r e c t i n gp r o g r a m s a ss u p p l e m e n t u s i n gt h em o u s e m e s s a g em e c h a n i s mo fw i n d o w ss y s t e m ，t h ed o c u m e n t v i e ws t n l o t u l eo fm f ca n dt h e f e a t u r eo f o p e n g l ，t h i sa r t i c l er e a l i z e dt h eo u t l i n er i n g s m a n u a lc o r r e c t i n ga n dt h es c a l i n g ， m o v i n g ，s n a p p i n gt e c h n i q u e si tu s e d a sf d m s l ar p s y s t e m sa l ln e e da d d i n gs u p p o r t a n dt h e i rd a t a - p r o c e s s i n gm o d u l ea l l i n v o l v e st h er e a d i n g s a v i n go fl a r g en u m b e ro fd a t a , i ti sn e c e s s a r yt od e v e l o pak i n do f d a t a - p r o c e s s i n gs o f t w a r es u i tt ot h e s es y s t e m s t h i sa r t i c l eu s e s d r a f t i n gm e t h o d w h i c hi s ak i n do fo o pm e t h o dt op l a nt h ec o d ea n dh a sl a i do u tt h ed a t a - p r o c e s s i n gs o f t w a r ew i t h f r i e n d i yi n t e r f a c es u i tt of d m s l as y s t e m s k e yw o r d s ：r a p i dp r o t o t y p i n g d a t a - p r o c e s s i n g s c a n f i l l i n g a l g o r i t h m m a n u a l c o r r e c t i n gd r a f t i n gm e t h o d o o ps t lm o d e l i i 华中科技大学硕士学位论文 1 绪论 本章介绍了快速原型技术的概况以及课题的来源、意义与课题研究的主要内容。 1 1 快速原型技术概述 快速原型( r a p i dp r o t o t y p i n g 简称r p ) 是8 0 年代末期才出现的一种全新的制造 技术，它高度集成了高分子树脂化学、c a d c a m 技术、数字控制技术、激光技术、 新型材料科学等诸多技术的最新成果，在家用电器、汽车、玩具、轻工产品、建筑模 型、医疗器具、航空航天、工业造型、电影制作等领域得到了广泛的应用 z - 5 1 。 其目前的作用有： 6 - 1 q ： 1 ) 提供产品样本，以便于设计评审、性能测试及装配实验。 2 ) 用于快速模具制造。 3 ) 用在医学领域。 4 ) 用在微型机械方面。 1 2 快速原型的工艺 快速原型系统的应用软件在功能上可以划分为两个层次：上层c a d 、c a m 模型 处理与下层系统控制两个层次。快速原型的上层软件模块的主要任务包括提供友好的 人机操作界面、接收c a d 模型的输入、显示三维c a d 模型、根据用户要求完成分层 切片处理任务并显示切片结果、生成快速原型系统的扫描路径信息以及把这些信息发 送给下层软件等；下层软件模块的主要任务包括接收扫描路径的信息、根据路径信息 完成插补运算、根据插补结果控制快速原型系统的运动等【l ”u 】。 r p 系统的应用软件中最为关键的是从c a d 到r p m 接口的数据转换和处理。国 外的各大r p 系统生产商一般都开发自己的数据变换接口软件，如3 ds y s t e m 公司 的a c e s 、q u i c k c a s t ，h e l l i s y s 公司的l o m s i i c c ，d t m 的r a p i d t o o l ，s t r a t a s y s 的 q u i c k s l i c e 、s u p p o r t w o r k s 、a u t o g e n ，c u b i t a l 的s o l i d e r d f e ，s a n d e rp r o t o t y p e 的 p r o t o b u i l d 和p r o t o s u p p o r t 等【1 4 1 。 具体到不同的快速原型工艺，他们的插补运算、控制模块是不同的，但是他们的 上层软件模块有很大的相似性与独立性。由于c a d 与r p m 的数据变换接口软件开发 华中科技大学硕士学位论文 = = = ；= = = ；= = = = = = = = = g = = = = = = = = = = = = = = = = = = 一一 的困难性，国外涌现了很多作为c a d 与r p 系统之间桥梁的第三方软件，这些软件 一般都是以常用的数据文件格式作为输入输出接口。输入的数据文件格式有s t l 、 i g e s 、d x f 、h p g l 、c t 层片文件等，而输出的数据文件一般为c l i ”l 。 从技术角度说，数据转换和处理软件的难度集中在s t l 自动纠错、支撑的自动 添加、快速模具制造时的实体空腔化或网格( 1 a t t i c e ) 化处理、扫描矢量的生成等环 节。目前国外软件综合起来在这些方面处理的比较好，而且有人工智能化的趋势。 1 3 课题的来源 华中科技大学( 原华中理工大学) 从1 9 9 1 年开始从事快速原型技术的研究，先 后得到了国家自然科学基金、国家教育部博士点基金、国家科技部、湖北省科委和武 汉市科委的资助。本课题来源于8 6 3 c i m s 重大且标产品项目“快速原型制造技术的 研究与开发”( 编号：8 6 3 - 5 1 1 - 9 2 0 - 0 1 0 ) 。 1 4 本文研究的主要内容 本文研究的主要工作就是开发种离线的适用于f d m 、s l a 快速原型系统的数 据处理软件，该软件包含了快速原型应用软件上层模块的内容，它们分别是： 读入模型。用于快速原型的模型有两种，一种是s t l 文件、c s 文件等实体文件 的模型，另一种则是实验室规定的适用于f d m 、s l a 快速原型系统的z i f 格式的文 件，它里面包含这两种系统所使用的实体、切片、填充路径等所有的信息。 对读入的实体模型进行切片处理。读入的实体模型可能是正确的实体模型，也可 能包含着漏洞等错误。在切片的时候，有两种选择，一种选择是采用自动修复的功能， 切片出来的轮廓环都是闭合的环，另一种选择是采用手动修复的功能，切出来的环不 一定是闭合的，这个时候要求对切片结果进行手动修复。手动修复的时候，需要对切 出来的轮廓环进行放缩、平移等变换以及捕捉、选中点、取消选中等操作。 对实体加支撑。实体模型可能遇到上面截面悬空的情况，这个时候就需要对他们 进行加支撑的操作。目前，加支撑的操作是根据切片结果进行的，它是由同课题组的 刘红军硕士完成的。 对生成的切片、支撑轮廓环分别进行生成填充路径的操作。本软件采用的路径生 成算法在生成路径的同时，就把分区工作给做好了，路径生成速度快、分区效果好， 是二盈理塑盟重艇迭蕉厦型丕筮丝墓鎏： 2 华中科技大学硕士学位论文 友好的操作界面。本软件为了用户的操作的方便，使用v c + + 6 0 以及o p e n g l 技术开发出了基于w m d o w s 的具有友好界面的应用程序。用户可以看到切片、路径 的轮廓环以及它们上下几层在世界坐标系里面的形状，用户可以从应用软件的左边的 列表框视图之中选择需要观察、修改的层，并且在显示轮廓环的视图里使用鼠标对他 们进行缩放、修复、平移、复原等操作。 1 5 小结 本文首先简要介绍了快速原型的应用；然后介绍了快速原型应用软件所要做的工 作；后面又介绍了课题的来源、以及课题的意义：最后介绍了本文所研究的主要内容。 华中科技大学硕士学位论文 = ；= = = = = = = = = = = = = ；= ；= = = = = = = = = = = t 一： 2 基于拓扑信息的路径生成算法 本章首先介绍了扫描线路径填充算法的意义以及以往该算法的缺陷，然后针对这 些缺陷提出了基于拓扑信息的路径生成算法，最后根据这种算法对拓扑信息要求严格 的特点，提出把它用于处理偏置以后轮廓环相交问题的设想。 2 1 弓l 言 在激光快速原型加工过程中，最基本的操作是扫描固化零件的截面 1 6 - 1 9 1 。对于 s l a 、s l s 以及f d m 等工艺的快速原型系统，扫描头的扫描轨迹一般是相互平行的 直线【2 0 】( 偏置线或扫描线) 。由于分层得到的截面信息只是轮廓数据，因此以上三种 快速原型加工过程必须经过由轮廓数据生成填充路径这一步骤，故填充路径生成算法 有很大的通用性，能够适用于多种快速成型工艺。 c a d 系统采用实体或表面模型表示零件，系统不同采用的数据格式也不相同( 如 i g e s ，d x f ) ，故在c a d 系统与r p 系统之间必须有一个接口标准。目前的事实接口 标准是s t l 接口，即用三角面片来近似表示模型的表面，零件的c a d 数据先转化成 s t l 文件，然后再由r p 系统的切片程序对s t l 文件进行分层，分层得到的截面轮廓 是封闭多边形，由顺序相连的顶点坐标表示，并且首尾坐标值相同。多边形的复杂程 度不定，可能是一个或多个，凹或凸，包围的区域可能是单连通的，也可能是多连通 的。 所以，问题转化为复杂多边形的填充问题。这个问题在计算机图形学中讨论得较 多，如光线跟踪法等，d a ng o r d o n 等又提出了一种快速算法 2 h ，但由于扫描要采用 合适的路径，故这些方法均不能适用。 虽然目前发展出了多种适合快速原型的填充方式，有的甚至申请了专利，但最基 本的填充路径有两种：一种是沿着截面的轮廓环一层一层向实心部分偏置( 外环向内， 内环向外偏置) 所得的填充路径( 图2 1 ) 。这种路径生成方法要处理环偏置后带来 的鼻j 的自交，内环与内环、外环与它所含内环的相交问题，以及偏置以后直线段的消 失问题。它生成的截面外形精度高，并能很好的解决成型过程中的变形、翘曲问题： 但是算法复杂，对于复杂的截面，生成路径所用的时间太长，不适合快速原型的“快 速”的要求a 因此，目前的快速原型系统基本不用这种路径方式填充，即使使用，也 一 华中科技大学硕士学位论文 往往做成离线的方式，或者只是偏置一层两层，其余部分仍然是使用扫描直线填充。 另一种则是采用一条一条的扫描直线，把截面实心的部分给填充起来所得到的填充路 径( 图2 2 ) 。这种方法生成的截面外形精度不高，连贯性不好，生成的零件的翘曲、 变形较为严重，并且由于系统惯性的影响，频繁的启停扫描设备生成的零件会有毛刺； 但是它算法比较简单、速度快，能够适应快速原型的“快速”的要求，并且如果采用 好的分区扫描的方法，能够大大减轻零件的变形、翘曲，以及减少生成零件的表面毛 刺。因此目前的快速原型设备( 特别是在线的快速原型设备) 所应用的路径填充算法 基本上都是针对这种填充方式的，被称作扫描线填充算法。 图2 一i 偏置填充示意图图2 2 扫描线填充示例图 目前实用的扫描线填充算法大都是要么是生成填充路径以后在进行加工的时候 进行分区；要么就是首先分区，在分区结果的基础上进行填充。前种思路速度快，但 是由于生成的填充路径没有足够的拓扑信息，分区效果不理想；后一种思路分区效果 好，但是由于多了一个耗时间的分区过程而使得速度较慢。 本课题针对目前采用的扫描线填充算法分区与速度不能兼顾的问题提出了一种速 度快，分区效果好的扫描线填充算法。该算法在生成扫描线填充路径的同时进行分区 处理，故在分区的时候有足够的拓扑信息来取得较好的分区效果；同时，该算法省去 了专门的分区步骤，节省了时间、速度快。另外，这种算法对轮廓环的拓扑关系敏感， 根据这一特性还可以把它应用在偏置填充算法中充当处理环的自交、环的相交问题的 工具。 2 2 以往的路径生成、分区算法 根据对快速原型系统的分析，路径生成算法主要解决的问题是如何提高路径生成 数速廑三一皇旦塑熊尘至堡丝塑鱼：銮丝坠垦垫堡量壹生感蕉亘箜垄鉴焦鏖盟塑垦：亘翌 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一 于扫描线填充路径生成算法来说，提高生成截面的形状精度是不可能的，因此，这些 算法所要解决的主要问题就是怎样提高路径的生成速度，以及怎样分区，以减小生成 零件的翘曲变形、减少毛刺的问题。 1 ) 提高路径生成速度的问题：扫描线填充路径生成算法一般都是首先求出扫描 线所在的直线与轮廓环的所有交点，然后再根据这些交点找出扫描线与被扫描截面的 交线段，这些交线段就是所要生成的扫描线填充路径。由于切片得出的轮廓环是一条 一条的小直线段连接起来所形成的闭合环，因此生成扫描线填充路径的问题就转换成 求出某直线与轮廓环中与该直线相交的所有直线段的交点，并以这些交点为界，找到 该扫描线与被扫描截面的交线段的问题。由于求水平直线( 竖直直线) 与轮廓环的交 线段的算法简单、速度快，并且求斜线与轮廓环的交线段的问题可以通过适当的旋转 变换转化成求水平直线( 竖直直线) 与轮廓环的交线段的问题，因此目前的扫描线填 充路径生成算法都是处理扫描线为水平直线( 竖直直线) 时的路径生成问题的。为了 方便，这里假设扫描线为水平线。而要求出某水平线与轮廓环之中与该直线相交的直 线段的交点，首先要找出该轮廓环之中所有与这条水平线有交点的直线段( 也就是找 出两端点的y 坐标分别在这条水平线的上方与下方的直线段) 。如果对于每一条水平 线都要遍历轮廓环的所有的组成线段来寻找与其有交点直线段的话，假设这个轮廓环 有n 条直线段、要把整个截面填充起来需要i n 条扫描线，那么这种思路的速度为( o ) m x n ，不理想。这里有两种解决方法较好的解决了路径生成速度的问题：一种是计 算机图形学之中的活性边表法，它的思路为：把与当前扫描线相交的边称作是活性边， 放到个活性边表之中，当扫描线的y 坐标小于这个边表的某一条活性边的y m i 。的时 候根据轮廓环的连贯性，从这条边开始沿这条边所在的环寻找，找到下一条与该扫描 线相交的边来替换这一条活性边。把同一扫描线与活性边表中所有边的交点求出来放 到一起并且按照x 坐标进行排序，那么两两相邻的交点组成的线段就是所要求的填充 路径田j 。另一种算法则是填表法，它的思路是：对于轮廓环的每一条边，由于知道了 其y m i 。与y 。，那么很容易可以得到与这条边有交点的所有扫描线，把这条边与所有 与其相交的扫描线的交点求出并且按照他们所在的扫描线进行存放。这样的操作依次 遍历轮廓环的每条边，那么同一条扫描线与轮廓环的所有交点都可以求出并放到一 起a 然后对于同一条扫描线上的所有交点按照x 坐标增大的顺序进行排序，那么根据 直线穿入、穿出实体相间排列的原则，排序完成之后该扫描线上的相邻成对的交点就 组成一条条填充路径印】。这两种算法都成功的解决了提高扫描速的问题，把速度提高 一 6 华中科技大学硕士学位论文 = = ；= ；= = = ；= ；= = = = = ；= = = = 2 = = = = = = ：一 到了( o ) m ，其中m 为扫描线的数目。但是它们在生成填充路径的时候均无法分区， 为了提高加工出零件的质量只能把分区过程给独立出来，通常是在生成路径以后进行 ( 这样速度快) 。分区原则就是如果交线段数目变化了，就重新建立所有的分区( 图2 3 ，其中a 、b 、c 、d 、e 为依次要填充的区域) 田l 。由图可知，遇到b 区的时候， a 、c 区本来没有必要断开的，之所以断开是由于生成的填充路径之中拓扑信息不足 而造成的，因此这种思路分区效果不理想。 b c 圉2 3 先生成路径再分区的应用示铡 e 2 ) 减小零件的翘曲、变形与减少零件毛刺的问题：这个问题的关键是把零件截 面分成一系列的小的单调区域。单调区域的定义是：如果一簇相互乎行的直线与一个 区域的交点最多只有两个时，则将该区域称为对该直线簇是单调的。显然，每个单调 区域均可使用一条连续的折线填充。 合理的分区还可以减少零件加工过程之中扫描开关的起停次数，从而间接提高零 件加工速度。 一个平面区域是否单调取决于该区域边界的局部极值点的凸凹性态与数目。由于 我们轮廓截面是由一条条直线段组成的，因此需基于轮廓环的小直线段与相应的数据 结构进行分析。若a i ( x j ，y j ) 点为局部极值点，其判别条件为： y i + l - - y i o & & y i i y i o ( 2 一1 ) 或y i + 1 - - y i o & & y i 1 - - y i o ( 2 2 ) 其中y i 1 和y i + 1 分别为a i 的前后相邻结点的纵坐标值。满足2 1 式者为极小值， j 莆足2 2 式者为极大值。两式中不能同时取等号，若2 1 或2 2 式中各式均不取 等号，则将该极值点称为平凡极值点，否则称为非平凡极值点。显然非平凡极值点总 是成对出现的其纵坐标值相等，有凸一凸，凸一凹，凹一凹三种组合。如果某区 一一一 华中科技大学硕士学位论文 域只由非平凡凸一凹极值点的组合与平凡凸极值点组成，该区域同样能够从最高点开 始只生成一条连续的扫描轨迹，无需再进一步对它单调分割。本文将这种区域称为广 义单调区域( 图2 - - 4 ) 。 传统的专门分区方法大多是首先把轮廓环重 新组合，把截面划分成一系列单调区域的集合， 这些单调区域即为所求。由于只有广义单调区域 能够肯定只生成一条连续的扫描轨迹，因此传统 的区域划分问题就转化成为把截面划分成多个广 义单调区域的问题。比较成功的分区思路有两种： 一种思路是：定义外环的凹极值点与它所包 含的内环的凸极值点为可连极值点；由同一可连 图2 4 广义单调区域示意图 极值点的外环与它所包含的内环组成可连轮廓组：分区的原则是将可连轮廓组划分为 多个广义单调区域。两个可连极值点满足互连的条件是一个为可连极大点，另一个为 可连极小点，且连线不能与其他轮廓线相交，如果外环没有相应的可连极值点，就把 过可连极值点做的垂线与外环的交点作为相应的可连极值点。每次循环将分为左右两 个可连轮廓组( l e f = t o u t l i n e s e t 和 r i g h t o u t l i n e s e t ) 或直接加入终值轮 廓组( 所得的轮廓环中不是可连轮廓 组的) 。直至最后不再有可连轮廓组， 全部加入终值轮廓组【2 4 1 。这样，终值 轮廓组就是所求的广义单调区域的 集合。( 如图2 5 ) 这种分区思路划分的区最少，因 此分区结果最合理，减少变形、翘曲 图2 - - 5 用可连极值点的连线进行分区的示例 以及减少毛刺的结果最理想。但是算法复杂，牵扯到大数据量的读写，分区太浪费时 间，效率不高，对于复杂的截面容易产生速度瓶颈。 另一种分区思路是：定义外环的凹极值点与内环的凸极值点为有效极值点，找到 轮廓环的所有有效极值点，将各有效极值点按其y 坐标值大小排列，分别求过每个有 效极值点的扫描直线与边界线的交点，在这些交点之中离有效极值点最近的那个点称 为派生结点：以有效极值点与它的派生结点的连线为界，把截面分成一系列的广义单 皇 华中科技大学硕士学位论文 调区域【1 7 l 。( 如图2 - 6 ) 这种分区算法虽然分区效 ，弋8 2 么b 2 果不是最好，减少变形、翘曲龉号 以及减少毛刺的结果不是最理、 i 想，但是由于它比较简单，运 行速度较快，还是颇受青睐的。 这两种分区算法各有优缺 点，但是它们均是专门的分区 图2 6 用水平线进行分区的示例 算法，都把分区作为单独的预 处理步骤进行，因此应用起来速度都并不算快，效率也不算高。 2 3 基于拓扑信息的路径生成算法 2 3 1 一些术语与约定 假设使用水平扫描线自上而下扫描。 设p 。点为环上的某极值点，它前面的点是p 。一l 、后面的点为p n + l ，如果 只一e o 只只。的方向是沿z 轴向上( 也就是说，叉乘结果的z 坐标大于o ) 则称极值 点p 。为外环极值点，如果只一。只只只。的方向是沿z 轴向下( 也就是，叉乘结果的z 坐标小于0 ) 则称极值点p n 为内环极值点。( 如图2 7 ) o 一 一 图2 7 内环极值点与外环极值点的实例 篓垫 茹， 釜 华中科技大学硕士学位论文 定义两条相邻的单调链所夹的在截面内实心部分的扫描线的集合为扫描段。 定义要求与轮廓环交线的扫描线为当前扫描线。 定义y 坐标范围跨过当前扫描线的扫描段为工作扫描段。 下面将分工作扫描段不变化与工作扫描段变化两种情况进行讨论 2 3 2 工作扫描段不变化的情况 设某一扫描段的某一条单调链m 上的有向线段只一。只与扫描线l 有交点，并且下 一条扫描线l + l 与有向线段只一。只没有交点。 1 ) 当点p 。在点p n _ l 的上方的时候，( 图2 8 ) ，沿着该有向线段的反向寻找肯定 能找到单调链m 上与下一条扫描线有交点的有向线段，并且如果再往下寻找的时候 寻找方向不变。 图2 - - 8 反向寻找的情况 圈2 9 正向寻找的情况 2 ) 当点p 。在点p 。一l 的下方的时候( 如图2 9 ) ，那么沿着该有向线段的正向寻 找肯定能找到该单调链上与下一条扫描线有交点的有向线段，并且如果再往下寻找的 时候，寻找方向不变。 因此在这种情况下，只要给出扫描段的单调链，把沿该单调链与当前扫描线 有交点的有向线段与往下寻找的寻找方向给分别定出来，就可以一次性定出这个扫 描段的所有填充路径。 2 3 3 工作扫描段变化的情况 由上下极值点的定义可知，当前扫描线遇到一个上极值点的时候，工作扫描段会 l o 华中科技大学硕士学位论文 增加一段，而遇到一个下极值点的时候，工作扫描段会减少一段。也即，只有遇到极 值点的时候，工作扫描段才会变化。 1 ) 该极值点为外环的上极值点的时候( 如图2 - 1 0 ) ：增加一扫描段。增加的这一 扫描段交点为填充线段左端点的有向线段从只只+ 。起，寻找方向为该极值点所在的环 的正方向，交点为填充线段右端点的有向线段从只只一。起，寻找方向为该极值点所在 的环的反方向。 图2 一1 0 遇到外环上极值点的情况 2 ) 当该极值点为内环的上极值点的时候( 如图2 - - i i ) ：找到夹住该极值点的工 作扫描段，把它一分为二，去掉原来的扫描段。左边扫描段交点为填充路径左端点的 有向线段以及寻找方向是原来扫描段交点为填充路径左端点的有向线段及其寻找方 向；交点为填充路径右端点的有向线段从j i i 起，寻找方向为该极值点所在的环的 图2 一l l 遇到内环上极值点的情况 反方向。右边扫描段交点为填充路径右端点的有向线段以及寻找方向是原来扫描段交 点为填充路径右端点的有向线段及其寻找方向，交点为填充路径左端点的有向线段从 i 瓦起，寻找方向为该极值点所在的环的正方向a 华中科技大学硕士学位论文 3 ) 当该极值点为外环的下极值点的时候( 如图2 - 1 2 ) ：找出单调链包括有向线段 巧z 与巧z 的工作扫描段，并把它去掉。 p n 一1 图2 一1 2 遇到外环下极值点的情况 4 ) 当该极值点为内环的下极值点的时候( 如图2 1 3 ) 。找出交点为填充路径右 端点的单调链之中包括有向线段e ，只的工作扫描段并取该扫描段交点为填充路径左 端点的有向线段及其寻找方向作为新扫描段的交点为填充路径左端点的有向线段及 其寻找方向：找出交点为填充左端点的单调链之中包括有向线段只+ 。只的工作扫描段 并取该扫描段交点为填充路径右端点的有向线段及其寻找方向作为新扫描段的交点 为轨迹线右端点的有向线段及寻找方向，建立新扫描段。然后，删除所找到的那两个 旧工作扫描段。 p n 图2 一1 3 遇到内环下极值点的情况 1 2 华中科技大学硕士学位论文 2 3 4 分区问墨 假定给扫描线从上到下编号，奇数号的填充扫描线段是沿x 增加的方向扫描，偶 数号的填充扫描线段是沿x 减少的方向扫描。 根据扫描段的定义可知，每一个扫描段都可以用一条填充扫描折线来填充。当工 作扫描段变化的时候，如果某被去掉的工作扫描段的填充扫描线的终点恰好是新增加 的工作扫描段的填充扫描线的起点，则这两个扫描段可以使用同一条填充扫描折线来 填充，因此，可以把这两个扫描段的填充路径放到一起。 由以上可知，只要在生成填充扫描路径的时候把同一扫描段的填充扫描线按照前 面规定的存放方向依次存放到一起形成一条由线段的端点构成的折线块，那么当扫描 线走过整个截面以后，每一个扫描段都由唯一的一个折线块与其一一对应。因此扫描 线走过整个截面以后得到的折线块的集合就是填充整个截面所要求的扫描线填充路 径( 图2 1 4 ) 。 圈2 一1 4 分区后填充路径示例 华中科技大学硕士学位论文 2 3 5 算法流程与应用效果 得到补偿后的轮廓环信息 遍历所有的轮廓环，找出所有的极值点放到 数组里，并按照y 坐标从大到小的顺序捧列 设置当前极值点为数组第0 号元素把当前 y 坐标设为该点号对应的极值点元素的y 坐标 当前y 坐标遇到当前极值点? 是 判断是内环上极值点、内环下极值点、外环 上极值点还是外环下极值点，并按照前面所 叙述的方法对当前工作扫描段进行操作 当前极值点为下一个极值点 当前极值点存在? 求出所有当前扫描段与当前扫描线的交线， 把同一扫描段的交线连接起来。注意，必要 的时候，要按照对工作扫描段不变化的情况 的分析，找到与当前扫描线有交点的线段。 当前扫描线y 坐标减小一路径宽度 路径生成结束，输出路径生成结果 图2 1 5 基于拓扑信息的路径生成算法流程 1 4 华中科技大学硕士学位论文 如前面所述，输入轮廓环信息，输出扫描线填充路径的算法流程如图2 1 5 ： 把应用该算法生成的填充路径应用到实验室的s l a 样机上，大大提高了加工后 零件的光洁度( 图2 1 6 ) 。其中a 图是采用原来的分区算法生成的零件，b 图是采用 本文提出的算法生成的零件。 2 4 算法展望 图2 一1 6 应用示例图 本文提出的基于拓扑信息的扫描线填充算法根据拓扑信息来分区，并且分区与生 成路径同时进行，分区效果好、速度快。但是，它对于拓扑关系要求很高，不能出现 环相交的情况( 如，当内环上极值点跑到包含它的外环之外，就会出现找不到夹住这 个极值点的扫描段的情况) 。 但是，正是因为它的对于拓扑信息要求很高的特点，我们可以利用它来处理轮廓 环偏置填充路径生成算法所要处理的外环的自交以及内环与外环、内环与内环的相交 的情况。处理偏置以后的外环自交与内环、外环之间的相交问题的关键是找到两环的 交点，根据交点把轮廓环分成多个有向链并判断出哪些有向链是应当保留的、哪些有 向链是应当舍去的，舍弃应当舍去的有向链、把应当保留的有向链重新连接起来生成 新的轮廓环。本文提出的这种算法，完全可以快速的判断出轮廓环的交点的位置，在 求出轮廓环的交点并把原来的轮廓环分成有向链以后，根据本算法能够很容易的判断 华中科技大学硕士学位论文 哪些有向链是应当保留的，哪些有向链是应当舍去的。其根据是： 令扫描线从上到下依次走过轮廓环所有顶点，并分别求出当前扫描线跟工作扫描 段左边的单调链与右边的单调链的交点，如果与左边单调链的交点的x 坐标小于与右 边单调链的交点的x 坐标，说明此时左边单调链与右边单调链没有交叠的区域，此时 这两条单调链都应当保留；反之，如果与左边单调链的交点的x 坐标大于等于与右边 单调链的交点的x 坐标则说明此时左边单调链与右边单调链的区域重叠，此时的这两 条单调链应当舍弃。而单调链的交点就是在交线段x 坐标大小关系发生变化( 由左链 交点大于右链交点转换到右链交点大于左链交点或者是相反变化) 的时候所在的线段 的交点。 因此，在交线段x 坐标大小关系发生变化的时候可以求出单调链的交点，并且把 左链应当保留的部分与右链应当保留的部分通过左右链的交点连接起来，舍弃左右链 应当舍弃的部分。这样当扫描线自上而下走完所有的交点以后，则所有的环相交的情 况都处理过了，所得的最终轮廓环就是拓扑关系完全正确的轮廓环。 由上面的分析可知，使用本文提出的算法处理环的自交与相交的问题的时候，可 以只遍历一遍环的顶点就处理求轮廓环的交点以及判断轮廓环应当舍去的部分，并把 轮廓环应当保留的部分连接起来等一系列的问题，把处理环的自交、外环与内环、内 环与内环的相交问题的速度提高到( o ) n ( n 为轮廓环的顶点的数目) 。这个速度如果 用在在线的偏置处理之中，完全可以达到实际应用的目的。 因此，基于拓扑信息的扫描路径生成算法不仅能快速生成分区效果好的扫描路 径；还可以根据它对拓扑信息要求严格的特点，应用到在偏置填充对环相交问题的处 理之中。这种扫描路径生成算法有很广阔的应用前景。 2 5 小结 本文首先介绍了扫描路径的分类以及他们各自的优缺点，接着介绍了扫描线填充 路径生成算法的关键问题以及前人的解决方法与不足。后面着重介绍了基于拓扑信息 的扫描线路径生成算法的原理、流程、实验结果与应用展望。 6 华中科技大学硕士学位论文 3 轮廓手动纠错算法 本文首先介绍了手动纠错的意义，然后介绍了手动纠错用到的关键技术及其在 o p e n o l 环境下的实现，最后介绍了手动纠错算具体的实现方式。 3 1 引言 s t l ( s t e r e ol i g h o g r a p h y ) 文件是美国3 ds y s t e m 提出的一种c a d 与r p 系统之间 数据交换格式【2 ”。其最重要的特点是他的简单性：它仅仅只存放c a d 模型表面的离 散三角形面片信息，并且这些三角形面片的存储顺序是无定义的。虽然s t l 文件是 一些离散的三角形网格描述，但它的正确性却依赖于其内部隐含的拓扑关系。正确的 数据模型必须满足如下一致性规则【2 6 】： 1 ) 相邻两个三角形之间只有一条公共边，即相邻三角形必须共享两个顶点； 2 ) 每一条组成三角形的边有且只有两个三角形面片与之相连； 3 ) 三角形面片的法向矢量要求指向实体的外部，其顶点排列顺序与外法矢之间 的关系要符合右手法则。 由于三角形网格拟合实体表面算法本身固有的复杂性，一般c a d 造型系统输出 复杂s t l 文件时都有可能出现或多或少的错误( 即不满足上述一致性规则) ，出错s t l 文件的比例可高达l 7 【2 ”。对于c a d 模型显示而言，小的三角形是否正确连接并不重 要，因为这些细节部分一般不会影响到视觉效果。但对于依赖于从s t l 文件导入的 实体从指定高度上进行切片的结果进行截面加工的快速原型系统来说，若不能正确处 理这些s t l 错误，则在切片时就会出现轮廓错误、混乱、轮廓环不闭合等情况，有 时会出现截面加工错误甚至截面加工不出来的结果。 针对这种情况，一种思路是使用s t l 文件修复程序来解决这种问题，但由于 技术上的限制，目前的多数s t l 纠错程序并不能将s t l 文件所描述的三维拓扑信 息还原出个整体、全局意义上的实体信息模型，也不具有对物理实体领域相关的 完备知识和经验，因而纠错只能停留在比较简单的层次上，无法对复杂错误进行自 动纠错，或者虽然能将有错的s t l 文件修复纠正成一个“文法”上正确的s t l 文 件，但其描述的三维模型却与原始模型大相径庭。对复杂的模型一般不能使用这种 方法。 华中科技大学硕士学位论文 为解决这个问题，张李超博士提出降维、容错切片的思想【2 7 j ，它基本避开在复杂 三维层次上的纠错，在模型拓扑重构过程中对复杂的s t l 文件错误( 如裂缝、漏洞 及非正则形体等) 建模，然后对s t l 模型直接切片，利用已建立的错误模型信息在 最大程度上恢复原始正确模型的切片轮廓信息，对这样切出来的仍然包含错误的切片 轮廓，则在二维层次上进行修复，由于二维轮廓信息十分简单，并有闭合性、不相交 性等简单的约束条件，特别是对于一般机械零件实体模型而言，其切片轮廓均为简单 的直线、圆弧、低次曲线组合而成，因而能很容易地在二维轮廓信息层次上发现错误， 并依照以上多种条件、信息及经验进行去除多余轮廓、在轮廓断点处进行插补等操作， 从而得到最终正确( 或接近正确) 的切片轮廓。这种自动纠错的算法在处理有缺陷的 s t l 文件的时间复杂度为o ( n ) ，效率相当高。 口 口 口口 其中。a 图为实体，b 图、c 图为层厚为o 1 m m 时在实体的第1 4 层上分别采用 自动修复与不自动修复方法的切片结果 图3 1 自动切片结果错误的实例图 应用这种方法，绝大多数断裂轮廓已经被正确连接，但还是剩下数目比较少的 断裂轮廓不能被连接或者不能被正确连接( 图3 1 ) ，因此，有必要对于不能正确 连接的情况使用手动纠错的方式，在二维层次上通过用户的经验使得轮廓环闭合。 针对这种情况，作者提出轮廓环的手动纠错算法，作为张李超博士的自动纠错算法 的补充。 1 8 华中科技大学硕士学位论文 3 2 算法用到的技术基础 3 2 1 o p e n g l 简介m i o p e n g l 最初是独立于操作系统和硬件环境的图形开发环境，其目的是将用户从 具体的硬件系统和操作系统中解放出来，使他们按规定格式书写的应用程序可以在任 何支持该语言的硬件平台上执行。 作为图形硬件的软件接口，o p e n g l 由几百个指令或函数组成。对程序员而言， o p e n g l 是一些指令或函数的集合。这些指令允许用户对二维几何对象或三维几何对 象进行说明，允许用户对对象实施操作以便把这些对象着色到帧存上。 o p e n g l 的指令是顺序解释执行的，它的的解释模型是客户服务器模式，即客户 ( 试图用o p e n g l 进行绘制工作的应用程序) 向服务器( o p e n g l 内核) 发布命令， 这些o p e n g l 命令由服务器按照发送的先后顺序依次来解释。基于客户服务器模式， 在网络环境中的多个客户可以很容易得到在其它计算机上的服务器的服务，因此， o p e n g l 是网络透明的。 o p e n g l 的几何对象由一系列的描述它们几何性质的顶点( v e r t e x ) 或描述图像 的像素( p i x e l ) 组成。o p e n g l 对它们的操作可以简要的归为以下几类： 1 ) 图元操作与指令：o p e n g l 能够从多种可选择的模式画图元( p r i m i t i v e ) ，而 且一种模式的设置一般不会影响其他模式的设置。图元由一组顶点定义，它可以包含 一个顶点，