計算機(jī)圖形學(xué)基本光柵圖形算法.ppt

1、第三章 基本光柵圖形算法,本章內(nèi)容,3,3.2 直線的掃描轉(zhuǎn)換,圖形圖像是由屏幕上不同亮度不同顏色的光點(diǎn)（像素）組成。在光柵顯示器的熒光屏上生成一個對象，實(shí)質(zhì)上是往幀緩存寄存器的相應(yīng)單元中填入數(shù)據(jù)。所以 對直線進(jìn)行光柵化的時候，只能在顯示器所給定的有限個像素組成的點(diǎn)陣中確定最佳逼近于該直線的一組像素，用這些像素表示該直線。所以 生成直線的主要工作是：快速找出距離直線最近的網(wǎng)格點(diǎn)，用這些網(wǎng)格點(diǎn)對應(yīng)的像素表示該直線。,4,像素逼近直線示意圖,5,3.2.1 基本增量算法,設(shè)直線 滿足 ，由于直線的斜率小于等于1，所以，該直線的掃描轉(zhuǎn)換可從最左端開始， 每次遞增一個單位，對每個 ，相應(yīng)的有 ，則,所

2、以， 每增加一個單位， 只需加上一個 ，這樣就去掉了乘法運(yùn)算，提高了算法效率。在該算法中，直線上的所有點(diǎn)的 和 值可由前一點(diǎn)的值加一個基本增量得到，所以該算法稱為基本增量算法。,3.2.1 基本增量算法(DDA-digital differential analyzer),1、基本思想：,6,3.2.1 基本增量算法,上述討論只適合 的情況，當(dāng) 時，只需將 和 的角色互換，即 每次增加一個單位， 每次增加 。,基本增量算法也叫數(shù)字微分分析器算法（Digital Differential Analyzer，DDA）。DDA是用數(shù)值方法求解微分方程的一種設(shè)備，即根據(jù) 111和 的一階導(dǎo)數(shù)，在 和

3、方向上漸進(jìn)地以小步長移動，由此產(chǎn)生連續(xù)的像素坐標(biāo) 。,7,2、直線的表示： 設(shè)直線的起點(diǎn)坐標(biāo)為(xs，ys)，終點(diǎn)坐標(biāo)為(xe, ye)，令xxe- xs，y ye- ys，則直線參數(shù)方程為,目標(biāo)：能快速地求出能很好地表示直線的像素,第 步時,(3.1),8,3、提高速度的方法：,乘法用加法實(shí)現(xiàn)，每一個點(diǎn)坐標(biāo)都可以由前一個坐標(biāo)變化一個增量得到。 設(shè)(xi,yi)是第i 步得的直線上的點(diǎn)，則直線上第個i+1 點(diǎn)是(xi+1,yi+1)，其中 當(dāng)x y0，即直線斜率小于1，應(yīng)使x方向每次增加1，y方向最多增加1，此時取t=1/x； 同理,當(dāng)yx0,直線斜率大于1，取t=1/y，所以,(3.2),令

4、 ，將參數(shù)區(qū)間0，1分為 等份，即 每次的增量為 。,9,下圖中，用公式（3.2）求得的直線 上的點(diǎn)用空心圓表示，但顯示時要用像素來表示，即采用四舍五入的辦法得到最靠近空心圓點(diǎn)的像素，用這些像素（下圖中的實(shí)心圓點(diǎn)）來表示直線。,10,圖中黑點(diǎn)表示用DDA法生成的直線,4、直線的DDA算法程序,void dda(Graphics g, int x1, int x2, int y1, int y2) int k; float x, y, dx, dy; k = Math.abs(x2-x1); if (Math.abs(y2-y1)k) k = Math.abs(y2-y1); dx = (flo

5、at)(x2-x1)/k; dy = (float)(y2-y1)/k; /變化的增量 x=(float)(x1); y=(float)(y1); for (int i=0;ik;i+) g.drawLine(int)(x+.5f),(int)(y+.5f),(int)(x+.5f), (int)(y+.5f); x = x+dx; y = y+dy; / end DDA,完成四舍五入,11,設(shè)給定直線的起點(diǎn)坐標(biāo)為(0，0)，終點(diǎn)坐標(biāo)為(9，6)，則上述DDA算法畫出的直線如下圖所示。,12,一般來說， 不一定是整數(shù)，所以 也不一定是整數(shù)，因此要用靠近該點(diǎn)最近的網(wǎng)格點(diǎn) 來近似。由于取整計算量較

