基本圖形生成算法3區(qū)域填充

1、第3章 基本圖形生成算法 3.3 區(qū)域填充,二維圖形填充是面著色的手段，是圖形到圖象的重要步驟二維圖形填充所要做的就是將圖形內(nèi)部所有的點(diǎn)----內(nèi)點(diǎn)用指定的顏色表示。,,,,3.3 區(qū)域填充,多邊形的兩種重要表示方法：1、頂點(diǎn)表示法，即用多邊形的頂點(diǎn)序列來表示。2、點(diǎn)陣表示法，即用多邊形的全體內(nèi)點(diǎn)來表示。頂點(diǎn)表示：數(shù)學(xué)上常用的方法，精確，數(shù)據(jù)量小，又叫矢量表示點(diǎn)陣表示：工程上常用的方法，直觀，數(shù)據(jù)量大，又叫柵格表示流行的4

2、D技術(shù)，大量的柵格--矢量轉(zhuǎn)換,多邊形的掃描轉(zhuǎn)換,多邊形掃描轉(zhuǎn)換是指從多邊形的頂點(diǎn)表示到多邊形的點(diǎn)陣表示的轉(zhuǎn)換常用的多邊形掃描轉(zhuǎn)換方法有：逐點(diǎn)判斷方法掃描線算法邊緣填充算法,逐點(diǎn)判斷方法,對(duì)于屏幕上的每一個(gè)像素判斷是否內(nèi)點(diǎn)掃描轉(zhuǎn)換的實(shí)質(zhì)就是找出所有的內(nèi)點(diǎn)。內(nèi)點(diǎn)的判斷方法有：射線法累計(jì)角度法編碼方法,射線法(1),從一點(diǎn)出發(fā)的射線，若與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)，為內(nèi)點(diǎn)；偶數(shù)，不是內(nèi)點(diǎn)射線的方向不是問題，為簡(jiǎn)便，射線方

3、向定為向右的水平線。這樣只要計(jì)算射線與邊界線的交點(diǎn)，或從待判定點(diǎn)出發(fā)，水平向右找邊界點(diǎn)，直到顯示器邊緣,射線法(2),即使經(jīng)過簡(jiǎn)化，計(jì)算量也非常大要計(jì)算射線與每條邊的交點(diǎn)要判斷交點(diǎn)是否在該點(diǎn)的右邊要判斷交點(diǎn)是否在邊的兩個(gè)端點(diǎn)之間逐點(diǎn)法的各種方法，原理簡(jiǎn)單，但割裂了像素之間的關(guān)系，導(dǎo)致計(jì)算量大，速度太慢。對(duì)于判斷個(gè)別點(diǎn)是否位于多邊形內(nèi)部有效，用來填充多邊形不合適。,掃描線算法（1）,掃描線算法充分利用了像素之間的各種關(guān)系，即區(qū)域的

4、連貫性、掃描線連貫性和邊的連貫性，減少了計(jì)算量，提高了速度。區(qū)域連貫性,兩條掃描線之間的區(qū)域分割成若干個(gè)相鄰區(qū)域兩個(gè)相鄰區(qū)域分別分屬多邊形內(nèi)外只要確定這些區(qū)域中任何一個(gè)區(qū)域內(nèi)的一個(gè)點(diǎn)與多邊形的內(nèi)外關(guān)系，就可確定所有這些區(qū)域的內(nèi)外關(guān)系,掃描線算法（2）,掃描線的連貫性一條掃描線與多邊形非水平邊的交點(diǎn)數(shù)為偶數(shù)這些交點(diǎn)從左到右排序，奇數(shù)交點(diǎn)與其后的偶數(shù)交點(diǎn)之間所有的點(diǎn)都是多邊形內(nèi)點(diǎn)。只要兩個(gè)相鄰交點(diǎn)，就可確定一批內(nèi)點(diǎn)。,掃描線算法（

5、3）,掃描線與兩個(gè)非水平邊的連接處的交點(diǎn)均為兩個(gè)重合點(diǎn)，即理論上應(yīng)有兩個(gè)交點(diǎn)解決辦法：非水平邊上端截取一個(gè)單位實(shí)際上每條邊不需專門處理，在算法中自動(dòng)解決,掃描線算法（4）,邊的連貫性：相鄰掃描線與同一條邊的交點(diǎn)坐標(biāo)在垂直方向相差1，在水平方向相差d,d等于邊的斜率的倒數(shù)知道了一個(gè)交點(diǎn)(xi,yi)，就可以用加減法算出下一個(gè)交點(diǎn)(xi+1,yi+1)=(xi+d,yi+1)。邊的兩個(gè)端點(diǎn)必然屬于交點(diǎn)。,掃描線算法（5）,掃描線算法充

6、分利用三個(gè)連貫性，通過對(duì)有關(guān)數(shù)據(jù)的組織，以很小的計(jì)算量，實(shí)現(xiàn)對(duì)多邊形的掃描轉(zhuǎn)換。掃描線算法對(duì)每條非水平邊按如下結(jié)構(gòu)組織：ymax:邊的上端點(diǎn)的y坐標(biāo)x:邊的下端點(diǎn)的x坐標(biāo)dx:邊的斜率的倒數(shù)next:指向下一條邊的指針,邊:(2,10)—(9,6)，其結(jié)構(gòu)為：,掃描線算法（6）,建立邊表（ET），按下列要求將多邊形的每條非水平邊的邊結(jié)構(gòu)放入ET表：ET表是按邊下端點(diǎn)的y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組下端點(diǎn)的y坐標(biāo)為i的邊

