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

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

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

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

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

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

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

7、歸入第i類有多少條掃描線，就設(shè)多少類邊同一類中，各邊按x值遞增的順序排列成行x值相等時就按dx值遞增的順序排列,掃描線算法（7）,例題：建立右圖ET表解：1號邊是水平邊，去掉0號邊：2號邊：3號邊：4號邊：5號邊：6號邊：,掃描線算法（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對應(yīng)的活化邊表,Y=7對應(yīng)的活化邊表,掃描線算法描述如下：,1.建立ET表2.將掃描線縱坐標(biāo)y的初值置為ET表非空元素的最小序號3.置AEL為空4.執(zhí)行下列步驟，直到ET、AEL都為空：如果ET中的第y類非空，將其中所有的邊取出并插入AEL,掃描線算法描述如下：,如果有新的插入AEL,則對AEL各邊排序?qū)EL中的邊兩兩配對，每對

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

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

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

14、法：教材p186堆棧的概念：堆棧是計算機(jī)領(lǐng)域常用的概念，是一個存儲區(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）,前述方法只能在面上著單色，有時需要在面上貼圖,圖案填充（2）,方法：將圖案像素值存入一

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