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

2.1.1 生成直線的DDA算法數(shù)值微分法即DDA法(Digital Differential Analyzer)，是一種基于直線的微分方程來(lái)生成直線的方法。一、直線DDA算法描述：設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點(diǎn)和終點(diǎn)坐標(biāo)，由直線的微分方程得= m =直線的斜率(21)可通過計(jì)算由x方向的增量x引起y的改變來(lái)生成直線：xi+1=xi+x(22)yi+1=yi+y=yi+xm(23)也可通過計(jì)算由y方向的增量y引起x的改變來(lái)生成直線：yi+1=yi+y(24)xi+1=xi+x=xi+y/m(25)式(22)至(25)是遞推的。二、直線DDA算法思想：選定x2x1和y2y1中較大者作為步進(jìn)方向(假設(shè)x2x1較大)，取該方向上的增量為一個(gè)象素單位(x=1)，然后利用式(21)計(jì)算另一個(gè)方向的增量(y=xm=m)。通過遞推公式(22)至(25)，把每次計(jì)算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。之所以取x2x1和y2y1中較大者作為步進(jìn)方向，是考慮沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。另外，算法實(shí)現(xiàn)中還應(yīng)注意直線的生成方向，以決定x及y是取正值還是負(fù)值。三、直線DDA算法實(shí)現(xiàn)：1、已知直線的兩端點(diǎn)坐標(biāo)：(x1，y1)，(x2，y2)2、已知畫線的顏色：color3、計(jì)算兩個(gè)方向的變化量：dx=x2x1 dy=y2y14、求出兩個(gè)方向最大變化量的絕對(duì)值： steps=max(|dx|，|dy|)5、計(jì)算兩個(gè)方向的增量(考慮了生成方向)： xin=dx/steps yin=dy/steps6、設(shè)置初始象素坐標(biāo)：x=x1,y=y17、用循環(huán)實(shí)現(xiàn)直線的繪制：for(i=1；i0)?static_cast(fNum+0.5):static_cast(fNum-0.5)/*!* brief DDA畫線函數(shù)* param pDC in窗口DC* param BeginPt in直線起點(diǎn)* param EndPt in直線終點(diǎn)* param LineCor in直線顏色* return 無(wú)*/void CDrawMsg:DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREF LineCor)long YDis = (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(YDis)/static_cast(MaxStep);fXUnitLen = static_cast(XDis)/static_cast(MaxStep);/ 設(shè)置起點(diǎn)像素顏色pDC-SetPixel(BeginPt.x,BeginPt.y,LineCor); float x = static_cast(BeginPt.x);float y = static_cast(BeginPt.y);/ 循環(huán)步進(jìn)for (long i = 1;iSetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);2.1.2 生成直線的Bresenham算法從上面介紹的DDA算法可以看到，由于在循環(huán)中涉及實(shí)型數(shù)據(jù)的加減運(yùn)算，因此直線的生成速度較慢。在生成直線的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來(lái)生成直線的方法。一、直線Bresenham算法描述：它也是采用遞推步進(jìn)的辦法，令每次最大變化方向的坐標(biāo)步進(jìn)一個(gè)象素，同時(shí)另一個(gè)方向的坐標(biāo)依據(jù)誤差判別式的符號(hào)來(lái)決定是否也要步進(jìn)一個(gè)象素。我們首先討論m=y/x，當(dāng)0m1且x1x2時(shí)的Bresenham算法。從DDA直線算法可知這些條件成立時(shí)，公式(2-2)、(2-3)可寫成：xi+1=xi+1(26)yi+1=yi+m(27)有兩種Bresenham算法思想，它們各自從不同角度介紹了Bresenham算法思想，得出的誤差判別式都是一樣的。二、直線Bresenham算法思想之一：由于顯示直線的象素點(diǎn)只能取整數(shù)值坐標(biāo)，可以假設(shè)直線上第i個(gè)象素點(diǎn)坐標(biāo)為(xi，yi)，它是直線上點(diǎn)(xi，yi)的最佳近似，并且xi=xi(假設(shè)md2，說(shuō)明直線上理論點(diǎn)離(xi+1，yi+1)象素較近，下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi+1)。(2)當(dāng)此值為負(fù)時(shí)，d10，因此pi與(d1-d2)有相同的符號(hào)；這里y=y2-y1，m=y/x；c=2y+x(2b-1)。下面對(duì)式(2-11)作進(jìn)一步處理，以便得出誤差判別遞推公式并消除常數(shù)c。將式(2-11)中的下標(biāo)i改寫成i+1，得到：pi+1=2yxi+1-2xyi+1+c(212)將式(2-12)減去(2-11)，并利用xi+1=xi+1，可得：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時(shí)： 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、直線的兩個(gè)端點(diǎn)坐標(biāo)分量差x和y有關(guān)，運(yùn)算中只含有整數(shù)相加和乘2運(yùn)算，而乘2可利用算術(shù)左移一位來(lái)完成，因此這個(gè)算法速度快并易于硬件實(shí)現(xiàn)。三、直線Bresenham算法思想之二：由于象素坐標(biāo)的整數(shù)性，數(shù)學(xué)點(diǎn)(xi，yi)與所取象素點(diǎn)(xi，yir)間會(huì)引起誤差(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 = yi+1+m-y(i+1)r-0.5(29)當(dāng)(xi+1)0時(shí)，選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時(shí)，選C點(diǎn)，y(i+1)r = yir(xi+2)= yi+1+myir-0.5=(xi+1)+m(211)初始時(shí)：(xs+1)=BC-AC=m-0.5(212)為了運(yùn)算中不含實(shí)型數(shù)，同時(shí)不影響不等式的判斷，將方程兩邊同乘一正整數(shù)。令方程兩邊同乘2x，即d=2x，則：初始時(shí)：d = 2y-x(213)遞推式：當(dāng)d0時(shí)： d=d+2(yx)；y+；x+；否則： d=d+2y；x+； (214)實(shí)現(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=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=0) y+, e=e-2dx;四、直線Bresenham算法實(shí)現(xiàn)：條件：0m1且x1x21、輸入線段的兩個(gè)端點(diǎn)坐標(biāo)和畫線顏色：x1，y1，x2，y2，color；2、設(shè)置象素坐標(biāo)初值：x=x1，y=y1；3、設(shè)置初始誤差判別值：p=2y-x；4、分別計(jì)算：x=x2-x1、y=y2-y1；5、循環(huán)實(shí)現(xiàn)直線的生成：for(x=x1；x=0) y=y+1；p=p+2(y-x)；else p=p+2y；五、直線Bresenham算法完善：現(xiàn)在我們修正(2-16)公式，以適應(yīng)對(duì)任何方向及任何斜率線段的繪制。如下圖所示，線段的方向可分為八種，從原點(diǎn)出發(fā)射向八個(gè)區(qū)。由線段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。容易證明：當(dāng)線段處于、區(qū)時(shí)，以|x|和|y|代替前面公式中的x和y，當(dāng)線段處于、區(qū)時(shí)，將公式中的|x|和|y|對(duì)換，則上述兩公式仍有效。在線段起點(diǎn)區(qū)分線段方向七、直線Bresenham算法特點(diǎn)：由于程序中不含實(shí)型數(shù)運(yùn)算，因此速度快、效率高，是一種有效的畫線算法。2.2.2 中點(diǎn)算法生成圓中點(diǎn)畫圓算法在一個(gè)方向上取單位間隔，在另一個(gè)方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實(shí)際處理中，用決策變量的符號(hào)來(lái)確定象素點(diǎn)的選擇，因此算法效率較高。一、中點(diǎn)畫圓算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0，R)處，終點(diǎn)在(，)處，順時(shí)針生成八分之一圓，利用對(duì)稱性掃描轉(zhuǎn)換全部圓。為了應(yīng)用中點(diǎn)畫圓法，我們定義一個(gè)圓函數(shù)F(x，y)=x2+y2-R2(219)任何點(diǎn)(x，y)的相對(duì)位置可由圓函數(shù)的符號(hào)來(lái)檢測(cè)：F(x，y)0點(diǎn)(x，y)位于數(shù)學(xué)圓外(220)如下圖所示，圖中有兩條圓弧A和B，假定當(dāng)前取點(diǎn)為Pi(xi，yi)，如果順時(shí)針生成圓，那么下一點(diǎn)只能取正右方的點(diǎn)E(xi+1，yi)或右下方的點(diǎn)SE(xi+1，yi-1)兩者之一。中點(diǎn)畫線算法假設(shè)M是E和SE的中點(diǎn)，即 ，則：1、當(dāng)F(M)0時(shí)，M在圓外(圓弧B)，表明SE點(diǎn)離圓更近，應(yīng)取SE點(diǎn)；3、當(dāng)F(M)=0時(shí)，在E點(diǎn)與SE點(diǎn)之中隨便取一個(gè)即可，我們約定取SE點(diǎn)。 二、中點(diǎn)畫圓算法思想因此，我們用中點(diǎn)M的圓函數(shù)作為決策變量di，同時(shí)用增量法來(lái)迭代計(jì)算下一個(gè)中點(diǎn)M的決策變量di+1。(221)下面分兩種情況來(lái)討論在迭代計(jì)算中決策變量di+1的推導(dǎo)。1、見圖（a），若di0，則選擇E點(diǎn)，接著下一個(gè)中點(diǎn)就是，這時(shí)新的決策變量為：(222)（a）(di0) 中點(diǎn)畫線算法式(222)減去(221)得：di+1=di+2xi+3(223)2、見圖（b），若di0，則選擇SE點(diǎn)，接著下一個(gè)中點(diǎn)就是 ，這時(shí)新的決策變量為：(224)（b）(di0) 中點(diǎn)畫線算法式(224)減去(221)得：di+1=di+2(xi-yi)+5(225)我們利用遞推迭代計(jì)算這八分之一圓弧上的每個(gè)點(diǎn)，每次迭代需要兩步處理：（1）用前一次迭代算出的決策變量的符號(hào)來(lái)決定本次選擇的點(diǎn)。（2）對(duì)本次選擇的點(diǎn)，重新遞推計(jì)算得出新的決策變量的值。剩下的問題是計(jì)算初始決策變量d0，如下圖所示。對(duì)于初始點(diǎn)(0，R)，順時(shí)針生成八分之一圓，下一個(gè)中點(diǎn)M的坐標(biāo)是 ，所以：(226生成圓的初始條件和圓的生成方向三、中點(diǎn)畫圓算法實(shí)現(xiàn)1、輸入：圓半徑r、圓心(x0，y0)；2、確定初值：x=0，y=r、d=5/4-r；3、While(x=y)利用八分對(duì)稱性，用規(guī)定的顏色color畫八個(gè)象素點(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ù)來(lái)表示決策變量d。為了簡(jiǎn)化算法，擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d=5/4-r對(duì)應(yīng)于e=1-r。決策變量d0對(duì)應(yīng)于e-1/4。算法中其它與d有關(guān)的式子可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算過程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e-1/4等價(jià)于e0。因此，可以寫出完全用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法。要求：寫出用整數(shù)實(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(d0)d+=x*2.0+3;elsed+=2.0*(x-y)+5;y-; x+;putdot(x0,y0,x,y,color)putpixel(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ū)域，對(duì)當(dāng)前點(diǎn)產(chǎn)生的圓函數(shù)進(jìn)行符號(hào)判別，利用負(fù)反饋調(diào)整以決定下一個(gè)點(diǎn)的產(chǎn)生來(lái)直接生成圓弧。一、正負(fù)畫圓算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，初始點(diǎn)的坐標(biāo)為(0，R)，順時(shí)針生成八分之一圓，令：F(x，y)=x2+y2-R2則圓的方程為：F(x，y)=0 (2-27)當(dāng)點(diǎn)(x，y)在圓內(nèi)時(shí)，則F(x，y)0；當(dāng)點(diǎn)(x，y)在圓上時(shí)，則F(x，y)=0；二、正負(fù)畫圓算法思想現(xiàn)以下圖的AB弧為例，來(lái)說(shuō)明正負(fù)畫圓法(順時(shí)針生成圓)。假設(shè)當(dāng)前點(diǎn)為Pi(xi，yi)，取下一個(gè)點(diǎn)Pi+1(xi+1，yi+1)的原則是： 1、當(dāng)F(xi，yi)0時(shí)：取xi+1= xi+1，yi+1= yi。即向右走一步，從圓內(nèi)走向圓外。對(duì)應(yīng)圖(a)中的從Pi到Pi+1。2、當(dāng)F(xi，yi)0時(shí)：取xi+1= xi，yi+1= yi-1。即向下走一步，從圓外走向圓內(nèi)。對(duì)應(yīng)圖(b)中的從Pi到Pi+1。由于向圓內(nèi)或向圓外走取決于F(xi，yi)的正負(fù)，因此稱為正負(fù)法。下面分兩種情況求出F(xi，yi)的遞推公式：(1) 當(dāng)F(xi，yi)0時(shí)，向右走，取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時(shí)，向下走，取xi+1=xi，yi+1=yi-1，則F(xi+1，yi+1)=F(xi，yi-1)=xi2+(yi-1)2-R2=(xi2+yi2-R2)-2yi+1= F(xi，yi)-2yi+1(2-9)初始時(shí)，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的符號(hào)進(jìn)行F值的遞推和下一個(gè)點(diǎn)的獲取，直到xy為止。同前面介紹的一樣，利用圓的八分對(duì)稱性，循環(huán)一次，畫八個(gè)點(diǎn)。三、正負(fù)畫圓算法實(shí)現(xiàn)注意：初值不同、圓的生成方向不同時(shí)，當(dāng)前點(diǎn)和下一個(gè)點(diǎn)的獲取原則是不同的，見下圖。例如，初始點(diǎn)(R，0)，逆時(shí)針生成圓，從圖（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) 順時(shí)針生成圓 (b) 逆時(shí)針生成圓五、正負(fù)畫圓算法特點(diǎn)物理意義清楚，程序中只含整數(shù)運(yùn)算，因此算法速度快。六、正負(fù)畫圓算法程序/ 順時(shí)針生成圓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ū)域填充前面介紹的直線和圓都屬于線劃圖，然而，光柵顯示的一個(gè)重要特點(diǎn)是能進(jìn)行面著色，區(qū)域填充就是在一個(gè)閉合區(qū)域內(nèi)填充某種顏色或圖案。區(qū)域填充一般分兩類：多邊形填充和種子填充。一、多邊形填充1、填充條件多邊形的頂點(diǎn)序列(Pi，i=0，1，n)、填充色。2、多邊形內(nèi)點(diǎn)的判別準(zhǔn)則對(duì)多邊形進(jìn)行填充，關(guān)鍵是找出多邊形內(nèi)的象素。在順序給定多邊形頂點(diǎn)坐標(biāo)的情況下，如何判明一個(gè)象素點(diǎn)是處于多邊形的內(nèi)部還是外部呢？從測(cè)試點(diǎn)引出一條伸向無(wú)窮遠(yuǎn)處的射線(假設(shè)是水平向右的射線)，因?yàn)槎噙呅问情]合的，那么：若射線與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，則該點(diǎn)為內(nèi)點(diǎn)(例：圖中測(cè)試點(diǎn)4引出的射線)；反之，交點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，則該點(diǎn)為外點(diǎn)。(例：測(cè)試點(diǎn)2引出的射線)。多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn)3、奇異點(diǎn)的處理：上述的判別準(zhǔn)則，在大多數(shù)情況下是正確的，但當(dāng)水平掃描線正好通過多邊形頂點(diǎn)時(shí)，要特別注意。例如，圖中過頂點(diǎn)的射線1、射線6，它們與多邊形的交點(diǎn)個(gè)數(shù)為奇數(shù)，按照判別準(zhǔn)則它們應(yīng)該是內(nèi)點(diǎn)，但實(shí)際上卻是外點(diǎn)。 而圖中過頂點(diǎn)的射線3、射線5，對(duì)于判別準(zhǔn)則的使用又是正確的。 多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn)綜合以上情況，我們將多邊形的頂點(diǎn)分為兩大類： (1) 局部極值點(diǎn)：如圖中的點(diǎn)P1、P2、P4和P6。對(duì)于這些點(diǎn)來(lái)說(shuō)，進(jìn)入該點(diǎn)的邊線和離開該點(diǎn)的邊線位于過該點(diǎn)掃描線的同一側(cè)。(2)非極值點(diǎn)：如圖中的點(diǎn)P3、P5。對(duì)于這些點(diǎn)來(lái)說(shuō)，進(jìn)入該點(diǎn)的邊線和離開該點(diǎn)的邊線位于過該點(diǎn)掃描線的兩側(cè)。處理奇異點(diǎn)規(guī)則：（1）對(duì)于局部極值點(diǎn)，應(yīng)看成兩個(gè)點(diǎn)；（2）對(duì)于非極值點(diǎn)，應(yīng)看成一個(gè)點(diǎn)。4、逐點(diǎn)判別算法步驟：(1)求出多邊形的最小包圍盒：從Pi(xi，yi)中求極值，xmin、ymin、xmax、ymax。 (2)對(duì)包圍盒中的每個(gè)象素引水平射線進(jìn)行測(cè)試。 (3)求出該射線與多邊形每條邊的有效交點(diǎn)個(gè)數(shù)。 (4)如果個(gè)數(shù)為奇數(shù)：該點(diǎn)置為填充色。 (5)否則：該點(diǎn)置為背景色。 逐點(diǎn)判別算法雖然簡(jiǎn)單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問題，由于要對(duì)每個(gè)象素進(jìn)行多次求交運(yùn)算，求交時(shí)要做大量的乘除運(yùn)算，從而影響了填充速度。 二、種子填充種子填充是將區(qū)域內(nèi)的一點(diǎn)(種子)賦予給定的顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過程。1、填充條件區(qū)域內(nèi)一點(diǎn)的坐標(biāo)即種子坐標(biāo)、邊界色、填充色。2、連通方式區(qū)域是互相連通著的象素的集合，連通方式可分為四連通和八連通。四連通：從區(qū)域內(nèi)一點(diǎn)出發(fā)，可通過四個(gè)方向：上、下、左、右到達(dá)該區(qū)域內(nèi)部的任意象素。八連通：區(qū)域內(nèi)部從一個(gè)象素到達(dá)另一個(gè)象素的移動(dòng)路徑，除了上、下、左、右四個(gè)方向外，還允許沿著對(duì)角線方向。注意：（1） 八連通區(qū)域中，既然區(qū)域內(nèi)的兩個(gè)象素可以通過對(duì)角線相通，那么，區(qū)域邊界上的象素則不能通過對(duì)角線相連，否則填充就會(huì)溢出到區(qū)域外，因此，八連通區(qū)域的邊界線必須是四連通的，見下圖(a)；（2）而四連通區(qū)域，其邊界象素是四連通和八連通的都可以，見下圖(b)。(a) 八連通區(qū)域四連通邊界(b) 四連通區(qū)域八連通(或四連通)邊界3、內(nèi)點(diǎn)(x,y)的檢測(cè)條件(1) if(getpixel(x,y)!=邊界色 & getpixel(x,y)!=填充色) (2) if(getpixel(x,y)!=背景色)這兩個(gè)條件任何一個(gè)都可以用來(lái)檢測(cè)象素點(diǎn)(x,y)是不是尚未填充。推薦使用條件(1)進(jìn)行象素點(diǎn)檢測(cè)。2.3.1 邊相關(guān)掃描線多邊形填充算法2.3.2 掃描線種子填充算法2.3.3 邊標(biāo)志填充算法2.3.4 圖案填充2.3.1 邊相關(guān)掃描線多邊形填充算法邊相關(guān)掃描線填充算法屬于多邊形填充類。它比逐點(diǎn)判別算法速度提高很多，是一種較經(jīng)典的多邊形填充算法。該算法利用了掃描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點(diǎn)進(jìn)行處理。一、邊相關(guān)掃描線填充算法描述掃描線的相關(guān)性：某條掃描線上相鄰的象素，幾乎都具有同樣的內(nèi)外性質(zhì)，這種性質(zhì)只有遇到多邊形邊線與該掃描線的交點(diǎn)時(shí)才會(huì)發(fā)生改變。見下圖(a)。邊的相關(guān)性：由于相鄰掃描線上的交點(diǎn)是與多邊形的邊線相關(guān)的。對(duì)同一條邊，前一條掃描線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)掃描線填充算法的實(shí)現(xiàn)需要建立兩個(gè)表：邊表（ET）和活動(dòng)邊表（AET）。1、邊表（ET：Edge Table）用來(lái)對(duì)除水平邊外的所有邊進(jìn)行登記，來(lái)建立邊的記錄。邊的記錄定義為：掃描線 y 對(duì)應(yīng)的ET表第一項(xiàng)：某邊的最大y值（ymax）。注意要進(jìn)行奇異點(diǎn)處理：對(duì)于非極值點(diǎn)應(yīng)該ymax=ymax-1。第二項(xiàng)：某邊的最小的y對(duì)應(yīng)的x值。第三項(xiàng)：某邊斜率的倒數(shù):1/m。第四項(xiàng)：指針。用來(lái)指向同一條掃描線相交的其它邊，如果其它邊不存在，則該項(xiàng)置空。2、活動(dòng)邊表（AET：Active Edge Table）ET表建立以后，就可以開始掃描轉(zhuǎn)換了。對(duì)不同的掃描線，與之相交的邊線也是不同的，當(dāng)對(duì)某一條掃描線進(jìn)行掃描轉(zhuǎn)換時(shí)，我們只需要考慮與它相交的那些邊線，為此需要建立一個(gè)只與當(dāng)前掃描線相交的邊記錄鏈表，稱之為活動(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。 對(duì)于循環(huán)變量yj的每一整數(shù)值，重復(fù)作以下事情，直到y(tǒng)j大于ymax，或ET表與AET表都為空為止：(1) 如果ET表中yj桶非空，則將yj桶中的全部記錄合并到AET表中。(2) 對(duì)AET表鏈中的記錄按x的大小從小到大排序。(3) 依次取出AET表各記錄中的xi坐標(biāo)值，兩兩配對(duì)填充，即將每對(duì)xi之間的象素填上所要求的顏色。(4) 如果AET表中某記錄的ymax=yj，則刪除該記錄。(5) 對(duì)于仍留在AET表中的每個(gè)記錄，用xi+1/m代替xi進(jìn)行修改，這就是該記錄的邊線與下一條掃描線yj+1的交點(diǎn)。(6) 使yj加1，以便進(jìn)入下一輪循環(huán)。三、邊相關(guān)掃描線填充算法舉例對(duì)下圖(a)的多邊形利用邊相關(guān)掃描線填充算法進(jìn)行處理：1、首先建立ET表。注意：在做奇異點(diǎn)處理時(shí)，當(dāng)該邊最大y值對(duì)應(yīng)的頂點(diǎn)為非極值點(diǎn)時(shí)，邊記錄的第一項(xiàng)：ymax=ymax-1。例如：P3P4邊、P3P2邊、P4P5邊，見下圖(b)。2、接著建立AET表。AET表的建立過程就是有效地進(jìn)行填充的操作，在這個(gè)期間不斷地做以下工作：（1）合并ET表；（2）x遞增排序；（3）實(shí)施填充；（4）刪除ymaxyj的邊；（5）修改邊記錄xi=xi+1/m；（6）yj+1進(jìn)入下一輪循環(huán)。結(jié)果見下圖(c)。(a) 多邊形 (b) ET表 (c) AET表四、邊相關(guān)掃描線填充算法實(shí)現(xiàn)1、根據(jù)給定的多邊形頂點(diǎn)坐標(biāo)，建立ET 表。2、AET表初始化，每個(gè)桶置空。3、for(y=ymin;y= ymax;y+) 合并當(dāng)前掃描線y的ET表； 將y桶中每個(gè)記錄按x項(xiàng)升序排列； 在當(dāng)前y值下，將兩兩記錄的x值之間的象素進(jìn)行填充； 刪除y=ymax的邊記錄； 修改邊記錄x=x+1/m； 六、邊相關(guān)掃描線填充算法特點(diǎn)該算法充分利用多邊形的邊相關(guān)性和掃描線的相關(guān)性，使用ET表對(duì)多邊形的非水平邊進(jìn)行登記；用AET表的建立和更新來(lái)支持填充，大大地減少了求交點(diǎn)的計(jì)算量，有效地提高了填充速度。2.3.2 掃描線種子填充算法該算法屬于種子填充算法，它是以掃描線上的區(qū)段為單位進(jìn)行操作。所謂區(qū)段，就是一條掃描線上相連著的若干內(nèi)部象素的集合。一、掃描線種子填充算法思想掃描線種子填充算法的基本思想是：首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于該區(qū)段內(nèi)是否存在需要填充的新區(qū)段，如果存在，則依次把它們保存起來(lái)。反復(fù)這個(gè)過程，直到所保存的各區(qū)段都填充完畢。二、掃描線種子填充算法實(shí)現(xiàn)借助于堆棧，上述算法實(shí)現(xiàn)步驟如下：1、初始化堆棧。2、種子壓入堆棧。3、while（堆棧非空） (1)從堆棧彈出種子象素。(2)如果種子象素尚未填充，則：a.求出種子區(qū)段：xleft、xright;b.填充整個(gè)區(qū)段。c.檢查相鄰的上掃描線的xleftxxright區(qū)間內(nèi),是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。d.檢查相鄰的下掃描線的xleftxxright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleftxxright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。四、掃描線種子填充算法特點(diǎn)1、該算法考慮了掃描線上象素的相關(guān)性，種子象素不再代表一個(gè)孤立的象素，而是代表一個(gè)尚未填充的區(qū)段。2、進(jìn)棧時(shí)，只將每個(gè)區(qū)段選一個(gè)象素進(jìn)棧（每個(gè)區(qū)段最右邊或最左邊的象素），這樣解決了堆棧溢出的問題。3、種子出棧時(shí)，則填充整個(gè)區(qū)段。4、這樣有機(jī)的結(jié)合：一邊對(duì)尚未填充象素的登記（素進(jìn)棧），一邊進(jìn)行填充（象素出棧），既可以節(jié)省堆?？臻g，又可以實(shí)施快速填充。2.3.3 邊標(biāo)志填充算法在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個(gè)閉合區(qū)域，填充是逐行進(jìn)行的，即用掃描線逐行對(duì)多邊形求交，在交點(diǎn)對(duì)之間填充。邊標(biāo)志填充算法就是在逐行處理時(shí)，利用邊界色作為標(biāo)志來(lái)進(jìn)行填充的。例如某掃描線從左到右掃描時(shí)碰到邊界色，立刻改變標(biāo)志的狀態(tài)，接下來(lái)再根據(jù)標(biāo)志的狀態(tài)決定某象素點(diǎn)是否填充。一、邊標(biāo)志填充算法思想掃描線具有連貫性，這種連貫性只有在掃描線與多邊形相交處才會(huì)發(fā)生變化，而每次的變化結(jié)果：無(wú)非是在前景色和背景色之間相互“切換”。邊標(biāo)志填充算法正是基于這一發(fā)現(xiàn)，先在屏幕上生成多邊形輪廓線，然后逐條掃描處理。處理中：逐點(diǎn)讀取象素值，若為邊界色，則對(duì)該象素值進(jìn)行顏色切換。二、邊標(biāo)志填充算法實(shí)現(xiàn) 1、用邊界色畫出多邊形輪廓線，也就是將多邊形邊界所經(jīng)過的象素打上邊標(biāo)志。 2、為了縮小范圍，加快填充速度，須找出多邊形的最小包圍盒：xmin、ymin、xmax、ymax。如下圖所示。邊標(biāo)志填充算法3、逐條掃描線進(jìn)行處理，對(duì)每條掃描線依從左往右的順序，逐個(gè)訪問該掃描線上的象素。每遇到邊界象素，標(biāo)志取反。然后，按照標(biāo)志是否為真，決定象素是否為填充色。四、邊標(biāo)志填充算法特點(diǎn)該算法思想簡(jiǎn)單，實(shí)現(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 ;in;i+)line(pi0,pi1,p(i+1)%n0,p(i+1)%n)1); /*畫出多邊形的n條邊*/用求極值的算法，從多邊形頂點(diǎn)數(shù)組p中，求出xmin,xmax,ymin,ymax;for(y=ymin;y=ymax;y+) flag=-1;for(x=xmin;xymax) /*（xmin，ymin）和（xmax，ymax）為窗口左下角、右上角坐標(biāo)。*/*c=*c|0x08; else if(yxmax)*c=*c|0x02;else if(xxmin)*c=*c|0x01;四、CohenSutherland算法的流程圖：3.2.2 中點(diǎn)分割算法CohenSutherland直線裁剪算法，充分利用了直線段與裁剪邊框的相關(guān)性，使裁剪速度大大提高，但在求交過程中仍采用了乘除運(yùn)算，裁剪速度受到影響。而中點(diǎn)分割法的特點(diǎn)，就在于它是用連續(xù)平分線段最終求得交點(diǎn)的方法代替用乘除法實(shí)現(xiàn)求交運(yùn)算。這樣只需進(jìn)行整數(shù)的加法和用運(yùn)算器右移一位來(lái)實(shí)現(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è)，移動(dòng)P1點(diǎn)；（即可能的交點(diǎn)只能出現(xiàn)在PP2段）if(C1&C)!=0) P1=P;（2）如果P1與P不同側(cè)，移動(dòng)P2點(diǎn)。（即可能的交點(diǎn)只能出現(xiàn)在P1P段）if(C1&C)= =0) P2=P;二、中點(diǎn)分割算法實(shí)現(xiàn)：1、將直線的兩端點(diǎn)P1、P2編碼得：C1、C2；2、判別根據(jù)C1和C2的具體值，可以有三種情況：（1）C1C20，表明兩端點(diǎn)全在窗口內(nèi)，因而整個(gè)線段也在窗內(nèi)，應(yīng)予保留。（2）C1&C20（兩端點(diǎn)代碼按位作邏輯乘不為0），即C1和C2至少有某一位同時(shí)為1，表明兩端點(diǎn)必定處于某一邊界的同一外側(cè)，因而整個(gè)線段全在窗外，應(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）對(duì)P1編碼為C1；（4）用中點(diǎn)公式求出中點(diǎn)，并編碼得C；（5）按照中點(diǎn)算法的求交規(guī)則：若P1和P同側(cè)，移動(dòng)P1點(diǎn)；if(C1&C)!=0)P1=P;否則，移動(dòng)P2點(diǎn)。 elseP2=P;（6）流程轉(zhuǎn)（3），直到P1和P2相差一個(gè)單位時(shí)：令交點(diǎn)為P2，取出暫存器的端點(diǎn)賦給P1，然后轉(zhuǎn)向流程1。三、中點(diǎn)分割算法特點(diǎn)：1、求交點(diǎn)的次數(shù)（n）與線段長(zhǎng)度