【文章內(nèi)容簡介】 1 1 11??xxk邊的連貫性 1 1 11 1 1? ??yy kxx計算機圖形學(xué) 福建師范大學(xué) 邊的連貫性 ? 推論：邊的連貫性是連接區(qū)域連貫性和掃描線連貫性的紐帶。 ? 掃描線連貫性 “ ＋” 邊連貫性 “＝” 區(qū)域連貫性 計算機圖形學(xué) 福建師范大學(xué) 掃描線算法 ?掃描線與多邊形的頂點或邊界相交時，必須進行正確的交點取舍。 只需檢查頂點的兩條邊的另外兩個端點的 y值。按這兩個 y值中大于交點 y值的個數(shù)是 0,1,2來決定。 1 2 3 P1 P2 P3 P4 P6 P5 P7 計算機圖形學(xué) 福建師范大學(xué) 掃描線算法 ? 數(shù)據(jù)結(jié)構(gòu) – 結(jié)點內(nèi)容 x：當前掃描線與邊的交點坐標 △ x：從當前掃描線到下一條掃描線間 x的增量 ymax：該邊所交的最高掃描線號 ymax 0 1122 3344 5566 7788 9 10 11P 2(5,1)EP 3(11,3 )DP 4(11,8 )GFCBP 5(5,5)P 6(2,7)AP 1(2,2) 2 0 7 P6P1 A △ x ymax 7 P5P6 B △ x ymax 7 2 8 P4P5 C △ x ymax 計算機圖形學(xué) 福建師范大學(xué) 掃描線算法 ?數(shù)據(jù)結(jié)構(gòu) – 新邊表（ NET）：存放在該掃描線 第一次 出現(xiàn)的邊。若某邊的較低端點為 ymin，則該邊就放在掃描線 ymin的新邊表中 ?上圖所示各條掃描線的新邊表 NET 0 1122 3344 5566 7788 9 10 11P 2(5,1)EP 3(11,3 )DP 4(11,8 )GFCBP 5(5,5)P 6(2,7)AP 1(2,2) 7 6 P4P5 P5P6 5 4 3 2 1 0 P1P2 P2P3 8 5 3 2 5 3 3 2 0 7 11 0 8 5 2 8 5 7 P6P1 P3P4 計算機圖形學(xué) 福建師范大學(xué) 掃描線算法 ? 數(shù)據(jù)結(jié)構(gòu) – 活性邊表 (AET)：把與當前掃描線相交的邊稱為 活性邊 ，并把它們按與掃描線交點 x坐標遞增的順序存放在一個鏈表中 0 1122 3344 5566 7788 9 10 11P 2(5,1)EP 3(11,3 )DP 4(11,8 )GFCBP 5(5,5)P 6(2,7)AP 1(2,2) 2 0 7 7 P6P1 P5P6 A B 7 2 8 11 0 8 P4P5 P3P4 C D △ x ymax △ x ymax △ x ymax △ x ymax 計算機圖形學(xué) 福建師范大學(xué) 掃描線算法 ? 假定當前掃描線與多邊形某一條邊的交點的 x坐標為 x，則 下一條掃描線與該邊的交點 不要重計算，只要加一個增量△ x。 ? 設(shè)該邊的直線方程為： ax+by+c=0； – 若 y＝ yi， x=xi；則當 y = yi+1時， ? 其中 為常數(shù)，并約定 a=0時， 。 。)(1 11 abxcybax iii ?????? ??abx ???0??x計算機圖形學(xué) 福建師范大學(xué) 算法過程 void polyfill (polygon, color) int color。 多邊形 polygon。 { for (各條掃描線 i ) { 初始化新邊表頭指針 NET [i]； 把 y min = i 的邊放進邊表 NET [i]。 } y = 最低掃描線號； 初始化活性邊表 AET為空； for (各條掃描線 i ) { 計算機圖形學(xué) 福建師范大學(xué) 算法過程 把新邊表 NET [i] 中的邊結(jié)點用插入排序法插入 AET表，使之按 x坐標遞增順序排列； 遍歷 AET表，把配對交點區(qū)間 (左閉右開 )上的象素 (x, y)，用 drawpixel (x, y, color) 改寫象素顏色值； i++。 遍歷 AET表，把 y max= i 的結(jié)點從 AET表中刪除，并把 y max i 結(jié)點的 x值遞增 ?x； } } /* polyfill */ 計算機圖形學(xué) 福建師范大學(xué) 思考題 ? 已知多邊形 P=(P0P1P2P3P4P5P6P0)；其各邊坐標分別為 ? [（ 2， 5）（ 2， 10）（ 9， 6）（ 16， 11）（ 16， 4）（ 12， 2）（ 7， 2） ] ? 建立其新邊表和活性邊表 計算機圖形學(xué) 福建師范大學(xué) 新邊表 計算機圖形學(xué) 福建師范大學(xué) y=3 y=8 活動邊表的例子 計算機圖形學(xué) 福建師范大學(xué) 掃描線算法小結(jié) ? 建立新邊表 ? 按照掃描線順序處理 ? 每條掃描線構(gòu)造活性邊表（ x遞增插入排序） ? 中間考慮交點取舍 ? 根據(jù)當前活性邊表選取像素進行填充（ x方向） ? 從活性邊表中刪除 y max= i 的結(jié)點 計算機圖形學(xué) 福建師范大學(xué) ? 基本思想： – 幀緩沖器中對多邊形的 每條邊進行直線掃描轉(zhuǎn)換 ，亦即對多邊形邊界所經(jīng)過的象素打上標志。 –填充。對每條與多邊形相交的掃描線，按從左到右的順序，逐個訪問該掃描線上的象素。 ?取一個布爾變量 inside來指示當前點的狀態(tài)，若點在多邊形內(nèi)，則 inside為真。若點在多邊形外，則 inside為假。 ?Inside 的初始值為假，每當當前訪問象素為被打上標志的點，就把 inside取反。對未打標志的點， inside不變。 計算機圖形學(xué) 福建師范大學(xué) 邊標志算法 例子 多邊形 P0P1P2P3P4頂點坐標為（ 2,1） ,(2,7),(8,5),(8,1),(6,4),以掃描線Y=3為例說明填充過程。開始時 inside=0. 1）對于 X=0，該像素未置成邊界值， inside=0， 該點為背景色； 2）對于 X=1，同上； 3）對于 X=2，該像素已置成邊界色， inside取反后為 1，該點被置成多邊形顏色； 4）對于 X=3， 4，像素未置成邊界色，由于 inside=1， 所以點被置成多邊形顏色； 5）對于 X=5，像素被置成邊界色， inside取反后為 0，該點被置成背景色； 6）對于 X=6，像素未置成邊界色，由于 inside=0，所以點被置成背景色； 7）對于 X=7，像素被置成邊界色， inside取反后為 1，該點被置成多邊形顏色； 8）對于 X=8，像素被置成邊界色， inside取反后為 0，該點被置成背景色； 計算機圖形學(xué) 福建師范大學(xué) 算法過程 void edgemark_fill(polydef, color) 多邊形定義 polydef； int color。 { 對多邊形 polydef 每條邊進行直線掃描轉(zhuǎn)換； for (每條與多邊形 polydef相交的掃描線 y ) { inside = FALSE。 for (掃描線上每個象素 x ) { if(象素 x 被打上邊標志 ) inside = ! (inside)。 if(inside！ = FALSE) drawpixel (x, y, color)。 else drawpixel (x, y, background)。 } } ? } 計算機圖形學(xué) 福建師范大學(xué) ? 用軟件實現(xiàn)時，掃描線算法與邊界標志算法的執(zhí)行速度幾乎相同， ? 但由于邊界標志算法不必建立維護邊表以及對它進行排序，所以邊界標志算法更適合硬件實現(xiàn)，這時它的執(zhí)行速度比有序邊表算法快一至兩個數(shù)量級 。 計算機圖形學(xué) 福建師范大學(xué) ? 區(qū)域 指已經(jīng)表示成點陣形式的填充圖形，它是象素的集合。 ? 區(qū)域填充 指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的。 計算機圖形學(xué) 福建師范大學(xué) ? 區(qū)域表示方法： 內(nèi)點表示、邊界表示 ? 內(nèi)點表示 – 枚舉出 區(qū)域內(nèi)部 的所有像素 – 內(nèi)部的所有像素著同一個顏色 – 邊界像素著與內(nèi)部像素不同的 顏色 ? 邊界表示 – 枚舉出 邊界上 所有的像素 – 邊界上的所有像素著同一顏色 – 內(nèi)部像素著與邊界像素不同的顏色 計算機圖形學(xué) 福建師范大學(xué) ? 區(qū)域填充要求區(qū)域是連通的 ? 連通性 : 4連通、 8連通 ? 4連通： ? 8連通 計算機圖形學(xué) 福建師范大學(xué) ? 4連通與 8連通區(qū)域的區(qū)別 – 連通性： 4連通可看作 8連通區(qū)域，但對邊界有要求 – 對邊界的要求 計算機圖形學(xué) 福建師范大學(xué) A：適合于內(nèi)點表示區(qū)域的填充算法 設(shè) G為一內(nèi)點表示的區(qū)域， (x,y)為區(qū)域內(nèi)一點，oldcolor為 G的原色。現(xiàn)取 (x,y)為種子點對區(qū)域 G進行填充：即先置像素 (x,y)的顏色為 newcolor，然后逐步將整個區(qū)域 G都置為同樣的顏色。 步驟如下： 種子象素入棧，當棧非空時，執(zhí)行如下三步操作： （ 1）棧頂象素出棧； （ 2）將出棧象素置成多邊形色； （ 3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界上且未置成多邊形色，則把該象素入棧。 （種子填充算法） 計算機圖形學(xué) 福建師范大學(xué) 種子填充算法 ——例子 ? 多 邊 形 由 P0P1P2P3P4 構(gòu)成 ，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1) ? 設(shè)種子點為 （ 3， 3） ， 搜索的方向是上 、下 、 左 、 右 。 依此類推 ， 最后像素被選中并填充的次序如圖中箭頭所示 計算機圖形學(xué) 福建師范大學(xué) ? 內(nèi)點表示 的 4連通區(qū)域的遞歸填充算法 : ? void FloodFill4(int x,int y,int oldcolor,int newcolor) ? { if(getpixel(x,y)==oldcolor) //屬于區(qū)域內(nèi)點 oldcolor ? { drawpixel(x,y,newcolor)。 ? FloodFill4(x,y+1,oldcolor,newcolor)。 ? FloodFill4(x,y1,oldcolor,newcolor)。 ? FloodFill4(x1,y,oldcolor,newcolor)。 ? FloodFill4(x+1,y,oldcolor,newcolor)。 ? } ? } 計算機圖形學(xué) 福建師范大學(xué) ? 邊界表示 的 4連通區(qū)域的遞歸填充算法 : ? void BoundaryFill4(int x,int y,int boundarycolor,int newcolor) ? { int color=getpixel(x,y)。 ? if(color!=newcolor amp。amp。 color!=boundarycolor) ? { drawpixel(x,y,newcolor)。 ? BoundaryFill4 (x,y+1, boundarycolor,newcolor)。 ? BoundaryFill4 (x,y1, boundarycolor,newcolor)。 ? BoundaryFill4 (x1,y, boundarycolor,newcolor)。 ? BoundaryFill4 (x+1,y, boundarycolor,newcolor)。