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

1、多邊形的掃描轉(zhuǎn)換l算法實施區(qū)域填充字符和矢量圖形的顯示反走樣基礎(chǔ)l掃描線算法原理回顧l求交l排序l交點(diǎn)配對l區(qū)間填色lX掃描線算法缺點(diǎn) 實際上一條掃描線只和少數(shù)邊相交，甚至沒有和任意邊相交，造成大量冗余計算。l計算交點(diǎn)時提取所有邊與掃描線求交l有序邊表算法活性邊表算法l改進(jìn)原理：l處理一條掃描線時，僅對與它相交的邊求交；l利用掃描線的連貫性l利用多邊形邊的連貫性如一條掃描線排序后與多邊形邊的交點(diǎn)x坐標(biāo)依次是x0, x1, x2,x2n+1，則對特殊點(diǎn)處理后，(x2i, x2i+1)(i=0,n)組成的區(qū)間為多邊形內(nèi)的區(qū)間。我們把與當(dāng)前掃描線相交的多邊形邊稱為活性邊(Active Edge，AE

2、)l多邊形邊的連貫性：l某條邊和當(dāng)前掃描線相交時，它很可能也與下一條掃描線相交，并且交點(diǎn)坐標(biāo)遵循下面的規(guī)律。(xi, yi)(xi+dx, yi+1)11/kl即對一條邊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)系，如何加以利用？l增量算法思想：l掃描線改變時，同一條邊上的后一個交點(diǎn)，可以利用上一次求交點(diǎn)的結(jié)果，直接加上一個增量來得到。x的增量dx =1/k, y的增量dy=1 l使用一個數(shù)據(jù)

3、結(jié)構(gòu)來表示與當(dāng)前掃描線相交的邊，掃描線改變時，只要相交邊活性邊不變，則不需要對該數(shù)據(jù)結(jié)構(gòu)中的內(nèi)容修改。l有初始值，有算法結(jié)束的限制條件。對于任意一條相交邊其交點(diǎn)的初始值為Y值小的端點(diǎn)；終止于Y值較大的端點(diǎn)。l數(shù)據(jù)結(jié)構(gòu)：l活性邊表（Active Edge Table， AET） 把活性邊按照與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個鏈表中，該鏈表稱為活性邊表。l活性邊表的結(jié)構(gòu)和存儲內(nèi)容：l一個活性邊表對應(yīng)多個節(jié)點(diǎn)，一個節(jié)點(diǎn)對應(yīng)一條邊，多個節(jié)點(diǎn)之間按照x從小到大規(guī)則，進(jìn)行排序。x0 ymax0next1/k0 x1 ymax1null1/k1具有兩條邊的活性鏈表l活性邊表的操作根據(jù)邊的連貫性，當(dāng)前掃描

4、線發(fā)生改變時：l如果沒有新的活性邊加入，也沒有邊到達(dá)終點(diǎn)，此時新掃描線和邊相交的交點(diǎn)序列不發(fā)生改變。l處理下一條掃描線時，如有新邊加入，則新邊需要作為新節(jié)點(diǎn)插入適當(dāng)位置適合插入排序。l當(dāng)某個相交邊到達(dá)終點(diǎn)，則需要將該邊從活性邊表中刪除。l邊表（Edge Table， ET）/新邊表 對于每個掃描線，建立一個最小y坐標(biāo)位于該掃描線上的活性邊的鏈表，來表示從下到上掃描到該掃描線時，新增加的活性邊。全體掃描線就對應(yīng)了一個（新）邊表。 從下到上掃描過程中，只有下一條掃描線具有一個對應(yīng)的活性邊的鏈表時，才需要對當(dāng)前的活性邊表進(jìn)行插入新邊的操作。l邊表的構(gòu)造(1)首先構(gòu)造一個縱向線性表，表的長度為多邊形所

