計算機圖形學(xué) 第四章 光柵轉(zhuǎn)化與消隱(1)課件

1、圖形的光柵轉(zhuǎn)化1內(nèi)容基本概念區(qū)域填充多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充的比較2內(nèi)容基本概念區(qū)域填充多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充的比較3光柵圖形的基本概念線框多邊形物體填充多邊形物體5關(guān)于平面多邊形圖形學(xué)中的多邊形：無自相交的簡單多邊形圖形學(xué)中多邊形的兩種表示方式頂點表示：用多邊形的有序頂點序列表示多邊形點陣表示：用位于多邊形內(nèi)部的像素集合來表示多邊形光柵圖形的基本概念6頂點表示優(yōu)點直觀幾何意義明顯存貯量小不足難以判斷哪些像素位于多邊形內(nèi)部不能直接用于多邊形著色?多邊形的頂點表示7點陣表示優(yōu)點便于用幀緩沖器(frame buffer)表示圖形面著色所需的圖形表示缺點丟失了幾

2、何信息占用存儲空間多多邊形的點陣表示8主要內(nèi)容基本概念區(qū)域填充四連通區(qū)域和八連通區(qū)域連通區(qū)域的種子填充算法多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充的比較104.1 區(qū)域填充 區(qū)域是指已經(jīng)表示成點陣形式的像素集合。在光柵圖形中，區(qū)域可采用內(nèi)點表示和邊界表示兩種形式進行描述。1、內(nèi)點表示法：把位于給定區(qū)域內(nèi)的所有像素一一列舉出來的方法稱為內(nèi)點表示法。2、邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。1、 區(qū)域的表示和類型圖3.22 內(nèi)點表示的區(qū)域 圖3.23 邊界表示的區(qū)域12 3） 4連通區(qū)域也可理解成8連通區(qū)域，即4連通能達到的8連通肯定能達到，4連通只是8連通的一

3、種特殊情況。連通不是指邊界而是邊界內(nèi)的區(qū)域這里是X圍起來的區(qū)域號是區(qū)域X是邊界8連通而非4連通的地方內(nèi)點表示的八連通區(qū)域邊界表示的八連通區(qū)域14 但是兩者的邊界不盡相同。如果圖中標有號的像素組成的區(qū)域作為4連通區(qū)域，則其邊界由圖中的標有號的像素組成。如果將該區(qū)域作為8連通的區(qū)域，則其邊界由圖中標有號和號的兩種像素組成。 四連通區(qū)域與八連通區(qū)域的不同邊界因為如果區(qū)域是8連通的，邊界不能將區(qū)域有效封堵，X的位置和區(qū)域也是連通的。 用于八連通區(qū)域的填充算法可用于四連通區(qū)域的填充，但用于四連通區(qū)域的填充算法并不適用于八連通區(qū)域的填充。 15區(qū)域的類型四連通區(qū)域 八連通區(qū)域 16內(nèi)部表示區(qū)域種子填充算法

4、假設(shè)內(nèi)部表示區(qū)域為G，其中的像素原有顏色為G0，需要填充的顏色為G1。算法需要提供一個種子點(x,y)，它的顏色為G0。具體算法如下(四連通區(qū)域)17內(nèi)部表示區(qū)域種子填充算法Flood_Fill_4(x, y, G0, G1)if(GetPixel(x,y) =G0 ) / GetPixel(x,y) 返回(x,y)的顏色SetPixel(x, y, G1); /將(x,y)的添上顏色G1 Flood_Fill_4(x-1, y, G0, G1);Flood_Fill_4(x, y+1, G0, G1); Flood_Fill_4(x+1, y, G0, G1); Flood_Fill_4(x

5、, y-1, G0, G1);18內(nèi)容基本概念區(qū)域填充多邊形的掃描轉(zhuǎn)換逐點判斷算法掃描線算法連貫性概念：區(qū)域、掃描線、邊奇異點的處理算法的數(shù)據(jù)結(jié)構(gòu)與實現(xiàn)多邊形的掃描轉(zhuǎn)換與區(qū)域填充的比較201、表示方法：頂點表示和點陣表示1）頂點表示是用多邊形的頂點的序列來描述多邊形，該表示幾何意義強、占內(nèi)存少，但它不能直觀地說明哪些像素在多邊形內(nèi)。2）點陣表示是用位于多邊形內(nèi)的像素的集合來描述多邊形，該方法雖然沒有多邊形的幾何信息，但具有面著色所需要的圖像表示形式。4.2 多邊形的掃描轉(zhuǎn)換 多邊形頂點表示P1P0P2P3P4 多邊形點陣表示 多邊形的掃描轉(zhuǎn)換就是把多邊形的頂點表示轉(zhuǎn)換為點陣表示，即從多邊形的給

