王印簽，蔣 輝，荊于勤

(重慶理工大學(xué)計算機科學(xué)與工程學(xué)院，重慶 400054)

隨著電子技術(shù)的迅速發(fā)展，用于印制電路板(PCB)行業(yè)的設(shè)備與技術(shù)突飛猛進(jìn)，特別是隨著“專用”和“超級噴墨”技術(shù)的出現(xiàn)，以及噴射所用的打印頭和專用油墨的改進(jìn)和突破，可以得到3～5 μm的線寬［1］。這些技術(shù)、工藝和應(yīng)用條件的不斷成熟，為噴墨打印技術(shù)在PCB領(lǐng)域中的應(yīng)用推廣提供了基礎(chǔ)和保證。

PCB噴印制作的生產(chǎn)流程總體分為6個步驟，如圖1所示。PCB制作的過程無需人工干預(yù)，并且制作完成的總時間一般在1～2 min，其中在噴印的同時進(jìn)行油墨固化，節(jié)省了大量時間。與傳統(tǒng)PCB絲網(wǎng)印刷相比，噴墨打印技術(shù)具有諸多顯著優(yōu)點，比如極大地簡化了PCB加工生產(chǎn)過程、體積小、周期短、成本低、環(huán)境友好等。采用數(shù)字噴墨打印技術(shù)明顯提高了層間的對位精度和圖形的印刷精度，大大提高了電路板制作的效率和質(zhì)量［2］。

圖1 PCB噴印制作流程

矢量圖形的光柵化是將矢量圖形元素轉(zhuǎn)化成具有一定線寬的圖像矩陣，從而使整幅圖面在顯示和打印時能有一個統(tǒng)一的表達(dá)形式。矢量基本圖形一般包括點、直線段、圓弧、折線段以及區(qū)域填充。在矢量圖形光柵化過程中，區(qū)域填充尤為復(fù)雜，其填充的效率和質(zhì)量直接影響光柵化的成敗。本文首先將原始的掃描線算法應(yīng)用到Gerber光柵化中，并針對該算法在填充過程中出現(xiàn)的錯誤和低效率的問題，對原算法進(jìn)行改進(jìn)，最后形成適用于Gerber文件的光柵化算法。根據(jù)客戶的分辨率精度要求，最大化地提高光柵化圖形的質(zhì)量，同時提升Gerber光柵化的效率。

1 光柵化區(qū)域填充

1.1 Gerber文件

Gerber是工業(yè)標(biāo)準(zhǔn)RS-274X格式中一種數(shù)據(jù)文件，被廣泛應(yīng)用于PCB制造業(yè)中。區(qū)域填充在Gerber文件中存在專用標(biāo)志，其語句如表1所示。

表1 Gerber語句

表1的Gerber語句所繪制的圖形如圖2所示。此實例可以簡單了解Gerber語句的用法［3］。Gerber是一套完整的規(guī)范化數(shù)據(jù)格式，包含了許多其他的語句和各種詳細(xì)的用法，比如Gerber語句“%MOMM%”表示設(shè)置文件的數(shù)據(jù)單位為mm。表1描述的填充圖形為簡單的連通區(qū)域，但在Gerber文件中存在大量復(fù)連通區(qū)域，如圖3所示，它是影響填充以及Gerber光柵化的關(guān)鍵圖形。本文以Gerber中的復(fù)連通區(qū)域填充為重點，詳細(xì)描述改進(jìn)的區(qū)域填充算法。

1.2 Gerber光柵化

矢量圖形光柵化作為PCB噴印制作中最重要的一步，其圖像生成的精度直接影響到最后的打印效果。由于PCB的噴印制作技術(shù)作為行業(yè)的待開發(fā)領(lǐng)域，本文所設(shè)計的Gerber光柵化主要分為4個步驟(見圖4):

1)解析Gerber文件。根據(jù)Gerber語法規(guī)則，將Gerber文件的數(shù)據(jù)按類型分類存儲，將需要填充的數(shù)據(jù)存放到指定位置。

2)分析填充數(shù)據(jù)。統(tǒng)計填充數(shù)據(jù)，獲得矩陣尺寸，設(shè)定填充參數(shù)。

3)區(qū)域逐個填充。調(diào)用填充函數(shù)，對區(qū)域逐個進(jìn)行填充。

