研究生計(jì)算機(jī)圖形學(xué)

3.1直線的生成算法

在點(diǎn)陣設(shè)備中，直線是用一系列靠近直線的像素點(diǎn)來(lái)逼近的。圖3.1.1是像素點(diǎn)逼近直線的幾個(gè)例子(用小圓點(diǎn)代表逼近的像素點(diǎn))。從圖中可見(jiàn)，只有當(dāng)直線是水平的(如AB)、垂直的(如AC)或與水平線成45°(如AD)時(shí)，由像素點(diǎn)拼成的圖形才是真正的直線，其他位置的直線(如AE)都呈階梯形，這種現(xiàn)象稱為階梯效應(yīng)。研究直線的生成就要減少這種階梯效應(yīng)。對(duì)生成直線的要求是：直線要直(即逼近程度好)、起點(diǎn)和終點(diǎn)位置要準(zhǔn)確(否則會(huì)在直線連接處出現(xiàn)間隙)、線上各點(diǎn)亮度要均勻(即要求點(diǎn)的密度要均勻，否則給人一段亮一段暗的感覺(jué))、畫(huà)線速度要快(與直線生成算法和計(jì)算機(jī)速度均有關(guān))。第1頁(yè)/共152頁(yè)第一頁(yè)，共153頁(yè)。圖3.1.1直線的像素化(VRC變換)第2頁(yè)/共152頁(yè)第二頁(yè)，共153頁(yè)。

點(diǎn)陣設(shè)備中直線的生成方法主要有：對(duì)稱DDA法、簡(jiǎn)單DDA法、Bresenham算法、中點(diǎn)畫(huà)線法等，每種方法各有優(yōu)缺點(diǎn)。矢量設(shè)備中直線的生成方法主要有：逐點(diǎn)比較法、正負(fù)法、Bresenham算法等。直線的生成算法是在設(shè)備坐標(biāo)系(如屏幕坐標(biāo)系、繪圖機(jī)坐標(biāo)系等)中進(jìn)行的，要求直線已知點(diǎn)即起點(diǎn)和終點(diǎn)的坐標(biāo)為設(shè)備坐標(biāo)。若已知點(diǎn)坐標(biāo)為世界坐標(biāo)則要換算成設(shè)備坐標(biāo)。第3頁(yè)/共152頁(yè)第三頁(yè)，共153頁(yè)。1.DDA法

DDA法即數(shù)字微分分析法(DigitalDifferentialAnalyzer)。我們知道，直線微分方程為這里(xa,ya)、(xb,yb)為直線起點(diǎn)和終點(diǎn)坐標(biāo)。將上式數(shù)字化(即像素化)，便可得到下面的遞推公式：第4頁(yè)/共152頁(yè)第四頁(yè)，共153頁(yè)。

當(dāng)ε取值不同時(shí)，便形成對(duì)稱DDA法和簡(jiǎn)單DDA法。下面以屏幕上生成直線為例來(lái)介紹這兩種算法。

(1)對(duì)稱DDA法。對(duì)稱DDA法取ε=2-n，n由下面關(guān)系式?jīng)Q定：

2n-1≤max(|Δx|,|Δy|)≤2n,n為正整數(shù)第5頁(yè)/共152頁(yè)第五頁(yè)，共153頁(yè)。計(jì)算點(diǎn)的公式為

上式中加0.5是為了減少誤差而采用的“四舍五入法”，xi、yi、xi+1、yi+1是計(jì)算坐標(biāo)，而xis、yis是顯示坐標(biāo)，即像素點(diǎn)的位置坐標(biāo)。第6頁(yè)/共152頁(yè)第六頁(yè)，共153頁(yè)?！纠?】用對(duì)稱DDA法在起點(diǎn)A(2，1)和終點(diǎn)B(12，7)之間生成一段直線。求解的第一步是計(jì)算初值Δx,Δy,n。這里Δx=10,Δy=6,n=4。第二步按遞推公式循環(huán)計(jì)算點(diǎn)的坐標(biāo)，并取整顯示。表3.1.1是本例的循環(huán)計(jì)算過(guò)程。圖3.1.2是其屏幕顯示結(jié)果。第7頁(yè)/共152頁(yè)第七頁(yè)，共153頁(yè)。表3.1.1對(duì)稱DDA法計(jì)算過(guò)程第8頁(yè)/共152頁(yè)第八頁(yè)，共153頁(yè)。圖3.1.2對(duì)稱DDA法生成的直線第9頁(yè)/共152頁(yè)第九頁(yè)，共153頁(yè)。

對(duì)稱DDA法生成的直線比較精確，像點(diǎn)位置偏離直線不超過(guò)半個(gè)像素。邏輯上也比較簡(jiǎn)單，用2的負(fù)指數(shù)冪作為ε，意味著把存放Δx和Δy的寄存器通過(guò)移位操作就可得到點(diǎn)與點(diǎn)之間的坐標(biāo)增量εΔx、εΔy，而不用除法計(jì)算，計(jì)算直線上每一點(diǎn)只用兩次加法即可實(shí)現(xiàn)。對(duì)稱DDA法適合用硬件來(lái)實(shí)現(xiàn)，當(dāng)然也可用軟件來(lái)實(shí)現(xiàn)。第10頁(yè)/共152頁(yè)第十頁(yè)，共153頁(yè)。(2)簡(jiǎn)單DDA法。簡(jiǎn)單DDA法取 。計(jì)算點(diǎn)的公式為第11頁(yè)/共152頁(yè)第十一頁(yè)，共153頁(yè)。圖3.1.3簡(jiǎn)單DDA法生成的直線第12頁(yè)/共152頁(yè)第十二頁(yè)，共153頁(yè)。

簡(jiǎn)單DDA法是按Δx,Δy絕對(duì)值較大的方向走步的，在這個(gè)方向上，每步走一個(gè)像素，然后再確定另一個(gè)方向的走步。簡(jiǎn)單DDA法生成直線的精度同對(duì)稱DDA法，但它在求一個(gè)點(diǎn)時(shí)要做兩次除法以決定坐標(biāo)增量值。簡(jiǎn)單DDA法不適合硬件實(shí)現(xiàn)，只適合于軟件處理。第13頁(yè)/共152頁(yè)第十三頁(yè)，共153頁(yè)。2.Bresenham直線生成算法由Bresenham提出的算法最初是為數(shù)控繪圖機(jī)設(shè)計(jì)的，后來(lái)被廣泛用于光柵掃描圖形顯示器。Bresenham直線生成算法實(shí)際上也是簡(jiǎn)單DDA算法，即在某一計(jì)長(zhǎng)方向上，每次必變化一個(gè)單位步長(zhǎng)或一個(gè)像素單位，另一方向上的變化量可通過(guò)計(jì)算得到。這種算法只用到整型數(shù)計(jì)算，不必作四舍五入操作，而且在計(jì)算判別式時(shí)，計(jì)算量很小，因而得到廣泛的應(yīng)用。下面我們介紹在光柵掃描圖形顯示器上實(shí)現(xiàn)的這種算法。第14頁(yè)/共152頁(yè)第十四頁(yè)，共153頁(yè)。

假設(shè)要生成的直線起點(diǎn)為(xa,ya)、終點(diǎn)為(xb,yb)，經(jīng)變換后直線起點(diǎn)為(0，0)、終點(diǎn)為(Δx,Δy)，其中Δx=xb-xa,Δy=yb-ya。此時(shí)直線方程可簡(jiǎn)化為

先考慮直線的斜率在0~1之間的情況。如圖3.1.4所示，設(shè)Pi-1(xi-1,yi-1)是已確定的逼近像素點(diǎn)，令Pi-1的坐標(biāo)為(r,q),Si(r+1,q)、Ti(r+1,q+1)是靠近直線的兩個(gè)像素點(diǎn)，現(xiàn)在要決定下一個(gè)像素是Si還是Ti。由圖中可直觀地看出：若s<t,則Si比較靠近直線，應(yīng)選Si;

若s≥t，則應(yīng)選Ti。第15頁(yè)/共152頁(yè)第十五頁(yè)，共153頁(yè)。第16頁(yè)/共152頁(yè)第十六頁(yè)，共153頁(yè)?，F(xiàn)在我們推導(dǎo)由Pi-1確定下一個(gè)像素點(diǎn)的遞推關(guān)系式。由于則即第17頁(yè)/共152頁(yè)第十七頁(yè)，共153頁(yè)。由于此時(shí)Δx為正，故我們可以用Δx(s-t)的正、負(fù)作為選擇Si和Ti的標(biāo)準(zhǔn)。若令di=Δx(s-t)，則有di=2(r·Δy-q·Δx)+2Δy-Δx將r=xi-1，q=yi-1代入，于是di=2xi-1·Δy-2yi-1·Δx+2Δy-Δx將式(3-1)中的i用i+1替換，便有di+1=2xi·Δy-2yi·Δx+2Δy-Δx用di+1減去di得di+1-di=2Δy(xi-xi-1)-2Δx(yi-yi-1)(3-1)第18頁(yè)/共152頁(yè)第十八頁(yè)，共153頁(yè)。由于此時(shí)走步方向?yàn)閤方向，即xi-xi-1=1，重寫(xiě)上式得di+1=di+2Δy-2Δx(yi-yi-1)

若di≥0，即s≥t，則選Ti,此時(shí)

yi=yi-1+1 Di+1=di+2(Δy-Δx)

若di<0,即s<t，則選Si，此時(shí)

yi=yi-1 di+1=di+2Δy

這樣，我們就有了一個(gè)遞推的方法，即由前一個(gè)di計(jì)算出下一個(gè)di+1，并對(duì)Si及Ti進(jìn)行選擇。di的初值d1可由式(3-1)求出，將i=1,x0=y0=0代入得d1=2Δy-Δx(3-3)(3-4)第19頁(yè)/共152頁(yè)第十九頁(yè)，共153頁(yè)。

根據(jù)以上分析，我們可得到斜率在0~1之間的Bresenham直線生成遞推計(jì)算公式：(3-5)第20頁(yè)/共152頁(yè)第二十頁(yè)，共153頁(yè)。

