第6講-多邊形填充

2025/1/151本章內(nèi)容直線的掃描轉換圓與橢圓的掃描轉換區(qū)域填充二維裁剪字符生成反走樣第三節(jié)區(qū)域填充區(qū)域填充是指：在一個封閉的二維圖形內(nèi)部象素上著色(紋理、圖案）。也稱為：多邊形的掃描轉換。本節(jié)內(nèi)容：矩形的掃描轉換多邊形區(qū)域填充圖案填充2025/1/153矩形的掃描轉換可利用矩形的簡單性提高掃描轉換的效率。問題：邊界（共享邊界）像素的繪制？解決：象素中心定位于矩形的左、下邊界時繪制象素點。該規(guī)則適用于線畫矩形及多邊形以及共享頂點的情形。2025/1/154多邊形填充—直線的掃描轉換算法填充區(qū)間：區(qū)間端點由掃描線與多邊形邊界線段的交點確定2025/1/155注：多邊形上的區(qū)間

(a)原始端點由中點算法確定(b)限制端點在多邊形內(nèi)

2025/1/156實現(xiàn)區(qū)間填充的三個步驟計算掃描線與多邊形邊界線段的交點按照x升序排列交點填充多邊形內(nèi)交點對之間的所有像素?：水平線段如何處理2025/1/157區(qū)間填充策略y=8為例：排序后的交點x坐標列表為:(2,4.5,8.5,13)如何填充?2025/1/1584舍？還是5入?當交點的x

坐標值是分數(shù)時需進行舍入運算。(b)左端點:向上取整右端點:向下取整2025/1/159內(nèi)？或者外?當交點的x

坐標值是整數(shù)時，需確定該點是內(nèi)點擬或是外點。(b)在右邊界:外點在左邊界:內(nèi)點2025/1/1510交點為尖點交點Pl為尖點時，可計數(shù)為：1，2或者0。如下圖P0P0P0P0P1P1P1P1P2P2P2P2(a)(b)(c)(d)a)(b)計數(shù)為1個交點(c)計數(shù)為2個交點(d)計為0個交點規(guī)則：端點縱坐標是ymin

時計數(shù)加1；

端點縱坐標是ymax

時不計數(shù)

2025/1/1511續(xù)：在具體實現(xiàn)時，對交點的后處理過程可以轉化為對邊界線段進行的預處理。2025/1/1512掃描線與多邊形邊界線段交點的計算(1)交點特點：Y方向坐標值滿足:交點界于線段兩端點間:第一個交點是其端點之一，不妨設為？：后續(xù)交點的計算取整？！2025/1/1513掃描線與多邊形邊界線段交點的計算(2)記前一掃描線與邊界線段交點為當前掃描線與該邊界線段有否交點可通過其縱坐標值確定。記當前掃描線與邊界線段交點為

x的取整需針對邊界線段在多邊形的左右兩側做不同的處理：左側邊：向右取整，且當交點落在邊界上時視做內(nèi)部點右側邊：向左取整，且當交點落在邊界上時視做外部點2025/1/1514考慮到，為消除浮點數(shù)運算，以交點在左側邊為例，可增設計數(shù)器Counter，并改寫交點公式為：掃描線與多邊形邊界線段交點的計算(3)下一個交點對應計算器的值為：Counter的初始值可以是：2025/1/1515仍以交點在左側邊為例。（1）判斷Counter的值是否大于0（2）若不是，則直接取為xi；若是，則進行如下運算：此時，計數(shù)器刷新為：問題：交點在右側邊時的處理掃描線與多邊形邊界線段交點的計算(4)（3）上述步驟反復執(zhí)行k次，直至Counter的值小于0，此時xi+k的值即為交點向右取整的結果。其截斷部分仍是。

2025/1/1516活性邊表AET

(active-edge

table)引入如下的數(shù)據(jù)結構記錄交點92092-5/211103/211130

P6P1P5P6P4P5P3P4Line9AETpointer1111.53/211130

P4P5P3P4Line10AETpointer引入Counter？92094.5-5/2118.53/211130

P6P1P5P6P4P5P3P4Line8AETpointer2025/1/15170123456789101137-5/2573/2

920

11130

97-5/21173/2

邊表(ET)的初始化2025/1/1518直線的掃描轉換填充算法生成初始邊表ET;把掃描線的y值設為ET的最小y坐標;AET初始化為空;循環(huán)直至滿足終止條件:AET和ET為空從ET取值(滿足ymin=y的線段)放到AET;從AET中刪除滿足y=ymax的線段,然后按照x坐標排序;填充既定區(qū)間;y

