第2章基本圖形生成

第2章基本圖形生成現(xiàn)在的計(jì)算機(jī)能夠生成非常復(fù)雜的圖形,但圖形無(wú)論多么復(fù)雜,它都是由基本圖形組合而成的。因此,學(xué)習(xí)基本圖形的生成算法是掌握計(jì)算機(jī)圖形學(xué)的基礎(chǔ)。本章主要討論一些基本圖形的生成原理,如直線、圓、橢圓的生成問(wèn)題,二維封閉圖形（多邊形、圓、橢圓）的填充問(wèn)題（包括顏色填充、影線填充和圖案填充）以及線型和線寬的處理。VisualC++的CDC圖形程序庫(kù)已提供了畫(huà)線、畫(huà)圓和橢圓、填充等基本圖形的繪制函數(shù),它們實(shí)質(zhì)上是按計(jì)算機(jī)圖形標(biāo)準(zhǔn)并以C++的語(yǔ)法約定提供給用戶(hù)使用的標(biāo)準(zhǔn)圖形生成算法。因此,從實(shí)用的角度出發(fā),用戶(hù)只需完全按照C++的語(yǔ)法約定使用這些圖形程序庫(kù),就沒(méi)有必要學(xué)習(xí)基本圖形的生成原理及算法。但是,基于下面的二個(gè)理由,我們認(rèn)為學(xué)習(xí)本章介紹的基本圖形生成原理及算法是非常有必要的。第二,VisualC++雖然提供了許多繪圖函數(shù),但總有滿足不了用戶(hù)特殊繪圖要求的時(shí)候。如果僅僅學(xué)會(huì)使用VisualC++的繪圖函數(shù),不掌握基本圖形生成原理及算法,那么你就永遠(yuǎn)無(wú)法超越VisualC++的限制。第一,基本圖形生成原理及算法是計(jì)算機(jī)圖形學(xué)的基本原理,如果不學(xué)習(xí)這些基本原理,那么以后還要涉及的其他計(jì)算機(jī)圖形學(xué)原理就無(wú)從談起；眾所周知,目前我們使用的主要圖形輸出設(shè)備顯示器和打印機(jī)本質(zhì)上是一種畫(huà)點(diǎn)設(shè)備,是由一定數(shù)量的網(wǎng)格狀細(xì)小光點(diǎn),使其某些像素亮,某些像素不亮來(lái)顯示圖形或文字的。所謂的基本圖形生成原理是指在點(diǎn)陣輸出設(shè)備的情況下,如何對(duì)一條斜的直線或彎曲的曲線盡可能快地輸出其最接近理想的直線或曲線。圖3-1用一系列的象素點(diǎn)來(lái)逼近直線

本章我們主要以光柵圖形顯示器為例討論基本圖形的生成原理及算法。我們假定,編程語(yǔ)言（以C語(yǔ)言為例）提供了一個(gè)最底層的像素操作函數(shù)：putpixel(x,y,

color)；

2.1直線的生成在計(jì)算機(jī)上畫(huà)線一般都是給定兩個(gè)坐標(biāo)點(diǎn)(x1,y1)和(x2,y2),要求畫(huà)出它們的直線。當(dāng)要在屏幕上顯示一條直線時(shí),只能在顯示器所給定的有限個(gè)像素矩陣中,確定最佳逼近于該直線的一組像素,對(duì)這些像素進(jìn)行寫(xiě)操作。這就是通常所說(shuō)的在顯示器上繪制直線,或直線的掃描轉(zhuǎn)換。直線的斜率截距方程為：

y=k·x+b(3–1)其中,k表示斜率,b是y軸截距。為此,只需讓x從起點(diǎn)到終點(diǎn)每次增加(或減少)1,用(3–1)式計(jì)算對(duì)應(yīng)的y值,再用putpixel(x,

(int)(y+0.5),color)函數(shù)輸出該像素的顏色值即可。

xi+1=xi+1

yi+1=kxi+1+b給定線段的兩個(gè)端點(diǎn)(x1,y1)和(x2,y2),可以計(jì)算出斜率k和截距b：

k=△y／△x=(y2–y1)/(x2–x1)

b=y1–k·x1

但是,用這種方法畫(huà)線效率太低,這是因?yàn)槊坎蕉夹枰粋€(gè)浮點(diǎn)乘法運(yùn)算和一個(gè)四舍五入運(yùn)算。為此我們要尋找更快的畫(huà)線方法。2.1.1數(shù)值微分法

對(duì)直線上任何給定的x的增量△x和y的增量△y,有下列計(jì)算公式：△y=

k·△x(3–2)或△x=△y/k(3–3)

當(dāng)斜率絕對(duì)值|k|<1時(shí)：△x>△y

可以讓x從起點(diǎn)到終點(diǎn)變化,每步遞增(或遞減)1,即令△x=±1,則△y=±k。若前一次的直線上像素點(diǎn)坐標(biāo)為(xi,yi),這一次的直線上像素點(diǎn)坐標(biāo)為(xi+1,yi+1),則xi+1=xi±1,yi+1=yi±k。隨后用putpixel函數(shù)輸出該像素的顏色值即可。見(jiàn)圖2.1。(xi,yi)(xi,(int)(yi+0.5))(xi+1,yi)(xi+1,(int)(yi+0.5))圖2.1數(shù)值微分法示意圖