5、占有的最大掃描線數(shù)，表的每個結(jié)點(diǎn)，稱為一個桶，對應(yīng)多邊形覆蓋的每一條掃描線。(2)每條邊的數(shù)據(jù)形成一個結(jié)點(diǎn)，內(nèi)容包括：該掃描線與該邊的初始交點(diǎn)x（即較低端點(diǎn)的x值），1/k，以及該邊的最大y值ymax。x ymax 1/k NEXT(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)的掃描線桶中。xy213 4 5 6 7 8 9111234567891011121012p1p3p4p5(a) 多邊形P0P1P2P3P4P5P6P0p2p0

6、p6邊表構(gòu)造示例12111098765432137-1/3353/485-1/2891/27 12-17951 122/5邊表構(gòu)造示例xy213 4 5 6 7 8 9111234567891011121012(a) 多邊形P0P1P2P3P4P5P6P0ly=8時，活性邊1.4122/5712-179511.5 91/2l算法實現(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

7、計算并（通過排序）修改AET表，同時將ET表中y=yi+1桶中的邊，按次序插入到AET表中，形成下一條掃描線的新AET表；(6)AET表不為空則轉(zhuǎn)(3)，否則結(jié)束。算法演示l活性邊表法優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：l采用鏈表實現(xiàn)，節(jié)約存儲空間l充分利用了邊連貫性和掃描線連貫性，減少了求交計算量，提高了排序的效率，從而大大減少了程序算法的復(fù)雜度。l對顯示的每個像素只訪問一次，輸入輸出量少缺點(diǎn)：l對鏈表的維持和排序開銷較大。l不適合硬件實現(xiàn)。l邊緣填充算法l基本思想：l對于每一條掃描線和每條多邊形邊的交點(diǎn)(xi, yi), 將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。對多邊形的每條邊都依次處理一次，順序隨意。所有邊完成

8、以后，像素結(jié)果即為該多邊形的填充區(qū)域。算法演示l算法優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：l該算法最適用于具有幀緩沖器的圖形系統(tǒng)，按任意順序處理多邊形的邊，在處理每條邊時，僅訪問與該邊相交的掃描線上交點(diǎn)右方的像素。當(dāng)所有邊處理完成后，直接按照掃描線順序讀出幀緩沖器的內(nèi)容，送入顯示設(shè)備。簡單，易于硬件實現(xiàn)。缺點(diǎn)：l對于復(fù)雜圖形，每個像素被訪問多次，輸入輸出量過大。l邊緣填充算法的改進(jìn)柵欄填充算法l基本思想：l柵欄一條與掃描線垂直的直線，通常取其位置過多邊形頂點(diǎn)，且把多邊形分成兩半。l對于每個掃描線與邊的交點(diǎn)，將交點(diǎn)與柵欄之間的像素取補(bǔ)。算法演示l算法優(yōu)缺點(diǎn)l該算法相比邊緣填充算法，減少了像素的重復(fù)訪問數(shù)量，但仍然有很

9、多像素被重復(fù)訪問。l邊標(biāo)志法l基本思想：l首先，對多邊形的每條邊進(jìn)行直線掃描轉(zhuǎn)換，即對多邊形邊界所經(jīng)過的像素，打上邊標(biāo)志；l然后，對每條與多邊形相交的掃描線，逐個訪問該掃描線上的像素，使用一個Bool量Inside來指示當(dāng)前點(diǎn)的狀態(tài)，以取值為真表示點(diǎn)在多邊形內(nèi)部。l掃描開始時，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ù)碰

10、到幾個邊界點(diǎn)，引起標(biāo)志的無序改變，導(dǎo)致填充的錯誤。解決辦法：判斷多邊形頂點(diǎn)的性質(zhì)，如果是局部極值點(diǎn)，那么掃描線碰上它則不改變標(biāo)志（可以建立邊表）。解決辦法：對于不同斜率的邊界，都要使用斜率大于1的直線掃描轉(zhuǎn)換方法：每次y方向增長一步，x方向增長1/m步距，以保證掃描線y遇到斜率小于1的邊界時，只能遇到一個點(diǎn)。l該算法與有序邊表算法的比較：l使用軟件實現(xiàn)時，兩者執(zhí)行速度幾乎相同。l邊標(biāo)志法在直接使用硬件實現(xiàn)時，因為不需要建立和維護(hù)邊表以及排序的運(yùn)算，其執(zhí)行速度比有序邊表算法快的多。1. 多邊形的掃描轉(zhuǎn)換2. 區(qū)域填充3. 字符和矢量圖形的顯示4. 反走樣基礎(chǔ)l2.1 區(qū)域的定義l區(qū)域是指已經(jīng)表示

