1、第二章 基本圖形的生成與計算,直線的生成算法 圓的生成算法 區(qū)域填充算法 字符的生成 圖形求交 圖形裁剪,光柵掃描式顯示器:CRT中的水平和垂直偏轉(zhuǎn)線圈分別產(chǎn)生水平和垂直磁場，電子束則在不同方向磁場力作用下進行行和列掃描，將屏幕分成由像素構(gòu)成的光柵網(wǎng)格，其中像素具有灰度和顏色,概述,光柵掃描顯示屏幕可以看作一個象素矩陣 每個象素可以用一種或多種顏色顯示一種圖形:具有一種或者多種顏色象素的集合. 圖形掃描轉(zhuǎn)換或生成:把點,線,區(qū)域和文字等從幾何描述轉(zhuǎn)換為顯存中位圖的過程.,傳統(tǒng)顯示器的網(wǎng)點式蔭罩,“瓏管”顯示器的網(wǎng)點式蔭罩,圖形掃描轉(zhuǎn)換分為兩個步驟: (1)確定有關(guān)象素 (2)用圖形的顏色或其他

2、屬性,對象素進行寫操作 通常用調(diào)用設(shè)備驅(qū)動程序來實現(xiàn) 掃描轉(zhuǎn)換的主要工作:確定最佳逼近圖形的象素集 一維:當不考慮線寬時,用一個象素寬的象素序列來顯示圖形 二維:區(qū)域的填充,即圖形的光柵化,必須確定區(qū)域所對應(yīng)的象素集,再用所要求的顏色或圖案顯示(填充),點是圖形中最基本的圖素，直線、曲線以及其它圖元都是點的集合 函數(shù)作用：使屏幕上坐標(x,y)的點輝亮,P(x,y),putpixel(x,y,color),圖形的生成 給定直線段的兩個端點(x0,y0)和(x1,y1), 把它在光柵掃描顯示器上顯示出來 在數(shù)學(xué)上，理想的直線是沒有寬度的，是由無數(shù)個在它上面的點構(gòu)成的集合。直線可以向一個方向及其相

3、反的方向無限延長 在圖形學(xué)中研究的對象是直線段，它是一條具有一個Pixel或多個Pixel寬的直線段,在數(shù)學(xué)上，理想的直線是一條由無窮多個無限小的連續(xù)的點組成,而圖形顯示器是由一個個排列有序的像素構(gòu)成，每個象素具有一定的尺寸,我們只能用二維光柵格網(wǎng)上盡可能靠近這條直線的象素點的集合來表示它,對于光柵顯示器來說: 1、像素間為均勻網(wǎng)格 2、整型坐標系 (10.48, 20.51)(10, 21),直線的掃描轉(zhuǎn)換 直線的掃描轉(zhuǎn)換，就是要找出顯示平面上最佳逼近理想直線的那些象素的坐標值，并將這些象素置成所要求的顏色,直線的掃描轉(zhuǎn)換,2.1 直線的生成算法,計算機是如何畫直線的？簡單來說，如下圖所示，

4、真實的直線是連續(xù)的，但我們的計算機顯示的精度有限，不可能真正顯示連續(xù)的直線，于是我們用一系列離散化后的點（像素）來近似表現(xiàn)這條直線,對于水平線、垂直線和45斜線，選擇哪些像素是顯而易見的，但是對于其它的直線，確定用哪些像素來表示它就不那麼簡單了。本節(jié)我們介紹用于直線掃描轉(zhuǎn)換的常用算法： 數(shù)值微分法 Bresenham畫線算法,象素,線,圓,Geometric Graphics i | Pi-nearest pixel 基本圖形的生成算法任務(wù)之一就是找出所有的i 。,在介紹畫線算法之前，我們先討論畫直線的基本要求： 外觀要直 直線必須有精確的起點和終點 線寬應(yīng)當均勻一致、且與直線的長度和方向無關(guān)

5、 算法速度要快,線條外觀應(yīng)該顯得筆直：由連續(xù)點組成的直線要顯示在離散網(wǎng)格的平面上，一定會有不經(jīng)過網(wǎng)格的點，如左下圖。在這種情況下，必須選擇靠近直線的網(wǎng)格點來逼近這條直線。若選擇的好，線就顯得較直；否則就會較彎曲，如右下,直線端點位置應(yīng)該準確：畫出的線段如果不準確，往往會使兩條線之間不能很好的鑲接，如右圖 直線濃度應(yīng)該均勻，直線濃度應(yīng)該與線段的長度和斜率無關(guān)：線段的濃度與單位線段中所顯示的點數(shù)成正比。要保持線段的濃度均勻端點應(yīng)該等距分布。只有與軸平行和成45的線才能做到,顯示線段的速度應(yīng)快：生成直線可用軟件和硬件來實現(xiàn)，一般情況下，硬件要比軟件實現(xiàn)得快,直線方程：ykxb k是直線的斜率，b是y

