計(jì)算機(jī)圖形學(xué)：第4章 基本圖形生成算法

1、第四章 基本圖形生成算法4.1引言4.2直線的掃描轉(zhuǎn)換4.3圓的掃描轉(zhuǎn)換4.4橢圓的掃描轉(zhuǎn)換4.5多邊形的掃描轉(zhuǎn)換與區(qū)域填充4.6字符處理4.7屬性處理4.8反走樣4.1引言提出問(wèn)題： 如何在指定的輸出設(shè)備上（顯示器）根據(jù)坐標(biāo)描述構(gòu)造基本二維幾何圖形（點(diǎn)、直線、圓、橢圓、多邊形域、字符串及其相關(guān)屬性等）？?jī)蓚€(gè)基本概念圖形的生成：是在指定的輸出設(shè)備上，根據(jù)坐標(biāo)描述構(gòu)造二維幾何圖形圖形的掃描轉(zhuǎn)換：在光柵顯示器等數(shù)字設(shè)備上確 定一個(gè)最佳逼近于圖形的象素集的過(guò)程。 利用圖形轉(zhuǎn)換算法來(lái)計(jì)算一系列離散點(diǎn)使它們能夠最好地?cái)M合連續(xù)圖形。4.1引言圖形的掃描轉(zhuǎn)換圖5-1 用一系列的象素點(diǎn)來(lái)逼近直線4.2直線的掃

2、描轉(zhuǎn)換直線的掃描轉(zhuǎn)換就是在數(shù)字設(shè)備上繪制一條直線實(shí)質(zhì)上就是往幀緩存寄存器的相應(yīng)單元中填入數(shù)據(jù)。畫(huà)一條從（x1, y1）到（x2, y2）的直線，實(shí)質(zhì)上是一個(gè)計(jì)算并輸出最佳逼近直線的象素序列的過(guò)程。這個(gè)過(guò)程也稱(chēng)為直線光柵化。直線的繪制有什么要求呢？直線的繪制要求1.直線要直，數(shù)據(jù)序列最佳逼近直線，無(wú)斷裂情況；2.直線的端點(diǎn)要準(zhǔn)確，即無(wú)定向性；3.直線的亮度、色澤要均勻；4.畫(huà)線的速度要快5.可按要求賦予直線不同的色澤、亮度及線型等。直線光柵化的主要算法數(shù)值微分算法Bresenham算法改進(jìn)的Bresenham算法算法性能比較1.數(shù)值微分算法數(shù)值微分算法(DDA法，Digital Differen

3、tial Analyzer)算法基礎(chǔ)算法原理算法實(shí)現(xiàn)代碼算法演示算法特點(diǎn)DDA算法基礎(chǔ)待解決問(wèn)題：給定直線兩端點(diǎn)P0(x0,y0)和P1(x1,y1)，畫(huà)出該直線。解決方法：直接從直線的微分方程生成直線直線微分方程如下： DDA算法原理其中， DDA算法原理max(|x|,|y|)=|x|,即|k|1的情況：max(|x|,|y|)=|y|,即|k|1的情況：DDA算法原理對(duì)求出的xi+1，yi+1進(jìn)行四舍五入，即round(xi+1)=(int)(x i+1+0.5)或round(y i+1)=(int)(y i+1+0.5)右圖中，紅色填充點(diǎn)表示的線段：起點(diǎn)為(0，0)終點(diǎn)為(10，20)