當(dāng)|k|>1時(shí),

△x<△y可以讓y從起點(diǎn)到終點(diǎn)變化,每步遞增(或遞減)1,即△y=±1,用(3–3)式計(jì)算對(duì)應(yīng)的x增量,即△x=±1/k。若前一次的直線上像素點(diǎn)坐標(biāo)為(xi,

yi),這一次的直線上像素點(diǎn)坐標(biāo)為(xi+1,yi+1),則yi+1=yi±1,xi+1=xi±1/k。隨后用putpixel函數(shù)輸出該像素的顏色值即可。

上述采用的增量計(jì)算方法稱(chēng)為數(shù)值微分算法(DigitalDifferentialAnalyzer簡(jiǎn)稱(chēng)DDA)。以下是用數(shù)值微分算法(DDA)生成直線(斜率在0～l)的C語(yǔ)言描述。voidDDALine(intx1,inty1,intx2,inty2,intcolor){intx;floatk,dx,dy,y=y1;dx=x2-x1;dy=y2-y1;k=dy/dx;for(x=x1;x<=x2;x++){putpixel(x,(int)(y+0.5),color);y=y+k;}}2.1.2中點(diǎn)畫(huà)線法

這里先討論直線斜率在0～l之間。如圖2.2所示,若直線在x方向上增加一個(gè)單位,則在y方向上的增量只能在0～1之間。假設(shè)直線上當(dāng)前已確定的一個(gè)像素點(diǎn)坐標(biāo)為(xp,yp),用實(shí)心小圓表示。P=(xp,yp)P2P1MQ圖2.2中點(diǎn)畫(huà)線法示意圖

那么,下一個(gè)與直線最近的像素只能是正右方的P1(xp+1、yp)或右上方的P2(xp+1、yp+1)兩者之一,用空心小圓表示。為了確定出下一個(gè)像素是P1還是P2設(shè)M為P1與P2的中點(diǎn),即M=(xp+1,yp+0.5)Q是理想直線與垂直線x=xp+l的交點(diǎn)。顯然,若M在Q的上方,則P1離直線近,應(yīng)取為下一個(gè)像素；否則應(yīng)取P2。這種以中點(diǎn)M作為判別標(biāo)志的方法就是中點(diǎn)畫(huà)線算法。下面來(lái)討論中點(diǎn)畫(huà)線法的具體實(shí)現(xiàn)。直線方程為：F(x,y)=ax+by+c＝0假設(shè)直線的起點(diǎn)和終點(diǎn)分別為(x1,y1)和(x2,y2),則上述參數(shù)：a=y1-y2,b=x2-x1,c=

x1y2-x2y1。P=(xp,yp)P2P1MQ對(duì)于直線上的點(diǎn),F(x,y)=0；對(duì)于直線上方的點(diǎn):F(x,y)>0；對(duì)于直線下方的點(diǎn),F(x,y)<0。因此,欲判斷前述Q在M的上方還是下方,只要把

M代入

F(x,y),并判斷它的符號(hào)。

構(gòu)造判別式

d＝F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當(dāng)

d>0時(shí),M在直線上方（即在Q的上方）,故應(yīng)取右方的P1作為下一個(gè)像素。而當(dāng)d<0,則應(yīng)取右上方的P2。當(dāng)d=0時(shí),約定取右方P1。

對(duì)每一個(gè)像素計(jì)算判別式d,根據(jù)它的符號(hào)確定下一像素。由于d是xp和yp的線性函數(shù),可采用增量計(jì)算,以便提高運(yùn)算效率。在d≥0的情況下,取正右方像素P1(xp+1,yp)欲判斷再下一個(gè)像素應(yīng)取那個(gè),應(yīng)計(jì)算

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c

=(a(xp+1)+b(yp+0.5)+c)+a=d+a故d的增量為a。在d<0時(shí),取右上方像素P2(xp+1,yp+1)。要判斷再下一個(gè)像素,應(yīng)計(jì)算

d2=F(xp+2,yp+l.5)=a(xp+2)+b(yp+1.5)+c

=(a(xp+1)+b(yp+0.5)+c)+a+b=d+a+b再看d的初始值。直線的第一個(gè)像素為左端點(diǎn)(x1,y1),所以相應(yīng)的判別式值為

d0=F(x1+1,y1+0.5)=a(x1+1)+b(y1+0.5)+c=(ax1+by1+c)+a+0.5b=F(x1,y1)+a+0.5b由于(x1,y1)在直線上,故F(x1,y1)

=0。因此,d的初始值為d0=a＋0.5b。由于我們使用的只是d的符號(hào),而且d的增量都是整數(shù),只是其初始值包含小數(shù)。因此,我們可以用2d代替d,就可以寫(xiě)出僅包含整數(shù)運(yùn)算的中點(diǎn)畫(huà)線算法(斜率在0～l)：

故d的增量為a＋b。