6、大，為了提高效率，Bresenham算法用下面的方法來避免使用取整運(yùn)算。,3.2.2 Bresenham算法,13,算法思想：,14,通過遞推的方式，高效地計算點(diǎn)序列和 ，由圖3.4可得,(3.5),由式（3.3）（3.5）可得,15,式（3.5）和（3.6）是根據(jù)圖3.4所示的情況推出的，容易驗(yàn)證，式（3.5）和（3.6）對圖3.5所示的兩種情況也成立。,圖3.5 的幾何意義的其他兩種情況,16,由式（3.3）和（3.4）可得,假設(shè)直線段起始點(diǎn)的坐標(biāo)分量 和 均為整數(shù)，則有,m = (double)dy/(double)dx； e = m0.5； for(i = 0; i =0) y = y

7、+1； e = e1; x = x+1；e = e+m; ,17,void bresenham(Graphics g, int xs, int ys, int xe, int ye) int dx = xe-xs; int dy = ye-ys; int e = 2*dy-dx; int x = xs; int y = ys; for(int i = 0;i =0) y=y+1; e=e-2*dx; x=x+1; e=e+2*dy; ,18,3.3 圓的掃描轉(zhuǎn)換,1、基本原理： 假設(shè)已選取Pi-1為第i-1個像素，則如果Pi-1在圓內(nèi)，就要向圓外方向走一步，若Pi-1在圓外就要向圓內(nèi)走一步。若

8、Pi-1在圓上，則可以向圓內(nèi)走一步，也可以向圓外走。,3.3.1 正負(fù)法,這樣用于表示圓弧的點(diǎn)均在理想圓弧附近且時正時負(fù)，因此稱為,正負(fù)法。由于這種方法每走完一步，都要比較當(dāng)前位置的函數(shù)值，以決定下一步的走向，因而也稱為逐點(diǎn)比較法。,19,2、正負(fù)法的具體實(shí)現(xiàn),1）圓的表示：設(shè)圓的圓心為(0,0),半徑為R，則圓的方程為： F(x,y)=x2+y2R2=0,如何判斷一個點(diǎn)和圓的內(nèi)外關(guān)系,當(dāng)點(diǎn)(x,y)在圓內(nèi)時，F(xiàn)(x,y)0； 當(dāng)點(diǎn)(x,y)在圓上時，F(xiàn)(x,y)=0。,20,2）實(shí)現(xiàn)步驟,第1步：x0=0，y0=R 第2步： 求得Pi(xi,yi)后找點(diǎn)Pi+1的原則為：,當(dāng)Pi在圓內(nèi)時(F

9、(xi,yi)0)， 要向右走一步得Pi+1，這是向圓外方 向走去。取xi+1= xi+1, yi+1= yi,Pi+1,當(dāng)Pi在圓外時(F(xi,yi)0)， 要向下走一步得Pi+1，這是向圓內(nèi)方向走去，取xi+1= xi, yi+1= yi-1,Pi+1,用來表示圓弧的點(diǎn)均在圓弧附近且 F(xi,yi)時正時負(fù),x,21,當(dāng) 時，,假設(shè)已經(jīng)算出F(xi,yi)，如何計算F(xi+1,yi+1)？,由上可知 。如果 的值已算出，計算 時可分為兩種情況：,(3.9),當(dāng) 時，,(3.10),由式（3.9）和式 (3.10) 知 ，,22,void pnarc(Graphics g,int ra

10、dius) int x,y,f; x = 0; y = 0+radius; f = 0; while (y 0) g.drawLine(x, y, x, y); if (f 0) f = f 2*y + 1; y-; else f = f + 2*x + 1; x+; if(y = 0) g.drawLine(x, y, x, y); ,23,3.3.2 Bresenham 算法,假設(shè)圓心(0,0)為原點(diǎn)， 考慮AB弧的畫法，顯示一 個整圓時，只要在顯示AB 上任一點(diǎn)(x,y)時，同時顯 示在圓周上其它七個對稱 點(diǎn) (y,x), (y,-x),(x,-y),(-x,-y), (-y,-x),(

11、-y,x),(-x,y)。,7個對稱點(diǎn),24,1、基本原理,考慮AB弧段，x每步增加1，從 x=0開始，到x=y結(jié)束。 即有： xi+1=xi+1 相應(yīng)的yi+1則在兩種 可能中選擇：yi+1=yi，或者 yi+1=yi-1。 所以 選擇的原則是確定這兩個點(diǎn)哪一 個更接近于圓弧。,25,2、Bresenham的具體實(shí)現(xiàn),1）令D(P)=(x2+y2)-R2，表示點(diǎn)P 到原點(diǎn)的距離平方與圓的半徑的 平方之差。令：,當(dāng)di=0時， 點(diǎn)Hi和Li距弧AB的距離相等 當(dāng)di|D(Li)|，取Li來顯示弧AB。,di=D(Hi)+D(Li),26,2）di遞推公式,設(shè)已選中的點(diǎn)Pi-1=(xi-1,yi

12、-1)，則Hi和Li點(diǎn)的坐標(biāo)分別 為(xi,yi-1)和(xi,yi-11), Hi+1和Li+1的坐標(biāo)分別為(xi+1,yi) 和(xi+1,yi 1)。 因?yàn)?x0=0, y0=R, x1=x0+1，所以 d1=D(H1)+D(L1)=(12+y20-R2)+(12+(y0-1)2-R2) =3-2y0=3-2R di=(x2i+y2i-1-R2)+(x2i+(yi-1-1)2-R2) =2x2i+2y2i-1-2yi-1-2R2+1 di+1=(xi+1)2+y2i-R2+(xi+1)2+(yi-1)2-R2 =2x2i+4xi+2y2i-2yi-2R2+3,27,di=2x2i+2y