上式中的坐標(biāo)x0、y0、xi-1,yi-1、xi,yi均為以直線起點(diǎn)為坐標(biāo)原點(diǎn)的局部坐標(biāo)系下的坐標(biāo)。當(dāng)斜率大于1時(shí)，只需將x,y交換計(jì)算即可(此時(shí)以y方向作為走步方向，每次增加一個(gè)像素單位)，顯示時(shí)再將x,y換過(guò)來(lái)。對(duì)于任意走向的直線，在用式(3-5)計(jì)算時(shí)，Δx,Δy要用絕對(duì)值代入，并根據(jù)Δx,Δy的正、負(fù)號(hào)決定x,y方向增量的正負(fù)。第21頁(yè)/共152頁(yè)第二十一頁(yè)，共153頁(yè)。3.生成直線的逐點(diǎn)比較法逐點(diǎn)比較法就是在輸出直線或圓弧的過(guò)程中，每走完一步就與理論的直線或圓弧進(jìn)行比較，確定當(dāng)前點(diǎn)是在線或弧上，還是在線或弧的一側(cè)，然后再?zèng)Q定下一步的走向，這樣一步一步地逼近所畫(huà)直線或圓弧。第22頁(yè)/共152頁(yè)第二十二頁(yè)，共153頁(yè)。

逐點(diǎn)比較法是針對(duì)筆式繪圖機(jī)提出的。根據(jù)繪圖機(jī)的結(jié)構(gòu)原理及數(shù)字控制原理，繪圖機(jī)的筆架可能的移動(dòng)方向(稱為走步方向)有八個(gè)：+X、-X、+Y、-Y、+X+Y、-X+Y、-X-Y、+X-Y。其中+X、-X、+Y、-Y四個(gè)走步方向是一般繪圖機(jī)都提供的，稱為基本走步方向。可見(jiàn)，繪圖機(jī)的基本繪圖元素是與走步方向相對(duì)應(yīng)的小直線段。繪圖機(jī)所畫(huà)的一般直線和曲線，實(shí)際上是由許多小直線段所組成的折線來(lái)逼近的。根據(jù)所畫(huà)圖線的已知條件(如直線兩個(gè)端點(diǎn)坐標(biāo)，圓弧的起點(diǎn)、終點(diǎn)和圓心等)計(jì)算畫(huà)圖所需要的一系列中間點(diǎn)(即折線的端點(diǎn))的坐標(biāo)，稱為插補(bǔ)運(yùn)算。根據(jù)插補(bǔ)對(duì)象不同，插補(bǔ)運(yùn)算有直線插補(bǔ)、圓弧插補(bǔ)和拋物線插補(bǔ)等，前兩種是基本的插補(bǔ)運(yùn)算。插補(bǔ)運(yùn)算可用軟件或硬件實(shí)現(xiàn)，不少繪圖機(jī)采用插補(bǔ)器(或稱線發(fā)生器、弧發(fā)生器)來(lái)完成插補(bǔ)運(yùn)算，目的在于提高圖線生成速度。逐點(diǎn)比較法可用于插補(bǔ)運(yùn)算。第23頁(yè)/共152頁(yè)第二十三頁(yè)，共153頁(yè)。

下面介紹逐點(diǎn)比較法。為敘述簡(jiǎn)捷并減少計(jì)算量，算法中建立了局部坐標(biāo)系，將有關(guān)坐標(biāo)轉(zhuǎn)化為局部坐標(biāo)計(jì)算。形成局部坐標(biāo)的方法很簡(jiǎn)單，對(duì)直線而言，各點(diǎn)坐標(biāo)減去起點(diǎn)坐標(biāo)就得到每點(diǎn)的局部坐標(biāo)，直線的起點(diǎn)就是局部坐標(biāo)系的原點(diǎn)；對(duì)圓弧而言，各點(diǎn)坐標(biāo)減去圓心坐標(biāo)就得到每點(diǎn)的局部坐標(biāo)，圓心就是局部坐標(biāo)系的原點(diǎn)。直線的生成運(yùn)算按直線所在的象限進(jìn)行。第24頁(yè)/共152頁(yè)第二十四頁(yè)，共153頁(yè)。

若畫(huà)第一象限的直線OA，如圖3.1.5所示，起點(diǎn)為O(0，0)，終點(diǎn)為A(xa,ya)，設(shè)繪圖筆當(dāng)前的位置為K(xk,yk)，這里坐標(biāo)均為局部坐標(biāo)。點(diǎn)K相對(duì)于直線OA的位置有三種情況：點(diǎn)K在OA上方，點(diǎn)K在OA上以及點(diǎn)K在OA下方。為判斷點(diǎn)K與OA的相對(duì)位置，引入偏差函數(shù)Fk。Fk=xayk-xkya當(dāng)K在OA上時(shí)，F(xiàn)k=0;K在OA上方時(shí)，F(xiàn)k>0;K在OA下方時(shí)，F(xiàn)k<0。第25頁(yè)/共152頁(yè)第二十五頁(yè)，共153頁(yè)。第26頁(yè)/共152頁(yè)第二十六頁(yè)，共153頁(yè)。

對(duì)第一象限內(nèi)直線的生成規(guī)定如下：當(dāng)Fk≥0時(shí)，繪圖筆從當(dāng)前位置沿+X方向走一步，記作+Δx；當(dāng)Fk<0時(shí)，繪圖筆從當(dāng)前位置沿+Y方向走一步，記作+Δy；在繪圖筆到達(dá)新的位置時(shí)，應(yīng)計(jì)算出新位置的偏差，為判斷繪圖筆下一步走向作準(zhǔn)備。繪圖筆走+Δx時(shí)，新點(diǎn)坐標(biāo)為xk+1=xk+1,yk+1=yk這時(shí)新點(diǎn)偏差為Fk+1=xayk+1-xk+1ya=xayk-xkya-ya=Fk-ya第27頁(yè)/共152頁(yè)第二十七頁(yè)，共153頁(yè)。

繪圖筆走+Δy時(shí)，新點(diǎn)坐標(biāo)為xk+1=xk,yk+1=yk+1這時(shí)新點(diǎn)偏差為Fk+1=xayk+1-xk+1ya=xayk+xa-xkya=Fk+xa

根據(jù)新偏差Fk+1的正、負(fù)號(hào)再確定繪圖筆的下一步走向，這樣逐步進(jìn)行，直到繪圖筆到達(dá)直線的終點(diǎn)為止。終點(diǎn)判斷可由X及Y向總走步數(shù)J(J=|xa|+|ya|)來(lái)控制，每走一步J減去1，當(dāng)J=0時(shí)即到達(dá)終點(diǎn)。第28頁(yè)/共152頁(yè)第二十八頁(yè)，共153頁(yè)。

對(duì)其他象限內(nèi)直線段生成計(jì)算走步方向的規(guī)定如圖3.1.6所示。偏差的遞推計(jì)算均按以下兩式進(jìn)行：當(dāng)沿X方向走步時(shí)，F(xiàn)k+1=Fk-|ya|；當(dāng)沿Y方向走步時(shí)，F(xiàn)k+1=Fk+|xa|。第29頁(yè)/共152頁(yè)第二十九頁(yè)，共153頁(yè)。圖3.1.6各象限內(nèi)直線生成的走步方向第30頁(yè)/共152頁(yè)第三十頁(yè)，共153頁(yè)?！纠?】用逐點(diǎn)比較法畫(huà)直線OA，其起點(diǎn)為O(0，0)，終點(diǎn)為A(5，3)。計(jì)算從起點(diǎn)開(kāi)始，總走步數(shù)J=8，起點(diǎn)處F0=0，走步方向的規(guī)定按第一象限進(jìn)行。算法的計(jì)算結(jié)果如圖3.1.7所示，其過(guò)程列于表3.1.2。圖3.1.7逐點(diǎn)比較法生成直線的圖例第31頁(yè)/共152頁(yè)第三十一頁(yè)，共153頁(yè)。表3.1.2直線生成的遞推計(jì)算過(guò)程第32頁(yè)/共152頁(yè)第三十二頁(yè)，共153頁(yè)。3.2圓弧與橢圓弧的生成算法

1.角度DDA法產(chǎn)生圓弧若已知圓心坐標(biāo)為(xc,yc)，半徑為R，則以角度t為參數(shù)的圓的參數(shù)方程可寫(xiě)為

當(dāng)t從0變化到2π時(shí)，上述方程所表示的軌跡是一整圓；當(dāng)t從起始角ts變化到終止角te時(shí)，則產(chǎn)生一段圓弧。由于我們定義角度的正方向是逆時(shí)針?lè)较?，所以圓弧是由ts到te逆時(shí)針畫(huà)圓得到的。第33頁(yè)/共152頁(yè)第三十三頁(yè)，共153頁(yè)。

若給定圓心坐標(biāo)(xc,yc)，半徑R及起始角ts和終止角te，要產(chǎn)生從ts到te這段圓弧的最主要問(wèn)題是離散化圓弧，即用小直線段逼近圓弧，這就需要求出從ts到te所需運(yùn)動(dòng)的總步數(shù)n?？闪钇渲校琩t為角度增量，即每走一步對(duì)應(yīng)的角度變化。問(wèn)題是如何選取dt?通常是根據(jù)半徑R的大小來(lái)給定dt的經(jīng)驗(yàn)數(shù)據(jù)。在實(shí)際應(yīng)用中，應(yīng)對(duì)速度和精度的要求加以折衷，并適當(dāng)調(diào)整dt的大小。如果用戶給定的te<ts，則可令te=te+2π，以保證從ts到te逆時(shí)針畫(huà)圖。如果畫(huà)整圓，則令n=2π/dt+0.5。為避免累積誤差，最后應(yīng)使t=te，強(qiáng)迫止于終點(diǎn)。第34頁(yè)/共152頁(yè)第三十四頁(yè)，共153頁(yè)。