6、方向的截距，若直線的兩端點為（x0，y0）及（x1，y1），則 k（y1y0）/（x1x0） by1kx1 對于一直線，在x方向取間隔dx， 則可計算y方向的間隔dy dyk*dx,1、直接求交法,但是由于y值由y=kx+b計算而來，可能為浮點數(shù)，需要對y值取整 對某個xi它所對應(yīng)的yi=kxi+b的結(jié)果進行四舍五入，記為yi,rround(yi)(int)(yi+0.5)，故對直線段P0P1掃描實際得到像素集為(xi,yi,r) ，其中yi,r是yi四舍五入所得的整數(shù)值 這個方法直觀，但效率太低，因為每一步需要一次浮點乘法和一次四舍五入取整運算,數(shù)值微分法(digital different

7、ial analyzer，DDA) 是一種基于直線的微分方程來生成直線的方法 先對一個方向的坐標取單位步長的變化,然后計算另一方向坐標相應(yīng)的變化值,.1.直線DDA算法 (Digital Differential Analyzer),一、直線DDA算法描述： 設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點和終點坐標，由直線的微分方程得 可通過計算由x方向的增量x引起y的改變來生成直線 也可通過計算由y方向的增量y引起x的改變來生成直線：,注意到公式: 因此當Dx=1時， 有yi+1=yi+m 即： Dy=m,.1.直線DDA算法,(xi+1,yi+m),(xi, round(yi),(x

8、 i , yi),柵格交點表示象素點位置,。,。,。,。,(xi+1,round(yi+m),當Dy=1時，有xi+1=xi+1/m, 即Dx=1/m,所以:當x每遞增1，y遞增m(即直線斜率) 注意上述分析的算法僅適用于m 1的情形。在這種情況下，x每增加1,y最多增加1 當 m 1時，必須把x，y的位置互換，依此處理，要保證任意兩點連線正確顯示,.1.直線DDA算法,當 DxDy 時，讓 x 從 x1 到 x2 變化，每步遞增 1， 那么，x 的變化可以表示為 xi+1xi1 (Dx=1) y 的變化可以表示為 yi+1yim ( Dy=m) 用上式可求得圖中直線 P1P2 和 y 向網(wǎng)格

9、線的交點，但顯 示時要用舍入 找到最靠近交點處的象素點來表示,.1.直線DDA算法,上述分析的算法僅適用于m 1的情形 原因： 當|m|1)，這時象素點會稀疏，所畫直線會斷斷續(xù)續(xù),因此，當 DxDy 時,讓 y從 y1 到 y2 變化，每步遞增 1， 那么，y 的變化可以表示為 yi+1yi1 (Dy=1) x 的變化可以表示為 xi+1xi1/m (Dx=1/m),讓 y 遞增 1，x作相應(yīng)變化。,.1. 直線DDA算法,i Xi=x i-1+1 y i=y i-1+k round (yi) 坐標 0 0 0 round( 0)=0 (0,0) 1 1 0+0.4=0.4 round(0.4

10、)=0 (1,0) 2 2 0.4+0.4=0.8 round(0.8)=1 (2,1) 3 3 0.8+0.4=1.2 round( 1.2)=1 (3,1) 4 4 1.2+0.4=1.6 round(1.6)=2 (4,2) 5 5 1.6+0.4=2.0 round( 2.0)=2 (5,2),例：用DDA算法畫直線段P0(0,0)-P1(5,2),k=(2-0)/(5-0)=0.4,已知直線 y=mx+b |m|1 m= Dy/ Dx,即：yi=y i-1+1 x i=xi-1+1/m,( round (xi), yi ),例：畫出p0(0,0)和p(2,6)之間的一條直線。 m=(

11、6-0)/(2-0)=31 采用通過yi的變化確定xi的變化 即： Dy =1 Dx=1/m 1/m=1/3=0.33,i yi=yi-1+1 xi=xi-1+1/m round (xi) 坐標 0 0 0 round( 0)=0 (0,0) 1 1 0+0.33=0.33 round(0.33)=0 (0,1) 2 2 0.33+0.33=0.66 round(0.66)=1 (1,2) 3 3 0.66+0.33=0.99 round(0.99)=1 (1,3) 4 4 0.99+0.33=1.32 round(1.32)=1 (1,4) 5 5 1.32+0.33=1.65 round(

12、1.65)=2 (2,5) 6 6 1.65+0.33=1.98 round(1.98)=2 (2,6),Line(0 , 0 , 2 , 6),讀入直線的起點(x0,y0)和終點(x,y),開始,結(jié)束,Y N,綜合考慮，按照從(x1, y1)到(x2, y2)方向不同，分8個象限 (圖2.1)。對于方向在第1a象限內(nèi)的直線而言，取增量值Dx=1， Dy=m。對于方向在第1b象限內(nèi)的直線而言，取增量值Dy=1，Dx= 1/m,圖2.1 直線方向的8個象限,表2.1 8個象限中的坐標增量值,研究表中的數(shù)據(jù)，可以發(fā)現(xiàn)兩個規(guī)律: 當dxdy時 Dx = 1，Dy = m 否則 Dx = 1/m，Dy

13、 = 1 Dx、Dy的符號與dx、dy的符號相同。,.1. 直線DDA算法,使用DDA算法，每生成 一條直線做兩次除法，畫線 中每一點做兩次加法。因此， 用DDA法生成直線的速度是 相當快的。,void CDDAlineView:Ddaline(CDC *pDC, int x0, int y0, int x1, int y1, COLORREF color) int dx,dy,steps,k,x,y; float delta_x,delta_y; dx=x1-x0; dy=y1-y0; if(abs(dx)abs(dy) /比較dx和dy哪個大，即判斷斜率大于還是小于1 steps=dx;

14、else steps=dy; delta_x=(float)dx/(float)steps; /計算x方向上的增量，如果steps=dx,此時delta_x=1,則delta_y=m delta_y=(float)dy/(float)steps; /計算y方向上的增量，如果steps=dy,此時delta_y=1,則delta_y=1/m x=x0; y=y0; pDC-SetPixel(x,y,color); /畫第一個點 for(k=1;kSetPixel(x,y,color); ,數(shù)字微分(DDA)法缺點： 在此算法中，y、k必須是float，且每一步都必須對y進行舍入取整，不利于硬件實

15、現(xiàn),在直線生成的算法中Bresenham算法是最有效的算法之一 該方法最初是為數(shù)字繪圖儀設(shè)計的，由于適用于光柵圖形顯示器，所以被廣泛用于直線的掃描轉(zhuǎn)換與其他一些應(yīng)用 Bresenham也是通過在每列像素中確定與理想直線最近的像素來進行直線的掃描轉(zhuǎn)換的 算法原理：過各行、各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后確定該列像素中與此交點最近的像素,.1. 直線Bresenham算法,設(shè)直線從起點(x1, y1)到終點(x2, y2)。直線可表示為 方程y=mx+b，其中 b=y1-m*x1 m=（y2-y1)/(x2-x1)=dy/dx,此處的討論先

16、將直線方向限于1a象限(圖2.1)，在這種情況下，當直線光柵化時，x每次都增加1個單元，即xi+1 = xi + 1而y的相應(yīng)增加值應(yīng)當小于1。為了光柵化，yi+1只可能選擇圖2.2中兩種位置之一,圖2.2 縱坐標的位置選擇,.1. 直線Bresenham算法,yi+1的位置選擇yi+1 =yi或者yi+1=yi+1，選擇的原則是看精確 值y與yi及yi+1的距離d1及d2的大小而定。計算公式為 y = m(xi + 1) + b (2.1) d1 = y yi (2.2) d2 = yi +1 y (2.3) 如果d1d20，則yi+1=yi+1，否則yi+1=yi。 將式(2.1)、(2.

17、2)、(2.3)代入d1d2，再用dx乘等式兩邊，并以Pi=(d1d2) dx代入上述等式，得 Pi = 2xidy2yidx+2dy+(2b1) dx (2.4) d1d2是用以判斷符號的誤差。由于在1a象限，dx總大于0，所 以Pi仍舊可以用作判斷符號的誤差。Pi+1為 Pi+1 = 2xi +1 dy2yi +1 dx+2dy+(2b1) dx Pi+1 = Pi+2dy2(yi+1yi) dx (2.5),.1. 直線Bresenham算法,求誤差的初值P1，可將x1、y1和b代入式(2.4)中的xi、yi而得到 P1 = 2dydx 綜述上面的推導(dǎo)，第1a象限內(nèi)的直線Bresenha

18、m算法思想如下： 畫點(x1, y1)，dx=x2x1，dy=y2y1，計算誤差初值P1=2dy dx，i=1； 求直線的下一點位置 xi+1 = xi + 1 如果Pi0，則yi+1=yi+1，否則yi+1=yi； 畫點(xi+1, yi+1)； 求下一個誤差Pi+1，如果Pi0，則Pi+1=Pi+2dy2dx，否則 Pi+1=Pi+2dy； i=i+1；如果idx+1則轉(zhuǎn)步驟2；否則結(jié)束操作。,.1. 直線Bresenham算法,Pi+1 = Pi+2dy2(yi+1yi) dx,例：利用Bresenham算法畫出L0(0,0)和L(6,2)之間的一條直線。解答 K=(2-0)/(6-0)

19、=1/3=1,dx=1,dy=k L0(0,0),起點(0,0) pi 坐標 p0= 2k-1 =-1/30 (2,1) p10 p2=p1+2k-2=-10 (5,2) p40 p5=p4+2k-2=-10 (6,2),p0= 2k -1 當Pi0時Pi+1=Pi+2k-2 當Pi0時pi+1=pi+ 2k,Bresenham算法的優(yōu)點如下： 不必計算直線的斜率，因此不做除法 不用浮點數(shù)，只用整數(shù) 只做整數(shù)加減運算和乘2運算，而乘2運算可以用移位操作實現(xiàn) Bresenham算法的運算速度很快，并適于用硬件實現(xiàn),.1. 直線Bresenham算法,討論：以上討論的是 0yx 的情況，對于適用所

20、有8個方向的直線(圖2.1)的生成算法，則要考慮以判斷條件|dx|dy|為分支，并分別將2a、3a象限的直線和3b、4b象限的直線變換到1a、4a和2b、1b象限方向去，以實現(xiàn)程序處理的簡潔,如下圖所示，線段的方向可分為八種，從原點出發(fā)射向八個區(qū)。由線段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。,Bresenham算法(其它教材上介紹的),假定直線段的0k1 基本原理：,誤差項d的計算 d初=0， 每走一步：d=d+k 一旦y方向上走了一步，d=d-1,算法步驟： 1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。 2.計算初始值x、y、d=0、x=x0、y=y0。 3

21、.繪制點(x,y)。 4.d更新為d+k，判斷d的值。若d0.5，則(x,y)更新為(x+1,y+1)，同時將d更新為d-1；否則(x,y)更新為(x+1,y)。 5.當直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。,改進1：令e=d-0.5,e初=-0.5， 每走一步有e=e+k。 if (e0) then e=e-1,算法步驟為： 1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。 2.計算初始值x、y、e=-0.5、x=x0、y=y0。 3.繪制點(x,y)。 4.e更新為e+k，判斷e的符號。若e0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-1；否則(x,y)更新為

22、(x+1,y)。 5.當直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。,改進2：用2ex來替換e e初=-x， 每走一步有e=e+2y。 if (e0) then e=e-2x,e=e+k e=e+y/x x e= x e+ y e=-0.5 2e=-1,算法步驟： 1.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。 2.計算初始值x、y、e=-x、x=x0、y=y0。 3.繪制點(x,y)。 4.e更新為e+2y，判斷e的符號。若e0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-2x；否則(x,y)更新為(x+1,y)。 5.當直線沒有畫完時，重復(fù)步驟3和4。否則結(jié)束。,B

23、resenham畫線算法,BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,dx,dy,e; dx = x1-x0; dy = y1-y0; e = -dx; x=x0; y=y0; for( i=0; i= 0) e = e - 2*dx; y+; ,舉例：用Bresenham方法掃描轉(zhuǎn)換連接兩點P0（0,0）和P1（5,2）的直線段。,x y e e0=-5; dx=5;dy=2 0 0 -1 1 0 3 (-7 ) 2 1 -3 3 1 1(-9) 4 2 -5 5 2 -1,Bresenham算法,3)一般B

24、resenham算法 要使上面的Bresenham算法適用于一般直線，只需對以下2點作出改造：,a、當直線的斜率|k|1時，改成y的增量總是1，再用Bresenham誤差判別式確定x變量是否需要增加1；,b、x或y的增量可能是“+1”或“-1”，視直線所在的象限決定。,圓的一般特征 不失一般性，假設(shè)圓的圓心位于坐標原點（如果圓心不在原點，可以通過坐標平移使其與原點重合），半徑為R。以原點為圓心的圓C有四條對稱軸：x=0,y=0,x=y和x=-y。若已知圓弧上一點P1C（x, y），利用其對稱性便可以得到關(guān)于四條對稱軸的其它7個點，即： P2C（x,y）， P3C（x, y）， P4C（x,y）

25、， P5C（y，x）， P6C（y，x）， P7C（y，x）， P8C（y，x）。 這種性質(zhì)稱為八對稱性。因此，只要掃描轉(zhuǎn)換八分之一圓弧，就可以通過圓弧的八對稱性得到整個圓 為了方便起見，考慮位于第一象限的第二個八分之一圓弧,2.2 圓的生成算法,2.2.1 基礎(chǔ)知識,給出圓心坐標(xc, yc)和半徑r，逐點畫出一個圓周 的公式有下列兩種： 直角坐標法 (xxc)2 + (yyc)2 = r2 由上式導(dǎo)出：,當xxc從r到r作加1遞增時，就可以求出對應(yīng)的圓周點的y坐標。 但是這樣求出的圓周上的點是不均勻的，xxc越大，對應(yīng)生成圓周點之間的圓周距離也就越長。因此，所生成的圓不美觀,2.2 圓的

26、生成算法, 極坐標法 x = xc + r cos，y = yc + r sin 當從0到作遞增時，由此式便可求出圓周上均勻分布的360個點的(x, y)坐標 利用圓周坐標的對稱性，此 算法還可以簡化。將圓周分為8 個象限(圖2.3)，只要將第1a象 限中的圓周光柵點求出，其余7 部分圓周就可以通過對稱法則 計算出來,圖2.3 圓心在(0, 0)點圓周 生成時的對稱變換,2.2 圓的生成算法,2.2.2 圓的Bresenham算法,設(shè)圓的半徑為r。先考慮圓心在(0, 0)，并從x=0、y=r 開始的順時針方向的1/8圓周的生成過程。在這種情況下， x每步增加1，從x=0開始，到x=y結(jié)束。即有

27、 xi+1 = xi + 1 相應(yīng)的yi+1則在兩種可能中選擇： yi+1 = yi或者yi+1 = yi1 選擇的原則是考察精確值y是靠近yi 還是靠近yi1(圖2.4)，計算式為 y2 = r2(xi+1)2 d1 = yi2y2 = yi2r2+(xi+1)2 d2 = y2(yi1)2 = r2(xi+1)2(yi1)2,圖2.4 y的位置,2.2 圓的生成算法,令pi=d1d2，并代入d1、d2，則有 pi = 2(xi+1)2 + yi2 + (yi1)22r2 (2.6) pi稱為誤差。如果pi0則yi+1=yi，否則yi+1=yi1。 pi的遞歸式為 pi+1 = pi + 4

28、xi +6+2(yi2+1 yi2) 2(yi+1yi) (2.7) pi的初值由式(2.6)代入xi=0，yi=r而得 p1 = 32r (2.8),2.2 圓的生成算法,根據(jù)上面的推導(dǎo)，圓周生成算法思想如下： 求誤差初值，p1=32r，i=1，畫點(0, r)； 求下一個光柵位置，其中xi+1=xi+1，如果pi0則yi+1=yi， 否則yi+1=yi1； 畫點(xi+1, yi+1)； 計算下一個誤差，如果pi0則pi+1=pi+4xi+6，否則pi+1=pi+4(xiyi)+10； i=i+1，如果x=y則結(jié)束，否則返回步驟2。,圓的Bresenham算法的程序?qū)崿F(xiàn)如下： circle

