基本圖形生成

基本圖形生成第一頁，共一百四十六頁，編輯于2023年，星期五

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

color)；

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

y=k·x+b(3–1)其中，k表示斜率，b是y軸截距。第五頁，共一百四十六頁，編輯于2023年，星期五為此，只需讓x從起點到終點每次增加(或減少)1,用(3–1)式計算對應的y值,再用putpixel(x,

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

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

b=y1–k·x1

但是，用這種方法畫線效率太低，這是因為每步都需要一個浮點乘法運算和一個四舍五入運算。為此我們要尋找更快的畫線方法。第六頁，共一百四十六頁，編輯于2023年，星期五3.1.1數(shù)值微分法

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

k·△x(3–2)或△x=△y/k(3–3)對于具有斜率絕對值|k|<1的線段，可以讓x從起點到終點變化，每步遞增(或遞減)1，即令△x=±1，則△y=±k。若前一次的直線上像素點坐標為

(xi,yi)，這一次的直線上像素點坐標為

(xi+1,yi+1)，則xi+1=xi±1，yi+1=yi±k。隨后用putpixel函數(shù)輸出該像素的顏色值即可。見圖3.1。第七頁，共一百四十六頁，編輯于2023年，星期五(xi,yi)(xi,(int)(yi+0.5))(xi+1,yi)(xi+1,(int)(yi+0.5))圖3.1數(shù)值微分法示意圖

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

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

第八頁，共一百四十六頁，編輯于2023年，星期五上述采用的增量計算方法稱為數(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;}}第九頁，共一百四十六頁，編輯于2023年，星期五3.1.2中點畫線法

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

那么，下一個與直線最近的像素只能是正右方的P1(xp+1、yp)或右上方的P2(xp+1、yp+1)兩者之一，用空心小圓表示。第十頁，共一百四十六頁，編輯于2023年，星期五為了方便地確定出下一個像素是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)，則上述參數(shù)：a=y1-y2，b=x2-x1，c=

x1y2-x2y1。第十一頁，共一百四十六頁，編輯于2023年，星期五對于直線上的點，F(xiàn)(x,y)=0；對于直線上方的點，F(xiàn)(x,y)>0；而對于直線下方的點，F(xiàn)(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，根據(jù)它的符號確定下一像素。第十二頁，共一百四十六頁，編輯于2023年，星期五由于d是xp和yp的線性函數(shù)，可采用增量計算，以便提高運算效率。在d≥0的情況下，取正右方像素P1，欲判斷再下一個像素應取那個，應計算

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。要判斷再下一個像素，應計算

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第十三頁，共一百四十六頁，編輯于2023年，星期五再看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的增量都是整數(shù)，只是其初始值包含小數(shù)。因此，我們可以用2d代替d，就可以寫出僅包含整數(shù)運算的中點畫線算法(斜率在0～l)：

故d的增量為a＋b。

第十四頁，共一百四十六頁，編輯于2023年，星期五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);}}第十五頁，共一百四十六頁，編輯于2023年，星期五3.1.3Bresenham畫線算法

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

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

第十六頁，共一百四十六頁，編輯于2023年，星期五在列位置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圖3.3

兩個候選像素的y值與線段上理想y值的差值d1和d2第十七頁，共一百四十六頁，編輯于2023年，星期五設△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步的決策參數(shù),則dk的計算僅包含整數(shù)運算,它的符號與d1–d2的符號相同。c為常量，在計算中將被消除。

第十八頁，共一百四十六頁，編輯于2023年，星期五在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

第十九頁，共一百四十六頁，編輯于2023年，星期五在每個整數(shù)x位置,從線段的坐標端點開始,反復進行決策參數(shù)的這種循環(huán)計算。在起始像素(x1,y1)的第一個參數(shù)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–△x第二十頁，共一百四十六頁，編輯于2023年，星期五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；}}}第二十一頁，共一百四十六頁，編輯于2023年，星期五3.2圓與橢圓的生成

3.2.1圓的特性

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

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

(x–xc)2+(y–yc)2=r2第二十二頁，共一百四十六頁，編輯于2023年，星期五利用這個方程，我們可以沿x軸從xc–r到xc+r以單位步長計算對應的y值來得到圓周上每點的位置：

y=yc

±

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

第二十三頁，共一百四十六頁，編輯于2023年，星期五另一種消除不等間距的方法是使用極坐標r和θ計算沿圓周的點。以參數(shù)極坐標形式表示圓方程可得到方程組：

x=xc+rcosθ

y=yc+rsinθ

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

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

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

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

第二十五頁，共一百四十六頁，編輯于2023年，星期五3.2.2中點畫圓法

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

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

F(x,y)=x2＋y2–r2(3–5)第二十七頁，共一百四十六頁，編輯于2023年，星期五若d＜0，則應取P1為下一像素，而且再下一個像素的判別式為

d=F(xp

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

–0.5)2–R2

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

與中點畫線法一樣，構造判別式

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