6、定邊界出發(fā)，求出位于其內(nèi)部的各個像素，并為幀緩存內(nèi)的各個對應(yīng)元素設(shè)置相應(yīng)的灰度或顏色。21逐點判斷算法判斷一點是否位于多邊形內(nèi)部？23逐點判斷算法算法描述for(y=0; y=y_resolution; y+)for(x=0; x=x_resolution; x+)if(inside(polygon, x+0.5, y+0.5)setpixel(framebuffer,x,y,polygon_color)elsesetpixel(framebuffer,x,y,background_color)241、掃描線算法 區(qū)域連貫性掃描線連貫性邊的連貫性?；舅枷?先求出掃描線與多邊形邊的交點，利用掃

7、描線的連續(xù)性求出多邊形與掃描線相交的連續(xù)區(qū)域，然后利用多邊形邊的連續(xù)性，求出下一條掃描線與多邊形的交點，對所有掃描線由下到上依次處理。 掃描線算法是按掃描線的順序計算出掃描線與多邊形的相交區(qū)間，然后用要求的顏色填充這些區(qū)間內(nèi)的像素。4.2.1 多邊形掃描轉(zhuǎn)換的連貫性特點：充分利用了相鄰像素之間的連續(xù)性，避免對像素的逐點判斷和反 復(fù)求交運算，減少了計算量，提高了算法速度。26區(qū)域連貫性兩條掃描線之間的長方形區(qū)域被所處理的多邊形分割成若干梯形(三角形可以看作退化梯形)梯形的底邊為掃描線，梯形的腰為多邊形的邊或窗口邊緣梯形分為兩類：多邊形內(nèi)部和多邊形外部兩類梯形在多邊形內(nèi)部相間排列(相鄰的兩個梯形必

8、然有一個位于多邊形內(nèi)部，有一個在多邊形外部)區(qū)域的連貫性是指多邊形定義的區(qū)域內(nèi)部相鄰的像素具有相同的性質(zhì)。例如具有相同的顏色推論：如果上述梯形屬于多邊形內(nèi)(外)，那么該梯形內(nèi)所有點的均屬于多邊形內(nèi)(外)。效率提高的根源：逐點判斷區(qū)域判斷27掃描線連貫性交點序列：掃描線與多邊形的交點個數(shù)為偶數(shù)(1,2,3,4,5,6)紅色區(qū)間(1,2)、(3,4)、(5,6)位于多邊形內(nèi)部其余綠色區(qū)間位于多邊形外部兩類區(qū)間相間排列區(qū)域連貫性在一條掃描線上的反映推論：如果上述交點區(qū)間屬于多邊形內(nèi)(外)，那么該區(qū)間內(nèi)所有點均屬于多邊形內(nèi)(外)。效率提高的根源：逐點判斷區(qū)間判斷28邊的連貫性相鄰掃描線(y1=y11+

9、1)與多邊形的同一條邊的交點存在如下關(guān)系：當知道掃描線與一條邊的一個交點之后，通過上述公式可以通過增量算法迅速求出其他交點 推論：邊的連貫性是連接區(qū)域連貫性和掃描線連貫性的紐帶。掃描線連貫性“”邊連貫性“”區(qū)域連貫性304.2.2 多邊形掃描轉(zhuǎn)換算法 核心思想(從下到上掃描)計算掃描線 y = ymin與多邊形的交點，通常這些交點由多邊形的頂點組成根據(jù)多邊形邊的連貫性，按從下到上的順序求得各條掃描線的交點序列根據(jù)區(qū)域和掃描線的連貫性判斷位于多邊形內(nèi)部的區(qū)段對位于多邊形內(nèi)的直線段進行著色31多邊形掃描轉(zhuǎn)換算法P0P1P2P3P4P5P6P7xy掃描轉(zhuǎn)換示意圖32多邊形掃描轉(zhuǎn)換算法為了實現(xiàn)上述思想

10、，算法中需要采取靈活的數(shù)據(jù)結(jié)構(gòu)。分類的邊表ET (Sorted Edge Table)：記錄多邊形信息活化邊鏈表AEL (Active Edge List) ：記錄當前掃描線信息它們共同基礎(chǔ)是邊的數(shù)據(jù)結(jié)構(gòu)33邊的數(shù)據(jù)結(jié)構(gòu)邊的數(shù)據(jù)結(jié)構(gòu)ymax：邊的上端點的y坐標x：邊的下端點x坐標，在活化邊鏈表中，表示掃描線與邊的交點的x坐標dx：邊的斜率的倒數(shù)next：指向下一條邊的指針 34邊的數(shù)據(jù)結(jié)構(gòu)實例35分類的邊表 (ET)分類的邊表是按邊的下端點的縱坐標y對非水平邊進行分類的指針數(shù)組下端點的縱坐標y值等于i的邊，歸入第i類同一類中，各邊按x值( x值相等時，按dx的值)遞增的順序排成行水平邊不加入分

11、類邊表中 36分類的邊表實例37活化邊鏈表(AEL)活化鏈表由與當前掃描線相交的邊組成記錄了多邊形的邊沿掃描線的交點序列根據(jù)邊的連貫性不斷刷新交點序列基本單元是邊(與掃描線相交的邊)與分類邊表不同分類邊表記錄初始狀態(tài)活化邊表隨掃描線的移動而動態(tài)更新38活化邊鏈表實例ymax xcur dx與分類邊表的區(qū)別39多邊形掃描轉(zhuǎn)換算法(y初始化) 取掃描線縱坐標y的初始值為ET中非空元素的最小序號 (y=2)40多邊形掃描轉(zhuǎn)換算法(AEL初始化) 將邊的活化鏈表AEL設(shè)置為空 按從下到上的順序?qū)v坐標值為y的掃描線(當前掃描線)執(zhí)行如下步驟，直到分類邊表ET和邊的活化鏈表AEL都變成空為止41多邊形掃