4、綠色填充點(diǎn)表示的線段：起點(diǎn)為(0，0)終點(diǎn)為(20，10)示例圖片Void DDAline(int x0,int y0,int x1,int y1) int dx,dy,epsl,k; float x,y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; x=(float)x0; y=(float)y0; if( abs(dx)abs(dy) epsl=abs(dx); else epsl=abs(dy); xIncre=(float)dx/(float)epsl; yIncre=(float)dy/(float)epsl; for(k=0;k0；直線下方的點(diǎn)集， F(x,

5、y)0。中點(diǎn)Bresenham算法基礎(chǔ)中點(diǎn)Bresenham算法基本原理由Bresenham在1965年提出該算法基本原理： 每次在最大位移方向上走一步，另一個(gè)方向是走步還是不走步取決于誤差項(xiàng)的判別。 實(shí)現(xiàn)的方法根據(jù)線段與待選兩點(diǎn)之間的中點(diǎn)的位置關(guān)系確定其中一個(gè)待選點(diǎn)。具體說(shuō)明如下：為簡(jiǎn)化討論，假定0k1，即x是最大位移方向，則x每次都增加1個(gè)單元，即xi+1=xi+1，而y的相應(yīng)增加應(yīng)當(dāng)小于1。為了光柵化，yi+1只可能選擇如下兩種位置之一：中點(diǎn)Bresenham算法基本原理yi+1=yi 或 yi+1=yi+1 兩點(diǎn)中該選擇哪一個(gè)點(diǎn)？（假設(shè)Pu和Pd 為兩個(gè)待選點(diǎn)，M表示Pu和Pd的中點(diǎn)）

6、中點(diǎn)Bresenham算法基本原理欲判斷Q在M的上方還是下方，將M代入F(x,y),再判斷其符號(hào)即可中點(diǎn)Bresenham算法基本原理判別式如下：則有：中點(diǎn)Bresenham算法基本原理誤差項(xiàng)的遞推當(dāng)di0的情況下：中點(diǎn)Bresenham算法基本原理誤差項(xiàng)的遞推:當(dāng)di0的情況下：中點(diǎn)Bresenham算法基本原理計(jì)算d的初始值中點(diǎn)Bresenham算法的實(shí)現(xiàn)過(guò)程僅列出當(dāng)0k1時(shí)的步驟1.輸入直線的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。 2.計(jì)算初始值x、y、d=0.5-k、x=x0、y=y0；3.繪制點(diǎn)(x,y)；根據(jù)d的符號(hào)，更新（ x,y ）和d。若d0，則(x,y)更新為(x+

7、1,y+1)，d更新為d+1-k；否則(x,y)更新為(x+1,y)，d更新為d-k。4.當(dāng)直線沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3。否則結(jié)束。2.計(jì)算初始值x、y、d=x-2y、x=x0、y=y0。若d x1) x = x0;x0= x1;x1=x; y = y0;y0= y1;y1=y; x = x0;y = y0; dx = x1-x0; dy = y1-y0; d = dx - 2*dy; UpInce = 2*dx - 2*dy; DownInce = -2*dy; while(x=x1) putpixel(x,y,RED); x+; if(d0) y+; d+=UpInce; else d+=D

8、ownInce; 中點(diǎn)Bresenham算法的演示用中點(diǎn)Bresenham算法連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。起點(diǎn)的選擇(p0) (2) 確定最大位移方向(k = 0.4 x方向) (3) 計(jì)算誤差項(xiàng) d0 = x - 2y = 1 di+1 = di + 2x - 2y = di + 6 (di 0.5，則(x,y)更新為(x+1,y+1)，同時(shí)將d更新為d-1；否則(x,y)更新為(x+1,y)。5.當(dāng)直線沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3和4。否則結(jié)束。改進(jìn)的Bresenham算法1的實(shí)現(xiàn)代碼僅列出當(dāng)0k1時(shí)的程序void Bresenhamline (int x0,int y0,i

9、nt 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; 改進(jìn)的Bresenham算法1的演示連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段如下E=-0.5 k=0.4x y e(判斷前) e(判斷后)0 0 -0.5 -0.51 0 -0.5 -0.12 1 0.3 -0.73 1 -0.7 -0.34 2 0.1 -0.9 5 2 -0.9 -0.5 改進(jìn)的Bresenham算法的優(yōu)化上

10、述介紹的Bresenham算法在計(jì)算直線斜率與誤差項(xiàng)時(shí)用到小數(shù)與除法?？梢愿挠谜麛?shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號(hào)，因此可作如下替換：2*e*dx。 優(yōu)化后算法的實(shí)現(xiàn)步驟1.輸入直線的兩端點(diǎn)P0(x0,y0)和P1(x1,y1)。2.計(jì)算初始值x、y、e=-x、x=x0、y=y0。3.繪制點(diǎn)(x,y)。4.e更新為e+2y，判斷e的符號(hào)。若e0，則(x,y)更新為(x+1,y+1)，同時(shí)將e更新為e-2x；否則(x,y)更新為(x+1,y)。5.當(dāng)直線沒(méi)有畫(huà)完時(shí)，重復(fù)步驟3和4。否則結(jié)束。改進(jìn)的Bresenham算法2的實(shí)現(xiàn)代碼僅列出當(dāng)0k1時(shí)的程序void Bresenhamline

11、 (int x0,int y0,int x1, int y1) int x, y, dx, dy，e； dx = x1-x0；dy = y1- y0； e=- dx ； x=x0,；y=y0； while(x0) y+； e=e-2*dx； 改進(jìn)的Bresenham算法的演示xyee+2y00-8211-14-421-4632-1004201053-6464-12-274-2885-82例：作連接兩點(diǎn)P0（0,0）和P1（8,5）的直線段。初始值： e=-x=-8, 2y=10, -2x=-1600+1 +10 -16 +10不變不變Bresenham算法特點(diǎn) 0 1 2 3 4 5 6 7

12、8 9654321 0 直線上的點(diǎn)：（0，0）（1，1）（2，1）（3，2）（4，2）（5，3）（6，4）（7，4）（8，5）Bresenham算法特點(diǎn)該算法采用增量計(jì)算，使得對(duì)于每一列，只要檢查一個(gè)誤差項(xiàng)的符號(hào)，就可以確定該列的所求象素。 算法性能比較4.3 圓的掃描轉(zhuǎn)換算法八分法畫(huà)圓簡(jiǎn)單方程產(chǎn)生圓弧中點(diǎn)Bresenham畫(huà)圓4.3.1 八分法畫(huà)圓(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)圓被定義為到給定中心位置(xc,yc)距離為r的點(diǎn)集。圓心位于原點(diǎn)的圓有四條對(duì)稱(chēng)軸x=0,y=0,x=y和x=-y。若已知圓弧上一點(diǎn)(x,y),可以得到其關(guān)于四條

13、對(duì)稱(chēng)軸的其它7個(gè)點(diǎn)，這種性質(zhì)稱(chēng)為圓的八對(duì)稱(chēng)性。八分法畫(huà)圓待解決的問(wèn)題：繪出圓心在原點(diǎn)，半徑為整數(shù)R的圓x2+y2=R2根據(jù)圓的八對(duì)稱(chēng)性，問(wèn)題轉(zhuǎn)換為八分法畫(huà)圓算法void CirclePoints(int x,int y,int color) drawpixel(x,y,color); drawpixel(y,x,color); drawpixel(-x,y,color); drawpixel(y,-x,color); drawpixel(x,-y,color); drawpixel(-y,x,color); drawpixel(-x,-y,color); drawpixel(-y,-x,col

14、or); 4.3.2 簡(jiǎn)單方程產(chǎn)生圓弧算法原理利用圓弧的函數(shù)方程，直接離散計(jì)算 考慮圓弧的函數(shù)方程直角坐標(biāo)系下極坐標(biāo)系下1.直角坐標(biāo)系下產(chǎn)生圓弧圓的函數(shù)方程為：如右圖，在這個(gè)區(qū)間范圍內(nèi)，x為最大位移方向 ，所以有：2. 極坐標(biāo)系下產(chǎn)生圓弧圓的極坐標(biāo)方程為： 簡(jiǎn)單方程產(chǎn)生圓弧特點(diǎn)方法簡(jiǎn)單直觀計(jì)算量很大效率極低4.3.3 中點(diǎn)Bresenham畫(huà)圓基礎(chǔ)知識(shí)基本原理實(shí)現(xiàn)步驟及代碼算法演示1.中點(diǎn)Bresenham畫(huà)圓基礎(chǔ)知識(shí)對(duì)圓x2+y2=R2構(gòu)造函數(shù)：F(x,y)=x2-y2-R2，則：圓上的點(diǎn)，有F(x,y)=0；圓外的點(diǎn)，F(xiàn)(x,y)0；圓內(nèi)的點(diǎn)，F(xiàn)(x,y)0。2.中點(diǎn)Bresenham畫(huà)圓

15、基本原理在此，只考慮如右圖所示的18圓弧。（其最大位移方向?yàn)閤方向） x方向每次走一步， Y方向減1，或減0Pu(xi+1,yi), Pd(xi+1,yi-1)中點(diǎn)Bresenham畫(huà)圓基本原理M的坐標(biāo)為：M(xi +1,yi-0.5)當(dāng)F(xM,yM)0時(shí)，取Pd(xi+1,yi-1)當(dāng)F(xM,yM)=0時(shí)，約定取Pu。當(dāng)d0時(shí)，下一點(diǎn)取Pu(xi +1,yi)；當(dāng)d0時(shí)， 下一點(diǎn)取Pd(xi +1,yi-1)。構(gòu)造判別式如下：中點(diǎn)Bresenham畫(huà)圓基本原理誤差項(xiàng)的遞推 d0時(shí)： 中點(diǎn)Bresenham畫(huà)圓基本原理d0時(shí)： 中點(diǎn)Bresenham畫(huà)圓基本原理判別式的初始值: P0( 0

16、, R)xi=0 ,yi=R中點(diǎn)Bresenham畫(huà)圓算法步驟1.輸入圓的半徑R。2.計(jì)算初始值d=1.25-R、x=0、y=R。3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱(chēng)點(diǎn)。4.判斷d的符號(hào)。若d0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)xy時(shí)，重復(fù)步驟3和4。否則結(jié)束。中點(diǎn)Bresenham畫(huà)圓算法改進(jìn)改進(jìn)方法：用d-0.25代替d算法步驟：1.輸入圓的半徑R。2.計(jì)算初始值d=1-R、x=0、y=R。3.繪制點(diǎn)(x,y)及其在八分圓中的另外七個(gè)對(duì)稱(chēng)點(diǎn)。4.判斷d的符號(hào)。若d

17、0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)xy時(shí)，重復(fù)步驟3和4。否則結(jié)束。中點(diǎn)Bresenham畫(huà)圓實(shí)現(xiàn)代碼MidBresenCircle(int r, int color) int x,y, d; x=0; y=r; d=1-r;while(xy) circlepoints (x,y,color); if(d0；橢圓內(nèi)的點(diǎn)，F(xiàn)(x,y)0，取Pd(xi+1,yi-1)橢圓的Bresenham中點(diǎn)算法原理誤差項(xiàng)的遞推d10：橢圓的Bresenham中點(diǎn)算法原理d10： 橢圓的Bres

18、enham中點(diǎn)算法原理判別式的初始值 橢圓的Bresenham中點(diǎn)算法原理下面推導(dǎo)橢圓弧下半部分的繪制公式基本原理橢圓的Bresenham中點(diǎn)算法原理判別式如下：若d20，取Pl(xi,yi-1)若d20，取Pr(xi+1,yi-1)橢圓的Bresenham中點(diǎn)算法原理誤差項(xiàng)的遞推d20時(shí)：橢圓的Bresenham中點(diǎn)算法原理d20時(shí)： 橢圓的Bresenham中點(diǎn)算法步驟1.輸入橢圓的長(zhǎng)半軸a和短半軸b。2.計(jì)算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.繪制點(diǎn)(x,y)及其在四分象限上的另外三個(gè)對(duì)稱(chēng)點(diǎn)。4.判斷d的符號(hào)。若d0，則先將d更新為d+b2(2x+3)，再將(x,

19、y)更新為(x+1,y)；否則先將d更新為d+b2(2x+3)+a2(-2y+2)，再將(x,y)更新為(x+1,y-1)。5.當(dāng)b2(x+1)0時(shí)，重復(fù)步驟7和8。否則結(jié)束。4.5 多邊形的掃描轉(zhuǎn)換與區(qū)域填充引 言多邊形的掃描轉(zhuǎn)換區(qū)域填充 引 言多邊形的掃描轉(zhuǎn)換:主要是通過(guò)確定穿越區(qū)域的掃描線的覆蓋區(qū)間來(lái)填充區(qū)域填充:是從給定的位置開(kāi)始涂描直到指定的邊界條件為止。(本節(jié)討論實(shí)心區(qū)域填充)4.5.1 多邊形的掃描轉(zhuǎn)換什么是多邊形的掃描轉(zhuǎn)換？多邊形的掃描轉(zhuǎn)換算法x-掃描線算法邊緣填充算法什么是多邊形的掃描轉(zhuǎn)換？在計(jì)算機(jī)圖形學(xué)中，多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。頂點(diǎn)表示是用多邊形的

20、頂點(diǎn)序列來(lái)表示多邊形。表示直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換不能直接用于面著色什么是多邊形的掃描轉(zhuǎn)換？點(diǎn)陣表示是用位于多邊形內(nèi)的象素集合來(lái)刻畫(huà)多邊形。丟失了許多幾何信息便于幀緩沖器表示圖形，是面著色所需要的圖形表示形式光柵圖形中把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，這種轉(zhuǎn)換稱(chēng)為多邊形的掃描轉(zhuǎn)換。 基本思想算法原理實(shí)現(xiàn)步驟算法演示算法的改進(jìn) (1) X-掃描線算法 X-掃描線算法是按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，完成轉(zhuǎn)換工作。區(qū)間的端點(diǎn)可以通過(guò)計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。 X-掃描線算法基本思想X-掃描線算法的原理如右圖所示，對(duì)于每條穿

21、越多邊形的掃描線，該算法確定掃描線與多邊形邊相交區(qū)間的像素點(diǎn)位置。例如對(duì)于y=3與多邊形交于四個(gè)點(diǎn)，定義了兩個(gè)區(qū)間即x=2到x=4和x=7到x=9的區(qū)間，所以該區(qū)間的像素應(yīng)取填充色核心：按x遞增的順序排列交點(diǎn)的x坐標(biāo)序列X-掃描線算法步驟(1)確定多邊形所占有的最大掃描線數(shù)，得到多邊形頂點(diǎn)的最小和最大y值（ymin和ymax）。(2)從y=ymin到y(tǒng)=ymax，每次用一條掃描線進(jìn)行填充。(3)對(duì)一條掃描線填充的過(guò)程可分為四個(gè)步驟：a.求交點(diǎn)b.排序c.交點(diǎn)配對(duì)d.區(qū)間填色X-掃描線算法中交點(diǎn)取舍問(wèn)題當(dāng)掃描線與多邊形頂點(diǎn)相交時(shí)，交點(diǎn)的取舍問(wèn)題如右圖所示，當(dāng)y=1時(shí)，雖然得到兩個(gè)交點(diǎn)，但這兩個(gè)交

22、點(diǎn)確定的區(qū)間并不能填充X-掃描線算法中交點(diǎn)取舍問(wèn)題當(dāng)掃描線與多邊形的頂點(diǎn)相交時(shí)，(1)若共享頂點(diǎn)的兩條邊分別落在掃描線的兩邊，交點(diǎn)只算一個(gè)；(2)若共享頂點(diǎn)的兩條邊在掃描線的同一邊，這時(shí)交點(diǎn)作為零個(gè)或兩個(gè)。 示例如右圖：兩側(cè)為1，上為2 ，下為00111102220X-掃描線算法演示X-掃描線算法的改進(jìn)由于該算法在處理每條掃描線時(shí)，需要與多邊形的所有邊求交，而實(shí)際中一條掃描線一般只和少數(shù)邊相交，甚至根本不與多邊形相交，所以該算法處理的效率很低。改進(jìn)的有效邊表算法改進(jìn)的有效邊表算法算法改進(jìn)原理基本概念算法實(shí)現(xiàn)步驟算法演示算法特點(diǎn)改進(jìn)的有效邊表算法原理改進(jìn)的有效邊表算法也稱(chēng)為Y連貫性算法改進(jìn)原理處

23、理一條掃描線時(shí)，僅對(duì)有效邊求交利用掃描線的連貫性利用多邊形邊的連貫性相關(guān)概念有效邊（Active Edge）：指與當(dāng)前掃描線相交的多邊形的邊，也稱(chēng)為活性邊。有效邊表（Active Edge Table, AET）：把有效邊按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，此鏈表稱(chēng)為有效邊表。相關(guān)概念有效邊表的每個(gè)結(jié)點(diǎn)存放對(duì)應(yīng)邊的有關(guān)信息如下： x ymax 1/k next其中，x為當(dāng)前掃描線與邊的交點(diǎn)；ymax是對(duì)應(yīng)邊的有關(guān)信息；舉例如下 有效邊表示例對(duì)應(yīng)左圖的y=8的有效邊表為：邊表的構(gòu)造步驟(1)首先構(gòu)造一個(gè)縱向鏈表，鏈表的長(zhǎng)度為多邊形所占有的最大掃描線數(shù)，鏈表的每個(gè)結(jié)點(diǎn)，稱(chēng)為一個(gè)桶，則對(duì)

24、應(yīng)多邊形覆蓋的每一條掃描線。(2)將每條邊的信息鏈入與該邊最小y坐標(biāo)（ymin ）相對(duì)應(yīng)的桶處。也就是說(shuō)，若某邊的較低端點(diǎn)為ymin，則該邊就放在相應(yīng)的掃描線桶中。邊表的構(gòu)造步驟(3)每條邊的數(shù)據(jù)形成一個(gè)結(jié)點(diǎn)，內(nèi)容包括：該掃描線與該邊的初始交點(diǎn)x（即較低端點(diǎn)的x值），1/k，以及該邊的最大y值ymax。x|ymin ymax 1/k NEXT(4)同一桶中若干條邊按X|ymin由小到大排序，若X|ymin 相等，則按照1/k由小到大排序。解決頂點(diǎn)交點(diǎn)計(jì)為1時(shí)的情形當(dāng)掃描線與多邊形的頂點(diǎn)相交時(shí)，可以將多邊形的某些邊縮短來(lái)分離那些應(yīng)記為個(gè)交點(diǎn)的頂點(diǎn)。分為兩種策略：將ymax更新為ymax -1將y

25、min更新為ymin+1解決頂點(diǎn)交點(diǎn)計(jì)為1時(shí)的情形處理交點(diǎn)為1時(shí)的舉例處理交點(diǎn)為1時(shí)的舉例算法實(shí)現(xiàn)步驟(1)初始化：構(gòu)造邊表，AET表置空；(2)將第一個(gè)不空的ET表中的邊與AET表并；(3)由AET表中取出交點(diǎn)對(duì)進(jìn)行填充。填充之后刪除y=ymax的邊；(4)yi+1=yi+1,根據(jù)xi+1=xi+1/k計(jì)算并修改AET表，同時(shí)合并ET表中y=yi+1桶中的邊，按次序插入到AET表中，形成新的AET表；(5)AET表不為空則轉(zhuǎn)(3)，否則結(jié)束。算法步驟演示算法的特點(diǎn)對(duì)各種表的維持和排序開(kāi)銷(xiāo)太大適合軟件實(shí)現(xiàn)不適合硬件實(shí)現(xiàn)邊緣填充算法邊緣填充算法柵欄填充算法邊標(biāo)志算法(1) 邊緣填充算法基本思想按

26、任意順序處理多邊形的每條邊在處理每條邊時(shí)，首先求出該邊與掃描線的交點(diǎn)，然后將每一條掃描線上交點(diǎn)右方的所有元素取補(bǔ)；多邊形的所有邊處理完后，填充即完成算法特點(diǎn)算法簡(jiǎn)單，但對(duì)于復(fù)雜圖型，每一象素可能被訪問(wèn)多次適用于具有幀緩存的圖形系統(tǒng)算法演示(2) 柵欄填充算法柵欄：一條過(guò)多邊形頂點(diǎn)且與掃描線垂直的直線基本思想按任意順序處理多邊形的每條邊，在處理每條邊時(shí)，首先求出該邊與掃描線的交點(diǎn)，然后將交點(diǎn)與柵欄之間的象素取補(bǔ)；多邊形的所有邊處理完后，填充即完成算法特點(diǎn)減少了被重復(fù)訪問(wèn)像素的數(shù)目，但仍有像素被重復(fù)訪問(wèn)算法演示(3)邊標(biāo)志算法基本思想 先用一種特殊的顏色在幀緩沖存儲(chǔ)器中將多邊形的邊界（水平邊除外）

27、勾畫(huà)出來(lái)，然后將著色的像素點(diǎn)依x坐標(biāo)遞增的順序兩兩配對(duì)，再將每一對(duì)像素所構(gòu)成的掃描線區(qū)間內(nèi)的所有像素置為填充色算法步驟(1)打標(biāo)記(2)填充算法特點(diǎn) 對(duì)每個(gè)像素僅訪問(wèn)一次 當(dāng)用軟件實(shí)現(xiàn)本算法時(shí)，速度與改進(jìn)的有效邊表算法相當(dāng)，但用硬件實(shí)現(xiàn)后本算法速度會(huì)有很大提高。算法演示4.4.3 區(qū)域填充引言區(qū)域填充算法邊界填充算法泛填充算法其它相關(guān)的知識(shí)引言區(qū)域：指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。區(qū)域的兩種表示形式：內(nèi)點(diǎn)表示和邊界表示。在內(nèi)點(diǎn)表示中，區(qū)域內(nèi)的所有象素著同一顏色。在邊界表示中，區(qū)域的邊界點(diǎn)著同一顏色。區(qū)域填充：指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。 引

28、言區(qū)域填充算法要求區(qū)域是連通的，因?yàn)橹挥性谶B通區(qū)域中，才可能將種子點(diǎn)的顏色擴(kuò)展到區(qū)域內(nèi)的其它點(diǎn)。區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域。 4鄰接點(diǎn)8鄰接點(diǎn)引言4-連通區(qū)域和8-連通區(qū)域如下所示邊界填充算法基本思想算法實(shí)現(xiàn)步驟4-連通邊界填充算法8-連通邊界填充算法算法特點(diǎn)算法改進(jìn)邊界填充算法基本思想基本思想算法的輸入：種子點(diǎn)坐標(biāo)(x,y)填充色、邊界顏色算法的思想：從(x,y)開(kāi)始檢測(cè)相鄰位置是否是邊界顏色，若不是，就用填充色著色，并檢測(cè)其相鄰位置；該過(guò)程延續(xù)到已經(jīng)檢測(cè)完區(qū)域邊界顏色范圍內(nèi)的所有像素為止4-連通邊界填充算法步驟利用棧結(jié)構(gòu)實(shí)現(xiàn)的算法步驟：種子象素入棧（棧非空）；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如