29、(xc, yc, radius, c) int xc, yc, radius, c; int x, y, p;x=0;y=radius;p=32*radius； while(xy) plot_circle_points(xc,yc,x,y,c); if(p0) p=p+4*x+6; else p=p+4*(xy)+10; y=1; x+=1; if(x=y) plot_circle_points(xc,yc,x,y,c); ,2.2 圓的生成算法,plot_circle_points(xc, yc, x, y, c) int xc, yc, x, y, c; set_pixel(xc+x, y

30、c+y, c); set_pixel(xcx, yc+y, c); set_pixel(xc+x, ycy, c); set_pixel(xcx, ycy, c); set_pixel(xc+y, yc+x, c); set_pixel(xcy, yc+x, c); set_pixel(xc+y, ycx, c); set_pixel(xcy, ycx, c); ,2.2 圓的生成算法,在光柵掃描顯示器中表示一個區(qū)域，僅僅畫出其邊界是不夠的，有時還要填上一定的灰度、色彩 區(qū)域填充區(qū)域填充即給出一個區(qū)域的邊界，要求對邊界范圍內(nèi)的所有像素單元賦予指定的顏色代碼。區(qū)域填充中最常用的是多邊形填色,2.

31、3.1 基礎(chǔ)知識,2.3 區(qū)域填充算法,多邊形的表示方法 頂點表示: 用多邊形的頂點序列來刻劃多邊形。直觀、幾何意義強、占內(nèi)存少；不能直接用于面著色 點陣表示: 用位于多邊形內(nèi)的像素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運用幀緩沖存儲器表示圖形，易于面著色,多邊形填色一個首要的問題，是判斷一個像素是在多邊形內(nèi)還是多邊形外。數(shù)學(xué)上提供的方法是“掃描交點的奇偶數(shù)判斷法” 用線段連接p和多邊形外部某一點，若該線段與多邊形邊界相交的交點數(shù)目為奇數(shù)，則p是多邊形內(nèi)部點，否則為外部點,2.3 區(qū)域填充算法,點是否在內(nèi)部的檢驗,錯判情況 A、B、C點處發(fā)生的錯判 需要加以改進,圖2.5 掃描線與

