基本圖形生成算法

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

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

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

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

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

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

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

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

△x：x的增量

ymax：該邊的最大y值新邊插入、舊邊刪除第14頁，課件共48頁，創(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頁，課件共48頁，創(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頁，課件共48頁，創(chuàng)作于2023年2月step1：把新邊表ET［i］中的邊結(jié)點(diǎn)，用插入排序法插入活性邊表AET，使之按X坐標(biāo)遞增順序排序；step2：遍歷AET表，把配對交點(diǎn)之間的區(qū)間(左閉右開)上的各象素(X，Y)，用drawpixel(x,y,color)改寫象素顏色值；step3：遍歷AET表，把Ymax=i的結(jié)點(diǎn)從AET表中刪除，并把

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

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

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

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

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

(3)按右、上、左、下順序檢查與出棧象素相鄰的四象素，若其中某象素不在邊界上且未被置成填充色，則將其入棧第25頁，課件共48頁，創(chuàng)作于2023年2月填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799缺點(diǎn)？第26頁，課件共48頁，創(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頁，課件共48頁，創(chuàng)作于2023年2月該算法也可以填充有孔區(qū)域。

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

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

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

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

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