1、計算機圖形學第三章第三章 基本光柵圖形算法基本光柵圖形算法本章內容1直線的掃描轉換2圓的掃描轉換3多邊形的掃描轉換多邊形的掃描轉換4區域填充區域填充5光柵圖形的反走樣算法光柵圖形的反走樣算法22014-2015-1:CG:SCUEC多邊形的掃描轉換v 什么是多邊形的掃描轉換？ 把多邊形的頂點表示轉化為點陣表示，也就是從多邊形的給定邊界出發，求出位于其內部的各個像素，并給幀緩沖器內各個對應元素設置相應的灰度和顏色 多邊形的掃描轉換過程，實際上是給多邊形包圍的區域著色的過程圖圖1 1 多邊形的頂點表示多邊形的頂點表示P0P1P2P3P4 圖圖2 2 多邊形的點陣表示多邊形的點陣表示v 多邊形的表示

2、方法頂點表示: 用多邊形的頂點序列來刻劃多邊形 該表示方法幾何意義強、占內存少 不能明確指出哪些像素在多邊形內，不能直接用于面著色點陣表示: 用位于多邊形內的象素的集合來刻劃多邊形 該方法便于利用幀緩沖器表示圖形，是面著色所需要的圖形表示形式 失去了許多重要的幾何信息32014-2015-1:CG:SCUEC為什么研究圖形的掃描轉換與區域填充？哪個長方形在前，哪個在后？哪個長方形在前，哪個在后？v 與單純由線條所構成的線畫圖形相比，采用面著色繪制的光柵圖形顯得更為生動、直觀，真實感更強v 面著色可以使使光柵圖形的畫面明暗自然,色彩豐富,形象逼真,具有真實感42014-2015-1:CG:SCU

3、EC逐點判斷法v 逐點判斷是實現多邊形掃描轉換最簡單的方法 逐個像素判別，確定它們是否在多邊形內，從而給出位于多邊形內的點（像素）的集合#define MAX 100typedef struct int VertexNum; / 多邊形頂點個數多邊形頂點個數 Point VerticesMAX /多邊形頂點數組多邊形頂點數組 Polygon / 多邊形多邊形52014-2015-1:CG:SCUECvoid FillPolygonPbyP(Polygon P) int x, y; for(x = xmin; x = xmax; x+) for(y = xmin; y e, d y k+1, 那

4、那么掃描線么掃描線d與上述邊也是相交的，與上述邊也是相交的，交點交點橫坐標遞增序列記為橫坐標遞增序列記為leieieieixxxx,321123,didididihxxxx 對同一條邊，前一條掃描線對同一條邊，前一條掃描線e與該邊與該邊的交點為的交點為xeir，而后一條掃描線，而后一條掃描線d=e+1與該邊的交點則為與該邊的交點則為xdir= xeir +1/m ，如右圖所示。如右圖所示。 以上性質稱為以上性質稱為邊的連續性。邊的連續性。122014-2015-1:CG:SCUEC存在的問題上述三種形式的連續性都基于一個幾何事實：每一條掃描線與多上述三種形式的連續性都基于一個幾何事實：每一條掃

5、描線與多邊形邊形P 的邊界的交點個數都是偶數（包括零）。的邊界的交點個數都是偶數（包括零）。但是當掃描線與多邊形但是當掃描線與多邊形P 的邊界的交點恰好是的邊界的交點恰好是P的頂點時：如果的頂點時：如果把每一奇點簡單地計為一個交點，則交點個數可能出現奇數（如把每一奇點簡單地計為一個交點，則交點個數可能出現奇數（如下圖中的掃描線下圖中的掃描線7的情況）；若將每一奇點都簡單地計為兩個交的情況）；若將每一奇點都簡單地計為兩個交點，同樣會導致反常的結果（如下圖中掃描線點，同樣會導致反常的結果（如下圖中掃描線2的情況）。的情況）。掃描線1掃描線2掃描線7EFGx123459681171012012345