若給定畫(huà)圓弧的條件為圓周上三點(diǎn)P1(x1,y1),P2(x2,y2),P3(x3,y3)，則利用幾何關(guān)系和三角關(guān)系不難求出圓心(xc,yc),半徑R及起始角ts和終止角te，要注意將ts,te規(guī)范至均大于0且ts<te,并由ts逆時(shí)針畫(huà)弧至te(若連接P1,P2,P3構(gòu)成的兩矢量叉乘為負(fù)，則說(shuō)明順時(shí)針畫(huà)弧，此時(shí)應(yīng)將P1,P3交換，就可保證逆時(shí)針畫(huà)弧)。第35頁(yè)/共152頁(yè)第三十五頁(yè)，共153頁(yè)。2.Bresenham畫(huà)圓算法算法中以圓心為坐標(biāo)原點(diǎn)建立了局部坐標(biāo)系。先考慮產(chǎn)生第一象限的八分之一圓弧，即從S(0，R)到 之間的45°圓弧，如圖3.2.1所示。設(shè)Pi-1(xi-1,yi-1)為已確定的逼近像素點(diǎn)?，F(xiàn)在，當(dāng)xi=xi-1+1時(shí)，必須決定是Ti(xi-1+1,yi-1-1)還是Si(xi-1+1,yi-1)更接近實(shí)際的圓弧。令D(Si)=［(xi-1+1)2+y2i-1］-R2

D(Ti)=［(xi-1+1)2+(yi-1-1)2］-R2

第36頁(yè)/共152頁(yè)第三十六頁(yè)，共153頁(yè)。

它們分別代表從圓心(坐標(biāo)原點(diǎn))到Si或到Ti的距離平方與半徑平方的差。如果|D(Si)|≥|D(Ti)|，則Ti比Si更接近實(shí)際的圓弧，應(yīng)選Ti;如果|D(Si)|<|D(Ti)|，則Si比Ti更接近實(shí)際的圓弧，應(yīng)選Si。令di=|D(Si)|-|D(Ti)| (3-6)于是，di≥0時(shí)，應(yīng)選Ti;di<0時(shí)，應(yīng)選Si。式(3-6)的計(jì)算要用到絕對(duì)值，故比較麻煩。參照?qǐng)D3.2.2實(shí)際的圓弧穿過(guò)柵格的各種可能的形式(從A到E)，可以簡(jiǎn)化式(3-6)的計(jì)算。第37頁(yè)/共152頁(yè)第三十七頁(yè)，共153頁(yè)。圖3.2.1Bresenham算法與八分之一圓弧第38頁(yè)/共152頁(yè)第三十八頁(yè)，共153頁(yè)。圖3.2.2Bresenham畫(huà)圓算法的判別點(diǎn)第39頁(yè)/共152頁(yè)第三十九頁(yè)，共153頁(yè)。對(duì)于情況C，因?yàn)镾i在圓外，我們有D(Si)>0，同時(shí)因?yàn)門i在圓內(nèi)，故有D(Ti)<0。于是式(3-6)可改寫(xiě)為di=D(Si)+D(Ti) (3-7)即可直接根據(jù)式(3-7)中di的正、負(fù)來(lái)選擇Ti或Si。對(duì)于情況A和B，由于|D(Si)|<|D(Ti)|，按式(3-6)應(yīng)選Si。若按式(3-7)計(jì)算，由于Ti在圓內(nèi)，有D(Ti)<0;Si在圓內(nèi)(情況A)或圓上(情況B)，有D(Si)≤0，故有di<0，也選Si?？梢?jiàn)式(3-7)對(duì)情況A和B也是適用的。經(jīng)過(guò)類似地分析可知，式(3-7)對(duì)于情況D和E也是適用的。第40頁(yè)/共152頁(yè)第四十頁(yè)，共153頁(yè)。

因此，我們可以用式(3-7)代替式(3-6)進(jìn)行判斷計(jì)算。下面的工作是要推導(dǎo)一個(gè)遞推公式，以簡(jiǎn)化di的計(jì)算。由式(3-7)及D(Si)、D(Ti)的表達(dá)式有用i+1代替上式中的i，得用di+1減去di,得第41頁(yè)/共152頁(yè)第四十一頁(yè)，共153頁(yè)。若di≥0，則選Ti，此時(shí)(3-9)若di<0，則選Si，此時(shí)(3-10)第42頁(yè)/共152頁(yè)第四十二頁(yè)，共153頁(yè)。di的初值d1可由式(3-8)求出，將i=1,x0=0,y0=R代入之，得

顯然，式(3-9)、式(3-10)、式(3-11)的計(jì)算量是很小的，因此效率較高。(3-11)第43頁(yè)/共152頁(yè)第四十三頁(yè)，共153頁(yè)。

根據(jù)以上分析，我們可以得到Bresenham算法產(chǎn)生八分之一圓弧的遞推計(jì)算公式：第44頁(yè)/共152頁(yè)第四十四頁(yè)，共153頁(yè)。3.生成圓弧的逐點(diǎn)比較法圓弧的生成按圓弧所在的象限以及畫(huà)弧方向(逆時(shí)針還是順時(shí)針)進(jìn)行。若圓弧跨過(guò)幾個(gè)象限，應(yīng)按象限分段生成。若畫(huà)第一象限的圓弧AB，如圖3.2.4所示，起點(diǎn)為A(xa,ya)，終點(diǎn)為B(xb,yb)，圓心為O(0，0)，設(shè)繪圖筆當(dāng)前位置為K(xk,yk)，這里的坐標(biāo)為局部坐標(biāo)。第45頁(yè)/共152頁(yè)第四十五頁(yè)，共153頁(yè)。圖3.2.3一個(gè)圓上的8個(gè)對(duì)稱點(diǎn)第46頁(yè)/共152頁(yè)第四十六頁(yè)，共153頁(yè)。圖3.2.4逐點(diǎn)比較法與圓弧的生成第47頁(yè)/共152頁(yè)第四十七頁(yè)，共153頁(yè)。

點(diǎn)K相對(duì)于圓弧AB的位置有三種情況：點(diǎn)K在AB外側(cè)，點(diǎn)K在AB上以及點(diǎn)K在AB內(nèi)側(cè)。為判斷點(diǎn)K與AB的相對(duì)位置，引入偏差函數(shù)Fk，((((R是為便于推導(dǎo)引入的半徑。當(dāng)K在AB上時(shí)，F(xiàn)k=0;

K在AB外側(cè)時(shí)，F(xiàn)k>0;

K在AB內(nèi)側(cè)時(shí)，F(xiàn)k<0。(((第48頁(yè)/共152頁(yè)第四十八頁(yè)，共153頁(yè)。

對(duì)第一象限的圓弧逆時(shí)針?lè)较蛏蓵r(shí)，規(guī)定如下：當(dāng)Fk≥0時(shí)，繪圖筆從當(dāng)前位置沿-X方向走一步，記作-Δx；當(dāng)Fk<0時(shí)，繪圖筆從當(dāng)前位置沿+Y方向走一步，記作+Δy。繪圖筆走-Δx時(shí)，新點(diǎn)坐標(biāo)為xk+1=xk-1,yk+1=yk新點(diǎn)偏差為第49頁(yè)/共152頁(yè)第四十九頁(yè)，共153頁(yè)。繪圖筆走+Δy時(shí)，新點(diǎn)坐標(biāo)為新點(diǎn)偏差為第50頁(yè)/共152頁(yè)第五十頁(yè)，共153頁(yè)。

新點(diǎn)偏差Fk+1由當(dāng)前點(diǎn)的坐標(biāo)值及偏差來(lái)計(jì)算。根據(jù)Fk+1的正、負(fù)號(hào)再確定繪圖筆的下一步走向，這樣逐步進(jìn)行，直到繪圖筆到達(dá)圓弧的終點(diǎn)為止。終點(diǎn)判斷可由總走步數(shù)J(J=|xb-xa|+|yb-ya|)來(lái)控制。每走一步J減去1，當(dāng)J=0時(shí)即到達(dá)終點(diǎn)。對(duì)其他象限內(nèi)圓弧生成的走步方向按圖3.2.5(a)、(b)進(jìn)行。第51頁(yè)/共152頁(yè)第五十一頁(yè)，共153頁(yè)。圖3.2.5各象限內(nèi)圓弧生成的走步方向(a)逆時(shí)針?lè)较虍?huà)圓弧；(b)順時(shí)針?lè)较虍?huà)圓弧第52頁(yè)/共152頁(yè)第五十二頁(yè)，共153頁(yè)。【例3】用逐點(diǎn)比較法逆時(shí)針畫(huà)圓弧AB，設(shè)起點(diǎn)為A(4，3)，終點(diǎn)為B(0，5)，圓心為O(0，0)。算法生成圓弧從起點(diǎn)開(kāi)始，總走步數(shù)J=|0-4|+|5-3|=6，起點(diǎn)處F0=0，走步方向的規(guī)定按第一象限進(jìn)行。算法的計(jì)算過(guò)程列于表3.2.1，其結(jié)果如圖3.2.6所示。第53頁(yè)/共152頁(yè)第五十三頁(yè)，共153頁(yè)。表3.2.1圓弧生成的遞推計(jì)算過(guò)程第54頁(yè)/共152頁(yè)第五十四頁(yè)，共153頁(yè)。圖3.2.6逐點(diǎn)比較法生成圓弧的圖例第55頁(yè)/共152頁(yè)第五十五頁(yè)，共153頁(yè)。

4.角度DDA法產(chǎn)生橢圓弧設(shè)給定的橢圓弧條件為：橢圓中心(xc,yc)，長(zhǎng)、短半軸a和b，橢圓弧起始點(diǎn)參數(shù)角ts及終止點(diǎn)參數(shù)角te、長(zhǎng)軸與X軸正向的夾角α，如圖3.2.7所示。這里對(duì)ts和te的要求同前面的圓弧，由ts逆時(shí)針畫(huà)弧至te?，F(xiàn)在我們要做的工作是推導(dǎo)出橢圓弧在世界坐標(biāo)系下的坐標(biāo)表達(dá)式。橢圓弧從標(biāo)準(zhǔn)位置(水平放正)變換至圖3.2.7所示位置，是經(jīng)過(guò)旋轉(zhuǎn)變換和平移變換這樣的組合變換形成的，利用第4章4.1.4節(jié)圖形變換的方法，我們可得到所需要的坐標(biāo)表達(dá)式，即x=acostcosα-bsintsinα+xcy=acostsinα+bsintcosα+yts≤t≤te

第56頁(yè)/共152頁(yè)第五十六頁(yè)，共153頁(yè)。圖3.2.7橢圓弧及其參數(shù)第57頁(yè)/共152頁(yè)第五十七頁(yè)，共153頁(yè)。

繪制橢圓弧的方法是用小直線段逼近。同DDA法產(chǎn)生圓弧一樣，我們將這段橢圓弧離散為幾等分，角度增量為dt，于是對(duì)于第i步，其對(duì)應(yīng)的參數(shù)角為ti=ts+i·dt

i=1,2,…,n

該點(diǎn)坐標(biāo)為xi=acosticosα-bsintisinα+xcyi=acostisinα+bsinticosα+y第58頁(yè)/共152頁(yè)第五十八頁(yè)，共153頁(yè)。3.3區(qū)域填充1.掃描線算法

(1)(YX)算法。這種算法充分利用一條掃描線上的像素存在著相關(guān)性這一特征進(jìn)行填充。因?yàn)樵谝粭l掃描線上，如果某個(gè)像素在多邊形之內(nèi)，那么，一般地說(shuō)，緊挨著的各像素也多半在多邊形內(nèi)。對(duì)于邊界外的像素也同樣存在著這種相關(guān)性。只有當(dāng)多邊形的邊恰好通過(guò)兩個(gè)像素之間時(shí)，它們?cè)诙噙呅蝺?nèi)、外的性質(zhì)才有所不同，而這種情況一般說(shuō)來(lái)是有限的。在圖3.3.1中，對(duì)于y=8這條掃描線，可求出交點(diǎn)a、b、c、d，因此，在該條掃描線上，凡是a<x<b和c<x<d之內(nèi)的像素，都位于多邊形之內(nèi)。根據(jù)這一思想，(YX)算法的步驟可敘述如下：第59頁(yè)/共152頁(yè)第五十九頁(yè)，共153頁(yè)。圖3.3.1多邊形和掃描線第60頁(yè)/共152頁(yè)第六十頁(yè)，共153頁(yè)。①求交。求出每一條掃描線與多邊形各邊的交點(diǎn)，建立起(x,y)交點(diǎn)表，若為水平邊則跳過(guò)。②排序。按x及y增加(或減少)的順序，對(duì)這些交點(diǎn)進(jìn)行排序。例如，交點(diǎn)(x1,y1)和(x2,y2)，當(dāng)y1≤y2而x1<x2時(shí)，則(x1,y1)先于(x2,y2)。③填充。將每一對(duì)交點(diǎn)之間的所有像素置成所需要的像素值。(YX)算法的核心是按(x,y)值對(duì)交點(diǎn)作一次分類，以便找出像素的相關(guān)群。分類的順序并不是特別重要的，但是卻影響位于多邊形內(nèi)的像素出現(xiàn)的順序，也即影響顯示畫(huà)面出現(xiàn)的順序。此算法是對(duì)每一對(duì)交點(diǎn)之間的所有像素進(jìn)行填充，因此交點(diǎn)的個(gè)數(shù)必須是偶數(shù)才能保證填充的正確性。而當(dāng)掃描線恰好通過(guò)多邊形的頂點(diǎn)(稱為奇異點(diǎn))時(shí)，不適當(dāng)?shù)赜?jì)數(shù)就會(huì)造成錯(cuò)誤。第61頁(yè)/共152頁(yè)第六十一頁(yè)，共153頁(yè)。

