計算機(jī)圖形學(xué)常用算法及代碼大全

1、2.1.1 生成直線的DDA算法數(shù)值微分法即DDA法(Digital Differential Analyzer)，是一種基于直線的微分方程來生成直線的方法。一、直線DDA算法描述：設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點(diǎn)和終點(diǎn)坐標(biāo)，由直線的微分方程得= m =直線的斜率(21)可通過計算由x方向的增量x引起y的改變來生成直線：xi+1=xi+x(22)yi+1=yi+y=yi+x·m(23)也可通過計算由y方向的增量y引起x的改變來生成直線：yi+1=yi+y(24)xi+1=xi+x=xi+y/m(25)式(22)至(25)是遞推的。二、直線DDA算法思想：選定x2x

2、1和y2y1中較大者作為步進(jìn)方向(假設(shè)x2x1較大)，取該方向上的增量為一個象素單位(x=1)，然后利用式(21)計算另一個方向的增量(y=x·m=m)。通過遞推公式(22)至(25)，把每次計算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。之所以取x2x1和y2y1中較大者作為步進(jìn)方向，是考慮沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。另外，算法實現(xiàn)中還應(yīng)注意直線的生成方向，以決定x及y是取正值還是負(fù)值。三、直線DDA算法實現(xiàn)：1、已知直線的兩端點(diǎn)坐標(biāo)：(x1，y1)，(x2，y2)2、已知畫線的顏色：color3、計算兩個方向的變化量：dx=x2x1

3、dy=y2y14、求出兩個方向最大變化量的絕對值： steps=max(|dx|，|dy|)5、計算兩個方向的增量(考慮了生成方向)： xin=dx/steps yin=dy/steps6、設(shè)置初始象素坐標(biāo)：x=x1,y=y17、用循環(huán)實現(xiàn)直線的繪制：for(i=1；i<=steps；i+) putpixel(x，y，color)；/*在(x，y)處，以color色畫點(diǎn)*/x=x+xin； y=y+yin； 五、直線DDA算法特點(diǎn)：該算法簡單，實現(xiàn)容易，但由于在循環(huán)中涉及實型數(shù)的運(yùn)算，因此生成直線的速度較慢。/brief 浮點(diǎn)數(shù)轉(zhuǎn)整數(shù)的宏實現(xiàn)代碼#define FloatToIntege

4、r(fNum) (fNum>0)?static_cast<int>(fNum+0.5):static_cast<int>(fNum-0.5)/*!* brief DDA畫線函數(shù)* param pDC in窗口DC* param BeginPt in直線起點(diǎn)* param EndPt in直線終點(diǎn)* param LineCor in直線顏色* return 無*/void CDrawMsg:DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor)long YDis =