voidMidpointLine(intx1,inty1,intx2,inty2,intcolor){intx,y,a,b,d1,d2,d;a=y1-y2;b=x2-x1;d=2*a+b;d1=2*a;d2=2*(a+b);x=x1;y=y1;putpixel(x,y,color);while(x<x2){x=x+1;if(d<0){y=y+1;d+=d2;}else{d+=d1;}putpixel(x,y,color);}}中點(diǎn)法繪制直線實(shí)例例2.1：已知直線段的起點(diǎn)為（0,0）,終點(diǎn)為（5,2）,用中點(diǎn)算法求出線段各像素坐標(biāo)值。

解：直線段的起點(diǎn)x=0,y=0,dx=5,dy=2,d0=5-2*2=1d0=1>0,x=1y=0,直線段的第二個(gè)像素點(diǎn)坐標(biāo)為（1,0）；d1=d0-4=-3<0,x=2,y=1,直線段第三個(gè)像素點(diǎn)坐標(biāo)為（2,1）d2=d1+10-4=3>0,x=3,y=1,直線段第四個(gè)像素點(diǎn)坐標(biāo)為（3,1）d3=d2-4=-1<0,x=4,y=2,直線段第五個(gè)像素點(diǎn)坐標(biāo)為（4,2）d4=d3+10-4=5<0,x=5,y=2,直線段第六個(gè)像素點(diǎn)坐標(biāo)為（5,2）d0=a＋0.5b=2a+bd1=d+ad2=d+a+b2.1.3Bresenham畫(huà)線算法

1965年,Bresenham提出了一種更好的直線生成算法,稱(chēng)為Bresenham算法。此算法的一個(gè)主要思想是借助于一個(gè)決策變量dk,來(lái)確定下一個(gè)該點(diǎn)亮的像素點(diǎn)。

對(duì)于直線斜率k在0～1之間的情況,如圖2.3所示,從給定線段的左端點(diǎn)(x1,y1)開(kāi)始,逐步處理每個(gè)后續(xù)列(x位置),并在掃描線y值最接近線段的像素上繪出一點(diǎn)。假設(shè)當(dāng)前直線上的像素已確定,其坐標(biāo)為(xk,yk)。那么下一步需要在列xk+1上確定掃描線y的值。y值要么不變,要么遞增1。

在列位置xk+1,用d1和d2來(lái)標(biāo)識(shí)兩個(gè)候選像素的y值與線段上理想y值的差值,則：

d1=y–yk=(k(xk+1)+b)–yk

d2=(yk+1)–y=yk+1–(k(xk+1)+b)那么

d1–d2=2k(xk+1)–2yk+2b–1xkykyk+1yxk+1d1d2圖2.3

兩個(gè)候選像素的y值與線段上理想y值的差值d1和d2設(shè)△y=y2–y1和△x=x2–x1,則k=△y/△x,代入上式,得：△x(d1–d2)=2△y·xk–2△x·yk+c(3–4)當(dāng)dk>0時(shí),直線上理想位置與右上方像素(xk+1,yk+l)更接近,所以應(yīng)取右上方像素；而當(dāng)dk<0時(shí),右方像素(xi+l,y)與直線上理想位置更接近,應(yīng)取右方像素；當(dāng)dk=0時(shí),兩個(gè)候選像素與直線上理想位置一樣接近,約定取(xk+l,yk+1)。

若令dk=△x(d1–d2),并稱(chēng)dk為畫(huà)線中第k步的決策參數(shù),則dk的計(jì)算僅包含整數(shù)運(yùn)算,它的符號(hào)與d1–d2的符號(hào)相同。c為常量,在計(jì)算中將被消除。

在k+1步,決策參數(shù)可從方程(3–4)算出：

dk+1=2△y·xk+1–2△x·yk+1+c從上述方程中減去方程（3–4）,可得：

dk+1–dk=2△y(xk+1–xk)–2△x(yk+1–yk)已知xk+1=xk+1,因而得到：

dk+1=dk

+2△y–2△x(yk+1–yk)若取右上方像素,yk+1–yk=1,則：

dk+1=dk

+2△y–2△x若取右方像素,yk+1=yk,則：

dk+1=dk

+2△y

在每個(gè)整數(shù)x位置,從線段的坐標(biāo)端點(diǎn)開(kāi)始,反復(fù)進(jìn)行決策參數(shù)的這種循環(huán)計(jì)算。在起始像素(x1,y1)的第一個(gè)參數(shù)d0可從方程(3–4)及k=△y/△x計(jì)算出：以下是Bresenham算法的C語(yǔ)言描述(斜率在0～l)。

d0=2△y·x1–2△x·y1+2△y+△x·(2b-1)=2△y·x1–2△x·(k·x1+b)+2△y+△x·(2b-1)=2△y·x1–2k△x·x1-2b△x+2△y+2b△x-△x