如圖3.3.1中y=7這條掃描線，若頂點(diǎn)④(亦即交點(diǎn)(7，7))只計(jì)一次，就會(huì)出現(xiàn)這種情況。對(duì)于頂點(diǎn)①、③、⑤也有類似的情況。對(duì)這些奇異點(diǎn)，我們最好多計(jì)入一個(gè)交點(diǎn)。但對(duì)于頂點(diǎn)②、⑥，重復(fù)計(jì)數(shù)又會(huì)出現(xiàn)錯(cuò)誤。為此，我們提出一種可靠的處理奇異點(diǎn)的方法，它依賴于多邊形的拓?fù)湫再|(zhì)。具體地說(shuō)，它利用多邊形相繼各邊的方向，若多邊形的邊單調(diào)地向上或向下伸展時(shí)，則對(duì)于每條與兩條邊的端點(diǎn)相交的掃描線，只需記錄一個(gè)交點(diǎn)。而當(dāng)邊的方向是由向下變成向上或相反時(shí)，則必須重復(fù)記錄一個(gè)交點(diǎn)。第62頁(yè)/共152頁(yè)第六十二頁(yè)，共153頁(yè)。

還有一種簡(jiǎn)單的處理奇異點(diǎn)的方法，就是對(duì)于那些不需要重復(fù)計(jì)數(shù)的奇異點(diǎn)，可以將其中一條邊的y坐標(biāo)值抬高一個(gè)像素，以保證僅有一條邊與掃描線有交點(diǎn)，確保填充的正確性。在設(shè)備分辨率足夠高的情況下，這種處理方法可以滿足一般的要求，對(duì)于圖3.3.1中的邊e2及e5，如使其y的最小值分別為y=4和y=6，則保證了頂點(diǎn)②及⑥只計(jì)一次交點(diǎn)。第63頁(yè)/共152頁(yè)第六十三頁(yè)，共153頁(yè)。(2)Y-X算法。上邊介紹的(YX)算法的第一步，也就是計(jì)算交點(diǎn)這一步，工作量是很大的，因?yàn)樾枰獙?duì)多邊形的每一條邊都進(jìn)行測(cè)試，看其是否與每一條掃描線相交。但是對(duì)于某一條掃描線，我們感興趣的常常只有少數(shù)幾條邊。而且，與第i條掃描線相交的許多條邊，一般地說(shuō)也與第i+1條掃描線相交，也即在與一條邊相交的很多條掃描線范圍內(nèi)，存在著邊的相關(guān)性。因此，對(duì)于每一條掃描線，我們只比較與其相交的那些邊。算法執(zhí)行時(shí)要求建立一張有效邊表(AET)，AET中的內(nèi)容隨每一條掃描線y值的不同而變化，也即在AET中，只保留與當(dāng)前掃描線相交的所有的邊。而且這些邊按其與該掃描線交點(diǎn)的x坐標(biāo)大小的順序存放，以便于在一對(duì)交點(diǎn)之間填充。當(dāng)從一條掃描線移到下一條掃描線時(shí)，我們利用兩條掃描線間隔為1的特性，可以簡(jiǎn)化邊與掃描線交點(diǎn)的計(jì)算。第64頁(yè)/共152頁(yè)第六十四頁(yè)，共153頁(yè)。圖3.3.2中，設(shè)邊AB的斜率為m，若其與掃描線yi的交點(diǎn)橫坐標(biāo)為xi,則與掃描線yi+1的交點(diǎn)的橫坐標(biāo)為

為了便于建立和修改AET，首先需要建立一張邊表(ET)。邊表一般是由一系列的存儲(chǔ)桶(bucket)構(gòu)成的，桶的數(shù)目與掃描線數(shù)一樣多。凡是與每條邊兩端點(diǎn)中較小的y坐標(biāo)值(ymin)對(duì)應(yīng)的桶，都記錄著待填充多邊形各邊的有關(guān)信息，包括每條邊兩端點(diǎn)中最大的y坐標(biāo)值(ymax)，y值較小的那個(gè)端點(diǎn)的x坐標(biāo)值(xmin)以及該邊斜率的倒數(shù)(1/m)。圖3.3.3表示出圖3.3.1的六條邊是如何存放的。第65頁(yè)/共152頁(yè)第六十五頁(yè)，共153頁(yè)。第66頁(yè)/共152頁(yè)第六十六頁(yè)，共153頁(yè)。圖3.3.3邊表第67頁(yè)/共152頁(yè)第六十七頁(yè)，共153頁(yè)。

當(dāng)形成了ET以后，Y-X算法按如下步驟執(zhí)行：

(1)將y值設(shè)置為ET中所列的最小y值，也即第一個(gè)非空的存儲(chǔ)桶。

(2)將AET初始化，使其為空。

(3)重復(fù)做以下各步，直至AET和ET都為空：①把ET中y的信息與AET合并，同時(shí)保存AET中按x值大小實(shí)現(xiàn)的排序序列。②對(duì)于掃描線y,在一對(duì)交點(diǎn)之間填充所需要的像素值。③從AET中刪去y>ymax的項(xiàng)。④對(duì)于仍留在AET中的每一項(xiàng)，用x+1/m代替x。⑤檢查并保證AET中各項(xiàng)按x值大小的排序。⑥使y增1，成為下一條掃描線的坐標(biāo)。第68頁(yè)/共152頁(yè)第六十八頁(yè)，共153頁(yè)。圖3.3.4有效邊表(a)掃描線9；(b)掃描線10第69頁(yè)/共152頁(yè)第六十九頁(yè)，共153頁(yè)。2.種子填充算法種子填充算法首先假定區(qū)域內(nèi)某點(diǎn)(即種子點(diǎn))是已知的，然后算法開(kāi)始搜索與它相鄰且位于邊界(封閉輪廓線)內(nèi)的點(diǎn)。如果相鄰點(diǎn)不在邊界內(nèi)，那么就到達(dá)區(qū)域的邊界；如果相鄰點(diǎn)位于邊界之內(nèi)，那么這一點(diǎn)就成為新的種子點(diǎn)，然后繼續(xù)遞歸地搜索下去。種子填充算法只適用于光柵掃描設(shè)備。在下面的討論中假設(shè)區(qū)域采用邊界定義，即區(qū)域邊界上所有像素均具有某個(gè)特定值，區(qū)域內(nèi)部所有像素取值可與邊界不同或相同。第70頁(yè)/共152頁(yè)第七十頁(yè)，共153頁(yè)。圖3.3.5兩類連通區(qū)域示意圖第71頁(yè)/共152頁(yè)第七十一頁(yè)，共153頁(yè)。

