基本圖形生成

基本圖形生成第一頁，共一百四十六頁，2022年，8月28日

VisualC++的CDC圖形程序庫已提供了畫線、畫圓和橢圓、填充等基本圖形的繪制函數(shù)，它們實(shí)質(zhì)上是按計(jì)算機(jī)圖形標(biāo)準(zhǔn)并以C++的語法約定提供給用戶使用的標(biāo)準(zhǔn)圖形生成算法。因此，從實(shí)用的角度出發(fā)，用戶只需完全按照C++的語法約定使用這些圖形程序庫，就沒有必要學(xué)習(xí)基本圖形的生成原理及算法。但是，基于下面的二個(gè)理由，我們認(rèn)為學(xué)習(xí)本章介紹的基本圖形生成原理及算法是非常有必要的。第二頁，共一百四十六頁，2022年，8月28日第二，VisualC++雖然提供了許多繪圖函數(shù)，但總有滿足不了用戶特殊繪圖要求的時(shí)候。如果僅僅學(xué)會(huì)使用VisualC++的繪圖函數(shù)，不掌握基本圖形生成原理及算法，那么你就永遠(yuǎn)無法超越VisualC++的限制。第一，基本圖形生成原理及算法是計(jì)算機(jī)圖形學(xué)的基本原理，如果不學(xué)習(xí)這些基本原理，那么以后還要涉及的其他計(jì)算機(jī)圖形學(xué)原理就無從談起；第三頁，共一百四十六頁，2022年，8月28日眾所周知，目前我們使用的主要圖形輸出設(shè)備顯示器和打印機(jī)本質(zhì)上是一種畫點(diǎn)設(shè)備，是由一定數(shù)量的網(wǎng)格狀細(xì)小光點(diǎn)，使其某些像素亮，某些像素不亮來顯示圖形或文字的。本章我們主要以光柵圖形顯示器為例討論基本圖形的生成原理及算法。我們假定，編程語言（以C語言為例）提供了一個(gè)最底層的像素操作函數(shù)：putpixel(x,y,

color)；

所謂的基本圖形生成原理是指在點(diǎn)陣輸出設(shè)備的情況下，如何對(duì)一條斜的直線或彎曲的曲線盡可能快地輸出其最接近理想的直線或曲線。第四頁，共一百四十六頁，2022年，8月28日3.1直線的生成在計(jì)算機(jī)上畫線一般都是給定兩個(gè)坐標(biāo)點(diǎn)(x1,y1)和(x2,y2)，要求畫出它們的直線。當(dāng)要在屏幕上顯示一條直線時(shí)，只能在顯示器所給定的有限個(gè)像素矩陣中，確定最佳逼近于該直線的一組像素，對(duì)這些像素進(jìn)行寫操作。這就是通常所說的在顯示器上繪制直線，或直線的掃描轉(zhuǎn)換。直線的斜率截距方程為：

y=k·x+b(3–1)其中，k表示斜率，b是y軸截距。第五頁，共一百四十六頁，2022年，8月28日為此，只需讓x從起點(diǎn)到終點(diǎn)每次增加(或減少)1,用(3–1)式計(jì)算對(duì)應(yīng)的y值,再用putpixel(x,

(int)(y+0.5),color)函數(shù)輸出該像素的顏色值即可。給定線段的兩個(gè)端點(diǎn)(x1,y1)和(x2,y2)，可以計(jì)算出斜率k和截距b：

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

b=y1–k·x1

但是，用這種方法畫線效率太低，這是因?yàn)槊坎蕉夹枰粋€(gè)浮點(diǎn)乘法運(yùn)算和一個(gè)四舍五入運(yùn)算。為此我們要尋找更快的畫線方法。第六頁，共一百四十六頁，2022年，8月28日3.1.1數(shù)值微分法

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

k·△x(3–2)或△x=△y/k(3–3)對(duì)于具有斜率絕對(duì)值|k|<1的線段，可以讓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ù)輸出該像素的顏色值即可。見圖3.1。第七頁，共一百四十六頁，2022年，8月28日(xi,yi)(xi,(int)(yi+0.5))(xi+1,yi)(xi+1,(int)(yi+0.5))圖3.1數(shù)值微分法示意圖

對(duì)于具有斜率絕對(duì)值|k|>1的線段，可以讓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)，則xi+1=xi±1/k，yi+1=yi±1。隨后用putpixel函數(shù)輸出該像素的顏色值即可。

第八頁，共一百四十六頁，2022年，8月28日上述采用的增量計(jì)算方法稱為數(shù)值微分算法(DigitalDifferentialAnalyzer簡稱DDA)。以下是用數(shù)值微分算法(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;}}第九頁，共一百四十六頁，2022年，8月28日3.1.2中點(diǎn)畫線法

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

那么，下一個(gè)與直線最近的像素只能是正右方的P1(xp+1、yp)或右上方的P2(xp+1、yp+1)兩者之一，用空心小圓表示。第十頁，共一百四十六頁，2022年，8月28日為了方便地確定出下一個(gè)像素是P1還是P2，設(shè)M為P1與P2的中點(diǎn)，即M=(xp+1,yp+0.5)。又設(shè)Q是理想直線與垂直線

