第2章基本圖形生成

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

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

color)；

2.1直線的生成在計算機上畫線一般都是給定兩個坐標點(x1,y1)和(x2,y2),要求畫出它們的直線。當要在屏幕上顯示一條直線時,只能在顯示器所給定的有限個像素矩陣中,確定最佳逼近于該直線的一組像素,對這些像素進行寫操作。這就是通常所說的在顯示器上繪制直線,或直線的掃描轉換。直線的斜率截距方程為：

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

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

xi+1=xi+1

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

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

b=y1–k·x1

但是,用這種方法畫線效率太低,這是因為每步都需要一個浮點乘法運算和一個四舍五入運算。為此我們要尋找更快的畫線方法。2.1.1數值微分法

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

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

當斜率絕對值|k|<1時：△x>△y

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

當|k|>1時,

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

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

上述采用的增量計算方法稱為數值微分算法(DigitalDifferentialAnalyzer簡稱DDA)。以下是用數值微分算法(DDA)生成直線(斜率在0～l)的C語言描述。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中點畫線法

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

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

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

M代入

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

構造判別式

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

d>0時,M在直線上方（即在Q的上方）,故應取右方的P1作為下一個像素。而當d<0,則應取右上方的P2。當d=0時,約定取右方P1。

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

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時,取右上方像素P2(xp+1,yp+1)。要判斷再下一個像素,應計算

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的初始值。直線的第一個像素為左端點(x1,y1),所以相應的判別式值為

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的符號,而且d的增量都是整數,只是其初始值包含小數。因此,我們可以用2d代替d,就可以寫出僅包含整數運算的中點畫線算法(斜率在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);}}中點法繪制直線實例例2.1：已知直線段的起點為（0,0）,終點為（5,2）,用中點算法求出線段各像素坐標值。

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

1965年,Bresenham提出了一種更好的直線生成算法,稱為Bresenham算法。此算法的一個主要思想是借助于一個決策變量dk,來確定下一個該點亮的像素點。

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

在列位置xk+1,用d1和d2來標識兩個候選像素的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

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

若令dk=△x(d1–d2),并稱dk為畫線中第k步的決策參數,則dk的計算僅包含整數運算,它的符號與d1–d2的符號相同。c為常量,在計算中將被消除。

在k+1步,決策參數可從方程(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

在每個整數x位置,從線段的坐標端點開始,反復進行決策參數的這種循環(huán)計算。在起始像素(x1,y1)的第一個參數d0可從方程(3–4)及k=△y/△x計算出：以下是Bresenham算法的C語言描述(斜率在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圓與橢圓的生成下面僅以圓心在原點、半徑R為整數的圓為例,討論圓的生成算法。假設圓的方程為：X2+Y2=R2圓的特征:八對稱性。只要掃描轉換八分之一圓弧,就可以求出整個圓弧的象素集(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)解決問題：簡單方程產生圓弧算法原理：利用其函數方程,直接離散計算圓的函數方程為：圓的極坐標方程為：1.中點畫圓法利用圓的對稱性,只須討論1/8圓：第二個8分圓P為當前點亮象素,那么,下一個點亮的象素可能是P1（Xp+1,Yp）或P2（Xp+1,Yp+1)。MP1P2P（Xp,Yp）算法原理構造函數：F（X,Y）=X2+Y2-R2；則

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

F（M）<0->M在圓內->取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為下一個象素,那么再下一個象素的判別式為：

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

=d+2xp+3即d的增量為2xp+3P1MP2算法原理若d>=0,則P2為下一個象素,那么再下一個象素的判別式為：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);} }算法程序為了進一步提高算法的效率,可以將上面的算法中的浮點數改寫成整數,將乘法運算改成加法運算,即僅用整數實現(xiàn)中點畫圓法。使用e=d-0.25代替de0=1-R可以更快地實現(xià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);}算法實現(xiàn)

該算法以點(0,r)為起點,按順時針方向生成圓時,相當于在第一象限內,所以y是x的單調遞減函數。y的計算式為：令d1、d2分別為yi到y(tǒng)、yi-1到y(tǒng)的距離,可知：

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

