第3章基本圖形的生成

第3章基本圖形生成原理一光柵掃描：

1光柵掃描的基本原理：電子束在熒光屏上按照固定的掃描線和掃描順序掃出一個由行和列組成的光的柵網(wǎng)。

2像素：柵網(wǎng)中的每一個孤立的光點，它是光柵顯示的最小單位。像素可以有不同的亮度,像素的坐標值都是整數(shù)。

概論

3提出問題(1)目前使用的圖形輸出設備顯示器：光柵圖形顯示器(2)光柵圖形顯示器:

以光柵掃描方式刷新線段、字符和圖形。其本質(zhì):是一種畫點設備，是由一定數(shù)量的網(wǎng)格狀細小光點（像素）組成，使其某些像素亮，某些像素不亮來顯示圖形或文字.(3)問題：

光柵圖形顯示器是畫點設備，而二維圖形并不是點的集合，

如何在光柵圖形顯示器上構(gòu)造基本二維幾何圖形(線圓)？(4)解決方法：

進行圖形掃描轉(zhuǎn)換

例：要在屏幕上顯示一條直線時，只能確定出逼近直線的一組像素，并按掃描線順序?qū)@些像素進行寫操作，即進行掃描轉(zhuǎn)換。

結(jié)果:使所畫的直線轉(zhuǎn)換成為逼近理想直線的由無數(shù)個點構(gòu)成的集合。

畫圖形：可使用同樣的方法，即進行圖形的掃描轉(zhuǎn)換.

使所畫的圖形轉(zhuǎn)換成為逼近理想圖形的由無數(shù)個點構(gòu)成的集合。掃描轉(zhuǎn)換（光柵化）：

1什么叫掃描轉(zhuǎn)換（光柵化）？在光柵顯示器等數(shù)字設備上確定一個最佳逼近于圖形的象素集的過程。

2掃描轉(zhuǎn)換的主要工作：由于理想的圖形是連續(xù)的，而光柵圖像是離散的，因此顯示過程中不可避免地產(chǎn)生鋸齒等畸變，掃描轉(zhuǎn)換的主要工作就是研究使光柵圖像逼近原始的圖形的算法。

用一系列的象素點來逼近直線3學習掃描轉(zhuǎn)換的目的：

(1)繪圖函數(shù)具有局限性：

在實際工作中遇到畫線的工作時，可以方便地調(diào)用程序設計語言中提供的繪圖函數(shù)，不需要自己編寫畫線的程序。但它由局限性，不能滿足用戶特殊繪圖要求，需要開發(fā)出滿足需求的繪圖程序。

(2)學習目的：掌握將數(shù)學的、模擬的、線形的圖形變成數(shù)字的離散的圖形的過程中的設計思想和方法，這些思想能夠在科學研究和產(chǎn)品開發(fā)中發(fā)揮作用。5.1直線的生成三算法要求：

1準確：掃描點盡可能地逼近理想點。

2快速：改進算法盡快提高掃描轉(zhuǎn)換速度。

一問題的提出：

給定直線兩端點P0(x0,y0)和P1(x1,y1)，在光柵顯示器上畫出該直線。二需要進行掃描轉(zhuǎn)換：給出一個將直線轉(zhuǎn)換為逼近理想直線的點的集合的算法。

2直線的斜截式方程：

y=kx+bb＝y(tǒng)1－kx1x從起點到終點每次增加1，用y=kx+b計算y值，再用putpixel(x,int(y+0.5),color)輸出該像素。

3該算法的缺點：畫線效率低，每步都需要一個浮點乘法運算和一個四舍五入運算，需要加以改進。

5.2.數(shù)值微分法(DDA算法

DigitalDifferentialAnalyzer)

1直線的微分方程：一數(shù)值微分法：是一種基于直線微分方程來生成直線的方法。

二數(shù)值微分法的改進算法（關鍵：找到Pi(Xi,Yi),Pi+1(Xi+1,Yi+1)的關系）

1推導：直線方程：y=kx+b

直線上的第i、第i+1……個點為：Pi(Xi,Yi),Pi+1(Xi+1,Yi+1),…

計算Pi+1時：x為xi+1,（在第1象限x總是向右前進一步），

y為y （畫水平線時，y的值不變）

yi+1 （畫非水平線時，y的值變化，需要計算）其中：yi+1的計算為：

yi+1=kxi+1+B =k(xi+△x)+B=kxi+k△x+B =kxi+B+k△x //yi=kxi+B =yi+k△x =yi+k //當△x的步進為1時故Pi+1點的坐標為：

