第5章基本圖形生成算法-第四講

第五章基本圖形生成算法多邊形的掃描轉(zhuǎn)換算法實(shí)施區(qū)域填充字符和矢量圖形的顯示反走樣基礎(chǔ)掃描線算法掃描線算法原理回顧求交排序交點(diǎn)配對區(qū)間填色X掃描線算法缺點(diǎn) 實(shí)際上一條掃描線只和少數(shù)邊相交，甚至沒有和任意邊相交，造成大量冗余計算。計算交點(diǎn)時提取所有邊與掃描線求交有序邊表算法－－活性邊表算法改進(jìn)原理：處理一條掃描線時，僅對與它相交的邊求交；利用掃描線的連貫性利用多邊形邊的連貫性

如一條掃描線排序后與多邊形邊的交點(diǎn)x坐標(biāo)依次是x0,x1,x2,…,x2n+1，則對特殊點(diǎn)處理后，(x2i,x2i+1)(i=0,…,n)組成的區(qū)間為多邊形內(nèi)的區(qū)間。

我們把與當(dāng)前掃描線相交的多邊形邊稱為活性邊(ActiveEdge，AE)多邊形邊的連貫性：某條邊和當(dāng)前掃描線相交時，它很可能也與下一條掃描線相交，并且交點(diǎn)坐標(biāo)遵循下面的規(guī)律。(xi,yi)(xi+dx,yi+1)11/k即對一條邊y=kx+b來說，如果當(dāng)前掃描線得到的交點(diǎn)為(xi,yi),則下一條掃描線交點(diǎn)為(xi+1/k,yi+1)直線方程y=kx+bdy/dx=k,即dx=dy/k微分形式：此時dy=1,則dx=1/k找到一條邊上前后掃描線交點(diǎn)的關(guān)系，如何加以利用？增量算法思想：掃描線改變時，同一條邊上的后一個交點(diǎn)，可以利用上一次求交點(diǎn)的結(jié)果，直接加上一個增量來得到。x的增量dx=1/k,y的增量dy=1使用一個數(shù)據(jù)結(jié)構(gòu)來表示與當(dāng)前掃描線相交的邊，掃描線改變時，只要相交邊－－活性邊不變，則不需要對該數(shù)據(jù)結(jié)構(gòu)中的內(nèi)容修改。有初始值，有算法結(jié)束的限制條件。對于任意一條相交邊

其交點(diǎn)的初始值為Y值小的端點(diǎn)；終止于Y值較大的端點(diǎn)。數(shù)據(jù)結(jié)構(gòu)：活性邊表（ActiveEdgeTable，AET） 把活性邊按照與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個鏈表中，該鏈表稱為活性邊表。活性邊表的結(jié)構(gòu)和存儲內(nèi)容：一個活性邊表對應(yīng)多個節(jié)點(diǎn)，一個節(jié)點(diǎn)對應(yīng)一條邊，多個節(jié)點(diǎn)之間按照x從小到大規(guī)則，進(jìn)行排序。x0ymax0next1/k0x1ymax1null1/k1具有兩條邊的活性鏈表活性邊表的操作根據(jù)邊的連貫性，當(dāng)前掃描線發(fā)生改變時：如果沒有新的活性邊加入，也沒有邊到達(dá)終點(diǎn)，此時新掃描線和邊相交的交點(diǎn)序列不發(fā)生改變。處理下一條掃描線時，如有新邊加入，則新邊需要作為新節(jié)點(diǎn)插入適當(dāng)位置適合插入排序。當(dāng)某個相交邊到達(dá)終點(diǎn)，則需要將該邊從活性邊表中刪除。邊表（EdgeTable，ET）/新邊表 對于每個掃描線，建立一個最小y坐標(biāo)位于該掃描線上的活性邊的鏈表，來表示從下到上掃描到該掃描線時，新增加的活性邊。全體掃描線就對應(yīng)了一個（新）邊表。

從下到上掃描過程中，只有下一條掃描線具有一個對應(yīng)的活性邊的鏈表時，才需要對當(dāng)前的活性邊表進(jìn)行插入新邊的操作。邊表的構(gòu)造