=2△y·x1–2(△y/△x)△x·x1+2△y-△xd0=2△y–△xvoidBresenham_Line(intx1,inty1,intx2,inty2,intcolor){intx,y,dx,dy,dk,I;dx=x2–x1;dy=y2–y1;dk=2dy–dx；x=x1;y=y1;for(i=0;i<=dx;i++){putpixel(x,y,color);x=x+1;dk=dk+2*dy;if(dk>=0){y=y+1;dk=dk–2*dx;}}}2.2圓與橢圓的生成下面僅以圓心在原點(diǎn)、半徑R為整數(shù)的圓為例,討論圓的生成算法。假設(shè)圓的方程為：X2+Y2=R2圓的特征:八對(duì)稱(chēng)性。只要掃描轉(zhuǎn)換八分之一圓弧,就可以求出整個(gè)圓弧的象素集(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)解決問(wèn)題：簡(jiǎn)單方程產(chǎn)生圓弧算法原理：利用其函數(shù)方程,直接離散計(jì)算圓的函數(shù)方程為：圓的極坐標(biāo)方程為：1.中點(diǎn)畫(huà)圓法利用圓的對(duì)稱(chēng)性,只須討論1/8圓：第二個(gè)8分圓P為當(dāng)前點(diǎn)亮象素,那么,下一個(gè)點(diǎn)亮的象素可能是P1（Xp+1,Yp）或P2（Xp+1,Yp+1)。MP1P2P（Xp,Yp）算法原理構(gòu)造函數(shù)：F（X,Y）=X2+Y2-R2；則

F（X,Y）=0（X,Y）在圓上；F（X,Y）<0（X,Y）在圓內(nèi)；F（X,Y）>0（X,Y）在圓外。設(shè)M為P1、P2間的中點(diǎn),M=(Xp+1,Yp-0.5)MP1P2有如下結(jié)論：

F（M）<0->M在圓內(nèi)->取P1F（M）>=0->M在圓外->取P2為此,可采用如下判別式：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2

若d<0,則P1為下一個(gè)象素,那么再下一個(gè)象素的判別式為：

d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3即d的增量為2xp+3P1MP2算法原理若d>=0,則P2為下一個(gè)象素,那么再下一個(gè)象素的判別式為：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+（2xp+3）+（-2yp+2）即d的增量為2(xp-yp)+5.d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-RMP1P2算法原理voidCTestView::OnMindpointcircle(){ CDC*pDC=GetDC(); intx=100,y=200,r=150,color=RGB(0,0,255);floatd; x=0;y=r;d=1.25-r; pDC->SetPixel(x,y,color); while(x<=y) { if(d<0)d+=2*x+3; else{d+=2*(x-y)+5;y--;} x++; pDC->SetPixel(x,y,color);} }算法程序?yàn)榱诉M(jìn)一步提高算法的效率,可以將上面的算法中的浮點(diǎn)數(shù)改寫(xiě)成整數(shù),將乘法運(yùn)算改成加法運(yùn)算,即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫(huà)圓法。使用e=d-0.25代替de0=1-R可以更快地實(shí)現(xiàn)圓的生成算法改進(jìn)voidCTestView::OnMindpointcircle(){ CDC*pDC=GetDC(); intx0=150,y0=120,r=100,color=RGB(0,0,255),x,y,d;

x=0;y=r;d=1-r; pDC->SetPixel(x,y,color); while(x<=y) { if(d<0)d+=2*x+3; else{d+=2*(x-y)+5;y--;} x++; pDC->SetPixel(x,y,color);

pDC->SetPixel(-x+x0,y+y0,color); pDC->SetPixel(-x+x0,-y+y0,color); pDC->SetPixel(x+x0,-y+y0,color); pDC->SetPixel(y+x0,x+y0,color); pDC->SetPixel(-y+x0,x+y0,color); pDC->SetPixel(-y+x0,-x+y0,color); pDC->SetPixel(y+x0,-x+y0,color);}ReleaseDC(pDC);}算法實(shí)現(xiàn)

該算法以點(diǎn)(0,r)為起點(diǎn),按順時(shí)針?lè)较蛏蓤A時(shí),相當(dāng)于在第一象限內(nèi),所以y是x的單調(diào)遞減函數(shù)。y的計(jì)算式為：令d1、d2分別為yi到y(tǒng)、yi-1到y(tǒng)的距離,可知：

令判斷式di=d1-d2,并代入d1、d2,則有：

（0,r)yx(xi,yi)2.Bresenham畫(huà)圓法（1）如果di<0,則y=yi,即選擇當(dāng)前像素的正右方作為下一個(gè)像素,遞推公式為：（2）如果di≥0,則y=yi-1,即選擇當(dāng)前像素的右下方作為下一個(gè)像素,遞推公式為：（3）計(jì)算判別式的初值。初始點(diǎn)為（0,R）,則：算法實(shí)現(xiàn)voidCMyView::OnBresenhamcircle(){ CDC*pDC=GetDC(); intx0=100,y0=100,x,y,r=80,c=0;//黑色圓弧

floate,d; e=3-2*r;x=0;y=r; while(x<=y) { if(e<0) {e=e+4*x+6;x++;} else{e=e+4*(x-y)+10;x++;y--;} pDC->SetPixel(x+x0,y+y0,c); pDC->SetPixel(-x+x0,y+y0,c); pDC->SetPixel(-x+x0,-y+y0,c); pDC->SetPixel(x+x0,-y+y0,c); pDC->SetPixel(y+x0,x+y0,c); pDC->SetPixel(-y+x0,x+y0,c); pDC->SetPixel(-y+x0,-x+y0,c); pDC->SetPixel(y+x0,-x+y0,c); } ReleaseDC(pDC);}3.橢圓的生成算法1.橢圓的特征橢圓函數(shù):對(duì)于橢圓上的點(diǎn),有F(x,y)=0；對(duì)于橢圓外的點(diǎn),F(x,y)>0；對(duì)于橢圓內(nèi)的點(diǎn),F(x,y)<0。1.橢圓的特征解決第1象限問(wèn)題：以弧上斜率為－1的點(diǎn)作為分界將第一象限橢圓弧分為上下兩部分。引理：若在當(dāng)前的中點(diǎn)（xm,ym）,法向量的y分量比x分量大,即：而在下一個(gè)中點(diǎn),不等號(hào)改變方向,則說(shuō)明橢圓弧從上部分轉(zhuǎn)入下部分。法向量1.橢圓的特征先推導(dǎo)上半部分的橢圓繪制公式2.上部分算法推導(dǎo)判別式若di≤0,取Pu(xi+1,yi)若di>0,取Pd(xi+1,yi-1)2.上部分算法推導(dǎo)di≥0：判別式的初始值：增量為：2.上部分算法推導(dǎo)再來(lái)推導(dǎo)橢圓弧下半部分的繪制公式原理3.下部分算法推導(dǎo)判別方法：

