1.4　基本圖形生成技術(shù)

基本圖形生成技術(shù)主要包括掃描轉(zhuǎn)換概念、掃描轉(zhuǎn)換直線、掃描轉(zhuǎn)換弧、圖元屬性控制、填充、字符表示和輸出、二維裁剪和三維裁剪。

1.4.1　掃描轉(zhuǎn)換概念

在繪圖紙上，可在任意兩點(diǎn)間畫一條連續(xù)的直線；但在屏幕上，只能畫任意兩個(gè)整數(shù)坐標(biāo)點(diǎn)（像素）之間的連線，且該直線不再連續(xù)，而是由落于其上或臨近的像素構(gòu)成。將頂點(diǎn)參數(shù)表示的圖形轉(zhuǎn)換為像素（點(diǎn)陣）表示的圖形稱為光柵圖形的掃描轉(zhuǎn)換。基本圖形的光柵掃描轉(zhuǎn)換也稱為圖元生成。

圖元的掃描轉(zhuǎn)換分為兩個(gè)步驟，即確定與圖元相關(guān)的像素集合，和用顏色及其他屬性對(duì)這些屬性進(jìn)行寫操作。

1.4.2　掃描轉(zhuǎn)換直線

掃描轉(zhuǎn)換直線是計(jì)算出落在直線上或與它臨近的一組像素，以一定的顏色用這組像素近似替代連續(xù)的沒有寬度的筆直直線，并在屏幕上顯示的過程。

屏幕上的光柵點(diǎn)（像素）用圖1-3中的光柵點(diǎn)格圖表示，填色的圓圈是直線上的點(diǎn)，未填色的圓圈不是直線上的點(diǎn)，這些圓圈是以像素點(diǎn)的坐標(biāo)（xi，yi）為圓心的小圓圈。這里暫且認(rèn)為直線的端點(diǎn)都是整型坐標(biāo)點(diǎn)且直線是一個(gè)像素寬的。

下面是掃描轉(zhuǎn)換直線的DDA算法（數(shù)值微分法）。

設(shè)直線的兩個(gè)端點(diǎn)坐標(biāo)為（x0，y0）和（x1，y1），若記Δx=x1-x0，Δy=y1-y0，則它的斜率m=Δy/Δx，那么直線上對(duì)應(yīng)于xi的yi坐標(biāo)是：yi=mxi+B，這里B是直線的截距，yi值四舍五入取整數(shù)值。

顯然，yi+1=mxi+1+B=m（xi+Δx）+B=mxi+mΔx+B=yi+mΔx。若取增量Δx=1，有yi+1=yi+m。

可見x每增加一個(gè)像素，y就增加一個(gè)m，即可以從yi直接得到y(tǒng)i+1，而不是由xi+1通過直線方程yi=mxi+B求得yi+1，這樣便消除了算法中的乘法，如圖1-4所示。上式所表示的生成直線的計(jì)算方法稱為數(shù)值微分法。

從直線最左面的端點(diǎn)（x0，y0）開始，假設(shè)x0，y0都是整數(shù)，由于直接使用y0，就不必計(jì)算截距B，這里是考慮直線斜率|m|≤1的情況。此時(shí)x增加1時(shí)，y的增量不大于1，在迭代的過程中，每次只寫一個(gè)像素。如果直線的斜率|m|>1，可將x，y交換使y值每增加1時(shí)，x值相應(yīng)增加1/m。

1.4.3　掃描轉(zhuǎn)換弧

生成圓弧的最簡(jiǎn)單算法是利用圓弧的方程x2+y2=R2，取一系列不同的x，求出相應(yīng)的y，連接畫出圓弧。若畫一個(gè)整圓，則只需畫出1/8圓弧，再利用對(duì)稱性即可畫出整圓。但它用到開方，計(jì)算量大，效率不高。

掃描轉(zhuǎn)換弧的算法有圓弧生成的中點(diǎn)算法、多邊形迫近法、正負(fù)法和橢圓弧生成的中點(diǎn)算法等，與掃描轉(zhuǎn)換直線的算法有相通之處。

1.4.4　圖元屬性控制

1.線寬控制

實(shí)際繪圖常常用到有寬度的直線和曲線。要生成有寬度的線，可用帶有一定寬度的刷子沿著單像素寬的線的中心移動(dòng)。這個(gè)刷子可以是線形的或正方形的。正方形的刷子效果較好。實(shí)現(xiàn)正方形刷子的算法是將正方形的中心對(duì)準(zhǔn)單像素寬直線上的每個(gè)像素，然后將正方形中全部像素置成直線的顏色。方法很簡(jiǎn)單，但會(huì)重寫各個(gè)像素，因相鄰兩個(gè)正方形中像素可能會(huì)重疊。為避免這一點(diǎn)，可采用區(qū)域填充的方法來生成有寬度的直線和弧線。

2.線型控制

線型是所有圖元都具有的屬性，在工程制圖中應(yīng)用廣泛，如實(shí)線、虛線、點(diǎn)畫線等。

線型控制一般用一個(gè)位屏蔽器來完成，如可用一個(gè)32位的整數(shù)表示一個(gè)位串，當(dāng)像素對(duì)應(yīng)的位為1時(shí)顯示該像素，為0時(shí)不顯示該像素。用這樣的整數(shù)控制線型時(shí)，線型必須以32像素為周期重復(fù)。

1.4.5　填充

基本圖形的填充有兩大步驟，一是確定應(yīng)填充的像素，二是填充顏色。確定像素是否被填充的方法是用順序的掃描線與圖形邊界相交，并對(duì)兩交點(diǎn)間的像素從左到右填充。

