計(jì)算機(jī)圖形學(xué)基本光柵圖形算法課件

第三章基本光柵圖形算法本章內(nèi)容3.1用Java語(yǔ)言繪圖13.2直線的掃描轉(zhuǎn)換23.3圓的掃描轉(zhuǎn)換33.4多邊形的掃描轉(zhuǎn)換43.5區(qū)域填充53.6字符的生成63.7光柵圖形的反走樣算法73.2直線的掃描轉(zhuǎn)換

⊙圖形圖像是由屏幕上不同亮度不同顏色的光點(diǎn)（像素）組成。在光柵顯示器的熒光屏上生成一個(gè)對(duì)象，實(shí)質(zhì)上是往幀緩存寄存器的相應(yīng)單元中填入數(shù)據(jù)。所以

⊙對(duì)直線進(jìn)行光柵化的時(shí)候，只能在顯示器所給定的有限個(gè)像素組成的點(diǎn)陣中確定最佳逼近于該直線的一組像素，用這些像素表示該直線。所以

⊙生成直線的主要工作是：快速找出距離直線最近的網(wǎng)格點(diǎn)，用這些網(wǎng)格點(diǎn)對(duì)應(yīng)的像素表示該直線。33.2.1基本增量算法設(shè)直線滿足，由于直線的斜率小于等于1，所以，該直線的掃描轉(zhuǎn)換可從最左端開始，每次遞增一個(gè)單位，對(duì)每個(gè)，相應(yīng)的有，則所以，每增加一個(gè)單位，只需加上一個(gè)，這樣就去掉了乘法運(yùn)算，提高了算法效率。在該算法中，直線上的所有點(diǎn)的和值可由前一點(diǎn)的值加一個(gè)基本增量得到，所以該算法稱為基本增量算法。3.2.1基本增量算法(DDA-digitaldifferential analyzer)

1、基本思想：53.2.1基本增量算法注：上述討論只適合的情況，當(dāng)時(shí)，只需將和的角色互換，即每次增加一個(gè)單位，每次增加?；驹隽克惴ㄒ步袛?shù)字微分分析器算法（DigitalDifferentialAnalyzer，DDA）。DDA是用數(shù)值方法求解微分方程的一種設(shè)備，即根據(jù)111和的一階導(dǎo)數(shù)，在和方向上漸進(jìn)地以小步長(zhǎng)移動(dòng)，由此產(chǎn)生連續(xù)的像素坐標(biāo)。62、直線的表示：

設(shè)直線的起點(diǎn)坐標(biāo)為(xs，ys)，終點(diǎn)坐標(biāo)為(xe,ye)，令Δx＝xe-xs，Δy＝y(tǒng)e-ys，則直線參數(shù)方程為目標(biāo)：能快速地求出能很好地表示直線的像素第步時(shí)(3.1)7下圖中，用公式（3.2）求得的直線上的點(diǎn)用空心圓表示，但顯示時(shí)要用像素來表示，即采用四舍五入的辦法得到最靠近空心圓點(diǎn)的像素，用這些像素（下圖中的實(shí)心圓點(diǎn)）來表示直線。圖中實(shí)心圓點(diǎn)表示用DDA方法生成的直線9圖中黑點(diǎn)表示用DDA法生成的直線4、直線的DDA算法程序voiddda(Graphicsg,intx1,intx2,inty1,inty2){intk;floatx,y,dx,dy;k=Math.abs(x2-x1);if(Math.abs(y2-y1)>k)k=Math.abs(y2-y1);dx=(float)(x2-x1)/k;dy=(float)(y2-y1)/k;//變化的增量x=(float)(x1);y=(float)(y1);for(inti=0;i<k;i++){

g.drawLine((int)(x+.5f),(int)(y+.5f),(int)(x+.5f),(int)(y+.5f));x=x+dx;y=y+dy;}}//endDDA