x=xp+l的交點(diǎn)。顯然，若M在Q的上方，則P1離直線近，應(yīng)取為下一個(gè)像素；否則應(yīng)取P2。這種以中點(diǎn)M作為判別標(biāo)志的方法就是中點(diǎn)畫線算法。下面來討論中點(diǎn)畫線法的具體實(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。第十一頁，共一百四十六頁，2022年，8月28日對(duì)于直線上的點(diǎn)，F(xiàn)(x,y)=0；對(duì)于直線上方的點(diǎn)，F(xiàn)(x,y)>0；而對(duì)于直線下方的點(diǎn)，F(xiàn)(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)確定下一像素。第十二頁，共一百四十六頁，2022年，8月28日由于d是xp和yp的線性函數(shù)，可采用增量計(jì)算，以便提高運(yùn)算效率。在d≥0的情況下，取正右方像素P1，欲判斷再下一個(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。要判斷再下一個(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第十三頁，共一百四十六頁，2022年，8月28日再看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，就可以寫出僅包含整數(shù)運(yùn)算的中點(diǎn)畫線算法(斜率在0～l)：

故d的增量為a＋b。

第十四頁，共一百四十六頁，2022年，8月28日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);}}第十五頁，共一百四十六頁，2022年，8月28日3.1.3Bresenham畫線算法

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

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

第十六頁，共一百四十六頁，2022年，8月28日在列位置xk+1，用d1和d2來標(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圖3.3

兩個(gè)候選像素的y值與線段上理想y值的差值d1和d2第十七頁，共一百四十六頁，2022年，8月28日設(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),并稱dk為畫線中第k步的決策參數(shù),則dk的計(jì)算僅包含整數(shù)運(yùn)算,它的符號(hào)與d1–d2的符號(hào)相同。c為常量，在計(jì)算中將被消除。

第十八頁，共一百四十六頁，2022年，8月28日在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

第十九頁，共一百四十六頁，2022年，8月28日在每個(gè)整數(shù)x位置,從線段的坐標(biāo)端點(diǎn)開始,反復(fù)進(jìn)行決策參數(shù)的這種循環(huán)計(jì)算。在起始像素(x1,y1)的第一個(gè)參數(shù)d0

可從方程(3–4)及k=△y/△x計(jì)算出：以下是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–△x第二十頁，共一百四十六頁，2022年，8月28日voidBresenham_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；}}}第二十一頁，共一百四十六頁，2022年，8月28日3.2圓與橢圓的生成

3.2.1圓的特性

由于圓是圖形和圖像中經(jīng)常使用的元素，因此在大多數(shù)圖形軟件中都包含有生成圓和圓弧的過程。也會(huì)提供一個(gè)既能顯示圓曲線，又能顯示橢圓曲線的繪圖函數(shù)。

圓被定義為所有離一中心位置(xc，yc)距離為給定值r的點(diǎn)集，可用如下方程表示：

(x–xc)2+(y–yc)2=r2第二十二頁，共一百四十六頁，2022年，8月28日利用這個(gè)方程，我們可以沿x軸從xc–r到xc+r以單位步長計(jì)算對(duì)應(yīng)的y值來得到圓周上每點(diǎn)的位置：

y=yc

±

但這并非是生成圓的最好方法。這個(gè)方法的一個(gè)問題是每一步包含很大的計(jì)算量。而且所畫像素位置間的間距是不一致的，在靠近x軸的0°和180°處像素點(diǎn)之間的間距越來越大。當(dāng)然可以在圓斜率的絕對(duì)值大于1后，交換x和y（即步進(jìn)y值，計(jì)算x值）來調(diào)整間距。但這樣增加了算法所需的計(jì)算量和處理過程。

第二十三頁，共一百四十六頁，2022年，8月28日另一種消除不等間距的方法是使用極坐標(biāo)r和θ計(jì)算沿圓周的點(diǎn)。以參數(shù)極坐標(biāo)形式表示圓方程可得到方程組：

x=xc+rcosθ

y=yc+rsinθ

使用上述方法以固定角度為步長生成顯示時(shí)，圓就可沿圓周等距點(diǎn)繪制出來。但這個(gè)方法使用了三角函數(shù)調(diào)用和浮點(diǎn)運(yùn)算，運(yùn)算速度太慢。

考慮到圓的對(duì)稱性可以減少計(jì)算量。只要能生成8分圓，那么圓的其他部分可通過一系列的簡單反射變換得到。第二十四頁，共一百四十六頁，2022年，8月28日如圖3.4所示，假設(shè)已知一個(gè)圓心在原點(diǎn)的圓上一點(diǎn)(x，y)，根據(jù)對(duì)稱性可得另外七個(gè)8分圓上的對(duì)應(yīng)點(diǎn)(y,x),(y,–x),(x,–y),(–x,–y),(–y,–x),(–y,x),(–x,y)。因此，只需討論8分圓的生成算法。

另外，為了方便起見，我們只考慮中心在原點(diǎn)，半徑為整數(shù)R的圓x2＋y2=R2。對(duì)于中心不在原點(diǎn)的圓，可先通過平移變換，化為中心在原點(diǎn)的圓，再進(jìn)行掃描轉(zhuǎn)換，把所得的像素坐標(biāo)加上一個(gè)位移量即得所求像素坐標(biāo)。

(y,x)(y,-x)(x,y)(x,-y)(-x,y)(-x,-y)(-y,-x)(-y,x)圖3.4圓的對(duì)稱性

第二十五頁，共一百四十六頁，2022年，8月28日3.2.2中點(diǎn)畫圓法

由于圓的對(duì)稱性，下面主要考慮中心在原點(diǎn)半徑為r的圓的第二8分圓。若從圓的正上方開始討論如何確定最佳逼近于該圓弧的像素序列。P=(x,y)P1P2M圖3.5中點(diǎn)畫圓法示意圖