xi+1=xi+1yi+1=round(yi+k) //進行取整運算分析：下一點的y坐標為當前點y坐標加上斜率k,省略了浮點乘法。xi+1=xi+1yi+1=round(yi+k) (xi,yi)(xi+1,(int)(yi+k))(xi,(int)(yi))(xi+1,yi+k)數(shù)值微分法示意圖理想直線上的坐標點掃描轉(zhuǎn)換后的像素點2算法：

1)計算斜率k=△y/△x

2)畫第1個點(x0,y0)

3)計算下一個點（x，y）的值P，

x=x+1,y=y+k 小數(shù)部分≥0.5,則y=y+1循環(huán) 小數(shù)部分<0.5,則y=y

畫點（x，y）voidddaline(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx;floatdx,dy,k,y;dx=x1-x0;dy=y1-y0;k=dy/dx; //計算斜率

y=y0; //設定第1點的y值

for(x=x0;x<=x1;x++) //x加1{putpixel(x,(int)(y+0.5),color); //畫點，y值取整

y=y+k; //計算y的值

}}3程序：

4分析：

本算法中k值需要使用浮點，每一步都要進行取整運算，不利于硬件實現(xiàn)。可以用中點畫線法解決。

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

中點畫線法示意圖3.2.2中點畫線法：1有直線F(x,y)=ax+by+c=0，假定其斜率在0，1之間.2直線在x方向增加一個單位，則在y方向上的增量只能在0與1之間。3當前點為P（xp，yp）,下一點有兩種選擇:P1（xp+1,yp）或P2（xp+1,yp+1).4Q點是直線與垂直線x=xp+1的交點。M（xp+1，yp+0.5）為P1與P2的中點。若直線上的點Q在M的下方，說明直線離P1近，則應取P1為下一點。若直線上的點Q在M的上方，說明直線離P2近，則應取P2為下一點，

問題：如何判斷Q在M的什么位置?一原理:二判別式推導：

1直線方程： F(x,y)=ax+by+c=0

直線上的點： F(x,y)=0

直線上方的點： F(x,y)>0

直線下方的點： F(x,y)<0

中點M的坐標為：xp+1 yp+0.5

2欲判斷Q點在M的上方還是下方，將M帶入F(x,y)，判斷它的符號即可。判別式：dk=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c

dk>0

Q在M的下方（M在直線的上方）則：取P1作為下一個象素，

dk=dk

=0

Q在M的上（M在直線的上）則：同上

dk

<0Q在M的上方（M在直線的下方）則：取P2作為下一個象素，

對每一個象素計算判別式d，根據(jù)它的符號判定下一個象素。d是xp，yp的線形函數(shù)，可以采用增量計算來提高運算效率。

Q

P1

P2

M

P3

P4

P5

M1

M2

P

根據(jù)不同情況分析如下：第一種情況：當dk≥0時，取正右方的象素p1，下一步則應在p3和p4當中選擇，設它們的中點為M1（xp+2，yp+0.5）,則判斷式d1為：

dk+1=F(M1)=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=axp+2a+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=dk+a下一步的判別式為：dk+1=dk+1+ad的增量為a。

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第二種情況：當d<0時，取正上方的象素p2，下一步則應在p4和p5當中選擇，設它們的中點為M2（xp+2，yp+1.5）,則判斷式d2為：

dk+1=F(M2)=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=axp+2a+b(yp+1.5)+c=a(xp+1)+a+b(yp+0.5)+c+b=dk+a+b

下一步的判別式為：dk+1

=dk+a+bd的增量為a+b。

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

初始值，第一個象素為起點（x0，y0），相應的判別式值為M0，由于起點（x0，y0）在直線上，故F（x0，y0）=0。推導：d0=F(M0)=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//∵起點必在直線上，∴F(x0，y0)=0=a+0.5b

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

小結(jié)：1）根據(jù)M選擇P1與P2之一：dk=a(xp+1)+b(yp+0.5)+c2）根據(jù)M1選擇P3與P4之一：dk+1=dk+a3）根據(jù)M2選擇P4與P5之一：dk+1=dk+a+b4)d的初始值為：d0=a+0.5b

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

三進一步改進算法：

注意到初始值中有浮點運算，消除浮點可以進一步改進算法。考察判別式dk，判別使用的僅僅是dk的符號，且dk的增量都是整數(shù)，

故用2dk來代替dk，擺脫小數(shù)（浮點），從而提高速度。