第二十八頁，共一百四十六頁，編輯于2023年，星期五而若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第二十九頁，共一百四十六頁，編輯于2023年，星期五由于上述公式中只有d0包含小數(shù)，而它又僅僅作為一個判別式，因此可以做一些特殊處理來擺脫浮點數(shù)，在算法中全部使用整數(shù)。若用e=d–0.25代替d，則d0=l.25–r對應于e0

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

以下是中點畫圓算法的C語言描述：第三十頁，共一百四十六頁，編輯于2023年，星期五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）；

}}第三十一頁，共一百四十六頁，編輯于2023年，星期五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)；}第三十二頁，共一百四十六頁，編輯于2023年，星期五3.2.3Bresenham畫圓算法

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

xi+1=xi+1則相應的y有二種選擇：

yi+1=yi

或yi+1=yi-1第三十三頁，共一百四十六頁，編輯于2023年，星期五

Bresenham畫圓算法采用一個決策值來確定到底是選擇yi還是yi-1。在x=xi+1位置上，用d1和d2來標識兩個候選像素的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，則可任選一個，我們約定yi+1=yi-1。

第三十四頁，共一百四十六頁，編輯于2023年，星期五下面來推導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程序：

第三十五頁，共一百四十六頁，編輯于2023年，星期五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);}第三十六頁，共一百四十六頁，編輯于2023年，星期五3.2.4橢圓的生成算法

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

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

第三十七頁，共一百四十六頁，編輯于2023年，星期五以下我們先考慮標準位置的橢圓，即：

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

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

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

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

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

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

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

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

2b2x=2a2y

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

2b2x>=2a2y

第三十九頁，共一百四十六頁，編輯于2023年，星期五與中點畫圓算法類似，當我們確定一個像素之后，接著在兩個候選像素的中點計算一個判別式的值。并根據(jù)判別式符號確定兩個候選像素哪個離橢圓更近。下面討論算法的具體步驟。先看橢圓弧的上部分。假設當前已確定的橢圓弧上的像素點為(xp,yp)，那么下一對候選像素的中點是(xp+l,yp–0.5)。

因此判別式為

dp=F(xp+1,yp–0.5)=b2(xp+1)2+a2(yp–0.5)2–a2b2它的符號將決定下一個像素是取正右方的那個，還是右下方的那個。第四十頁，共一百四十六頁，編輯于2023年，星期五若dp<0，中點在橢圓內(nèi)，則應取正右方像素，且判別式應更新為

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)。而當dp≥0，中點在橢圓之外，這時應取右下方像素，并且更新判別式為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第四十一頁，共一百四十六頁，編輯于2023年，星期五所以，沿右下方向，判別式d的增量為：

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

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

第四十三頁，共一百四十六頁，編輯于2023年，星期五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);}第四十四頁，共一百四十六頁，編輯于2023年，星期五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);}}第四十五頁，共一百四十六頁，編輯于2023年，星期五3.3區(qū)域填充3.3.1有序邊表填充算法本節(jié)討論如何用一種顏色或圖案來填充一個二維區(qū)域。填充的區(qū)域可以是多邊形的，也可以是圓或橢圓的，還可以是帶孔的。區(qū)域填充可以分兩步進行，第一步先確定需要填充哪些像素。第二步確定用什么顏色值或圖案來填充。多邊形區(qū)域填充的一種常用方法是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。第四十六頁，共一百四十六頁，編輯于2023年，星期五ABCDP1P2P3P4P5P62468102468Oyx如圖3.8所示，掃描線3與多邊形的邊界線交于四點A、B、C、D。這四點把掃描線分為四個區(qū)間[0,3],[3,4.5],[4.5,6],[6,8.3],[8.3,11]。其中,[3,4.5],[6,8.3]兩個區(qū)間落在多邊形內(nèi)，該區(qū)間內(nèi)的像素應取多邊形色。其他區(qū)間內(nèi)的像素取背景色。

圖3.8多邊形與掃描線

第四十七頁，共一百四十六頁，編輯于2023年，星期五有些在多邊形頂點處的掃描線交點需要專門處理。在這些位置上，掃描線通過一個頂點與多邊形的兩條邊相交。例如圖3.8所示，若交點算一個，則掃描線2與P6相交，求得交點(x坐標)序列3,6.5,7.5。這將導致[3,6.5]區(qū)間內(nèi)的像素被填充，而這個區(qū)間的像素是屬于多邊形外部，不需要填充。若交點算二個，則掃描線7與P1相交，求得交點(x坐標)序列2,2,10。這將導致[2,10]區(qū)間內(nèi)的像素不被填充，而這個區(qū)間的像素是屬于多邊形內(nèi)部，需要填充。