假定當(dāng)前已確定了圓弧上的一個(gè)像素點(diǎn)為P(xp,yp)，那么，下一個(gè)像素只能是正右方的P1(xp+1,yp)或右下方的P2(xp+1,yp–1)兩者之一。如圖3.5所示。第二十六頁，共一百四十六頁，2022年，8月28日那么，當(dāng)F(M)>0時(shí)，M在圓外，這說明P2距離圓弧更近，應(yīng)取P2作為下一像素。而當(dāng)F(M)<0時(shí)，P1離圓弧更近，應(yīng)取P1。當(dāng)F(M)=0時(shí)，在P1與P2之中隨便取一個(gè)即可，約定取P2。對(duì)于圓上的點(diǎn)，F(xiàn)(x,y)=0；對(duì)于圓外的點(diǎn)，F(xiàn)(x,y)>0；而對(duì)于圓內(nèi)的點(diǎn)，F(xiàn)(x,y)><0。與中點(diǎn)畫線法類似，設(shè)M是P1和P2的中點(diǎn)，即M=(xp+1，yp–0.5)。構(gòu)造函數(shù)：

F(x,y)=x2＋y2–r2(3–5)第二十七頁，共一百四十六頁，2022年，8月28日若d＜0，則應(yīng)取P1為下一像素，而且再下一個(gè)像素的判別式為

d=F(xp

+2，yp–0.5)=(xp+2)2+(yp

–0.5)2–R2

=d+2xp+3所以，沿正右方向，d的增量為2xp+3。

與中點(diǎn)畫線法一樣，構(gòu)造判別式

d=F(M)=F(xp+1，yp–0.5)=(xp+1)2+(yp–0.5)2–r2

第二十八頁，共一百四十六頁，2022年，8月28日而若d≥0，則P2是下一像素，而且下一像素的判別式為

d'=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。由于我們從圓的正上方開始，因此第一像素是(0,r)，判別式d的初始值為：

d0=F(l,r–0.5)=1+(r–0.5)2–r2

=1.25–r第二十九頁，共一百四十六頁，2022年，8月28日由于上述公式中只有d0包含小數(shù)，而它又僅僅作為一個(gè)判別式，因此可以做一些特殊處理來擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)。若用e=d–0.25代替d，則d0=l.25–r對(duì)應(yīng)于e0

=1–r。判別式d<0對(duì)應(yīng)于e<–0.25。算法中其他與d有關(guān)的式子可把d直接換成e。這樣，就可以寫出完全用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法。算法中e仍用d來表示。

以下是中點(diǎn)畫圓算法的C語言描述：第三十頁，共一百四十六頁，2022年，8月28日voidMidpointCircle(intxc,intyc,intr,intcolor){intx=0,y=r,d=1–r；

WholeCircle（xc，yc，x，y，color）；

while（x<=y）

{if（d＜0）

{d+=2*x+3；x++；}else{d+=2*（x–y）+5；x++;y––；}WholeCircle（xc，yc，x，y，color）；

}}第三十一頁，共一百四十六頁，2022年，8月28日voidWholeCircle(intxc,intyc,intx,inty,intcolor){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)；}第三十二頁，共一百四十六頁，2022年，8月28日3.2.3Bresenham畫圓算法

考慮圓心在原點(diǎn)，半徑為r的第一個(gè)8分圓。取(0,r)為起點(diǎn)，按順時(shí)針方向生成圓。如圖3.6所示。從這段圓弧的任意一點(diǎn)出發(fā)，按順時(shí)針方向生成圓時(shí)。在這種情況下，x每步增加1，即：yxyiyi-1xixi+1y圖3.6y的位置

xi+1=xi+1則相應(yīng)的y有二種選擇：

yi+1=yi

或yi+1=yi-1第三十三頁，共一百四十六頁，2022年，8月28日

Bresenham畫圓算法采用一個(gè)決策值來確定到底是選擇yi還是yi-1。在x=xi+1位置上，用d1和d2來標(biāo)識(shí)兩個(gè)候選像素的y值與圓弧上理想y值的差值，則：y2=r2-(xi+1)2d1=yi2-y2=yi2-r2+(xi+1)2d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2令di=d1-d2，并代入d1、d2，則有：

di=2(xi+1)2+yi2+(yi-1)2-2r2這里di就是Bresenham畫圓算法的第i步?jīng)Q策值。如果di<0，則yi+1=yi，否則yi+1=yi-1。若di=0，則可任選一個(gè)，我們約定yi+1=yi-1。

第三十四頁，共一百四十六頁，2022年，8月28日下面來推導(dǎo)di的遞推公式。在i+1步，di+1為：

di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2若di<0，取右方像素，yi+1=yi，則：

di+1=2(xi+1+1)2+yi2+(yi-1)2-2r2=di+4xi+6而決策值的初值d0由x=0,y=r代入前面公式，得：

d0=2(0+1)2+r2+(r-1)2-2r2=3-2r已知xi+1=xi+1，因而得到：

di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2若di>=0，取右下方像素，yi+1=yi-1，則：di+1=2(xi+1+1)2+(yi-1)2+(yi-1-1)2-2r2=di+4(xi-yi)+10由此，可寫出Bresenham畫圓算法的C程序：

第三十五頁，共一百四十六頁，2022年，8月28日voidBresenhamCircle(intxc,intyc,intr,intcolor){intx=0,y=r,d=3-2*r;while(x<y){WholeCircle(xc,yc,x,y,color);if(d<0)d=d+4*x+6;else{d=d+4*(x-y)+10;y--;}x++;}if(x==y)WholeCircle(xc,yc,x,y,color);}第三十六頁，共一百四十六頁，2022年，8月28日3.2.4橢圓的生成算法

中點(diǎn)畫圓法可以推廣到一般二次曲線的生成。給定橢圓參數(shù)中心（xc，yc）、長半軸a和短半軸b，該橢圓的一般方程為：

(x–xc)2/a2+(y–yc)2/b2=1為此，可以先把中心平移到坐標(biāo)原點(diǎn)，確定好中心在原點(diǎn)的標(biāo)準(zhǔn)位置的橢圓像素點(diǎn)集后，再平移到(xc,yc)位置。如果橢圓的長軸和短軸方向不與坐標(biāo)軸x和y平行，可以先繞中心點(diǎn)進(jìn)行旋轉(zhuǎn)變換，確定變換矩陣，然后用本方法生成橢圓像素點(diǎn)集，再用變換矩陣乘以這些點(diǎn)集，就可繪出傾斜的橢圓。