區(qū)域可以分為四向連通和八向連通兩種，四向連通區(qū)域指的是從區(qū)域上一點(diǎn)出發(fā)，可通過(guò)四個(gè)方向(上、下、左、右)移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素；八向連通區(qū)域指的是區(qū)域內(nèi)每一個(gè)像素，可以通過(guò)左、右、上、下、左上、右上、左下、右下這八個(gè)方向移動(dòng)的組合來(lái)到達(dá)。圖3.3.5(a)所示的區(qū)域是四向連通區(qū)域，圖3.3.5(b)所示的區(qū)域是八向連通區(qū)域。第72頁(yè)/共152頁(yè)第七十二頁(yè)，共153頁(yè)。

種子填充算法中，允許從四個(gè)方向?qū)ふ蚁乱幌袼氐模Q為四向算法；允許從八個(gè)方向搜索下一像素的，稱為八向算法。八向算法可以填充八向連通區(qū)域，也可以填充四向連通區(qū)域。但四向算法只能填充四向連通區(qū)域。如果圖3.3.5(b)中的區(qū)域是兩個(gè)分離的區(qū)域，并且每個(gè)區(qū)域需填成不同的顏色，那么，用八向算法會(huì)使兩個(gè)區(qū)域被錯(cuò)誤地填上同一顏色。以下我們只討論四向算法。只要把搜索方向從四個(gè)改變到八個(gè)，即可得到八向算法?？梢允褂脳＝Y(jié)構(gòu)來(lái)實(shí)現(xiàn)簡(jiǎn)單的種子填充算法。算法原理為：種子像素入棧。具體地，當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：第73頁(yè)/共152頁(yè)第七十三頁(yè)，共153頁(yè)。(1)棧頂像素出棧；

(2)將出棧像素置成填充色；

(3)按左、上、右、下順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界上且未置成填充色，則把該像素入棧；若其中某個(gè)像素值與填充色相同，說(shuō)明該像素已填充過(guò)或者該像素就是邊界上的像素(當(dāng)填充色與邊界色相同時(shí))，這時(shí)像素不入棧。上述算法也可以用于填充帶有內(nèi)孔的平面區(qū)域。第74頁(yè)/共152頁(yè)第七十四頁(yè)，共153頁(yè)。

簡(jiǎn)單的種子填充算法把太多的像素壓入堆棧，有些像素甚至?xí)霔６啻?，這一方面降低了算法的效率，另一方面還要求很大的存儲(chǔ)空間以實(shí)現(xiàn)棧結(jié)構(gòu)，解決這個(gè)問(wèn)題的一個(gè)辦法是，在任意一個(gè)掃描線與多邊形相交的區(qū)間(含若干個(gè)連續(xù)像素)上，只取一個(gè)種子像素。相應(yīng)的算法稱為掃描線種子填充算法，算法原理為：種子像素入棧。具體地，當(dāng)棧非空時(shí)作如下四步操作：

(1)棧頂像素出棧；第75頁(yè)/共152頁(yè)第七十五頁(yè)，共153頁(yè)。(2)在區(qū)間上，沿掃描線對(duì)出棧像素的左右像素進(jìn)行填充，直至遇到邊界像素為止，即每出棧一個(gè)像素，就對(duì)包含該像素的整個(gè)區(qū)間進(jìn)行填充；

(3)上述區(qū)間內(nèi)最左、最右的像素分別記為xl和xr；

(4)在區(qū)間［xl,xr］中，檢查與當(dāng)前掃描線相鄰的上下兩條掃描線的有關(guān)像素是否全為邊界像素或已填充的像素，若存在非邊界、未填充的像素，則把每一區(qū)間的最右像素取作種子像素入棧。第76頁(yè)/共152頁(yè)第七十六頁(yè)，共153頁(yè)。3.區(qū)域填充圖案前面介紹的區(qū)域填充算法，把區(qū)域內(nèi)部的像素全部置成同一種顏色。但在實(shí)際應(yīng)用中，有時(shí)需要用一種圖案來(lái)填充平面區(qū)域。這可以通過(guò)對(duì)前述掃描線算法中寫(xiě)像素的部分稍作修改來(lái)實(shí)現(xiàn)：在確定了區(qū)域內(nèi)一像素之后，不是馬上往該像素填色，而是先查詢圖案位圖的對(duì)應(yīng)位置。若是以透明方式填充圖案，則當(dāng)圖案位圖對(duì)應(yīng)位置為1時(shí)，用前景色寫(xiě)像素，否則，不改變?cè)撓袼氐闹?。而若以不透明方式填充圖案，則視圖案位圖對(duì)應(yīng)位置為1或0來(lái)決定是用前景色還是背景色去寫(xiě)像素。第77頁(yè)/共152頁(yè)第七十七頁(yè)，共153頁(yè)。

進(jìn)行圖案填充時(shí)，在不考慮圖案旋轉(zhuǎn)的情況下，必須確定區(qū)域與圖案之間的位置關(guān)系。這可以通過(guò)把圖案原點(diǎn)與圖形區(qū)某點(diǎn)對(duì)齊的辦法來(lái)實(shí)現(xiàn)。對(duì)齊方式有兩種。第一種方式是把圖案原點(diǎn)與填充區(qū)域邊界或內(nèi)部的某點(diǎn)對(duì)齊。用第一種方式填充的圖案，將隨著區(qū)域的移動(dòng)而跟著移動(dòng)，看起來(lái)很自然。對(duì)于多邊形，可取區(qū)域邊界上最左邊的頂點(diǎn)。而對(duì)于圓和橢圓這樣的具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點(diǎn)(如中心)對(duì)應(yīng)圖案原點(diǎn)。第78頁(yè)/共152頁(yè)第七十八頁(yè)，共153頁(yè)。

第二種對(duì)齊方式是整除取余方式。假定圖案是一個(gè)M×N位圖，用M×N數(shù)組存放。M、N一般比需要填充的區(qū)域的尺寸小得多。所以圖案總是設(shè)計(jì)成周期性的，使之能通過(guò)重復(fù)使用，構(gòu)成任意尺寸的圖案。當(dāng)需要填充的區(qū)域與當(dāng)前掃描線的相交區(qū)間確定之后，假定相交區(qū)間上一像素坐標(biāo)為(x,y)，則其與圖案位圖上的對(duì)應(yīng)位置為(x%M,y%N)，其中%為C語(yǔ)言整除取余運(yùn)算符。當(dāng)然，在圖形填充時(shí)，若設(shè)備驅(qū)動(dòng)程序提供一次寫(xiě)多個(gè)連續(xù)像素的指令時(shí)，也可以利用區(qū)間連貫性，把區(qū)間上的像素按一個(gè)周期一個(gè)周期地填充。例如，假設(shè)圖案是16×16位圖，那么每個(gè)周期為16。第79頁(yè)/共152頁(yè)第七十九頁(yè)，共153頁(yè)。

如果區(qū)間左端點(diǎn)對(duì)應(yīng)圖案的左邊緣，即x坐標(biāo)除以16余為0，且區(qū)間長(zhǎng)度超過(guò)16，那么可以一次把圖案的一行直接寫(xiě)到區(qū)間的一組對(duì)應(yīng)像素上去。如果區(qū)間剩余長(zhǎng)度還超過(guò)16，那么就把圖案的一行再寫(xiě)到區(qū)間的對(duì)應(yīng)部分。這樣一直重復(fù)下去，直至把整個(gè)區(qū)間填滿。如果區(qū)間的左端點(diǎn)或右端點(diǎn)并不剛好對(duì)應(yīng)于圖案的邊緣，那么可先把區(qū)間的首或末周期內(nèi)不屬于區(qū)域的像素屏蔽起來(lái)，再執(zhí)行上述多像素寫(xiě)操作。從算法復(fù)雜性看，第二種對(duì)齊方式比較簡(jiǎn)單，并且在相鄰區(qū)域用同一圖案填充時(shí)，可以達(dá)到無(wú)縫連接的效果。但是它有一個(gè)潛在的毛病，即當(dāng)區(qū)域移動(dòng)時(shí)，圖案不會(huì)跟著移動(dòng)。其結(jié)果是區(qū)域內(nèi)的圖案變了。第80頁(yè)/共152頁(yè)第八十頁(yè)，共153頁(yè)。

有些反復(fù)使用的圖符以及一些應(yīng)用系統(tǒng)常用的特殊符號(hào)，若按第二種對(duì)齊方式下填充圖案的方法，則每填一次圖形就必須進(jìn)行掃描轉(zhuǎn)換一次。如果在系統(tǒng)啟動(dòng)時(shí)就對(duì)圖形掃描轉(zhuǎn)換填充圖案，并把圖形各像素的值存起來(lái)，以后每次生成時(shí)直接讀出，并寫(xiě)到指定位置，可以大大提高系統(tǒng)效率。為了提高以后每次填充的速度，可構(gòu)造圖符的包圍盒矩形，把含于包圍盒，但不在圖符區(qū)域內(nèi)部的像素用0表示，把圖符區(qū)域內(nèi)部的像素用非零的顏色值表示，在需要填充圖符時(shí)，以透明方式寫(xiě)矩形：for(i=0;i<矩形寬；i++)for(j=0;j<矩形高；j++)if(symbol［i,j］)drawpixel(i0+i,j0+j,symbol［i,j］);第81頁(yè)/共152頁(yè)第八十一頁(yè)，共153頁(yè)。