(1)首先構(gòu)造一個縱向線性表，表的長度為多邊形所占有的最大掃描線數(shù)，表的每個結(jié)點(diǎn)，稱為一個桶，對應(yīng)多邊形覆蓋的每一條掃描線。(2)每條邊的數(shù)據(jù)形成一個結(jié)點(diǎn)，內(nèi)容包括：該掃描線與該邊的初始交點(diǎn)x（即較低端點(diǎn)的x值），1/k，以及該邊的最大y值ymax。xymax1/kNEXT(4)同一桶中若干條邊按X由小到大排序，若X相等，則按照1/k由小到大排序。(3)將每條邊的對應(yīng)結(jié)點(diǎn)鏈入與該邊最小y坐標(biāo)（ymin）相對應(yīng)的桶處。也就是說，若某邊的較低端點(diǎn)為ymin，則該邊的結(jié)點(diǎn)就放在相應(yīng)的掃描線桶中。邊表構(gòu)造示例12111098765432137-1/3353/485-1/2891/2712-17951122/5邊表構(gòu)造示例y=8時，活性邊1.4122/5712-179511.591/2算法實(shí)現(xiàn)(1)初始化：構(gòu)造邊表ET，如果邊表為空則返回； 活性邊表AET置空；(2)初始化：將ET表中第一個非空桶中邊插入AET；(3)處理當(dāng)前掃描線：由AET表中取出交點(diǎn)對進(jìn)行 填充。(4)令yi+1=yi+1,刪除ymax=y的邊；(5)根據(jù)xi+1=xi+1/k計算并（通過排序）修改AET表， 同時將ET表中y=yi+1桶中的邊，按次序插入 到AET表中，形成下一條掃描線的新AET表；(6)AET表不為空則轉(zhuǎn)(3)，否則結(jié)束。算法演示活性邊表法優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：采用鏈表實(shí)現(xiàn)，節(jié)約存儲空間充分利用了邊連貫性和掃描線連貫性，減少了求交計算量，提高了排序的效率，從而大大減少了程序算法的復(fù)雜度。對顯示的每個像素只訪問一次，輸入輸出量少缺點(diǎn)：對鏈表的維持和排序開銷較大。不適合硬件實(shí)現(xiàn)。邊緣填充算法基本思想：對于每一條掃描線和每條多邊形邊的交點(diǎn)(xi,yi),將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。對多邊形的每條邊都依次處理一次，順序隨意。所有邊完成以后，像素結(jié)果即為該多邊形的填充區(qū)域。算法演示算法優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：該算法最適用于具有幀緩沖器的圖形系統(tǒng)，按任意順序處理多邊形的邊，在處理每條邊時，僅訪問與該邊相交的掃描線上交點(diǎn)右方的像素。當(dāng)所有邊處理完成后，直接按照掃描線順序讀出幀緩沖器的內(nèi)容，送入顯示設(shè)備。簡單，易于硬件實(shí)現(xiàn)。缺點(diǎn)：對于復(fù)雜圖形，每個像素被訪問多次，輸入輸出量過大。邊緣填充算法的改進(jìn)－－柵欄填充算法基本思想：柵欄－－一條與掃描線垂直的直線，通常取其位置過多邊形頂點(diǎn)，且把多邊形分成兩半。對于每個掃描線與邊的交點(diǎn)，將交點(diǎn)與柵欄之間的像素取補(bǔ)。算法演示算法優(yōu)缺點(diǎn)該算法相比邊緣填充算法，減少了像素的重復(fù)訪問數(shù)量，但仍然有很多像素被重復(fù)訪問。邊標(biāo)志法基本思想：首先，對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，即對多邊形邊界所經(jīng)過的像素，打上邊標(biāo)志；然后，對每條與多邊形相交的掃描線，逐個訪問該掃描線上的像素，使用一個Bool量Inside來指示當(dāng)前點(diǎn)的狀態(tài)，以取值為真表示點(diǎn)在多邊形內(nèi)部。掃描開始時，Inside初始值為假，每當(dāng)遇到打上了邊標(biāo)志的像素，則對Inside取反。Inside取值為真的像素全部為多邊形內(nèi)部需要著色的像素。算法演示錯誤處理對于局部極值點(diǎn)，掃描線與多邊形的相交次數(shù)是奇數(shù)，填充時會出現(xiàn)“抽絲”現(xiàn)象。即某掃描線上不該填充的區(qū)段填上色，而應(yīng)該填充的區(qū)段卻沒有填上色。當(dāng)掃描線y遇到斜率小于1的邊界線時，會連續(xù)碰到幾個邊界點(diǎn)，引起標(biāo)志的無序改變，導(dǎo)致填充的錯誤。解決辦法：判斷多邊形頂點(diǎn)的性質(zhì)，如果是局部極值點(diǎn)，那么掃描線碰上它則不改變標(biāo)志（可以建立邊表）。解決辦法：對于不同斜率的邊界，都要使用斜率大于1的直線掃描轉(zhuǎn)換方法：每次y方向增長一步，x方向增長1/m步距，以保證掃描線y遇到斜率小于1的邊界時，只能遇到一個點(diǎn)。該算法與有序邊表算法的比較：使用軟件實(shí)現(xiàn)時，兩者執(zhí)行速度幾乎相同。邊標(biāo)志法在直接使用硬件實(shí)現(xiàn)時，因?yàn)椴恍枰⒑途S護(hù)邊表以及排序的運(yùn)算，其執(zhí)行速度比有序邊表算法快的多。1.多邊形的掃描轉(zhuǎn)換2.區(qū)域填充3.字符和矢量圖形的顯示4.反走樣基礎(chǔ)2.區(qū)域填充2.1區(qū)域的定義區(qū)域是指已經(jīng)表示成點(diǎn)陣形式的填充圖形，是一個像素集合。2.區(qū)域填充2.2區(qū)域填充和掃描線填充算法的區(qū)別區(qū)域填充－－假設(shè)區(qū)域內(nèi)部至少有一個像素，其顏色已經(jīng)給定，由此出發(fā)找到區(qū)域內(nèi)的所有像素并填充顏色。所處理的對象是點(diǎn)陣表示的區(qū)域。掃描線算法則沒有對刷新緩沖器的初始值有任何假設(shè)。所處理的是幾何表示的多邊形。2.3區(qū)域的表示邊界表示法：把位于給定區(qū)域的邊界上的像素一一列舉出來的方法，此時區(qū)域外部像素取值可以和內(nèi)部一樣，但不能和邊界像素一樣枚舉出區(qū)域內(nèi)所有像素的表示方法稱為內(nèi)點(diǎn)表示法2.區(qū)域填充像素的4-鄰接點(diǎn)和8-鄰接點(diǎn)