第三十七頁，共一百四十六頁，2022年，8月28日以下我們先考慮標(biāo)準(zhǔn)位置的橢圓，即：

x2/a2+y2/b2=1把上式改變?yōu)橄旅嫘问剑?/p>

F(x,y)=b2x2＋a2y2–a2b2=0(3–6)則該式可作為中點(diǎn)算法的判別式：

<0說明(x，y)在橢圓邊界內(nèi)

F(x,y)=0說明(x，y)在橢圓邊界上

>0說明(x,y)在橢圓邊界外

由于橢圓的對(duì)稱性，我們只要討論第一象限橢圓弧的生成。在處理這段橢圓弧時(shí)，我們進(jìn)一步把它分為兩部分：上部分和下部分。第三十八頁，共一百四十六頁，2022年，8月28日以弧上斜率為–1的點(diǎn)作為分界，如圖3.7(P83)所示。在上部分，在x方向取單位步長，確定下一像素的位置；在斜率小于–1的下部分，在y方向取單位步長來確定下一像素的位置。

橢圓的斜率可從方程(3–6)中計(jì)算出：

dy/dx=–2b2x/2a2y在上部分和下部分的交界處,斜率dy/dx=–1,則上式變?yōu)椋?/p>

2b2x=2a2y

因此，從上部分變?yōu)橄虏糠值臈l件是：

2b2x>=2a2y

第三十九頁，共一百四十六頁，2022年，8月28日與中點(diǎn)畫圓算法類似，當(dāng)我們確定一個(gè)像素之后，接著在兩個(gè)候選像素的中點(diǎn)計(jì)算一個(gè)判別式的值。并根據(jù)判別式符號(hào)確定兩個(gè)候選像素哪個(gè)離橢圓更近。下面討論算法的具體步驟。先看橢圓弧的上部分。假設(shè)當(dāng)前已確定的橢圓弧上的像素點(diǎn)為(xp,yp)，那么下一對(duì)候選像素的中點(diǎn)是(xp+l,yp–0.5)。

因此判別式為

dp=F(xp+1,yp–0.5)=b2(xp+1)2+a2(yp–0.5)2–a2b2它的符號(hào)將決定下一個(gè)像素是取正右方的那個(gè)，還是右下方的那個(gè)。第四十頁，共一百四十六頁，2022年，8月28日若dp<0，中點(diǎn)在橢圓內(nèi)，則應(yīng)取正右方像素，且判別式應(yīng)更新為

dp+1=F(xp+2,yp–0.5)=b2(xp+2)2+a2(yp–0.5)2–a2b2=(b2(xp+1)2+a2(yp–0.5)2–a2b2)+b2(2xp+1+1)=dp+b2(2xp+1+1)因此，往正右方向，判別式dl的增量為b2(2xp+1+1)。而當(dāng)dp≥0，中點(diǎn)在橢圓之外，這時(shí)應(yīng)取右下方像素，并且更新判別式為dp+1=F(xp+2,yp–1.5)=b2(xp+2)2+a2(yp–1.5)2–a2b2=(b2(xp+1)2+a2(yp–0.5)2–a2b2)+b2(2xp+1+1)–2a2yp+1=dp+b2(2xp+1+1)–2a2yp+1第四十一頁，共一百四十六頁，2022年，8月28日所以，沿右下方向，判別式d的增量為：

b2(2xp+1+1)–2a2yp+1接下來，我們來看判別式dp的初始條件。由于弧起點(diǎn)為(0,b)，因此，第一個(gè)中點(diǎn)是(1,b–0.5)，對(duì)應(yīng)的判別式是dp0=F(1,b–0.5)=b2+a2(b–0.5)2–a2b2=b2+a2(–b+0.25)在生成橢圓弧的上部分時(shí)，在每步迭代中，必須隨時(shí)計(jì)算和比較從上部分轉(zhuǎn)入下部分的條件是否成立，這是由于在下一部分步進(jìn)方向由x改為y，因此算法也就不同。在下部分，應(yīng)改為從正下方和右下方兩個(gè)像素中選擇下一像素。

第四十二頁，共一百四十六頁，2022年，8月28日在剛轉(zhuǎn)入下一部分之時(shí)，必須對(duì)下部分的中點(diǎn)判別式d2進(jìn)行初始化。具體地說，如果在上部分所選擇的最后一像素是(xp,yp)，則下部分的中點(diǎn)判別式d2在(xp+0.5,yp–1)處計(jì)算。d2在正下方向與右下方向的增量計(jì)算與上部分類似，這里不再贅述。下部分弧的終止條件是y=0。至此，可寫出完整的中點(diǎn)畫橢圓的算法如下：

