二維圖形填充

第5講二維圖形填充二維圖形填充是面著色的手段，是圖形到圖象的重要步驟二維圖形填充所要做的就是將圖形內(nèi)部所有的點(diǎn)----內(nèi)點(diǎn)用指定的顏色表示。多邊形的兩種重要表示方法：1、頂點(diǎn)表示法，即用多邊形的頂點(diǎn)序列來表示。2、點(diǎn)陣表示法，即用多邊形的全體內(nèi)點(diǎn)來表示。頂點(diǎn)表示：數(shù)學(xué)上常用的方法，精確，數(shù)據(jù)量小，又叫矢量表示點(diǎn)陣表示：工程上常用的方法，直觀，數(shù)據(jù)量大，又叫柵格表示流行的4D技術(shù)，大量的柵格--矢量轉(zhuǎn)換1多邊形的掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換是指從多邊形的頂點(diǎn)表示到多邊形的點(diǎn)陣表示的轉(zhuǎn)換常用的多邊形掃描轉(zhuǎn)換方法有：逐點(diǎn)判斷方法掃描線算法邊界標(biāo)志算法種子填充算法2逐點(diǎn)判斷方法對于屏幕上的每一個(gè)像素判斷是否內(nèi)點(diǎn)內(nèi)點(diǎn)：多邊形內(nèi)部的點(diǎn)。掃描轉(zhuǎn)換的實(shí)質(zhì)就是找出所有的內(nèi)點(diǎn)。內(nèi)點(diǎn)的判斷方法有：射線法累計(jì)角度法編碼方法3射線法(1)從一點(diǎn)出發(fā)的射線，若與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)，為內(nèi)點(diǎn)；偶數(shù)，不是內(nèi)點(diǎn)射線的方向不是問題，為簡便，射線方向定為向右的水平線。這樣只要計(jì)算射線與非水平線的交點(diǎn)4射線法(2)即使經(jīng)過簡化，計(jì)算量也非常大要計(jì)算射線與每條邊的交點(diǎn)要判斷交點(diǎn)是否在該點(diǎn)的右邊要判斷交點(diǎn)是否在邊的兩個(gè)端點(diǎn)之間逐點(diǎn)法的各種方法，原理簡單，但割裂了像素之間的關(guān)系，導(dǎo)致計(jì)算量大，速度太慢。對于判斷個(gè)別點(diǎn)是否位于多邊形內(nèi)部有效，用來填充多邊形不合適。5掃描線算法（1）掃描線算法充分利用了像素之間的各種關(guān)系，即區(qū)域的連貫性、掃描線連貫性和邊的連貫性，減少了計(jì)算量，提高了速度。區(qū)域連貫性12345兩條掃描線之間的區(qū)域分割成若干個(gè)相鄰區(qū)域兩個(gè)相鄰區(qū)域分別分屬多邊形內(nèi)外只要確定這些區(qū)域中任何一個(gè)區(qū)域內(nèi)的一個(gè)點(diǎn)與多邊形的內(nèi)外關(guān)系，就可確定所有這些區(qū)域的內(nèi)外關(guān)系6掃描線算法（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)。12347掃描線算法（3）掃描線與兩個(gè)非水平邊的連接處的交點(diǎn)均為兩個(gè)重合點(diǎn)，即理論上應(yīng)有兩個(gè)交點(diǎn)解決辦法：非水平邊上端截取一個(gè)單位實(shí)際上每條邊不需專門處理，在算法中自動解決2108掃描線算法（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)。ddd9掃描線算法（5）掃描線算法充分利用三個(gè)連貫性，通過對有關(guān)數(shù)據(jù)的組織，以很小的計(jì)算量，實(shí)現(xiàn)對多邊形的掃描轉(zhuǎn)換。掃描線算法對每條非水平邊按如下結(jié)構(gòu)組織：ymax:邊的上端點(diǎn)的y坐標(biāo)x:邊的下端點(diǎn)的x坐標(biāo)dx:邊的斜率的倒數(shù)next:指向下一條邊的指針ymaxxdxnext邊:(2,10)—(9,6)，其結(jié)構(gòu)為：109-1.75next10掃描線算法（6）建立邊表（ET），按下列要求將多邊形的每條非水平邊的邊結(jié)構(gòu)放入ET表：ET表是按邊下端點(diǎn)的y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組下端點(diǎn)的y坐標(biāo)為i的邊歸入第i類有多少條掃描線，就設(shè)多少類邊同一類中，各邊按x值遞增的順序排列成行x值相等時(shí)就按dx值遞增的順序排列11掃描線算法（7）例題：建立右圖ET表解：1號邊是水平邊，去掉0號邊：2號邊：3號邊：4號邊：5號邊：6號邊：571221547811012345645-1575/4111201175/487-582012掃描線算法（8）組織ET表：01234567845-1575/4111201175/487-5820571221547811012345613掃描線算法（9）活化邊鏈表AEL:與掃描線相交的邊結(jié)構(gòu)組成。邊結(jié)構(gòu)組成情況隨掃描線位置的變化而不斷變化。邊結(jié)構(gòu)中的x值隨掃描線遞增不斷變化。14掃描線算法（10）11120820AEL11120820AEL1175/487-5Y=6對應(yīng)的活化邊表Y=7對應(yīng)的活化邊表15掃描線算法描述如下：1.建立ET表2.將掃描線縱坐標(biāo)y的初值置為ET表非空元素的最小序號3.置AEL為空4.執(zhí)行下列步驟，直到ET、AEL都為空：如果ET中的第y類非空，將其中所有的邊取出并插入AEL16掃描線算法描述如下：如果有新的插入AEL,則對AEL各邊排序?qū)EL中的邊兩兩配對，每對邊中的x取整，獲得有效填充區(qū)段，并填充將當(dāng)前掃描線縱坐標(biāo)y值遞增1將AEL中滿足y=ymax的邊刪除對AEL中剩下的邊的x字段作x=x+dx操作17練習(xí)一練習(xí)二p5618邊界標(biāo)志算法(1)19邊界標(biāo)志算法(2)

20邊界標(biāo)志算法(3)

21邊界標(biāo)志算法(4)

22種子填充算法面著色的另一類算法是種子填充算法，與掃描轉(zhuǎn)換的區(qū)別在于：要求區(qū)域有一個(gè)連通的邊界，需要一顆種子點(diǎn)。適合于已經(jīng)畫出大量邊界線的場合適合于人機(jī)交互操作方式，或者事先保留了種子點(diǎn)最常用的是遞歸和掃描線種子填充算法232425遞歸填充算法(1)

26遞歸種子填充算法（2）27遞歸種子填充算法（3）

28掃描線種子填充算法（1）具體算法：教材p64堆棧的概念：堆棧是計(jì)算機(jī)領(lǐng)域常用的概念，是一個(gè)存儲區(qū)，后進(jìn)先出，先進(jìn)后出123壓入順序1,2,3………堆棧指針：指向下一個(gè)可用單元123彈出順序3,2,1………29掃描線種子填充算法（2）掃描線種子填充過程說明過程：1、壓入種子12、彈出種子