改進結(jié)果：(中點畫線法的精髓）

d0=2a+b(a=y0-y1,b=x1-x0)dk+1=dk+2a（dk》0）此時取正右方像素

dk+2a+2b（dk<0）此時取右上方像素

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

學習目標：1理解該算法的來龍去脈（上述結(jié)果是怎么得來的）。2能夠用上述結(jié)果解題，編程實現(xiàn)該算法。四總結(jié)中點畫線算法：

1基本思想：通過判斷dk的值來確定下一個該點亮的像素

2思路：

(1)先求d0的值(利用中點M求）：d0=2a+b(2)再找到dk+1與dk的關系：

dk+1=dk+2a（dk》0）此時取正右方像素

dk+2a+2b（dk<0）此時取右上方像素

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

五利用推導結(jié)果編程實現(xiàn)中點畫線算法：voidMidpointLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{inta,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b; //d為d0，d=a+0.5b，2d=2a+b，D=2a+b,D=a+a+b delta1=2*a; //delta1為d1delta2=2*(a+b); //delta2為d2x=x0;y=y0;putpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=delta2;

}else{x++;d+=delta1;}putpixel(x,y,color);} //while} //MidpointLine

課后作業(yè)題：用中點畫線算法掃描轉(zhuǎn)換從像素點(1,1)到(8,5)線段的像素位置3改進的Bresenham算法假定直線段的0≤k≤1基本原理：誤差項的計算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1算法步驟：1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、d=0、x=x0、y=y0。3.繪制點(x,y)。4.d更新為d+k，判斷d的符號。若d>0.5，則(x,y)更新為(x+1,y+1)，同時將d更新為d-1；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。否則結(jié)束。改進1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1算法步驟為：1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、e=-0.5、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+k，判斷e的符號。若e>0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-1；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。否則結(jié)束。改進2：用2e△x來替換ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△x算法步驟：1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、e=-△x、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+2△y，判斷e的符號。若e>0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-2△x；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。否則結(jié)束。三利用推導結(jié)果編程實現(xiàn)bresenham算法：voidbresenhamline(intx0,inty0,intx1,inty1){intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;

while(x<=x1){ putpixel(x,y); x=x+1;

e=e+2*dy;

if(e>0){y=y+1;e=e-2*dx;}}}五中點畫線算法與bresenham算法的比較：

相似處：1求出d0的值2再找到dk+1與dk的關系.3利用dk的值判斷下一個該點亮的像素：不同點：1求d0時：中點畫線法：利用中點M坐標來求，d0＝2a＋bbresenham法：利用始點終點來求，d0＝2△y-△x2利用dk的值取像素時：

bresenham法：dk》0時取右上方像素

dk<0時取右方像素中點法正相反：dk》0時取右方像素

dk<0時取右上方像素課后作業(yè)題：用bresenham算法掃描轉(zhuǎn)換從像素點(1,1)到(8,5)線段的像素位置。3.3圓的生成3.3.1八分法畫圓算法思路：（考慮到圓的對稱性）畫出A點則剩下的7個點都能畫出，畫出B點則剩下的7個點都能畫出，因此，只討論8分圓的畫法即可A(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)B二算法原理：利用其函數(shù)方程，直接離散計算圓的函數(shù)方程為：缺點：計算量過大三圓的極坐標方程為：

可先通過平移變換，把計算所得的像素(x1,y1)坐標加上一個位移量(delta_x和delta_y)即得所求像素坐標(x2,y2)。即：

x2=x1+delta_xy2=y1+delta_y四中點不在原點的圓：3.3.2中點畫圓算法（關鍵：找到d的增量）一基本思路：利用中點M來選擇下一個要顯示的像素。二分析：

M的坐標是（x+1,y-0.5）

F(M)>0點M在圓的外邊,圓離P2點近,取P2F(M)=0點M在圓的上邊,取P2F(M)<0點M在圓的里邊,圓離P1點近,取P1

問題：下一次取P3？P4？P5？

M1P1P2M2M3P3P4P51

構(gòu)造判別式：若d<0點M在圓的里邊，圓離P1點近,則應取P1

下一個中點M2的判別式為：

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

即求出d的增量為：2xp+3若d≥0點M在圓的外邊,圓離P2點近,則應取P2

下一個中點M3的判別式為：

d=F(xp+2,yp-1.5) =(xp+2)2+(yp-1.5)2-R2 =d+2(xp-yp)+5

即求出d的增量為：2(xp-yp)+5總結(jié)求得的d的增量：2xp+3d<02(xp-yp)+5d≥0

2求d的增量：（目的：判斷下一個該顯示的像素）解決方法：M1P1P2M2M3P3P4P5p3求d的初始值d0：

起始點（即第一個像素)為（0,R）,

