《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦1

光柵顯示器顯示的圖形是用一系列緊靠該圖形路徑的像素表示的。確定哪些像素能構(gòu)成所需圖形的過程稱為圖形的光柵化(也稱光柵圖形生成算法，或稱為圖形的掃描轉(zhuǎn)換)

。第3章光柵圖形生成算法《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦2圖象生成器顯示存儲器彩色表

監(jiān)視器主機CRT控制器讀/寫讀同步信號象素值顏色(亮度)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦33.1直線生成算法

3.2圓生成算法

3.3橢圓生成算法

3.4區(qū)域填充算法

3.5字符的生成

3.6反走樣技術(shù)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦43.1

直線生成算法

直線是最基本的圖元，曲線由一系列直線段逼近，復(fù)雜圖形可看作是由無數(shù)直線段組成的。直線生成質(zhì)量影響計算機圖形設(shè)計的質(zhì)量。因此，光柵化直線生成算法必須服從四條原則：直而光滑、端點準(zhǔn)確、亮度均勻、速度快。生成算法:逐點比較法、數(shù)值微分法、中點畫線法、Bresenham畫線算法等。《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦53.1.1逐點比較法

在每次畫圖過程中,繪圖筆每畫一筆，就與規(guī)定的圖形進(jìn)行比較，然后決定下一步的走向，用步步逼近的方法畫出規(guī)定的圖形。繪圖儀常用的一種方法。OXY《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦61偏差計算一般公式:

要畫的線段為OA，畫筆的當(dāng)前的位置為M。以O(shè)M，OA的斜率的大小來計算偏差。d=tg-tg=ym/xm-ya/xa=(ym*xa-ya*xm)/xm*xa；當(dāng)d<0時，表示筆在OA線段的下方，根據(jù)約定此時應(yīng)走+y一步；當(dāng)d>=0時，表示筆在OA線段的上方，應(yīng)該走+x一步。只判斷d的正負(fù),不管大小。第一象限偏差的判斷公式:

Fm=ym*xa-ya*xmXYOA(xA,yA)M(xM,yM)αβ《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦7遞推公式:

上述公式要計算兩次乘法,設(shè)法用前一點的偏差來推算走步的方向以及走步后的偏差.

筆的當(dāng)前位置為Mi(xi,yi),此時Fi=yixa-yaxi.如果Fi<0,應(yīng)走+y一步到Mi+1,即:xi+1=xi,yi+1=yi+1;Mi+1處的偏差Fi+1=yi+1xa-yaxi+1=yixa+xa-yaxi=Fi+xa;如果Fi>=0,應(yīng)走+x一步到Mi+1,即:xi+1=xi+1,yi+1=yi;Mi+1處的偏差Fi+1=yi+1xa-yaxi+1=yixa-yaxi-ya=Fi-ya;如果Fi>=0則走+x一步,此時Fi+1=Fi-ya;如果Fi<0則走+y一步,此時Fi+1=Fi+xa;《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦8

2終點判斷設(shè)繪圖機的步距為t,直線在x,y方向的增量分別為x和y.按上述運算方法,繪圖筆從直線的起點畫到終點,在x方向應(yīng)走|x/t|步,在y方向應(yīng)走|y/t|步.取n=|x/t|+|y/t|作為終點判斷的控制數(shù),并將此數(shù)存入計數(shù)器內(nèi).在x或y方向上每走一步計數(shù)器減1,當(dāng)計數(shù)器減到零時,作圖停止.xtyt《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦93.1.2

數(shù)值微分法（DDA)是基于直線微分方程生成直線的算法。直線段的兩端點坐標(biāo)為(x1，y1)、(x2，y2)，直線的截距式方程為y=kx+b,其斜率為k=dy/dx。用增量代替微分，有

k=dy/dx=△y/△x=得:即(3-1)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦10(3-1)可見，像素(xi+1，yi+1)坐標(biāo)由像素(xi，yi)坐標(biāo)遞推得到。為使直線的像素不產(chǎn)生跳躍，常對x(或y)坐標(biāo)分量用單位間隔取樣，則另一坐標(biāo)y(或x)分量計算為：當(dāng)|k|≤1時:（3-2）（3-3）當(dāng)|k|>1時:《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦11像素地址用其網(wǎng)格左下角的整數(shù)坐標(biāo)表示，對未用單位間隔取樣的分量需作取整（int）運算。DDA畫線算法(圖3-1)說明：Sign()為符號函數(shù)，其結(jié)果隨變量值為正、負(fù)、零，分別對應(yīng)取+1、-1和0。

{intsteps,i;floatdx,dy;floatx=x1;floaty=y1；if(abs(x2-x1)＞abs(y2-y1))thensteps=abs(x2-x1);/**|k|=<1**/elsesteps=abs(y2-y1);/**|k|>1**/dx=(x2-x1)／(float)steps;dy=(y2-y1)／(float)steps;for(i=0;i＜steps;i++){drawpixel(int(x+0.5sign(x))， int(y+0.5sign(y)),color);x+=dx;y+=dy;}}

