面向PCB打印的区域填充算法

王印签，蒋 辉，荆于勤

(重庆理工大学计算机科学与工程学院，重庆 400054)

随着电子技术的迅速发展，用于印制电路板(PCB)行业的设备与技术突飞猛进，特别是随着“专用”和“超级喷墨”技术的出现，以及喷射所用的打印头和专用油墨的改进和突破，可以得到3～5 μm的线宽［1］。这些技术、工艺和应用条件的不断成熟，为喷墨打印技术在PCB领域中的应用推广提供了基础和保证。

PCB喷印制作的生产流程总体分为6个步骤，如图1所示。PCB制作的过程无需人工干预，并且制作完成的总时间一般在1～2 min，其中在喷印的同时进行油墨固化，节省了大量时间。与传统PCB丝网印刷相比，喷墨打印技术具有诸多显著优点，比如极大地简化了PCB加工生产过程、体积小、周期短、成本低、环境友好等。采用数字喷墨打印技术明显提高了层间的对位精度和图形的印刷精度，大大提高了电路板制作的效率和质量［2］。

图1 PCB喷印制作流程

矢量图形的光栅化是将矢量图形元素转化成具有一定线宽的图像矩阵，从而使整幅图面在显示和打印时能有一个统一的表达形式。矢量基本图形一般包括点、直线段、圆弧、折线段以及区域填充。在矢量图形光栅化过程中，区域填充尤为复杂，其填充的效率和质量直接影响光栅化的成败。本文首先将原始的扫描线算法应用到Gerber光栅化中，并针对该算法在填充过程中出现的错误和低效率的问题，对原算法进行改进，最后形成适用于Gerber文件的光栅化算法。根据客户的分辨率精度要求，最大化地提高光栅化图形的质量，同时提升Gerber光栅化的效率。

1 光栅化区域填充

1.1 Gerber文件

Gerber是工业标准RS-274X格式中一种数据文件，被广泛应用于PCB制造业中。区域填充在Gerber文件中存在专用标志，其语句如表1所示。

表1 Gerber语句

表1的Gerber语句所绘制的图形如图2所示。此实例可以简单了解Gerber语句的用法［3］。Gerber是一套完整的规范化数据格式，包含了许多其他的语句和各种详细的用法，比如Gerber语句“%MOMM%”表示设置文件的数据单位为mm。表1描述的填充图形为简单的连通区域，但在Gerber文件中存在大量复连通区域，如图3所示，它是影响填充以及Gerber光栅化的关键图形。本文以Gerber中的复连通区域填充为重点，详细描述改进的区域填充算法。

1.2 Gerber光栅化

矢量图形光栅化作为PCB喷印制作中最重要的一步，其图像生成的精度直接影响到最后的打印效果。由于PCB的喷印制作技术作为行业的待开发领域，本文所设计的Gerber光栅化主要分为4个步骤(见图4):

1)解析Gerber文件。根据Gerber语法规则，将Gerber文件的数据按类型分类存储，将需要填充的数据存放到指定位置。

2)分析填充数据。统计填充数据，获得矩阵尺寸，设定填充参数。

3)区域逐个填充。调用填充函数，对区域逐个进行填充。

4)生成图像矩阵。区域填充数据操作完成后即得到图像矩阵。

图2 Gerber语句示例

图3 填充复连通区域

图4 Gerber光栅化步骤

2 改进的区域填充算法

2.1 原算法问题分析

区域填充作为Gerber文件中最为重要的图形之一，其填充的效果、精度直接影响光栅化的成败。目前的填充算法主要分为两大类:扫描线填充算法［4］和种子填充算法［5］。前者主要利用扫描线的连贯性，按扫描线顺序对图形进行填充;后者主要利用图形空间的连贯性，从内部一个种子点出发测试点的连贯性。但是由于种子填充算法采用了大量的出入栈操作，不仅浪费了大量的空间，而且操作重复，使得种子填充算法的效率极其低下［5］。

扫描线填充算法一般包括4个步骤，如图5所示。

1)求交。遍历整个扫描线，计算扫描线与多边性区域的交点，并存入扫描行链表。

2)排序。遍历整个交点链表，对每一行的交点按照x的大小各自进行排序。

3)配对。对每个扫描行的交点两两进行配对，形成填充区间。

4)填充。对填充区间进行二值填充。

图5 扫描线填充算法流程

工业设计中对Gerber文件有高精度要求。假设2点间的最小距离为 20 μm，按照分辨率360DPI、720DPI、1440DPI光栅化得到的 2 像素点距离分别为 70.56、35.28、17.64 μm。如图 6 所示，每一个方格表示一个像素，轮廓记录的是待填充多边形。对于图6，如果采用1440DPI光栅化，2像素点的距离为17.64 μm，由图6可见任2个坐标点均在不同的像素点上。图7中，如果采用720DPI进行光栅化，则存在2坐标点落在同一个像素点，如C和D，E和F，I和J，此时采用扫描线算法将导致统计的交叉点数目出现错误，最后填充失败。

