矢量轉(zhuǎn)換為柵格(面狀)

1、多邊形掃描轉(zhuǎn)換與區(qū)域填充在計(jì)算機(jī)圖形學(xué)中，多邊形有兩種重要的表示方法：頂點(diǎn)頂點(diǎn)表示和點(diǎn)陣點(diǎn)陣表示。頂點(diǎn)表示是用多邊形的頂點(diǎn)序列來表示多邊形。這種表示直觀、幾何意義強(qiáng)、占內(nèi)存少，易于進(jìn)行幾何變換，但由于它沒有明確指出哪些象素在多邊形內(nèi)故不能直接用于面著色。點(diǎn)陣表示是用位于多邊形內(nèi)的象素集合來刻畫多邊形。這種表示丟失了許多幾何信息，但便于幀緩沖器表示圖形，是面著色所需要的圖形表示形式。光柵圖形的一個(gè)基本問題是把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示。這種轉(zhuǎn)換稱為多邊形的掃描轉(zhuǎn)換多邊形的掃描轉(zhuǎn)換。 逐點(diǎn)判斷算法逐點(diǎn)判斷算法 算法原理：逐個(gè)判斷繪圖窗口內(nèi)的像素，確定它們是否在多邊形區(qū)域內(nèi)部。 問題：如何判別點(diǎn)

2、(x,y)關(guān)于多邊形區(qū)域P的內(nèi)外關(guān)系？射線法 逐點(diǎn)判斷法簡(jiǎn)單，但效率不高 掃描線算法 掃描線多邊形區(qū)域填充算法是按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。區(qū)間的端點(diǎn)可以通過計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。經(jīng)過觀察，可以發(fā)現(xiàn)，對(duì)于一條掃描線，它與多邊形的交點(diǎn)總是偶數(shù)。 對(duì)于一條掃描線，多邊形的填充過程可以分為四個(gè)步驟： （1）求交：計(jì)算掃描線與多邊形各邊的交點(diǎn)； （2）排序：把所有交點(diǎn)按x值遞增順序排序； （3）配對(duì)：第一個(gè)與第二個(gè)，第三個(gè)與第四個(gè)等等；每對(duì)交點(diǎn)代表掃描線與多邊形的一個(gè)相交區(qū)間， （4）填色：把相交區(qū)間內(nèi)的象素置成多邊形顏色

3、，把相交區(qū)間外的象素置成背景色。 減少求交計(jì)算量，采用活性邊表。 對(duì)于一根掃描線而言，與之相交的邊只占多邊形全部邊的一部分,每根掃描線與多邊形所有邊求交的操作是一種浪費(fèi)，需要加以改進(jìn)。活性邊表(Active List of Side)的采用將多邊形的邊分成兩個(gè)子集：與當(dāng)前掃描線相交的邊的集合，以及與當(dāng)前掃描線不相交的邊的集合。對(duì)后者不必進(jìn)行求交運(yùn)算，這樣就提高了算法的效率。改進(jìn)的有效邊表算法改進(jìn)的有效邊表算法1）活性邊：與當(dāng)前掃描線相交的邊。按交點(diǎn)x的增量順序存放在一個(gè)鏈表中；該鏈表稱作活性邊表（邊表（AEL)。算法所涉及的數(shù)據(jù)結(jié)構(gòu)：AEL 與與ET的結(jié)點(diǎn)信息:lYmax: 所交邊的最高掃描線

4、號(hào)lX：當(dāng)前掃描線與邊的交點(diǎn)的x坐標(biāo)lX：邊的斜率的倒數(shù)lNextage: 下一條邊的指針typedef struct int ymax; float x,deltax; Edge *nextEdge; Edge; 掃描線填充算法2）邊的分類表）邊的分類表（ET）按照邊的下端點(diǎn)按照邊的下端點(diǎn)y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組,下端點(diǎn)下端點(diǎn)y坐標(biāo)值等于坐標(biāo)值等于i的邊屬于的邊屬于第第i類類typedef struct int ymax; float x,deltax; Edge *nextEdge; Edge; 邊的分類表的作用是避免盲目求交。當(dāng)處理一條掃描線時(shí)，