29、下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)檢查出棧象素的4-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。算法演示(左、上、右、下)8-連通邊界填充算法步驟利用棧結(jié)構(gòu)實(shí)現(xiàn)的算法步驟：種子象素入棧；當(dāng)棧非空時(shí)重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將出棧象素置成填充色；(3)檢查出棧象素的8-鄰接點(diǎn)，若其中某個(gè)象素點(diǎn)不是邊界色且未置成多邊形色，則把該象素入棧。算法演示邊界填充算法的特點(diǎn)可以用于填充帶有內(nèi)孔的平面區(qū)域。把太多的象素壓入堆棧，有些像素入棧多次要求很大的存儲(chǔ)空間邊界填充算法的改進(jìn)通過(guò)沿掃描線填充水平象素段，來(lái)代替處理4-鄰接點(diǎn)和8-

30、鄰接點(diǎn)。這樣就僅需要將每個(gè)水平像素的起始位置放進(jìn)棧，不必將所有的當(dāng)前位置周?chē)奈闯鰜?lái)鄰接點(diǎn)放入棧具體實(shí)現(xiàn)步驟如下邊界填充算法的改進(jìn)種子象素入棧；當(dāng)棧非空時(shí)作如下三步操作：(1)棧頂象素出棧；(2)填充出棧象素所在掃描行的連續(xù)象素段，直到遇到邊界象素為止，即每出棧一個(gè)象素，就對(duì)包含該象素的整個(gè)掃描線區(qū)間進(jìn)行填充；(3)在區(qū)間中檢查與當(dāng)前掃描線相鄰的上下兩條掃描線的有關(guān)象素是否全為邊界象素或已填充的象素，若存在非邊界、未填充邊界的象素，則把每一區(qū)間的最右象素取作種子象素入棧。其它相關(guān)概念1.內(nèi)-外測(cè)試為了測(cè)試平面上哪個(gè)區(qū)域是“內(nèi)部”哪個(gè)是“外部”，提出如下規(guī)則：奇偶規(guī)則非零環(huán)繞數(shù)規(guī)則2.曲線邊界區(qū)