完成四舍五入10實(shí)例設(shè)給定直線的起點(diǎn)坐標(biāo)為(0，0)，終點(diǎn)坐標(biāo)為(9，6)，則上述DDA算法畫出的直線如下圖所示。DDA方法所畫直線圖DDA算法缺點(diǎn)：需要進(jìn)行浮點(diǎn)數(shù)運(yùn)算，產(chǎn)生一個(gè)像素要做兩次加法和兩次取整運(yùn)算，運(yùn)行效率低且取整運(yùn)算不利于硬件實(shí)現(xiàn)。11當(dāng)B在A的下面時(shí)，，此時(shí)應(yīng)取C點(diǎn)作為；當(dāng)B在A的上面時(shí)，，則應(yīng)取D點(diǎn)作為。BACD圖3.4的幾何意義設(shè)圖3.4中已得到第個(gè)顯示的點(diǎn)，B點(diǎn)是直線與第列網(wǎng)格線的交點(diǎn)，則第個(gè)顯示的點(diǎn)只能從C或D點(diǎn)中去選。設(shè)A為CD邊的中點(diǎn)，令誤差項(xiàng)(3.4)算法思想：13通過遞推的方式，高效地計(jì)算點(diǎn)序列和，由圖3.4可得(3.5)由式（3.3）～（3.5）可得=(3.6)14注：式（3.5）和（3.6）是根據(jù)圖3.4所示的情況推出的，容易驗(yàn)證，式（3.5）和（3.6）對(duì)圖3.5所示的兩種情況也成立。CBADBACD圖3.5的幾何意義的其他兩種情況15改進(jìn)后的算法程序voidbresenham(Graphicsg,intxs,intys,intxe,intye) {intdx=xe-xs; intdy=ye-ys; inte=2*dy-dx; intx=xs; inty=ys; for(inti=0;i<dx;i++){g.drawLine(x,y,x,y);//畫點(diǎn)（x,y）if(e>=0){y=y+1;e=e-2*dx;}x=x+1;e=e+2*dy;} }注：上面討論了的情況，如果，則需把和的地位互換。如果或，程序中 或需換成或，同時(shí)也應(yīng)相應(yīng)地改變。173.3圓的掃描轉(zhuǎn)換1、基本原理：

假設(shè)已選取Pi-1為第i-1個(gè)像素，則如果Pi-1在圓內(nèi)，就要向圓外方向走一步，若Pi-1在圓外就要向圓內(nèi)走一步。若Pi-1在圓上，則可以向圓內(nèi)走一步，也可以向圓外走。xypiPi+1Pi-1BA(0,0)圖3.9對(duì)圓弧AB用正負(fù)法取點(diǎn)3.3.1正負(fù)法這樣用于表示圓弧的點(diǎn)均在理想圓弧附近且時(shí)正時(shí)負(fù)，因此稱為正負(fù)法。由于這種方法每走完一步，都要比較當(dāng)前位置的函數(shù)值，以決定下一步的走向，因而也稱為逐點(diǎn)比較法。182、正負(fù)法的具體實(shí)現(xiàn)1）圓的表示：設(shè)圓的圓心為(0,0),半徑為R，則圓的方程為：

F(x,y)=x2+y2–R2=0

ypiPi+1Pi-1BA(0,0)圖3.9對(duì)圓弧AB用正負(fù)法取點(diǎn)如何判斷一個(gè)點(diǎn)和圓的內(nèi)外關(guān)系當(dāng)點(diǎn)(x,y)在圓內(nèi)時(shí)，F(xiàn)(x,y)<0；

當(dāng)點(diǎn)(x,y)在圓外時(shí)，F(xiàn)(x,y)>0；當(dāng)點(diǎn)(x,y)在圓上時(shí)，F(xiàn)(x,y)=0。19當(dāng)時(shí)，假設(shè)已經(jīng)算出F(xi,yi)，如何計(jì)算F(xi+1,yi+1)？？？由上可知。如果的值已算出，計(jì)算 時(shí)可分為兩種情況：(3.9)當(dāng)時(shí)，(3.10)由式（3.9）和式(3.10)知，21算法的程序?qū)崿F(xiàn)voidpnarc(Graphicsg,intradius){intx,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);}223.3.2Bresenham算法假設(shè)圓心(0,0)為原點(diǎn)，考慮AB弧的畫法，顯示一個(gè)整圓時(shí)，只要在顯示AB上任一點(diǎn)(x,y)時(shí)，同時(shí)顯示在圓周上其它七個(gè)對(duì)稱點(diǎn)