第四十三頁，共一百四十六頁，2022年，8月28日voidMidpointEllipse(intxc,intyc,inta,intb,intcolor){intaa=a*a,bb=b*b;inttwoaa=2*aa,twobb=2*bb;intx=0,y=b;intdx=0,dy=twoaa*y;intd=(int)(bb+aa*(–b+0.25)+0.5);WholeEllipse(xc,yc,x,y,color);while(dx<dy){x++;dx+=twobb; if(d<0)d+=bb+dx; else{y––;dy–=twoaa;d+=bb+dx–dy;}WholeEllipse(xc,yc,x,y,color);}第四十四頁，共一百四十六頁，2022年，8月28日voidWholeEllipse(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);}d=(int)(bb*(x+0.5)*(x+0.5)+aa*(y–1)*(y–1)–aa*bb+0.5);while(y>0){y––;dy–=twoaa;if(d>0)d+=aa–dy;else{x++;dx+=twobb;d+=aa–dy+dx;}WholeEllipse(xc,yc,x,y,color);}}第四十五頁，共一百四十六頁，2022年，8月28日3.3區(qū)域填充3.3.1有序邊表填充算法本節(jié)討論如何用一種顏色或圖案來填充一個(gè)二維區(qū)域。填充的區(qū)域可以是多邊形的，也可以是圓或橢圓的，還可以是帶孔的。區(qū)域填充可以分兩步進(jìn)行，第一步先確定需要填充哪些像素。第二步確定用什么顏色值或圖案來填充。多邊形區(qū)域填充的一種常用方法是按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。第四十六頁，共一百四十六頁，2022年，8月28日ABCDP1P2P3P4P5P62468102468Oyx如圖3.8所示，掃描線3與多邊形的邊界線交于四點(diǎn)A、B、C、D。這四點(diǎn)把掃描線分為四個(gè)區(qū)間[0,3],[3,4.5],[4.5,6],[6,8.3],[8.3,11]。其中,[3,4.5],[6,8.3]兩個(gè)區(qū)間落在多邊形內(nèi)，該區(qū)間內(nèi)的像素應(yīng)取多邊形色。其他區(qū)間內(nèi)的像素取背景色。

圖3.8多邊形與掃描線

第四十七頁，共一百四十六頁，2022年，8月28日有些在多邊形頂點(diǎn)處的掃描線交點(diǎn)需要專門處理。在這些位置上，掃描線通過一個(gè)頂點(diǎn)與多邊形的兩條邊相交。例如圖3.8所示，若交點(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)部，需要填充。

第四十八頁，共一百四十六頁，2022年，8月28日為了正確地進(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來決定是取零個(gè)、一個(gè)、還是兩個(gè)。第四十九頁，共一百四十六頁，2022年，8月28日例如，掃描線1交頂點(diǎn)P4，由于共享該頂點(diǎn)的兩條邊的另外二個(gè)頂點(diǎn)均高于掃描線，故取交點(diǎn)P4兩次。這使得P4像素用多邊形顏色設(shè)置。而在P2處，由于P1和P3均在下方，所以掃描線9與之相交時(shí)，交點(diǎn)算零個(gè)，該點(diǎn)不予填充。

在處理一條掃描線時(shí)，只需對(duì)與它相交的多邊形的邊進(jìn)行求交運(yùn)算。由于邊的連貫性，即當(dāng)某條邊與當(dāng)前掃描線相交時(shí)，它很可能也與下一條掃描線相交，為此，計(jì)算下一條掃描線與同一條邊的交點(diǎn)x值時(shí)，只需把當(dāng)前交點(diǎn)x值加上一個(gè)邊的反斜率即可：

xk+1=xk

+1/m(m為邊的斜率)

第五十頁，共一百四十六頁，2022年，8月28日我們把與當(dāng)前掃描線相交的邊稱為活化邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，稱此鏈表為活化邊表。令△x=1/m為常量，可以存放在對(duì)應(yīng)邊的活化邊表結(jié)點(diǎn)中。

另外，使用增量法計(jì)算時(shí)，我們需要知道一條邊何時(shí)不再與下一條掃描線相交，以便及時(shí)把它從活化邊表中刪除出去，避免下一步進(jìn)行無謂的計(jì)算。為此，需設(shè)一個(gè)變量ymax，用于保存邊所交的最高掃描線號(hào)。由此，活化邊表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可定義為如下形式：第五十一頁，共一百四十六頁，2022年，8月28日typedefstructtEdge{floatx;/*當(dāng)前掃描線與邊的交點(diǎn)的x值*/floatdx;/*從當(dāng)前掃描線到下一條掃描線之間的x增量*/intymax;/*邊所交的最高掃描線號(hào)*/}Edge;為了保證交點(diǎn)的正確配對(duì)，必須使活化邊表中的結(jié)點(diǎn)按交點(diǎn)x值的升序排序。排序方法可采用插入排序法。

第五十二頁，共一百四十六頁，2022年，8月28日在處理完當(dāng)前掃描線后轉(zhuǎn)入下一條掃描線之前，要對(duì)交點(diǎn)x坐標(biāo)進(jìn)行更新(+dx),插入新加入的邊，并把那些與當(dāng)前掃描線有交，而與下一條掃描線不再相交的邊，從活化邊表中刪除出去(通過檢查當(dāng)前掃描線y值是否等于各邊的ymax值來確定)。

另外，為了方便活化邊表的建立與更新，我們?yōu)槊恳粭l掃描線建立一個(gè)有序邊表，存放在該掃描線第一次出現(xiàn)的邊。也就是說，若某邊的較低端點(diǎn)的y值為ymin，則該邊就放在掃描線為ymin的有序邊表中。這樣，當(dāng)我們按掃描線號(hào)從小到大順序處理掃描線時(shí)，該邊在該掃描線第一次出現(xiàn)。第五十三頁，共一百四十六頁，2022年，8月28日有序邊表的數(shù)據(jù)結(jié)構(gòu)與活化邊表相同，每個(gè)結(jié)點(diǎn)存放對(duì)應(yīng)邊的初始信息。如該掃描線與該邊的初始交點(diǎn)x值(即較低端點(diǎn)的x值)，x的增量△x，以及該邊的最大y值ymax。有序邊表的邊結(jié)點(diǎn)也按x值升序排序。

在活化邊表的基礎(chǔ)上，進(jìn)行交點(diǎn)配對(duì)和區(qū)間填充是很容易的事。令指針從活化邊表中第一個(gè)結(jié)點(diǎn)到第二個(gè)結(jié)點(diǎn)遍歷一次，對(duì)每一個(gè)像素進(jìn)行寫操作。然后令指針從活化邊表中第三個(gè)結(jié)點(diǎn)到第四個(gè)結(jié)點(diǎn)遍歷一次，對(duì)每一個(gè)像素進(jìn)行寫操作。如此反復(fù)，直至本掃描線全部填充完畢。

