【正文】 y作為當前掃描線。將種子點（ x， y）入棧。 –反復這個過程，直到填充結束。 ? 改進算法，減少遞歸次數，提高效率。 ? 缺點 ： ? (1) 有些象素會入棧多次，降低算法效率；棧結構占空間。 ? BoundaryFill4 (x+1,y, boundarycolor,newcolor)。 ? BoundaryFill4 (x,y1, boundarycolor,newcolor)。 color!=boundarycolor) ? { drawpixel(x,y,newcolor)。 ? if(color!=newcolor amp。 ? FloodFill4(x+1,y,oldcolor,newcolor)。 ? FloodFill4(x,y1,oldcolor,newcolor)。 依此類推 ， 最后像素被選中并填充的次序如圖中箭頭所示 計算機圖形學 福建師范大學 ? 內點表示 的 4連通區(qū)域的遞歸填充算法 : ? void FloodFill4(int x,int y,int oldcolor,int newcolor) ? { if(getpixel(x,y)==oldcolor) //屬于區(qū)域內點 oldcolor ? { drawpixel(x,y,newcolor)。 步驟如下： 種子象素入棧，當棧非空時，執(zhí)行如下三步操作： （ 1）棧頂象素出棧； （ 2）將出棧象素置成多邊形色； （ 3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界上且未置成多邊形色，則把該象素入棧。 計算機圖形學 福建師范大學 ? 區(qū)域表示方法： 內點表示、邊界表示 ? 內點表示 – 枚舉出 區(qū)域內部 的所有像素 – 內部的所有像素著同一個顏色 – 邊界像素著與內部像素不同的 顏色 ? 邊界表示 – 枚舉出 邊界上 所有的像素 – 邊界上的所有像素著同一顏色 – 內部像素著與邊界像素不同的顏色 計算機圖形學 福建師范大學 ? 區(qū)域填充要求區(qū)域是連通的 ? 連通性 : 4連通、 8連通 ? 4連通： ? 8連通 計算機圖形學 福建師范大學 ? 4連通與 8連通區(qū)域的區(qū)別 – 連通性： 4連通可看作 8連通區(qū)域，但對邊界有要求 – 對邊界的要求 計算機圖形學 福建師范大學 A：適合于內點表示區(qū)域的填充算法 設 G為一內點表示的區(qū)域， (x,y)為區(qū)域內一點，oldcolor為 G的原色。 ? 區(qū)域填充 指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。 } } ? } 計算機圖形學 福建師范大學 ? 用軟件實現時，掃描線算法與邊界標志算法的執(zhí)行速度幾乎相同， ? 但由于邊界標志算法不必建立維護邊表以及對它進行排序，所以邊界標志算法更適合硬件實現，這時它的執(zhí)行速度比有序邊表算法快一至兩個數量級 。 if(inside！ = FALSE) drawpixel (x, y, color)。 { 對多邊形 polydef 每條邊進行直線掃描轉換； for (每條與多邊形 polydef相交的掃描線 y ) { inside = FALSE。 計算機圖形學 福建師范大學 邊標志算法 例子 多邊形 P0P1P2P3P4頂點坐標為（ 2,1） ,(2,7),(8,5),(8,1),(6,4),以掃描線Y=3為例說明填充過程。 ?Inside 的初始值為假，每當當前訪問象素為被打上標志的點，就把 inside取反。 ?取一個布爾變量 inside來指示當前點的狀態(tài)，若點在多邊形內，則 inside為真。 –填充。 } y = 最低掃描線號； 初始化活性邊表 AET為空； for (各條掃描線 i ) { 計算機圖形學 福建師范大學 算法過程 把新邊表 NET [i] 中的邊結點用插入排序法插入 AET表，使之按 x坐標遞增順序排列； 遍歷 AET表，把配對交點區(qū)間 (左閉右開 )上的象素 (x, y)，用 drawpixel (x, y, color) 改寫象素顏色值； i++。 多邊形 polygon。 。若某邊的較低端點為 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 計算機圖形學 福建師范大學 掃描線算法 ? 數據結構 – 活性邊表 (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 計算機圖形學 福建師范大學 掃描線算法 ? 假定當前掃描線與多邊形某一條邊的交點的 x坐標為 x，則 下一條掃描線與該邊的交點 不要重計算，只要加一個增量△ x。按這兩個 y值中大于交點 y值的個數是 0,1,2來決定。 ? 掃描線連貫性 “ ＋” 邊連貫性 “＝” 區(qū)域連貫性 計算機圖形學 福建師范大學 掃描線算法 ?掃描線與多邊形的頂點或邊界相交時，必須進行正確的交點取舍。 ? 效率提高的根源：逐點判斷 ?區(qū)域判斷 計算機圖形學 福建師范大學 掃描線連貫性 ? 區(qū)域連貫性在一條掃描線上的反映 掃描線的連貫性 計算機圖形學 福建師范大學 掃描線連貫性 ? 交點序列：掃描線與多邊形的交點個數為偶數 (1,2,3,4,5,6) ? 紅色 區(qū)間 (1,2)、 (3,4)、(5,6)位于多邊形內部 ? 其余 綠色 區(qū)間位于多邊形外部 ? 兩類區(qū)間相間排列 掃描線的連貫性 計算機圖形學 福建師范大學 掃描線連貫性 ? 推論：如果上述交點區(qū)間屬于多邊形內 (外 )，那么該區(qū)間內所有點均屬于多邊形內 (外 )。 –對于一條掃描線填充過程可以分為四個步驟： ?求交 ?排序 ?配對 ?填色 計算機圖形學 福建師范大學 多邊形掃描轉換算法 P0 P1 P2 P3 P4 P5 P6 P7 x y 掃描轉換示意圖 計算機圖形學 福建師范大學 相鄰像素之間的連貫性 ? 掃描線算法充分利用了相鄰像素之間的連貫性，避免了對像素的逐點判斷和求交運算，提高了算法效率 ? 各種連貫性的定義 –區(qū)域連貫性 –掃描線連貫性 –邊的連貫性 計算機圖形學 福建師范大學 區(qū)域連貫性 ? 區(qū)域的連貫性是指多邊形定義的區(qū)域內部相鄰的像素具有相同的性質。 x=x_resolution。 y=y_resolution。 計算機圖形學 福建師范大學 多邊形的掃描轉換與區(qū)域填充 ? 區(qū)域表示方法： 內點表示、邊界表示 ? 內點表示 – 枚舉出 區(qū)域內部 的所有像素 – 內部的所有像素著同一個顏色 – 邊界像素著與內部像素不同的 顏色 ? 邊界表示 – 枚舉出 邊界上 所有的像素 – 邊界上的所有像素著同一顏色 – 內部像素著與邊界像素不同的顏色 計算機圖形學 福建師范大學 ? 多邊形分為凸多邊形、凹多邊形、含內環(huán)的多邊形。 ? 區(qū)域填充 指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。 計算機圖形學 福建師范大學 多邊形的掃描轉換與區(qū)域填充 ? 多邊形的掃描轉換： 把多邊形的頂點表示轉換為點陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內部的各個象素，并給幀緩沖器內的各個對應元素設置相應的灰度和顏色，通常稱這種轉換為多邊形的掃描轉換。 ? 點陣表示：用位于多邊形內的象素的集合來刻劃多邊形。 ? 如何改？ 計算機圖形學 福建師范大學 圓弧的掃描轉換算法 ? 使用 e= d ? e0=1R 計算機圖形學 福建師范大學 圓弧的中點掃描轉換算法 ? 利用圓八對稱性 ? 類似于直線的中點法 ? 使用了圓的隱式方程 ? 兩種不同的增量（ 0時 ， 0時） ? 為了改為整數算法 e= d 計算機圖形學 福建師范大學 小結 ? 直線段的掃描轉換算法 – 數值微分 (DDA)法 – 中點畫線法 – Bresenham算法 ? 圓弧的掃描轉換算法 計算機圖形學 福建師范大學 多邊形的掃描轉換與區(qū)域填充 ? 多邊形的表示方法 – 頂點表示 – 點陣表示 ? 頂點表示：用多邊形頂點的序列來刻劃多邊形。 circlepoints (x,y,color)。 y。 //顯示圓弧上的八個對稱點 ? while(x=y) ? { if(d0) d+=2*x+3。 d=。 ? x=0。 222 ???????????? pppppp yxdRyxyxFdRRFd ???? ),1(0計算機圖形學 福建師范大學 圓弧的掃描轉換算法 ? MidPointCircle(int r int color) ? { int x,y。只要掃描轉換八分之一圓弧，就可以求出整個圓弧的象素集 ? 中點畫圓法 ? 考慮中心在原點，半徑為 R ? 的第二個 8分圓， –構造判別式（圓方程） 222 )()1(),1()(RyxyxFMFdpppp?????????計算機圖形學 福建師范大學 圓弧的掃描轉換算法 若 d0, 則取 P1為下一象素，而且再下一象素的判別式為 ? 若 d=0, 則應取 P2為下一象素，而且下一象素的判別式為 ? 第 一個象素是（ 0,R），判別式 d的初始值為 32)()2(),2(39。 dx e e * * 2 39。 if (e?0) { y++, e=e1。 i++) {drawpixel (x, y, color)。 for (i=0。 k=dy/dx,e=。 float k, e。 ? if (e?0) ? { y++, e=e2*dx。 i++) ? { drawpixel (x, y, color)。 ? for (i=0。 ? dx = x1x0, dy = y1 y0。由于算法中只用到誤差項的符號，因此可作如下替換： dx e e * * 2 39。 ? if (e?0) ? { y++, e=e1。 i++) ? { drawpixel (x, y, color)。 ? for (i=0。 ? dx = x1x0, dy = y1 y0, k=dy/dx。 計算機圖形學 福建師范大學 Bresenham算法 ?例： Line: P0(0, 0), P1(5,2) k=dy/dx= ? x y e ? 0 0