13、2i-1-2yi-1-2R2+1 (3.13) di+1=2x2i+4xi+2y2i-2yi-2R2+3 (3.14) 當(dāng)di0時,點(diǎn)Hi被選中, xi= xi-1+1， yi=yi-1，由 (3.13)- (3.14) 得 di+1= di+ 4xi+2= di+ 4xi-1+6 (3.15) 當(dāng)di0時,點(diǎn)Li被選中, xi= xi-1+1， yi= yi-1-1， 由(3.13) -(3.14)得 di+1=di+4xi-4yi-1+6=di+4(xi-1-yi-1)+10 (3.16),28,void bresenham_arc(Graphics g,int radius) int x

14、,y,d; x = 0; y = radius; d = 3-2*radius; while (x y) g.drawLine(x, y, x, y); if(d0) d=d+4*x+6; else d=d+4*(x-y)+10; y-; x+; if(x = y) g.drawLine(x,y,x,y); ,29,按一定方式計算給定圓弧軌跡上的一系列頂點(diǎn)，然后用連接相鄰點(diǎn)的一系列直線段來逼近圓弧。,用正多邊形迫近圓弧法,設(shè)圓弧所在圓的半徑為R，圓弧的起始角和終止角分別為 和 ，把圓弧分割成 份，則相鄰兩個頂點(diǎn)之間的夾角為 。設(shè)頂點(diǎn)序列的第 個點(diǎn)為 ， 為該點(diǎn)的幅角。則下一個頂點(diǎn) 的坐標(biāo)為,或

15、表示為矩陣形式,3.3.3 圓的多邊形迫近法,30,設(shè)橢圓的中心在原點(diǎn)，長短軸分別為a 和b，且平行于坐標(biāo)柚，則該橢圓的參數(shù)方程為,，,設(shè)頂點(diǎn)序列的第i個頂點(diǎn)為 ,則下一個頂點(diǎn) 的坐標(biāo)應(yīng)滿足,由此可得,其中,31,3.4.1 多邊形的掃描轉(zhuǎn)換,1、表示方法：頂點(diǎn)表示和點(diǎn)陣表示,1）頂點(diǎn)表示是用多邊形的頂點(diǎn)的序列來描述多邊形，該表示幾何意義強(qiáng)、占內(nèi)存少，但它不能直觀地說明哪些像素在多邊形內(nèi)。,2）點(diǎn)陣表示是用位于多邊形內(nèi)的像素的集合來描述多邊形，該方法雖然沒有多邊形的幾何信息，但具有面著色所需要的圖像表示形式。,3.4 多邊形的掃描轉(zhuǎn)換,32,3.4.2 掃描線算法,特點(diǎn)：充分利用了相鄰像素之間