判別式d的初始值為：

d0=F(1,R-0.5) =1+(R-0.5)2-R2 =1.25-R4推導出的結(jié)果:d0＝1.25-R

d+2xp+3d<0d+2(xp-yp)+5d≥0

M1P1P2M2M3P3P4P5d=

5可以利用推導出的結(jié)果，編寫程序。三算法步驟：1.輸入圓的半徑R。2.計算初始值d=1.25-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d≤0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當x<y時，重復步驟3和4。否則結(jié)束。改進：用d-0.25代替d算法步驟：1.輸入圓的半徑R。2.計算初始值d=1-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d<0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當x<y時，重復步驟3和4。否則結(jié)束。四源程序：voidMidpointCircle(r,color)intr,color;{intx,y,d;x=0;y=r;d=1-r;wholecircle(x,y,color);

while(x<y){if(d<0) {d+=2*x+3;x++;}else {d+=2*(x-y)+5; x++;y--;}wholecircle(x,y,color);}}voidWholeCircle(xc,yc,x,y.color)intxc,yc,x,y,color;{putpixel(xc+x,yc+y,color);putpixel(xc-x,yc+y,color);putpixel(xc+x,yc-y,color);putpixel(xc-x,yc-y,color);putpixel(xc+y,yc+x,color);putpixel(xc-y,yc+x,color);putpixel(xc+y,yc-x,color);putpixel(xc-y,yc-x,color);}Oyiyyyi-1xixi-1x圓的半徑為r，圓心在原點，順時針方向畫1/8圓的過程。X每次增加1個步長。y則有兩種可能或選擇的原則是，y更靠近yi，還是更靠近yi-1令3、Bresenham畫圓算法xOyiyyyi-1xixi-1令pi<0下個像素點yi+1=yi

否則

yi+1=yi-1結(jié)論：1、求誤差初值，p0=3-2r,畫點（0，r）2、求下一個點坐標。xi+1=xi+1,如果pi<0,則yi+1=yi，pi+1=pi+4xi+6。否則yi+1=yi-1，pi+1=pi+4(xi-yi)3、i=i+1，重復2。3.4區(qū)域填充:

區(qū)域填充研究如何用一種顏色或一個圖案來充滿一個二維區(qū)域。

一區(qū)域：一組具有相同的屬性相鄰又相連的象素。二區(qū)域填充：根據(jù)邊或頂點的簡單描述生成區(qū)域的過程叫作區(qū)域填充。三區(qū)域填充要做的兩個工作：

1在什么地方填充，2填充什么內(nèi)容。四區(qū)域填充算法分為兩大類：

1.掃描轉(zhuǎn)換填充算法：按掃描線的順序確定。

2.種子填充算法：假設在多邊形或區(qū)域的內(nèi)部，至少有一個象素是已知的，然后設法找到區(qū)域內(nèi)所有其它象素，并對它們進行填充。

3.4.1種子填充算法

一種子填充算法的原理：假設在多邊形區(qū)域內(nèi)部有一像素已知，由此出發(fā)找到區(qū)域內(nèi)的所有像素。假設區(qū)域采用邊界定義，即區(qū)域邊界上所有像素均具有某個特定值，區(qū)域內(nèi)部所有象素均不取這一特定值，而邊界外的像素則可具有與邊界相同的值。

從區(qū)域上一點出發(fā)，可通過四個方向，即上、下、左、右移動的組合，在不越出區(qū)域的前提下，到達區(qū)域內(nèi)的任意像素。圖(a)所示的區(qū)域是四連通區(qū)域。

特點：區(qū)域內(nèi)像素由四向連接，而區(qū)域的邊界卻是八連通式的。二幾個概念：區(qū)域分兩種：四向連通區(qū)域和八向連通區(qū)域1四向連通區(qū)域：

區(qū)域內(nèi)每—個象素，可以通過左、右、上、下、左上、右上、左下、右下這八個方向的移動的組合來到達區(qū)域內(nèi)的任意象素。圖(b)所示的區(qū)域是八連通區(qū)域。

特點：區(qū)域內(nèi)象素由八向連接。如兩個矩形的連接處為右上連接。但是區(qū)域的邊界是四連通式的。

八向連通區(qū)域：