7、歸入第i類有多少條掃描線，就設(shè)多少類邊同一類中，各邊按x值遞增的順序排列成行x值相等時(shí)就按dx值遞增的順序排列,掃描線算法（7）,例題：建立右圖ET表解：1號(hào)邊是水平邊，去掉0號(hào)邊：2號(hào)邊：3號(hào)邊：4號(hào)邊：5號(hào)邊：6號(hào)邊：,掃描線算法（8）,組織ET表：,掃描線算法（9）,活化邊鏈表AEL:與掃描線相交的邊結(jié)構(gòu)組成。邊結(jié)構(gòu)組成情況隨掃描線位置的變化而不斷變化。邊結(jié)構(gòu)中的x值隨掃描線遞增不斷變化。,掃描線算法,組織

8、ET表：,掃描線算法,組織ET表：,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,11,12,0,,,,,,,掃描線算法,組織ET表：,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,,,,,,,掃描線算法,組織ET表：,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,,,,5,10.7,5/4,,,,掃描線算法,組織ET表：,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,,,

9、,,,,掃描線算法,組織ET表：,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,,,,,,,掃描線算法,組織ET表：,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,,,,,,,掃描線算法,組織ET表：,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,,,,,,,掃描線算法,,,,,,,,,,,0,1,2,3,4,5,6,7,8,,,,,,,,,,,掃描線算法,,,,,,,,,,,0,1,2,

10、3,4,5,6,7,8,,,,,,,,,,,掃描線算法（10）,,,AEL,,AEL,,,,Y=6對(duì)應(yīng)的活化邊表,Y=7對(duì)應(yīng)的活化邊表,掃描線算法描述如下：,1.建立ET表2.將掃描線縱坐標(biāo)y的初值置為ET表非空元素的最小序號(hào)3.置AEL為空4.執(zhí)行下列步驟，直到ET、AEL都為空：如果ET中的第y類非空，將其中所有的邊取出并插入AEL,掃描線算法描述如下：,如果有新的插入AEL,則對(duì)AEL各邊排序?qū)EL中的邊兩兩配對(duì)，每對(duì)

11、邊中的x取整，獲得有效填充區(qū)段，并填充將當(dāng)前掃描線縱坐標(biāo)y值遞增1將AEL中滿足y=ymax的邊刪除對(duì)AEL中剩下的邊的x字段作x=x+dx操作,邊緣填充算法（1）,掃描線算法數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要頻繁排序。邊緣填充算法與掃描線算法類似，但不需要排序，用“異或”方式，繞開了排序問題?！爱惢颉碧攸c(diǎn)：在橡皮筋技術(shù)中用過。同一像素以異或方式畫兩次，顏色擦除。設(shè)背景色：01110101（任選），畫筆顏色：11100101 （任選），第一

12、次畫點(diǎn)（異或）： 01110101 XOR 11100101 =10010000第二次畫點(diǎn)（異或）：10010000 XOR 11100101 =01110101,還原,邊緣填充算法（2）,與掃描線算法比較：掃描線算法：排序分出1，2，3，4，從1畫到2，從3畫到4。邊緣填充算法：從邊上一點(diǎn)畫到最右邊，不管1，2，3，4哪個(gè)先畫，從1到2，從3到4。畫了奇數(shù)次。,,,,1,2,3,4,,,,1,2,3,4,,,,,,,邊緣

13、填充算法（3）,邊緣填充算法省去了排序，且每個(gè)邊緣點(diǎn)的操作方法一樣，十分有利于編程；但要處理大量像素（尤其是對(duì)大屏幕），速度比掃描線算法慢。加速方法，確定圖形邊緣框，只畫到邊緣框右邊,種子填充算法,面著色的另一類算法是種子填充算法，與掃描轉(zhuǎn)換的區(qū)別在于：要求區(qū)域有一個(gè)連通的邊界，需要一顆種子點(diǎn)。適合于已經(jīng)畫出大量邊界線的場(chǎng)合適合于人機(jī)交互操作方式，或者事先保留了種子點(diǎn)最常用的是掃描線種子填充算法,掃描線種子填充算法（1）,具體算

14、法：教材p186堆棧的概念：堆棧是計(jì)算機(jī)領(lǐng)域常用的概念，是一個(gè)存儲(chǔ)區(qū)，后進(jìn)先出，先進(jìn)后出,掃描線種子填充算法（2）,掃描線種子填充過程說明,過程：1、壓入種子12、彈出種子1，左右填充直到邊界3、填充線上下搜索未填充區(qū)，每區(qū)選一粒種子2，3，4壓入4、彈出種子4，填區(qū)域45、彈出種子3，填區(qū)域36，彈出種子2，填區(qū)域2,圖案填充（1）,前述方法只能在面上著單色，有時(shí)需要在面上貼圖,圖案填充（2）,方法：將圖案像素值存入一

15、個(gè)UxV 數(shù)組用前述各種方法計(jì)算填充像素坐標(biāo)(x,y)求余運(yùn)算：u=x%U,v=y%V從圖案數(shù)組中取出(u, v)像素值，填入像素(x,y),圖案填充（3）,兩種填充方案像素坐標(biāo)取設(shè)備坐標(biāo)，(x,y)原點(diǎn)在屏幕左下（上）角像素坐標(biāo)取圖形相對(duì)坐標(biāo)， (x,y)原點(diǎn)在圖形區(qū)域左下（上）角,圖案填充（4）,像素坐標(biāo)(x,y)首先轉(zhuǎn)化成相對(duì)坐標(biāo)(x1,y1) ， (x1,y1)原點(diǎn)在圖形區(qū)域左下（上）角方案2多轉(zhuǎn)換一次坐標(biāo)，填充的圖