(y,x),(y,-x),(x,-y),(-x,-y),(-y,-x),(-y,x),(-x,y)。7個(gè)對(duì)稱點(diǎn)232、Bresenham的具體實(shí)現(xiàn)1）令D(P)=(x2+y2)-R2，表示點(diǎn)P到原點(diǎn)的距離平方與圓的半徑的平方之差。令：當(dāng)di=0時(shí)，點(diǎn)Hi和Li距弧AB的距離相等當(dāng)di<0時(shí)，|D(Hi)|<|D(Li)|，取Hi來顯示弧AB當(dāng)di≥0時(shí)，|D(Hi)|>|D(Li)|，取Li來顯示弧AB。Pi-1HiLidi=D(Hi)+D(Li)252）di遞推公式設(shè)已選中的點(diǎn)Pi-1=(xi-1,yi-1)，則Hi和Li點(diǎn)的坐標(biāo)分別為(xi,yi-1)和(xi,yi-1–1),Hi+1和Li+1的坐標(biāo)分別為(xi+1,yi)和(xi+1,yi

–1)。因?yàn)閤0=0,y0=R,x1=x0+1，所以d1=D(H1)+D(L1)=(12+y20-R2)+(12+(y0-1)2-R2)=3-2y0=3-2Rdi=(x2i+y2i-1-R2)+(x2i+(yi-1-1)2-R2)=2x2i+2y2i-1-2yi-1-2R2+1di+1=(xi+1)2+y2i-R2+(xi+1)2+(yi-1)2-R2=2x2i+4xi+2y2i-2yi-2R2+326基本思想按一定方式計(jì)算給定圓弧軌跡上的一系列頂點(diǎn)，然后用連接相鄰點(diǎn)的一系列直線段來逼近圓弧。用正多邊形迫近圓弧法設(shè)圓弧所在圓的半徑為R，圓弧的起始角和終止角分別為和，把圓弧分割成份，則相鄰兩個(gè)頂點(diǎn)之間的夾角為。設(shè)頂點(diǎn)序列的第個(gè)點(diǎn)為，為該點(diǎn)的幅角。則下一個(gè)頂點(diǎn)的坐標(biāo)為或表示為矩陣形式3.3.3圓的多邊形迫近法29橢圓弧的生成設(shè)橢圓的中心在原點(diǎn)，長(zhǎng)短軸分別為a和b，且平行于坐標(biāo)柚，則該橢圓的參數(shù)方程為，設(shè)頂點(diǎn)序列的第i個(gè)頂點(diǎn)為,則下一個(gè)頂點(diǎn)的坐標(biāo)應(yīng)滿足,

由此可得其中303.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)換圖3.11多邊形頂點(diǎn)表示P1P0P2P3P4圖3.16多邊形點(diǎn)陣表示

多邊形的掃描轉(zhuǎn)換就是把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)像素，并為幀緩存內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度或顏色。313.4.2掃描線算法特點(diǎn)：充分利用了相鄰像素之間的連續(xù)性，避免對(duì)像素的逐點(diǎn)判斷和反復(fù)求交運(yùn)算，減少了計(jì)算量，提高了算法速度?；靖拍睿?）掃描線的連續(xù)性2）邊的連續(xù)性3）奇點(diǎn)基本思想先求出掃描線與多邊形邊的交點(diǎn)，利用掃描線的連續(xù)性求出多邊形與掃描線相交的連續(xù)區(qū)域，然后利用多邊形邊的連續(xù)性，求出下一條掃描線與多邊形的交點(diǎn)，對(duì)所有掃描線由下到上依次處理。掃描線算法是按掃描線的順序計(jì)算出掃描線與多邊形的相交區(qū)間，然后用要求的顏色填充這些區(qū)間內(nèi)的像素。321掃描線的連續(xù)性設(shè)多邊形P的頂點(diǎn)，將各頂點(diǎn)的縱坐標(biāo)按遞減順序排列,即設(shè)當(dāng)前掃描線，，與多邊形P的邊的交點(diǎn)記為。設(shè)為與P的邊界各交點(diǎn)橫坐標(biāo)的遞增序列，該序列稱為交點(diǎn)序列。(3.21)當(dāng)知道一條掃描線上一點(diǎn)與多邊形的內(nèi)外關(guān)系時(shí)，即可確定該掃描線上所有點(diǎn)與多邊形之間的內(nèi)外關(guān)系。33交點(diǎn)序列具有以下性質(zhì)：1)交點(diǎn)個(gè)數(shù)l是偶數(shù)；2)掃描線上的區(qū)間 l–1位于多邊形P內(nèi)（圖3.13中的實(shí)線段部分），其余區(qū)間都在P外（圖3.13中的虛線段部分），兩類區(qū)間沿掃描線相間排列。這些性質(zhì)就稱為掃描線的連續(xù)性。P0P1P2P3P4P5P6P7P8xe01xe22xe33xe74xe65xe46圖3.13掃描線的連續(xù)性圖中----表示在多邊形外的區(qū)間──表示在多邊形內(nèi)的區(qū)間根據(jù)掃描線的連續(xù)性，只需求出掃描線與多邊形P的邊界的所有交點(diǎn)，就可確定掃描線位于多邊形P內(nèi)的區(qū)間。342邊的連續(xù)性掃描線的連續(xù)性知，序列（3.21）和（3.22）的點(diǎn)滿足以下關(guān)系：（1）兩序列元素的個(gè)數(shù)相等，即；（2）點(diǎn)（）與（）位于多邊形P的同一邊上（見圖3.14），所以可由下式計(jì)算(3.23)以上性質(zhì)稱為邊的連續(xù)性。若,