31、域的填充奇偶規(guī)則奇-偶規(guī)則（Odd-even Rule）從任意位置p作一條射線，若與該射線相交的多邊形邊的數(shù)目為奇數(shù)，則p是多邊形內(nèi)部點(diǎn)，否則是外部點(diǎn)。動(dòng)態(tài)演示非零環(huán)繞數(shù)規(guī)則非零環(huán)繞數(shù)規(guī)則（Nonzero Winding Number Rule）1. 使多邊形的邊變?yōu)槭噶?，將環(huán)繞數(shù)初始化為零。2. 從任意位置p作一條射線。當(dāng)從p點(diǎn)沿射線方向移動(dòng)時(shí)，對(duì)在每個(gè)方向上穿過(guò)射線的邊計(jì)數(shù)，每當(dāng)多邊形的邊從右到左穿過(guò)射線時(shí)，環(huán)繞數(shù)加1，從左到右時(shí)，環(huán)繞數(shù)減1。3. 處理完多邊形的所有相關(guān)邊之后，若環(huán)繞數(shù)為非零，則p為內(nèi)部點(diǎn)，否則，p是外部點(diǎn)。動(dòng)態(tài)演示4.5 字符字符：指數(shù)字、字母、漢字等符號(hào)。計(jì)算機(jī)中字符