32、多邊形相交,圖2.6 光柵化后直線變成離散點,填色算法分為兩大類： 掃描線填色(Scan-Line Filling)算法。這類算法 建立在多邊形邊界的矢量形式數(shù)據(jù)之上，可用于程序填 色，也可用于交互填色 種子填色(Seed Filling)算法。這類算法建立在多 邊形邊界的圖像形式數(shù)據(jù)之上，并還需提供多邊形邊界 內(nèi)一點的坐標。所以，它一般只能用于人機交互填色， 而難以用于程序填色,2.3 區(qū)域填充算法,2.3.2 掃描線填色算法,算法的基本思想: 多邊形以n、x_array、y_array 的形式給出，其中，x_array、y_array 中存放著多邊形的n個頂點的x，y坐標 用水平掃描線從上

33、到下掃描由點線段 構(gòu)成的多段定義成的多邊形。每根掃 描線與多邊形各邊產(chǎn)生一系列交點。 這些交點按照x坐標進行排序，將排序 后的交點成對取出，作為兩個端點， 以所需要填的色彩畫水平直線。多邊 形被掃描完畢后，填色也就完成,2.3 區(qū)域填充算法,求交點，即計算該掃描線與多邊形各邊的交點,排序，由于交點不一定由左到右求出，因此將求出的交點按 x 坐標值排序,交點配對，1與2，3與4， ，每對表示一個區(qū)間,區(qū)間填充,上述基本思想中，有幾個問題需要解決或改進： 左、右頂點處理。當以1、2、3的次序畫多邊形外框時，多邊形的左頂點和右頂點如圖2.7中所示的頂點2。它們具有以下性質(zhì)。 左頂點2：y1y2y3