5、為了求出它與多邊形邊的所有交點(diǎn)，必須將它與所有的邊進(jìn)行求交測(cè)試。而實(shí)際上只有某幾條邊與該掃描線有交點(diǎn)。邊的分類表正是用來排除不必要的求求交測(cè)試的。0123456789101145-157 5/410 2011 12 010 7 -5/311 7 5/4ET表掃描線填充算法 具體算法具體算法1、建立、建立ET；2、將掃描線縱坐標(biāo)、將掃描線縱坐標(biāo)y的初值置為的初值置為ET中非空元素的最小序號(hào)；中非空元素的最小序號(hào)；3、置、置AEL為空；為空；4、執(zhí)行下列步驟直至、執(zhí)行下列步驟直至ET和和AEL都為空都為空4.1、如、如ET中的第中的第y類非空，則將其中的所有邊取出并插入類非空，則將其中的所有邊取出

6、并插入AEL中；中；4.2、如果有新邊插入、如果有新邊插入AEL，則對(duì)，則對(duì)AEL中各邊排序；中各邊排序；4.3、對(duì)、對(duì)AEL中的邊兩兩配對(duì)，（中的邊兩兩配對(duì)，（1和和2為一對(duì)，為一對(duì)，3和和4為一對(duì)，為一對(duì)，），將每），將每對(duì)邊中對(duì)邊中x坐標(biāo)按規(guī)則取整，獲得有效的填充區(qū)段，再填充坐標(biāo)按規(guī)則取整，獲得有效的填充區(qū)段，再填充4.4、將當(dāng)前掃描線縱坐標(biāo)、將當(dāng)前掃描線縱坐標(biāo)y值遞值值遞值1；4.5、將、將AEL中滿足中滿足y=ymax邊刪去（因?yàn)槊織l邊被看作下閉上開的）；邊刪去（因?yàn)槊織l邊被看作下閉上開的）；4.6、對(duì)、對(duì)AEL中剩下的每一條邊的中剩下的每一條邊的x遞增遞增deltax，即，即x =

7、 x+deltax#include stdio.h#includestdlib.h#include math.h#define pi 3.14159265#include Conio.h#include graphics.h#include malloc.h#define closegr closegraph#define max 400/*建立結(jié)構(gòu)體類型數(shù)據(jù)Edge*/typedef struct Edge int ymax; float x,deltax; struct Edge *nextEdge;Edge;struct Edge *ETmax;void initgr(void) /*