1.矩形的填充

填充四條邊是水平和垂直的矩形比較容易，與矩形相交的順序掃描線從左邊界掃到右邊界，在此過程中，把遇到的每個(gè)像素填充同樣的顏色。

2.多邊形填充

一般多邊形的填充過程，對(duì)每條掃描線都需要執(zhí)行以下4個(gè)步驟：

（1）求該掃描線與多邊形每條邊的交點(diǎn)。

（2）對(duì)所有的交點(diǎn)，按從左到右以x遞增的順序排序。

（3）把排序的交點(diǎn)進(jìn)行配對(duì)。每對(duì)交點(diǎn)代表掃描線與多邊形的一個(gè)相交區(qū)間，該區(qū)間的點(diǎn)屬于多邊形的內(nèi)部點(diǎn)。

（4）將相交區(qū)間內(nèi)的像素點(diǎn)置成多邊形的顏色，把區(qū)間外的像素點(diǎn)置成背景的顏色。

這是多邊形填充的掃描轉(zhuǎn)換算法。還有邊緣填充算法、種子填充算法等。

3.圖案填充

填充方式分為均勻填充方式、位圖不透明方式、位圖透明方式、像素圖填充方式。

前面所述的都是均勻填充方式，即將邊界內(nèi)部的像素置成同一種顏色。后3種方式只需將前述算法稍加修改即可實(shí)現(xiàn)。

當(dāng)按照位圖不透明方式填充時(shí)，若像素對(duì)應(yīng)的位圖單元的值為1，則仍用前景色顯示該像素；若為0，則以背景色顯示該像素。

當(dāng)按照位圖透明方式填充時(shí)，若像素對(duì)應(yīng)的位圖單元的值為1，則仍用前景色顯示該像素；若為0，則不改變屏幕上該像素的顏色。

當(dāng)按照像素圖方式填充時(shí)，以像素對(duì)應(yīng)的像素圖單元的顏色顯示該像素。

1.4.6　字符表示和輸出

字符是圖形中的一個(gè)重要組成部分，包括字母、數(shù)字、漢字和標(biāo)點(diǎn)等符號(hào)。目前有ASCII碼和漢語字符集GB 2312—1980《信息交換用漢字編碼字符集基本集》。

1.字符的表示

字符的圖形有兩種表示方法：點(diǎn)陣字符法和輪廓字型法。

（1）點(diǎn)陣字符法

每個(gè)字符都定義成一個(gè)正方形的矩陣，該矩陣對(duì)應(yīng)著一個(gè)正方形的位圖，字符的筆畫經(jīng)過的位，其值為1，對(duì)應(yīng)的像素置成字符的顏色。字符的筆畫不經(jīng)過的位，其值為0，對(duì)應(yīng)的像素置成背景顏色（寫模式為“替換方式”時(shí)）或像素顏色不變（寫模式為“與”方式時(shí)）。

（2）輪廓字型法

這種方法采用直線、二次或三次曲線來描述一個(gè)字符的輪廓線。這些輪廓線構(gòu)成了平面上一個(gè)或幾個(gè)封閉的圖形。這樣形成的字符無論變大還是變小，其清晰度和美感都不受影響。

2.字符的輸出

字符顯示和打印的步驟是先根據(jù)字符的編碼將字符從字庫中檢索出來，然后把字符定位在正確的位置上。

1.4.7　二維裁剪

把整個(gè)圖形中所需要的一部分放到屏幕顯示區(qū)內(nèi)，舍棄圖形的其他部分，這個(gè)過程稱為裁剪（clip）。圖形在屏幕上顯示的區(qū)域稱做窗口，一般為矩形。裁剪算法的關(guān)鍵是確定圖形中哪些點(diǎn)、線、多邊線位于窗口之中或之外。

1.直線裁剪

直線裁剪的算法很多，有編碼算法（Cohen-Sutherland算法）、中點(diǎn)分割算法和參數(shù)化算法（Cyrus-Beck）等。下面是編碼算法。

直線與裁剪窗口的關(guān)系有4種可能，如圖1-5所示。

（1）線段完全在窗口之內(nèi)，如線段AB。

（2）線段完全在窗口之外，如線段CD。

（3）線段與窗口的一條邊界相交，即線段一部分在窗口之內(nèi)，一部分在窗口之外，如線段EF。

（4）線段與窗口的兩條邊界相交，中間一段在窗口之內(nèi)，兩頭在窗口之外，如線段HK。

對(duì)于完全在窗口之外的線段可舍棄。其他的在窗口內(nèi)都有可見段，可見段不可舍棄。確定可見段的方法是求它的兩個(gè)可見端點(diǎn)。

2.字符裁剪

字符裁剪有多種方法，常用的有以下3種：

（1）基于字符串：當(dāng)整個(gè)字符串全部位于窗口之內(nèi)時(shí)顯示，否則不顯示。

（2）基于字符：當(dāng)一個(gè)字符完全位于窗口之內(nèi)時(shí)顯示，否則不顯示。

（3）基于構(gòu)成字符的最小元素：對(duì)于點(diǎn)陣字符而言，構(gòu)成字符的最小元素為像素，此時(shí)字符的裁剪變?yōu)辄c(diǎn)裁剪。對(duì)于輪廓字符而言，構(gòu)成字符的最小元素為直線和曲線，此時(shí)字符的裁剪就變?yōu)榫€裁剪。

1.4.8　三維裁剪

三維圖形經(jīng)過投影變換后才能在二維平面上顯示出來，所以，可以對(duì)已作過投影變換的二維圖形進(jìn)行裁剪。三維投影在1.6.3小節(jié)介紹。