成立，則掃描線與掃描線和多邊形P相同的邊相交，由圖3.14邊的連續(xù)性P0P1P2P3P4P5P6P7P8xe01xe22xe33xe74xe65xe46xd01xd65xd46設(shè)當(dāng)前掃描線的下一條掃描線為，，且,設(shè)位于掃描線上的交點(diǎn)序列為（3.22）35但當(dāng)掃描線與多邊形P的邊界的交點(diǎn)恰好是P的頂點(diǎn)時(shí)（該交點(diǎn)稱為奇點(diǎn)），必須按不同的情況區(qū)別對(duì)待。3奇點(diǎn)的處理上述兩種形式的連續(xù)性都基于一個(gè)幾何事實(shí)：每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)都是偶數(shù)（包括零）。設(shè)多邊形P的頂點(diǎn)為這些頂點(diǎn)可分為兩類：極值點(diǎn)和非極值點(diǎn)。如果，則稱頂點(diǎn)為極值點(diǎn)（如圖3.15中的）；否則稱為非極值點(diǎn)（如圖3.15中的）。圖3.15一個(gè)多邊形與若干條掃描線P8P0P1P2P3P4P5P6P736為使每一條掃描線與多邊形P的邊界的交點(diǎn)個(gè)數(shù)始終為偶數(shù)，規(guī)定當(dāng)奇點(diǎn)是多邊形P的極值點(diǎn)時(shí)，該點(diǎn)按兩個(gè)交點(diǎn)計(jì)算，否則按一個(gè)交點(diǎn)計(jì)算。圖3.16非極值點(diǎn)的處理（a）（b）實(shí)際計(jì)算中，可如下處理非極值點(diǎn)：若是非極值點(diǎn)，則將,兩邊中位于掃描線上方的那條邊在處截去一個(gè)單位長(zhǎng)，這樣就能保證掃描線只和，中的一邊相交，只有一個(gè)交點(diǎn)。374算法的實(shí)現(xiàn)步驟與數(shù)據(jù)結(jié)構(gòu)對(duì)于每一條掃描線，多邊形的填充過程可分為以下4步：計(jì)算掃描線與多邊形各邊的交點(diǎn)，設(shè)交點(diǎn)個(gè)數(shù)為n；把所有的交點(diǎn)按x值遞增的順序進(jìn)行排列；將排序后的第1個(gè)與第2個(gè)交點(diǎn)，第3個(gè)與第4個(gè)交點(diǎn)，……第n-1個(gè)與第n個(gè)交點(diǎn)配對(duì)，每對(duì)交點(diǎn)就代表掃描線與多邊形的一個(gè)相交區(qū)間；把相交區(qū)間內(nèi)的像素置成多邊形的顏色，相交區(qū)間外的像素置成背景色。1234上述方法要計(jì)算每一條掃描線與所有邊的交點(diǎn)，計(jì)算量很大。為提高效率，可以對(duì)每一條掃描線，僅對(duì)與它相交的多邊形進(jìn)行求交運(yùn)算。38使用增量計(jì)算時(shí)，還要知道一條邊何時(shí)不再與下一條掃描線相交，以及時(shí)地把該邊從活性邊表中刪除，因此需要記錄下與該邊相交的最高掃描線號(hào)?；钚赃叡砼c當(dāng)前掃描線相交的邊稱為活性邊。把活性邊與掃描線的交點(diǎn)按x坐標(biāo)遞增的順序放在一個(gè)鏈表中，該鏈表就稱為活性邊表（ActiveEdgeList,AEL）。設(shè)多邊形某一條邊的方程為，當(dāng)前掃描線與該邊的交點(diǎn)坐標(biāo)為，則下一條掃描線與該邊的交點(diǎn)不需要重新計(jì)算，只要加一個(gè)增量即可。因?yàn)榇藭r(shí)有其中為常數(shù)，并規(guī)定時(shí)，。39綜上，AEL中的節(jié)點(diǎn)應(yīng)由如下四個(gè)域組成：:邊的上端點(diǎn)的y坐標(biāo)，即與該邊相交的最高掃描線號(hào)。