8、BGI初始化 */int gd=DETECT,gm; /* 和gd=VGA,gm=VGAHI是同樣效果 */ /* 注冊(cè)BGI后可以驅(qū)動(dòng)不需要.BGI文件的支持運(yùn)行 */ initgraph(&gd,&gm,E:TC);/*得到多邊形頂點(diǎn)*/void GetST(float x5,float y5,float radius)int i; float r; setcolor(BLUE); x0=300; y0=100; x1=100; y1=200; x2=200; y2=300; x3=400; y3=400; x4=500; y4=200; for(i=0;iymax=y4;

9、e-x=x0;e-deltax=(x4-x0)/(y4-y0); h=(Edge*)malloc(sizeof(Edge); h-ymax=y1;h-x=x0;h-deltax=(x1-x0)/(y4-y0); e-nextEdge=h;h-nextEdge=NULL; ETn=e;n=y1; e=(Edge*)malloc(sizeof(Edge); e-ymax=y2;e-x=x1;e-deltax=(x2-x1)/(y2-y1); h=(Edge*)malloc(sizeof(Edge); h-ymax=y3;h-x=x4;h-deltax=(x3-x4)/(y3-y4); e-next

10、Edge=h;h-nextEdge=NULL; ETn=e; n=y2; e=(Edge*)malloc(sizeof(Edge); e-ymax=y3;e-x=x2;e-deltax=(x3-x2)/(y3-y2); e-nextEdge=NULL; ETn=e; void Fillin(Edge *AEL,int bottom,int top ) char *s; Edge *e; Edge *p,*q; int n,m,i=0,j=0,a8; AEL=(Edge*)malloc(sizeof(Edge);AEL-x=-1; AEL-nextEdge=NULL; for(n=bottom;

11、nnextEdge; while(q) if(p-xx)break; q=q-nextEdge; e=e-nextEdge; q=p-nextEdge; p-nextEdge=e-nextEdge; e-nextEdge=p; p=q; p=AEL;q=AEL-nextEdge; m=1; getch(); while(q) if(q-ymax=n) p-nextEdge=q-nextEdge; e=q; q=q-nextEdge;free(e); else if(p!=AEL&m%2=0) setcolor(RED); line(int)(p-x+0.5),n,(int)(q-x+0

12、.5),n); p-x+=p-deltax; q-x+=q-deltax; p=p-nextEdge; q=q-nextEdge; m+; main() int n,m ,i; float x5,y5,a5,b5,r; Edge *AEL;initgr();/* BGI初始化 */GetST(x,y,100); /*得到五角星的頂點(diǎn)*/setcolor(9);for(i=0;i4;i+) getch(); line(xi,yi,xi+1,yi+1);getch();getch(); line(x4,y4,x0,y0); getch(); n=y0; m=y3; getch(); CreatET

13、(x,y); Fillin(AEL,n,m); /*填充*/ outtextxy(200,400,Fillin Finished!); getch(); /* 暫停一下，看看前面繪圖代碼的運(yùn)行結(jié)果 */ closegr(); /* 恢復(fù)TEXT屏幕模式 */問題：如何處理多邊形的水平邊？如何修改掃描線算法，使它能處理邊自交的多邊形？邊填充算法（適用與幀緩存圖形系統(tǒng)，利于硬件的實(shí)現(xiàn)） 簡(jiǎn)單的邊填充算法 柵欄填充算法 簡(jiǎn)單的邊填充算法：復(fù)雜圖形中每一像素可能被訪問多次，輸入、輸出工作量大 柵欄邊填充算法：減少像素被重復(fù)訪問的次數(shù)1. 對(duì)多邊形的每一條邊進(jìn)行掃描轉(zhuǎn)換，即對(duì)多邊形邊界所經(jīng)過的象素作一個(gè)

14、邊界標(biāo)志。2.填充。對(duì)每條與多邊形相交的掃描線，按從左到右的順序，逐個(gè)訪問該掃描線上的象素。取一個(gè)布爾變量inside來指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。Inside 的初始值為假，每當(dāng)當(dāng)前訪問象素為被打上標(biāo)志的點(diǎn)，就把inside取反。對(duì)未打標(biāo)志的點(diǎn)，inside不變。邊界標(biāo)志算法邊界標(biāo)志算法:算法過程void edgemark_fill(polydef, color)多邊形定義 polydef； int color; 對(duì)多邊形polydef 每條邊進(jìn)行直線掃描轉(zhuǎn)換； inside = FALSE; for (每條與多邊形polydef

15、相交的掃描線y ) for (掃描線上每個(gè)象素x ) if(象素 x 被打上邊標(biāo)志) inside = ! (inside); if(inside！= FALSE) putpixel (x, y, color); else putpixel (x, y, background); 邊界標(biāo)志算法 用軟件實(shí)現(xiàn)時(shí)，掃描線算法與邊界標(biāo)志算法的執(zhí)行速度幾乎相同， 但由于邊界標(biāo)志算法不必建立維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊界標(biāo)志算法更適合硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快一至兩個(gè)數(shù)量級(jí)。多邊形掃描轉(zhuǎn)換區(qū)域填充種子填充算法種子填充算法思想：從區(qū)域內(nèi)的一個(gè)點(diǎn)（種子）開始，由內(nèi)向外將填充色擴(kuò)展到整個(gè)區(qū)域

16、內(nèi)的過程。條件： 要求給出邊界顏色特征及區(qū)域內(nèi)的一個(gè)點(diǎn)，并并要求區(qū)域是連通的 區(qū)域：分為4連通區(qū)域連通區(qū)域和8連通區(qū)域連通區(qū)域 表示內(nèi)點(diǎn)表示邊界點(diǎn) 四個(gè)方向運(yùn)動(dòng) 八個(gè)方向運(yùn)動(dòng) 四連通區(qū)域 八連通區(qū)域6754S9328區(qū)域連通方式對(duì)填充結(jié)果的影響區(qū)域連通方式對(duì)填充結(jié)果的影響4連通區(qū)域邊界填充算法的填充結(jié)果8連通區(qū)域邊界填充算法的填充結(jié)果 常見的種子填充算法由邊界表示的四連通區(qū)域種子填充算法、內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法、邊界表示的八連通區(qū)域種子填充算法、內(nèi)點(diǎn)表示的八連通區(qū)域種子填充算法。（1）邊界表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，按照“右上左下”的順序判斷

17、相鄰像素，若不是邊界像素且沒被填充過，則對(duì)其填充，并重復(fù)上述過程，直至所有像素填充完畢?？梢允褂脳＝Y(jié)構(gòu)來實(shí)現(xiàn)該算法，種子像素入棧，當(dāng)棧非空，重復(fù)執(zhí)行下面操作：1）棧頂像素出棧；2）將出棧像素置成多邊形填充的顏色；3）按“右上左下”的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素不在邊界上且未置成多邊形色，則把該像素入棧。邊界表示的四連通區(qū)域種子填充算法內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法（2）內(nèi)點(diǎn)表示的四連通區(qū)域種子填充算法基本思想：從多邊形內(nèi)部任一點(diǎn)（像素）出發(fā)，按照“右上左下”的順序判斷相鄰像素，若是區(qū)域內(nèi)的像素，則對(duì)其填充，并重復(fù)上述過程，直至所有像素填充完畢?？梢允褂脳＝Y(jié)構(gòu)來實(shí)現(xiàn)該算法，

18、種子像素入棧，當(dāng)棧非空，重復(fù)執(zhí)行下面操作：1）棧頂像素出棧；2）將出棧像素置成多邊形填充的顏色；3）按“右上左下”的順序檢查與出棧像素相鄰的四個(gè)像素，若其中某個(gè)像素是區(qū)域內(nèi)的像素，則把該像素入棧。6754S9328S247938479484795684796847978479847994794796754S9328S799填充算法演示填充算法演示種子填充算法內(nèi)點(diǎn)表示的區(qū)域遞歸算法可實(shí)現(xiàn)如下內(nèi)點(diǎn)表示的區(qū)域遞歸算法可實(shí)現(xiàn)如下void FloodFill4(int x,int y,int oldColor,int newColor) if(GetPixel(x,y) = oldColor) PutP

19、ixel(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); /*end of FloodFill4()*/ 種子填充算法邊界表示的邊界表示的4 4連通區(qū)域連通區(qū)域void BoundaryFill4(int x,int y,int boundaryColor,int newColor)int color;color = G

20、etPixel(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);/*end of BoundaryFill4()*/ 對(duì)邊界和內(nèi)點(diǎn)表示的八連通區(qū)域的填充，只要將上述算法的對(duì)四個(gè)

21、像素點(diǎn)填充改為八個(gè)像素點(diǎn)即可。四連通區(qū)域種子填充算法的缺點(diǎn)是有時(shí)不能通過狹窄區(qū)域區(qū)域，因而不能填滿多邊形。八連通算法的缺點(diǎn)是有時(shí)會(huì)填出多邊形的邊界。由于填不滿比涂出更容易補(bǔ)救，因此四連通算法比八連通算法用得更多。 該算法也可以填充有孔區(qū)域。該算法也可以填充有孔區(qū)域。 缺點(diǎn)缺點(diǎn)：(1) 有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2) 遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。 改進(jìn)算法，減少遞歸次數(shù)，提高效率。解決方法是用掃描線填充算法種子填充算法掃描線算法目標(biāo)：減少遞歸層次目標(biāo)：減少遞歸層次適用于邊界表示的適用于邊界表示的4 4連通區(qū)域連通區(qū)域算法思想算法思想：在任意不間斷區(qū)間中只