第四十八頁，共一百四十六頁，編輯于2023年，星期五為了正確地進行交點取舍，必須對上述兩種情況區(qū)別對待。在第一種情況，掃描線交于一頂點，而共享頂點的兩條邊分別落在掃描線的兩邊。這時，交點只算一個。在第二種情況，共享交點的兩條邊在掃描線的同一邊，這時交點作為零個或兩個，取決于該點是多邊形的局部最高點還是局部最低點。具體實現(xiàn)時，只需檢查頂點的兩條邊的另外兩個端點的y值。按這兩個y值中大于交點y值的個數(shù)是0，1，2來決定是取零個、一個、還是兩個。第四十九頁，共一百四十六頁，編輯于2023年，星期五例如，掃描線1交頂點P4，由于共享該頂點的兩條邊的另外二個頂點均高于掃描線，故取交點P4兩次。這使得P4像素用多邊形顏色設置。而在P2處，由于P1和P3均在下方，所以掃描線9與之相交時，交點算零個，該點不予填充。

在處理一條掃描線時，只需對與它相交的多邊形的邊進行求交運算。由于邊的連貫性，即當某條邊與當前掃描線相交時，它很可能也與下一條掃描線相交，為此，計算下一條掃描線與同一條邊的交點x值時，只需把當前交點x值加上一個邊的反斜率即可：

xk+1=xk

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

第五十頁，共一百四十六頁，編輯于2023年，星期五我們把與當前掃描線相交的邊稱為活化邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中，稱此鏈表為活化邊表。令△x=1/m為常量，可以存放在對應邊的活化邊表結(jié)點中。

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

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

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

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

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

④對處理范圍內(nèi)的每條掃描線，重復下列步驟：第五十五頁，共一百四十六頁，編輯于2023年，星期五

A．用有序邊表建立當前掃描線的活化邊表；

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

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

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

第五十六頁，共一百四十六頁，編輯于2023年，星期五//按交點x的升序?qū)呥M行插入排序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)//重排活化邊表

第五十七頁，共一百四十六頁，編輯于2023年，星期五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++) putpixel((int)i,scan,color);p1=p2–>next;}}第五十八頁，共一百四十六頁，編輯于2023年，星期五voidScanFill(intcnt,POINT*pts,intcolor)//cnt為多邊形的頂點數(shù)，pts為頂點坐標數(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;}第五十九頁，共一百四十六頁，編輯于2023年，星期五

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);//填充當前掃描線

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

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

}}}第六十頁，共一百四十六頁，編輯于2023年，星期五3.3.2邊填充算法

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

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

第六十三頁，共一百四十六頁，編輯于2023年，星期五P5P4P3P1P2P2P3P4P5P3P4P5P1圖3.10柵欄填充算法示意圖

第六十四頁，共一百四十六頁，編輯于2023年，星期五柵欄填充算法只是減少了被重復訪問的像素的數(shù)目，但仍有一些像素會被重復訪問。因此又進一步提出了改進的邊標志算法，使得算法對每個像素僅訪問一次。

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

inside的初始值為假，每當當前訪問像素為被打上邊標志的點，就把inside取反。對未打標志的像素，inside不變。若訪問當前像素時，對inside作必要操作之后，inside為真，則把該像素置為多邊形色。第六十六頁，共一百四十六頁，編輯于2023年，星期五voidedge_mark_fill(polydef,color)多邊形定義polydef;intcolor;{

對多邊形polydef每條邊進行直線掃描轉(zhuǎn)換;inside=FALSE;for(每條與多邊形polydef相交的掃描線y){if(像素x被打上邊標志)inside=!(inside);if(inside!=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background);}}第六十七頁，共一百四十六頁，編輯于2023年，星期五3.3.3種子填充算法

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

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

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

第七十頁，共一百四十六頁，編輯于2023年，星期五下面程序給出了四向連通填充的遞歸算法。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);}}第七十一頁，共一百四十六頁，編輯于2023年，星期五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);}第七十二頁，共一百四十六頁，編輯于2023年，星期五這種算法的優(yōu)點是算法簡單，易于實現(xiàn)，也可以填充帶有內(nèi)孔的平面區(qū)域。但是這種算法需要很大的存儲空間以實現(xiàn)棧結(jié)構，同一個像素多次入棧和出棧，所花費的時間也很多。因此后來提出了許多改進的算法，如書上的掃描線種子填充算法，我也提出了一個鏈隊列種子填充算法。

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

第七十三頁，共一百四十六頁，編輯于2023年，星期五3.3.4圓和橢圓的填充

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

以下是圓的四向連通填充算法的C語言描述。第七十四頁，共一百四十六頁，編輯于2023年，星期五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);}}第七十五頁，共一百四十六頁，編輯于2023年，星期五3.3.5圖案填充

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

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

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

elseputpixel(x,y,bkcolor)；

第七十九頁，共一百四十六頁，編輯于2023年，星期五采用透明方式填充圖案時，只要去掉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方向)第八十頁，共一百四十六頁，編輯于2023年，星期五修改后的FillScan函數(shù)：voidFillScan(intscan,Edge*active,intcolor){Edge*p1,*p2;inti;p1=active–>next;while(p1){p2=p1–>next;for(i=p1