32、由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)國(guó)際上最流行的字符集是“美國(guó)信息交換用標(biāo)準(zhǔn)代碼集”簡(jiǎn)稱(chēng)ASCII碼。我國(guó)除采用ASCII碼外，還另外制定了漢字編碼的國(guó)家標(biāo)準(zhǔn)字符集GB231280。為了在顯示器等輸出設(shè)備上輸出字符，系統(tǒng)中必須裝備有相應(yīng)的字庫(kù)。字庫(kù)中存儲(chǔ)了每個(gè)字符的形狀信息，字庫(kù)分為：點(diǎn)陣字符矢量字符 返回點(diǎn)陣字符在點(diǎn)陣表示中，每個(gè)字符由一個(gè)點(diǎn)陣位圖來(lái)表示顯示時(shí)經(jīng)過(guò)些簡(jiǎn)單的轉(zhuǎn)換形成字符的象素圖案點(diǎn)陣字符的顯示分為兩步：首先從字庫(kù)中將它的位圖檢索出來(lái)然后將檢索到的位圖寫(xiě)到幀緩沖器中 點(diǎn)陣字符的特點(diǎn)：定義和顯示直接、簡(jiǎn)單需要大量存儲(chǔ)空間字符A的點(diǎn)陣表示字符A的點(diǎn)陣表示矢量字符矢量字符采用直線和曲線段來(lái)描述字符