16、的連續(xù)性，避免對像素的逐 點(diǎn)判斷和反復(fù)求交運(yùn)算，減少了計算量，提高了算法速度。,基本概念： 1）掃描線的連續(xù)性 2）邊的連續(xù)性 3）奇點(diǎn),先求出掃描線與多邊形邊的交點(diǎn)，利用掃描線的連續(xù)性求出多邊形與掃描線相交的連續(xù)區(qū)域，然后利用多邊形邊的連續(xù)性，求出下一條掃描線與多邊形的交點(diǎn)，對所有掃描線由下到上依次處理。,掃描線算法是按掃描線的順序計算出掃描線與多邊形的相 交區(qū)間，然后用要求的顏色填充這些區(qū)間內(nèi)的像素。,33,設(shè)多邊形P的頂點(diǎn) ，將各頂點(diǎn) 的縱坐標(biāo) 按遞減順序排列 , 即 設(shè)當(dāng)前掃描線 ， ， 與多邊形P的邊 的交點(diǎn)記為 。設(shè) 為 與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，該序列稱為交點(diǎn)序列。,(3

17、.21),當(dāng)知道一條掃描線上一點(diǎn)與多邊形的內(nèi)外關(guān)系時，即可確定該掃描線上所有點(diǎn)與多邊形之間的內(nèi)外關(guān)系。,34,交點(diǎn)序列具有以下性質(zhì)：1) 交點(diǎn)個數(shù) l 是偶數(shù)； 2) 掃描線上的區(qū)間 l1位于多邊形P內(nèi)（圖3.13中的實(shí)線段部分），其余區(qū)間都在P 外（圖3.13中的虛線段部分），兩類區(qū)間沿掃描線相間排列。這些性質(zhì)就稱為掃描線的連續(xù)性。,35,掃描線的連續(xù)性知，序列（3.21）和（3.22）的點(diǎn)滿足以下關(guān)系： （1）兩序列元素的個數(shù)相等，即 ； （2）點(diǎn)（ ）與（ ）位于多邊形P的同一邊 上（見圖3.14），所以 可由下式計算 (3.23) 以上性質(zhì)稱為邊的連續(xù)性。,若 , 成立，則掃描線 與掃

18、描線 和多邊形P相同的邊相交，由,36,但當(dāng)掃描線與多邊形P 的邊界的交點(diǎn)恰好是P的頂點(diǎn)時（該交點(diǎn)稱為奇點(diǎn)），必須按不同的情況區(qū)別對待。,上述兩種形式的連續(xù)性都基于一個幾何事實(shí)：每一條掃描線與多邊形P 的邊界的交點(diǎn)個數(shù)都是偶數(shù)（包括零）。,設(shè)多邊形P 的頂點(diǎn)為 這些頂點(diǎn)可分為兩類：極值點(diǎn)和非極值點(diǎn)。如果 ，則稱頂點(diǎn) 為極值點(diǎn)（如圖3.15中的 ）；否則稱為非極值點(diǎn)（如圖3.15中的 ）。,37,為使每一條掃描線與多邊形P 的邊界的交點(diǎn)個數(shù)始終為偶數(shù)，規(guī)定當(dāng)奇點(diǎn)是多邊形P 的極值點(diǎn)時，該點(diǎn)按兩個交點(diǎn)計算，否則按一個交點(diǎn)計算。,實(shí)際計算中，可如下處理非極值點(diǎn)：若 是非極值點(diǎn)，則將 , 兩邊中位于掃