4)生成圖像矩陣。區(qū)域填充數(shù)據(jù)操作完成后即得到圖像矩陣。

圖2 Gerber語句示例

圖3 填充復(fù)連通區(qū)域

圖4 Gerber光柵化步驟

2 改進(jìn)的區(qū)域填充算法

2.1 原算法問題分析

區(qū)域填充作為Gerber文件中最為重要的圖形之一，其填充的效果、精度直接影響光柵化的成敗。目前的填充算法主要分為兩大類:掃描線填充算法［4］和種子填充算法［5］。前者主要利用掃描線的連貫性，按掃描線順序?qū)D形進(jìn)行填充;后者主要利用圖形空間的連貫性，從內(nèi)部一個種子點出發(fā)測試點的連貫性。但是由于種子填充算法采用了大量的出入棧操作，不僅浪費了大量的空間，而且操作重復(fù)，使得種子填充算法的效率極其低下［5］。

掃描線填充算法一般包括4個步驟，如圖5所示。

1)求交。遍歷整個掃描線，計算掃描線與多邊性區(qū)域的交點，并存入掃描行鏈表。

2)排序。遍歷整個交點鏈表，對每一行的交點按照x的大小各自進(jìn)行排序。

3)配對。對每個掃描行的交點兩兩進(jìn)行配對，形成填充區(qū)間。

4)填充。對填充區(qū)間進(jìn)行二值填充。

圖5 掃描線填充算法流程

工業(yè)設(shè)計中對Gerber文件有高精度要求。假設(shè)2點間的最小距離為 20 μm，按照分辨率360DPI、720DPI、1440DPI光柵化得到的 2 像素點距離分別為 70.56、35.28、17.64 μm。如圖 6 所示，每一個方格表示一個像素，輪廓記錄的是待填充多邊形。對于圖6，如果采用1440DPI光柵化，2像素點的距離為17.64 μm，由圖6可見任2個坐標(biāo)點均在不同的像素點上。圖7中，如果采用720DPI進(jìn)行光柵化，則存在2坐標(biāo)點落在同一個像素點，如C和D，E和F，I和J，此時采用掃描線算法將導(dǎo)致統(tǒng)計的交叉點數(shù)目出現(xiàn)錯誤，最后填充失敗。

圖6 1440分辨率效果圖

圖7 720分辨率效果圖

本文針對掃描線填充算法在Gerber光柵化應(yīng)用上的劣勢，對掃描線填充算法加以改進(jìn)，達(dá)到對包含任意多邊形均能實現(xiàn)有效光柵化的目的。

2.2 基于閾值的自適應(yīng)填充算法

根據(jù)系統(tǒng)的分辨率需求，計算當(dāng)前Gerber光柵化最合適的閾值。幾種經(jīng)常使用的分辨率與閾值對應(yīng)關(guān)系如表2所示。按照不同的分辨率可以計算出閾值 α =25.4 ×1 000/DPI。

表2 分辨率與閾值對應(yīng)關(guān)系

根據(jù)用戶選擇的分辨率確定閾值，對上圖的坐標(biāo)進(jìn)行判斷，最后得到用戶選擇的簡化坐標(biāo)，如圖8所示。

在掃描點鏈表的過程中，根據(jù)系統(tǒng)的分辨率要求，過濾掉當(dāng)前數(shù)據(jù)鏈表中不必要的坐標(biāo)點，既提高了算法的執(zhí)行效率，又提高了Gerber光柵化的正確率。

圖8 用戶選擇的簡化坐標(biāo)

算法中定義的邊節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下:

NEXT xmin Δx ymax

其中:xmin為當(dāng)前掃描線與邊的交點坐標(biāo);Δx為縱坐標(biāo)Y每增大1時X的增量;ymax為該邊所交的最高掃描線;NEXT為下一條邊。

基于閾值的自適應(yīng)填充算法步驟:

1)初始化。置有序邊表NET表為空，計算當(dāng)前分辨率的閾值α。

2)利用閾值判斷是否刪掉當(dāng)前坐標(biāo)點。掃描點鏈表，將第1個坐標(biāo)點記為PRE，將第2個坐標(biāo)點記為TEMP，計算2點PRE和TEMP的歐氏距離DIST。如果DIST≤α，則忽略當(dāng)前節(jié)點TEMP，并將第3個坐標(biāo)點作為TEMP;如果DIST≥α，則將PRE和TEMP記為邊ET，并加入到NET鏈表中。最后生成有序邊表。