33、形狀，記錄字符的筆畫(huà)信息而不是整個(gè)位圖。矢量字符的顯示分為兩步：首先從字庫(kù)中將它的字符信息檢索出來(lái)然后取出端點(diǎn)坐標(biāo)，對(duì)其進(jìn)行適當(dāng)?shù)膸缀巫儞Q，再根據(jù)各端點(diǎn)的標(biāo)志顯示出字符。 目前常用的矢量字符表示是輪廓字型法矢量字符A的表示特點(diǎn)：具有存儲(chǔ)空間小，美觀、變換方便等優(yōu)點(diǎn)。矢量字符A的表示4.6 屬性處理引言線型和線寬字符的屬性區(qū)域填充屬性返回引 言圖素和圖段的外觀由其屬性來(lái)控制。例如對(duì)于線段來(lái)說(shuō)，顏色、線型、線寬等圖形軟件中常通過(guò)當(dāng)前屬性值表來(lái)選擇屬性圖形系統(tǒng)可提供的最明顯的屬性控制是顏色和亮度等級(jí)選擇線型和線寬線型處理線寬處理線刷子方刷子區(qū)域填充改變刷子形狀曲線的線型和線寬線型處理線型包括實(shí)線、虛

34、線和點(diǎn)線等通過(guò)設(shè)置沿線路徑實(shí)線段的長(zhǎng)度和間距來(lái)修改畫(huà)線算法，以生成各種線型實(shí)心段和中間空白段的長(zhǎng)度（象素?cái)?shù)目）可用象素模板(pixel mask)指定。存在問(wèn)題：如何保持任何方向的劃線長(zhǎng)度近似地相等解決：可根據(jù)線的斜率來(lái)調(diào)整實(shí)心段和中間空白段的象素?cái)?shù)目。線段a和線段b都是根據(jù)11100的像素模板畫(huà)出的線刷子處理線寬線刷子處理線寬特點(diǎn)特點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單、效率高。斜線與水平(或垂直)線不一樣粗。當(dāng)線寬為偶數(shù)個(gè)象素時(shí)，線的中心將偏移半個(gè)象素。利用線刷子生成線的始末端總是水平或垂直的，看起來(lái)不太自然。解決：添加“線帽（line cap）”線帽當(dāng)比較接近水平的線與比較接近垂直的線匯合時(shí)，匯合處外角將有缺口解