《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦12在DDA算法中，涉及一次浮點數(shù)的除法、每步的浮點數(shù)加法及其取整數(shù)運算，這些影響其算法的效率。[例]從(0，0)到(3，6)的直線段。

Steps=6，dx=1/2，dy=1i0123456(xi，yi)(0，0)(.5，1)(1，2)(1.5，3)(2，4)(2.5，5)(3，6)(x，y)+.5int(x，y)(0，0)(1，1)(1，2)(2，3)(2，4)(3，5)(3，6)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦133.1.3中點畫線法（1）直線斜率｜k｜≤1的情形

起點(x1,y1)、終點(x2,y2)，直線方程為：ax+by+c=0(a=y1-y2,b=x2-x1,c=x1y2-x2y1)中點畫線法原理：令判別式:d=F(x,y)=ax+by+c

(3-4)顯然，d的符號可判斷點(x,y)與直線的相對位置關(guān)系?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦14如圖，設(shè)P(xi,yi)為過直線的當(dāng)前像素，相鄰的下一個過直線的像素是S(xi+1,yi)還是T(xi+1,yi+1)?STMM

P(xi,yi)QS(xi+1,yi)T(xi+1,yi+1)設(shè)M(xi+1,yi+0.5)為S與T的中點，Q為所畫理想直線與x=xi+1的準(zhǔn)交點,則M點坐標(biāo)代入求ddi=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦15若di＞0,M在Q的上方,取正右方S為下一個像素；若di＜0,M在Q的下方,取右上方T為下一個像素；若di=0,M與Q重合，取S或T均可，約定取正右方S為下一個像素。STMM

P(xi,yi)QS(xi+1,yi)T(xi+1,yi+1)下面求di式的增量形式di+1:

di≥0,取正右方像素(xi+1=xi+1,yi+1=yi)；若再求下一個直線上的點，得判別式增量形式：di+1=F(xi+2,yi+0.5)=a(xi+2)+b(yi+0.5)+c=di+a(3-5）式中,d增量為a《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦16di＜0,取右上方像素(xi+1=xi+1,yi+1=yi+1);同理,若再取右上方的下一個像素,得判別式增量形式:STMM

P(xi,yi)QS(xi+1,yi)T(xi+1,yi+1)di+1=F(xi+2,yi+1.5)=a(xi+2)+b(yi+1.5)+c=di+a+b

式中,d增量為a+b。求d初始值d0:直線段左端點(x1,y1)代入di式:d0=F(x1+1,y1+0.5)=a(x1+1)+b(y1+0.5)+c=a+0.5b(3-7)(3-6)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦17(2)直線斜率|k|＞1的情況與（1）同理，得到d的遞推式和初始值為:di≤0時,取正上方像素(xi+1=xi,yi+1=yi+1)有di+1=di+b

(3-8)di＞0:取右上方像素(xi+1=xi+1,yi+1=yi+1)有di+1=di+a+b

(3-9)d的初始值為

d0=0.5a+b

(3-10)為使算法只含整數(shù)運算，在算法中將d表達(dá)式(3-5)~(3-10)兩邊同乘以2，明顯改善算法運算效率?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦18算法說明:if(abs(a)＜=abs(b))/**|k|<=1**/

{while(x＜x2)/**d1=2*a+b**/

{if(d1＜0){x++;y++;d1+=twoab;}/**twoab=2(a+b)**/else{x++;d1+=twoa;}/**twoa=2a**/drawpixel(x,y,color);}

}else/**|k|>1**/

{while(y＜y2)/**d2=a+2*b**/

{if(d2＞0){x++;y++;d2+=twoab;}else{y++;d2+=twob;}/**twob=2b**/drawpixel(x,y,color);}}《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦19[例]用中點法畫（1，2）到（3，7）的直線段。

a=-5，b=2，twob=4，twoab=-6，(|k|>1)，d2(初始d0)=-1i-101234(xi+1，yi+1)(1，2)(1，3)(2，4)(2，5)(3，6)(3，7)di+1-13-31-5-1《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦203.1.4Bresenham畫線算法

是計算機圖形學(xué)領(lǐng)域中應(yīng)用最廣泛的直線掃描轉(zhuǎn)換算法。

算法原理與中點畫線法類似。(1)直線斜率0＜

k＜1情形x的變化率比y的變化率大，約定每次x方向變化一個象素單位，相應(yīng)y方向的變化量為0或1個象素單位。《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦21stP(xi,yi)S(xi+1,yi)T(xi+1,yi+1)已知直線起點(x1,y1)，終點(x2,y2)；直線上第i個選定的象素為P(xi,yi)，它是在x=xi處離直線最近的當(dāng)前像素。現(xiàn)在要決定下一個像素是S(xi+1,yi),還是T(xi+1,yi+1)?若s<t,則S靠近直線,應(yīng)該選擇S;若s>=t,則選擇T?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦22計算判別式:理論直線上點Q坐標(biāo)為y=k(xi+1)+b;求s和t:stP(xi,yi)S(xi+1,yi)T(xi+1,yi+1)Qs=y-yi=k(xi+1)+b-yi;t=(yi+1)-y=(yi+1)-k(xi+1)-b《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦23則s-t=2k(xi+1)-2yi+2b-1由于k=△y／△x,△x=x2-x1,△y=y2-y1,代入，記di=△x(s-t),得到di=2△y·xi-2△x·yi+(2△y-△x+2b△x)(3-11)因為△x＞0,故di與(s-t)同號;

di值符號為選擇下一個像素的判別因子。為得到di的增量形式,以i+1代式(3-11)的i，得

di+1=2△y·xi+1-2△x·yi+1+(2△y-△x+2b△x)(3-12)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦24將(3-12)減去(3-11),且xi+1=xi+1，得di+1=di+2△y-2△x(yi+1-yi)(3-13)其中,yi+1-yi=0或1取決于判別因子di值的符號。如果di＜0，取S為下一像素,即xi+1=xi＋1,yi+1=yi,有

di+1=di+2△y(3-14)如果di≥0，取T為下一像素,即xi+1=xi+1,yi+1=yi+1,有

di+1=di+2△y-2△x(3-15)將y1=kx1+b代入式(3-11),得di初始值:

d0=2△y-△x(3-16)

《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦25該算法僅涉及整數(shù)加法運算和左移(乘2)操作，運算效率高，易于硬件實現(xiàn)。該算法不僅適用于光柵圖形顯示器顯示圖元，還適用于數(shù)字繪圖儀的圖元輸出。《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦26Bresenham線算法示例端點為：（20，10）和（30，18），斜率為0.8

?x=10;?y=8;

d0=2?y-?x=6；2?y=16；2?y-2?x=-4------------------------------------------------------------------kpk(xk+1,yk+1)kpk(xk+1,yk+1)06(21,11)56(26,15)12(22,12)62(27,16)2-2(23,12)7-2(28,16)314(24,13)814(29,17)410(25,14)910(30,18)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦27中心在坐標(biāo)原點，半徑為整數(shù)r的圓:考慮在第一象限中,順時針從x=0到x=r/sqr(2)的圓弧段的光柵化過程。

因為圓的對稱特性。一個圓可由一個八分圓弧經(jīng)對稱獲得,所以圓的生成算法只須考慮1/8圓弧。3.2圓生成算法

3.2.1中點畫圓算法XY《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦28P(xi,yi)S(xi+1,yi)T(xi+1,yi-1)M設(shè)與圓弧最近的x=xi處的當(dāng)前像素為P(xi,yi),下一個像素是其正右方的S(xi+1,yi),還是右下方的T(xi+1,yi-1)更接近圓弧?定義函數(shù):F(x,y)=x2+y2-r2

＞0時,點(x,y)在圓邊界外則F(x,y)=0時,點(x,y)在圓邊界上＜0時,點(x,y)在圓邊界內(nèi)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦29S、T的中點M(xi+1,yi-0.5)處求值,并令判別式:di=F(M)=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-r2di＞0:M在圓外，取與圓弧更近的右下方像素T；di=0:M在圓上,任取T或S,約定取右下方像素T;

di＜0：M在圓內(nèi)，取正右方S像素為下一像素。當(dāng)di＜0時,取正右方的下一個像素,得下一個判別式:di+1=F(xi+2,yi-0.5)=di+2xi+3(3-17)若di≥0,T為下一個像素;取右下方的下一個像素,得下一個判別式:di+1=F(xi+2,yi-1.5)=di+2(xi-yi)+5(3-18)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦301/8圓弧起始點為(0,r),d的初始值為d0=F(1,r-0.5)，即

d0=1.25-r(3-19)為避免浮點數(shù)運算,令e=d0-0.25,e=1-r，d0＜0等價于e＜-0.25。e為整數(shù)，e＜-0.25等價于e＜0。中心不在原點的圓:先平移變換成原點為中心的圓光柵化;再把光柵化所得像素位置作逆平移變換.圖3-11算法中,先計算中心(xc,yc)不在坐標(biāo)原點的1/8圓弧像素點,再利用對稱性,完成整圓畫法。《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦31算法說明:while(x＜y){if(d＜0){d+=2*x+3;x++;}/*取當(dāng)前像素的正右方像素*/

else{d+=2*(x-y)+5;x++;y--;}/*取當(dāng)前像素的右下方像素*/circlepoints(xc,yc,x,y,color);}[例3-4]《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦32中點畫圓算法示例設(shè)r=7，圓心在坐標(biāo)原點

d0=1-r=-6;2x0=0;2y0=14kdk(xk+1,yk+1)2xk+12yk+10-6(1,7)2141-3(2,7)41422(3,6)6144-3(4,6)81256(5,5)1010《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦333.2.2Bresenham畫圓算法設(shè)逼近理論圓弧的最佳當(dāng)前像素是P(xi,yi)，對于下一像素，可能是正右方的S(xi+1，yi)或右下方的T(xi+1，yi-1)中取其一。ABCDEP(xi,yi)S(xi+1,yi)T(xi+1,yi-1)理論圓弧與侯選像素S、T之間的關(guān)系存在五種(從A到E)可能情況。這兩個像素分別到圓心的距離平方與理論圓(弧)的半徑平方差為D(S)=(Xi+1)2+Yi2-r2

D(T)=(Xi+1)2+(Yi-1)2-r2《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦34若|D(S)|≥|D(T)|,選像素T;否則,選像素S。令

di=|D(S)|-|D(T)|

(3-20)當(dāng)di≥0時,選像素T；當(dāng)di＜0時,選像素S。分析五種情形可知:(3-20)式的di值符號可由(3-21)式等價表示:

di=D(S)+D(T)(3-21)

為簡化di計算,推導(dǎo)di的增量形式:《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦35再以i+1代i，得di+1=(xi+1+1)2+yi+12-r2+(xi+1+1)2+(yi+1-1)2-r2若di＜0,選S,即有

xi+1=xi+1,yi+1=yi,di+1=di+4xi+6(3-22)若di≥0,選T,即有

xi+1=xi+1,yi+1=yi-1,di+1=di+4(xi-yi)+10(3-23)當(dāng)i=0，(xi,yi)=(0,r),初始值為

d0=3-2r

(3-24)《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦36該算法只包含整數(shù)運算，運算速度很快。Bresenhem畫圓算法的程序形式類似圖3-11的中點畫圓算法，只要將后者中的d初始值和條件中的兩個“d+”語句的內(nèi)容作相應(yīng)修改?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦37思考：幾種算法的共同點，給予我們什么啟發(fā)？遞推；避免乘除運算、用整數(shù)運算；硬件實現(xiàn)方法；算法的應(yīng)用領(lǐng)域。《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦38OpenGL畫點函數(shù)glBegin(GL_POINTS); glVertex*();glEnd();glBegin(GL_POINTS);glVertex2i(50,100);glVertex2i(75,150);glVertex2i(100,200);glEnd();《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦39intpoint1[]={50,100};intpoint2[]={75,150};intpoint3[]={100,200};glBegin(GL_POINTS);glVertex2iv(point1);glVertex2iv(point2);glVertex2iv(point3);glEnd();glBegin(GL_POINTS);glVertex3f(-78.05,909.72,14.60);glVertex3f(261.91,-5200.67,188,34);glEnd();《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦40OpenGL畫線函數(shù)glBegin(GL_LINES); glVertex2iv(p1); glVertex2iv(p2);glVertex2iv(p3);glVertex2iv(p4);glVertex2iv(p5);glEnd()intp1[]={50,100};intp2[]={100,100};intp3[]={100,50};intp4[]={50,50};intp5[]={150,100};《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦41《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦42多邊形First,theedgesofOpenGLpolygonscan'tintersectSecond,OpenGLpolygonsmustbeconvexpolygonswithholescan'tbedescribed.《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦43glBegin(GL_POLYGON); glVertex2f(0.0,0.0); glVertex2f(0.0,3.0); glVertex2f(3.0,3.0); glVertex2f(4.0,1.5); glVertex2f(3.0,0.0);glEnd();

《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦44《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦453.4區(qū)域填充區(qū)域是指一組相鄰而又連通、并具有相同屬性的像素集。在區(qū)域內(nèi)，生成某一屬性的實心或圖案的過程稱為區(qū)域填充。光柵系統(tǒng)有兩種區(qū)域填充算法：一種是掃描線填充算法，主要用于填充多邊形、圓、橢圓以及其它簡單曲線所圍成的封閉區(qū)域；另一種是種子填充算法，適用于具有復(fù)雜形狀邊界的區(qū)域填充?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦463.4.1掃描線多邊形填充算法

按順序計算掃描線與多邊形的相交區(qū)域，用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。P3(11,3)P4(11,8)P2(5,1)P1(2,2)P6(2,7)P5(5,5)

例如，y=6的掃描線與多邊形有四個交點，顯然，第1與第2、第3與第4間的區(qū)域落在多邊形內(nèi)，這些區(qū)間的像素填充預(yù)期的顏色?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦47填充算法四個步驟：P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)(1)求交：計算掃描線與多邊形每個邊的交點。(2)排序：把所求出的交點按x遞增（減）的順序排序。(3)交點配對：第一與第二，第三與第四等等，每對交點代表掃描線與多邊形的一個相交區(qū)域。(4)區(qū)間填色：把相交區(qū)域內(nèi)的象素設(shè)置成多邊形的顏色，把相交區(qū)域外的象素設(shè)置成背景色?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦48（1）掃描線過頂點時,如何確定交點個數(shù)？P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)2468幾個特殊問題多邊形頂點的計數(shù)方法：任取一頂點,取過該頂點兩條邊的另外兩個端點的yi(i=1,2);計算yi-y(y為該頂點的坐標(biāo)值)，按大于0的次數(shù)確定該頂點是計零次、一次，還是兩次?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦491個交點0個交點，不填充

