基本圖形生成算法第1頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月3.2實(shí)區(qū)域填充算法

確定待填充的象素，即檢查光柵的每一像素是否位于多邊形區(qū)域內(nèi)解決的主要問(wèn)題是什么？圖案填充還有一個(gè)什么象素填什么顏色的問(wèn)題曲線圍成的區(qū)域，可用多邊形逼近第2頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月點(diǎn)在多邊形內(nèi)的包含性檢驗(yàn)檢驗(yàn)夾角之和射線法檢驗(yàn)交點(diǎn)數(shù)第3頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月檢驗(yàn)夾角之和若夾角和為0，則點(diǎn)p在多邊形外若夾角和為360°，則點(diǎn)p在多邊形內(nèi)ABCDEPABCDEP第4頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月射線法檢驗(yàn)交點(diǎn)數(shù)ABCDEPABCDEP交點(diǎn)數(shù)=偶數(shù)（包括0）點(diǎn)在多邊形之外交點(diǎn)數(shù)=奇數(shù)點(diǎn)在多邊形之內(nèi)zx左閉右開(kāi)第5頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月包圍盒法凸多邊形凹多邊形逐點(diǎn)測(cè)試效率低不實(shí)用怎么辦？第6頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月實(shí)區(qū)域填充算法分類(lèi)掃描線填充算法---掃描線順序有序邊表算法邊填充算法種子填充算法---內(nèi)部一個(gè)點(diǎn)出發(fā)簡(jiǎn)單種子算法掃描線種子算法第7頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月掃描線填充算法求交：I4,I3,I2,I1排序：I1,I2,I3,I4交點(diǎn)配對(duì)：(I1,I2),(I3,I4)區(qū)間填色利用圖形的空間連貫性和掃描線的連貫性第8頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月填充擴(kuò)大化問(wèn)題解決方法：取中心掃描線y+0.5檢查交點(diǎn)右方像素的中心是否落在區(qū)間內(nèi)

xl≤x+0.5≤xryxy012345671234567012345671234567xP1P2P3P4x第9頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月頂點(diǎn)交點(diǎn)的計(jì)數(shù)問(wèn)題

543210P1P2P3P4I1I2I3I4P5掃描線5掃描線4掃描線3掃描線2掃描線1I5I6檢查交于該頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的y值大于該頂點(diǎn)y值的個(gè)數(shù)

計(jì)數(shù)0次計(jì)數(shù)1次計(jì)數(shù)2次10第10頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有序邊表算法影響一般掃描線填充算法效率的因素？所有的邊和掃描線求交，效率很低。因?yàn)橐粭l掃描線往往只和少數(shù)幾條邊相交。如何提高效率？建立每條掃描線的活性邊表何謂活性邊？求交和排序目標(biāo)是簡(jiǎn)化交點(diǎn)計(jì)算第11頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有序邊表算法與當(dāng)前掃描線相交的邊稱為活性邊（activeedge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活性邊表（AEL,Activeedgetable)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。只需對(duì)當(dāng)前掃描線的活性邊表作更新，即可得到下一條掃描線的活性邊表。第12頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有序邊表算法如何計(jì)算下一條掃描線與邊的交點(diǎn)。直線方程：ax+by+c=0當(dāng)前交點(diǎn)坐標(biāo)：(xi,yi)下一交點(diǎn)坐標(biāo)：(xi+1,yi+1)xi+1=

((-byi+1)-c)/a=((-byi-b)-c)/a=xi-b/a=xi+1/k活動(dòng)邊表中需要存放的信息：

x：當(dāng)前掃描線與邊的交點(diǎn)

△x＝-b/a：從當(dāng)前掃描線到下一條掃描線之間的x增量

ymax：邊所交的最高掃描線y=yi+1y=yiPjPj+1(xi,yi)(xi+1,yi+1)第13頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有序邊表算法活性邊表的更新為了方便邊的活性邊表的更新，建立另一個(gè)表-新邊表，存放在該掃描線第一次出現(xiàn)的邊。存放的信息：

x：掃描線與該邊的初始交點(diǎn)

△x：x的增量

ymax：該邊的最大y值新邊插入、舊邊刪除第14頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月即算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由新邊表ET（EdgeTable）和活性邊表AEL（ActiveEdgeList）兩部分組成。表結(jié)構(gòu)ET和AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成：