第五十四頁，共一百四十六頁，2022年，8月28日歸納上述討論，我們可寫出多邊形區(qū)域填充的步驟為：①輸入欲填充多邊形的頂點(diǎn)數(shù)及其頂點(diǎn)坐標(biāo)。這里，頂點(diǎn)數(shù)為實(shí)際頂點(diǎn)數(shù)加1，最后一個(gè)頂點(diǎn)坐標(biāo)與第一個(gè)頂點(diǎn)坐標(biāo)相同。②計(jì)算所有多邊形頂點(diǎn)坐標(biāo)中y的最大值和最小值，以此作為掃描線的處理范圍。③對(duì)處理范圍內(nèi)的每條掃描線建立有序邊表。

④對(duì)處理范圍內(nèi)的每條掃描線，重復(fù)下列步驟：第五十五頁，共一百四十六頁，2022年，8月28日

A．用有序邊表建立當(dāng)前掃描線的活化邊表；

B．從活化邊表中依次取出一對(duì)交點(diǎn)，對(duì)該兩個(gè)交點(diǎn)內(nèi)的像素進(jìn)行填充；

C．為下一條掃描線更新活化邊表，即增加交點(diǎn)的x值和刪除不再相交的邊；

D．重排活化邊表。#defineWINDOW_HEIGHT480typedefstructpoint{intx,y;}POINT;以下是有序邊表填充算法的C語言描述。

第五十六頁，共一百四十六頁，2022年，8月28日//按交點(diǎn)x的升序?qū)呥M(jìn)行插入排序voidInsertEdge(Edge*list,Edge*edge)//生成有序邊表的一條邊voidMakeEdgeRec(POINTlower,POINTupper,intyComp,Edge*edge,Edge*edges[])voidBuildEdgeList(intcnt,POINT*pts,Edge*edges[])//建立有序邊表voidBuildActiveList(intscan,Edge*active,Edge*edges[])//建立活化邊表voidDeleteAfter(Edge*q)//刪除不再相交的邊

//更新活化邊表

voidUpdateActiveList(intscan,Edge*active)voidResortActiveList(Edge*active)//重排活化邊表

第五十七頁，共一百四十六頁，2022年，8月28日voidFillScan(intscan,Edge*active,intcolor)//對(duì)當(dāng)前掃描線填充{Edge*p1,*p2;inti;p1=active–>next;while(p1){p2=p1–>next;for(i=p1–>x;i<p2–>x;i++) putpixel((int)i,scan,color);p1=p2–>next;}}第五十八頁，共一百四十六頁，2022年，8月28日voidScanFill(intcnt,POINT*pts,intcolor)//cnt為多邊形的頂點(diǎn)數(shù)，pts為頂點(diǎn)坐標(biāo)數(shù)組{Edge*edges[WINDOW_HEIGHT],*active;inti,scan,smax=0,smin=1024;for(i=0;i<cnt–1;i++)//求smax和smin{if(smax<pts[i].y)smax=pts[i].y;if(smin>pts[i].y)smin=pts[i].y;}for(scan=smin;scan<=smax;scan++)//初始化每條掃描線的邊鏈表

{edges[scan]=(Edge*)malloc(sizeof(Edge)); edges[scan]–>next=NULL;}第五十九頁，共一百四十六頁，2022年，8月28日

BuildEdgeList(cnt,pts,edges);//建立有序邊表

active=newEdge;//初始化活化邊表

active–>next=NULL;for(scan=smin;scan<=smax;scan++){BuildActiveList(scan,active,edges);if(active–>next){FillScan(scan,active,color);//填充當(dāng)前掃描線

UpdateActiveList(scan,active);//更新活化邊表

ResortActiveList(active);//重排活化邊表

}}}第六十頁，共一百四十六頁，2022年，8月28日3.3.2邊填充算法

邊填充算法的基本思想是：對(duì)于每一條掃描線和每條多邊形的交點(diǎn)(x1,y1)，將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。對(duì)多邊形的每條邊作此處理，多邊形的順序隨意。如圖3.9所示，為應(yīng)用最簡單的邊填充算法填充一個(gè)多邊形的示意圖。邊填充算法最適用于具有幀緩沖器的圖形系統(tǒng)，按任意順序處理多邊形的邊。在處理每條邊時(shí)，僅訪問與該邊有交的掃描線上交點(diǎn)右方的像素。當(dāng)所有的邊都處理之后，按掃描線順序讀出幀緩沖器的內(nèi)容，送入顯示設(shè)備。第六十一頁，共一百四十六頁，2022年，8月28日P5P4P3P1P2P2P3P3P4P4P5P5P1圖3.9邊填充算法示意圖

本算法的優(yōu)點(diǎn)是簡單，缺點(diǎn)是對(duì)于復(fù)雜圖形，每一像素可能被訪問多次，輸入/輸出的量比有序邊表算法大得多。第六十二頁，共一百四十六頁，2022年，8月28日為了減少邊填充算法訪問像素的次數(shù)，可引入柵欄。所謂柵欄指的是一條與掃描線垂直的直線，柵欄位置通常取過多邊形頂點(diǎn)、且把多邊形分為左右兩半。柵欄填充法的基本思想是：對(duì)于每個(gè)掃描線與多邊形的交點(diǎn)，就將交點(diǎn)與柵欄之間的像素取補(bǔ)。若交點(diǎn)位于柵欄左側(cè)，則將交點(diǎn)之右至柵欄之左的所有像素取補(bǔ)；若交點(diǎn)位于柵欄右邊，則將柵欄之右至交點(diǎn)之左的像素取補(bǔ)。圖3.10為柵欄填充法示意圖。