2個交點，填充《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦50（2）多邊形邊界上的象素的取舍問題。P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)2468幾個特殊問題《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦51掃描線與水平邊界線重合時：理論上,邊界線不用考慮填充,也無需求交。但為使算法在處理問題時保持一致，將前述的頂點計數(shù)方法用于多邊形水平邊的頂點，該水平邊界線是否填充取決于兩頂點的計數(shù)結(jié)果。

按上述頂點計數(shù)方法，多邊形上方的水平邊界線將不被填充；多邊形非水平邊的局部最高的頂點計數(shù)為零次不被填充。算法保證多邊形填充時邊界“下閉上開”,同理規(guī)定多邊形邊界“左閉右開”；避免多邊形在填充前后因邊界上像素的取舍而導(dǎo)致形狀和面積的改變?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦52(3)算法的效率活性邊和活性邊表：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點x坐標(biāo)遞增的順序存儲在一個鏈表中，稱此鏈表為活性邊表。P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)2468y=6活性邊表y=7活性邊表P6P1P5P6P4P5P3P4P4P5P3P42073.5-1.5772811089288011xymaxx《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦53y=6活性邊表y=7活性邊表P6P1P5P6P4P5P3P4P4P5P3P42073.5-1.5772811089288011xymaxx邊的連貫性和掃描線的連貫性：活性邊表的每個結(jié)點存放對應(yīng)邊的有關(guān)信息： 1、x當(dāng)前掃描線與邊的交點； 2、x從當(dāng)前掃描線到下一條掃描線之間的x增量 3、ymax邊所交的最高掃描線號P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)2468《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦54012345678P2(5,1)P1(2,2)P3(11,3)P4(11,8)P6(2,7)P5(5,5)24685-32P1P2533P2P3207P1P61108P3P4528P4P55-1.57P5P6