有些圖符僅由0、1構(gòu)成，1代表前景色，0代表背景色，每個(gè)像素僅占一位。這時(shí)若采用上述寫(xiě)矩形的方法，則不僅不屬于圖符的部分是透明的，而且矩形中屬于圖符，但用背景色表示的部分像素也透明了。如圖3.3.6(a)所示，圖符與原有圖形混在一起了。這個(gè)問(wèn)題有兩種解決辦法，一是用不透明方式寫(xiě)，即當(dāng)矩形中像素值為0時(shí)，不管像素屬于圖符與否，統(tǒng)統(tǒng)用背景色改寫(xiě)屏幕像素，結(jié)果如圖3.3.6(b)所示。屏幕上原有圖形中不該清除的部分也被清除了?？梢?jiàn)，簡(jiǎn)單地用透明或不透明方式都不能產(chǎn)生理想的結(jié)果(圖3.3.6(c))。為了得到圖3.3.6(c)的填充效果，可采用掃描轉(zhuǎn)換與填充圖案分開(kāi)的辦法進(jìn)行。掃描轉(zhuǎn)換時(shí)，對(duì)圖符輪廓線圖(圖3.3.7(a))處理一次，得一位圖(圖3.3.7(b))。用透明方式寫(xiě)位圖矩陣得圖3.3.7(c)。再把位圖(圖3.3.7(b))和圖案(圖3.3.7(d))進(jìn)行與(AND)運(yùn)算得圖3.3.7(e)。再用透明方式寫(xiě)矩陣3.3.7(e)即得理想結(jié)果(圖3.3.6(c))。第82頁(yè)/共152頁(yè)第八十二頁(yè)，共153頁(yè)。圖3.3.6把一圖符加入圖形的三種方案第83頁(yè)/共152頁(yè)第八十三頁(yè)，共153頁(yè)。圖3.3.7用二次寫(xiě)方式繪制圖符第84頁(yè)/共152頁(yè)第八十四頁(yè)，共153頁(yè)。

目前的C語(yǔ)言軟件都向用戶提供了定義圖案(或稱模板、掩碼(mask))和填充圖案的功能。如在MicrosoftC/C++軟件中，定義圖案的函數(shù)為-setfillmask。其中，參數(shù)mask(即掩碼數(shù)組)是8×8位的數(shù)組，每一位代表一個(gè)像素。值為1的位，將相應(yīng)像素設(shè)置成當(dāng)前顏色；值為0的位，則不改變?cè)袼刂?。而在一些CAD系統(tǒng)(AutoCAD)中，圖案的定義則采用矢量(即幾何)參數(shù)形式，圖案可看作是由幾組帶間隔的平行線構(gòu)成的。圖案填充的思想較簡(jiǎn)單，將每組平行線按剖面線方式填充，按順序?qū)⑺衅叫芯€填完后就得到了在區(qū)域內(nèi)要填充的圖案。第85頁(yè)/共152頁(yè)第八十五頁(yè)，共153頁(yè)。3.4線寬與線型的生成1.直線線寬的生成要產(chǎn)生具有寬度的線，可以順著掃描所生成的單像素線條軌跡，移動(dòng)一把具有一定寬度的“刷子”來(lái)獲得，“刷子”的形狀可以是一條線段或一個(gè)正方形。也可以采用區(qū)域填充的辦法間接地產(chǎn)生有寬度的線(如AutoCAD系統(tǒng)即是)。線刷子的原理最簡(jiǎn)單。假設(shè)直線斜率在［-1,1］之間，這時(shí)可以把刷子置成垂直方向，刷子的中點(diǎn)對(duì)準(zhǔn)直線一端點(diǎn)，然后讓刷子中心往直線的另一端移動(dòng)，即可“刷出”具有一定寬度的線。當(dāng)直線斜率不在［-1,1］之間時(shí)，把刷子置成水平方向。具體實(shí)現(xiàn)刷子時(shí)，只要對(duì)直線掃描轉(zhuǎn)換算法稍作修改即可。例如，當(dāng)直線斜率在［-1,1］之間時(shí)，把每步迭代所得的點(diǎn)的上、下方半線寬之內(nèi)的像素全部置成直線顏色。如圖3.4.1所示為線寬是5個(gè)像素的情形。第86頁(yè)/共152頁(yè)第八十六頁(yè)，共153頁(yè)。圖3.4.1用線刷子繪制的具有寬度的線第87頁(yè)/共152頁(yè)第八十七頁(yè)，共153頁(yè)。圖3.4.2線刷子所產(chǎn)生的缺口第88頁(yè)/共152頁(yè)第八十八頁(yè)，共153頁(yè)。

算法簡(jiǎn)單、效率高是線刷子的優(yōu)點(diǎn)。但是，線的始末端總是水平或垂直的。因此，當(dāng)線寬較大時(shí)，看起來(lái)很不自然。當(dāng)比較接近水平的線與比較接近垂直的線匯合時(shí)，匯合處外角將有缺口，如圖3.4.2所示。再者，斜線與水平(或垂直)線不一樣粗。對(duì)于水平線或垂直線，刷子與線條垂直，因而最粗，其粗細(xì)與指定線寬相等；而對(duì)于45°斜線，刷子與線條成45°角，粗細(xì)僅為指定線寬的 倍。線刷子還有另一個(gè)問(wèn)題：當(dāng)線寬為偶數(shù)個(gè)像素時(shí)，用上述方法繪制的線條要么粗一個(gè)像素，要么細(xì)一個(gè)像素。第89頁(yè)/共152頁(yè)第八十九頁(yè)，共153頁(yè)。

為了生成有寬度的線，還可以用正方形的刷子。把邊寬為指定線寬的正方形的中心沿直線作平行移動(dòng)，即可獲得具有線寬的線條，如圖3.4.3所示為用正方形刷子繪制的具有寬度的線條。比較圖3.4.3與圖3.4.1可知，用正方形刷子所得的線條比用線刷子所繪制的線條要粗一些。與線刷子類似，用正方形刷子繪制的線條始末端也是水平或垂直的，且線寬與線條方向有關(guān)。與線刷子的情形相反，對(duì)于水平線與垂直線，線寬最小，而對(duì)于斜率為±1的線條，線寬最大，為垂直(水平)線寬度的倍。第90頁(yè)/共152頁(yè)第九十頁(yè)，共153頁(yè)。圖3.4.3第91頁(yè)/共152頁(yè)第九十一頁(yè)，共153頁(yè)。

實(shí)現(xiàn)正方形刷子最簡(jiǎn)單的辦法是：把正方形中心依次對(duì)準(zhǔn)單像素寬的線條上各個(gè)像素，并把正方形內(nèi)的像素全部置成線條顏色。這種簡(jiǎn)單方法將會(huì)重復(fù)地寫(xiě)像素。這是因?yàn)閷?duì)應(yīng)于相鄰兩像素的正方形一般會(huì)重疊。為了避免重復(fù)寫(xiě)像素，可以采用與有效邊表類似的技術(shù)，為每條掃描線建一個(gè)表，存放該掃描線與線條的相交區(qū)間左右端點(diǎn)位置。在每個(gè)像素使用正方形刷子時(shí)，用該正方形與各掃描線的相交區(qū)間端點(diǎn)坐標(biāo)去更新原表內(nèi)端點(diǎn)數(shù)據(jù)，圖3.4.4為刷子移動(dòng)的相鄰兩步和有關(guān)掃描線的臨時(shí)數(shù)據(jù)結(jié)構(gòu)所保存的對(duì)應(yīng)于各步的區(qū)間端點(diǎn)坐標(biāo)。生成具有寬度的線條還可以采用區(qū)域填充的算法。先算出線條各角點(diǎn)，再用直線段把相鄰角點(diǎn)連接起來(lái)，最后調(diào)用多邊形填充算法把所得的四邊形進(jìn)行填色，即得到具有寬度的線條。用這種方法還可以生成兩端粗細(xì)不一樣的線條。第92頁(yè)/共152頁(yè)第九十二頁(yè)，共153頁(yè)。圖3.4.4正方形刷子移動(dòng)的相鄰兩步對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)第93頁(yè)/共152頁(yè)第九十三頁(yè)，共153頁(yè)。

2.圓弧線寬的生成為了生成具有寬度的圓弧，可采用與直線情形類似的方法，當(dāng)采用線刷子時(shí)，在經(jīng)過(guò)曲線斜率為±1的點(diǎn)時(shí)，必須把線刷子在水平與垂直方向之間切換。由于線刷子總是置成水平或垂直的，所以在曲線接近水平與接近垂直的地方，線條更粗一些；而在斜率接近±1的點(diǎn)附近，線條更細(xì)一些，如圖3.4.5所示。當(dāng)采用正方形刷子時(shí)，無(wú)須移動(dòng)刷子方向。只需順著單像素寬的軌跡，把正方形中心對(duì)準(zhǔn)軌跡上的像素，把正方形內(nèi)的像素全部用線條顏色填充。用正方形刷子繪制的曲線條，在接近水平與垂直的部分最細(xì)，而在斜率為±1的點(diǎn)附近最粗，這恰與線刷子情形相反，如圖3.4.6所示。第94頁(yè)/共152頁(yè)第九十四頁(yè)，共153頁(yè)。圖3.4.5用線刷子繪制的圓弧第95頁(yè)/共152頁(yè)第九十五頁(yè)，共153頁(yè)。圖3.4.6用正方形刷子繪制的圓弧第96頁(yè)/共152頁(yè)第九十六頁(yè)，共153頁(yè)。

繪制具有寬度的圓弧線條也可以采用填充的辦法，先繪制圓弧線條的內(nèi)邊界和外邊界，然后在內(nèi)外邊界之間填色?？梢宰寖?nèi)外邊界都與單像素弧線軌跡距離半線寬，或把內(nèi)外邊界之一對(duì)準(zhǔn)單像素弧線軌跡，另一邊界線離開(kāi)此線一個(gè)線寬距離。如圖3.4.7所示為采用填充方法所得的圓弧線條示意圖。第97頁(yè)/共152頁(yè)第九十七頁(yè)，共153頁(yè)。圖3.4.7采用區(qū)域填充方法繪制的圓弧第98頁(yè)/共152頁(yè)第九十八頁(yè)，共153頁(yè)。3.線型的生成在繪圖應(yīng)用中常用到不同線型的線條，以便區(qū)分各種不同的意義。如采用實(shí)線表示立體線框圖中可見(jiàn)的輪廓線，用虛線表示不可見(jiàn)的輪廓線，用點(diǎn)劃線表示中心線等等。線型可以用一個(gè)布爾值的序列來(lái)存放。例如，用一個(gè)32位整數(shù)可以存放32個(gè)布爾值。用這樣的整數(shù)存放線型定義時(shí)，線型必須以32個(gè)像素為周期進(jìn)行重復(fù)?？砂聪率稣Z(yǔ)句寫(xiě)像素：if(位串［i%32］)drawpixel(x,y,color)；其中i為循環(huán)變量，在掃描轉(zhuǎn)換算法的內(nèi)循環(huán)中，每處理一個(gè)像素就遞增1，然后除以32取余。第99頁(yè)/共152頁(yè)第九十九頁(yè)，共153頁(yè)。