6、67yP1P2P3P4P5P6(2,2)(2,2)(5,1)(5,1)(11,3)(11,3)(2,7)(2,7)(5,5)(5,5)(11,8)(11,8)132014-2015-1:CG:SCUEC多邊形頂點的分類設多邊形P 的頂點為 這些頂點可分為兩類：極值點和非極值點。如果 ，則稱頂點 為極值點（如下圖中的 ）；否則稱 為非極值點（如下圖中的 ）。, 1 , 0),(niyxPiii0)(11iiiiyyyyiP123568,P P P P P PiP047,P P PP0P1P2P3P4P5P6P7多邊形頂點的分類多邊形頂點的分類P8142014-2015-1:CG:SCUEC奇點的

7、處理 為了使交點個數保持為偶數，規定當奇點是P的極值點時，該點按兩個交點計算；否則按一個交點計算。 預處理: 若Pi是非極值點，則將 兩邊中位于掃描線y = yi上方的那條邊在Pi點處截去一單位長。11,iiiippppPiyi-1y = yiyi+1Piyi-1y = yiyi+1非極值點的處理非極值點的處理152014-2015-1:CG:SCUEC算法的實現步驟對于每一條掃描線，多邊形的掃描轉換可分為以下4步： 求交點：計算掃描線與多邊形各邊的交點，設交點個數為n。 交點排序：把所有的交點按x值遞增的順序進行排列。 交點配對：將排序后的第1個與第2個交點，第3個與第4個交點，第n-1個與

8、第n個交點配對，每對交點就代表掃描線與多邊形的一個相交區間。 區間填色：把相交區間內的像素置成多邊形的顏色，相交區間外的像素置成背景色。1234162014-2015-1:CG:SCUEC算法的數據結構活性邊表與當前掃描線相交的邊稱為活性邊。把活性邊與掃描線的交點按x坐標遞增的順序放在一個鏈表中，該鏈表就稱為活性邊表（Active Edge List, AEL ）。 設多邊形某一條邊的方程為 ，當前掃描線 與該邊的交點坐標為 ，則下一條掃描線 與該邊的交點 不需要重新計算，只要加一個增量 即可。因為此時有0axbyciyy( ,)iix y1iyy11(,)iixyx111()iiiibcbb

9、xb ycyxaaaaa 其中 為常數，并規定 時， 。/xb a 0a 0 x 172014-2015-1:CG:SCUEC使用增量計算時，還要知道一條邊何時不再與下一條掃描線相交，以及時地把該邊從活性邊表中刪除，因此需要記錄下與該邊相交的最高掃描線號。綜上，AEL中的節點應由如下四個域組成： : 邊的上端點的y坐標，即與該邊相交的最高掃描線號。 x: 邊與掃描線的交點的x坐標。 : 從當前掃描線到下一條掃描線間的x坐標的增量，即邊的斜率的倒數。Next: 指向下一條邊的指針。maxyx算法的數據結構182014-2015-1:CG:SCUEC新邊表為方便活性邊表的建立與更新，還要為每一條掃

10、描線建立一個新邊表（New Edge List, NEL ），存放在該掃描線上第一次出現的邊。也就是說，如果某邊的較低端點為 ，則該邊就放在掃描線 的新邊表中。minyminy注意：水平邊不放到任何掃描線的NEL中，即水平邊不參加分類。NEL中的節點結構與AEL相同，只是 x 在這里不再表示邊與掃描線的交點，而是表示該邊較低端點的 x 坐標值。 算法的數據結構192014-2015-1:CG:SCUEC算法描述1. 根據給出的多邊形頂點坐標，建立新邊表NEL； 2. (AEL初始化)將邊的活性邊表AEL設置為空3. (y初始化)取掃描線縱坐標y的初始值為NEL中非空元素的最小序號202014-

11、2015-1:CG:SCUEC 如新邊表NEL中的第y類元素非空，則將屬于該類的所有邊從NEL中取出并插入邊的活性邊表AEL中，AEL中的各邊按照x值(當x的值相等時，按x值)遞增方向排序 若相對于當前掃描線，邊的活性邊表AEL非空，則將AEL中的邊兩兩依次配對，即第1，2邊為一對，第3，4邊為一對，依此類推。每一對邊與當前掃描線的交點所構成的區段位于多邊形內，依次對這些區段上的點(象素)按多邊形屬性著色 將活性邊表AEL中滿足y = ymax的邊刪去 將活性邊表AEL剩下的每一條邊的 x 域累加x，即x = x +x 將當前的掃描線的縱坐標值 y 累加，即y: = y+14. 按從下到上的順

12、序對縱坐標值為y的掃描線(當前掃描線)執行下列步驟，直到新邊表NEL和活性邊表AEL都為空算法描述212014-2015-1:CG:SCUECP0(2, 5), P1(2, 10), P2(9, 6), P3(16, 11), P4(16, 4), P5(12, 2), P6(7, 2)具體例子222014-2015-1:CG:SCUEC邊緣填充算法基本思想假設某像素的顏色是 ，對該像素做偶數次求補運算后，其顏色還是 ；做奇數次求補運算后，其顏色變為 。在光柵圖形中，如某區域已著上值為M 的某種顏色，則上述求補運算的結果是：對區域作偶數次求補運算后，該區域的顏色不變；作奇數次求補運算后，該區域

13、的顏色則變成值為 的顏色。 CCCM232014-2015-1:CG:SCUEC以掃描線為中心的邊緣填充算法 設x0, x2,xm是掃描線y=e與多邊形P的邊界交點x坐標序列（不要求遞增排列），則該掃描線上位于多邊形P內的像素可按如下步驟求得： 步驟1：將位于掃描線y=e上的所有像素都著上值 為M的顏色 for x:=xmin to xmax do setpixel(framebuffer, x, e, M) 步驟2：將位于掃描線y=e上所有坐標大于xi (i =1,2,m)的像素向右求反for i:=1 to m do for x:=xi to xmax do complement(framebuffer, x, e)242014-2015-1:CG:SCUEC1、將繪圖窗口的背景色置為 ；M以邊為中心的邊緣填充算法2、對多邊