5、(EndPt.y - BeginPt.y);long XDis = (EndPt.x-BeginPt.x);long MaxStep = max(abs(XDis),abs(YDis); / 步進(jìn)的步數(shù)float fXUnitLen = 1.0f; / X方向的單位步進(jìn)float fYUnitLen = 1.0f; / Y方向的單位步進(jìn)fYUnitLen = static_cast<float>(YDis)/static_cast<float>(MaxStep);fXUnitLen = static_cast<float>(XDis)/static_cast

6、<float>(MaxStep);/ 設(shè)置起點(diǎn)像素顏色pDC->SetPixel(BeginPt.x,BeginPt.y,LineCor); float x = static_cast<float>(BeginPt.x);float y = static_cast<float>(BeginPt.y);/ 循環(huán)步進(jìn)for (long i = 1;i<=MaxStep;i+)x = x + fXUnitLen;y = y + fYUnitLen;pDC->SetPixel(FloatToInteger(x),FloatToInteger(y),

7、LineCor);2.1.2 生成直線的Bresenham算法從上面介紹的DDA算法可以看到，由于在循環(huán)中涉及實型數(shù)據(jù)的加減運(yùn)算，因此直線的生成速度較慢。在生成直線的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來生成直線的方法。一、直線Bresenham算法描述：它也是采用遞推步進(jìn)的辦法，令每次最大變化方向的坐標(biāo)步進(jìn)一個象素，同時另一個方向的坐標(biāo)依據(jù)誤差判別式的符號來決定是否也要步進(jìn)一個象素。我們首先討論m=y/x，當(dāng)0m1且x1<x2時的Bresenham算法。從DDA直線算法可知這些條件成立時，公式(2-2)、(2-3)可寫成：xi+1

8、=xi+1(26)yi+1=yi+m(27)有兩種Bresenham算法思想，它們各自從不同角度介紹了Bresenham算法思想，得出的誤差判別式都是一樣的。二、直線Bresenham算法思想之一：由于顯示直線的象素點(diǎn)只能取整數(shù)值坐標(biāo)，可以假設(shè)直線上第i個象素點(diǎn)坐標(biāo)為(xi，yi)，它是直線上點(diǎn)(xi，yi)的最佳近似，并且xi=xi(假設(shè)m<1），如下圖所示。那么，直線上下一個象素點(diǎn)的可能位置是(xi+1，yi)或(xi+1，yi+1)。由圖中可以知道，在x=xi+1處，直線上點(diǎn)的y值是y=m(xi+1)+b，該點(diǎn)離象素點(diǎn)(xi+1，yi)和象素點(diǎn)(xi+1，yi+1)的距離分別是d1

9、和d2： d1=y-yi=m(xi+1)+b-yi(28)d2=(yi+1)-y=(yi+1)-m(xi+1)-b(29)這兩個距離差是d1-d2=2m(xi+1)-2yi2b-1(210)我們來分析公式(2-10)：(1)當(dāng)此值為正時，d1>d2，說明直線上理論點(diǎn)離(xi+1，yi+1)象素較近，下一個象素點(diǎn)應(yīng)取(xi+1，yi+1)。(2)當(dāng)此值為負(fù)時，d1<d2，說明直線上理論點(diǎn)離(xi+1，yi)象素較近，則下一個象素點(diǎn)應(yīng)取(xi+1，yi)。(3)當(dāng)此值為零時，說明直線上理論點(diǎn)離上、下兩個象素點(diǎn)的距離相等，取哪個點(diǎn)都行，假設(shè)算法規(guī)定這種情況下取(xi+1，yi+1)作為下

10、一個象素點(diǎn)。 因此只要利用(d1-d2)的符號就可以決定下一個象素點(diǎn)的選擇。為此，我們進(jìn)一步定義一個新的判別式：pi=x×(d1-d2)=2y·xi-2x·yi+c(211)式(2-11)中的x=(x2-x1)>0，因此pi與(d1-d2)有相同的符號；這里y=y2-y1，m=y/x；c=2y+x(2b-1)。下面對式(2-11)作進(jìn)一步處理，以便得出誤差判別遞推公式并消除常數(shù)c。將式(2-11)中的下標(biāo)i改寫成i+1，得到：pi+1=2y·xi+1-2x·yi+1+c(212)將式(2-12)減去(2-11)，并利用xi+1=xi+1，

11、可得：pi+1= pi+2y-2x·(yi+1-yi)(213)再假設(shè)直線的初始端點(diǎn)恰好是其象素點(diǎn)的坐標(biāo)，即滿足：y1=mx1+b(214)由式(2-11)和式(2-14)得到p1的初始值： p1=2y-x(215)這樣，我們可利用誤差判別變量，得到如下算法表示：初始 p1=2y-x(216)當(dāng)pi0時： yi+1=yi+1,xi+1=xi+1，pi+1=pi+2(y-x)否則：yi+1=yi,xi+1=xi+1， pi+1=pi+2y從式(2-16)可以看出，第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線的兩個端點(diǎn)坐標(biāo)分量差x和y有關(guān)，運(yùn)算中只含有整數(shù)相加和乘2運(yùn)算，而

12、乘2可利用算術(shù)左移一位來完成，因此這個算法速度快并易于硬件實現(xiàn)。三、直線Bresenham算法思想之二：由于象素坐標(biāo)的整數(shù)性，數(shù)學(xué)點(diǎn)(xi，yi)與所取象素點(diǎn)(xi，yir)間會引起誤差(i)，當(dāng)xi列上已用象素坐標(biāo)(xi，yir)表示直線上的點(diǎn)(xi，yi)，下一直線點(diǎn)B(xi+1，yi+1)，是取象素點(diǎn)C(xi+1，yir )，還是D(xi1，y(i+1)r)呢？設(shè)A為CD邊的中點(diǎn)，正確的選擇：若B點(diǎn)在A點(diǎn)上方，選擇D點(diǎn)； 否則，選C點(diǎn)。用誤差式描述為：(xi+1)=BC-AC=(yi+1-yir)-0.5(28')求遞推公式：(xi+2)=(yi+2-y(i+1)r)-0.5 =

13、 yi+1+m-y(i+1)r-0.5(29')當(dāng)(xi+1)0時，選D點(diǎn)，y(i+1)r = yir+1(xi+2)= yi+1+m-yir-1-0.5=(xi+1)+m-1(210')當(dāng)(xi+1)0時，選C點(diǎn)，y(i+1)r = yir(xi+2)= yi+1+myir-0.5=(xi+1)+m(211')初始時：(xs+1)=BC-AC=m-0.5(212')為了運(yùn)算中不含實型數(shù)，同時不影響不等式的判斷，將方程兩邊同乘一正整數(shù)。令方程兩邊同乘2·x，即d=2·x·，則：初始時：d = 2·y-x(213')

14、遞推式：當(dāng)d0時： d=d+2·(yx)；y+；x+；否則： d=d+2·y；x+； (214')實現(xiàn)代碼void Bresenhamline (int x0,int y0,int x1, int y1,int color)  int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; i<=dx; i+)     drawp

15、ixel (x, y, color); x=x+1，e=e+k; if (e>=0)  y+, e=e-1; 或者將e擴(kuò)大2dx倍；void Bresenhamline (int x0,int y0,int x1, int y1,int color)int x, y, dx, dy;float k, e;dx = x1-x0, dy = y1- y0, k=dy/dx;e=-dx, x=x0, y=y0;for (i=0; i<=dx; i+) drawpixel (x, y, color);x=x+1，e=e+2dy;if (e>=0

16、) y+, e=e-2dx;四、直線Bresenham算法實現(xiàn)：條件：0m1且x1<x21、輸入線段的兩個端點(diǎn)坐標(biāo)和畫線顏色：x1，y1，x2，y2，color；2、設(shè)置象素坐標(biāo)初值：x=x1，y=y1；3、設(shè)置初始誤差判別值：p=2·y-x；4、分別計算：x=x2-x1、y=y2-y1；5、循環(huán)實現(xiàn)直線的生成：for(x=x1；x<=x2；x+) putpixel(x,y,color) ；if(p>=0) y=y+1；p=p+2·(y-x)；else p=p+2·y；五、直線Bresenham算法完善：現(xiàn)在我們修正(2-16)公式，以適應(yīng)對任何

17、方向及任何斜率線段的繪制。如下圖所示，線段的方向可分為八種，從原點(diǎn)出發(fā)射向八個區(qū)。由線段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。容易證明：當(dāng)線段處于、區(qū)時，以|x|和|y|代替前面公式中的x和y，當(dāng)線段處于、區(qū)時，將公式中的|x|和|y|對換，則上述兩公式仍有效。在線段起點(diǎn)區(qū)分線段方向七、直線Bresenham算法特點(diǎn)：由于程序中不含實型數(shù)運(yùn)算，因此速度快、效率高，是一種有效的畫線算法。2.2.2 中點(diǎn)算法生成圓中點(diǎn)畫圓算法在一個方向上取單位間隔，在另一個方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實際處理中，用決策變量的符號來確定象素點(diǎn)的選擇，因此算法效率較高。一、中點(diǎn)畫圓

18、算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0，R)處，終點(diǎn)在(，)處，順時針生成八分之一圓，利用對稱性掃描轉(zhuǎn)換全部圓。為了應(yīng)用中點(diǎn)畫圓法，我們定義一個圓函數(shù)F(x，y)=x2+y2-R2(219)任何點(diǎn)(x，y)的相對位置可由圓函數(shù)的符號來檢測：F(x，y)<0點(diǎn)(x，y)位于數(shù)學(xué)圓內(nèi)=0點(diǎn)(x，y)位于數(shù)學(xué)圓上>0點(diǎn)(x，y)位于數(shù)學(xué)圓外(220)如下圖所示，圖中有兩條圓弧A和B，假定當(dāng)前取點(diǎn)為Pi(xi，yi)，如果順時針生成圓，那么下一點(diǎn)只能取正右方的點(diǎn)E(xi+1，yi)或右下方的點(diǎn)SE(xi+1，yi-1)兩者之一。中點(diǎn)畫線算法假設(shè)M是E和SE的中點(diǎn)，即

19、 ，則：1、當(dāng)F(M)<0時，M在圓內(nèi)(圓弧A)，這說明點(diǎn)E距離圓更近，應(yīng)取點(diǎn)E作為下一象素點(diǎn)；2、當(dāng)F(M)>0時，M在圓外(圓弧B)，表明SE點(diǎn)離圓更近，應(yīng)取SE點(diǎn)；3、當(dāng)F(M)=0時，在E點(diǎn)與SE點(diǎn)之中隨便取一個即可，我們約定取SE點(diǎn)。 二、中點(diǎn)畫圓算法思想因此，我們用中點(diǎn)M的圓函數(shù)作為決策變量di，同時用增量法來迭代計算下一個中點(diǎn)M的決策變量di+1。(221)下面分兩種情況來討論在迭代計算中決策變量di+1的推導(dǎo)。1、見圖（a），若di<0，則選擇E點(diǎn)，接著下一個中點(diǎn)就是，這時新的決策變量為：(222)（a）(di<0) 中點(diǎn)畫線算法式(222)減去(221

20、)得：di+1=di+2xi+3(223)2、見圖（b），若di0，則選擇SE點(diǎn)，接著下一個中點(diǎn)就是 ，這時新的決策變量為：(224)（b）(di0) 中點(diǎn)畫線算法式(224)減去(221)得：di+1=di+2(xi-yi)+5(225)我們利用遞推迭代計算這八分之一圓弧上的每個點(diǎn)，每次迭代需要兩步處理：（1）用前一次迭代算出的決策變量的符號來決定本次選擇的點(diǎn)。（2）對本次選擇的點(diǎn)，重新遞推計算得出新的決策變量的值。剩下的問題是計算初始決策變量d0，如下圖所示。對于初始點(diǎn)(0，R)，順時針生成八分之一圓，下一個中點(diǎn)M的坐標(biāo)是 ，所以：(226生成圓的初始條件和圓的生成方向三、中點(diǎn)畫圓算法實現(xiàn)

21、1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x<=y)·利用八分對稱性，用規(guī)定的顏色color畫八個象素點(diǎn)(x，y)；· 若d0y=y-1；d=d+2(x-y)+5)；否則d=d+2x+3；·x=x+1；五、中點(diǎn)畫圓算法完善在上述算法中，使用了浮點(diǎn)數(shù)來表示決策變量d。為了簡化算法，擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d=5/4-r對應(yīng)于e=1-r。決策變量d<0對應(yīng)于e<-1/4。算法中其它與d有關(guān)的式子可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算

22、過程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e<-1/4等價于e<0。因此，可以寫出完全用整數(shù)實現(xiàn)的中點(diǎn)畫圓算法。要求：寫出用整數(shù)實現(xiàn)的中點(diǎn)畫圓算法程序，并上機(jī)調(diào)試，觀看運(yùn)行結(jié)果。六、中點(diǎn)畫圓算法程序void MidpointCircle(int x0,int y0,int r,int color)int x,y;float d;x=0;y=r;d=5.0/4-r;while(x<=y)putdot(x0,y0,x,y,color);if(d<0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;putdot(x0,y0,x,y,color)pu

23、tpixel(x0+x,y0+y,color);putpixel(x0+x,y0-y,color);putpixel(x0-x,y0+y,color);putpixel(x0-x,y0-y,color);putpixel(x0+y,y0+x,color);putpixel(x0+y,y0-x,color);putpixel(x0-y,y0+x,color);putpixel(x0-y,y0-x,color);2.2.3 正負(fù)算法生成圓正負(fù)法是利用平面曲線將平面劃分成正負(fù)區(qū)域，對當(dāng)前點(diǎn)產(chǎn)生的圓函數(shù)進(jìn)行符號判別，利用負(fù)反饋調(diào)整以決定下一個點(diǎn)的產(chǎn)生來直接生成圓弧。一、正負(fù)畫圓算法描述設(shè)要顯示圓的圓心

24、在原點(diǎn)(0，0)，半徑為R，初始點(diǎn)的坐標(biāo)為(0，R)，順時針生成八分之一圓，令：F(x，y)=x2+y2-R2則圓的方程為：F(x，y)=0 (2-27)當(dāng)點(diǎn)(x，y)在圓內(nèi)時，則F(x，y)<0；當(dāng)點(diǎn)(x，y)在圓外時，則F(x，y)>0；當(dāng)點(diǎn)(x，y)在圓上時，則F(x，y)=0；二、正負(fù)畫圓算法思想現(xiàn)以下圖的AB弧為例，來說明正負(fù)畫圓法(順時針生成圓)。假設(shè)當(dāng)前點(diǎn)為Pi(xi，yi)，取下一個點(diǎn)Pi+1(xi+1，yi+1)的原則是： 1、當(dāng)F(xi，yi)0時：取xi+1= xi+1，yi+1= yi。即向右走一步，從圓內(nèi)走向圓外。對應(yīng)圖(a)中的從Pi到Pi+1。2、當(dāng)F

25、(xi，yi)>0時：取xi+1= xi，yi+1= yi-1。即向下走一步，從圓外走向圓內(nèi)。對應(yīng)圖(b)中的從Pi到Pi+1。由于向圓內(nèi)或向圓外走取決于F(xi，yi)的正負(fù)，因此稱為正負(fù)法。下面分兩種情況求出F(xi，yi)的遞推公式：(1) 當(dāng)F(xi，yi)0時，向右走，取xi+1=xi+1，yi+1=yi，則F(xi+1，yi+1)=F(xi+1，yi)=(xi+1)2+yi2-R2=(xi2+yi2-R2)+2xi+1= F(xi，yi)+2xi+1(2-28)(2) 當(dāng)F(xi，yi)>0時，向下走，取xi+1=xi，yi+1=yi-1，則F(xi+1，yi+1)=F

26、(xi，yi-1)=xi2+(yi-1)2-R2=(xi2+yi2-R2)-2yi+1= F(xi，yi)-2yi+1(2-9)初始時，x=0，y=R，故 F(0，R)=(02+R2)-R2=0 (2-30)公式(2-28)、(2-29)和(2-30)就構(gòu)成正負(fù)畫圓算法的核心。給象素坐標(biāo)(x，y)及F賦初始值后，進(jìn)入循環(huán)畫點(diǎn)；畫點(diǎn)后，根據(jù)F的符號進(jìn)行F值的遞推和下一個點(diǎn)的獲取，直到x>y為止。同前面介紹的一樣，利用圓的八分對稱性，循環(huán)一次，畫八個點(diǎn)。三、正負(fù)畫圓算法實現(xiàn)注意：初值不同、圓的生成方向不同時，當(dāng)前點(diǎn)和下一個點(diǎn)的獲取原則是不同的，見下圖。例如，初始點(diǎn)(R，0)，逆時針生成圓，從

27、圖（b）可知：若當(dāng)前點(diǎn)Pi在圓內(nèi)，則下一點(diǎn)Pi+1(xi，yi+1)，即向上走一步；若當(dāng)前點(diǎn)Pi在圓外，則下一點(diǎn)Pi+1(xi-1，yi)，即向左走一步；(a) 順時針生成圓 (b) 逆時針生成圓五、正負(fù)畫圓算法特點(diǎn)物理意義清楚，程序中只含整數(shù)運(yùn)算，因此算法速度快。六、正負(fù)畫圓算法程序/ 順時針生成圓void PNARC(int x0,int y0,int r,int color)int x=0,y=r,f=0;while(x<=y)putdot(x0,y0,x,y,color);if(f<=0)f=f+2*x+1;x+;elsef=f-2*y+1;y-;2.3 區(qū)域填充前面介紹的

28、直線和圓都屬于線劃圖，然而，光柵顯示的一個重要特點(diǎn)是能進(jìn)行面著色，區(qū)域填充就是在一個閉合區(qū)域內(nèi)填充某種顏色或圖案。區(qū)域填充一般分兩類：多邊形填充和種子填充。一、多邊形填充1、填充條件多邊形的頂點(diǎn)序列(Pi，i=0，1，n)、填充色。2、多邊形內(nèi)點(diǎn)的判別準(zhǔn)則對多邊形進(jìn)行填充，關(guān)鍵是找出多邊形內(nèi)的象素。在順序給定多邊形頂點(diǎn)坐標(biāo)的情況下，如何判明一個象素點(diǎn)是處于多邊形的內(nèi)部還是外部呢？從測試點(diǎn)引出一條伸向無窮遠(yuǎn)處的射線(假設(shè)是水平向右的射線)，因為多邊形是閉合的，那么：若射線與多邊形邊界的交點(diǎn)個數(shù)為奇數(shù)時，則該點(diǎn)為內(nèi)點(diǎn)(例：圖中測試點(diǎn)4引出的射線)；反之，交點(diǎn)個數(shù)為偶數(shù)時，則該點(diǎn)為外點(diǎn)。(例：測試點(diǎn)

29、2引出的射線)。多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn)3、奇異點(diǎn)的處理：上述的判別準(zhǔn)則，在大多數(shù)情況下是正確的，但當(dāng)水平掃描線正好通過多邊形頂點(diǎn)時，要特別注意。例如，圖中過頂點(diǎn)的射線1、射線6，它們與多邊形的交點(diǎn)個數(shù)為奇數(shù)，按照判別準(zhǔn)則它們應(yīng)該是內(nèi)點(diǎn)，但實際上卻是外點(diǎn)。 而圖中過頂點(diǎn)的射線3、射線5，對于判別準(zhǔn)則的使用又是正確的。 多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn)綜合以上情況，我們將多邊形的頂點(diǎn)分為兩大類： (1) 局部極值點(diǎn)：如圖中的點(diǎn)P1、P2、P4和P6。對于這些點(diǎn)來說，進(jìn)入該點(diǎn)的邊線和離開該點(diǎn)的邊線位于過該點(diǎn)掃描線的同一側(cè)。(2)非極值點(diǎn)：如圖中的點(diǎn)P3、P5。對于這些點(diǎn)來說，進(jìn)入該點(diǎn)的邊線和離開該

30、點(diǎn)的邊線位于過該點(diǎn)掃描線的兩側(cè)。處理奇異點(diǎn)規(guī)則：（1）對于局部極值點(diǎn)，應(yīng)看成兩個點(diǎn)；（2）對于非極值點(diǎn)，應(yīng)看成一個點(diǎn)。4、逐點(diǎn)判別算法步驟：(1)求出多邊形的最小包圍盒：從Pi(xi，yi)中求極值，xmin、ymin、xmax、ymax。 (2)對包圍盒中的每個象素引水平射線進(jìn)行測試。 (3)求出該射線與多邊形每條邊的有效交點(diǎn)個數(shù)。 (4)如果個數(shù)為奇數(shù)：該點(diǎn)置為填充色。 (5)否則：該點(diǎn)置為背景色。 逐點(diǎn)判別算法雖然簡單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問題，由于要對每個象素進(jìn)行多次求交運(yùn)算，求交時要做大量的乘除運(yùn)算，從而影響了填充速度。 二、種子填充種子填充是

31、將區(qū)域內(nèi)的一點(diǎn)(種子)賦予給定的顏色，然后將這種顏色擴(kuò)展到整個區(qū)域內(nèi)的過程。1、填充條件區(qū)域內(nèi)一點(diǎn)的坐標(biāo)即種子坐標(biāo)、邊界色、填充色。2、連通方式區(qū)域是互相連通著的象素的集合，連通方式可分為四連通和八連通。四連通：從區(qū)域內(nèi)一點(diǎn)出發(fā)，可通過四個方向：上、下、左、右到達(dá)該區(qū)域內(nèi)部的任意象素。八連通：區(qū)域內(nèi)部從一個象素到達(dá)另一個象素的移動路徑，除了上、下、左、右四個方向外，還允許沿著對角線方向。注意：（1） 八連通區(qū)域中，既然區(qū)域內(nèi)的兩個象素可以通過對角線相通，那么，區(qū)域邊界上的象素則不能通過對角線相連，否則填充就會溢出到區(qū)域外，因此，八連通區(qū)域的邊界線必須是四連通的，見下圖(a)；（2）而四連通區(qū)域

32、，其邊界象素是四連通和八連通的都可以，見下圖(b)。(a) 八連通區(qū)域四連通邊界(b) 四連通區(qū)域八連通(或四連通)邊界3、內(nèi)點(diǎn)(x,y)的檢測條件(1) if(getpixel(x,y)!=邊界色 && getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色)這兩個條件任何一個都可以用來檢測象素點(diǎn)(x,y)是不是尚未填充。推薦使用條件(1)進(jìn)行象素點(diǎn)檢測。2.3.1 邊相關(guān)掃描線多邊形填充算法2.3.2 掃描線種子填充算法2.3.3 邊標(biāo)志填充算法2.3.4 圖案填充2.3.1 邊相關(guān)掃描線多邊形填充算法邊相關(guān)掃描線填充算法屬于多邊形填充類

33、。它比逐點(diǎn)判別算法速度提高很多，是一種較經(jīng)典的多邊形填充算法。該算法利用了掃描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點(diǎn)進(jìn)行處理。一、邊相關(guān)掃描線填充算法描述掃描線的相關(guān)性：某條掃描線上相鄰的象素，幾乎都具有同樣的內(nèi)外性質(zhì)，這種性質(zhì)只有遇到多邊形邊線與該掃描線的交點(diǎn)時才會發(fā)生改變。見下圖(a)。邊的相關(guān)性：由于相鄰掃描線上的交點(diǎn)是與多邊形的邊線相關(guān)的。對同一條邊，前一條掃描線yi與該邊的交點(diǎn)為xi，而后一條掃描線yi+1=yi+1與該邊的交點(diǎn)則為xi+1=xi+1/m，利用這種相關(guān)性可以省去大量的求交運(yùn)算。見下圖(b)所示。(a) 掃描線的相關(guān)性(b) 邊的相關(guān)性邊相關(guān)掃描線填充算法的實現(xiàn)需要建

34、立兩個表：邊表（ET）和活動邊表（AET）。1、邊表（ET：Edge Table）用來對除水平邊外的所有邊進(jìn)行登記，來建立邊的記錄。邊的記錄定義為：掃描線 y 對應(yīng)的ET表第一項：某邊的最大y值（ymax）。注意要進(jìn)行奇異點(diǎn)處理：對于非極值點(diǎn)應(yīng)該ymax=ymax-1。第二項：某邊的最小的y對應(yīng)的x值。第三項：某邊斜率的倒數(shù):1/m。第四項：指針。用來指向同一條掃描線相交的其它邊，如果其它邊不存在，則該項置空。2、活動邊表（AET：Active Edge Table）ET表建立以后，就可以開始掃描轉(zhuǎn)換了。對不同的掃描線，與之相交的邊線也是不同的，當(dāng)對某一條掃描線進(jìn)行掃描轉(zhuǎn)換時，我們只需要考慮與

35、它相交的那些邊線，為此需要建立一個只與當(dāng)前掃描線相交的邊記錄鏈表，稱之為活動邊表。二、邊相關(guān)掃描線填充算法思想1、根據(jù)給出的多邊形頂點(diǎn)坐標(biāo)，建立ET表； 求出頂點(diǎn)坐標(biāo)中最大y值ymax和最小y值ymin。2、初始化AET表指針，使它為空。3、使用掃描線的yj值作為循環(huán)變量，使其初值為ymin。 對于循環(huán)變量yj的每一整數(shù)值，重復(fù)作以下事情，直到y(tǒng)j大于ymax，或ET表與AET表都為空為止：(1) 如果ET表中yj桶非空，則將yj桶中的全部記錄合并到AET表中。(2) 對AET表鏈中的記錄按x的大小從小到大排序。(3) 依次取出AET表各記錄中的xi坐標(biāo)值，兩兩配對填充，即將每對xi之間的象素

36、填上所要求的顏色。(4) 如果AET表中某記錄的ymax=yj，則刪除該記錄。(5) 對于仍留在AET表中的每個記錄，用xi+1/m代替xi進(jìn)行修改，這就是該記錄的邊線與下一條掃描線yj+1的交點(diǎn)。(6) 使yj加1，以便進(jìn)入下一輪循環(huán)。三、邊相關(guān)掃描線填充算法舉例對下圖(a)的多邊形利用邊相關(guān)掃描線填充算法進(jìn)行處理：1、首先建立ET表。注意：在做奇異點(diǎn)處理時，當(dāng)該邊最大y值對應(yīng)的頂點(diǎn)為非極值點(diǎn)時，邊記錄的第一項：ymax=ymax-1。例如：P3P4邊、P3P2邊、P4P5邊，見下圖(b)。2、接著建立AET表。AET表的建立過程就是有效地進(jìn)行填充的操作，在這個期間不斷地做以下工作：（1）合

37、并ET表；（2）x遞增排序；（3）實施填充；（4）刪除ymaxyj的邊；（5）修改邊記錄xi=xi+1/m；（6）yj+1進(jìn)入下一輪循環(huán)。結(jié)果見下圖(c)。(a) 多邊形 (b) ET表 (c) AET表四、邊相關(guān)掃描線填充算法實現(xiàn)1、根據(jù)給定的多邊形頂點(diǎn)坐標(biāo)，建立ET 表。2、AET表初始化，每個桶置空。3、for(y=ymin;y<= ymax;y+) 合并當(dāng)前掃描線y的ET表； 將y桶中每個記錄按x項升序排列； 在當(dāng)前y值下，將兩兩記錄的x值之間的象素進(jìn)行填充； 刪除y=ymax的邊記錄； 修改邊記錄x=x+1/m； 六、邊相關(guān)掃描線填充算法特點(diǎn)該算法充分利用多邊形的邊相關(guān)性和掃描

38、線的相關(guān)性，使用ET表對多邊形的非水平邊進(jìn)行登記；用AET表的建立和更新來支持填充，大大地減少了求交點(diǎn)的計算量，有效地提高了填充速度。2.3.2 掃描線種子填充算法該算法屬于種子填充算法，它是以掃描線上的區(qū)段為單位進(jìn)行操作。所謂區(qū)段，就是一條掃描線上相連著的若干內(nèi)部象素的集合。一、掃描線種子填充算法思想掃描線種子填充算法的基本思想是：首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于該區(qū)段內(nèi)是否存在需要填充的新區(qū)段，如果存在，則依次把它們保存起來。反復(fù)這個過程，直到所保存的各區(qū)段都填充完畢。二、掃描線種子填充算法實現(xiàn)借助于堆棧，上述算法實現(xiàn)步驟如下：1、

39、初始化堆棧。2、種子壓入堆棧。3、while（堆棧非空） (1)從堆棧彈出種子象素。(2)如果種子象素尚未填充，則：a.求出種子區(qū)段：xleft、xright;b.填充整個區(qū)段。c.檢查相鄰的上掃描線的xleftxxright區(qū)間內(nèi),是否存在需要填充的新區(qū)段，如果存在的話，則把每個新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。d.檢查相鄰的下掃描線的xleftxxright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話，則把每個新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。四、掃描線種子填充算法特點(diǎn)1、該算法考慮了掃描

40、線上象素的相關(guān)性，種子象素不再代表一個孤立的象素，而是代表一個尚未填充的區(qū)段。2、進(jìn)棧時，只將每個區(qū)段選一個象素進(jìn)棧（每個區(qū)段最右邊或最左邊的象素），這樣解決了堆棧溢出的問題。3、種子出棧時，則填充整個區(qū)段。4、這樣有機(jī)的結(jié)合：一邊對尚未填充象素的登記（素進(jìn)棧），一邊進(jìn)行填充（象素出棧），既可以節(jié)省堆棧空間，又可以實施快速填充。2.3.3 邊標(biāo)志填充算法在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個閉合區(qū)域，填充是逐行進(jìn)行的，即用掃描線逐行對多邊形求交，在交點(diǎn)對之間填充。邊標(biāo)志填充算法就是在逐行處理時，利用邊界色作為標(biāo)志來進(jìn)行填充的。例如某掃描線從左到右掃描時碰到邊界色，立刻改變

41、標(biāo)志的狀態(tài)，接下來再根據(jù)標(biāo)志的狀態(tài)決定某象素點(diǎn)是否填充。一、邊標(biāo)志填充算法思想掃描線具有連貫性，這種連貫性只有在掃描線與多邊形相交處才會發(fā)生變化，而每次的變化結(jié)果：無非是在前景色和背景色之間相互“切換”。邊標(biāo)志填充算法正是基于這一發(fā)現(xiàn)，先在屏幕上生成多邊形輪廓線，然后逐條掃描處理。處理中：逐點(diǎn)讀取象素值，若為邊界色，則對該象素值進(jìn)行顏色切換。二、邊標(biāo)志填充算法實現(xiàn) 1、用邊界色畫出多邊形輪廓線，也就是將多邊形邊界所經(jīng)過的象素打上邊標(biāo)志。 2、為了縮小范圍，加快填充速度，須找出多邊形的最小包圍盒：xmin、ymin、xmax、ymax。如下圖所示。邊標(biāo)志填充算法3、逐條掃描線進(jìn)行處理，對每條掃描

42、線依從左往右的順序，逐個訪問該掃描線上的象素。每遇到邊界象素，標(biāo)志取反。然后，按照標(biāo)志是否為真，決定象素是否為填充色。四、邊標(biāo)志填充算法特點(diǎn)該算法思想簡單，實現(xiàn)容易。既不需要求交點(diǎn)、交點(diǎn)排序、邊的登記，也不需要使用鏈表、堆棧等數(shù)據(jù)結(jié)構(gòu)。五、邊標(biāo)志填充算法程序EdgeMarkFill(int p2,int n,int boundarycolor,int newcolor)int i,x,y,flag,xmin,xmax,ymin,ymax;setcolor(boundarycolor); /*設(shè)置畫筆色*/ for(i=0 ;i<n;i+)line(pi0,pi1,p(i+1)%n0,p(

43、i+1)%n)1); /*畫出多邊形的n條邊*/用求極值的算法，從多邊形頂點(diǎn)數(shù)組p中，求出xmin,xmax,ymin,ymax;for(y=ymin;y<=ymax;y+) flag=-1;for(x=xmin;x<=xmax;x+) if(getpixel(x,y)=boundarycolor)flag=-flag;if(flag=1)putpixel(x,y, newcolor);六、邊標(biāo)志填充算法錯誤處理1、該算法雖然簡單，但程序運(yùn)行后會出現(xiàn)局部錯誤。從下圖可以發(fā)現(xiàn)，對于多邊形頂點(diǎn)為局部極值點(diǎn)時，掃描線與多邊形的相交次數(shù)不再是偶數(shù)，而是奇數(shù)，填充時會出現(xiàn)“抽絲”現(xiàn)象。即某掃

44、描線上不該填充的區(qū)段填上色，而應(yīng)該填充的區(qū)段卻沒有填上色。解決的辦法：判斷多邊形頂點(diǎn)的性質(zhì)，如果是局部極值點(diǎn)，那么掃描線碰上它則不改變標(biāo)志。2、特別當(dāng)心多邊形邊界的掃描轉(zhuǎn)換。在這里就不能考慮：不同的斜率產(chǎn)生的直線要亮度均勻，如下圖(a)所示。否則當(dāng)掃描線y遇到斜率小于1的邊界線時，碰到幾個邊界點(diǎn)，會引起標(biāo)志的無序改變，將導(dǎo)致填充的錯誤。解決的辦法：對于不同斜率的邊界，都要使用斜率大于1的直線掃描轉(zhuǎn)換方法：每次y方向增長一步，x方向增長1/m步距，以保證掃描線y遇到斜率小于1的邊界時，只能遇到一個點(diǎn)。請看下圖(b)。在邊標(biāo)志填充算法中要注意多邊形邊界的掃描轉(zhuǎn)換3.2 線段的裁剪直線段的裁剪比點(diǎn)復(fù)

45、雜，其裁剪方法又是多邊形裁剪和三維圖形裁剪的基礎(chǔ)。一、直線裁剪的基本思想判斷直線與窗口的位置關(guān)系：1確定直線是完全可見；2部分可見；3還是完全不可見。對部分可見線段，求出它與窗口邊界的交點(diǎn)，并將窗口內(nèi)的線段輸出。二、裁剪線段和窗口的關(guān)系假定窗口左下角坐標(biāo)為(xmin，ymin)，右上角坐標(biāo)為(xmax，ymax)，待裁剪線段和窗口的關(guān)系如圖所示，這五種位置關(guān)系存在下面三種情況：1、直線的兩個端點(diǎn)均在窗口內(nèi)，如圖中AB線。這時直線完全可見，可被簡單接受。2、直線的兩個端點(diǎn)都在窗口外，并且位于窗口某一邊界的同一外側(cè)，如圖中EF線。則直線完全不可見，可被簡單舍棄。3、除此之外需要求交點(diǎn)，以確定直線在

46、窗口某一邊界內(nèi)是否有可見部分,并裁掉外部線段，顯示內(nèi)部線段。如CD、GH、IJ線。為了提高裁剪效率，算法設(shè)計一般可從下面兩方面作出考慮：(1) 快速判斷情況1和情況2。(2)在情況3中，設(shè)法減少求交的次數(shù)和每次求交時所需的計算量。三、直線求交計算當(dāng)線段P1P2穿過某邊界L時，交點(diǎn)P的計算如圖中所示。根據(jù)直線兩點(diǎn)式方程：(32)整理后得通用交點(diǎn)公式：(33)1、與上邊界的求交公式：(34)2、與下邊界的求交公式：(35)3、與右邊界的求交公式：(36)4、與左邊界的求交公式：(37)四、直線裁剪的常用算法 1CohenSutherland算法2中點(diǎn)分割算法3梁友棟-Barsky裁剪算法3.2.1

47、 CohenSutherland算法一、CohenSutherland算法思想：該算法也稱為編碼算法，首先對線段的兩個端點(diǎn)按所在的區(qū)域進(jìn)行分區(qū)編碼，根據(jù)編碼可以迅速地判明全部在窗口內(nèi)的線段和全部在某邊界外側(cè)的線段。只有不屬于這兩種情況的線段，才需要求出線段與窗口邊界的交點(diǎn)，求出交點(diǎn)后，舍去窗外部分。對剩余部分，把它作為新的線段看待，又從頭開始考慮。兩遍循環(huán)之后，就能確定該線段是部分截留下來，還是全部舍棄。二、CohenSutherland算法步驟：1、分區(qū)編碼延長裁剪邊框?qū)⒍S平面分成九個區(qū)域，每個區(qū)域各用一個四位二進(jìn)制代碼標(biāo)識。各區(qū)代碼值如圖中所示。四位二進(jìn)制代碼的編碼規(guī)則是：(1)第一位置

