二維填充圖元的生成

二維填充圖元的生成2023/7/81第1頁，課件共60頁，創(chuàng)作于2023年2月

掃描轉換矩形問題：矩形是簡單的多邊形，那么為什么要單獨處理矩形？比一般多邊形可進行簡化計算。應用非常多，窗口系統(tǒng)。共享邊界如何處理？ 原則：左閉右開，下閉上開屬于誰？2023/7/82第2頁，課件共60頁，創(chuàng)作于2023年2月掃描轉換矩形方法：voidFillRectangle(Rectangle*rect,intcolor) {intx,y; for(y=rect->ymin;y<=rect->ymax;y++) for(x=rect->xmin;x<=rect->xmax;x++) PutPixel(x,y,color); }/*endofFillRectangle() */2023/7/83第3頁，課件共60頁，創(chuàng)作于2023年2月多邊形的掃描轉換范圍：多邊形分為凸多邊形、凹多邊形、含內環(huán)的多邊形。2023/7/84第4頁，課件共60頁，創(chuàng)作于2023年2月掃描轉換多邊形多邊形的表示方法頂點表示點陣表示頂點表示：用多邊形頂點的序列來刻劃多邊形。直觀、幾何意義強、占內存少；不能直接用于面著色。點陣表示：用位于多邊形內的象素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運用幀緩沖存儲器表示圖形，易于面著色。2023/7/85第5頁，課件共60頁，創(chuàng)作于2023年2月多邊形的掃描轉換多邊形的掃描轉換：把多邊形的頂點表示轉換為點陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內部的各個象素，并給幀緩沖器內的各個對應元素設置相應的灰度和顏色，通常稱這種轉換為多邊形的掃描轉換。幾種方法：逐點判斷法；掃描線算法；邊緣填充法；柵欄填充法；邊界標志法。2023/7/86第6頁，課件共60頁，創(chuàng)作于2023年2月voidFillPolygonPbyP(Polygon*P,intpolygonColor){intx,y;

for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++) if(IsInside(P,x,y)) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP() */#defineMAX100Typedefstruct{intPolygonNum;//多邊形頂點個數

Pointvertexces[MAX]//多邊形頂點數組

}Polygon//多邊形結構逐點判斷法2023/7/87第7頁，課件共60頁，創(chuàng)作于2023年2月逐個判斷繪圖窗口內的像素：如何判斷點在多邊形的內外關系？1）射線法：2）累計角度法3）編碼法；逐點判斷法2023/7/88第8頁，課件共60頁，創(chuàng)作于2023年2月1）射線法步驟：從待判別點v發(fā)出射線求交點個數kK的奇偶性決定了點與多邊形的內外關系逐點判斷法2023/7/89第9頁，課件共60頁，創(chuàng)作于2023年2月2）累計角度法步驟從v點向多邊形P頂點發(fā)出射線，形成有向角計算有向角的和，得出結論逐點判斷法2023/7/810第10頁，課件共60頁，創(chuàng)作于2023年2月逐點判斷的算法雖然程序簡單，但不可取。原因是速度太慢，主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內外關系，使得幾十萬甚至幾百萬個象素都要一一判別，每次判別又要多次求交點，需要做大量的乘除運算，花費很多時間。逐點判斷法2023/7/811第11頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法掃描線算法目標：利用相鄰像素之間的連貫性，提高算法效率處理對象：非自交多邊形（邊與邊之間除了頂點外無其它交點）2023/7/812第12頁，課件共60頁，創(chuàng)作于2023年2月

掃描線算法是多邊形掃描轉換的常用算法。與逐點判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對象素的逐點判斷和反復求交的運算，達到了減少了計算量和提高速度的目的。

開發(fā)和利用相鄰象素之間的連貫性是光柵圖形算法研究的重要內容。掃描轉換算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。掃描線算法2023/7/813第13頁，課件共60頁，創(chuàng)作于2023年2月

設多邊形P的頂點Pi=(xi,yi),i=0,1,…,n，又設yi0,yi1,…yin是各頂點Pi的坐標yi的遞減數列，即yik≥yik+1,0≤k≤n-1這樣，當yik≥yik+1,0≤k≤n-1時，屏幕上位于y=yik和y=yik+1兩條掃描線之間的長方形區(qū)域被多邊形P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形），它們具有下列性質：區(qū)域的連貫性2023/7/814第14頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域的連貫性1）梯形的兩底邊分別在y=yik和y=yik+1兩條掃描線上，腰在多邊形P的邊上或在顯示屏幕的邊界上。2）這些梯形可分為兩類：一類位于多邊形P的內部；另一類在多邊形P的外部。3）兩類梯形在長方形區(qū)域{yik,yik+1}內相間的排列，即相鄰的兩梯形必有一個在多邊形P內，另一個在P外。

