第3章+基本圖形元素生成算法.ppt

1、第 3 章 基本圖形元素生成算法,3.1 直線的掃描轉(zhuǎn)換 3.2 圓和橢圓的掃描轉(zhuǎn)換 3.3 區(qū)域填充 3.4 字符的生成 3.5 圖形裁剪 3.6 屬性控制 3.7 反走樣 習(xí)題,3.1 直線的掃描轉(zhuǎn)換,3.1.1 DDA算法 DDA算法是根據(jù)直線的微分方程來計(jì)算x或y生成直線的掃描轉(zhuǎn)換算法。 在一個坐標(biāo)軸上以單位間隔對線段取樣, 以決定另一個坐標(biāo)軸方向上最靠近理想線段的整數(shù)值。,設(shè)(x0, y0)為直線段的始點(diǎn), (x1, y1)為直線段的終點(diǎn), 且端點(diǎn)坐標(biāo)均為整數(shù), 則直線的微分方程為,設(shè)|k|1, 則有 yi+1=kxi+1+b=k(xi+x)+b=yi+kx 上式表明, 若x=1,

2、則當(dāng)x每遞增1時(shí), y遞增k。 掃描轉(zhuǎn)換開始時(shí), 取直線始點(diǎn)(x0, y0)作為初始坐標(biāo)。 算法描述如下:,k為直線的斜率,void DDA-line(x0, y0, x1, y1, color) int x0, y0, x1, y1, color; int x; float y, k, deltx, delty; deltx=x1-x0; delty=y1-y0; k=deltydeltx; y=y0; for(x=x0; x=x1; x+) putpixel(x, int(y+0.5), clolor); y=y+k; ,3.1.2 中點(diǎn)畫線法 為了討論的方便, 假定直線的斜率在01之間,

3、 其它情況參照下述討論進(jìn)行處理。 假設(shè)直線的起點(diǎn)和終點(diǎn)分別為(x0, y0)和(x1, y1), 則直線方程為 F(x, y)=ax+by+c=0,其中, a=y0-y1, b=x1-x0, c=x0y1-x1y0。 對于直線上的點(diǎn), F(x,y)=0; 對于直線上方的點(diǎn), F(x,y)0; 而對于直線下方的點(diǎn), F(x,y)0。 如圖3.1所示, 若直線在x方向上增加一個單位, 則在y方向上的增量只能在0和1之間。 假設(shè)橫坐標(biāo)為xP的各像素點(diǎn)中最佳逼近于理想直線的像素為(xP,yP), 用實(shí)心小圓表示。 那么, 下一個與直線最近的像素只能是正右方的P1(xP+1,yP)或右上方的P2(xP+

4、1, yP+1)兩者之一, 用空心小圓表示。 我們用P1和P2的中點(diǎn)M(xP+1, yP+0.5)與理想直線的位置關(guān)系來判定。,圖3.1 中點(diǎn)畫線示意圖,設(shè)Q是理想直線與垂直線x=xP+1的交點(diǎn)。 若M在Q的下方, 則P2離理想直線近, 應(yīng)取為下一個像素; 否則應(yīng)取P1。 為此, 我們構(gòu)造判別式 d=F(M)=F(xP+1,yP+0.5)=a(xP+1)+b(yP+0.5)+c 當(dāng)d0時(shí), M在直線上方, 則應(yīng)取正右方的P1; 當(dāng)d=0時(shí), 約定取正右方的P1。,下面我們討論如何計(jì)算判別式d。 由于d是xP和yP的線性函數(shù), 因而可以采用增量方法計(jì)算, 以提高運(yùn)算效率。 當(dāng)d0時(shí), 取正右方像

5、素P1, 再下一個像素應(yīng)在P1的正右方像素P3(xP+2, yP)和P1的右上方像素P4(xP+2, yP+1)中選取, 應(yīng)計(jì)算 d1=F(xP+2,yP+0.5)=a(xP+2)+b(yP+0.5)+c=d+a,故在d0的情況下, d的增量為a 。 而若d0, 則取右上方像素P2, 再下一個像素應(yīng)在P2的正右方像素P4(xP+2,yP+1)和P2的右上方像素P5(xP+2,yP+2)中選取, 應(yīng)計(jì)算 d1=F(xP+2, yP+1.5)=a(xP+2)+b(yP+1.5)+c=d+a+b 故在d0的情況下, d的增量為a+b。,再討論d的初始值。 第一個像素應(yīng)取左端點(diǎn)(x0,y0), 相應(yīng)的

6、判別式為 d0=F(x0+1, y0+0.5)=a(x0+1)+b(y0+0.5)+c =ax0+by0+c+a+0.5b =F(x0, y0)+a+0.5b,中點(diǎn)畫線法的偽C算法描述如下: void MidPoint-Line(x0, y0, x1, y1, color) int x0, y0, x1, y1, color; int a, b, delta1, delta2, d, x, y; a=y0-y1; b=x1-x0; d=2*a+b delta1=2*a; delta2=2*(a+b); x=x0; y=y0;,putpixel(x, y, color); while(xx1)

7、if(d0) x+; y+; d+=delta2; else x+; d+=delta1; putpixel(x, y, color); ,3.1.3 Bresenham算法 Bresenham畫線算法與中點(diǎn)畫線法有相似之處, 也是通過在每列像素中確定與理想直線最近的像素來進(jìn)行直線的掃描轉(zhuǎn)換的。 為了討論的方便,不妨也假定直線的斜率在01之間。 如圖3.2所示, 過各行、 各列像素中心構(gòu)造一組虛擬網(wǎng)格線, 按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn), 然后確定該列像素中與該交點(diǎn)最近的像素。,圖 3.2 Bresenham算法誤差項(xiàng)d的幾何意義,算法的偽C描述如下: void Bres

