研究生計算機圖形學

3.1直線的生成算法

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

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

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

當ε取值不同時，便形成對稱DDA法和簡單DDA法。下面以屏幕上生成直線為例來介紹這兩種算法。

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

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

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

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

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

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

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

若s≥t，則應(yīng)選Ti。第15頁/共152頁第十五頁，共153頁。第16頁/共152頁第十六頁，共153頁?，F(xiàn)在我們推導由Pi-1確定下一個像素點的遞推關(guān)系式。由于則即第17頁/共152頁第十七頁，共153頁。由于此時Δx為正，故我們可以用Δx(s-t)的正、負作為選擇Si和Ti的標準。若令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頁/共152頁第十八頁，共153頁。由于此時走步方向為x方向，即xi-xi-1=1，重寫上式得di+1=di+2Δy-2Δx(yi-yi-1)

若di≥0，即s≥t，則選Ti,此時

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

若di<0,即s<t，則選Si，此時

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

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

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

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

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

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

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

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

繪圖筆走+Δy時，新點坐標為xk+1=xk,yk+1=yk+1這時新點偏差為Fk+1=xayk+1-xk+1ya=xayk+xa-xkya=Fk+xa

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

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

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

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

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

若給定畫圓弧的條件為圓周上三點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逆時針畫弧至te(若連接P1,P2,P3構(gòu)成的兩矢量叉乘為負，則說明順時針畫弧，此時應(yīng)將P1,P3交換，就可保證逆時針畫弧)。第35頁/共152頁第三十五頁，共153頁。2.Bresenham畫圓算法算法中以圓心為坐標原點建立了局部坐標系。先考慮產(chǎn)生第一象限的八分之一圓弧，即從S(0，R)到 之間的45°圓弧，如圖3.2.1所示。設(shè)Pi-1(xi-1,yi-1)為已確定的逼近像素點。現(xiàn)在，當xi=xi-1+1時，必須決定是Ti(xi-1+1,yi-1-1)還是Si(xi-1+1,yi-1)更接近實際的圓弧。令D(Si)=［(xi-1+1)2+y2i-1］-R2

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

第36頁/共152頁第三十六頁，共153頁。

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

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

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

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

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

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

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

對第一象限的圓弧逆時針方向生成時，規(guī)定如下：當Fk≥0時，繪圖筆從當前位置沿-X方向走一步，記作-Δx；當Fk<0時，繪圖筆從當前位置沿+Y方向走一步，記作+Δy。繪圖筆走-Δx時，新點坐標為xk+1=xk-1,yk+1=yk新點偏差為第49頁/共152頁第四十九頁，共153頁。繪圖筆走+Δy時，新點坐標為新點偏差為第50頁/共152頁第五十頁，共153頁。

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

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

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

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

i=1,2,…,n

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

再如，圖3.5.3所示表面粗糙度符號的形定義為(符號的圖線采用標準矢量近似表示)*20,7,ROUG002,053,001,058,05D,0A3,0第111頁/共152頁第一百一十一頁，共153頁。圖3.5.2矩形圖例第112頁/共152頁第一百一十二頁，共153頁。圖3.5.3表面粗糙度符號第113頁/共152頁第一百一十三頁，共153頁。(2)非標準矢量方式。這種方式采用相對坐標描述線段的長度和方向。由控制碼008和009引出，緊跟其后的相對坐標取值為-128~127的整數(shù)。這一方式完成后自動回到標準矢量方式。例如，圖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

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

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

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

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

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

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

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