35、決方法解決：斜角連接（miter join）、圓連接（round join）、斜切連接（bevel join）方刷子特點(diǎn)：方刷子繪制的線條（斜線）比用線刷子所繪制的線條要粗一些方刷子繪制的斜線與水平（或垂直）線不一樣粗方刷子繪制的線條自然地帶有一個(gè)“方線帽”區(qū)域填充處理線寬先算出線條各角點(diǎn)再用直線把相鄰角點(diǎn)連接起來(lái)最后調(diào)用多邊形填充算法把得到的四邊形進(jìn)行填充，即可生成具有寬度的線條改變刷子形狀處理線寬利用像素模板來(lái)定義其它形狀的刷子曲線的線型線型：可采用象素模板的方法曲線的線寬通過(guò)利用刷子的形狀來(lái)實(shí)現(xiàn)線寬：線刷子方刷子要顯示一致的曲線寬度可通過(guò)旋轉(zhuǎn)刷子方向以使其在沿曲線移動(dòng)時(shí)與斜率方向一致，圓

36、弧刷子采用填充的辦法字符的屬性字符的常用屬性包括字體、字形、字號(hào)、字間距、行間距等。一般字體確定風(fēng)格，字形確定外觀，字號(hào)確定尺寸。字符的常用屬性如下字符串屬性在輸出字符串之前要指定如下屬性：文本高度、文本寬度（擴(kuò)展/壓縮因子）、字符方向、文本路徑方向、對(duì)齊方式（左對(duì)齊，中心對(duì)齊，或右對(duì)齊，指定起始、終止點(diǎn)）、文本字體、字符的顏色屬性等。實(shí)際中還要根據(jù)系統(tǒng)進(jìn)行設(shè)計(jì)如反繪（從右到左）、倒繪（旋轉(zhuǎn)180）、寫(xiě)方式（替換或與方式）等。區(qū)域填充屬性區(qū)域填充屬性選擇包括顏色、圖案和透明度。根據(jù)圖案填充平面區(qū)域的基本思想首先用模板定義各種圖案。然后，修改填充的掃描轉(zhuǎn)換算法：在確定了區(qū)域內(nèi)一象素之后，不是馬上往該象素填色而是先查詢(xún)模板位圖的對(duì)應(yīng)位置若是以透明方式填充圖案，則當(dāng)模板位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫(xiě)象素，否則，不改變?cè)撓笏氐闹?。若是以不透明方式填充圖案，則視模板位圖對(duì)應(yīng)位置為1或0來(lái)決定是用前景