第六十三頁，共一百四十六頁，2022年，8月28日P5P4P3P1P2P2P3P4P5P3P4P5P1圖3.10柵欄填充算法示意圖

第六十四頁，共一百四十六頁，2022年，8月28日柵欄填充算法只是減少了被重復(fù)訪問的像素的數(shù)目，但仍有一些像素會(huì)被重復(fù)訪問。因此又進(jìn)一步提出了改進(jìn)的邊標(biāo)志算法，使得算法對(duì)每個(gè)像素僅訪問一次。

邊標(biāo)志算法分為兩步驟：第一步，對(duì)多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，亦即對(duì)多邊形邊界所經(jīng)過的像素打上邊標(biāo)志；第六十五頁，共一百四十六頁，2022年，8月28日第二步，填充。對(duì)每條與多邊形相交的掃描線，依從左到右順序，逐個(gè)訪問該掃描線上像素。使用一個(gè)布爾量inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。上述邊標(biāo)志算法思想可歸納為如下偽程序：

inside的初始值為假，每當(dāng)當(dāng)前訪問像素為被打上邊標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的像素，inside不變。若訪問當(dāng)前像素時(shí)，對(duì)inside作必要操作之后，inside為真，則把該像素置為多邊形色。第六十六頁，共一百四十六頁，2022年，8月28日voidedge_mark_fill(polydef,color)多邊形定義polydef;intcolor;{

對(duì)多邊形polydef每條邊進(jìn)行直線掃描轉(zhuǎn)換;inside=FALSE;for(每條與多邊形polydef相交的掃描線y){if(像素x被打上邊標(biāo)志)inside=!(inside);if(inside!=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background);}}第六十七頁，共一百四十六頁，2022年，8月28日3.3.3種子填充算法

種子填充算法則采用不同的原理：填充方法是從多邊形區(qū)域內(nèi)部的一點(diǎn)開始，由此出發(fā)找到區(qū)域內(nèi)的所有像素。這種填充算法在交互式繪圖中很常用。

種子填充算法采用的邊界定義是區(qū)域邊界上所有像素均具有某個(gè)特定的顏色值，區(qū)域內(nèi)部所有像素均不取這一特定顏色，而邊界外的像素則可具有與邊界相同的顏色值。第六十八頁，共一百四十六頁，2022年，8月28日程序從(x，y)開始，先檢測(cè)該點(diǎn)的顏色，如果它與邊界色和填充色均不相同，就用填充色填充該點(diǎn)，然后檢測(cè)相鄰位置，以確定它們是否是邊界色和填充色，若不是，就填充該相鄰點(diǎn)。這個(gè)過程延續(xù)到已經(jīng)檢測(cè)完區(qū)域邊界范圍內(nèi)的所有像素為止。

從當(dāng)前點(diǎn)檢測(cè)相鄰像素有兩種方法：四向連通和八向連通。四向連通方法指的是從區(qū)域上一點(diǎn)出發(fā)，可通過四個(gè)方向，即上、下、左、右移動(dòng)的組合，在不越出區(qū)域的前提下，到達(dá)區(qū)域內(nèi)的任意像素；第六十九頁，共一百四十六頁，2022年，8月28日八向連通方法指的是區(qū)域內(nèi)每一個(gè)像素，可以通過左、右、上、下、左上、右上、左下、右下這八個(gè)方向的移動(dòng)的組合來到達(dá)。種子填充算法中允許從四個(gè)方向?qū)ふ蚁乱幌袼卣撸Q為四向算法；允許從八個(gè)方向搜索下一像素者，稱為八向算法。八向算法可以填充八向連通區(qū)域，也可以填充四向連通區(qū)域。但四向算法只能填充四向連通區(qū)域，而不能填充八向填充區(qū)域。以下我們只討論四向算法。只要把搜索方向從四個(gè)改變八個(gè)，即可得到八向算法。

第七十頁，共一百四十六頁，2022年，8月28日下面程序給出了四向連通填充的遞歸算法。voidboundaryfill4(intseedx,intseedy,intfcolor,intbcolor){intcurrent=getpixel(seedx,seedy);if((current!=bcolor)&&(current!=fcolor)){ putpixel(seedx,seedy,fcolor); boundaryfill4(seedx+1,seedy,fcolor,bcolor); boundaryfill4(seedx–1,seedy,fcolor,bcolor); boundaryfill4(seedx,seedy+1,fcolor,bcolor); boundaryfill4(seedx,seedy–1,fcolor,bcolor);}}第七十一頁，共一百四十六頁，2022年，8月28日voidSeedFill(intcnt,POINT*pts,intseedx,intseedy,intfcolor,intbcolor){POINTv1,v2;inti;for(i=0;i<cnt–1;i++){v1=pts[i];v2=pts[i+1];BoundaryMark(v1.x,v1.y,v2.x,v2.y,bcolor);}boundaryfill4(seedx,seedy,fcolor,bcolor);}第七十二頁，共一百四十六頁，2022年，8月28日這種算法的優(yōu)點(diǎn)是算法簡單，易于實(shí)現(xiàn)，也可以填充帶有內(nèi)孔的平面區(qū)域。但是這種算法需要很大的存儲(chǔ)空間以實(shí)現(xiàn)棧結(jié)構(gòu)，同一個(gè)像素多次入棧和出棧，所花費(fèi)的時(shí)間也很多。因此后來提出了許多改進(jìn)的算法，如書上的掃描線種子填充算法，我也提出了一個(gè)鏈隊(duì)列種子填充算法。

鏈隊(duì)列種子填充算法的算法基本思路是：從鏈隊(duì)列中獲得一個(gè)像素點(diǎn)，判斷其四連通像素點(diǎn)，若沒有填充，則填充它，并將它入隊(duì)列，如此循環(huán)，直到隊(duì)列空為止。