3)掃描當(dāng)前行的有序邊表NET，建立活性邊表AET。

4)由AET表取出交點進(jìn)行(奇偶)配對獲得填充區(qū)間，并對區(qū)間進(jìn)行填充。

5)當(dāng)y=yi+1時，根據(jù)x=xi+1/k修改AET表所有結(jié)點中交點的x坐標(biāo)。如果相應(yīng)的邊表ET不空，則將其中的結(jié)點插入AET表，形成新的AET表。

6)如AET表不空，則轉(zhuǎn)步驟3)，否則結(jié)束。

為了方便活性邊表的建立與更新，可為每一條掃描線建立一個邊表(ET)，存放在該掃描線第1次出現(xiàn)的邊。也就是說，若某邊的較低端點為ymin，則該邊就放在掃描線ymin的邊表中。

為了提高速度，假定當(dāng)前掃描線與多邊形某一條邊的交點的x坐標(biāo)為xi，則下一條掃描線與該邊的交點不需要重新計算，直接增加一個Δx得到。對于直線ax+by+c=0，Δx=-b/a為常數(shù)。在使用增量法計算時，需要計算一條邊與掃描線相交的范圍，以便及時把它從活性邊表中刪除。正確求得掃描線與區(qū)域內(nèi)外輪廓線的交點是算法成敗的關(guān)鍵。

3 算法分析

基于閾值的自適應(yīng)填充算法將整個光柵化的過程分為6個步驟，這種算法實現(xiàn)起來比較快，填充效果非?？捎^。下面采用PCB實際制版圖形的填充部分進(jìn)行實驗。實驗圖形分別為高精度填充區(qū)域和空心填充區(qū)域圖形，算法測試效果見圖9～11。

圖9 原算法填充效果

圖10 新算法填充效果

圖11 原算法填充效果

圖9、10為高精度填充區(qū)域。Gerber文件記錄的坐標(biāo)點間距小于當(dāng)前所選擇的分辨率的像素距離，原算法填充導(dǎo)致圖形填充出現(xiàn)錯誤，如圖9所示。新改進(jìn)的填充算法效果達(dá)到了正確光柵化的目的，如圖10所示。圖11、12中包含多個空心區(qū)域，原算法不能正確填充(如圖11所示)。新改進(jìn)算法的填充效果達(dá)到了正確光柵化的目的，接近原始的矢量圖形，如圖12所示。

圖12 新算法填充效果

根據(jù)客戶光柵化的要求，以閾值作為度量標(biāo)準(zhǔn)，適當(dāng)簡化Gerber文件的部分坐標(biāo)點，達(dá)到了提高效率的目的。效率測試結(jié)果如表3所示。

表3 測試圖像填充時間比較

實驗結(jié)果表明，改進(jìn)算法的填充效果大大的優(yōu)于原來的填充算法，改進(jìn)算法實用性相當(dāng)高。

4 結(jié)束語

本文改進(jìn)的掃描線填充算法，利用客戶精度需求對Gerber文件簡化處理，在保證填充正確的同時大大縮短了Gerber光柵化的時間。目前，該填充算法已經(jīng)在Gerber文件光柵化中得到了實際應(yīng)用。實踐證明，本算法對Gerber文件的各種多邊形區(qū)域都能準(zhǔn)確無誤地填充，滿足了客戶的需求，具有較大的應(yīng)用價值和市場前景。

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

［2］林金堵.噴墨打印技術(shù)在PCB中的應(yīng)用前景［M］.印制電路信息，2008(4)：8-14.

［3］陳優(yōu)廣，顧國慶，王玲.一種基于縫隙碼的區(qū)域填充算法［J］.中國圖象圖形學(xué)報，2007，11(12)：121-124.

［4］宋斌，鄭建生，代永紅.基于區(qū)域填充算法的PCB網(wǎng)絡(luò)提?。跩］.計算機工程與設(shè)計，2006，27(4)：89-94.

［5］蘇小紅.計算機圖形學(xué)實用教程［M］.2版.北京：人民郵電出版社，2010.

［6］馬輝，陸國棟，譚建榮，等.基于頂點與鄰邊相關(guān)性的多邊形填充算法［J］.中國圖象圖形學(xué)報，2004，11(9)：55-60.