x

:邊與掃描線的交點(diǎn)的x坐標(biāo)。:從當(dāng)前掃描線到下一條掃描線間的x坐標(biāo)的增量，即邊的斜率的倒數(shù)。Next

:指向下一條邊的指針。新邊表為方便活性邊表的建立與更新，還要為每一條掃描線建立一個(gè)新邊表（NewEdgeList,NEL），存放在該掃描線上第一次出現(xiàn)的邊。也就是說，如果某邊的較低端點(diǎn)為，則該邊放在掃描線的新邊表中。注意：水平邊不放到任何掃描線的NEL中，即水平邊不參加分類。NEL中的節(jié)點(diǎn)結(jié)構(gòu)與AEL相同，只是x在這里不再表示邊與掃描線的交點(diǎn)，而是表示該邊較低端點(diǎn)的x坐標(biāo)值。40具體例子圖3.18和3.19是圖3.17中多邊形的新邊表NEL和活性邊表AEL。在左圖中表示邊，各頂點(diǎn)為[P0P1…P6]=[(2,5)(2,10)(9,6)(16,9)(16,4)(12,2)(7,2)]

其中，是非極值點(diǎn)，在分類前已對(duì)邊作了預(yù)處理，即分別在處把它們截去一個(gè)單位長(zhǎng)，這樣保證掃描線只和兩邊中的一邊相交，求得一個(gè)交點(diǎn)，是水平邊，不參加分類。圖3.17邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e641-5/3516/3AELe0e54214AEL在y=3掃描線上的狀態(tài)AEL-5/3511/3e0e54216AEL在y=4掃描線上的狀態(tài)AEL-5/352e0e49016AEL在y=5掃描線上的狀態(tài)…0102e1e210-7/411/2AEL在y=8掃描線上的狀態(tài)AEL97/341/3e39016e4圖3.18新邊表NEL123456e11002△xxymaxnexte49016e54212圖3.17多邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e6e2109-7/4e3997/357e0-5/3423.4.3邊緣填充算法1、特點(diǎn)：采用對(duì)圖像進(jìn)行逐位求補(bǔ)的方法，免去對(duì)邊排序的工作量。2、預(yù)備知識(shí)：假設(shè)某像素的顏色是C，對(duì)該像素做偶數(shù)次求補(bǔ)運(yùn)算后，其顏色還是C；做奇數(shù)次求補(bǔ)運(yùn)算后，其顏色變?yōu)镃。在光柵圖形中，如某區(qū)域已著上值為M的某種顏色，則上述求補(bǔ)運(yùn)算的結(jié)果是：對(duì)區(qū)域作偶數(shù)次求反運(yùn)算后，該區(qū)域的顏色不變；作奇數(shù)次求反運(yùn)算后，該區(qū)域的顏色則變成值為M的顏色。43對(duì)多邊形P的每一非水平邊（i=0,1,…,n）上的各像素進(jìn)行向右求補(bǔ)運(yùn)算，當(dāng)相對(duì)于所有邊的求補(bǔ)運(yùn)算都完成后，多邊形的掃描轉(zhuǎn)換也隨之完成。圖3.20a為給定的多邊形；b為對(duì)區(qū)域賦初值；c、d、e和f表示逐邊向右求補(bǔ)。(c)(d)(f)(e)(a)(b)圖3.20邊緣填充算法的過程3、邊緣填充算法的實(shí)現(xiàn)443.4.4邊界標(biāo)志算法1、基本原理：首先用一種特殊的顏色在幀緩沖器中將多邊形的邊界（水平邊的部分邊界除外）勾畫出來。然后再把位于多邊形內(nèi)的各個(gè)像素著上所需的顏色。2、算法具體實(shí)現(xiàn)步驟：步驟1：以值為boundary_color