增加1;針對新的y值刷新AET中各項的x

值.2025/1/1519算法偽代碼Polygongfill(polydef,color)Pointpolydef[];intcolor;{for(各條掃描線i)

建立初始化活性邊表EdgeTable[i];i=0;ActiveEdgeList=0；//當前掃描線對應的活性邊表初始化

for(各條掃描線i){

把EdgeTable[i]插入ActiveEdgeList中，并排序；遍歷ActiveEdgeList，把配對交點構成半開半閉區(qū)間；填充各區(qū)間；從ActiveEdgeList中刪除假交點；刷新ActiveEdgeList中交點的X坐標值；

}//for}2025/1/1520曲線邊界區(qū)域填充應用舉例可用類似方法（掃描轉換確定出交點）實現(xiàn)曲線邊界區(qū)域的填充，但所需運算量顯然比多邊形更大。例：圓域的活性邊表填充算法。仍假設圓心在坐標原點；每條掃描線與圓周有兩個交點，填充兩個交點構成的區(qū)間即可；掃描線與圓周的交點的計算，可利用圓的掃描轉換結果。2025/1/1521算法特點利用了多邊形邊界的連貫性加速與掃描線交點的計算：算法及數(shù)據(jù)結構復雜計算效率高對每個象素只訪問一次，對硬件的訪問量最小，且與設備無關。引入活性邊表結構，增加了維持邊表及進行交點排序的開銷，不適合硬件實現(xiàn)。2025/1/1522練習題-作業(yè)4用多邊形的掃描線算法對如下多邊形進行掃描轉換。（其中多邊形各頂點的坐標為p1(5,7)，p2(5,11)，p3(8,13)，p4(12,12)，p5(12,7)，p6(9,9)）求該多邊形的ET表用AEL表表示出多邊形掃描轉換的過程2025/1/1523其它填充算法邊緣填充算法種子填充算法：從區(qū)域內(nèi)部一點開始填充直至邊界。遞歸種子填充算法掃描線種子填充算法2025/1/1524邊緣填充算法條件：已通過掃描線與線段求交或對線段進行掃描轉換得到邊界點。思路：利用求余運算代替交點排序、配對、構造填充區(qū)間。原理：象素點顏色值經(jīng)過偶數(shù)次求余運算后保持不變，經(jīng)過奇數(shù)次求余運算后變?yōu)槠溆鄶?shù)算法：以掃描線為中心的邊緣填充算法以邊為中心的邊緣填充算法像素求余運算2025/1/1525以掃描線為中心的邊緣填充算法將當前掃描線上的所有象素著上指定顏色的補色2025/1/1526以掃描線為中心的邊緣填充算法逐個“邊界點”向右取余2025/1/1527以掃描線為中心的邊緣填充算法逐個“邊界點”向右取余2025/1/1528以掃描線為中心的邊緣填充算法逐個“邊界點”向右取余2025/1/1529以掃描線為中心的邊緣填充算法逐個“邊界點”向右取余2025/1/1530以掃描線為中心的邊緣填充算法逐個“邊界點”向右取余2025/1/1531以掃描線為中心的邊緣填充算法逐個“邊界點”向右取余2025/1/1532以掃描線為中心的邊緣填充算法逐個“邊界點”向右取余2025/1/1533以掃描線為中心的邊緣填充算法對各條掃描線循環(huán)上述處理過程。2025/1/1534以邊為中心的邊緣填充算法原始多邊形2025/1/1535以邊為中心的邊緣填充算法初始化：將繪圖窗口的背景色置為多邊形顏色的補色2025/1/1536以邊為中心的邊緣填充算法對非水平邊上的每個象素點向右求余邊1求余的結果圖示2025/1/1537以邊為中心的邊緣填充算法邊2求余的結果圖示2025/1/1538以邊為中心的邊緣填充算法邊3求余的結果圖示2025/1/1539以邊為中心的邊緣填充算法邊4求余的結果圖示2025/1/1540種子填充算法原理在多邊形內(nèi)部找到一個已知的象素點作為種子點，由此開始，利用區(qū)域的連通性找到多邊形內(nèi)部的其它所有象素點進行填充。區(qū)域連通性2025/1/1541區(qū)域連通性（1）四向連通區(qū)域從區(qū)域上任一點出發(fā)，在不超出區(qū)域邊界的前提下，可通過4個方向：上、下、左、右的移動組合到達區(qū)域中的任意象素點。允許從4個方向搜索下一個象素的填充算法稱為是四向填充算法2025/1/1542區(qū)域連通性（2）八向連通區(qū)域從區(qū)域上任一點出發(fā)，在不超出區(qū)域邊界的前提下，可通過8個方向：上、下、左、右、左上、左下、右上、右下的移動組合，到達區(qū)域中的任意象素。允許從8個方向搜索下一個象素的填充算法稱為是8向填充算法2025/1/1543區(qū)域連通性（3）理論上認為，8向填充算法可以填充4向、8向連通區(qū)域，但實際上對于4向連通區(qū)域來說，使用8向填充算法會擴大填充范圍、甚至會導致所定義區(qū)域不閉合的問題。2025/1/1544填充問題描述設填充區(qū)域為四向連通區(qū)域。區(qū)域表示采用邊界表示方法：即區(qū)域邊界上所有象素點的值與區(qū)域內(nèi)部象素點的值不同。對于有內(nèi)環(huán)的區(qū)域仍可進行處理。2025/1/1545種子填充算法分類遞歸填充算法掃描線算法改進的掃描線種子填充算法2025/1/1546遞歸填充算法初始化：種子象素入棧第一步：棧頂象素出棧，作為種子點；第二步：種子點被置為填充色；第三步：按照左、上、右、下順序檢查與種子點相鄰的象素：若非邊界且未被填充，則入棧（8向連通區(qū)域需考慮更多相鄰象素）。若棧不空，則重復第一步。2025/1/1547s125697834象素填充順序示意圖問題：效率低下。2025/1/1548掃描線算法原理：在每條掃描線上只取一個種子，每次填充該種子所在掃描線上區(qū)域內(nèi)部象素點區(qū)間。（減少水平方向連通性測試次數(shù)）在其相鄰的上、下掃描線上確定出一個新的種子，進行如上處理。（減少在垂直方向上連通性測試次數(shù)）2025/1/1549掃描線種子填充算法流程（1）初始化：由指定的種子象素點(x,y)生成種子(y,xl,xr)填充區(qū)間并入棧。(xl,xr分別為種子點所在掃描線上多邊形內(nèi)部區(qū)間的左、右端點)第一步：若種子?？談t算法終止，否則棧頂種子出棧第二步：確定新種子：分別確定y+1,y-1掃描線上與(y,xl,xr)連通的區(qū)間；填充新區(qū)間并將新種子壓入堆棧，第三步：上述過程循環(huán)執(zhí)行。2025/1/1550掃描線種子填充算法流程（2）考慮到區(qū)域可以是凹的或有內(nèi)環(huán)的，所以可能在該掃描線上出現(xiàn)多個填充區(qū)間，亦即需定義多個種子。yy+1同樣考慮到凹或有孔的區(qū)域，需對掃描線y-1進行同樣的處理，獲得新的種子。2025/1/1551掃描線種子填充算法的改進思路算法中的回溯過程并非總是必要的。無需進行填充回溯需要進行填充回溯2025/1/1552Referto:任繼成，劉慎權，區(qū)域填充掃描線算法的改進，計算機輔助設計與圖形學學報，Vol.10No.61998.改進的掃描線種子填充算法對棧結構進行改造記錄種子點所在區(qū)間的左右端點，及掃描順序標志+y：表示沿縱坐標增加的方向進行逐行掃描；-y：表示沿縱坐標減小的方向進行逐行掃描。實際的記錄數(shù)據(jù)分別可以表示為：2025/1/1553相關問題對于8向連通區(qū)域的填充需考慮：當象素點（x，y）為內(nèi)部點時，需考察象素點（x+1，y+1）是否是邊界。圖案填充2025/1/1554圖案填充圖案定義：可以使用一個二維數(shù)組：MXN來記錄color[i][j]:表示局部坐標系(i,j)處的象素值涉及問題：圖案與區(qū)域的定位問題:相對定位，絕對定位像素著色模式的問題：透明(Transparent)還是不透明(Opaque)2025/1/1555圖案定位(1)圖案在區(qū)域所在的繪圖空間坐標系中定位

此時若區(qū)域的位置不同，則區(qū)域中填充的圖案也不同。此時的視覺效果是：若區(qū)域移動，則區(qū)域中的填充圖案發(fā)生變化。(x,y)value[x][y]=color[x%M][y%n]MN個像素定義的圖案2025/1/15