若di≥0,取Pl(xi,yi-1)若di<0,取Pr(xi+1,yi-1)3.下部分算法推導(dǎo)誤差項(xiàng)的遞推,di≥0：增量：3.下部分算法推導(dǎo)4.中點(diǎn)橢圓算法小結(jié)第Ⅰ象限內(nèi)橢圓弧的中點(diǎn)算法可以概括為：算法實(shí)現(xiàn)voidCTestView::OnMidpointellispe(){CDC*pDC=GetDC();inta=100,b=300,x,y,color=50;floatd1,d2;x=0;y=b;d1=b*b+a*a*(-b+0.25);pDC->SetPixel(x,y,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(x,-y,color);while(b*b*(x+1)<a*a*(y-0.5)){if(d1<=0){d1+=b*b*(2*x+3); x++;}else{d1+=b*b*(2*x+3)+a*a*(-2*y+2); x++;y--;}

pDC->SetPixel(x,y,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(x,-y,color);}/*while上半部分*/d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;while(y>0){if(d2<=0){ d2+=b*b*(2*x+2)+a*a*(-2*y+3); x++;y--;}else{ d2+=a*a*(-2*y+3);y--;}pDC->SetPixel(x,y,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(x,-y,color);} }2.3圖元屬性及走樣控制圖元的基本表現(xiàn)是線段,其基本屬性包括線型、線寬和色彩。任何影響圖元顯示方法的參數(shù)稱(chēng)為屬性參數(shù)。1.線型：實(shí)線、虛線、點(diǎn)線等。通過(guò)設(shè)置沿直線路徑顯示的實(shí)線線段的長(zhǎng)度和間距來(lái)修改畫(huà)線算法,產(chǎn)生各種類(lèi)型的直線。

在顯示器上實(shí)現(xiàn)具有一定寬度的直線,可以沿著生成直線時(shí)獲得的象素點(diǎn),通過(guò)移動(dòng)一把具有一定寬度的“刷子”來(lái)實(shí)現(xiàn)。垂直線刷子:假設(shè)直線斜率在[-1,1]之間,把刷子放置成垂直方向,刷子中點(diǎn)對(duì)準(zhǔn)直線一端點(diǎn),然后讓刷子中點(diǎn)往直線的另一端移動(dòng),即可“刷出”具有一定寬度的線。水平線刷子:直線斜率不在[-1,1]之間,可以把刷子放置成水平方向,刷子中點(diǎn)對(duì)準(zhǔn)直線一端點(diǎn)并往直線的另一端移動(dòng),即可“刷出”具有一定寬度的線。

方形刷子:把邊寬為指定線寬的正方形的中心沿直線作平行移動(dòng),即可獲得具有線寬的線條。生成具有寬度的線條還可以采用區(qū)域填充的算法。2.線寬控制3.反走樣用離散量表示連續(xù)量引起的失真,就叫做走樣。走樣現(xiàn)象：一是光柵圖形產(chǎn)生的階梯形一是圖形中包含相對(duì)微小的物體時(shí),這些物體在靜態(tài)圖形中容易被丟棄或忽略,在動(dòng)畫(huà)序列中時(shí)隱時(shí)現(xiàn),產(chǎn)生閃爍用于減少或消除這種效果的技術(shù),稱(chēng)為反走樣簡(jiǎn)單方法：提高分辨率簡(jiǎn)單區(qū)域取樣加權(quán)區(qū)域取樣反走樣技術(shù)

重疊過(guò)取樣基于加權(quán)模板的過(guò)取樣2.4平面區(qū)域填充表示一個(gè)區(qū)域

邊界（閉合的線段）+填充（灰度或色彩）多邊形區(qū)域填充：給出一個(gè)區(qū)域的定義,要求對(duì)此區(qū)域范圍內(nèi)的所有像素賦予指定的顏色代碼多邊形的掃描轉(zhuǎn)換主要是通過(guò)確定穿越區(qū)域的掃描線的覆蓋區(qū)間來(lái)填充區(qū)域填充是從給定的位置開(kāi)始涂描直到指定的邊界條件為止。（一）區(qū)域的表示及類(lèi)型區(qū)域的表示有兩種：頂點(diǎn)表示和點(diǎn)陣表示

頂點(diǎn)表示也稱(chēng)為幾何表示,是用多邊形的頂點(diǎn)序列來(lái)表示區(qū)域。點(diǎn)陣表示也稱(chēng)像素表示,是用位于多邊形內(nèi)的像素集合來(lái)刻畫(huà)多邊形。

（一）區(qū)域的表示及類(lèi)型

點(diǎn)陣表示通常有兩種情況：內(nèi)點(diǎn)表示和邊界表示。在內(nèi)點(diǎn)表示中,區(qū)域內(nèi)所有像素具有同一顏色,區(qū)域以外的所有像素是另外一種顏色；在邊界表示中,區(qū)域邊界上的所有像素具有特定的顏色（可以是填充顏色）,在區(qū)域內(nèi)、外的所有像素均不能具有這種顏色。（一）區(qū)域的表示及類(lèi)型

區(qū)域填充算法要求區(qū)域是連通的,因?yàn)橹挥性谶B通區(qū)域中,才能將種子點(diǎn)的顏色擴(kuò)充到區(qū)域內(nèi)的其他點(diǎn)。區(qū)域按連通情況可分為四連通區(qū)域和八連通區(qū)域。四連通區(qū)域是指從區(qū)域上一點(diǎn)出發(fā),可通過(guò)上、下、左、右4個(gè)方向移動(dòng),在不越出區(qū)域的前提下到達(dá)區(qū)域內(nèi)的任意像素；八連通區(qū)域是指從區(qū)域內(nèi)每一像素出發(fā),可通過(guò)上、下、左、右、左上、右上、左下、右下8個(gè)方向的移動(dòng),在不越出區(qū)域的前提下到達(dá)區(qū)域內(nèi)的任意像素。

區(qū)域連通方式對(duì)填充結(jié)果的影響4連通區(qū)域邊界填充算法的填充結(jié)果8連通區(qū)域邊界填充算法的填充結(jié)果例如:有的圖形其邊界像素是8連通的而內(nèi)部像素是4連通的1.填充點(diǎn)的判別方法“掃描線交點(diǎn)的奇偶數(shù)判斷”法：用一根水平掃描線自左而右通過(guò)多邊形而與多邊形的邊界相交,掃描線與邊界相交奇次數(shù)后進(jìn)入該多邊形,相交偶次數(shù)后離開(kāi)該多邊形。

（二）多邊形的掃描轉(zhuǎn)換有些在多邊形頂點(diǎn)處的掃描線交點(diǎn)需要專(zhuān)門(mén)處理。在這些位置上,掃描線通過(guò)一個(gè)頂點(diǎn)與多邊形的兩條邊相交。例如圖所示,若交點(diǎn)算一個(gè),則掃描線2與P6相交,求得交點(diǎn)(x坐標(biāo))序列3,6.5,7.5。這將導(dǎo)致[3,6.5]區(qū)間內(nèi)的像素被填充,而這個(gè)區(qū)間的像素是屬于多邊形外部,不需要填充。若交點(diǎn)算二個(gè),則掃描線7與P1相交,求得交點(diǎn)(x坐標(biāo))序列2,2,10。這將導(dǎo)致[2,10]區(qū)間內(nèi)的像素不被填充,而這個(gè)區(qū)間的像素是屬于多邊形內(nèi)部,需要填充。

ABCDP1P2P3P4P5P62468102468Oyx為了正確地進(jìn)行交點(diǎn)取舍,必須對(duì)上述兩種情況區(qū)別對(duì)待。在第一種情況,掃描線交于一頂點(diǎn),而共享頂點(diǎn)的兩條邊分別落在掃描線的兩邊。這時(shí),交點(diǎn)只算一個(gè)。在第二種情況,共享交點(diǎn)的兩條邊在掃描線的同一邊,這時(shí)交點(diǎn)作為零個(gè)或兩個(gè),取決于該點(diǎn)是多邊形的局部最高點(diǎn)還是局部最低點(diǎn)。具體實(shí)現(xiàn)時(shí),只需檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的y值。按這兩個(gè)y值中大于交點(diǎn)y值的個(gè)數(shù)是0,1,2來(lái)決定是取零個(gè)、一個(gè)、還是兩個(gè)。2.交點(diǎn)的異常處理（1）當(dāng)奇點(diǎn)在多邊形兩邊之下方時(shí),該點(diǎn)計(jì)為2個(gè)點(diǎn),如圖中的P1、P3和P5點(diǎn)。（2）當(dāng)奇點(diǎn)在多邊形兩邊之上方時(shí),該點(diǎn)計(jì)為0個(gè)點(diǎn),如圖中的P2、P4和P6點(diǎn)。（3）當(dāng)奇點(diǎn)在多邊形兩邊之間時(shí),該點(diǎn)計(jì)為1個(gè)點(diǎn),如圖中的P7點(diǎn)。具體實(shí)現(xiàn)時(shí),只需檢查頂點(diǎn)兩條邊的另外兩個(gè)端點(diǎn)的y值,由這兩個(gè)y值中大于交點(diǎn)y值的個(gè)數(shù)是0、1、2來(lái)決定。（4）掃描線與多邊形的水平邊重合,理論上是無(wú)窮多個(gè)交點(diǎn),但在實(shí)際處理時(shí)不計(jì)其交點(diǎn)。10x2134567891111121012y123456789ABCDP1P2P3P4P5P6P7P00111102223.算法步驟：(1)確定多邊形所占有的最大掃描線數(shù),得到多邊形頂點(diǎn)的最小和最大y值（ymin和ymax）。(2)從y=ymin到y(tǒng)=ymax,每次用一條掃描線進(jìn)行填充。(3)對(duì)生成的多邊形進(jìn)行填充的過(guò)程可分為四個(gè)步驟： a.求交點(diǎn) b.交點(diǎn)排序：按X值遞增順序排序 c.交點(diǎn)配對(duì) d.區(qū)間填色有效邊（ActiveEdge）：指與當(dāng)前掃描線相交的多邊形的邊,也稱(chēng)為活性邊。有效邊表（ActiveEdgeTable,AET）：把有效邊按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中,此鏈表稱(chēng)為有效邊表。有效邊表的每個(gè)結(jié)點(diǎn)：（三）有效邊表算法（Y連貫性算法）原理：處理一條掃描線時(shí),僅對(duì)有效邊求交利用掃描線的連貫性利用多邊形邊的連貫性邊表（EdgeTable）的構(gòu)造：(1)首先構(gòu)造一個(gè)縱向鏈表,鏈表的長(zhǎng)度為多邊形所占有的最大掃描線數(shù),鏈表的每個(gè)結(jié)點(diǎn),稱(chēng)為一個(gè)桶,則對(duì)應(yīng)多邊形覆蓋的每一條掃描線。(2)將每條邊的信息鏈入與該邊最小y坐標(biāo)（ymin）相對(duì)應(yīng)的桶處。即某邊最低端點(diǎn)的x坐標(biāo)放進(jìn)相應(yīng)掃描線桶中。(3)每條邊的數(shù)據(jù)形成一個(gè)結(jié)點(diǎn)。同一桶中若干條邊按x由小到大排序,若x相等,則△x由小到大排序。10x2134567891111121012y123456789ABCDP1P2P3P4P5P6P7P0算法步驟：①初始化：構(gòu)造邊表ET,AET表置空,取掃描線縱坐標(biāo)y的初值置為ET中非空元素的最小序號(hào),如在上圖中,y=1。②按從下到上的順序?qū)γ織l掃描線重復(fù)以下各步,直至ET和AEL都為空。將ET中與當(dāng)前y有關(guān)的結(jié)點(diǎn)加入至AET,同時(shí)保存AET中按x值從小到大實(shí)現(xiàn)的排列序列；對(duì)于AEL中的掃描線y,交點(diǎn)兩兩配對(duì),在每一對(duì)交點(diǎn)之間填充填充所需的像素值；在AEL中刪掉y≥ymax的結(jié)點(diǎn)。對(duì)于留在AEL中的每個(gè)結(jié)點(diǎn),執(zhí)行xi+1=xi+1/k；對(duì)AET中的各結(jié)點(diǎn)按x值從小到大排序；yi+1=yi+1成為下一條掃描線的坐標(biāo),根據(jù)計(jì)算并修改AET表,形成新的AET表。

1.邊緣填充算法也稱(chēng)為正負(fù)相消法。該填充算法的基本原理是：對(duì)每一條掃描線,依次求與多邊形各邊的交點(diǎn),將該掃描線上交點(diǎn)右邊的所有像素求補(bǔ)。多邊形所有邊處理完畢,填充即完成。（四）邊填充算法2.柵欄填充算法柵欄指的是一條過(guò)多邊形頂點(diǎn)且與掃描線垂直的直線,它將多邊形分成兩半,只要將柵欄與多邊形之間的像素求補(bǔ)即可。柵欄填充算法的基本原理是：對(duì)于每條掃描線與多邊形的交點(diǎn),將交點(diǎn)與柵欄之間的掃描線上的像素取補(bǔ),也就是說(shuō),若交點(diǎn)位于柵欄左邊,則將交點(diǎn)之右、柵欄之左的所有像素取補(bǔ)；若交點(diǎn)位于柵欄右邊,則將柵欄之右、交點(diǎn)之左的所有像素取補(bǔ)。

（五）種子填充算法區(qū)域是指已經(jīng)表示成點(diǎn)陣形式的填充圖形,它是像素集合。根據(jù)填充方向分4-連通區(qū)域和8-連通區(qū)域。區(qū)域兩種表示形式：邊界表示：把位于給定區(qū)域的邊界上的象素一一列舉出來(lái)的方法。區(qū)域的邊界點(diǎn)有相同顏色。其填充算法有掃描線填充算法或邊界填充算法（Boundary-fillAlgorithm）。內(nèi)點(diǎn)表示：枚舉出給定區(qū)域內(nèi)所有象素的表示方法。即區(qū)域內(nèi)的所有象素有相同的顏色。其填充算法常為種子填充或泛填充算法（遞歸算法）1.邊界表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點(diǎn)像素出發(fā),按照“左上右下”的順序判斷相鄰像素,若不是邊界像素且沒(méi)有被填充過(guò),則對(duì)其填充,并重復(fù)上述過(guò)程,直到所有像素填充完畢?？梢允褂脳＝Y(jié)構(gòu)來(lái)實(shí)現(xiàn)該算法,種子像素入棧,當(dāng)棧非空時(shí),重復(fù)執(zhí)行如下操作：（1）棧頂像素出棧；（2）將出棧像素置成多邊形填充的顏色；（3）按“左上右下”的順序檢查與出棧像素相鄰的四個(gè)像素,若其中某個(gè)像素不在邊界上且未置成多邊形色,則把該像素入棧。設(shè)(x,y)為邊界表示的四連通區(qū)域內(nèi)的一點(diǎn),bcolor為定義區(qū)域邊界的顏色,要將整個(gè)區(qū)域填充為新的顏色ncolor,邊界表示的四連通區(qū)域的遞歸填充算法如下：voidBoundaryFill(int

x,int

y,int

bcolor,int

ncolor){color=GetPixel(x,y)；

if((color!=bcolor)&&(color!=ncolor)){PutPixel(x,y,ncolor)；

BoundaryFill(x-1,y,bcolor,ncolor)；

BoundaryFill(x,y+1,bcolor,ncolor)；

BoundaryFill(x+1,y,bcolor,ncolor)；

BoundaryFill(x,y-1,bcolor,ncolor)；

}}1算法功能：按順序重新著色順序：上下左右思考：如果是左上右下順序呢？請(qǐng)?zhí)顚?xiě)右下圖序號(hào)23465其它顏色1其它顏色12463456789101112131415161718192021222324252627282930313233343536373839404142434445P遞歸填充算法（上下左右）：VoidFill(intx,inty,intbcolor,intncolor){intcolor；color=GetPixel(x,y)；if((color!=bcolor)&&(color!=ncolor)){PutPixel(x,y,ncolor)；Fill(x,y+1,bcolor,ncolor)；Fill(x,y-1,bcolor,ncolor)；Fill(x-1,y,bcolor,ncolor)；Fill(x+1,y,bcolor,ncolor)；}}思考：如果換成左上右下的順序呢？2.內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點(diǎn)像素出發(fā),按照“左上右下”的順序判斷相鄰像素,如果是區(qū)域內(nèi)的像素,則對(duì)其填充,并重復(fù)上述過(guò)程,直到所有像素填充完畢,常稱(chēng)為漫水法?？梢允褂脳＝Y(jié)構(gòu)來(lái)實(shí)現(xiàn)該算法,種子像素入棧,當(dāng)棧非空時(shí),重復(fù)執(zhí)行如下操作：（與邊界表示類(lèi)似）（1）棧頂像素出棧；（2）將出棧像素置成多邊形填充的顏色；（3）按“左上右下”的順序檢查與出棧像素相鄰的四個(gè)像素,若其中某個(gè)像素不在邊界上且未置成多邊形色,則把該像素入棧。(2)當(dāng)棧非空時(shí),重復(fù)如下步驟:從棧頂彈出一個(gè)像素,將該像素置成填充色;按右、上、左、下順序檢查與該像素相鄰的四個(gè)像素是否是邊界像素或者是否已被置填充色:若是,返回（2）；若不是,將該像素入棧后,返回（2）。