用這種簡(jiǎn)單辦法實(shí)現(xiàn)的線型有個(gè)毛病。因?yàn)槊课粚?duì)應(yīng)于算法的一個(gè)迭代步驟而不是線條上一個(gè)長(zhǎng)度單位，因此線型中的筆劃長(zhǎng)度與直線長(zhǎng)度有關(guān)，斜線上的筆劃長(zhǎng)度比橫向或豎向上的筆劃更長(zhǎng)。對(duì)于工程圖，這種變化是不能接受的。這時(shí)，每個(gè)筆劃應(yīng)該作為與角度無(wú)關(guān)的線段進(jìn)行計(jì)算并掃描轉(zhuǎn)換。粗線的線型計(jì)算為實(shí)的或透明的正方形，其頂點(diǎn)位置根據(jù)線型要求進(jìn)行準(zhǔn)確計(jì)算。然后對(duì)正方形進(jìn)行掃描轉(zhuǎn)換，對(duì)于垂直或水平的粗線線型，可以用寫(xiě)方塊的簡(jiǎn)單辦法進(jìn)行。第100頁(yè)/共152頁(yè)第一百頁(yè)，共153頁(yè)。3.5字符的生成

字符是指數(shù)字、字母、漢字及各種符號(hào)，用于圖形的標(biāo)注、說(shuō)明等。國(guó)際上應(yīng)用最廣的字符集是“美國(guó)信息交換用標(biāo)準(zhǔn)代碼集”(AmericanStandardCodeforInformationInterchange)簡(jiǎn)稱ASCII碼。該字符集規(guī)定了127個(gè)字符代碼。其中代碼0~31表示控制字符，代碼32~127表示英文字母、標(biāo)點(diǎn)符號(hào)、數(shù)字符號(hào)、各種運(yùn)算符以及特殊符號(hào)。每個(gè)ASCII碼用一個(gè)字節(jié)(實(shí)際上只要7位二進(jìn)制)代碼表示。第101頁(yè)/共152頁(yè)第一百零一頁(yè)，共153頁(yè)。

我國(guó)除采用ASCII碼外，還另外制訂了漢字代碼的國(guó)家標(biāo)準(zhǔn)字符集。最常用的字符集是“信息交換用漢字編碼字符集基本集”GB2312-80。該字符集包含了6000多個(gè)常用漢字、英文字母、數(shù)字和其他圖形符號(hào)，分成94個(gè)區(qū)、94個(gè)位。區(qū)碼和位碼各用一個(gè)字節(jié)(實(shí)際上只要7位二進(jìn)制)來(lái)表示。為了能識(shí)別哪些字節(jié)表示ASCII碼，哪些字節(jié)表示漢字編碼，一般采用多余的一位(最高位)來(lái)標(biāo)識(shí)。最高位為0時(shí)，表示ASCII碼，最高位為1時(shí)，表示漢字編碼。為了在終端顯示器或繪圖儀上輸出字符，系統(tǒng)中必須裝備有相應(yīng)的字符庫(kù)。字符庫(kù)中儲(chǔ)存了每個(gè)字符的形狀信息。字符庫(kù)分為矢量型和點(diǎn)陣型兩種。第102頁(yè)/共152頁(yè)第一百零二頁(yè)，共153頁(yè)。

在筆式繪圖儀上采用矢量型字符比較適合，矢量型字符庫(kù)采用矢量代碼序列表示字符的各個(gè)筆畫(huà)。輸出一個(gè)字符時(shí)，系統(tǒng)中的字符處理器解釋該字符的每個(gè)矢量代碼，輸出對(duì)應(yīng)的矢量，達(dá)到產(chǎn)生字符的目的。在終端顯示器上顯示字符一般采用點(diǎn)陣型字符庫(kù)。點(diǎn)陣型字符庫(kù)為每個(gè)字符定義一個(gè)字符掩膜，即表示該字符的像素圖案的一個(gè)點(diǎn)陣。第103頁(yè)/共152頁(yè)第一百零三頁(yè)，共153頁(yè)。

1.矢量字符與AutoCAD的形用軟件產(chǎn)生矢量字符時(shí)，應(yīng)先定義字符，把字符的筆劃數(shù)字信息按事先定義好的編碼結(jié)構(gòu)存儲(chǔ)起來(lái)，再編寫(xiě)通用程序調(diào)用和書(shū)寫(xiě)字符。定義字符時(shí)，一般在正方形的網(wǎng)格(如8×8、16×16、32×32……)紙上寫(xiě)好要定義的字符，并記錄各筆劃的頂點(diǎn)坐標(biāo)及抬、落筆信息的編碼，以一定的格式存儲(chǔ)形成編碼文件。由此可見(jiàn)，一個(gè)能產(chǎn)生字符的好的軟件需要有一套完整的定義字符的編碼系統(tǒng)。下面以AutoCAD軟件中矢量字符的生成為例加以說(shuō)明。在AutoCAD中，使用一種稱為形(Shape)的圖形實(shí)體來(lái)定義西文字符、漢字及符號(hào)等。形定義中使用直線、圓弧作為基本筆劃。第104頁(yè)/共152頁(yè)第一百零四頁(yè)，共153頁(yè)。1)形的定義格式每個(gè)形的定義由一個(gè)標(biāo)題行和若干個(gè)描述行組成，即*〈形編號(hào)〉，〈定義字節(jié)數(shù)〉，〈形名稱〉(標(biāo)題行)〈控制碼1〉，〈矢量1描述碼〉，〈矢量2描述碼〉，…，〈控制碼2〉，矢量1描述碼〉，…，〈控制碼n〉，…，0(結(jié)束碼)(描述行)第105頁(yè)/共152頁(yè)第一百零五頁(yè)，共153頁(yè)。

各項(xiàng)內(nèi)容解釋如下：形編號(hào)：每個(gè)形必須有一個(gè)編號(hào)，占用一個(gè)字節(jié)，編號(hào)范圍是0~255之間的整數(shù)值。定義字節(jié)數(shù)：定義形所需的字節(jié)總數(shù)。字節(jié)用逗號(hào)隔開(kāi)，從描述行第一個(gè)編碼開(kāi)始數(shù)，直到結(jié)束符“0”(包括該字符在內(nèi))。形名稱：每個(gè)形賦予一個(gè)名稱，即形名。形名小寫(xiě)時(shí)只起到形的一種標(biāo)志作用，而不被存入存儲(chǔ)器中。形名全部大寫(xiě)時(shí)才能被調(diào)用。第106頁(yè)/共152頁(yè)第一百零六頁(yè)，共153頁(yè)?？刂拼a：由系統(tǒng)規(guī)定的專用碼。有14個(gè)，常用碼含義如下：000形定義結(jié)束001啟動(dòng)繪圖方式(落筆)002退出繪圖方式(抬筆)008由下兩個(gè)字節(jié)給出X、Y位移(相對(duì)坐標(biāo))，繪制非標(biāo)準(zhǔn)矢量009由下面多個(gè)字節(jié)給出連續(xù)的X、Y位移來(lái)繪制非標(biāo)準(zhǔn)矢量，并必須用(0，0)結(jié)束00A(10)由下兩個(gè)字節(jié)定義八分圓弧第107頁(yè)/共152頁(yè)第一百零七頁(yè)，共153頁(yè)。2)形的描述方式直線段采用標(biāo)準(zhǔn)矢量方式和非標(biāo)準(zhǔn)矢量方式(即相對(duì)坐標(biāo)方式)來(lái)描述；圓弧用八分圓弧和非八分圓弧等方式描述。下面介紹常用的幾種形描述方式。

(1)標(biāo)準(zhǔn)矢量方式。標(biāo)準(zhǔn)矢量劃分為16個(gè)單位矢量，其方向及代碼如圖3.5.1所示，圖中各方向矢量長(zhǎng)度不同，但都作為一個(gè)單位長(zhǎng)度。字符的線段走向凡符合這16個(gè)標(biāo)準(zhǔn)方向的，用其對(duì)應(yīng)的代碼表示，線段長(zhǎng)度根據(jù)需要而定。方向及長(zhǎng)度結(jié)合起來(lái)構(gòu)成矢量描述碼。第108頁(yè)/共152頁(yè)第一百零八頁(yè)，共153頁(yè)。圖3.5.1標(biāo)準(zhǔn)矢量方向代碼第109頁(yè)/共152頁(yè)第一百零九頁(yè)，共153頁(yè)。

矢量描述碼由三位數(shù)組成(×××)。最左一位是前導(dǎo)，“0”表示十六進(jìn)制數(shù)，否則表示十進(jìn)制數(shù)。最右一位是矢量的方向代碼(大小寫(xiě)均可)。中間一位是矢量長(zhǎng)度，用矢量單位長(zhǎng)度的整數(shù)倍(1~F）表示。用標(biāo)準(zhǔn)矢量描述形時(shí)，對(duì)于非水平和非垂直方向的矢量(代碼為1，2，3，5，6，7，9，A，B，D，E，F(xiàn))，規(guī)定其大小為該矢量X與Y方向分量中長(zhǎng)度較大者。AutoCAD在用矢量描述形時(shí)，都要定義一個(gè)矢量的起點(diǎn)，該點(diǎn)稱為基點(diǎn)。第一個(gè)矢量從基點(diǎn)出發(fā)，以后的矢量(包括抬筆的空矢量)首尾相連?；c(diǎn)的另一個(gè)作用是與形調(diào)用時(shí)的插入點(diǎn)重合?？梢?jiàn)，為了以后形調(diào)用的方便應(yīng)選擇合適的基點(diǎn)。第110頁(yè)/共152頁(yè)第一百一十頁(yè)，共153頁(yè)。

在一個(gè)形定義內(nèi)，描述行的第一個(gè)控制碼缺省時(shí)，其默認(rèn)狀態(tài)為落筆(即控制碼001)。另外，一旦設(shè)置了抬筆或落筆狀態(tài)，此狀態(tài)在該形定義內(nèi)一直保持下去直到改變這種狀態(tài)為止。例如，圖3.5.2所示圖形的形定義為*10,6,RECT(標(biāo)題行)014,020,01C,028,021,0(描述行)