48、1：區(qū)域在左邊界外側(cè)(2)第二位置1：區(qū)域在右邊界外側(cè)(3)第三位置1：區(qū)域在下邊界外側(cè)(4)第四位置1：區(qū)域在上邊界外側(cè)裁剪窗口內(nèi)（包括邊界上）的區(qū)域，四位二進(jìn)制代碼均為0。設(shè)線段的兩個端點(diǎn)為P1（x1，y1）和P2（x2，y2），根據(jù)上述規(guī)則，可以求出P1和P2所在區(qū)域的分區(qū)代碼C1和C2。2、判別根據(jù)C1和C2的具體值，可以有三種情況：（1）C1=C20，表明兩端點(diǎn)全在窗口內(nèi)，因而整個線段也在窗內(nèi)，應(yīng)予保留。（2）C1&C20（兩端點(diǎn)代碼按位作邏輯乘不為0），即C1和C2至少有某一位同時為1，表明兩端點(diǎn)必定處于某一邊界的同一外側(cè)，因而整個線段全在窗外，應(yīng)予舍棄。（3）不屬于上面兩

49、種情況，均需要求交點(diǎn)。3、求交點(diǎn)假設(shè)算法按照：左、右、下、上邊界的順序進(jìn)行求交處理，對每一個邊界求完交點(diǎn)，并相關(guān)處理后，算法轉(zhuǎn)向第2步，重新判斷，如果需要接著進(jìn)入下一邊界的處理。為了規(guī)范算法，令線段的端點(diǎn)P1為外端點(diǎn)，如果不是這樣，就需要P1和P2交換端點(diǎn)。當(dāng)條件(C1&00010)成立時，表示端點(diǎn)P1位于窗口左邊界外側(cè)，按照前面介紹的求交公式，進(jìn)行對左邊界的求交運(yùn)算。依次類推，對位于右、下、上邊界外側(cè)的判別，應(yīng)將條件式中的0001分別改為0010、0100、1000即可。求出交點(diǎn)P后，用P1=P來舍去線段的窗外部分，并對P1重新編碼得到C1，接下來算法轉(zhuǎn)回第2步繼續(xù)對其它邊界進(jìn)行判別