的特殊顏色勾畫多邊形P的邊界。設(shè)多邊形頂點(diǎn)為Pi=(xi,yi),0≤i≤n，

xi,yi均為整數(shù)；置Pn+1=P0。每一條掃描線上著上這種特殊顏色的點(diǎn)的個(gè)數(shù)必定是偶數(shù)(包括零)。45intred=Color.red.getRGB();publicImageboundary(){Imageimage;//定義Image對(duì)象for(i=0;i<7;i++){dy=p[i+1].y-p[i].y;dx=(p[i+1].x-p[i].x)/dy;if(dy>0)x=p[i].x;elsex=p[i+1].x; ymax=(Math.max(p[i].y,p[i+1].y)); ymin=(Math.min(p[i].y,p[i+1].y));for(y=ymin+1;y<=ymax;y++){x=(int)(x+dx+.5);if(pixels[y*w+x]==red)pixels[y*w+x+1]=red;elsepixels[y*w+x]=red;}}ImageProducerip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}圖3.17多邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e646//maxx、maxy、minx、miny是獲得的多邊形最小矩形包圍盒邊界值publicImageinterior(){Imageimage;intmaxx=150,minx=20,maxy=120,miny=20,l;intin_flag；//多邊形內(nèi)部標(biāo)志變量for(y=miny;y<=maxy;y++){in_flag=0;for(x=minx;x<maxx;x++){l=pixels[y*w+x];if(l==red){if(in_flag==0)in_flag=1;elsein_flag=0;}if(in_flag==1)pixels[y*w+x]=red;}}ImageProducerip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}步驟2：設(shè)in_flag是一布爾變量。對(duì)每一條掃描線從左到右進(jìn)行搜索，如果當(dāng)前像素位于多邊形P內(nèi)，則in_flag=true，需要填上值為polygon_color的顏色；否則該像素在多邊形P外，需要填上值為background_color的顏色。圖3.17多邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e6473、邊界標(biāo)志算法實(shí)例XXXXXXP2(9,6)XXXXXXP0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)XXXXxXXxXXXXXXY=2Y=3Y=4Y=5Y=648實(shí)例最終結(jié)果XXXXXXXXXX

49區(qū)域填充是指先將區(qū)域內(nèi)的一點(diǎn)（常稱種子點(diǎn)）賦予給定顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過程。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ū)域的表示和類型圖3.22內(nèi)點(diǎn)表示的區(qū)域圖3.23邊界表示的區(qū)域501）4連通的區(qū)域:取區(qū)域內(nèi)任意兩點(diǎn)，在該區(qū)域內(nèi)若從其中一點(diǎn)出發(fā)通過上、下、左、右四種運(yùn)動(dòng)可到達(dá)另一點(diǎn)。圖3.24四個(gè)方向的運(yùn)動(dòng)2）8連通的區(qū)域:取區(qū)域內(nèi)任意兩點(diǎn)，若從其中任一點(diǎn)出發(fā)，在該區(qū)域內(nèi)通過沿水平方向、垂直方向和對(duì)角線方向的八種運(yùn)動(dòng)可到達(dá)另一點(diǎn)。圖3.25八個(gè)方向的運(yùn)動(dòng)3、區(qū)域的連通性513）4連通區(qū)域也可理解成8連通區(qū)域，即4連通能達(dá)到的8連通肯定能達(dá)到，4連通只是8連通的一種特殊情況。連通不是指邊界而是邊界內(nèi)的區(qū)域這里是X圍起來的區(qū)域·號(hào)是區(qū)域X是邊界8連通而非4連通的地方圖3.26內(nèi)點(diǎn)表示的八連通區(qū)域圖3.27邊界表示的八連通區(qū)域52但是兩者的邊界不盡相同。如果圖中標(biāo)有·號(hào)的像素組成的區(qū)域作為4連通區(qū)域，則其邊界由圖中的標(biāo)有△號(hào)的像素組成。如果將該區(qū)域作為8連通的區(qū)域，則其邊界由圖中標(biāo)有△號(hào)和×號(hào)的兩種像素組成。圖3.28四連通區(qū)域與八連通區(qū)域的不同邊界因?yàn)槿绻麉^(qū)域是8連通的，△邊界不能將區(qū)域有效封堵，X的位置和區(qū)域也是連通的。用于八連通區(qū)域的填充算法可用于四連通區(qū)域的填充，但用于四連通區(qū)域的填充算法并不適用于八連通區(qū)域的填充。53基本思想設(shè)（x,y）是內(nèi)點(diǎn)表示的一區(qū)域G內(nèi)的一點(diǎn)，old_color是G的原色。先?。▁,y）點(diǎn)為種子點(diǎn)，測(cè)試其顏色，若等于old_color，說明是區(qū)域內(nèi)一點(diǎn)，則將其置為新的顏色new_color，否則說明該點(diǎn)不在區(qū)域G內(nèi)，則停止填充；然后將該點(diǎn)周圍的四個(gè)點(diǎn)（四連通）或八個(gè)點(diǎn)（八連通）作為新的種子點(diǎn)進(jìn)行同樣的處理，通過這種擴(kuò)散完成對(duì)整個(gè)區(qū)域的填充。顯然，這一過程是用遞歸實(shí)現(xiàn)的。3.5.2遞歸算法54publicvoidflood_fill_8(int[]pixels,intx,inty,intold_color,intnew_color){if(x<w&&x>0&&y<h&&y>0){if(pixels[w*y+x]==old_color){pixels[w*y+x]=new_color; flood_fill_8(pixels,x,y+1,old_color,new_color); flood_fill_8(pixels,x,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y,old_color,new_color); flood_fill_8(pixels,x+1,y,old_color,new_color); flood_fill_8(pixels,x+1,y+1,old_color,new_color); flood_fill_8(pixels,x+1,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y+1,old_color,new_color); flood_fill_8(pixels,x-1,y-1,old_color,new_color);}}}算法實(shí)現(xiàn)553.5.3掃描線種子填充算法1、基本思想：從給定的種子點(diǎn)開始，先填充當(dāng)前掃描線上種子點(diǎn)所在的一區(qū)段，然后確定與這一段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段（需要填充的區(qū)間），從這些區(qū)間上各取一個(gè)種子點(diǎn)依次把它們存起來，作為下次填充的種子點(diǎn)。反復(fù)進(jìn)行這過程，直到所保存的各區(qū)段都填充完畢。562、算法步驟：步驟1：（初始化）將算法設(shè)置的堆棧置為空。將給定的種子點(diǎn)（x,y）壓入堆棧；步驟2：（出棧）如果堆棧為空，算法結(jié)束；否則取棧頂元素（x,y）作為種子點(diǎn)；12棧種子57步驟3：（區(qū)段填充）從種子點(diǎn)（x,y）開始，沿縱坐標(biāo)為y的當(dāng)前掃描線向左右兩個(gè)方向逐個(gè)像素用新的顏色值進(jìn)行填充，直到邊界為止即像素顏色等于邊界色。設(shè)區(qū)間兩邊界的橫坐標(biāo)分別為xleft和xright；步驟4：在與當(dāng)前掃描線相鄰的上下兩條掃描線上，以區(qū)間[xleft,xright]為搜索范圍，求出需要填充的各小區(qū)間，把各小區(qū)間中最右邊的點(diǎn)并作為種子點(diǎn)壓入堆棧，轉(zhuǎn)到步驟2。12種子點(diǎn)xleftxright583、算法的關(guān)鍵原則：1）搜索原則：從前一個(gè)填充的區(qū)間（區(qū)間的范圍為xleft,xright）作為后一條掃描線種子點(diǎn)尋找的范圍。2）種子點(diǎn)的位置原則：（1）當(dāng)xleft,xright范圍比較大時(shí)，當(dāng)前區(qū)間的種子點(diǎn)可能是邊界前一點(diǎn)；（2）當(dāng)xleft,xright范圍比較小，當(dāng)前區(qū)間的種子點(diǎn)就是xright位置。3）填充原則：從種子點(diǎn)往左，右填，填到邊界。1212如果種子點(diǎn)在這里xleftxright搜索確定種子點(diǎn)種子點(diǎn)填充59publicvoidscan(int[]pixels,Pointpoint,intboundary_color,intnew_color,intold_color){intx,y,savex,xright,xleft;Pointp;Stackstack=newStack();//設(shè)置堆棧對(duì)象stack.push(point);//壓棧booleanspan_need_fill;while(!stack.empty()){p=(Point)(stack.pop());//出棧，從堆棧中取一像素作為種子像素x=p.x;y=p.y;savex=x;//保存橫坐標(biāo)x的值while(pixels[y*w+x]!=boundary_color){ pixels[y*w+x]=new_color;x++;}//從種子像素開始向右填充到邊界

xright=x-1;//保存線段的右端點(diǎn)

x=savex-1;x-1填充過程xxright4、程序?qū)崿F(xiàn)60while(pixels[y*w+x]!=boundary_color){pixels[y*w+x]=new_color;x--;}//從種子像素開始向左填充到邊界，以上兩步完成區(qū)間填充xleft=x+1;//保存線段的左端點(diǎn)x=xleft;y=y+1;while(x<=xright){//在上一條掃描線上檢查是否需要填充span_need_fill=false;while(pixels[w*y+x]!=boundary_color&&pixels[w*y+x]!=new_color&&x<=xright){//待填充的線段span_need_fill=true;x++;}//待填充的線段處理完if(span_need_fill){//如果區(qū)間需要填充，則將其右端點(diǎn)作為