2023/7/815第15頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域的連貫性根據這些性質，實際上只需知道該長方形區(qū)域內任一梯形內一點關于多邊形P的內外關系后，即可確定區(qū)域內所有梯形關于P的內外關系。2023/7/816第16頁，課件共60頁，創(chuàng)作于2023年2月

設e為一整數，yi0≥e≥yin。若掃描線y=e與多邊形P的Pi-1Pi相交，則記其交點的橫坐標為xei。

現設xei1,xei2,xei3,…,xeil是該掃描線與P的邊界各交點橫坐標的遞增序列，稱此序列為交點序列。由區(qū)域的連貫性可知，此交點序列具有以下性質：掃描線的連貫性2023/7/817第17頁，課件共60頁，創(chuàng)作于2023年2月掃描線的連貫性1）l是偶數。2）在該掃描線上，只有區(qū)段xeik,xeik+1）,k=1,3,5,…,l-1位于多邊形P內，其余區(qū)段都在P外。以上性質稱為掃描線的連貫性，它是多邊形區(qū)域連貫性在一條掃描線上的反映。2023/7/818第18頁，課件共60頁，創(chuàng)作于2023年2月

設d為一整數，并且d=e-1,并且

yi0≥d≥yin。設位于掃描線y=d上的交點序列為xdj1,xdj2,xdj3,…,xdjk

現在來討論掃描線d，e交點序列之間的關系。若多邊形P的邊Pr-1Pr與掃描線y=e,y=d都相交，則交點序列中對應元素xer,xdr滿足下列關系：xer=xdr+1/mr(1)其中mr為邊Pr-1Pr的斜率。

邊的連貫性2023/7/819第19頁，課件共60頁，創(chuàng)作于2023年2月邊的連貫性

可利用d的交點序列計算e的交點序列：先運用遞推關系式(1)求得與掃描線y=e和y=d都相交的所有多邊形上的交點xer；再求得與掃描線y=d不相交但與掃描線y=e相交的所有邊PqPq+1上的交點xeq。然后把這兩部分按遞增的順序排列，即可得e的交點序列。

2023/7/820第20頁，課件共60頁，創(chuàng)作于2023年2月當掃描線與多邊形P的交點是P的頂點時，則稱該交點為奇點。以上所述多邊形的三種形式的連貫性都基于這樣的幾何事實：每一條掃描線與多邊形P的邊界的交點個數都是偶數。但是如果把每一奇點簡單地計為一個交點或者簡單地計為兩個交點，都可能出現奇數個交點。那么如果保證交點數為偶數呢？奇點的處理2023/7/821第21頁，課件共60頁，創(chuàng)作于2023年2月奇點的處理若奇點做一個交點處理，則情況A，交點個數不是偶數。若奇點做兩個交點處理，則情況B，交點個數不是偶數。2023/7/822第22頁，課件共60頁，創(chuàng)作于2023年2月奇點的處理多邊形P的頂點可分為兩類：極值奇點和非極值奇點。如果(yi-1-yi)(yi+1-yi)≥0，則稱頂點Pi為極值點；否則稱Pi為非極值點。規(guī)定：奇點是極值點時，該點按兩個交點計算，否則按一個交點計算。奇點的預處理：非極值奇點屬于y值小的邊

2023/7/823第23頁，課件共60頁，創(chuàng)作于2023年2月數據結構與實現步驟算法基本思想：首先取d=yin。容易求得掃描線y=d上的交點序列為xdj1,xdj2,…xdjn，這一序列由位于掃描線y=d上的多邊形P的頂點組成。由yin的交點序列開始，根據多邊形的邊的連貫性，按從下到上的順序求得各條掃描線的交點序列；根據掃描線的連貫性，可確定各條掃描線上位于多邊形P內的區(qū)段，并表示成點陣形式。2023/7/824第24頁，課件共60頁，創(chuàng)作于2023年2月即算法中采用較靈活的數據結構。它由邊的分類表ET（EdgeTable）和邊的活化鏈表AEL（ActiveEdgeList）兩部分組成。表結構ET和AEL中的基本元素為多邊形的邊。邊的結構由以下四個域組成：

ymax

邊的上端點的y坐標；

x在ET中表示邊的下端點的x坐標，在AEL中則表示邊與掃描線的交點的坐標；

Δx邊的斜率的倒數；

next指向下一條邊的指針。