（0,r)yx(xi,yi)2.Bresenham畫圓法（1）如果di<0,則y=yi,即選擇當前像素的正右方作為下一個像素,遞推公式為：（2）如果di≥0,則y=yi-1,即選擇當前像素的右下方作為下一個像素,遞推公式為：（3）計算判別式的初值。初始點為（0,R）,則：算法實現(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.橢圓的特征橢圓函數:對于橢圓上的點,有F(x,y)=0；對于橢圓外的點,F(x,y)>0；對于橢圓內的點,F(x,y)<0。1.橢圓的特征解決第1象限問題：以弧上斜率為－1的點作為分界將第一象限橢圓弧分為上下兩部分。引理：若在當前的中點（xm,ym）,法向量的y分量比x分量大,即：而在下一個中點,不等號改變方向,則說明橢圓弧從上部分轉入下部分。法向量1.橢圓的特征先推導上半部分的橢圓繪制公式2.上部分算法推導判別式若di≤0,取Pu(xi+1,yi)若di>0,取Pd(xi+1,yi-1)2.上部分算法推導di≥0：判別式的初始值：增量為：2.上部分算法推導再來推導橢圓弧下半部分的繪制公式原理3.下部分算法推導判別方法：

若di≥0,取Pl(xi,yi-1)若di<0,取Pr(xi+1,yi-1)3.下部分算法推導誤差項的遞推,di≥0：增量：3.下部分算法推導4.中點橢圓算法小結第Ⅰ象限內橢圓弧的中點算法可以概括為：算法實現(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)是線段,其基本屬性包括線型、線寬和色彩。任何影響圖元顯示方法的參數稱為屬性參數。1.線型：實線、虛線、點線等。通過設置沿直線路徑顯示的實線線段的長度和間距來修改畫線算法,產生各種類型的直線。

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

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

重疊過取樣基于加權模板的過取樣2.4平面區(qū)域填充表示一個區(qū)域

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

頂點表示也稱為幾何表示,是用多邊形的頂點序列來表示區(qū)域。點陣表示也稱像素表示,是用位于多邊形內的像素集合來刻畫多邊形。

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

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

區(qū)域填充算法要求區(qū)域是連通的,因為只有在連通區(qū)域中,才能將種子點的顏色擴充到區(qū)域內的其他點。區(qū)域按連通情況可分為四連通區(qū)域和八連通區(qū)域。四連通區(qū)域是指從區(qū)域上一點出發(fā),可通過上、下、左、右4個方向移動,在不越出區(qū)域的前提下到達區(qū)域內的任意像素；八連通區(qū)域是指從區(qū)域內每一像素出發(fā),可通過上、下、左、右、左上、右上、左下、右下8個方向的移動,在不越出區(qū)域的前提下到達區(qū)域內的任意像素。

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

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

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

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

（五）種子填充算法區(qū)域是指已經表示成點陣形式的填充圖形,它是像素集合。根據填充方向分4-連通區(qū)域和8-連通區(qū)域。區(qū)域兩種表示形式：邊界表示：把位于給定區(qū)域的邊界上的象素一一列舉出來的方法。區(qū)域的邊界點有相同顏色。其填充算法有掃描線填充算法或邊界填充算法（Boundary-fillAlgorithm）。內點表示：枚舉出給定區(qū)域內所有象素的表示方法。即區(qū)域內的所有象素有相同的顏色。其填充算法常為種子填充或泛填充算法（遞歸算法）1.邊界表示的四連通區(qū)域種子填充算法基本思想：從多邊形內部任一點像素出發(fā),按照“左上右下”的順序判斷相鄰像素,若不是邊界像素且沒有被填充過,則對其填充,并重復上述過程,直到所有像素填充完畢?？梢允褂脳＝Y構來實現(xiàn)該算法,種子像素入棧,當棧非空時,重復執(zhí)行如下操作：（1）棧頂像素出棧；（2）將出棧像素置成多邊形填充的顏色；（3）按“左上右下”的順序檢查與出棧像素相鄰的四個像素,若其中某個像素不在邊界上且未置成多邊形色,則把該像素入棧。設(x,y)為邊界表示的四連通區(qū)域內的一點,bcolor為定義區(qū)域邊界的顏色,要將整個區(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算法功能：按順序重新著色順序：上下左右思考：如果是左上右下順序呢？請?zhí)顚懹蚁聢D序號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.內點表示的四連通區(qū)域種子填充算法基本思想：從多邊形內部任一點像素出發(fā),按照“左上右下”的順序判斷相鄰像素,如果是區(qū)域內的像素,則對其填充,并重復上述過程,直到所有像素填充完畢,常稱為漫水法?？梢允褂脳＝Y構來實現(xiàn)該算法,種子像素入棧,當棧非空時,重復執(zhí)行如下操作：（與邊界表示類似）（1）棧頂像素出棧；（2）將出棧像素置成多邊形填充的顏色；（3）按“左上右下”的順序檢查與出棧像素相鄰的四個像素,若其中某個像素不在邊界上且未置成多邊形色,則把該像素入棧。(2)當棧非空時,重復如下步驟:從棧頂彈出一個像素,將該像素置成填充色;按右、上、左、下順序檢查與該像素相鄰的四個像素是否是邊界像素或者是否已被置填充色:若是,返回（2）；若不是,將該像素入棧后,返回（2）。

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

SABCDEFGH

GGGGGGHG

HHGGGGGG

HHGGGG

HHGH

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