p=newPoint(x-1,y);

//種子點(diǎn)壓進(jìn)堆棧stack.push(p);//進(jìn)棧span_need_fill=false;}填充過程xx-1xleftxright61//繼續(xù)向右檢查以防有遺漏

while((pixels[y*w+x]==boundary_color||pixels[w*y+x]!=new_color)&&x<=xright)x++;}//在上一條掃描線上檢查完

如果種子點(diǎn)在這里12123xleftxright62x=xleft;y=y-2;//形成下一條掃描線的y值

//在下一條掃描線上從左向右地檢查位于區(qū)間[xleft,xright]上的像素while(x<=xright){ span_need_fill=false;while(pixels[w*y+x]!=boundary_color&&pixels[w*y+x]!= new_color){ span_need_fill=true; x++;} if(span_need_fill){ p=newPoint(x-1,y); stack.push(p); span_need_fill=false;} while(pixels[y*w+x]==boundary_color||pixels[w*y+x]!= new_color)&&x<=xright)x++;}}}631210222233222225、實(shí)例0643.6字符的生成點(diǎn)陣式字符是將字符形狀表示為一個(gè)矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值來表達(dá)字符的形狀。常用的點(diǎn)陣大小有7×9、8×8、16×16等。顯示點(diǎn)陣式字符時(shí)，只需將字庫(kù)中的矩形點(diǎn)陣映射到幀緩沖器中的單元即可。在復(fù)制過程中，可施加變換，以獲得簡(jiǎn)單的變化。從字庫(kù)中讀出原字型，經(jīng)過變換復(fù)制到緩沖器中的操作，可由專門的硬件來完成，這就大大加快了字符生成的速度。但同時(shí)由于每個(gè)變化都必須存儲(chǔ)在緩沖器中，所以需要較大的存儲(chǔ)空間。3.6.1點(diǎn)陣式字符65(a)(b)(c)(d)圖3.30點(diǎn)陣式字符及其變化下圖(a)所示的是字母“P”的點(diǎn)陣式表示。(b)-(d)即以(a)為原型的變化例子。其中，(b)表示變成粗體字，(c)表示旋轉(zhuǎn)90o,(d)表示變成斜體字。663.6.2輪廓式字符輪廓式字符是將每個(gè)字符定義為一條曲線或多邊形的輪廓，顯示時(shí)需要進(jìn)行掃描轉(zhuǎn)換。如圖3.31所示為字母“B”的輪廓表示，輪廓線構(gòu)成了一個(gè)或若干個(gè)封閉的平面區(qū)域，顯示時(shí)字符輪廓的內(nèi)部需用掃描線填充程序來填充。

673.7光柵圖形的反走樣算法3.7.1光柵圖形的走樣現(xiàn)象采用本章介紹的算法在光柵圖形顯示器上繪制的非水平且非垂直的直線或多邊形邊界，會(huì)或多或少地呈現(xiàn)鋸齒狀。這是由于采用離散量表示連續(xù)量而引起的。圖形信號(hào)是連續(xù)的，而它們?cè)诠鈻棚@示器上對(duì)應(yīng)的圖形則是由一系列相同亮度的離散像素組成。用離散的像素表示連續(xù)的直線