第七十三頁，共一百四十六頁，2022年，8月28日3.3.4圓和橢圓的填充

上面所討論的多邊形區(qū)域的填充原理也可以推廣到圓域的填充。由于圓和橢圓的特殊屬性，即可依據(jù)任何欲填充的像素點(diǎn)與圓心的距離是否大于或小于半徑來判斷是否在圓外或圓內(nèi)，或者依據(jù)欲填充的像素點(diǎn)與橢圓兩焦點(diǎn)的距離之和是否大于或小于橢圓的半徑常數(shù)來判斷是否在橢圓外或橢圓內(nèi)，因此圓和橢圓的填充采用種子填充算法最為簡單，并且它不需要先對(duì)圓或橢圓邊界進(jìn)行掃描轉(zhuǎn)換。

以下是圓的四向連通填充算法的C語言描述。第七十四頁，共一百四十六頁，2022年，8月28日voidCircleFill4(intxc,intyc,intr,intseedx,intseedy,intcolor){intfill=getpixel(seedx,seedy);if(((seedx–xc)*(seedx–xc)+(seedy–yc)*(seedy–yc)<=r*r)&&(fill!=color)){putpixel(seedx,seedy,color); CircleFill4(xc,yc,r,seedx+1,seedy,color);CircleFill4(xc,yc,r,seedx–1,seedy,color); CircleFill4(xc,yc,r,seedx,seedy+1,color); CircleFill4(xc,yc,r,seedx,seedy–1,color);}}第七十五頁，共一百四十六頁，2022年，8月28日3.3.5圖案填充

前面介紹的區(qū)域填充算法，把區(qū)域內(nèi)部的像素全部置成同一種顏色。但在實(shí)際應(yīng)用中，有時(shí)需要用一種圖案來填充平面區(qū)域。這可以通過對(duì)前述填充算法中寫像素的那部分代碼稍作修改來實(shí)現(xiàn)：在確定了區(qū)域內(nèi)一像素之后,不是馬上往該像素填色，而是先查詢圖案位圖的對(duì)應(yīng)位置。若是以透明方式填充圖案,則當(dāng)圖案的對(duì)應(yīng)位置為1時(shí),用前景色寫像素,否則,不改變?cè)撓袼氐闹?。若以不透明方式填充圖案，則視圖案位圖對(duì)應(yīng)位置為1或0來決定是用前景色還是背景色去寫像素。

第七十六頁，共一百四十六頁，2022年，8月28日進(jìn)行圖案填充時(shí),在不考慮圖案旋轉(zhuǎn)的情況下，必須確定區(qū)域與圖案之間的位置關(guān)系。這可以通過把圖案原點(diǎn)與圖形區(qū)某點(diǎn)對(duì)齊的辦法來實(shí)現(xiàn)。對(duì)齊方法有兩種。第一種方式是把圖案原點(diǎn)與填充區(qū)域邊界或內(nèi)部的某點(diǎn)對(duì)齊。第二種方式是把圖案原點(diǎn)與填充區(qū)域外部的某點(diǎn)對(duì)齊。用第一種方式填充的圖案，將隨著區(qū)域的移動(dòng)而跟著移動(dòng)，看起來很自然。對(duì)于多邊形，可取區(qū)域邊界上最左邊的頂點(diǎn)。而對(duì)于圓和橢圓這樣的具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點(diǎn)，如中心，對(duì)應(yīng)圖案原點(diǎn)。第七十七頁，共一百四十六頁，2022年，8月28日從算法復(fù)雜性看，第二種方法比較簡單，并且在相鄰區(qū)域用同一圖案填充時(shí)，可以達(dá)到無縫連接的效果。但是它有一個(gè)潛在的毛病，即當(dāng)區(qū)域移動(dòng)時(shí)，圖案不會(huì)跟著移動(dòng)。其結(jié)果是區(qū)域內(nèi)的圖案變了。

下面我們來討論在第二種對(duì)齊方式下，如何對(duì)平面區(qū)域填充圖案。假定圖案是一個(gè)M×N位圖，用M×N數(shù)組存放。M、N一般比需要填充的區(qū)域的尺寸小得多。所以圖案總是設(shè)計(jì)成周期性的，使之能通過重復(fù)使用，構(gòu)成任意尺寸的圖案。第七十八頁，共一百四十六頁，2022年，8月28日當(dāng)需要填充的區(qū)域與當(dāng)前掃描線的相交區(qū)間確定之后，假定相交區(qū)間上一像素坐標(biāo)為(x,y)，則圖案位圖上的對(duì)應(yīng)位置為(x％M,y％N)，其中％為C語言整除取余運(yùn)算符。若采用不透明方式填充圖案，則應(yīng)把算法中用前景色color寫像素的操作putpixel(x,y,color)，改為當(dāng)圖案值為1時(shí)，用前景色color寫，否則，用背景色bkcolor寫，即if(pattern(x％M，y％N))putpixel(x,y,color)；

elseputpixel(x,y,bkcolor)；

第七十九頁，共一百四十六頁，2022年，8月28日采用透明方式填充圖案時(shí)，只要去掉else分句即可。以下是把有序邊表填充算法改為用圖案填充的算法。為了節(jié)省篇幅，以下僅給出圖案的定義和有序邊表填充算法中修改后的FillScan函數(shù)。圖案定義：intpattern[8][8]={{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{0,0,0,1,1,1,1,1},{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{1,1,1,1,0,0,0,1}};(注：這里列為x方向，行為y方向)第八十頁，共一百四十六頁，2022年，8月28日修改后的FillScan函數(shù)：voidFillScan(intscan,Edge*active,intcolor){Edge*p1,*p2;inti;p1=active–>next;while(p1){p2=p1–>next;for(i=p1–>x;i<p2–>x;i++)

if(pattern[i%8][scan%8])