图6 1440分辨率效果图

图7 720分辨率效果图

本文针对扫描线填充算法在Gerber光栅化应用上的劣势，对扫描线填充算法加以改进，达到对包含任意多边形均能实现有效光栅化的目的。

2.2 基于阈值的自适应填充算法

根据系统的分辨率需求，计算当前Gerber光栅化最合适的阈值。几种经常使用的分辨率与阈值对应关系如表2所示。按照不同的分辨率可以计算出阈值 α =25.4 ×1 000/DPI。

表2 分辨率与阈值对应关系

根据用户选择的分辨率确定阈值，对上图的坐标进行判断，最后得到用户选择的简化坐标，如图8所示。

在扫描点链表的过程中，根据系统的分辨率要求，过滤掉当前数据链表中不必要的坐标点，既提高了算法的执行效率，又提高了Gerber光栅化的正确率。

图8 用户选择的简化坐标

算法中定义的边节点的数据结构如下:

NEXT xmin Δx ymax

其中:xmin为当前扫描线与边的交点坐标;Δx为纵坐标Y每增大1时X的增量;ymax为该边所交的最高扫描线;NEXT为下一条边。

基于阈值的自适应填充算法步骤:

1)初始化。置有序边表NET表为空，计算当前分辨率的阈值α。

2)利用阈值判断是否删掉当前坐标点。扫描点链表，将第1个坐标点记为PRE，将第2个坐标点记为TEMP，计算2点PRE和TEMP的欧氏距离DIST。如果DIST≤α，则忽略当前节点TEMP，并将第3个坐标点作为TEMP;如果DIST≥α，则将PRE和TEMP记为边ET，并加入到NET链表中。最后生成有序边表。

3)扫描当前行的有序边表NET，建立活性边表AET。

4)由AET表取出交点进行(奇偶)配对获得填充区间，并对区间进行填充。

5)当y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。如果相应的边表ET不空，则将其中的结点插入AET表，形成新的AET表。

6)如AET表不空，则转步骤3)，否则结束。

为了方便活性边表的建立与更新，可为每一条扫描线建立一个边表(ET)，存放在该扫描线第1次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的边表中。

为了提高速度，假定当前扫描线与多边形某一条边的交点的x坐标为xi，则下一条扫描线与该边的交点不需要重新计算，直接增加一个Δx得到。对于直线ax+by+c=0，Δx=-b/a为常数。在使用增量法计算时，需要计算一条边与扫描线相交的范围，以便及时把它从活性边表中删除。正确求得扫描线与区域内外轮廓线的交点是算法成败的关键。

3 算法分析

基于阈值的自适应填充算法将整个光栅化的过程分为6个步骤，这种算法实现起来比较快，填充效果非常可观。下面采用PCB实际制版图形的填充部分进行实验。实验图形分别为高精度填充区域和空心填充区域图形，算法测试效果见图9～11。

图9 原算法填充效果

图10 新算法填充效果

图11 原算法填充效果

图9、10为高精度填充区域。Gerber文件记录的坐标点间距小于当前所选择的分辨率的像素距离，原算法填充导致图形填充出现错误，如图9所示。新改进的填充算法效果达到了正确光栅化的目的，如图10所示。图11、12中包含多个空心区域，原算法不能正确填充(如图11所示)。新改进算法的填充效果达到了正确光栅化的目的，接近原始的矢量图形，如图12所示。

图12 新算法填充效果

根据客户光栅化的要求，以阈值作为度量标准，适当简化Gerber文件的部分坐标点，达到了提高效率的目的。效率测试结果如表3所示。

表3 测试图像填充时间比较

实验结果表明，改进算法的填充效果大大的优于原来的填充算法，改进算法实用性相当高。

4 结束语

本文改进的扫描线填充算法，利用客户精度需求对Gerber文件简化处理，在保证填充正确的同时大大缩短了Gerber光栅化的时间。目前，该填充算法已经在Gerber文件光栅化中得到了实际应用。实践证明，本算法对Gerber文件的各种多边形区域都能准确无误地填充，满足了客户的需求，具有较大的应用价值和市场前景。

［1］Dunlavey M R.Efficient Polygon-filling Algorithm for Raster Displays［J］.ACM Transactions on Graphics，1983，2(4)：264-273.

［2］林金堵.喷墨打印技术在PCB中的应用前景［M］.印制电路信息，2008(4)：8-14.

［3］陈优广，顾国庆，王玲.一种基于缝隙码的区域填充算法［J］.中国图象图形学报，2007，11(12)：121-124.

［4］宋斌，郑建生，代永红.基于区域填充算法的PCB网络提取［J］.计算机工程与设计，2006，27(4)：89-94.

［5］苏小红.计算机图形学实用教程［M］.2版.北京：人民邮电出版社，2010.

［6］马辉，陆国栋，谭建荣，等.基于顶点与邻边相关性的多边形填充算法［J］.中国图象图形学报，2004，11(9)：55-60.