34、其中y1、y2、y3是3個相鄰的頂點的y坐標,圖2.7 多邊形的頂點,當掃描線與多邊形的每個頂點相交時， 會同時產(chǎn)生2個交點。這時，填色就會因 掃描交點的奇偶計數(shù)出錯而出現(xiàn)錯誤。 因此，對所有左、右頂點作如下處理：,2.3 區(qū)域填充算法,左、右頂點的入邊(以該頂點為終點的那條邊，即12邊)之終點刪去 對于左頂點，入邊端點(x1, y1)、(x2, y2)修改為(x1, y1)、(, y21)； 對于右頂點，入邊端點(x1, y1)、(x2, y2)修改為(x1, y1)、(, y2+1)； 其中，即入邊的斜率。 對于多邊形的上頂點(y2y1、y2y3)或下頂點(y2y1、y2y3)，奇偶計數(shù)保

35、持正確,2.3 區(qū)域填充算法,當掃描線與多邊形的頂點相交時， 若共享頂點的兩條邊分別落在掃描線的兩邊，交點只算一個 若共享頂點的兩條邊在掃描線的同一邊，這時交點作為零個或兩個,具體解決方法為： 檢查共享頂點的兩條邊的另外兩個端點的y值，按這兩個y值中大于交點y值的個數(shù)是0、1、2來決定交點數(shù)取0、1、2,可以這樣理解,0,1,1,1,1,0,2,2,2,進行求交點之前，先對每個左右頂點進行預(yù)處理，然后再求交點 方法：如下圖，將Pi-1Pi , PiPi+1兩條邊中位于yi上方的那條邊在Pi處去掉一個單位長,Pi,yi+1,yi,yi-1,Pi-1,x,y, 水平邊處理。水平邊(y1=y2)與水