簡(jiǎn)單的種子填充算法它適合四連通、邊界定義的區(qū)域。(1)種子像素入棧;

SABCDEFGH

GGGGGGHG

HHGGGGGG

HHGGGG

HHGH

HEFHDGSCBA下左上右此算法如何修改,便可適合八連通區(qū)域？簡(jiǎn)單的四連通種子填充算法的應(yīng)用主要缺點(diǎn)是什么？此例中棧的最大深度為幾層？簡(jiǎn)單的種子填充算法應(yīng)用6754S9328S247938479484795684796847978479847994794796754S9328S799下左上右算法特點(diǎn)：可以用于填充帶有內(nèi)孔的平面區(qū)域。把太多的象素壓入堆棧,有些象素會(huì)入棧多次,降低算法效率；棧結(jié)構(gòu)占空間改進(jìn)： 減少遞歸次數(shù),提高效率。通過(guò)沿掃描線填充水平象素段,來(lái)代替處理4-鄰接點(diǎn)和8-鄰接點(diǎn)。方法之一：掃描線填充算法3.掃描線種子填充算法基本思想：在任意不間斷區(qū)間（一條掃描線上的一組相鄰像素）中,只取一個(gè)種子像素,填充當(dāng)前掃描線上的該段區(qū)間,然后確定與這一區(qū)段相鄰的上下兩條掃描線位于區(qū)域內(nèi)的區(qū)段,并依次把它們保存起來(lái),反復(fù)進(jìn)行這個(gè)過(guò)程,直到所保存的每個(gè)區(qū)段都填充完畢。算法執(zhí)行步驟：1）初始化：堆棧置空,將種子點(diǎn)(x,y)入棧。2）出棧：若棧空則結(jié)束,否則棧頂元素(x,y)出棧,并以y值作為當(dāng)前掃描線號(hào)。3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)(x,y)出發(fā),沿當(dāng)前掃描線向左、向右兩個(gè)方向逐個(gè)像素填充,直到遇到邊界像素為止。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。4)確定新的種子點(diǎn)：在區(qū)間[xl,xr]中檢查與當(dāng)前掃描