8、enham-Line(x0, y0, x1, y1, color) int x0, y0, x1, y1, color; int x, y, dx, dy; float k, e; dx=x1-x0; dy=y1-y0; k=dy/dx; e=-0.5; x=x0; y=y0;,for(i=0; i=0) y=y+1; e=e-1; ,上述算法在計(jì)算直線的斜率與誤差項(xiàng)時(shí), 要用到小數(shù)和除法, 不便于硬件實(shí)現(xiàn)。 由于算法中只用到誤差項(xiàng)的符號, 因此, 為了避免除法, 令e=2 e dx, 用e 代替e 。 改進(jìn)之后的算法如下:,void Bresenham-Line(x0, y0, x1, y1

9、, color) int x0, y0, x1, y1, color; int x, y, dx, dy, e; dx=x1-x0; dy=y1-y0; e=-dx; x=x0; y=y0; for(i=0; i=0), y=y+1; e=e-2*dx; ,3.2 圓和橢圓的掃描轉(zhuǎn)換,3.2.1 圓的掃描轉(zhuǎn)換 1. 中點(diǎn)畫圓法 為了討論的方便, 我們考慮中心在原點(diǎn), 半徑為R的圓的第二個八分圓弧, 圓的其它部分可通過一系列的簡單的反射變換得到。 也就是討論如何從(0, R)到 (R / , R / )順時(shí)針確定最佳逼近于該圓弧的像素序列。,中心在原點(diǎn), 半徑為R的圓的方程為 x2+y2=R2

10、若令F(x,y)=x2+y2-R2, 則上述方程為 F(x, y)=0,如圖3.3所示, 假定x坐標(biāo)為xP的像素中最佳逼近理想圓弧的為P(xP, yP), 那么, 下一個像素只能是正右方的P1(xP+1, yP)或右下方的P2(xP+1, yP-1)兩者之一。 引入P1和P2的中點(diǎn)M(xP+1, yP-0.5), 當(dāng)M在圓內(nèi)時(shí), 應(yīng)取P1(xP+1, yP)為下一個像素, 否則, 應(yīng)取P2(xP+1, yP-1)為下一個像素。 為此, 構(gòu)造判別式 d=F(M)=F(xP+1, yP-0.5)=(xP+1)2+(yP-0.5)2-R2,圖3.3 中點(diǎn)畫圓法,若d0, 則應(yīng)取P1(xP+1, yP

11、)為下一個像素, 而且再下一個像素的判別式為 d=F(xP+2, yP-0.5)=(xP+2)2+(yP-0.5)2-R2 =d+2xP+3 而d0, 則應(yīng)取P2(xP+1, yP-1)為下一個像素, 而且再下一個像素的判別式為 d=F(xP+2, yP-1.5)=(xP+2)2+(yP-1.5)2-R2 =d+2(xP-yP)+5 由于第一個像素是(0，R), 因而d的初始值為 d0=F(1, R-0.5)=1.25-R,根據(jù)以上分析, 可得中點(diǎn)畫圓法算法如下: void MidPoint-Circle(r, color) int r, clor; int x, y; float d; x=

12、0; y=r; d=1.25-r; putpixel(x, y, color); while(xy) if(d0) d+=2*x+3; x+; ,else d+=2*(x-y)+5; x+; y-; putpixel(x, y, color); ,在上述的算法中, 判別式d使用了浮點(diǎn)數(shù), 影響了算法的效率。 為了擺脫浮點(diǎn)數(shù), 令e=d-0.25, 則e的初始值為1-r。 判別式d0對應(yīng)于e-0.25。 而e的初始值為整數(shù), 且在運(yùn)算過程中的增量也是整數(shù), 故e始終是整數(shù), 因而e-0.25等價(jià)于e0。 改進(jìn)之后的算法為,void MidPoint-Circle(r, color) int r,

13、 clor; int x, y, e; x=0; y=r; e=1-r ; putpixel(x, y, clolor); while (xy) if (e0) e+=2*x+3; x+;, else e+=2*(x-y)+5; x+; y-; putpixel(x, y, clolor); ,上述算法中, e的增量是x, y的線性函數(shù)。 每當(dāng)x 遞增1, e遞增2； 每當(dāng)y遞減1, e遞增2。由于初始像素為(0, r), 所以x可以看成從3開始遞增, y可看成從2r+2開始遞減。 因而上述算法可改進(jìn)為,void MidPoint-Circle(r, color) int r, clor; i

14、nt x, y, deltax, deltay, e; x=0; y=r; e=1-r; deltax=3; deltay=2-r-r; putpixel(x, y, color); while(xy) if(e0) e+=deltax; deltax+=2;,x+; else e+=(deltax+deltay); deltax+=2; deltay+=2; x+; y-; putpixel(x, y, color); ,2. Bresenham算法 由于圓具有對稱性, 因而我們只討論圓心在原點(diǎn), 半徑為R的第一個四分圓, 如圖3.4 所示。 取(0, R)為起點(diǎn), 按順時(shí)針方向生成圓。 假