12、描轉(zhuǎn)換算法如果分類邊表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表AEL中(同時將ET中相應(yīng)的邊表刪除)，AEL中的各邊按照x值(x值相等時，按dx值)遞增方向排序；若對于當前掃描線，邊的活化鏈表非空，則將AEL中的邊交點兩兩依次配對。每一對邊與當前掃描線的交點區(qū)間位于多邊形內(nèi)部，依次對這些區(qū)間上的像素按多邊形屬性著色；42多邊形掃描轉(zhuǎn)換算法將邊的活化鏈表AEL中滿足y=ymax的邊刪除；將邊的活化鏈表AEL中剩下的每一條邊的x累加dx，即：x=x+dx;將當前掃描線的縱坐標值y累加，即y=y+1。43多邊形掃描轉(zhuǎn)換實例44多邊形掃描轉(zhuǎn)換實例45多邊形掃描轉(zhuǎn)換實例

13、46多邊形掃描轉(zhuǎn)換實例47多邊形掃描轉(zhuǎn)換實例48多邊形掃描轉(zhuǎn)換實例49多邊形掃描轉(zhuǎn)換實例50多邊形掃描轉(zhuǎn)換實例51多邊形掃描轉(zhuǎn)換實例52多邊形掃描轉(zhuǎn)換實例53多邊形掃描轉(zhuǎn)換實例54多邊形掃描轉(zhuǎn)換優(yōu)點充分利用多邊形的區(qū)域、掃描線和邊的連貫性，避免了反復(fù)求交的大量運算不足算法的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)復(fù)雜對各種表的維持和排序開銷太大，適合軟件實現(xiàn)而不適合硬件實現(xiàn)55內(nèi)容基本概念區(qū)域填充多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換與區(qū)域填充的比較56多邊形掃描轉(zhuǎn)換與區(qū)域填充比較基本思想不同多邊形掃描轉(zhuǎn)換將多邊形頂點表示轉(zhuǎn)換為點陣表示，掃描過程利用了多邊形的各種連貫性區(qū)域填充只改變區(qū)域的顏色，不改變區(qū)域的表示方法。填充