36、平掃描線重合無法求交點。因此，將水平邊畫出后刪去，不參加求交點及求交點以后的操作, 掃描線與邊的求交點方法采用遞歸算法。以(x1, y1)、(x2, y2)為端點的邊與第i+1條掃描線的交點為, 減少求交計算量，采用活性邊表。對于一根掃描線而言，與之相交的邊只占多邊形全部邊的一部分,每根掃描線與多邊形所有邊求交的操作是一種浪費，需要加以改進,活性邊表(Active List of Side)的采用將多邊形的邊分成兩個子集：與當前掃描線相交的邊的集合，以及與當前掃描線不相交的邊的集合。對后者不必進行求交運算，這樣就提高了算法的效率,2.3 區(qū)域填充算法,活性邊表的構(gòu)成方法是： 1）將經(jīng)過左、右頂

37、點處理及剔除水平邊后的多邊形之各邊按照maxy值排序，存入一個線性表中。表中每一個元素代表一根邊。第一個元素是maxy值最大的邊，最后一個元素是maxy值最小的邊。圖2.3.4 (a)中的多邊形所形成的線性表如（b）所示。其中F點和B點的y值相等，且為全部多邊形的max y的最大值。因此FG, FE, AB, BC等四邊排在表之首。而C點的y值E點的y值，所以CH排在DE前面，余類推。在max y值相等的邊之間，按任意次序排列,2)在上述線性表上加入兩個指針first和last，即形成活性邊表。這兩個指針之間是與當前掃描線相交的邊的集合和已經(jīng)處理完（即掃描完）的邊的集合。這兩者的區(qū)分方法是在處

38、理完的邊上加上記號： y=0。在last指針以后的是尚未與當前掃描線相交的，在first指針以前的是已經(jīng)處理完了的邊。對于圖2.3.4 (a)中掃描線scan1的情況下，圖2.3.4 (b)中列出first, last的位置。如果掃描線由上而下移到了scan2的位置，則活性邊表的first應(yīng)指向AB，last應(yīng)指向CH。每根掃描線只須與位于first, last之間的，而且 y不為 0的邊求交即可。這就縮小了求交的范圍,3）活性邊表中每個元素的內(nèi)容包括： 邊的max y值，記為y_top； 與當前掃描線相交點的x坐標值，記為x_int； 邊的y方向當前總長。初始值為y2-y1。記為 y； 邊的

39、斜率倒數(shù)：x2-x1/y2-y1 ，記為x_change_per_scan。,typedef struct int y_top; float x_int; int delta_y float x_change_per_scan; EACH_ENTRY;,4）活性邊在每根掃描線掃描之后刷新。刷新的內(nèi)容有2項： 調(diào)整first和last指針之間的參加求交的邊元素之值： y= y-1; x_int = x_int - x_change_per_scan; 調(diào)整first和last指針，以便讓新邊進入激活范圍，處理完的邊退出激活范圍： 當first所指邊的 y=0時，first=first+1； 當l

40、ast所指的下一條邊的y_top大于下一條掃描線的y值時，last=last+1。,掃描線填色程序 程序2.3.1示出掃描線填色算法的程序。主程序名為fill_area(count, x, y)，其中參數(shù)x, y是兩個一維數(shù)組，存放多邊形頂點（共count個）的x和y坐標。它調(diào)用8個子程序，彼此的調(diào)用關(guān)系如圖2.3.5所示。各子程序的功能為：,各子程序的功能：,1、sort_on_bigger_y子程序的主要功能是按照輸入的多邊形，建立起活性邊表 操作步驟是：對每條邊加以判斷：如非水平邊則調(diào)用put_in_side_list子程序放入活性邊來；如是水平邊則直接畫出 2、put_in_sides

41、_list子程序的主要功能是將一條邊存入活性邊表之內(nèi) 操作步驟是：對該邊判別是否左頂點或右頂點，如果將入邊之終點刪去，按照y_top的大小在活性邊表中找到該點的合適位置，在該邊的位置中填入數(shù)據(jù) 3、update_first_and_last子程序的主要功能是刷新活性邊表的first和last兩根指針的所指位置，以保證指針指出激活邊的范圍,4、process_x_intersections子程序的主要功能是對活性邊表中的激活邊（即位于first和last之間的，并且 y 不為0的邊）按照x_int的大小排序 操作步驟是：從first到last，對每一根y不為 0的邊，調(diào)用sort_on_x子程序