15、設(shè)像素(x, y)為最佳逼近理想圓弧的點(diǎn), 下一個像素只可能為正右方像素H(x+1, y)、 右下方像素D(x+1, y-1)或正下方像素V(x, y-1)之一, 如圖3.5所示。,圖 3.4 第一個四分圓,圖 3.5 下一個像素的三個候選像素,它們與理想圓弧之間的關(guān)系為下列五種情況: (1) H、 D、 V全在圓外; (2) H、 D在圓外, V在圓內(nèi); (3) D在圓上, H在圓外, V在圓內(nèi); (4) H在圓外, D、 V在圓內(nèi); (5) H、 D、 V全在圓內(nèi)。 令H=(x+1)2+y2-R2, D=(x+1)2+(y-1)2-R2, V=x2+(y-1)2-R2。 下面根據(jù)D(x+1

16、, y-1)與圓弧的位置關(guān)系分三種情況討論。,如果D0, 這時(shí), 右下方像素D在圓外, 圓弧與候選點(diǎn)的關(guān)系只可能是和的情形, 最佳逼近圓弧的像素只可能是D與V二者之一。 為了確定D和V哪個更接近于圓弧, 令 DV=|D|-|V| =|(x+1)2+(y-1)2-R2|-|x2+(y-1)2-R2|,若DV0, 應(yīng)取正下方像素V。 而當(dāng)DV=0時(shí), 二者均可取, 約定取右下方像素D。 對于情形, 由于右下方像素D在圓外, 而正下方像素V在圓內(nèi), 所以D0, V0, 因此 DV=D+V =(x+1)2+(y-1)2-R2+x2+(y-1)2-R2 =2D-2x-1,故可根據(jù)2D-2x-1的符號,

17、在情形判斷應(yīng)取D或V。 對于情形, D和V都在圓外, 應(yīng)取V為下一像素。 由于這時(shí)D0且V0, 因此 2D-2x-1=D+V0 可見, 在D0的情況下, 若2D-2x-10, 應(yīng)取D為下一像素, 否則取V作為下一像素。,如果D0, 則D到圓的距離小于H到圓的距離, 這時(shí)應(yīng)取D為下一個像素。 而當(dāng)HD=0時(shí), 二者均可, 約定取正右方像素H。,對于情形, H總在圓外, D在圓內(nèi), 因而有H0, D0, 所以 HD=H+D =(x+1)2+y2-R2+(x+1)2+(y-1)2-R2 =2D+2y-1 故可根據(jù)2D+2y-1的符號, 在情形判斷應(yīng)取H或D。,而對于情形。 這時(shí), H、 D都在圓內(nèi),

18、 而在這段圓弧上, y是x的單調(diào)遞減函數(shù), 所以只能取H為下一個像素。 又H0且D0, 因此, 2D+2y-1=H+D0與情形的判別條件一致。 可見在D0的情況下, 若2(D+y)-10, 則應(yīng)取H為下一個像素, 否則應(yīng)取D為下一個像素。,如果D=0, 這時(shí), 右下方像素D恰好在圓上, 也就是情形, 應(yīng)取D作為下一像素。 綜上所述, 可得計(jì)算下一像素的算法: 當(dāng)D0 時(shí), 若HD0, 則取D, 否則取V; 當(dāng)D0時(shí), 若DV0, 則取H, 否則取D; 當(dāng)D0時(shí), 取D。,從以上的討論中可知, HD和DV可由D推算出來, 因而該算法的關(guān)鍵在于求D。 D可用增量法計(jì)算。 若下一個像素為H(x+1,

19、 y), 其右下方像素為 D(x+2, y-1), 則 D=(x+1)+1)2+(y-1)2-R2 =D+2(x+1)+1 =D+2x+1,若下一個像素為D(x+1, y-1), 其右下方像素為 D(x+2, y-2), 則 D=(x+1)+1)2+(y-1)-1)2-R2 =D+2(x+1)-2(y-1)-2 =D+2x-2y-2 若下一個像素為V(x, y-1), 其右下方像素為 D(x+1, y-2), 則 D=(x+1)2+(y-1)-1)2-R2 =D-2y+1,Bresenham畫圓算法的偽C描述如下: void Bresenham-Circle(r, color) int r,

20、color; int x, y, delta, delta1, delta2, direction; x=0; y=r; delta=2*(1-r); while(y=0) putpixel(x, y, color); if(delta0) delta1=2*(delta+y)-1; if(delta1=0) diretion=1;,else direction=2; else if(delta0) delta2=2*(delta-x)-1; if(delta2=0) direction=2; else direcion=3; else direction=2; switch(directio

21、n) case 1:x+; delta+=2*x+1; break;,case 2: x+; y-; delta+=2*(x-y+1) break; case 3: y-; delta+=(-2*y+1); break; ,3.2.2 橢圓的掃描轉(zhuǎn)換 中點(diǎn)畫圓法可以推廣到一般二次曲線的生成, 下面以中心在原點(diǎn)的標(biāo)準(zhǔn)橢圓的掃描轉(zhuǎn)換為例說明。 設(shè)橢 圓的方程為 F(x,y)=b2x2+a2y2-a2b2=0 其中, a為沿x軸方向的長半軸長度, b為y軸方向的短半軸長度, a、 b均為整數(shù)。 不失一般性, 我們只討論第一象限橢圓弧的生成。需要注意的是, 在處理這段橢圓時(shí), 必須以弧上斜率為-1的點(diǎn)

22、(即法向量兩個分量相等的點(diǎn))作為分界把它分為上部分和下部分, 如圖3.6所示。,圖 3.6 第一象限的橢圓弧,該橢圓上一點(diǎn)(x, y)處的法向量為,其中, i和j分別為沿x軸和y軸方向的單位向量。 從圖3.6可看出, 在上部分, 法向量的y分量更大, 而在下部分, 法向量的x分量更大, 因而, 在上部分若當(dāng)前最佳逼近理想橢圓弧的像素(xP,yP)滿足下列不等式 b2(xP+1)a2(yP-0.5) 而確定的下一個像素不滿足上述不等式, 則表明橢圓弧從上部分轉(zhuǎn)入下部分。,在上部分, 假設(shè)橫坐標(biāo)為xP的像素中與橢圓弧更接近點(diǎn)是(xP, yP), 那么下一對候選像素的中點(diǎn)是 (xP+1, yP-0.

23、5)。 因此判別式為 d1=F(xP+1, yP-0.5)=b2(xP+1)2+a2(yP-0.5)2-a2b2 若d10, 中點(diǎn)在橢圓內(nèi), 則應(yīng)取正右方像素, 且判別式應(yīng)更新為 d1=F(xP+2, yP-0.5)=b2(xP+2)2+a2(yP-0.5)2-a2b2 =d1+b2(2xP+3),當(dāng)d10, 中點(diǎn)在橢圓之外, 這時(shí)應(yīng)取右下方像素, 并且更新判別式為 d1=F(xP+2, yP-1.5)=b2(xP+2)2+a2(yP-1.5)2-a2b2 =d1+b2(2xP+3)+a2(-2yP+2) 由于弧起點(diǎn)為(0, b), 因此, 第一中點(diǎn)是(1, b-0.5), 對應(yīng)的判別式是 d

