王印簽，蔣 輝，荊于勤

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

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

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

圖1 PCB噴印制作流程

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

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

1.1 Gerber文件

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

表1 Gerber語(yǔ)句

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

1.2 Gerber光柵化

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

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

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

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

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

圖2 Gerber語(yǔ)句示例

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

圖4 Gerber光柵化步驟

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

2.1 原算法問(wèn)題分析

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

掃描線(xiàn)填充算法一般包括4個(gè)步驟，如圖5所示。

1)求交。遍歷整個(gè)掃描線(xiàn)，計(jì)算掃描線(xiàn)與多邊性區(qū)域的交點(diǎn)，并存入掃描行鏈表。

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

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

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

圖5 掃描線(xiàn)填充算法流程

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

圖6 1440分辨率效果圖

圖7 720分辨率效果圖

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

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

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

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

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

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

圖8 用戶(hù)選擇的簡(jiǎn)化坐標(biāo)

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

NEXT xmin Δx ymax

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

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

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

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

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

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

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

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

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

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

3 算法分析

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

圖9 原算法填充效果

圖10 新算法填充效果

圖11 原算法填充效果

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

圖12 新算法填充效果

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

表3 測(cè)試圖像填充時(shí)間比較

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

4 結(jié)束語(yǔ)

本文改進(jìn)的掃描線(xiàn)填充算法，利用客戶(hù)精度需求對(duì)Gerber文件簡(jiǎn)化處理，在保證填充正確的同時(shí)大大縮短了Gerber光柵化的時(shí)間。目前，該填充算法已經(jīng)在Gerber文件光柵化中得到了實(shí)際應(yīng)用。實(shí)踐證明，本算法對(duì)Gerber文件的各種多邊形區(qū)域都能準(zhǔn)確無(wú)誤地填充，滿(mǎn)足了客戶(hù)的需求，具有較大的應(yīng)用價(jià)值和市場(chǎ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)廣，顧國(guó)慶，王玲.一種基于縫隙碼的區(qū)域填充算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2007，11(12)：121-124.

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

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

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