（物理电子学专业论文）基于图形计算几何技术的激光加工优化算法研究.pdf

i 摘 要 本文针对激光加工软件系统的特点，对 a u t o c a d d x f文件进行了深入的研究，解 决了多义线、样条曲线、面域等特殊图元的数据提取和输出等问题，并结合计算机图 形学算法，针对 d x f文件中的离散图元实现了路径优化排序，提高激光加工效率。另 外本文还研究了中轴线生成算法，并将其应用到激光加工图形填充领域，该方法在保 持边缘光滑度方面比传统的扫描线填充算法更好。本文所做的创新工作可概括如下： （1）分析和研究了 dxf 文件图形的结构，设计了适合于激光加工软件的 dxf 文 件接口程序，实现了 autocad 软件与激光加工应用的紧密结合。 （2）研究了 autocad中面域图元的作图原理和技术，设计了 dxf 文件中面域图 元的提取与优化算法，该算法可用于激光加工中针对封闭图元的连续加工。 （3）研究了基于多图元复杂 dxf 文件的图元优化排序算法，可以在激光切割软 件中对图元输出顺序进行优化和重新排序，减少空走行程，提高加工效率。 （4）研究了多边形中轴的原理和中轴生成算法，并将其应用在激光标刻过程中实 现对边缘轮廓直接偏置的螺旋路径填充加工方式中，该填充方式可以比传统的扫描方 式保持图形的边缘更光滑，无锯齿现象。 最后，本文利用 v i s u a l c + + 面向对象编程技术对上述关键算法进行了编程实现， 并将每一个功能模块程序添加到已有的激光加工排版软件中，在 d x f文件数据输入、 面域路径优化、减少空走行程以及螺旋填充加工等方面均取得了显著的经济效益。 关键词：激光加工 计算几何 d x f 文件 面域 中轴 ii abstract based on the speciality of laser processing software, this paper has made a deep research on the autocad dxf file format,solved the problem of reading and outputting of such particular object as polyline、b- spline and region,then realized the path ordered optimizedly based on dispersed graphes learned from the algorithm of computer graphics, which improved work effience. additionally, this paper has made a research on the algorithm of producting axis, which has been used in filling a closed area, and it has been proved more smooth at the edge than the old means. the main innovations of the dissertation are given below: (1) the structure of dxf format file has been analyzed and studied, a dxf file interface has been designed which has been used in the laser processing software, combined laser processing application to autocad tightly. (2) the drawing theory and technology of region in autocad has been studied, the reading and optimization algorithm of region in dxf files has been designed, in laser processing which can be used in the continuously processing with the closed edge. (3) the optimization algorithm on how to order a complex dxf file with a large number of objects has been studied, the algorithm could be used in laser curving software to help optimize the ouput order of graphics, reduce the vacant path, improve the work effience. (4) the theory and algorithm of the axis of a polygen has been studied, and it has been applicated into labeling pocess to fill a closed area offsetted directly by the edge, this means can keep the edge more smooth than the traditionally scaning filling mode, have none sawtooth. at last, the proposed key algorithms in the paper have been implemented by programming with visual c+, which is object oriented, every module function have been added the laser processing editing software, several striking beneficial results have been made in such aspects as input of dxf file, optimization for path of region, reduction of vacant path and filling a closed area spirally. keywords: laser processing computing geometry dxf file region medial axis 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密， 在 年解密后适用本授权书。 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 1 1 绪言 1.1 激光加工技术概况 激光加工技术是利用激光束与物质相互作用的特性对材料（包括金属与非金属） 进行切割、焊接、表面处理、打孔及微加工等的一门加工技术。激光加工技术是涉及 到光、机、电、材料及检测等多门学科的一门综合技术，它的研究范围一般可分为13： （1）激光加工系统。包括激光器、导光系统、加工机床、控制系统及检测系统。 （2）激光加工工艺。包括切割、焊接、表面处理、打孔、打标、划线、微调等各 种加工工艺。 激光和激光加工是一门发展极快的高新技术，已成为发展新兴产业、改造传统制 造业的关键技术之一。各种激光（标记、焊接、微调、打孔、切割、划线、热处理等） 系统、设备，已经或正在进入各工业领域，诸如电子、轻工、包装、礼品、小五金工 业、医疗器械、汽车、机械制造、钢铁、冶金、石油等，为传统工业的技术改造和制 造业的现代化提供先进的技术装备45。 近 30 年来，中国的改革开放和迅速发展着的市场经济，极大地推动着高新技术的 研发和应用。激光科学技术和激光加工是中国发展较快的高新技术产业之一。至今， 国内从事制造工业激光系统公司超过 100 家，正在形成研发、批量生产和供、销、维 修服务的体系。国产激光器已能批量生产供应中、小功率（30w500w）的 nd:yag 固体激光加工系统设备和高功率（100w- 5kw）co2激光加工系统设备。国内工业激光 制造企业已能小批量提供低、中档的激光标记、划线、焊接、切割、打孔等设备。中 国的激光器和激光技术产业的初步规模正在形成。据中国光学光电子行业协会 (coema)激光分会的统计，2001 年全国激光加工系统设备产值为 6.3 亿元人民币，相 对2000年增长86%。 2002年全国激光加工系统设备产值首次突破10亿元， 达到10.355 亿元，又比 2001 年增长 65%。据统计，2002 年全球激光加工市场销售额为 29.9 亿美 元（约 260 亿人民币） ，两者相比，中国约占 1/26。 中国国内存在着巨大的激光加工应用市场， 而这个市场因中国加入 wto 以来国内 正在迅速形成的“全球制造基地”而获得快速增长。国内外投资者和激光业者正在抢 2 滩这一市场。因此中国的激光加工技术市场将迅速增长，中国激光加工技术产业化将 会加速实现。国内外从事激光器和激光加工技术系统研发、生产和经营的企业正面临 极好机遇和挑战。 作为 20 世纪科学技术发展的主要标志和现代信息社会光电子技术的支柱之一，激 光技术和激光产业的发展受到世界先进国家的高度重视。全球激光加工设备市场持续 增长，2000 年起受经济萧条的影响，增长速度减缓，随着世界经济复苏，2004 年起激 光加工设备市场迅速回升，说明技术发达国家对发展激光加工技术的重视。我国国产 激光加工设备的销售额随国民经济的发展增长更快，尤其是从 2000 年开始进入高速发 展时期，到 2004 年已超过了 15 亿元人民币;但只占全球销售额的 5%，对一个制造大 国来说是不相称的，必须大力发展先进的激光加工技术，改造传统的制造工艺，提升 我国的制造水平，成为全球的制造强国。 2 4 % 3 2 % 1 1 % 1 2 % 1 3 % 3 % 5 % 切割 标记 焊接 微加工 雕刻 打孔 其它 图 1- 1 2005 年全球激光加工的应用情况 激光技术在我国经过 40 余年的发展，取得了上千项科技成果，许多已用于生产实 践，激光加工设备产量平均每年以 20的速度增长，为传统产业的技术改造、提高产 品质量解决了许多问题，如激光毛化纤技术正在宝钢、本钢等大型钢厂推广，将改变 我国汽车覆盖件的钢板完全依赖进口的状态，激光标记机与激光焊接机的质量、功能、 价格符合国内目前市场的需求，市场占有率达 90以上。目前激光加工技术研究开发 的重点可归纳为： （1）新一代工业激光器研究，目前处在技术上的更新时期，其标志是二极管泵浦 全固态激光器的发展及应用； （2）精细激光加工，在激光加工应用中的所占的份额和比例呈现递增的趋势，而 且应用面也愈来愈广； 3 （3）加工系统智能化，系统集成不仅是加工本身，而是带有实时检测、反馈处理， 随着专家系统的建立，加工系统智能化已成为必然的发展趋势。 进入 21 世纪后，激光加工技术更是得到较快发展，各国政府和工业部门都非常重 视激光器和激光加工技术设备的研制。中国政府一直将激光作为“先进制造技术”列 为国家重点发展项目。随着中国经济快速发展和国内“全球制造基地”规模的迅速扩 大，中国也将迅速成为全球激光器和激光加工设备应用的重要市场。面对日益增长的 巨大的激光加工应用市场和国际竞争新格局，中国的激光器和激光加工技术产业必将 有一个大的发展，这种状况给国内外从事激光、激光加工技术设备研发、生产和经营 的企业和投资者带来极好的机遇和挑战。 1.2 图形计算几何技术在激光加工中的应用概述 1975 年，shamos 和 hoey 利用计算机有效地计算平面点集的 voronoi图，并发表 了一篇著名论文，从此计算几何诞生了。自那时以来该领域取得了辉煌的成果，使得 计算几何成为理论计算机科学领域中一个新的极有生命力的子领域，并且，计算几何 中的研究成果已在计算机图形学、化学、统计分析、模式识别、地理数据库以及其他 许多领域中得到了广泛的应用。 周培德在他的计算几何算法设计与分析（第 2 版） 一书中提到4，计算几 何研究的典型问题由几何基元（ geometric primitives） 、 查找、优化等问题类组成。其中： （1）几何基元包括凸壳和 voronoi图、多边形的三角剖分、划分问题与相交问题； （2）几何查找包括点定位、可视化、区域查找等问题； （3）几何优化包括参数查找和线性规划。 计算几何的新近发展包括几何抽样理论、计算实代数几何、计算拓扑、运动规划、 并行计算几何、隐藏面的移动、结构和图形、网络生成以及计算机视觉中的几何问题 等。这些问题在自然科学的各个领域的应用将推动这些学科的进一步发展，其中包括 激光加工学科领域。 1.3 激光切雕加工软件功能概述 激光切雕加工软件的主要功能为提供方便的加工轨迹编辑环境、 根据加工轨迹控制 4 数控机构按照特定的规律进行运动并实现激光器的相应动作、监控加工参数的变化， 实现系统的反馈功能。其功能构架如图 1- 2 所示： 图 1- 2 激光切雕加工软件构架图 现具体说明其功能模块如下： （1）加工轨迹编辑部分 提供良好的人机界面，实现有关的加工数据的输入与编辑功能。对于复杂加工轨 迹， 目前通常采用图形、 图像文件的方式输入， 其中常用的格式有 bmp 图像格式、 jpeg 图像格式、plt 矢量文件格式、autocad下的 dxf 文件格式以及 window系统所支持 的 truetype 字体等。同时提供各种图形图像以及加工轨迹的编辑功能，使之适合激光 加工的需求。 （2）数据处理部分 根据激光切雕加工系统的特性以及要求，对输入的数据进行处理和变换，以实现 良好的加工效果。同时对加工的方式、路径、速度以及功率等加工参数进行选择和处 理，以实现高效的输出。 （3）输出控制部分 完成显示输出、加工数据保存输出、运动机构的运动控制、激光器的动作控制以 及加工参数的实时反馈。 1.4 图形优化算法对激光加工质量和效率的影响 在激光加工中，影响激光切雕加工质量和效率的主要因素如下2： （1）激光束的能量和光束模式； （2）激光束的聚焦特性； 键盘输入 鼠标输入 文件输入 扫描仪输入 图形编辑 图像编辑 图像图形处理 加工路径选择 加工参数控制 显示输出 运动机构控制 激光器控制 加工参数反馈 激光输出 图形图像输入 加工轨迹编辑 数据处理 输出控制 5 （3）运动机构的精度； （4）光路系统； （5）激光束与工件的相对运动速度； （6）材料本身的特性； （7）辅助设备； （8）软件的功能特性。 上述因素可以归结为两大类，即硬件因素和软件因素。对于硬件因素，有些得益 于技术的进步导致新材料、高精度设备的出现使得加工质量和效率出现质的飞跃；但 基于同样硬件条件下，良好的软件功能更利于加工方式的智能控制，高效率的算法可 以更好的提高加工质量和加工效率，产生意想不到的经济效益。 1.5 课题的来源、研究内容和意义 本课题是华中科技大学激光国家工程研究中心的重点研究方向之一。主要为如何 将激光技术与传统数控技术以及图形计算几何算法进行结合，如何优化激光切雕加工 软件的输出效果和效率。本课题的研究有助于弥补目前国内激光切雕加工系统中软件 功能部分的空缺，对于激光切雕加工系统的高效化有一定的作用。 本文的主要研究内容如下： (1) 分析和研究了 dxf 文件图形的结构， 设计了适合于激光加工软件的 dxf 文件 接口程序，将 autocad 图形直接应用到了激光加工软件中。 (2) 研究了 autocad中面域图元的作图原理和技术， 设计了 dxf 文件中面域图元 的提取与优化算法，该算法可用于激光加工中针对封闭图元的连续加工。 (3) 研究了基于多图元复杂 dxf 文件的图元优化排序算法，可以在激光切割软件 中对图元输出顺序进行优化和重新排序，减少空走行程，提高加工效率。 (4) 研究了多边形中轴的原理和中轴生成算法， 并将其应用在激光标刻过程中实现 对边缘轮廓直接偏置的螺旋路径填充加工方式中，该填充方式比传统的扫描方式可以 保持图形的边缘更光滑，无锯齿现象。 6 2 激光加工软件中 dxf 文件接口的设计与实现 计算机矢量图形的生成可以通过许多绘图软件实现，如 autocad2000、 coreldraw 10 等得到，用 cad 图形标准数据交换格式dxf 格式可以保存这些图形的精确数 据，再通过 dxf 文件接口读取这些图形数据，实现图形加工。 dxf 为国际知名的 autocad 软件所采用的一种重要图形数据存储文件。dxf 虽 然不是标准，但由于 autocad 系统的普遍应用，使得 dxf 成为事实上的数据交换标 准。dxf 是具有专门格式的 ascii 码文本文件，它易于被其它程序处理，主要用于实 现高级语言编写的程序与 autocad 系统的连接，或其它 cad 系统与 autocad 系统 交换图形文件67。 2.1 dxf 文件概述 一个完整的 dxf 文件分为五个区段和一个文件结尾组成的。其顺序如下： （1）标题段（header） ，记录autocad 系统的所有标题变量的当前值或当前状态。 这些标题变量记录了 autocad 系统的当前工作环境。例如，autocad 版本号、插入 基点、绘图界限、snap 捕捉的当前状态、栅格间距、式样、当前图层名、当前线型和 当前颜色等； （2）表段（tables） ，包含了四个表，每个表又包含可变数目的表项。按照这些表 在文件中出现的顺序，它们依次为线型表、图层表、字样表和视图表； （3）块段（blocks） ，记录定义每一块时的块名、当前图层名、块的种类、块的插 入基点及组成该块的所有成员。块的种类分为图形块、带有属性的块和无名块三种。 无名块包括用 hatch命令生成的剖面线和用 dim 命令完成的尺寸标注； （4）实体段（entities） ，记录了每个几何实体段的名称、所在图层的名称、线型 名、颜色号、基面高度、厚度以及有关几何数据； （5） 对象区段 （objects） ， 适用于非图形对象。 这些出现在 dxf 文件的 objects 区域中的组码被图元定义表中的 autolisp 和 objectarx 应用程序使用。 （6）文件结束，字符串“eof”标识文件结束。 7 2.1.1 dxf 文件的组码和组值 dxf 文件每个段的数据由顺序存放的若干个组构成， 每个组在 dxf 文件中占有两 行。组的第一行为组代码，它是一个非零的正整数，相当于数据类型代码，每个组代 码的含义是由 autocad系统约定好的，以 fortran “i3”格式（即向右对齐并且用 三字符字段填满空格的输出格式）输出。组的第二行为组值，相当于数据的值，采用 的格式取决于组代码指定的组的类型。组代码和组值合起来表示一个数据的含义和它 的值。组代码范围见表 2- 1。需要注意的是，在 autocad 系统中组代码既用于指出如 表 2- 1 所示的组值的类型，又用来指出组的一般应用（如表 2- 2） 。组代码的具体含义 取决于实际变量、表项或元素描述，但“固定”的组代码总具有相同的含义，如组代 码“8”总表示图层名。 表 2- 1 组码范围及组值数据类型说明 组码范围 组值数据类型 09 字符串 1059 浮点数 6079 整数 210239 浮点数 999 注释文本 表 2- 2 常用组码及其组值定义 组码 组值定义 0 标识一个实体、表入口或文件分隔符的开始，跟在后面的文本值指示是哪一个 2 一个名称、属性标志、块名等 8 图层名 10，20，30 初始 x，y，z 坐标（线或文本实体的起点、圆中心等） 11，21，31 终点 x，y，z 坐标 100 子类标记（(acdbline)） 62 颜色号 72 顶点数 2.1.2 段结构分析 一个 dxf 不必设置所有段。若没有设置 header段变量，整个 header 段可被 忽略。段与段之间有一定的先后次序。若图形中没有使用任何块定义，可忽略整个 8 blocks 段；若图形中使用块定义，blocks 段必须出现在 entities 段前，块定义 不能嵌套。每一个段都有段开始组码对和段结束组码对。最后，文件结束处必须出现 eof 项。 段开始组码对为： 0 section 段结束组码对为： 0 endsec 表 2- 3 以最常用的实体段（entities）说明段内的数据组织方式： 表 2- 3 实体段组码说明 序号 段内数据 说明 1 0 entities 段开始 2 section 3 2 4 entities 5 0 每一个图元定义为一个条目 6 如 line、circle、arc、point、spline 7 5 8 9 100 10 acdbentity 11 8 12 0 代表缺省图层 13 6 14 15 62 16 17 100 18 acdb 19 20 起止点坐标、方向导矢、凸度等 21 描述其它图元 22 0 23 endsec entities 段结束 9 2.2 多义线图元 2.2.1 多义线图元的基本特点 多义线（lwpolyline）是 dxf 中的一种重要图元，通常由连续的直线段和圆弧首 尾相连构成，因此读取这样的图元数据对于连续加工有重要意义。多义线图元在 dxf 文件中存储的信息较多，与几何特性有关的数据主要有 5 个： （1）各个顶点的坐标值， 分别保存在 10 组码和 20 组码中； （2）凸度值，保存在 42 组码中。凸度指一段圆弧所 包含的角度的 18 的正切值，当弧从起点到终点为顺时针时，凸度为负值，0 凸度表 示直线段，1 凸度表示半圆； （3）多义线的封闭性，保存在 70 组码中，其对应的组值 为 0 或 1，分别表示不封闭、封闭多义线； （4）图层，图层名的组码为 8，其对应的组 图 2- 1 多义线数据示例，右上角为对应多义线图形，左边为 dxf 文件数据及说明 10 值为“0”时，表示缺省图层。图层信息可以实现对图元的分类。 （5）顶点数，组码为 90。读取顶点数可以在读取顶点坐标值前分配足够的临时存储空间。图 2- 1 表示了一 个多义线图元及其组码数据。 2.2.2 凸度及其计算 凸度在 dxf 文件中的定义是：弧的 0.25 *（被包括的角度）的正切，如果弧从开 始到结束为顺时针方向，则为负值，反之为正值。毫无疑问，每一个凸度组码的定义 与它的起止点都是相关的。设多义线上有一段圆弧的起点定义为 a，凸度值为 a，终点 为 b。这段弧属于某个圆，我们须根据定义求出构成此弧的圆心和半径。按照定义可 先求出该弧被包括的角度，定义该角度为。则从 a 到 b 连线= arctan（a）* 4，由 该角度可求出半径和可能的两个圆心位置。过程如下： 如图 2- 2 所示，设圆 1 和圆 2 是可能包含 ab 连线的两个大小相等的圆，它们的圆 图 2- 2 包含弦 ab的两个圆 心分别是 r1、 r2，设它们的半径为 r，根据 a 点的凸度值的大小和正负，ab 间的连 线可能是弧 ap1b、aq1b、ap2b、aq2b 中的某一段。ab 弧的圆心究竟是 r1，还是 r2，则视的大小和正负而定，由定义可推它们之间的关系如下（从上面的求值可 知（- 22） ） ： 从 a 到 b 的连线： （1 ） 0：| , 连线为弧 a p2b， 圆心为 r2； | next; bfinish = true; q = q- next; while(q != null); if(!bfinish) break; while(链表不为空且图元数目大于 2 遍历 p 的全部后继结点； do if(q 是 head 的前驱) 将 q 插入到 head 前 bfinish = true; break; q = q- next; while(q != null); if(!bfinish) break; 3.3.2 有向环的数据输出 将面域中各图元的几何信息输入到临时文件中供激光切割软件读取时不仅要恢复 转换直线数据到临时 文件 转换样条曲线数据到 临时文件 链表未完 s t r a i g h t - c u r v e e l l i p s e - c u r v e i n t c u r v e - c u r v e 遍历链表 转换圆和椭圆数据到 临时文件 图 3- 6 解析面域数据流程图 22 原始图元的数据类型，还要保持加工的连续性，因此不同图元的数据输出要考虑差别 性。首先遍历链表中的全部结点，判断 node- ntype 为以下情况（如图 3- 6） 。 (1) 输出图元如果是直线，读取每个 node 的起点和最后一个 node 的终点，连接成 一条直线； (2) 输出图元如果是圆或椭圆，读取圆和椭圆的圆心坐标，再根据起止点算出起始 角和终止角，如果是椭圆还要根据长度轴的比例计算出旋转角度；13 (3) 输出图元如果是样条曲线9，逐个读取结点值和控制点坐标，输出到临时文件 中。 输出的临时文件数据按格式( n, px, py )组织。其中 n为指令类型，取值为 0、1、2、 3；0 代表 moveto，1 代表 lineto，2 代表样条曲线，3 代表圆弧；px和 py分别是 当前点的坐标值。只需要再根据用户指定的精度，设计出针对 da 卡的插补算法就可 以实现激光输出了1213。未经过面域处理的封闭图形切割时仍然与作图时的图元顺序 有关（如图 3- 7） ，切割过程中光头移动不连续且需要多次开关光；而该封闭图形被编 辑为面域后，针对面域的切割刚好执行一次完整的行走路径，并最终回到起点（如图 3- 8） ，切割过程中光头的移动路径是连续的，无需重复复位，且只需一次开关光，因 此提高了切割效率。 图 3- 7 未经过面域编辑时的切割次序 图 3- 8 经过面域编辑后的切割次序 3.4 本章小结 本章对 autocad 中一种重要的作图技术面域（region）进行了研究，设计了 能提取 dxf 文件中面域实体数据的有效算法以及针对面域的路径优化算法。本章还为 二维激光加工软件设计了一个良好的数据模型，该模型可以直接应用于第四章针对 dxf 文件的路径优化算法的预处理过程中。 23 4 基于多图元复杂 dxf 文件的路径优化技术 加工路径优化类似于经典的旅行商问题( traveling salesman problem ，tsp) ，属于 np 难问题8。其一般化的数学模型可以用图的理论表示如下：存在图 g = v ， e ， v 为组成图的结点， e 为连接这些结点的边，寻找一条最小耗费的路径，使得这条路径 只对每一个结点穿行一次18。在大多数这类问题中，随着求解问题规模的扩大，得到最 优解往往意味着无法完成的计算量。因此，工程上往往寻找一种能够在可约束条件下的 优化算法，该算法往往能够解决一些具体问题的路径优化问题。本章正是遵循这个原则， 在 dxf 文件预处理的基础上，提出了专门针对复杂 dxf 文件的路径优化算法。 从 dxf 文件中提取出所有加工图元，这些图元可以分为两类，即封闭图元和非封 闭图元。进行激光切割和标刻时，封闭图元和非封闭图元的加工方式不同，封闭图元 要考虑轮廓和填充扫描线，非封闭图元只需要考虑轮廓即可。如果将填充扫描线的优 化算法另外考虑，仅针对行走路径，减少激光空走行程也是提高加工效率的重要途径。 实际加工过程中，从每个图元中得到连续的轮廓路径，再将所有的轮廓路径按一定的 顺序连接起来，而连接这些轮廓路径的线段在激光加工中对应于空走行程，一般可以 将输出脉冲定得很高以实现较快的加工速度 。 4.1 dxf 文件中离散图元的连接处理 4.1.1 基本概念 (1) 图组：由连续图元按逆时针或顺时针方向进行连续排列的集合（如图 4- 1） ，是 图 4 - 1 图组的图元排序方式 路径优化的基本单元。一个图组可以是封闭的，也可以是不封闭的。 24 ( 2 ) 控制点：在排序过程中，为了简化计算，将每一个图元的起止点设定为控制 点。控制点是路径优化过程中比较的依据，一个图组中至少有 2 个这样的控制点。 ( 3 ) 参考点：参考点是行进过程中每次进入下一个图组前的位置，它也是上一个 图组的终点，它与下一个图组之间的路径是空走行程。初始参考点可以设为原点。 4.1.2 图元连接预处理 dxf 文件中图形元素以图元绘制先后顺序为依据的记录顺序以及 dxf 对某一图 元的控制点顺序存在默认排序的情况（如 arc 在 dxf 中默认为逆时针方向、line为 从起点到末点等） ，使得对 dxf 解析获得的各图元信息成为无序性排列，导致按此转 化进行的绘图或加工过程中路径的随机性和无序性，使得工作过程中的无效行程大大 增加。由于在 entities 段中对所记录的图形元素任意交换其出现的先后顺序以及对 其中某一图元交换其控制点排列顺序不影响 dxf 文件的有效性。因此在提取 dxf 文 件中的图形元素数据时，对无序的离散图元进行连接处理之后再应用排序算法，可以 提高排序算法的效率。 连接处理的过程要考虑各种图形元素的特性，同时为了提高计算速度，采取“边 读取边排序”的方式，排序算法则使用基于双向链表的二路插入排序算法。具体实现 过程如下： (1) 将非封闭图组和封闭图组都设计为双向链表， 分别用头指针和尾指针来表示加 工方向上的第一个图元的起点和最后一个图元的终点，每一个连续加工序列都唯一对 应这样一个双向链表； (2) 按 dxf 文件中 entity 段中的图元顺序逐个读取每一图元的属性值，进行分 类处理： 1) 如果该图元是直线，则将直线的首末点与每一个双向链表的头指针和尾指针分 别作比较，如果该直线的一端与头指针相同，则插入到队头，修改头指针指向该直线 的另一端；否则如果该直线的一端与尾指针相同，则插入到队尾，修改尾指针指向该 直线的另一端；否则就以该直线为第一个图元建立新的双向链表； 2) 如果该图元是非封闭的圆弧、曲线段，则处理方法与直线类似，只不过圆弧要 通过起止角计算起止点； 25 3) 如果该图元是非封闭多义线，则除了比较起止点外，如果需要交换起止点，则 还需要将每一个图元按第一个与最后一个，第二个与倒数第二个，的顺序进行 交换； 4) 如果该图元是一个封闭图元，如圆、封闭曲线、封闭多义线、面域等，就新建 一个双向链表，按这些封闭图元的原始顺序记录到链表中； (3) 用一个模板数组存储这些双向链表。 上述算法在排序时只需比较头指针和尾指针， 最坏的情况每个双向链表需要比较 4 次，假设双向链表的数目是 m（m n） ，则其算法复杂度为 o（mn） ，比传统的搜索算 法 （复杂度为 o （n2） ） 效率高， 尤其是连续图元较多的情况下 （m d1，则 pn 1变为原图组的起始点，p0变为原图组的末点，将图组控制点顺序改 图 4- 2 非封闭图组控制点到参考点的距离 27 为 pn- 1、pn- 2、p0，修改图组中首尾队列的指针。 (2) 对于封闭图组，将参考点与每一个控制点计算，得到d0，d1，dn- 2，取 d = min ( di ) ( i = 0、1、n- 2)，将头指针从 p0移到 pi，将尾指针从 pn- 2移到 pi- 1，控 制点加工顺序变为 pi、pi+1、pn- 1、p0、pi- 1。 图 4- 3 封闭图组部分控制点到参考点的距离 (3) 另外，如果该封闭图组是一个单独的圆或椭圆，则只需要根据参考点到圆心的 连线与圆方程计算交点 p0，就可以将其作为加工起点。 图 4- 4 通过椭圆圆心与参考点连线得到控制点坐标 按照上述步骤， 得到一幅dxf 文件图纸在路径优化前后的实际行走路径对比图 （图 4- 5 和图 4- 6 中虚线表示行走路径） ： 图 4- 5 路径优化前实际行走路径 28 图 4- 6 路径优化后实际行走路径 4.3 结论及效果显示 由于 autocad软件中没有图形编组的功能，因此，可以使用与面域（region）绘 图技术（见第 3 章）相结合的方式使得图形编组在 dxf 文件中容易实现。被面域处理 过的 dxf 优化时具有良好的性能，可以比未处理的 dxf 文件优化效率更高。 由上述路径优化算法可知： (1) 经过路径优化后，dxf 文件中图元轮廓连接路径得到优化。表 4- 1 显示了优化 前后的空行程明显减少，加工效率被大大提高； (2) 在图形处理时创建的面域越多，得到的路径优化效果越好，因此在 autocad 编辑环境中应该利用面域的运算功能多作有效的图形处理。 (3) 该算法使用队列存放图组和图元，保证了“先进先出”的行走顺序，同时改变 图元顺序只需要修改队头指针和队尾指针，减少计算量，算法效率较高。 表 4- 1 不同图元数量下的优化效率对照表 图元数量 优化前空行程（mm） 优化后空行程（mm） 优化效率 100 8815.254 2781.353 68.448% 1000 64818.563 11747.811 81.876% 2000 84518.563 15547.044 91. 603% 4.4 本章小结 本章所提出的优化算法在本质上是递归的、有效的。该算法在确定了某一起始参考 点后时间复杂度为 o ( n 2 )，这在实际的生产过程中是能被操作人员所接受的。通过对 29 dxf 文件中的图元及其控制点的优化排序，实现了按绘图或加工方向的图元优化排序 的数据输出，应用于激光加工软件中，优化了其图形雕切时的路径顺序，减少了大量 无效空走行程，提高了雕切效率，降低了经济成本。 对特别复杂的 dxf 文件的路径优化算法还可以考虑人工智能算法等，已经有一些 类似的成果，如文献15讨论的遗传算法可以将时间复杂度提高到 o（nlog(n)） ，文献 16还讨论了六种可应用于该类问题的智能算法，但在工程实现上较为复杂，留待以后 作进一步研究。 30 5 中轴线算法及任意多边形螺旋线填充算法 激光打标和雕刻过程中，对多边形的填充往往是用扫描填充算法2122，又分为单 向扫描、来回扫描、z 形扫描等，并且有很多快速算法得以实现。而螺旋线填充算法 在刺绣和快速成型领域得到广泛应用，如果能够在激光领域借鉴刺绣过程中的螺旋路 径连接技术，应用到激光雕切加工软件和打标软件中，可以实现填充边缘光滑，填充 图案美观的加工效果。 螺旋线填充的主要思想就是按一定偏置距离沿着边界轮廓线由外向内或由内向外 偏置，直到出现两条偏置线碰撞为止。封闭区域的轮廓线通过读取 dxf 文件可以很容 易得到，检测偏置线的碰撞是该算法实现的关键。直接检测法计算量太大，一般都是 使用多边形 voronoi图算法检测偏置，并且效果很好，但该算法计算过程复杂，效率较 低。由于激光加工过程中，圆弧、自由曲线等都被离散成只包含直线段的简单多边形。 实践证明，使用多边形的中轴或直骨架也可以实现偏置线的碰撞检测，而且算法效率 较高。 本章研究了简单多边形的中轴线算法， 并利用计算出的中轴骨架对多边形轮廓进行 偏置，得到螺旋线填充效果。 5.1 多边形中轴线定义 5.1.1