14、過程利用了區(qū)域的連貫性57多邊形掃描轉(zhuǎn)換與區(qū)域填充比較對邊界的要求不同多邊形掃描轉(zhuǎn)換只要求每一條掃描線與多邊形有偶數(shù)個交點區(qū)域填充中四連通區(qū)域必須是封閉的八連通邊界八連通區(qū)域必須是封閉的四連通邊界58多邊形掃描轉(zhuǎn)換與區(qū)域填充比較多邊形掃描轉(zhuǎn)換允許邊界區(qū)域填充允許邊界對邊界的要求不同多邊形掃描轉(zhuǎn)換只要求每一條掃描線與多邊形有偶數(shù)個交點區(qū)域填充中四連通區(qū)域必須是封閉的八連通邊界八連通區(qū)域必須是封閉的四連通邊界59多邊形掃描轉(zhuǎn)換與區(qū)域填充比較出發(fā)點不同區(qū)域填充：知道需要區(qū)域內(nèi)一個種子點(復(fù)雜計算)多邊形掃描轉(zhuǎn)換：沒有要求60總結(jié)基本概念區(qū)域填充四連通區(qū)域和八連通區(qū)域連通區(qū)域的種子填充算法多邊形的掃描

15、轉(zhuǎn)換逐點判斷算法掃描線算法區(qū)域、掃描線、邊的連貫性奇異點的處理數(shù)據(jù)結(jié)構(gòu)與算法實現(xiàn)多邊形的掃描轉(zhuǎn)換與區(qū)域填充的比較61具體例子 圖2和3是圖1中多邊形 的新邊表NEL和活性邊表AEL。在左圖中 表示邊 ，各頂點為 P0P1P6=(2,5)(2,10)(9,6) (16,9)(16,4)(12,2)(7,2) 其中， 是非極值點，在分類前已對邊 作了預(yù)處理，即分別在 處把它們截去一個單位長，這樣保證掃描線 只和 兩邊中的一邊相交，求得一個交點， 是水平邊，不參加分類。 圖3.17 邊形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e662-5/3516/3AELe0

16、e54214AEL在y=3掃描線上的狀態(tài)AEL-5/3511/3e0e54216AEL在y=4掃描線上的狀態(tài)AEL-5/35 2e0e49016AEL在y=5掃描線上的狀態(tài) 010 2e1e210-7/411/2AEL在y=8掃描線上的狀態(tài)AEL 97/341/3e3 9016e4圖3.18 新邊表NEL123456e11002xxymaxnexte49016e54212圖3.17 多邊形P0P1P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e6e2109-7/4e3997/357e0-5/363 如圖所示的多邊形，若采用改進的有效邊表算法進行填充，在填充時采用“下閉上

17、升”的原則（即刪除y=ymax的邊之后再填充）試畫出該多邊形的ET表和當掃描線Y=3和Y=8時的AET表。6465作業(yè) 已知一多邊形如圖，其中P1=(2,2),P2=(5,10),P3=(11,3), P4=(11,8),P5=(5,5),P6=(2,7),請寫出其新邊表的數(shù)據(jù)結(jié)構(gòu)。6667P0P1P2P3P4P5P6對于圖所示的多邊形，頂點表示法為：P0（7,8）, P1（3,12）,P2（1,7）,P3（3,1）, P4（6,5）,P5（8,1）,P6（12,9）。試寫出每條掃描線的有效邊表。作業(yè)68 掃描線的最大值為Smax12，最小值為Smin1，共有12條掃描線，每條掃描線之間間隔1個像素單位。每條掃描線的有效邊表為如圖418所示。6970 這條掃描線處理完畢后 對于P3P4和P4P5兩條邊，因