[理學(xué)]第四章二維圖形的生成__區(qū)域填充(參考版)
2025-01-22 15:14本頁面
【正文】 多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較 。 ? 前者：從邊界頂點信息出發(fā)。 ? 前者只要求掃描線與多邊形邊界交點個數(shù)為偶數(shù)。 ? 區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換；若已知給定多邊形的頂點，則區(qū)域填充轉(zhuǎn)化為多邊形的掃描轉(zhuǎn)換。 可相互轉(zhuǎn)換 。 種子掃描線算法 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 46 ? 該算法也可以填充有孔區(qū)域。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點壓入堆棧，返回第（ 2）步。分別標(biāo)記區(qū)段的左、右端點坐標(biāo)為 xl和 xr。否則取棧頂元素（ x， y），以 y作為當(dāng)前掃描線。將種子點（ x， y）入棧。 解決方法是用掃描線填充算法 、種子填充算法 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 44 、種子掃描線算法 ? 掃描線算法 ? 目標(biāo)：減少遞歸層次 ? 適用于邊界表示的 4連通區(qū)域 算法思想 ： 在任意不間斷區(qū)間中只取一個種子像素（ 不間斷區(qū)間指在一條掃描線上一組相鄰元素 ） ， 填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段 ， 并依次把它們保存起來 ， 反復(fù)進(jìn)行這個過程 ， 直到所保存的個區(qū)段都填充完畢 。 ?缺點 ： (1) 有些象素會入棧多次 ， 降低算法效率； (2) 遞歸執(zhí)行 ， 算法簡單 ， 但效率不高 ， 區(qū)域內(nèi)每一象素都引起一次遞歸 ， 進(jìn) /出棧 ， 費時費內(nèi)存 。 BoundaryFill4(x+1,y,oldColor,newColor)。 BoundaryFill4(x,y1,oldColor,newColor)。 (color != newColor)) { PutPixel(x,y,newColor)。 if((color != boundaryColor) amp。 } }/*end of FloodFill4() */ 、種子填充算法 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 42 邊界表示的 4連通區(qū)域 void BoundaryFill4(int x,int y,int boundaryColor,int newColor) { int color。 FloodFill4(x1,y,oldColor,newColor)。 FloodFill4(x,y+1,oldColor,newColor)。 、種子填充算法 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 40 ? 例 ： 多邊形由 P0P1P2P3P4 構(gòu)成 ， P0(1,5) P1(5,5) P2(7,3) P3(7,1) P4(1,1) ? 設(shè)種子點為 （ 3， 3） ， 搜索的方向是上 、 下 、 左 、 右 。 現(xiàn)取 (x,y)為種子點對區(qū)域 G進(jìn)行填充：即先置像素 (x,y)的顏色為 new_color， 然后逐步將整個區(qū)域 G都置為同樣的顏色 。種子填充算法是從區(qū)域內(nèi)任一個種子像素位置開始，由內(nèi)向外將填充色擴(kuò)散到整個多邊形區(qū)域的填充過程。 } } 邊界標(biāo)志算法 :算法過程 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 31 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 32 邊界標(biāo)志算法 :算法過程 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 33 ? 用軟件實現(xiàn)時，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同， ? 但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級。 if(inside！ = FALSE) drawpixel (x, y, color)。 { 對多邊形 polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE。 對未打標(biāo)志的點 ， inside 不變 。 若點在多邊形外 ， 則inside 為假 。 對每條與多邊形相交的掃描線 ， 按從左到右的順序 ， 逐個訪問該掃描線上的象素 。 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 29 ?1. 對多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換 ， 即對多邊形邊界所經(jīng)過的象素作一個邊界標(biāo)志 。 2022/2/16 西安工程大學(xué)計算機(jī)圖形學(xué) 28 、掃描線算法 ? 特點：算法效率比逐點填充法高很多。 4） x:=x+Δx 。 并填色 。 遞增方向排序 。 （ 3）按從下到
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1