允許從四個方向?qū)ふ蚁乱幌笏?，稱為四向算法；允許從八個方向?qū)ふ蚁乱幌笏?，稱為八向算法。八向算法可以填充八向連通區(qū)域，也可以填充四向連通區(qū)域。四向算法只能填充四向連通區(qū)域，而不能填充八向填充區(qū)域。如果圖(b)中的區(qū)域是兩個分離的區(qū)域，并且每個區(qū)域需填成不同的顏色，那么，用八向算法會使兩個區(qū)域被錯誤地填上同一顏色。3四向算法和八向算法：1問題點：采用什么數(shù)據(jù)結(jié)構(gòu)？

(1)聯(lián)想迷宮求解問題：

相似處：迷宮圖中的每一個方塊象一個像素，所有的通道塊象要填充的區(qū)域。不同處：求解迷宮路徑：不是所有的通道塊都被選中區(qū)域填充：與種子像素特性相同的不超過邊界的所有像素都被選中。本質(zhì)：屬于后進先出問題。

(2)四向算法采用的數(shù)據(jù)結(jié)構(gòu)：棧結(jié)構(gòu)

四向算法：2四向算法原理：

種子像素入棧；當棧非空時重復執(zhí)行如下三步操作：

(1)棧頂像素出棧

(2)將出棧像素置成多邊形色

(3)按右上左下方向逆時針旋轉(zhuǎn)，順序檢查與出棧像素相鄰的四個像素，若其中某個像素不在邊界而且未置成多邊形色則把該像素入棧。有一個用邊界表示的區(qū)域，用種子填充算法對該區(qū)域進行填充。

3

8

24

7

9

24

7

9

1

4

3

84

7

9

5

6

4

84

7

9

5

6

84

7

9

7

6

84

7

9

7

84

7

9

8

4

7

9

4

7

9

7

9

9

堆棧中的數(shù)據(jù)：紅色代表出棧數(shù)據(jù)，灰色代表棧頂

1號出棧填充,按右上左下順序?qū)ふ椅刺畛湎笏亍?/p>

2號出棧填充,按右上左下順序找到8，3。

3號出棧填充,按右上左下順序找到4。

4號出棧填充,按右上左下順序找到6，5。

5號出棧填充,6為棧頂。

6號出棧填充,按右上左下順序找到7。

7號出棧填充,8為棧頂。

8號出棧填充,4為棧頂.4號出棧填充,7為棧頂(4號重復填充)7號出棧填充,9為棧頂(7號重復填充)

9號出棧填充,?？?，結(jié)束。3四向算法的缺點：

1把太多的象素壓入堆棧，有些象素甚至會入棧多次，降低了算法的效率，

2要求很大的存儲空間以實現(xiàn)棧結(jié)構(gòu).4解決辦法：在任意一個掃描線與多邊形的相交區(qū)間中，只取一個種子象素。通過沿掃描線填充水平象素段，來代替處理4-鄰接點和8-鄰接點。3.4.2掃描線填充算法算法原理：種子象素入棧；當棧非空時作如下四步操作：

1棧頂象素出棧；

2沿掃描線對出棧象素的左右象素進行填充，直至遇到邊界象素為止，即每出棧一個象素，就對包含該象素的整個區(qū)間進行填充；

3上述區(qū)間內(nèi)最左、最右的象素分別記為xl，xr（x_left,x_right）;4在區(qū)間[xl，xr]中檢查與當前掃描線相鄰的上下兩條掃描線的有關象素是否全為邊界象素或已填充的象素，若存在非邊界、末填充的象素，則把每一區(qū)間的最右象素取作種子象素入棧。二掃描線填充算法舉例：

要求：用紅色象素●填充，以◆為邊界的藝術A字。1．種子位置為●，填充一行（紅），檢查上下兩行中未填充區(qū)域，將最右的一個象素壓入堆棧中，堆棧中為1，2，3，棧頂為3，故下一步填充3號行。

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆

3◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆2．填充一行（綠），檢查上下兩行中未填充區(qū)域，將最右的一個象素壓入堆棧中，堆棧中為1，2，3，4，下一步處理4號的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆

4◆◆◆◆

3◆◆

◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆

3填充一行（綠），堆棧為1，2，3，新4，下一步處理新4號的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆

3◆◆

4◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆4．填充了兩行（蘭色），堆棧為1，2，3，下一步處理3號的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆

3◆◆●●◆

◆

◆◆●●◆

◆

◆◆◆◆◆

◆◆◆◆5．填充了三行（綠色），堆棧為1，2，下一步處理2號的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆●●◆◆●●◆

◆●●◆◆●●◆

◆●●◆◆◆◆◆

◆◆◆◆

6．填充了三行（綠色），堆棧為1，2，下一步處理2號的