數據結構與實現步驟2023/7/825第25頁，課件共60頁，創(chuàng)作于2023年2月數據結構與實現步驟邊的分類表ET是按邊的下端點的y坐標對非水平邊進行分類的指針數組。下端點的y坐標的值等于i的邊歸入第i類。有多少條掃描線，就設多少類。同一類中，各邊按x值（x值相等時，按Δx的值）遞增的順序排列成行。

2023/7/826第26頁，課件共60頁，創(chuàng)作于2023年2月數據結構與實現步驟與當前掃描線相交的邊稱為活性邊（activeedge)，把它們按與掃描線交點x坐標遞增的順序存入一個鏈表中，邊的活化鏈表（AEL,Activeedgetable)。它記錄了多邊形邊沿掃描線的交點序列。2023/7/827第27頁，課件共60頁，創(chuàng)作于2023年2月例子已知多邊形P=(P0P1P2P3P4P5P6P0)；其各邊坐標分別為[P0（2，5）P1（2，10）P2（9，6）P3（16，11）P4（16，4）P5（12，2）P6（7，2）]建立其邊表和邊的活化鏈表2023/7/828第28頁，課件共60頁，創(chuàng)作于2023年2月邊表2023/7/829第29頁，課件共60頁，創(chuàng)作于2023年2月y=3Y=8活動鏈表的例子2023/7/830第30頁，課件共60頁，創(chuàng)作于2023年2月算法實現步驟這樣，當建立了邊的分類表ET后，掃描線算法可按下列步驟進行：（1）取掃描線縱坐標y的初始值為ET中非空元素的最小序號。（2）將邊的活化鏈表AEL設置為空。（3）按從下到上的順序對縱坐標值為y的掃描線（當前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。

2023/7/831第31頁，課件共60頁，創(chuàng)作于2023年2月算法實現步驟1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中。遞增方向排序。2）若相對于當前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對，依此類推。并填色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）x:=x+Δx。5）y:=y+1。2023/7/832第32頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法總結特點：算法效率比逐點填充法高很多。缺點：對各種表的維持和排序開銷太大，適合軟件實現而不適合硬件實現。2023/7/833第33頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法總結問題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？有孔的多邊形如何處理？如何處理圓、橢圓的掃描線算法？2023/7/834第34頁，課件共60頁，創(chuàng)作于2023年2月邊緣填充算法▼求余運算：假定A為一個正整數，則M的余定義為A–M,記為。計算機中取A為n位能表示的最大整數。即，A=0xFFFFFFFF▼算法由來：光柵圖形中，如果某區(qū)域已著上值為M的顏色值，對該區(qū)域做偶數次求余運算，該區(qū)域顏色不變；而做奇數次求余運算，則該區(qū)域顏色變?yōu)橹禐榈念伾?。這一規(guī)律應用于多邊形掃描轉換，就為邊緣填充算法。▼算法基本思想：對于每條掃描線和每條多邊形邊的交點，將該掃描線上交點右方的所有象素取余。2023/7/835第35頁，課件共60頁，創(chuàng)作于2023年2月1、將當前掃描線上的所有象素著上顏色；2、求余：

for(i=0;i<=m;i++)

在當前掃描線上，從橫坐標為Xi的交點向右求余；

算法1（以掃描線為中心的邊緣填充算法）2023/7/836第36頁，課件共60頁，創(chuàng)作于2023年2月 1、將繪圖窗口的背景色置為；