42、排入活性邊表中合適位置 5、sort_on_x子程序主要功能是將一條邊sideentry，在活性邊表的first到entry之間按x_int的大小插入合適位置。 操作步驟是：檢查位于entry的邊的x_int是否小于位置entry-1的邊的x_int，如是，調(diào)用swap子程序交換兩條邊的彼此位置 6、swap子程序的主要功能是交換活性邊表中兩條相鄰位置邊的彼此位置,7、draw_lines子程序的主要功能是在一條掃描線位于多邊形內(nèi)的部分，填上指定的色彩 操作步驟是：在活性邊表的激活邊范圍內(nèi)，依次取出y 0兩邊的x_int，作為兩個端點（x1, scan），(x2, scan)，畫一條水平線 8

43、、update_sides_list子程序的主要功能是刷新活性邊表內(nèi)激活邊的值：y=Dy-1 x_int=x_int_x_chang_per_scan；,算法基本步驟： a)建立活性邊表。 b)對每一條水平掃描線，確定激活邊范圍。 c)對每一條水平掃描線，確定它與激活邊交點，并將交點排序。 d)將交點成對取出，畫線填色。 e)調(diào)整更新活性邊表。 f) 掃描線下移，返回b)，直至結(jié)束。,EACH_ENTRY SIDESMAX_POINT; int xMAX_POINT, yMAX_POINT; int side_count, first_s, last_s, scan, bottomscan,

44、x_int_count, r; fill_area(count, x, y) int count, x , y ; sort_on_bigger_y(count); first_s=1; last_s=1; for (scan=sides1.y_top; scanbottomscan ?; scan - -) up date_first_and_last(count, scan); process_x_intersections(scan, first_s, last_s); draw_lines (scan, x_int_count, first_s); update-_sides_list

45、 ( ); ,typedef struct int y_top; float x_int; int delta_y; floaat x_change_per_scan; EACH_ENTRY;,程序代碼,void put_in_sides_list(entry, x1, y1, x2, y2, next_y); int entry, x1, y1, x2, y2, next_y; int maxy; float x2_temp, x_change_temp; x_change_temp = (float) (x2-x1) / (float) (y2-y1); x2_temp =x2; /*以下

46、為退縮一點操作. */ if (y2y1) ,/* 以下為插入活性表操作. */ maxy = (y1 y2)? y1: y2; while ( entry 1) ,void sort_on_bigger_y(n) int n; int k, x1, y1; side_count=0; y1=yn; x1=xn; bottomscan=yn; for (k=1; kn+1; k+) if (y1 ! =yk) side_count +; put_in_sides_list(side_count, x1, y1, xk, yk); else move (short)x1, (short)y1);

47、 line(short)xk, (short)y1, status); if (yk bottomscan) bottomscan=yk; y1=yk; x1=xk; ,void update_first_and_last(count, scan) int count, scan; while(sideslast_s+1. y_top=scan) ,void swap(x, y) EACH_ENTRY x, y; int i_temp; float f_temp; i_temp=x.y_top; x.y_top=y.y_top; y.y_top=i_temp; f_temp=x.x_int;

48、x.x_int=y.x_int; y.x_int=f_temp; i_temp=x.delta_y; x.delta=y.delta_y; y.delta_y=i_temp; f_temp=x.x_change_per_scan; x. x_change_per_scan=y. x_change_per_scan; y.x. change_per_scan=f_temp; ,void sort_on_x(entry, first_s) int entry, first_s; while(entry first_s) ,void process_x_intersections(scan, fir

49、st_s, last_s) int scan, first_s, last_s; int k; x_int_cout=0; for(k=first_s; k0) x_int_count +; sort_on_x(k, first_s); ,void draw_lines(scan, x_int_count, index) int scan, x_int_count, index; int k, x, x1, x2; for (k=1; k (int) (x_int_count/2+1.5); k+) while(sidesindex. delta_y = = 0) index +; x1=(i

50、nt)(sidesindex. x_int +0.5); index +; while(sidesindex.delta_y = = 0) index +; x2 = (int) (sides index. x_int +0.5); move(short)x1, (short)scan); line(short)x2, (short)scan, status); index +; ,void update_sides_list( ) int k; for (k=first_s; k0) sidesk.delta_y - -; sidesk. x_int - = sidesk. x_change

51、_per_scan; ,種子填色又稱邊界填色(Boundary Filling)。 它的功能是，給出多邊形光柵化后的邊界位置及 邊界色代碼boundary_color，以及多邊形內(nèi)的一 點(x, y)位置，要求將顏色fill_color填滿多邊形,2.3.3 種子填色算法,2.3 區(qū)域填充算法,基本思想 指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程 種子填充算法要求區(qū)域是連通的,算法要求區(qū)域是連通的 連通性 4連通、8連通 4連通： 從區(qū)域內(nèi)任意一點出發(fā)， 可通過上、下、左、右 四個方向到達區(qū)域內(nèi)的任意象素 8連通 從區(qū)域內(nèi)任意一點出發(fā)， 可通過上、下、左、右、左上、 左下