再如，圖3.5.3所示表面粗糙度符號(hào)的形定義為(符號(hào)的圖線采用標(biāo)準(zhǔn)矢量近似表示)*20,7,ROUG002,053,001,058,05D,0A3,0第111頁(yè)/共152頁(yè)第一百一十一頁(yè)，共153頁(yè)。圖3.5.2矩形圖例第112頁(yè)/共152頁(yè)第一百一十二頁(yè)，共153頁(yè)。圖3.5.3表面粗糙度符號(hào)第113頁(yè)/共152頁(yè)第一百一十三頁(yè)，共153頁(yè)。(2)非標(biāo)準(zhǔn)矢量方式。這種方式采用相對(duì)坐標(biāo)描述線段的長(zhǎng)度和方向。由控制碼008和009引出，緊跟其后的相對(duì)坐標(biāo)取值為-128~127的整數(shù)。這一方式完成后自動(dòng)回到標(biāo)準(zhǔn)矢量方式。例如，圖3.5.4的漢字“中”的形定義為*30,25,ZHONG002,008,(2,2),001,009,(0,4),(4,0),#;(0,-4),(-4,0),(0,0),002,008,(2,6),001,#;008,(0,-8),0

上述形定義中，相對(duì)坐標(biāo)加括號(hào)是為了增加可讀性，括號(hào)不包括在總字節(jié)數(shù)內(nèi)。標(biāo)準(zhǔn)矢量方式與非標(biāo)準(zhǔn)矢量方式可以混合使用。第114頁(yè)/共152頁(yè)第一百一十四頁(yè)，共153頁(yè)。圖3.5.4用相對(duì)坐標(biāo)描述漢字第115頁(yè)/共152頁(yè)第一百一十五頁(yè)，共153頁(yè)。(3)八分圓弧方式。該方式由控制碼00A(10)引出，八分圓弧是指把一個(gè)整圓作八等分，如圖3.5.5表示各段圓弧的起點(diǎn)位置碼(0，1，2，…)。要求所畫(huà)弧的起點(diǎn)、終點(diǎn)必須落在等分點(diǎn)上。一段圓弧用兩個(gè)字節(jié)描述，即

10,(半徑，(-)0SC)其中，半徑的取值為1~255。0SC前面的符號(hào)，規(guī)定以逆時(shí)針畫(huà)弧取正(省略“+”號(hào))，否則取負(fù)。S為圓弧起點(diǎn)位置碼；C為圓弧跨過(guò)八分弧的個(gè)數(shù)，取值為0~7，畫(huà)整圓時(shí)取0。括號(hào)用來(lái)改善可讀性。第116頁(yè)/共152頁(yè)第一百一十六頁(yè)，共153頁(yè)。

用八分弧方式可以定義含有圓或弧的各種符號(hào)，可與其他描述方式混合使用。例如，圖3.5.6所示的基準(zhǔn)符號(hào)的形定義為*60,16,JZ#;002,038,001,060,002,014,001,068,002,030,001,0A4,10,(004,060),0

上述定義中，取圓的半徑為4個(gè)單位，中間連線長(zhǎng)度為10，下方兩條橫線長(zhǎng)均為6，用兩條靠近的線來(lái)代替一條粗線(因?yàn)樾蚊枋龅木€均為細(xì)線)。第117頁(yè)/共152頁(yè)第一百一十七頁(yè)，共153頁(yè)。圖3.5.5八分弧劃分第118頁(yè)/共152頁(yè)第一百一十八頁(yè)，共153頁(yè)。圖3.5.6基準(zhǔn)符號(hào)第119頁(yè)/共152頁(yè)第一百一十九頁(yè)，共153頁(yè)。3)形的調(diào)用用文本編輯軟件把若干個(gè)形定義放在一個(gè)形文件中，就形成了AutoCAD所使用的字符庫(kù)。形文件經(jīng)過(guò)編譯(COMPILE)、裝入(LOAD)，形調(diào)用(SHAPE)通過(guò)后，就可以隨時(shí)調(diào)用形繪出字符。第120頁(yè)/共152頁(yè)第一百二十頁(yè)，共153頁(yè)。2.點(diǎn)陣字符在點(diǎn)陣字符庫(kù)中，每個(gè)字符都定義成一個(gè)稱為字符掩膜的矩陣。矩陣中的每個(gè)元素都是一位二進(jìn)制數(shù)。該位為1時(shí)，表示字符的筆劃經(jīng)過(guò)此位，對(duì)應(yīng)于此位的像素應(yīng)置為字符顏色；該位為0時(shí)，表示字符的筆劃不經(jīng)過(guò)此位，對(duì)應(yīng)此位的像素應(yīng)置為背景色(若當(dāng)前的寫(xiě)方式是“替換”方式)或不改變(若當(dāng)前寫(xiě)方式是“與”方式)。一般認(rèn)為，定義西文字符的掩膜矩陣尺寸應(yīng)不小于5×7，而定義漢字字符的掩膜矩陣尺寸應(yīng)不小于16×16。在我國(guó)廣泛使用的微機(jī)漢字系統(tǒng)，如中文Windows等，都采用16×16點(diǎn)陣漢字作為顯示用字符，而在打印時(shí)，采用24×24，40×40甚至72×72的點(diǎn)陣字符。第121頁(yè)/共152頁(yè)第一百二十一頁(yè)，共153頁(yè)。

一個(gè)5×7西文字符點(diǎn)陣包括35個(gè)點(diǎn)，需要35b，故需要35b二進(jìn)制數(shù)(占4個(gè)多字節(jié))。一個(gè)16×16點(diǎn)陣漢字，需要256b，即32B。而一個(gè)72×72點(diǎn)陣漢字需要9×72=648B。用于打印的高分辨率點(diǎn)陣字符的掩膜位圖，可以用掃描儀輸入放大的手寫(xiě)美術(shù)字符或印刷字符，然后用交互作圖程序?qū)ξ粓D的個(gè)別像素進(jìn)行修改，使之完善。用于顯示的或用于低分辨率打印機(jī)的字符位圖可以使用交互繪圖程序，通過(guò)手工建立。用低分辨率點(diǎn)陣字符產(chǎn)生的字符一般比較粗糙，不美觀，所以在微機(jī)上通常使用幾個(gè)不同分辨率的字符庫(kù)，以滿足不同的需要。第122頁(yè)/共152頁(yè)第一百二十二頁(yè)，共153頁(yè)。3.字型技術(shù)當(dāng)應(yīng)用對(duì)輸出字符的要求較高時(shí)(如排版印刷)，需要使用高質(zhì)量的點(diǎn)陣字符。然而直接使用上一小節(jié)所介紹的點(diǎn)陣字符方法將耗費(fèi)巨大的存儲(chǔ)空間。對(duì)于GB2312-80所規(guī)定的6763個(gè)基本漢字，假設(shè)每個(gè)漢字是72×72點(diǎn)陣，那么一個(gè)字庫(kù)就需要4.4MB存儲(chǔ)空間!在實(shí)際使用時(shí)，需要多種字體(如宋體、仿宋體、黑體、楷體等)，而每種字體又需要10種以上字號(hào)。因此把每種字體、字號(hào)的字符都存儲(chǔ)成一個(gè)對(duì)應(yīng)的點(diǎn)陣，在一般情況下是不可行的。第123頁(yè)/共152頁(yè)第一百二十三頁(yè)，共153頁(yè)。

解決這個(gè)問(wèn)題一般采用壓縮技術(shù)。對(duì)字型數(shù)據(jù)壓縮后再存儲(chǔ)，使用時(shí)，將壓縮的數(shù)據(jù)還原為字符位圖點(diǎn)陣。壓縮方法有多種，最簡(jiǎn)單的是黑白段壓縮法。這種方法簡(jiǎn)單，還原快，不失真，但壓縮效果較差，使用起來(lái)也不方便，一般用于低級(jí)的文字處理系統(tǒng)中。二是部件壓縮法。這種方法壓縮比大，缺點(diǎn)是字型質(zhì)量不能保證。三是輪廓字型法(一種雙線筆劃)。這種方法壓縮比大，且能保證字符質(zhì)量，是當(dāng)今國(guó)際上最流行的一種方法，基本上也被認(rèn)為是符合工業(yè)標(biāo)準(zhǔn)化的方法。第124頁(yè)/共152頁(yè)第一百二十四頁(yè)，共153頁(yè)。

輪廓字型法采用直線或者二/三次Bézier曲線的集合來(lái)描述一個(gè)字符的輪廓線。輪廓線構(gòu)成一個(gè)或若干個(gè)封閉的平面區(qū)域。輪廓線定義加上一些指示橫寬、豎寬、基點(diǎn)、基線等的控制信息，就構(gòu)成了字符的壓縮數(shù)據(jù)。這種控制信息用于保證字符變倍時(shí)引起的字符筆劃原來(lái)的橫寬/豎寬變大變小時(shí)，其寬度在任何點(diǎn)陣情況下永遠(yuǎn)一致。采用適當(dāng)?shù)膮^(qū)域填充算法，可以從字符的輪廓線定義產(chǎn)生字符位圖點(diǎn)陣，區(qū)域填充算法可以用硬件實(shí)現(xiàn)，做在RISC集成電路板上成為光柵圖像處理器RIP(RasterImageProcessor)；也可以用軟件實(shí)現(xiàn)，寫(xiě)成一段精心編制的程序。如目前國(guó)際上廣泛使用的TrueType字體，采用的是輪廓字型法，國(guó)產(chǎn)的電子出版系統(tǒng)(如方正、華光)中的漢字字型技術(shù)也采用輪廓字型法。第125頁(yè)/共152頁(yè)第一百二十五頁(yè)，共153頁(yè)。TrueType字型技術(shù)是由Apple公司和Microsoft公司聯(lián)合開(kāi)發(fā)的，它使用二次Bézier曲線來(lái)描述字符輪廓，對(duì)字符輪廓線的控制點(diǎn)進(jìn)行編號(hào)，編號(hào)的方法是按順時(shí)針