為了方便活性邊表的建立和修改，還需建立一張新邊表。邊的y的最小值對應(yīng)的x值，x的增量，y的最大值《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦55Polygonfill(polydef,color)intcolor;多邊形定義polydef;{for(各條掃描線i）{初始化新邊表表頭指針NET[i];把ymin＝i的邊放進(jìn)新邊表NET[i];}y＝最低掃描線號；初始化活性邊表AET為空；《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦56for(各條掃描線i）{

把新邊表NET[i]中的邊結(jié)點用插入排序法插入AET

表，使其按x坐標(biāo)升序排列；遍歷AET表，把配對的交點之間的區(qū)域（左閉右開）上的象素（x,y)，用drawpiexl(x,y,color)改寫象素顏色；

遍歷AET表，把Ymax=i的結(jié)點從AET表中刪除，并把Ymax>i結(jié)點的x值遞增x;}}此邊不再與掃描線相交求下一條掃描線與邊的交點Ymax=i+1《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦57基本思想:從區(qū)域內(nèi)部已定義新值的某像素(種子)開始,搜索與該種子相鄰且位于區(qū)域內(nèi)的像素,該像素為新的種子；不斷地遞歸搜索,逐個像素填充所需顏色,直到填充完區(qū)域邊界內(nèi)的所有像素為止。3.4.2種子填充算法(1)邊界填充算法如果采用邊界定義區(qū)域，邊界上的所有像素具有某個相同的特定值(顏色或亮度)，區(qū)域內(nèi)部所有像素均具有非新值的某個給定值；這種區(qū)域內(nèi)的種子填充算法又稱邊界填充算法?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦58區(qū)域分四連通區(qū)域和八連通區(qū)域。四連通和八連通區(qū)域之間可用(從區(qū)域內(nèi)的當(dāng)前檢測像素到相鄰像素的)上述兩種不同填充方法區(qū)別。四連通和八連通區(qū)域填充法：四向/八向填充算法八向填充算法除了可填充八連通區(qū)域外，還可填充四連通區(qū)域；但四向填充算法只能填充四連通區(qū)域?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦59《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦60(2)漫溢填充算法區(qū)域邊界若不具有單一的顏色,就無法用邊界填充算法對它們填充。在這種情況下,若區(qū)域內(nèi)部所有像素均具有某個相同的特定值，區(qū)域外的所有像素具有其它不同的值，這種區(qū)域稱內(nèi)定義區(qū)域。其中的種子填充算法叫漫溢填充算法。漫溢填充算法也分四向填充算法和八向填充算法?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦61若內(nèi)定義區(qū)域中具有多種內(nèi)部顏色,首先預(yù)設(shè)置像素值,使所有的內(nèi)部像素具有相同的顏色,然后再用四向或八向填充算法把當(dāng)前區(qū)域內(nèi)的像素都予新值。《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦62內(nèi)定義區(qū)域的四向填充算法如圖3-24，newcolor為區(qū)域內(nèi)填充的新值,oldcolor為區(qū)域內(nèi)各像素的原值。將該算法作適當(dāng)修改可得到八向漫溢填充算法。Flood-fill-4(x,y,newcolor,oldcolor)intx,y,newcolor,oldcolor;{if(getpixel(x,y)==oldcolor){putpixel(x,y,newcolor,oldcolor);flood-fill-4(x,y+1,newcolor,oldcolor);flood-fill-4(x,y-1,newcolor,oldcolor);flood-fill-4(x+1,y,newcolor,oldcolor);flood-fill-4(x-1,y,newcolor,oldcolor);}}《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦633.4.3區(qū)域填充屬性區(qū)域填充屬性是軟件系統(tǒng)提供用戶對已定義的圖形區(qū)域(可包含邊界)填充自己所選擇的圖形內(nèi)容的一種功能。一般區(qū)域填充屬性包括填充模式填充顏色填充圖案《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦64(1)填充模式常見的有三種基本形式：空心的、實心的和選定圖案。TurboC中由函數(shù)Setfillstyle(intpattern,intcolor)設(shè)置填充模式和填充顏色。pattern——定義填充模式類型

Empty_Fill 以背景色填充

Solid_Fill 以某一單色填充

Xhatch_Fill 以斜網(wǎng)格填充填充函數(shù)：矩形bar(),多邊形fillpoly()等?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦65(2)填充顏色

Color是定義區(qū)域邊界或區(qū)域內(nèi)部填充顏色的參數(shù)，例如，對于空心區(qū)域，只有在邊界輪廓上顯示所指定的填充顏色；對于實心區(qū)域包括具有圖案的區(qū)域，將以填充顏色顯示區(qū)域內(nèi)部，也可包含其邊界?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦66是指把用戶預(yù)先定義的所需圖案填充到指定的區(qū)域中。在TurboC中，用戶可用函數(shù)Setfillpattern(charfar*upattern,intcolor)自行定義圖案并作為填充模式。upattern是指向連續(xù)8字節(jié)的指針，每個字節(jié)與8個像素相對應(yīng)，只要其中某個字節(jié)的某一位置被置為1，對應(yīng)像素將以color值所對應(yīng)的顏色被顯示；若某一位被置為0，不改變原像素顏色。(3)填充圖案《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦673.5字符的生成字符生成是計算機圖形學(xué)中圖元生成的基本內(nèi)容之一,是字處理/電子出版/計算機繪圖等應(yīng)用領(lǐng)域的一種基礎(chǔ)技術(shù)。字符包括ASCII碼字符和漢字字符。ASCII碼字符集共有127個字符代碼,包含字母/數(shù)字/標(biāo)點/運算等符號。漢字字符由我國國家標(biāo)準(zhǔn)局制訂實施的“信息交換用漢字編碼字符基本集”(GB2312-80),收集的常用國標(biāo)一級漢字(3755個)、國標(biāo)二級漢字(3008個)以及其它圖形符號所規(guī)定。

《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦68在計算機內(nèi)，把字符形狀描述信息按其編碼排列順序記錄下來的一張表，稱為字符庫。字符庫分為矢量型和點陣型兩種。字符的生成過程：按字符編碼、字體,讀出字形描述信息;按字形描述信息及輸出設(shè)備類型,還原該字符原始形狀(點陣或矢量表示);修飾處理字符形狀及大小、方向等;在指定設(shè)備上輸出該字符?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦69

定義矢量字符，首先要寫字模(即把字符的筆劃、形狀定位在一標(biāo)準(zhǔn)模板上)；再編字符代碼，然后存入字符庫。例如:選用一個大小為８×８倍數(shù)的正方形網(wǎng)格作為寫字的模板,相對于網(wǎng)格左下角點(0,0)的坐標(biāo)值對字符的每一筆劃采集其兩端點或更多的中間點,編碼整個字符所有筆劃的相對軌跡。3.5.1矢量字符《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦70ABCDEFGHID(Down)落筆，U(Up)抬筆。編碼字符軌跡：U，D(xa,ya),(xb,yb),U,D(xc,yc),(xd,yd),(xe,ye),(xf,yf),(xg,yg),U,D(xe,ye),(xh,yh),(xi,yi).《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦71AutoCAD中的TXT.SHP文件是通過形定義描述字符庫的，其ASCII碼字符在形定義時，先把線條筆劃分割，再按其長度、方向以及起落筆進(jìn)行編碼；同樣，通過形定義描述漢字，建立所需的矢量漢字庫。

《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦72NESWNEESSWWNABCDEFD(Down)落筆，U(Up)抬筆。編碼字符軌跡：U，D,E6,U,D,S3,SW5.24,U,D,ES5.24.筆畫方向定義《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦73目前普遍使用輪廓方式定義的矢量字符，字符形狀的輪廓線用一組有向折線/或用直線段與光滑的二、三次Bezier曲線段組合描述。大大大大大大大大《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦74建立字符庫后,為了節(jié)省存儲空間和能迅速查找,需要對字符庫進(jìn)行壓縮,如采用二進(jìn)制記錄格式,或定長記錄格式等壓縮技術(shù)存儲字模?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦75在光柵掃描顯示系統(tǒng)中是通過字符掩膜定義的。字符掩膜就是包含顯示字符圖案的一塊光柵。對于黑白顯示器,掩膜中的每個像素被一位二進(jìn)制數(shù)定義;對于彩色或可顯示灰度的顯示器,掩膜中的像素可用多位二進(jìn)制數(shù)定義表示色彩的濃淡或灰度的等級。(若將字符掩膜中的每個像素值均置成背景色,表示該字符在屏幕上被擦除。)

字符掩膜只是幀緩存器所對應(yīng)的顯示器光柵的一小塊，它的坐標(biāo)原點在幀緩存器中有對應(yīng)的坐標(biāo)。所以,字符在掩膜上的表示實際上是寫到幀緩存器中的。3.5.2點陣字符《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦76圖圖《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦77點陣字符最適合于光柵掃描輸出設(shè)備，其字符生成過程簡單、快速，但不同字號大小的字形不能保持一致的質(zhì)量，字符庫容量大,占用很大存儲空間。目前在廣為使用的壓縮字符庫中，將點陣字符方式與矢量字符輪廓方式描述相結(jié)合，生成字形輪廓是矢量方式的，輪廓內(nèi)部以點陣方式填充的字符，獲得滿意的效果?！秷D形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦783.5.3字符的顯示在光柵顯示器上輸出字符，不管是矢量型的還是點陣型的，圖形標(biāo)準(zhǔn)或一般的軟件系統(tǒng)通常都用各自統(tǒng)一的函數(shù)提供字符生成顯示的功能，通過參數(shù)選擇來控制字符的字體、大小、顏色、方向等屬性。例如,在TurboC圖形模式下，用函數(shù)Settextstyle(font,direction,charsize)設(shè)置文本的字體、方向及大小。其中，參數(shù)font可設(shè)置一個整數(shù)值(０~４)選擇指定字體,包括點陣字體或不同式樣的矢量字體；direction可設(shè)置整數(shù)值(0~1)選擇水平或垂直的顯示方向；charsize可控制點陣或矢量字符大小(１《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦79~１０)，若該參數(shù)取0值，只控制矢量字體，且通過函數(shù)Setusercharsize(multx,dirx,multy,diry)中的兩個參數(shù)比值multx／dirx、multy／diry縮放字體的寬度和高度來實現(xiàn)對矢量字體大小的控制.最后,調(diào)用函數(shù)Outtext(*textstring)或Outtextxy(x,y,*textstring)在屏幕上以當(dāng)前前景色在當(dāng)前位置或指定的(x,y)位置顯示字符串textstring所指定的文本.《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦80OpenGL繪圖屬性glPointSize(GLfloatsize)；glLineWidth(GLfloatwidth);glLineStipple(1,0x3F07);glEnable(GL_LINE_STIPPLE);《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦81PolygonsasPoints,Outlines,orSolidsglPolygonMode(GL_FRONT,GL_FILL);glPolygonMode(GL_BACK,GL_LINE);GL_FRONT_AND_BACK,GL_FRONTGL_POINT,GL_LINE,orGL_FILL《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦82Bydefault,filledpolygonsaredrawnwithasolidpattern.Theycanalsobefilledwitha32-bitby32-bitwindow-alignedstipplepattern,whichyouspecifywithglPolygonStipple().voidglPolygonStipple(constGLubyte*mask);GLubytefly[]={0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x03,0x80,0x01,0xC0,0x06,0xC0,0x03,0x60,0x04,0x60,0x06,0x20,0x04,0x30,0x0C,0x20,0x04,0x18,0x18,0x20,0x04,0x0C,0x30,0x20,0x04,0x06,0x60,0x20,0x44,0x03,0xC0,0x22,0x44,0x01,0x80,0x22,0x44,0x01,0x80,0x22,0x44,0x01,0x80,0x22,0x44,0x01,0x80,0x22,0x44,0x01,0x80,0x22,0x44,0x01,0x80,0x22,0x66,0x01,0x80,0x66,0x33,0x01,0x80,0xCC,0x19,0x81,0x81,0x98,0x0C,0xC1,0x83,0x30,0x07,0xe1,0x6274,0xe0,0x03,0x3f,0xfc,0xc0,0x03,0x31,0x8c,0xc0,0x03,0x33,0xcc,0xc0,0x06,0x64,0x26,0x60,0x0c,0xcc,0x33,0x30,0x18,0xcc,0x33,0x18,0x10,0xc4,0x23,0x08,0x10,0x63,0xC6,0x08,0x10,0x30,0x0c,0x08,0x10,0x18,0x18,0x08,0x10,0x00,0x00,0x08};GLubytehalftone[]={0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55,0xAA,0xAA,0xAA,0xAA,0x55,0x55,0x55,0x55};glEnable(GL_POLYGON_STIPPLE);glPolygonStipple(fly);glRectf(125.0,25.0,225.0,125.0);glPolygonStipple(halftone);glRectf(225.0,25.0,325.0,125.0);glDisable(GL_POLYGON_STIPPLE);《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦83位圖和字符位圖是以元素值為0或1的矩陣形式存儲的，通常用于對窗口中相應(yīng)區(qū)域的繪圖屏蔽。比如說，當(dāng)前顏色設(shè)置為紅色，則在矩陣元素值為1的地方象素用紅色來取代，反之，在為0的地方，對應(yīng)的象素不受影響。位圖普遍用于字符顯示，《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦84采用顯示列表方式繪圖一般要比立即執(zhí)行方式快，尤其是顯示列表方式可以大量地提高網(wǎng)絡(luò)性能，即當(dāng)通過網(wǎng)絡(luò)發(fā)出繪圖命令時，由于顯示列表駐留在服務(wù)器中，因而使網(wǎng)絡(luò)的負(fù)擔(dān)減輕到最小。另外，在單用戶的機器上，顯示列表同樣可以提高效率。因為一旦顯示列表被處理成適合于圖形硬件的格式，則不同的OpenGL實現(xiàn)對命令的優(yōu)化程度也不同。例如旋轉(zhuǎn)矩陣函數(shù)glRotate*()，若將它置于顯示列表中，則可大大提高性能。因為旋轉(zhuǎn)矩陣的計算并不簡單，包含有平方、三角函數(shù)等復(fù)雜運算，而在顯示列表中，它只被存儲為最終的旋轉(zhuǎn)矩陣，于是執(zhí)行起來如同硬件執(zhí)行函數(shù)glMultMatrix()一樣快。一般來說，顯示列表能將許多相鄰的矩陣變換結(jié)合成單個的矩陣乘法，從而加快速度。

顯示列表《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦85OpenGL提供類似于繪制圖元的結(jié)構(gòu)即glBegin()與glEnd()的形式創(chuàng)建顯示列表，其相應(yīng)的函數(shù)為：

voidglNewList(GLuintlist,GLenummode);

說明一個顯示列表的開始，其后的OpenGL函數(shù)存入顯示列表中，直至調(diào)用結(jié)束表的函數(shù)（見下面）。參數(shù)list是一個正整數(shù)，它標(biāo)志唯一的顯示列表。參數(shù)mode的可能值有GL_COMPILE和GL_COMPILE_AND_EXECUTE。若要使后面的函數(shù)語句只存入而不執(zhí)行，則用GL_COMPILE；若要使后面的函數(shù)語句存入表中且按瞬時方式執(zhí)行一次，則用GL_COMPILE_AND_EXECUTE。

voidglEndList(void);

標(biāo)志顯示列表的結(jié)束。

《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦86DisplayListsdrawCircle(){GLinti;GLfloatcosine,sine;glBegin(GL_POLYGON);for(i=0;i<100;i++){cosine=cos(i*2*PI/100.0); sine=sin(i*2*PI/100.0); glVertex2f(cosine,sine);}glEnd();}drawCircle(){GLinti;GLfloatcosine,sine;staticGLfloatcircoords[100][2];staticGLintinited=0;if(inited==0){inited=1;for(i=0;i<100;i++){circcoords[i][0]=cos(i*2*PI/100.0);circcoords[i][1]=sin(i*2*PI/100.0);}}glBegin(GL_POLYGON);for(i=0;i<100;i++)glVertex2fv(&circcoords[i][0]);glEnd();}《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦87#defineMY_CIRCLE_LIST1buildCircle(){GLinti;GLfloatcosine,sine;glNewList(MY_CIRCLE_LIST,GL_COMPILE);glBegin(GL_POLYGON);for(i=0;i<100;i++){cosine=cos(i*2*PI/100.0);sine=sin(i*2*PI/100.0);glVertex2f(cosine,sine);}glEnd();glEndList();}NotethatthecodefordrawingacircleisbracketedbyglNewList()andglEndList().Asyoumighthaveguessed,thesecommandsdefineadisplaylist.TheargumentMY_CIRCLE_LISTforglNewList()isanintegerindexthatuniquelyidentifiesthisdisplaylist.YoucanexecutethedisplaylistlaterwiththisglCallList()command:glCallList(MY_CIRCLE_LIST);《圖形學(xué)與虛擬環(huán)境》鄭州大學(xué)信息工程學(xué)院趙新燦88GLuintglGenLists(Glsizeirange);GLbooleanglIsList(GLuintlist);ReturnsTRUEiflistisalreadyusedforadisplaylistandFALSEotherwise.voidglCallList(GLuintlist);

執(zhí)行顯示列表。