11、成點(diǎn)陣形式的填充圖形，是一個像素集合。l2.2 區(qū)域填充和掃描線填充算法的區(qū)別l區(qū)域填充假設(shè)區(qū)域內(nèi)部至少有一個像素，其顏色已經(jīng)給定，由此出發(fā)找到區(qū)域內(nèi)的所有像素并填充顏色。所處理的對象是點(diǎn)陣表示的區(qū)域。l掃描線算法則沒有對刷新緩沖器的初始值有任何假設(shè)。所處理的是幾何表示的多邊形。l2.3 區(qū)域的表示l邊界表示法：把位于給定區(qū)域的邊界上的像素一一列舉出來的方法，此時區(qū)域外部像素取值可以和內(nèi)部一樣，但不能和邊界像素一樣l枚舉出區(qū)域內(nèi)所有像素的表示方法稱為內(nèi)點(diǎn)表示法44p44(b)p的8-鄰接點(diǎn)8 8 888p88 8(a)p的4-鄰接點(diǎn)鄰接點(diǎn)的定義圖5-32 區(qū)域的邊界表示和內(nèi)點(diǎn)表示(a)以邊界表

12、示的4-連通區(qū)域(b)以內(nèi)點(diǎn)表示的4-連通區(qū)域(c)以邊界表示的8-連通區(qū)域(d)以內(nèi)點(diǎn)表示的8-連通區(qū)域l一個結(jié)論l4-連通區(qū)域的邊界是8-連通的：邊界點(diǎn)可以通過8-鄰接點(diǎn)遍歷l反之，8-連通區(qū)域的邊界是4-連通的：邊界點(diǎn)可以通過4-鄰接點(diǎn)遍歷l2.4 邊界填充算法l算法思想：從內(nèi)部一個種子像素出發(fā)，通過四算法思想：從內(nèi)部一個種子像素出發(fā)，通過四連通（四向算法）或者八連通方向（八向算法）連通（四向算法）或者八連通方向（八向算法）對所有像素進(jìn)行遍歷和著色操作，直到所有像對所有像素進(jìn)行遍歷和著色操作，直到所有像素都完成著色操作為止。素都完成著色操作為止。l邊界填充算法實現(xiàn)（4-鄰接點(diǎn)）l需要的數(shù)

13、據(jù)結(jié)構(gòu)需要的數(shù)據(jù)結(jié)構(gòu)l堆棧：后進(jìn)先出。堆棧：后進(jìn)先出。123l首先，種子像素入棧，然后，當(dāng)棧頂元素非空首先，種子像素入棧，然后，當(dāng)棧頂元素非空時，重復(fù)執(zhí)行下面的操作：時，重復(fù)執(zhí)行下面的操作：(1)棧頂像素出棧；棧頂像素出棧；(2)將出棧像素置成填充色；將出棧像素置成填充色；(3)檢查出棧像素的檢查出棧像素的4-鄰接點(diǎn)，若其中某個鄰接點(diǎn)，若其中某個像素點(diǎn)不是邊界色且未置成多邊形色，則像素點(diǎn)不是邊界色且未置成多邊形色，則把該像素入棧。返回到把該像素入棧。返回到(1)。算法演示l算法輸入的初始數(shù)據(jù)：算法輸入的初始數(shù)據(jù)： 種子點(diǎn)坐標(biāo)，填充色，邊界像素顏色。種子點(diǎn)坐標(biāo)，填充色，邊界像素顏色。l算法具體實現(xiàn)算法具體實現(xiàn)l種子填充算法實現(xiàn)（8-鄰接點(diǎn)）算法演示l種子填充算法的優(yōu)缺點(diǎn)l優(yōu)點(diǎn)：可以填充帶有內(nèi)孔的區(qū)域l缺點(diǎn)：太多的像素被壓入堆棧