24、10=F(1, b-0.5)=b2+a2(b-0.5)2-a2b2 =b2+a2(-b+0.25),在下部分, 應(yīng)改為從正下方和右下方兩個像素中選擇下一像素。 如果在上部分所選擇的最后一像素是 (xP, yP), 則下部分的中點(diǎn)判別式d2的初始值為 d20=F(xP+0.5, yP-1)=b2(xP+0.5)2+a2(yP-1)2-a2b2 d2在正下方向與右下方向的增量計(jì)算與上部分類似, 這里不再贅述。 下部分弧的終止條件是y=0。,第一象限橢圓弧的掃描轉(zhuǎn)換中點(diǎn)算法的偽C描述如下: void MidpointEllipse(a, b, color) int a, b, color; int

25、x, y; float d1, d2; x=0; y=b; d1=b*b+a*a*(-b+0.25); putpixel(x, y, color); while(b*b*(x+1)a*a(y-0.5) if(d10) d1+=b*b*(2*x+3); x+; ,else d1+=(b*b*(2*x+3)+a*a*(-2*y+2); x+; y-; putpixel(x, y, color); /*上半部分*/ d2=sqr(b*(x+0.5)+sqr(a*(y-1)-sqr(a*b); while(y0) if(d20) d2+=b*b(2*x+2)+a*a*(-2*y+3); x+; y-;

26、 else d2+=a*a*(-2*y+3);,y-; putpixel(x, y, color); ,3.3 區(qū) 域 填 充,3.3.1 多邊形區(qū)域填充 這里所討論的多邊形域可以是凸的、 凹的, 還可以是帶孔的。 該算法的基本原理是按掃描線順序, 對每一條掃描線執(zhí)行如下四步:,(1) 求掃描線與多邊形各邊的交點(diǎn); (2) 將求得的交點(diǎn)按遞增順序進(jìn)行排序; (3) 交點(diǎn)配對, 確定相交區(qū)間; (4) 將相交區(qū)間內(nèi)的像素置成多邊形色, 相交區(qū)間外的像素置成背景色。,圖 3.7 多邊形域的填充,如圖3.7所示, 掃描線6與多邊形的邊界線交于四點(diǎn)A、 B、 C、 D, 得到的各交點(diǎn)的橫坐標(biāo)分別為2、

27、 4、 8、 11, 按遞增順序排序后仍為2、 4、 8、 11, 相交區(qū)間為2, 4、 8, 11, 這兩個區(qū)間的像素置成多邊形色, 把相交區(qū)間外的像素置成背景色。,圖 3.8 對區(qū)域邊界上像素全部填充的結(jié)果,下面再進(jìn)一步討論填充算法實(shí)現(xiàn)問題。 該算法關(guān)鍵在于計(jì)算每條掃描線與多邊形各邊的交點(diǎn), 直接用直線方程求交點(diǎn)的方法效率較低, 是不可取的。 為了提高效率, 在處理一條掃描線時(shí), 僅對與它相交的多邊形的邊進(jìn)行求交運(yùn)算。 把與當(dāng)前掃描線相交的邊稱為活性邊, 可以為每一條掃描線建立活性邊表, 以存放與該掃描線相交的邊的有關(guān)信息, 如掃描線與該邊的交點(diǎn)x等。,由于邊的連貫性(即當(dāng)某條邊與當(dāng)前掃描

28、線相交時(shí), 它很可能也與下一條掃描線相交), 以及掃描線的連貫性(即當(dāng)前掃描線和各邊的交點(diǎn)順序與下一條掃描線和各邊的交點(diǎn)順序很可能相同或非常類似), 我們根據(jù)當(dāng)前掃描線的活性邊表來導(dǎo)出下一條掃描線的活性邊表, 不必為下一條掃描線從頭開始構(gòu)造活性邊表。 設(shè)邊的直線方程為 ax+by+c=0 若y=yi時(shí), x=xi, 則當(dāng)y=yi+1時(shí),令x=-b/a, 上式表明某一條邊與當(dāng)前掃描線相交, 交點(diǎn)x坐標(biāo)為xi, 如果它與下一條掃描線相交, 交點(diǎn)x坐標(biāo)為xi+1, 則xi+1=xi+x。 此外, 如果它與下一條掃描線不相交, 那么要及時(shí)把它從活性邊表中刪除出去, 避免下一步進(jìn)行無謂的計(jì)算。 因而活性

29、邊表的結(jié)點(diǎn)中至少應(yīng)為對應(yīng)邊保存如下內(nèi)容: x: 當(dāng)前掃描線與邊的交點(diǎn); x: 從當(dāng)前掃描線到下一條掃描線之間的x增量; ymax: 邊所交的最高掃描線號。,圖 3.9 圖3.7中掃描線6和掃描線7的活性邊表 (a) 掃描線6的活性邊表；(b) 掃描線7的活性邊表,(a),(b),圖 3.10 圖3.7中各掃描線的新邊表,3.3.2 邊填充算法 圖3.11(a)所示為對圖中的多邊形的各邊打上了邊標(biāo)志, 圖3.11(b)所示為掃描線4填充前和填充后的各像素, 填黑色者表示置為多邊形色。 邊填充算法的偽C算法如下:,define FALSE 0 edge-mark-fill(polydef, col

30、or) 多邊形定義polydef; int color; 對多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換; InsideFlag=FALSE; For (每條與多邊形polydef相交的掃描線y) for(掃描線上每個像素x) if(像素x被打上邊標(biāo)志) InsideFlag=!(InsideFlag); if(InsideFlag!=FALSE) putpixel(x, y, color); else putpixel(x, y, backgroud); ,圖 3.11 邊填充算法示意圖,3.3.3 種子填充算法 種子填充算法是從多邊形內(nèi)部一個已知像素出發(fā), 找到區(qū)域內(nèi)的所有像素, 并把這些像

31、素置成多邊形色。 算法原理如下: 種子像素入棧, 當(dāng)棧非空時(shí)執(zhí)行如下三步操作: (1) 棧頂像素出棧; (2) 將出棧像素置成多邊形色; (3) 按左、 上、 右、 下順序檢查與出棧像素相鄰的四個像素, 若其中某個像素不在邊界且未置成多邊形色, 則把該像素入棧。,如圖3.12所示, 種子像素為S(3, 3), 用種子填充算法填充該封閉區(qū)域時(shí)各像素出棧的順序?yàn)?3, 3)、 (3, 4)、 (2, 4)、 (4, 3)、 (5, 2)、 (4, 2)、 (3, 2)、 (2, 2)、 (2, 3)。,上述的算法把連通區(qū)域內(nèi)的像素都壓入堆棧, 有些像素會入棧多次, 這不僅降低了算法的時(shí)間效率, 而

32、且增大了空間開銷。 其實(shí), 我們可以在任意一個掃描線與多邊形的相交區(qū)間中, 只取一個種子像素, 并將種子像素入棧, 當(dāng)棧非空時(shí)作如下四步操作:,(1) 棧頂像素出棧; (2) 沿掃描線對出棧像素的左右像素進(jìn)行填充, 直至遇到邊界像素為止, 也就是對包含出棧像素的整個區(qū)間進(jìn)行填充; (3) 上述區(qū)間內(nèi)最左最右的像素分別記為xl和xr; (4) 在區(qū)間xl, xr中檢查與當(dāng)前掃描線相鄰的上下兩條掃描線的有關(guān)像素是否全為邊界像素或已填充的像素, 若存在非邊界、 非填充的像素, 則把每一區(qū)間的最右像素入棧。,上述改進(jìn)之后的算法稱之為掃描線種子填充算法, 其偽C語言描述如下: void scanline

33、-seed-fill(polydef, color, x, y) 多邊形定義 polydef; int color, x, y; / * (x, y)為種子像素*/ int x, y, x0, xl, xr push(seed(x, y); /* 種子像素x棧 */ while (棧非空), pop (pixel(x, y); /* 棧頂像素出棧, 并置為(x, y) */ putpixel(x, y, color); x0=x+1; while (getpixel(x0, y)的值不等于邊界像素顏色值) /* 填充出棧像素的右方像素*/ putpixel(x0, y, color); x0=

34、x0+1; xr=x0-1; /*最右像素*/ x0=x-1;,while(getpixel(x0, y)的值不等于邊界像素顏色值) /* 填充出棧像素的左方 像素*/ putpixel(x0, y, color); x0=x0-1; xl=x0+1; /*最左像素*/ /* 檢查上一條掃描線, 若存在非邊界且未填充的像素, 則將各連續(xù)區(qū)間的最右像素入棧 */ x0=xl; y=y+1;,while(x0=xr) flag=0; while( getpixel(x0, y)的值不等于邊界像素顏色值),else push(x0-1, y); flag=0; xnext=x0; while( pi

35、xel(x0, y1)等于邊界像素顏色值)|(pixel(x0, y1)等于多邊形內(nèi)像素顏色值) ,/* 檢查下一條掃描線, 若存在非邊界, 未填充的像素, 則將各連續(xù)區(qū)間的最右像素入棧; 處理與前面一條掃描線的算法相同, 只要把y+1換為y-1即可 */ ,3.4 字 符 的 生 成,3.4.1 字符生成的方法 矢量字符使用矢量的方向和長度來表示字符中的每一筆筆劃。 矢量的方向編碼如圖3.13 所示。,圖 3.13 矢量的方向編碼,一個88西文字符點(diǎn)陣包括64個點(diǎn), 需要64位二進(jìn)制數(shù)(占八個字節(jié))表示, 一個1616點(diǎn)陣漢字, 需要256位表示, 即32個字節(jié)。 英文字母“F”的88點(diǎn)陣如

36、圖3.14所示, 其二進(jìn)制與十六進(jìn)制分別表示為,圖3.14 字符“F”8 8點(diǎn)陣,11111110 0 xfe 10000000 0 x80 10000000 0 x80 11111100 0 xfc 10000000 0 x80 10000000 0 x80 10000000 0 x80 10000000 0 x80,3.4.2 點(diǎn)陣字符 字符庫有壓縮型和非壓縮型兩種。 UCDOS中的1616點(diǎn)陣漢字字符庫是非壓縮型的, 它分94個區(qū)94個位, 每個字符由區(qū)碼和位碼編碼, 區(qū)碼和位碼各用一個字節(jié)(最高位為1)來表示。 要顯示輸出一個字符, 必須從字符庫中讀取相應(yīng)的字符掩膜矩陣數(shù)據(jù)。 其方法是

37、根據(jù)區(qū)碼和位碼計(jì)算出字符掩膜矩陣在字符庫中的起始位置, 從起始位置開始連續(xù)32個字節(jié)為該字符的掩膜矩陣數(shù)據(jù)。 計(jì)算公式為,row =(區(qū)碼0a1h)7fh col =(位碼0a1h)7fh rec = row94+ col start= rec32 其中, h表示十六進(jìn)制, 為按位與運(yùn)算符, rec為字符在字符庫中的序號, start為字符掩膜矩陣在字符庫中的起始位置。,假如一個字符掩膜矩陣存儲于字符型數(shù)組buf32中, 可用下面的偽程序輸出該字符。 void hz16xs(int x, int y, int color) int i, j, k; for(i=0; i(7-k) ,讀者可參照

38、本節(jié)所附的參考算法。 此外, 常常在輸出字符時(shí)要考慮字體、 字型、 字號和方向等屬性, 可將上述算法加以修改實(shí)現(xiàn)。 例如, 為了實(shí)現(xiàn)黑體字, 若某個像素對應(yīng)掩膜矩陣中的值為1, 則將該像素及其正右方像素置為字符顏色即可。,3.5 圖 形 裁 剪,3.5.1 直線段裁剪 直線段裁剪常有三種方法: Dan Cohen和Ivan Sutherland直線段裁剪算法、 中點(diǎn)再分直線段裁剪算法和LiangBarsky算法。,1. Dan Cohen和Ivan Sutherland直線段裁剪算法 Dan Cohen和Ivan Sutherland直線段裁剪算法是由Dan Cohen和Ivan Suther

39、land兩人提出的, 主要分三步進(jìn)行。 (1) 將矩形窗口的四條邊界延長, 則整個平面被分成九個區(qū)域, 如圖3.15所示, 每個區(qū)域內(nèi)的點(diǎn)都對應(yīng)著一個四位二進(jìn)制的區(qū)位碼, 其各位含義如圖3.16所示。,圖 3.15 區(qū)域劃分及編碼,圖 3.16 區(qū)位碼各位含義,(2) 判斷P1、 P2是否都在窗口內(nèi)。 (a) 若C1=C2=0, 即P1、 P2的編碼全為零, 線段P1P2在窗 口內(nèi), 保留線段P1P2, 過程結(jié)束。 (b) 否則, 若C1C20, 即作P1、 P2編碼的邏輯與, 結(jié)果為非零時(shí), 表示P1、 P2在窗口外同側(cè), 棄之, 過程結(jié)束。 (c) 否則, 線段必有一點(diǎn)在窗口外, 令該點(diǎn)為

40、P1, 進(jìn)行下一步。,(3) 根據(jù)P1點(diǎn)的編碼確定其在哪條邊界線之外, 求線段與該邊界的交點(diǎn)P, 交點(diǎn)把線段分成兩段, 舍去P1P段, 把交點(diǎn)P作為剩余線段的P1端點(diǎn)重新進(jìn)行第二步。 如圖3.17所示, 線段a經(jīng)第二步測試為窗內(nèi)口的線段(C1=C2=0), 取之。,圖 3.17 Dan Cohen和Ivan Sutherland直線段裁剪算法示意圖,Dan Cohen和Ivan Sutherland直線段裁剪算法的偽C代碼如下: define LEFT 1 define RIGHT 2 define BOTTOM 4 define TOP 8 void encode (x, y, code)

41、float x, y; int *code; int c; c=0; if(xXL) c=c|LEFT;,else if(xXR) c=c|RIGHT; if(yYT) c=c|TOP; *code=c; return; void SwapPoint(x1, y1, x2, y2) float *x1, *y1, *x2, *y2; float t; t=*x1; *x1=*x2; *x2=t; t=*y1; *y1=*y2; *y2=t; void SwapCode(code1, code2),int *code1, *code2; int t; t=*code1; *code1=*code

42、2; *code2=t; /*(x1,y1)與(x2,y2)是線段端點(diǎn)坐標(biāo), 其它四個參數(shù)分別為窗口的左、 下、 右、 上邊界*/ C-S-Line-Clip(x1, y1, x2, y2, XL, XR, YB, YT) float x1, y1, x2, y2, XL, XR, YB, YT; int code1, code2, code; encode(x1, y1, ,encode(x2, y2, ,else if(RIGHT ,x1=x; y1=y; encode(x, y, code1); Displayline(x1, y1, x2, y2); return; ,2. 中點(diǎn)再分直

43、線段裁剪算法 中點(diǎn)再分直線段裁剪算法是對Dan Cohen和Ivan Sutherland直線段裁剪算法的改進(jìn)。 在Dan Cohen和Ivan Sutherland直線段裁剪算法中, 為了避免求直線段與窗口邊界的交點(diǎn), 用不斷對分線段的方法排斥線段在窗口外的部分, 最后求出離線段端點(diǎn)最遠(yuǎn)的可見點(diǎn)(所謂可見點(diǎn)就是線段落在窗口內(nèi)的點(diǎn)), 若這兩點(diǎn)存在, 則這兩點(diǎn)就是線段P1P2的可見線段端點(diǎn), 下面我們僅介紹如何在線段P1P2上求離P1最遠(yuǎn)的可見點(diǎn), 其具體步驟如下：,(1) 測試P2是否在窗口內(nèi)。 若是, 則P2就是離P1最遠(yuǎn)的可見點(diǎn), 結(jié)束; 否則, 進(jìn)行下一步。 (2) 測試P1P2是否在

44、窗外同側(cè)。 若是, P1P2全部不可見, 結(jié)束; 否則, 進(jìn)行下一步。 (3) 取P1P2的中點(diǎn)Pm, 若PmP2在窗外同側(cè), 棄之, 剩余段以P2代替Pm重復(fù)步驟(2)。 否則, 以P1代替Pm重復(fù)步驟(2), 直到線段不能再分為止。,3. LiangBarsky算法 LiangBarsky算法是直線段的基于矩形窗口的參數(shù)化裁剪方法。 設(shè)直線段的兩個端點(diǎn)坐標(biāo)分別為(x1, y2)和(x2, y2), 其參數(shù)方程為,其中, x=x2-x1, y=y2-y1。 由于矩形窗口內(nèi)的點(diǎn)滿足,因而有,上述不等式可以表示為 upkqk k=1, 2, 3, 4 其中, 參數(shù)p,q定義為 p1=-x, q1

45、=x1-xL p2=x, q2=xR-x1 p3=-y, q3=y1-yB p4=y, q4=yT-y1,如果pk=0, 則表明直線段平行于矩形窗口邊界之一, 若還滿足qk0, 則表明直線段完全在邊界外, 舍棄該線段。 若qk0, 則表明直線段平行于矩形窗口邊界并且與窗口相交。 如果pk0, 直線段從矩形窗口邊界延長線的外部延伸到內(nèi)部。 如果pk0, 直線段從矩形窗口邊界延長線的內(nèi)部延伸到外部。 當(dāng)pk非零時(shí), 可以計(jì)算出直線段與邊界k的延長線的交點(diǎn)參數(shù)u值。,上述不等式的解為,若u1u2, 則u1、 u2是直線段在矩形窗口內(nèi)的部分的端點(diǎn)參數(shù)。 否則, 表明直線段完全落在邊界外。,LiangB

46、arsky算法的偽C代碼描述如下: int LiangBarsky(x1, y1, x2, y2, xL, yB, xR, yT, ul, uu) float x1, y1, x2, y2, xL, yB, xR, yT; float *ul, *uu; int k; float r, u1, u2, dx, dy, p4, q4; u1=0.0; u2=1.0; dx=x2-x1; dy=y2-y1;,p0= -dx; p1=dx; p2= -dy; p3=dy; q0=x1-xL; q1=xR-x1; q2=y1-yB; q3=yT-y1; for(k=0; k=0.0) continue

47、; else return(0); else r=qk/pk; if(pku1) u1=r;, if(u1u2) return(0); *ul=u1; *uu=u2; ,3.5.2 多邊形裁剪 對于多邊形裁剪, 自然就想到用線段裁剪方法處理多邊形的每一條邊界, 但是, 這樣做將得到一系列不連接的直線段, 如圖3.18所示。 但真正想顯示的是如圖3.19所示的裁剪后有邊界的區(qū)域。 因而用線段裁剪方法處理多邊形的每一條邊界是不可行的。 通常采用Sutherland-Hodgman裁剪算法, 該算法又稱為逐邊裁剪法, 其基本思想是逐次用窗口的一條邊裁剪多邊形。,圖 3.18 用線段裁剪算法處理多邊形

48、后的結(jié)果,圖 3.19 正確的裁剪結(jié)果,圖 3.20 線段SP與裁剪線的四種位置關(guān)系,如圖3.21所示, 用裁剪窗口的左邊界裁剪圖3.18中多邊形的每一條邊。 對于P1P2,令P1為S, P2為P, 由于S在不可見一側(cè), P在可見一側(cè), 因而輸出線段SP與裁剪線的交點(diǎn)I1和線段終點(diǎn)P(即P2)。 對于P2P3, 令P2為S, P3為P, 由于S、 P都在可見一側(cè),則輸出P(即P3)。 同樣, 對于P3P4, 輸出P4, 對于P4P5, 輸出P5。 而對于P5P1, 令P5為S, P1為P, 由于S在可見一側(cè), P在不可見一側(cè), 則輸出線段SP與裁剪線的交點(diǎn)I2。 至此, 用裁剪窗口的左邊界裁剪

49、圖3.18中多邊形的每一條邊的過程結(jié)束, 結(jié)果如圖3.22所示。,圖 3.21 用窗口的左邊界裁剪多邊形,圖 3.22 裁剪結(jié)果,3.6 屬 性 控 制,3.6.1 線型與線寬 1. 線型的處理 在實(shí)際繪圖中, 我們經(jīng)常遇到繪制指定線型的線條, 如點(diǎn)畫線、 虛線等。 線型可以用一個布爾值的序列來存放, 如用一個長度為32的布爾數(shù)組pattern存放。 把掃描轉(zhuǎn)換算法中的寫像素語句改為 if(pattern i%32) putpixel(x, y, color);,2. 線寬的處理 線寬的處理是指繪制多個像素寬的圖形。 通常有線刷子、 方形刷子和區(qū)域填充的三種方法。 線刷子的基本原理是: 把掃描

50、轉(zhuǎn)換所得的每個像素上下方或左右方半線寬之內(nèi)的像素全部置成圖形顏色, 即可“刷出”具有一定寬度的圖形。,對于直線來說, 如果直線斜率在, 之間, 把直線掃描轉(zhuǎn)換所得的每個像素上下方半線寬之內(nèi)的像素全部置成直線顏色, 否則, 把直線掃描轉(zhuǎn)換所得的每個像素左右方半線寬之內(nèi)的像素全部置成直線顏色。 如圖3.23所示為線寬是三個像素的直線。 對于圓弧來說, 在斜率為的點(diǎn)處, 必須將線刷子在水平與垂直方向之間切換。,如圖3.24所示為線寬是三個像素的圓弧。 線刷子簡單、 效率高。 但是, 當(dāng)線寬較大時(shí), 看起來很不自然。 當(dāng)比較接近水平的直線與比較接近垂直的直線匯合時(shí), 匯合處外角將有缺口。 同樣線寬的斜

51、線與水平線或垂直線不一樣粗。 當(dāng)線寬為偶數(shù)個像素時(shí), 用上述方法繪制的線條要么粗一個像素, 要么細(xì)一個像素。 圓弧在接近水平或垂直的地方, 線條更粗一些, 而在斜率接近的點(diǎn)附近, 線條更細(xì)一些。,圖 3.23 用線刷子繪制的三個像素寬的直線,圖 3.24 用線刷子繪制的三個像素寬的圓弧,圖 3.25 用方形刷子繪制的圓弧,方形刷子的基本原理是: 方形刷子是把掃描轉(zhuǎn)換所得的每個像素上下方和左右方半線寬之內(nèi)的像素全部設(shè)置成直線顏色。 圖3.25所示為用方形刷子繪制的圓弧。 但是這種方法將會重復(fù)地寫像素, 這是因?yàn)閷?yīng)于相鄰兩像素的方形一般會重疊。 為了避免重復(fù)寫像素, 可以為每個掃描線建一個表,

52、存放該掃描線與線條的相交區(qū)間左右端點(diǎn)位置。,在每個像素使用方形刷子時(shí), 用該方形與各掃描線的相交區(qū)間端點(diǎn)坐標(biāo)去更新原表內(nèi)端點(diǎn)數(shù)據(jù)。 如圖3.26所示為刷子移動的相鄰兩步和有關(guān)掃描線的臨時(shí)數(shù)據(jù)結(jié)構(gòu)所保存的對應(yīng)于各步的區(qū)間端點(diǎn)坐標(biāo)。,圖 3.26 刷子移動的相鄰兩步對應(yīng)的數(shù)據(jù)結(jié)構(gòu),3.6.2 字符屬性 在3.4節(jié)中我們介紹了字符的生成方法, 但是, 沒有考慮字體、 字號等屬性。 在實(shí)際應(yīng)用中, 在輸出字符時(shí), 常常要指定字體、 字號、 方向、 顏色、 對齊方式。 常用的西文字體有基本體、 簡體、 繁體、 斜體、 黑體。 常用的漢字字體有基本體、 宋體、 仿宋體、 楷體、黑體等。,3.6.3 區(qū)域填

53、充屬性 在實(shí)際應(yīng)用中, 我們常常要求在一個區(qū)域中填充指定的圖案, 比如一張地圖中在不同的區(qū)域內(nèi)需要填充不同圖案以形象表示和區(qū)分各個區(qū)域的范圍及特點(diǎn)。 圖案常用位圖矩陣表示。 區(qū)域填充圖案有兩種填充方式。 一種方式是透明方式, 當(dāng)位圖矩陣的對應(yīng)位置為時(shí), 用前景色寫像素; 否則, 不改變該像素的值。 另一種方式是不透明方式, 當(dāng)位圖矩陣的對應(yīng)位置為時(shí), 用前景色寫像素; 否則, 用背景色寫像素。,在不考慮圖案旋轉(zhuǎn)的情況下, 在進(jìn)行圖案填充時(shí), 區(qū)域與圖案之間的位置對齊有兩種方式。 第一種方式是把圖案原點(diǎn)與填充區(qū)域邊界或內(nèi)部的某點(diǎn)對齊。 第二種方式是把圖案原點(diǎn)與填充區(qū)域外部的某點(diǎn)對齊。 用第一種方

54、式填充的圖案, 將隨著區(qū)域的移動而跟著移動, 看起來很自然。 對于多邊形, 可取區(qū)域邊界上最左邊的頂點(diǎn)。 而對于圓和橢圓這樣的具有光滑邊界的區(qū)域, 則最好取區(qū)域內(nèi)部某一點(diǎn), 如中心, 對應(yīng)圖案原點(diǎn)。,3.7 反 走 樣,3.7.1 過取樣 過取樣也叫超采樣, 是指對于光柵圖形顯示器上提高邏輯分辨率, 使得邏輯分辨率超過其物理分辨率的一種偽光柵化。 也就是在高于顯示分辨率的較高分辨率下進(jìn)行掃描轉(zhuǎn)換, 然后對掃描轉(zhuǎn)換所得的像素及周圍幾個像素的值進(jìn)行平均得到較低分辨率下的像素值。,如圖3.27所示, 把每個像素劃分為四個子像素, 由掃描轉(zhuǎn)換求得各子像素的顏色值, 對四個子像素的顏色值進(jìn)行簡單平均,

55、得到顯示像素的顏色值。 也可以進(jìn)行加權(quán)平均計(jì)算顯示像素的顏色值, 如圖3.28所示, 設(shè)光柵圖形顯示器的分辨率為RC, 則把顯示窗口分成(2R+1)(2C+1)個子像素, 對位于像素中心及四周的九個子像素的顏色值進(jìn)行加權(quán)平均, 得到顯示像素的顏色值。,圖 3.27 簡單平均子像素劃分示意圖,圖 3.28 加權(quán)平均子像素劃分示意圖,3.7.2 簡單的區(qū)域取樣 簡單的區(qū)域取樣是對像素采用盒式濾波器進(jìn)行前置濾波后再取樣, 以決定像素的顯示灰度值的一種方法。 如圖3.29所示, 正方體代表盒式濾波器,它是一個二維加權(quán)函數(shù), 以W表示, 函數(shù)W定義域?yàn)檎麄€平面, 在當(dāng)前像素所代表的正方形區(qū)域上每點(diǎn)取值1, 在其它區(qū)域取值0。,圖 3.29 簡單的區(qū)域取樣采用的盒式濾波器,假設(shè)在多灰度黑白顯示器上在白色背景上繪制一條線寬為一個像素單位的直線, 直線的斜率為k(0k1)。 若一個像素整個落在線條上, 則將它置為黑色, 若一個像素與線條部分相交, 根據(jù)相交部分的大小來選擇不同的灰度。 相交部分大的像素更黑一些, 相交部分小的像素更白一些。 直線條與像素的相交有五種情況, 如圖3.30所示, 根