19、描線 上方的那條邊在 處截去一個單位長，這樣就能保證掃描線 只和 ， 中的一邊相交，只有一個交點(diǎn)。,38,對于每一條掃描線，多邊形的填充過程可分為以下4步： 計算掃描線與多邊形各邊的交點(diǎn)，設(shè)交點(diǎn)個數(shù)為n； 把所有的交點(diǎn)按x值遞增的順序進(jìn)行排列； 將排序后的第1個與第2個交點(diǎn)，第3個與第4個交點(diǎn)， 第n-1個與第n個交點(diǎn)配對，每對交點(diǎn)就代表掃描 線與多邊形的一個相交區(qū)間； 把相交區(qū)間內(nèi)的像素置成多邊形的顏色，相交區(qū)間外 的像素置成背景色。,39,與當(dāng)前掃描線相交的邊稱為活性邊。把活性邊與掃描線的交點(diǎn)按x坐標(biāo)遞增的順序放在一個鏈表中，該鏈表就稱為活性邊表（Active Edge List, AEL

20、）。,設(shè)多邊形某一條邊的方程為 ，當(dāng)前掃描線 與該邊的交點(diǎn)坐標(biāo)為 ，則下一條掃描線 與該邊的交點(diǎn) 不需要重新計算，只要加一個增量 即可。因?yàn)榇藭r有,其中 為常數(shù)，并規(guī)定 時， 。,40,綜上，AEL中的節(jié)點(diǎn)應(yīng)由如下四個域組成： :邊的上端點(diǎn)的y坐標(biāo)，即與該邊相交的最高掃描線號。 x :邊與掃描線的交點(diǎn)的x坐標(biāo)。 :從當(dāng)前掃描線到下一條掃描線間的x坐標(biāo)的增量，即邊的斜率的倒數(shù)。 Next :指向下一條邊的指針。,為方便活性邊表的建立與更新，還要為每一條掃描線建立一個新邊表（New Edge List, NEL），存放在該掃描線上第一次出現(xiàn)的邊。也就是說，如果某邊的較低端點(diǎn)為 ，則該邊放在掃描線

21、的新邊表中。,注意：水平邊不放到任何掃描線的NEL中，即水平邊不參加分類。NEL中的節(jié)點(diǎn)結(jié)構(gòu)與AEL相同，只是 x 在這里不再表示邊與掃描線的交點(diǎn)，而是表示該邊較低端點(diǎn)的 x 坐標(biāo)值。,41,圖3.18和3.19是圖3.17中多邊形 的新邊表NEL和活性邊表AEL。在左圖中 表示邊 ，各頂點(diǎn)為 P0P1P6=(2,5)(2,10)(9,6) (16,9)(16,4)(12,2)(7,2) 其中， 是非極值點(diǎn)，在分類前已對邊 作了預(yù)處理，即分別在 處把它們截去一個單位長，這樣保證掃描線 只和 兩邊中的一邊相交，求得一個交點(diǎn)， 是水平邊，不參加分類。,42,圖3.18 新邊表NEL,43,3.4.

22、3 邊緣填充算法,1、特點(diǎn)：采用對圖像進(jìn)行逐位求補(bǔ)的方法，免去對邊排序 的工作量。,2、預(yù)備知識： 假設(shè)某像素的顏色是C，對該像素做偶數(shù)次求補(bǔ)運(yùn)算 后，其顏色還是C ；做奇數(shù)次求補(bǔ)運(yùn)算后，其顏色變?yōu)?C。在光柵圖形中，如某區(qū)域已著上值為M的某種顏色，則上 述求補(bǔ)運(yùn)算的結(jié)果是：對區(qū)域作偶數(shù)次求反運(yùn)算后，該區(qū)域 的顏色不變；作奇數(shù)次求反運(yùn)算后，該區(qū)域的顏色則變成值 為M的顏色。,44,對多邊形 P 的每一非水平邊 （i=0,1,n）上的各像素進(jìn)行向右求補(bǔ)運(yùn)算，當(dāng)相對于所有邊的求補(bǔ)運(yùn)算都完成后，多邊形的掃描轉(zhuǎn)換也隨之完成。圖3.20a為給定的多邊形；b為對區(qū)域賦初值；c、d、e和f表示逐邊向右求補(bǔ)。