50、。三、CohenSutherland算法分區(qū)編碼程序：Code(int x,int y,int *c)*c=0;if(y>ymax) /*（xmin，ymin）和（xmax，ymax）為窗口左下角、右上角坐標(biāo)。*/*c=*c|0x08; else if(y<ymin)*c=*c|0x04;if(x>xmax)*c=*c|0x02;else if(x<xmin)*c=*c|0x01;四、CohenSutherland算法的流程圖：3.2.2 中點(diǎn)分割算法CohenSutherland直線裁剪算法，充分利用了直線段與裁剪邊框的相關(guān)性，使裁剪速度大大提高，但在求交過程中仍采用

51、了乘除運(yùn)算，裁剪速度受到影響。而中點(diǎn)分割法的特點(diǎn)，就在于它是用連續(xù)平分線段最終求得交點(diǎn)的方法代替用乘除法實現(xiàn)求交運(yùn)算。這樣只需進(jìn)行整數(shù)的加法和用運(yùn)算器右移一位來實現(xiàn)除法運(yùn)算，從而避免去做大量的乘除法。一、中點(diǎn)分割算法思想：1、中點(diǎn)公式（38）2、中點(diǎn)分割法求交點(diǎn)的規(guī)則如圖中所示，當(dāng)線段P1P2求出中點(diǎn)P后，舍棄線段的哪部分，由下面兩條規(guī)則決定：中點(diǎn)分割法求交點(diǎn)規(guī)則（1）如果P1與P同側(cè)，移動P1點(diǎn)；（即可能的交點(diǎn)只能出現(xiàn)在PP2段）if(C1&C)!=0) P1=P;（2）如果P1與P不同側(cè)，移動P2點(diǎn)。（即可能的交點(diǎn)只能出現(xiàn)在P1P段）if(C1&C)= =0) P2=P;二

52、、中點(diǎn)分割算法實現(xiàn)：1、將直線的兩端點(diǎn)P1、P2編碼得：C1、C2；2、判別根據(jù)C1和C2的具體值，可以有三種情況：（1）C1C20，表明兩端點(diǎn)全在窗口內(nèi)，因而整個線段也在窗內(nèi)，應(yīng)予保留。（2）C1&C20（兩端點(diǎn)代碼按位作邏輯乘不為0），即C1和C2至少有某一位同時為1，表明兩端點(diǎn)必定處于某一邊界的同一外側(cè)，因而整個線段全在窗外，應(yīng)予舍棄。（3）不屬于上面兩種情況，均需要求交點(diǎn)。3、求交點(diǎn)（1）令窗外端點(diǎn)為P1，如果窗外點(diǎn)不是P1，則P1和P2交換端點(diǎn)；（2）保留窗內(nèi)端點(diǎn)P2到暫存器里；（3）對P1編碼為C1；（4）用中點(diǎn)公式求出中點(diǎn)，并編碼得C；（5）按照中點(diǎn)算法的求交規(guī)則：若P1和P同側(cè)，移動P1點(diǎn)；if