x:在ET中表示邊的下端點(diǎn)的x坐標(biāo)，在AEL中則表示邊與掃描線的交點(diǎn)的坐標(biāo)；Δx:邊的斜率的倒數(shù)；ymax:邊的上端點(diǎn)的y坐標(biāo)；next:指向下一條邊的指針。

有序邊表算法第15頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月yx0123456789101112345678P6P4P1P5P2P3新邊表8.57.56.55.54.53.52.51.50.5∧∧∧∧∧528.5-1.57∧1108∧207∧5-32.533∧P4P5P5P6P3P4P6P1P1P2P2P3活性邊表5-32.533∧P1P2P2P3y=1.5207.833∧P6P1P2P3y=2.5207.1108∧P6P1P3P4y=3.5528.P4P51108∧P3P45-1.57P5P6207.P6P1y=5.5728.P4P51108∧P3P43.5-1.57P5P6207.P6P1y=6.5928.P4P51108∧P3P4y=7.5207.1108∧P6P1P3P4y=4.5第16頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月step1：把新邊表ET［i］中的邊結(jié)點(diǎn)，用插入排序法插入活性邊表AET，使之按X坐標(biāo)遞增順序排序；step2：遍歷AET表，把配對(duì)交點(diǎn)之間的區(qū)間(左閉右開(kāi))上的各象素(X，Y)，用drawpixel(x,y,color)改寫(xiě)象素顏色值；step3：遍歷AET表，把Ymax=i的結(jié)點(diǎn)從AET表中刪除，并把

Ymax＞i的結(jié)果點(diǎn)的X值遞增△X；step4：重復(fù)各掃描線算法：(對(duì)每一條掃描線i)第17頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月有序邊表算法優(yōu)點(diǎn)：對(duì)每個(gè)像素只訪問(wèn)一次與設(shè)備無(wú)關(guān)缺點(diǎn)：數(shù)據(jù)結(jié)構(gòu)復(fù)雜只適合軟件實(shí)現(xiàn)第18頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月邊填充算法

第19頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月邊填充算法

優(yōu)點(diǎn)：最適合于有幀緩存的顯示器可按任意順序處理多邊形的邊僅訪問(wèn)與該邊有交點(diǎn)的掃描線上右方的像素，算法簡(jiǎn)單缺點(diǎn)：對(duì)復(fù)雜圖形，每一像素可能被訪問(wèn)多次，輸入/輸出量大圖形輸出不能與掃描同步進(jìn)行，只有全部畫(huà)完才能打印第20頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月柵欄填充算法

引入柵欄的目的？第21頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月種子填充算法種子填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。種子填充算法要求區(qū)域是連通的6754S9328第22頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月種子填充算法假設(shè)多邊形區(qū)域內(nèi)至少有一個(gè)像素已知區(qū)域定義法：Interior-definedBoundary-definedFlood-fillalgorithmBoundary-fillalgorithm區(qū)域連通方式：4-connected8-connected23第23頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月區(qū)域連通方式對(duì)填充結(jié)果的影響4連通區(qū)域邊界填充算法的填充結(jié)果8連通區(qū)域邊界填充算法的填充結(jié)果第24頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單的種子填充算法

（4連通邊界）種子像素入棧,當(dāng)棧非空時(shí)，重復(fù)以下步驟：(1)棧頂像素出棧(2)將出棧象素置成填充色

(3)按右、上、左、下順序檢查與出棧象素相鄰的四象素，若其中某象素不在邊界上且未被置成填充色，則將其入棧第25頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺點(diǎn)？第26頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月4-connectedboundary-fill

voidBoundaryFill4(intx,inty,intfill,intboundary){intcurrent;current=getpixel(x,y);

if((current!=boundary)&&(current!=fill)){putpixel(x,y,fill);BoundaryFill4(x+1,y,fill,boundary);BoundaryFill4(x-1,y,fill,boundary);BoundaryFill4(x,y+1,fill,boundary);BoundaryFill4(x,y-1,fill,boundary);}}4-connectedboundary-fill

voidFloodFill4(intx,inty,intfillColor,intoldColor){intcurrent;current=getpixel(x,y);

if(current==oldColor){putpixel(x,y,fillColor);BoundaryFill4(x+1,y,fillColor,oldColor);BoundaryFill4(x-1,y,fillColor,oldColor);BoundaryFill4(x,y+1,fillColor,oldColor);BoundaryFill4(x,y-1,fillColor,oldColor);}}第27頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月該算法也可以填充有孔區(qū)域。