23、,圖3.20 邊緣填充算法的過程,3、邊緣填充算法的實(shí)現(xiàn),45,3.4.4 邊界標(biāo)志算法,1、基本原理： 首先用一種特殊的顏色在幀緩沖器中將多邊形的邊界（水平邊的部分邊界除外）勾畫出來。然后再把位于多邊形內(nèi)的各個像素著上所需的顏色。,2、算法具體實(shí)現(xiàn)步驟： 步驟1：以值為boundary_color 的特殊顏色勾畫多邊形P的邊界。設(shè)多邊形頂點(diǎn)為Pi= (xi, yi),0in， xi, yi均為整數(shù)；置Pn+1=P0。每一條掃描線上著上這種特殊顏色的點(diǎn)的個數(shù)必定是偶數(shù)(包括零)。,46,int red=Color.red.getRGB(); public Image boundary() Im

24、age image; /定義Image對象 for ( i=0; i0) x=pi.x; else x=pi+1.x; ymax=(Math.max(pi.y,pi+1.y); ymin=(Math.min(pi.y,pi+1.y); for ( y=ymin+1; y=ymax; y+ ) x=(int)(x+dx+.5); if(pixelsy*w+x=red) pixelsy*w+x+1=red; else pixelsy*w+x=red; ImageProducer ip = new MemoryImageSource(w,h,pixels,0,w); image = createIm

25、age(ip); return image; ,47,/maxx、maxy、minx、miny是獲得的多邊形最小矩形包圍盒邊界值 public Image interior() Image image; int maxx = 150, minx = 20, maxy = 120, miny = 20, l; int in_flag；/多邊形內(nèi)部標(biāo)志變量 for ( y=miny; y=maxy; y+ ) in_flag=0; for ( x=minx; xmaxx; x+ ) l=pixelsy*w+x; if (l=red) if(in_flag=0) in_flag=1; else in

26、_flag=0; if(in_flag=1) pixelsy*w+x=red; ImageProducer ip=new MemoryImageSource(w,h,pixels,0,w); image=createImage(ip); return image; ,步驟2：設(shè)in_flag是一布爾變量。對每一條掃描線從左到右進(jìn)行搜索，如果當(dāng)前像素位于多邊形P內(nèi)，則in_flag=true，需要填上值為polygon_color的顏色；否則該像素在多邊形P外，需要填上值為background_color的顏色。,48,3、邊界標(biāo)志算法實(shí)例,P2(9,6),P0(2,5),P1(2,11),P3

27、(15,9),P4(15,3),P5(12,1),P6(7,1),49,實(shí)例最終結(jié)果,50,3.5 區(qū)域填充,區(qū)域是指已經(jīng)表示成點(diǎn)陣形式的像素集 合。在光柵圖形中，區(qū)域可采用內(nèi)點(diǎn)表示 和邊界表示兩種形式進(jìn)行描述。,1、內(nèi)點(diǎn)表示法：把位于給定區(qū)域內(nèi)的所有像素一一列舉出來的方法稱為內(nèi)點(diǎn)表示法。,2、邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。,3.5.1 區(qū)域的表示和類型,51,1）4連通的區(qū)域: 取區(qū)域內(nèi)任意兩 點(diǎn)，在該區(qū)域內(nèi)若從其中一點(diǎn)出發(fā) 通過上、下、左、右四種運(yùn)動可到 達(dá)另一點(diǎn)。,2）8連通的區(qū)域: 取區(qū)域內(nèi)任意兩 點(diǎn)，若從其中任一點(diǎn)出發(fā)，在該 區(qū)域內(nèi)通過沿水平

28、方向、垂直方向 和對角線方向的八種運(yùn)動可到達(dá)另 一點(diǎn)。,3、區(qū)域的連通性,52,3） 4連通區(qū)域也可理解成8連通區(qū)域，即4連通能達(dá)到的8連通肯定能達(dá)到，4連通只是8連通的一種特殊情況。,連通不是指邊界而是邊界內(nèi)的區(qū)域這里是X圍起來的區(qū)域,號是區(qū)域 X是邊界,8連通而 非4連通 的地方,圖3.26 內(nèi)點(diǎn)表示的八連通區(qū)域,圖3.27 邊界表示的八連通區(qū)域,53,但是兩者的邊界不盡相同。如果圖中標(biāo)有號的像素組成的區(qū)域作為4連通區(qū)域，則其邊界由圖中的標(biāo)有號的像素組成。如果將該區(qū)域作為8連通的區(qū)域，則其邊界由圖中標(biāo)有號和號的兩種像素組成。,圖3.28 四連通區(qū)域與八連通區(qū)域的不同邊界,因?yàn)槿绻麉^(qū)域是8連

29、通的，邊界不能將區(qū)域有效封堵，X的位置和區(qū)域也是連通的。,54,設(shè)（x, y）是內(nèi)點(diǎn)表示的一區(qū)域 G 內(nèi)的一點(diǎn)，old_color是G 的原色。先?。▁, y）點(diǎn)為種子點(diǎn)，測試其顏色，若等于old_color，說明是區(qū)域內(nèi),一點(diǎn)，則將其置為新的顏色new_color，否則說明該點(diǎn)不在區(qū)域 G 內(nèi)，則停止填充；然后將該點(diǎn)周圍的四個點(diǎn)（四連通）或八個點(diǎn)（八連通）作為新的種子點(diǎn)進(jìn)行同樣的處理，通過這種擴(kuò)散完成對整個區(qū)域的填充。顯然，這一過程是用遞歸實(shí)現(xiàn)的。,3.5.2 遞歸算法,55,public void flood_fill_8(int pixels,int x,int y,int old_co

30、lor,int new_color) if(x0 ,56,3.5.3 掃描線種子填充算法,1、基本思想： 從給定的種子點(diǎn)開始，先填充當(dāng)前掃描線上 種子點(diǎn)所在的一區(qū)段，然后確定與這一段相鄰的 上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段（需要填充 的區(qū)間），從這些區(qū)間上各取一個種子點(diǎn)依次把 它們存起來，作為下次填充的種子點(diǎn)。反復(fù)進(jìn)行 這過程，直到所保存的各區(qū)段都填充完畢。,57,2、算法步驟：,步驟 1：（初始化）將算法設(shè)置的堆棧置為空。將給定的 種子點(diǎn)（x, y）壓入堆棧；,步驟 2：（出棧）如果堆棧為空，算法結(jié)束；否則取棧頂 元素（x, y）作為種子點(diǎn)；,棧,種子,58,步驟 3：（區(qū)段填充）從種子點(diǎn)（

31、x, y）開始，沿縱坐標(biāo)為y的當(dāng)前掃描線向左右兩個方向逐個像素用新的顏色值進(jìn)行填充，直到邊界為止即像素顏色等于邊界色。設(shè)區(qū)間兩邊界的橫坐標(biāo)分別為xleft和xright；,步驟4：在與當(dāng)前掃描線相鄰的上下兩條掃描線上，以區(qū)間xleft, xright為搜索范圍，求出需要填充的各小區(qū)間，把各小區(qū)間中最右邊的點(diǎn)并作為種子點(diǎn)壓入堆棧，轉(zhuǎn)到步驟2。,xleft xright,59,3、算法的關(guān)鍵原則： 1）搜索原則：從前一個填充的區(qū)間（區(qū)間的范圍為xleft, xright）作為后一條掃描線種子點(diǎn)尋找的范圍。 2）種子點(diǎn)的位置原則：（1）當(dāng)xleft, xright范圍比較大時， 當(dāng)前區(qū)間的種子點(diǎn)可能

32、是邊界前一點(diǎn)；（2）當(dāng)xleft, xright 范圍比較小，當(dāng)前區(qū)間的種子點(diǎn)就是xright位置。 3）填充原則：從種子點(diǎn)往左，右填，填到邊界。,1,2,如果種子 點(diǎn)在這里,xleft,xright,搜索確定種子點(diǎn),種子點(diǎn)填充,60,public void scan(int pixels,Point point,int boundary_color,int new_color,int old_color) int x,y,savex,xright,xleft; Point p; Stack stack=new Stack(); /設(shè)置堆棧對象 stack.push(point); /壓棧 b

33、oolean span_need_fill; while (!stack.empty() p=(Point)(stack.pop(); /出棧，從堆棧中取一像素作為種子像素 x=p.x; y=p.y; savex=x; /保存橫坐標(biāo)x的值 while (pixelsy*w+x!=boundary_color) pixelsy*w+x=new_color; x+; /從種子像素開始向右填充到邊界 xright=x-1; /保存線段的右端點(diǎn) x=savex-1;,x-1,xright,4、程序?qū)崿F(xiàn),61,while (pixelsy*w+x!=boundary_color) pixelsy*w+x

34、=new_color; x-; /從種子像素開始向左填充到邊界，以上兩步完成區(qū)間填充 xleft=x+1; /保存線段的左端點(diǎn) x=xleft; y=y+1; while (x=xright) /在上一條掃描線上檢查是否需要填充 span_need_fill=false; while (pixelsw*y+x!=boundary_color ,xleft,xright,62,/繼續(xù)向右檢查以防有遺漏 while( (pixelsy*w+x=boundary_color | pixelsw*y+x!= new_color ) /在上一條掃描線上檢查完,如果種子 點(diǎn)在這里,1,2,3,xleft,

35、xright,63,x=xleft; y=y-2; /形成下一條掃描線的y值 /在下一條掃描線上從左向右地檢查位于區(qū)間xleft,xright上的像素 while (x=xright) span_need_fill=false; while (pixelsw*y+x!=boundary_color ,64,1,2,1,0,2,2,2,2,3,3,2,2,2,2,2,5、實(shí)例,0,65,3.6 字符的生成,點(diǎn)陣式字符是將字符形狀表示為一個矩形點(diǎn)陣， 由點(diǎn)陣中點(diǎn)的不同值來表達(dá)字符的形狀。常用 的點(diǎn)陣大小有79、88、1616等。 顯示點(diǎn)陣式字符時，只需將字庫中的矩形點(diǎn)陣映射到幀緩沖器中的單元即可。

36、在復(fù)制過程中，可施加變換，以獲得簡單的變化。 從字庫中讀出原字型，經(jīng)過變換復(fù)制到緩沖器中的操作，可由專門的硬件來完成，這就大大加快了字符生成的速度。但同時由于每個變化都必須存儲在緩沖器中，所以需要較大的存儲空間。,3.6.1 點(diǎn)陣式字符,66,下圖(a)所示的是字母“P”的點(diǎn)陣式表示。(b)-(d)即以(a)為原型的變化例子。其中，(b)表示變成粗體字 ，(c)表示旋轉(zhuǎn)90o, (d)表示變成斜體字。,67,3.6.2 輪廓式字符,輪廓式字符是將每個字符定義為一條曲線或多邊形的輪廓，顯示時需要進(jìn)行掃描轉(zhuǎn)換。如圖3.31所示為字母“B”的輪廓表示，輪廓線構(gòu)成了一個或若干個封閉的平面區(qū)域，顯示時字

37、符輪廓的內(nèi)部需用掃描線填充程序來填充。,68,3.7 光柵圖形的反走樣算法,3.7.1 光柵圖形的走樣現(xiàn)象,采用本章介紹的算法在光柵圖形顯示器上繪制的非水平且非垂直的直線或多邊形邊界，會或多或少地呈現(xiàn)鋸齒狀。這是由于采用離散量表示連續(xù)量而引起的。圖形信號是連續(xù)的，而它們在光柵顯示器上對應(yīng)的圖形則是由一系列相同亮度的離散像素組成。用離散的像素表示連續(xù)的直線或多邊形的邊界必然會引起圖形的失真，即光滑的線段變成了階梯的形狀，這種現(xiàn)象就稱為走樣。用于減輕或消除這種效果的技術(shù)就稱為反走樣。,69,圖3.33 狹小圖形的遺失,圖3.32 細(xì)節(jié)失真,光柵圖形的走樣現(xiàn)象表現(xiàn)為： 產(chǎn)生階梯狀的邊界 圖形的細(xì)節(jié)失真 狹小圖形遺失等,階梯狀邊界,70,第一種是提高硬件的分辨率。 如把圖形顯示器的分辨率提高一倍，直線經(jīng)過兩倍的像素，鋸齒增加了一倍，但同時每個階梯的寬度也減小了一半，因此顯示出的直線看起來就平滑了一些。這種方法是以4倍的存儲器代