一個結(jié)論4-連通區(qū)域的邊界是8-連通的：邊界點(diǎn)可以通過8-鄰接點(diǎn)遍歷反之，8-連通區(qū)域的邊界是4-連通的：邊界點(diǎn)可以通過4-鄰接點(diǎn)遍歷2.區(qū)域填充2.4邊界填充算法算法思想：從內(nèi)部一個種子像素出發(fā)，通過四連通（四向算法）或者八連通方向（八向算法）對所有像素進(jìn)行遍歷和著色操作，直到所有像素都完成著色操作為止。邊界填充算法實(shí)現(xiàn)（4-鄰接點(diǎn)）需要的數(shù)據(jù)結(jié)構(gòu)堆棧：后進(jìn)先出。123首先，種子像素入棧，然后，當(dāng)棧頂元素非空時，重復(fù)執(zhí)行下面的操作：(1)棧頂像素出棧；(2)將出棧像素置成填充色；(3)檢查出棧像素的4-鄰接點(diǎn)，若其中某個像素點(diǎn)不是邊界色且未置成多邊形色，則把該像素入棧。返回到(1)。算法演示算法輸入的初始數(shù)據(jù)：種子點(diǎn)坐標(biāo)，填充色，邊界像素顏色。算法具體實(shí)現(xiàn)種子填充算法實(shí)現(xiàn)（8-鄰接點(diǎn)）算法演示種子填充算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：可以填充帶有內(nèi)孔的區(qū)域缺點(diǎn)：太多的像素被壓入堆棧，同一像素被重復(fù)入棧。種子算