缺點(diǎn)：(1)有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2)遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。改進(jìn)算法，減少遞歸次數(shù)，提高效率。 解決方法是用掃描線種子填充算法簡(jiǎn)單的種子填充算法

第28頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月掃描線種子填充算法目標(biāo)：減少遞歸層次適用于邊界表示的4連通區(qū)域算法思想：

在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來(lái)，反復(fù)進(jìn)行這個(gè)過(guò)程，直到所保存的各區(qū)段都填充完畢。第29頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月掃描線種子填充算法種子像素入棧,當(dāng)棧非空時(shí)，重復(fù)以下步驟：(1)棧頂像素出棧(2)沿掃描線對(duì)出棧像素的左右像素進(jìn)行填充，直到遇到邊界像素為止(3)將上述區(qū)間內(nèi)最左、最右像素記為xl和xr

(4)在區(qū)間[xl,xr]中檢查與當(dāng)前掃描線相鄰的上下兩條掃描線是否全為邊界像素、或已填充的像素，若為非邊界、未填充的像素，則把每一區(qū)間的最右像素取為種子像素入棧第30頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月掃描線算法分析（舉例分析）該算法也可以填充有孔區(qū)域。

像素中的序號(hào)標(biāo)指它所在區(qū)段位于堆棧中的位置第31頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月掃描線算法分析（舉例分析）第32頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月掃描線算法分析（舉例分析）第33頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月掃描線算法分析（舉例分析）第34頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月第3章基本圖形生成算法3.1圖元掃描轉(zhuǎn)換3.2實(shí)區(qū)域填充算法3.3圖形反走樣技術(shù)第35頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月3.3反走樣用離散量表示連續(xù)量引起的失真現(xiàn)象稱之為走樣(aliasing)。光柵圖形的走樣現(xiàn)象階梯狀邊界；圖形細(xì)節(jié)失真；狹小圖形遺失：動(dòng)畫(huà)序列中時(shí)隱時(shí)現(xiàn)，產(chǎn)生閃爍。第36頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月走樣現(xiàn)象舉例不光滑(階梯狀）的圖形邊界例子：PaintBrush第37頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月走樣現(xiàn)象舉例圖形細(xì)節(jié)失真第38頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月走樣現(xiàn)象舉例狹小圖形的遺失與動(dòng)態(tài)圖形的閃爍第39頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月反走樣概念及方法用于減少或消除走樣現(xiàn)象的技術(shù)稱為反走樣(antialiasing)提高分辨率(硬件、軟件方法）簡(jiǎn)單區(qū)域取樣第40頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月提高分辨率把顯示器分辨率提高一倍（硬件方法）直線經(jīng)過(guò)兩倍的象素，鋸齒也增加一倍，但同時(shí)每個(gè)階梯的寬度也減小了一倍，所以顯示出的直線段看起來(lái)就平直光滑了一些。第41頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月提高分辨率方法簡(jiǎn)單，但代價(jià)非常大。顯示器的水平、豎直分辯率各提高一倍，則顯示器的點(diǎn)距減少一倍，幀緩存容量則增加到原來(lái)的4倍，而掃描轉(zhuǎn)換同樣大小的圖元卻要花4倍時(shí)間。而且它也只能減輕而不能消除鋸齒問(wèn)題第42頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月提高分辨率高分辨率計(jì)算低分辨率顯示（軟件方法）用較高的分辨率的顯示模式下計(jì)算，（對(duì)各自像素下計(jì)算，再求加權(quán)平均的顏色值），在較低的分辨率模式下顯示。只能減輕而不能消除鋸齒問(wèn)題。第43頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月高分辨率計(jì)算低分辨率顯示把每個(gè)像素分為四個(gè)子像素，掃描轉(zhuǎn)換算法求得各子像素的灰度值，然后對(duì)四像素的灰度值簡(jiǎn)單平均，作為該像素的灰度值。1111算術(shù)平均122142121加權(quán)平均第44頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單區(qū)域取樣方法由來(lái)兩點(diǎn)假設(shè)1、象素是數(shù)學(xué)上抽象的點(diǎn)，它的面積為0，它的亮度由覆蓋該點(diǎn)的圖形的亮度所決定；2、直線段是數(shù)學(xué)上抽象直線段，它的