52、、右上、右下八個方向 到達區(qū)域內(nèi)的任意象素,2.3 區(qū)域填充算法,圖2.10 四鄰法和八鄰法種子填色,2.3 區(qū)域填充算法,void seed_filling (int x,int y,int, fillcolor,int boundarycolor) int c; c = inquire_color(x,y); if(c!= fillcolor ,算法步驟： 1.初始化：種子像素入棧，當棧非空時，重復(fù)2 4的步驟 2.棧頂像素出棧 3.將出棧像素置為多邊形顏色 4.按左、上、右、下順序依次檢查與出棧像素相鄰的四個像素，若其中某個像素不在邊界上且未置成多邊形色，則該像素入棧 5.當堆棧為空時，

53、算法終止,填充算法演示,缺點？,種子填充特點： 算法簡單，可以用于填充帶有內(nèi)孔的區(qū)域 像素可能重復(fù)入棧，降低了算法效率 存儲空間開銷較大,練習(xí)題,如圖所示的多邊形，若采用改進的有效邊表算法進行填充，試寫出該多邊形的活性邊表 以及first、 last指針的位置。,P1P2 P1P0 P0P6 P5P6 P2P3 P4P3 P4P5,first,next,藍色掃描線指針位置：,P1P2 P1P0 P0P6 P5P6 P2P3 P4P3 P4P5,first,next,紅色掃描線指針位置：,在下圖中，待填充的區(qū)域內(nèi)部由標有數(shù)字的像素組成。設(shè)1號像素為初始種子，按“右上左下”順序考察四鄰域。請寫出種

54、子填充算法的填充次序。,1,4 6 11 2,9 5 3 6 11 2,8 12 5 3 6 11 2,5 12 5 3 6 11 2,7 6 4 12 5 3 6 11 2,6 4 12 5 3 6 11 2,10 1 4 12 5 3 6 11 2,11 1 4 12 5 3 6 11 2,1 4 12 5 3 6 11 2,2 4 12 5 3 6 11 2,3 4 12 5 3 6 11 2,4 12 5 3 6 11 2,12 5 3 6 11 2,5 3 6 11 2,3 6 11 2,6 11 2,11 2,2,字符指數(shù)字、字母、漢字等符號 計算機中字符由一個數(shù)字編碼唯一標識 “

55、美國信息交換用標準代碼集”簡稱ASCII碼。它是用7位二進制數(shù)進行編碼表示128個字符，用一個字節(jié)表示 漢字編碼的國家標準字符集。每個符號由一個區(qū)碼和一個位碼（2字節(jié)）共同標識,2.4 字符的生成,點陣字符:每個字符由一個位圖表示 矢量字符:記錄字符的筆畫信息,1,1,1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,點陣字符,點陣字庫中的位圖表示,矢量輪廓字符,例子,特點： 點陣字符：存儲量大，易

56、于顯示 矢量字符：存儲量小，美觀，變換方便需要光柵化后才能顯示,2.4.1 點陣式字符,點陣式字符將字符形狀表示為一個矩形點陣，由點陣中點的不 同值表達字符的形狀,每個字符都定義成一個稱為掩膜的矩陣。矩陣中的元素都是一位二進制數(shù)，當該位為1時，表示字符的筆劃經(jīng)過此位，對應(yīng)于此位的象素應(yīng)置為字符顏色；當該位為0時，表示字符的筆劃不經(jīng)過此位，對應(yīng)于此位的象素應(yīng)置為背景色或不改變,2.4 字符的生成,0000000000000000 0001111111110000 0001100000011000 0001100000001100 0001100000001100 0001100000011000

57、 0001100001100000 0001111111000000 0001100000000000 0001100000000000 0001100000000000 0001100000000000 0000000000000000 0000000000000000,當該位為1時，表示字符的筆劃經(jīng)過此位 當該位為0時，表示字符的筆劃不經(jīng)過此位,P-DotText,掩膜的矩陣(1616),使用點陣式字符時，需將字庫中的矩形點陣復(fù)制到緩沖器中指 定的單元中去。在復(fù)制過程中，可以施加變換，以獲得簡單的變化。 圖2.11(b)(d)列出了以字母P為原型的一些變化例子,圖2.11 點陣式字符及其變

58、化,相應(yīng)的變換算法是： 1、變成粗體字。算法是：當字符原型中每個象素被寫入幀緩存寄存器的指定位置xi, yi時，同時被寫入xi+1, yi 2、旋轉(zhuǎn)90 。算法是：把字符原型中每個象素的x, y坐標彼此交換，并使y值改變符號后，再寫入幀緩存寄存器的指定位置 3、斜體字。算法是：從底到頂逐行拷貝字符，每隔n行，左移一單元,點陣式字符是主要的文字表示形式 常用的點陣大小有 5 7、7 9、8 8、16 16等等 當點陣變大時，字型可以做得非常漂亮 點陣式字符字形美觀，但旋轉(zhuǎn)比較困難、占用的存儲空間較大,2.4.2 矢量式字符,矢量式字符將字符表達為點坐標的序列，相鄰兩點表示一條矢量，字符的形狀便由矢量序列刻畫。圖2.12示出用矢量式表示的字符“B”?！癇”是由頂點序列a, b, c, d, e, f, e, g, h,