2、對多邊形的每一條非水平邊做： 從該邊上的每個象素開始向右求余；算法2（以邊為中心的邊緣填充算法）2023/7/837第37頁，課件共60頁，創(chuàng)作于2023年2月邊緣填充算法總結適合用于具有幀緩存的圖形系統(tǒng)。處理后，按掃描線順序讀出幀緩存的內容，送入顯示設備。優(yōu)點：算法簡單缺點：對于復雜圖形，每一象素可能被訪問多次，輸入/輸出的量比有序邊表算法大得多。2023/7/838第38頁，課件共60頁，創(chuàng)作于2023年2月引入柵欄，以減少填充算法訪問象素的次數。柵欄：與掃描線垂直的直線，通常過一頂點，且把多邊形分為左右二半?；舅枷耄簰呙杈€與多邊形的邊求交，將交點與柵欄之間的象素取補。減少了象素重復訪問數目，但不徹底。柵欄填充算法2023/7/839第39頁，課件共60頁，創(chuàng)作于2023年2月1.對多邊形的每一條邊進行掃描轉換，即對多邊形邊界所經過的象素作一個邊界標志。2.填充。對每條與多邊形相交的掃描線，按從左到右的順序，逐個訪問該掃描線上的象素。取一個布爾變量inside來指示當前點的狀態(tài)，若點在多邊形內，則inside為真。若點在多邊形外，則inside為假。Inside的初始值為假，每當當前訪問象素為被打上標志的點，就把inside取反。對未打標志的點，inside不變。邊界標志算法2023/7/840第40頁，課件共60頁，創(chuàng)作于2023年2月邊界標志算法:算法過程voidedgemark_fill(polydef,color)多邊形定義polydef；intcolor;{對多邊形polydef每條邊進行直線掃描轉換；

inside=FALSE;for(每條與多邊形polydef相交的掃描線y)for(掃描線上每個象素x){if(象素x被打上邊標志)inside=!(inside);if(inside！=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background); }}2023/7/841第41頁，課件共60頁，創(chuàng)作于2023年2月邊界標志算法總結用軟件實現時，掃描線算法與邊界標志算法的執(zhí)行速度幾乎相同，但由于邊界標志算法不必建立維護邊表以及對它進行排序，所以邊界標志算法更適合硬件實現，這時它的執(zhí)行速度比有序邊表算法快一至兩個數量級。2023/7/842第42頁，課件共60頁，創(chuàng)作于2023年2月邊界標志算法總結思考：如何處理邊界的交點個數使其成為偶數？2023/7/843第43頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充區(qū)域指已經表示成點陣形式的填充圖形，它是象素的集合。區(qū)域填充指先將區(qū)域的一點賦予指定的顏色，然后將該顏色擴展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的2023/7/844第44頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充表示方法：內點表示、邊界表示內點表示(象素表示區(qū)域)枚舉出區(qū)域內部的所有像素內部的所有像素著同一個顏色邊界像素著與內部像素不同的顏色邊界表示（幾何表示區(qū)域）枚舉出邊界上所有的像素邊界上的所有像素著同一顏色內部像素著與邊界像素不同的顏色2023/7/845第45頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充區(qū)域填充要求區(qū)域是連通的連通性

4連通、8連通4連通：8連通2023/7/846第46頁，課件共60頁，創(chuàng)作于2023年2月區(qū)域填充4連通與8連通區(qū)域的區(qū)別連通性：4連通可看作8連通區(qū)域，但對邊界有要求對邊界的要求內點表示的4連通區(qū)域，它的邊界必然是一個8連通區(qū)域，反之，內點表示的8連通區(qū)域，它的邊界必然是一個4連通區(qū)域2023/7/847第47頁，課件共60頁，創(chuàng)作于2023年2月A：適合于內點表示區(qū)域的填充算法設G為一內點表示的區(qū)域，(x,y)為區(qū)域內一點，old_color為G的原色?，F取(x,y)為種子點對區(qū)域G進行填充：即先置像素(x,y)的顏色為new_color，然后逐步將整個區(qū)域G都置為同樣的顏色。步驟如下：種子象素入棧，當棧非空時，執(zhí)行如下三步操作：（1）棧頂象素出棧；（2）將出棧象素置成new_color

；（3）按上、下、左、右的順序檢查與出棧象素相鄰的四個象素，若其中某個象素在邊界內且未置成new_color

，則把該象素入棧。種子填充算法2023/7/848第48頁，課件共60頁，創(chuàng)作于2023年2月種子填充算法例：多邊形由P0P1P2P3P4構成，P0(1,5)P1(5,5)P2(7,3)P3(7,1)P4(1,1)設種子點為（3，3），搜索的方向是上、下、左、右。依此類推，最后像素被選中并填充的次序如圖中箭頭所示

2023/7/849第49頁，課件共60頁，創(chuàng)作于2023年2月種子填充算法遞歸算法可實現如下voidFloodFill4(intx,inty,intoldColor,intnewColor){if(GetPixel(x,y)==oldColor){PutPixel(x,y,newColor);FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);}}/*endofFloodFill4() */

2023/7/850第50頁，課件共60頁，創(chuàng)作于2023年2月種子填充算法邊界表示的4連通區(qū)域voidBoundaryFill4(intx,inty,intboundaryColor,intnewColor){ intcolor; color=GetPixel(x,y); if((color!=boundaryColor)&&(color!=newColor)) { PutPixel(x,y,newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,newColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}/*endofBoundaryFill4() */

2023/7/851第51頁，課件共60頁，創(chuàng)作于2023年2月該算法也可以填充有孔區(qū)域。

缺點：

(1)有些象素會入棧多次，降低算法效率；

(2)遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內每一象素都引起一次遞歸，進/出棧，費時費內存。改進算法，減少遞歸次數，提高效率。 解決方法是用掃描線填充算法種子填充算法2023/7/852第52頁，課件共60頁，創(chuàng)作于2023年2月掃描線算法掃描線算法目標：減少遞歸層次適用于邊界表示的4連通區(qū)域算法思想：在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在