面向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.