計(jì)算機(jī)圖形學(xué)實(shí)驗(yàn)報(bào)告

計(jì)算機(jī)圖形學(xué)實(shí)驗(yàn)二維填充圖的生成1．圖元填充利用多種圖元填充的方法繪制一面五星紅旗。方法有：掃描轉(zhuǎn)換多邊形的逐點(diǎn)判斷法（編碼算法），掃描線算法，區(qū)域填充的掃描線算法，自創(chuàng)的向內(nèi)復(fù)制邊法。1.1說明：1.1.1宏定義和類型定義：#definemax400#definepi3.14159265#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#definefalse0#definetrue1#defineok1#defineerror0#defineinfeasible-1#defineoverflow-2typedefintStatus;typedefintbool;typedefstruct{inty,xLeft,xRight;}SElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;typedefstructEdge{intymax;floatx,deltax;structEdge*nextEdge;}Edge;Edge*EL[max];typedefstruct{floatx,y;}point;StatusSetStackEmpty(SqStack*s){s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s->base)returnoverflow;s->top=s->base;s->stacksize=STACK_INIT_SIZE;returnok;}StatusPushStack(SqStack*s,SElemTypee){if(s->top-s->base>=s->stacksize){s->base=(SElemType*)(s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s->base)returnerror;s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;}*s->top++=e;returnok;}StatusPopStack(SqStack*s,SElemType*e){if(s->top==s->base)returnerror;*e=*(--s->top);returnok;}StatusIsStackEmpty(SqStack*s){if(s->base==s->top)returntrue;elsereturnfalse;}1.1.2其他由于要填充五角星，我們就要得到五角星的十個(gè)頂點(diǎn)。把頂點(diǎn)存入a,b,x,y四個(gè)數(shù)組中，子程序如下：voidGetST(floatx[5],floaty[5],floata[5],floatb[5],floatradius){inti;floatr;for(i=0;i<5;i++){x[i]=radius*cos(i*0.4*pi+0.05*pi)-radius*sin(i*0.4*pi+0.05*pi);y[i]=radius*sin(i*0.4*pi+0.05*pi)+radius*cos(i*0.4*pi+0.05*pi);}r=sin(0.1*pi)*radius/sin(126.0/180.0*pi);for(i=0;i<5;i++){a[i]=r*cos(i*0.4*pi+0.25*pi)-r*sin(i*0.4*pi+0.25*pi);b[i]=r*sin(i*0.4*pi+0.25*pi)+r*cos(i*0.4*pi+0.25*pi);}}我們還提供了平移旋轉(zhuǎn)的子函數(shù)：voidmove(floatx[5],floaty[5],floata[5],floatb[5],floatcx,floatcy){inti;for(i=0;i<5;i++){x[i]=x[i]+cx;a[i]=a[i]+cx;y[i]=y[i]+cy;b[i]=b[i]+cy;}}voidrotate(floatx[5],floaty[5],floata[5],floatb[5],floattheta){inti;floatt1,t2;for(i=0;i<5;i++){t1=x[i];x[i]=x[i]*cos(theta)-y[i]*sin(theta);y[i]=t1*sin(theta)+y[i]*cos(theta);t2=a[i];a[i]=a[i]*cos(theta)-b[i]*sin(theta);b[i]=t2*sin(theta)+b[i]*cos(theta);}}2.掃描轉(zhuǎn)換多邊形2.1把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。幾種方法：逐點(diǎn)判斷法；掃描線算法；邊緣填充法；柵欄填充法；邊界標(biāo)志法。2.2逐點(diǎn)判斷法逐個(gè)判斷繪圖窗口內(nèi)的像素。如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？有1）射線法：2）累計(jì)角度法3）編碼法；我這里用的是編碼算法。Step:a.預(yù)處理，測試點(diǎn)在邊上否？b.V為中點(diǎn)作局部坐標(biāo)系,對象限按逆時(shí)針（或順時(shí)針）編碼；c.頂點(diǎn)編碼Ipi，d.邊編碼。PiPi+1:△PiPi+1=Ipi+1-Ipie.計(jì)算∑△PiPi+1（其中△PnPn+1=△PnP0)：若∑為0,V在P外； 若∑為+/-4，V在P內(nèi)；主要子程序：/**************************得到某一條邊關(guān)于某一點(diǎn)的編碼******************/intEdge_code(pointnode,pointstart,pointend){intw,v,s=0;pointp;floatx0,y0;if(start.x>node.x&&start.y>node.y)v=0;if(start.x<=node.x&&start.y>node.y)v=1;if(start.x<=node.x&&start.y<=node.y)v=2;if(start.x>node.x&&start.y<=node.y)v=3;if(end.x>node.x&&end.y>node.y)w=0;if(end.x<=node.x&&end.y>node.y)w=1;if(end.x<=node.x&&end.y<=node.y)w=2;if(end.x>node.x&&end.y<=node.y)w=3;s=w-v;if(s==2||s==-2){x0=(end.x+start.x)/2;y0=(end.y+start.y)/2;p.x=x0;p.y=y0;s=Edge_code(node,start,p)+Edge_code(node,p,end);}if(s==3)s=-1;if(s==-3)s=1;returns;}/**************************得到填充區(qū)域的上界*******************/pointGetmax(pointpoints[10]){inti;floatmaxx,maxy;pointp;maxx=points[0].x;maxy=points[0].y;for(i=1;i<10;i++){if(points[i].x>maxx)maxx=points[i].x;if(points[i].y>maxy)maxy=points[i].y;}p.x=maxx;p.y=maxy;returnp;}/**************************得到區(qū)域填充的下界******************/pointGetmin(pointpoints[10]){inti;floatminx,miny;pointp;minx=points[0].x;miny=points[0].y;for(i=1;i<10;i++){if(points[i].x<minx)minx=points[i].x;if(points[i].y<miny)miny=points[i].y;}p.x=minx;p.y=miny;returnp;}/*****************************函數(shù)調(diào)用：*******************/for(i=0;i<10;i++){if(i%2==0){points[i].x=x[i/2];points[i].y=y[i/2];}else{points[i].x=a[i/2];points[i].y=b[i/2];}}p1=Getmax(points);p2=Getmin(points);for(n=p2.y;n<p1.y;n++)for(m=p2.x;m<p1.x;m++)if(getpixel(m,n)!=YELLOW){node.x=m;node.y=n;j=Edge_code(node,points[0],points[1]);for(i=1;i<9;i++)j+=Edge_code(node,points[i],points[i+1]);j+=Edge_code(node,points[9],points[0]);if(j==4||j==-4)putpixel(m,n,YELLOW);}逐點(diǎn)判斷法程序簡單，速度太慢，效率低逐點(diǎn)判斷的算法雖然程序簡單，但不可取。原因是速度太慢，主要是由于該算法割斷了各象素之間的聯(lián)系，孤立地考察各象素與多邊形的內(nèi)外關(guān)系，使得幾十萬甚至幾百萬個(gè)象素都要一一判別，每次判別又要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)很多時(shí)間2.3掃描線算法目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率處理對象：非自交多邊形（邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)）算法基本思想：首先取d=yin。容易求得掃描線y=d上的交點(diǎn)序列為xdj1,xdj2,…xdjn，這一序列由位于掃描線y=d上的多邊形P的頂點(diǎn)組成。由yin的交點(diǎn)序列開始，根據(jù)多邊形的邊的連貫性，按從上到下的順序求得各條掃描線的交點(diǎn)序列；根據(jù)掃描線的連貫性，可確定各條掃描線上位于多邊形P內(nèi)的區(qū)段，并表示成點(diǎn)陣形式。與當(dāng)前掃描線相交的邊稱為活性邊（activeedge)，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存入一個(gè)鏈表中，邊的活化鏈表（AEL,Activeedgetable)。它記錄了多邊形邊沿掃描線的交點(diǎn)序列。只需對當(dāng)前掃描線的活動(dòng)邊表作更新，即可得到下一條掃描線的活動(dòng)邊表。算法中采用較靈活的數(shù)據(jù)結(jié)構(gòu)。它由邊的分類表ET（EdgeTable）和邊的活化鏈表AEL（ActiveEdgeList）兩部分組成。表結(jié)構(gòu)ET和AEL中的基本元素為多邊形的邊。邊的結(jié)構(gòu)由以下四個(gè)域組成：ymax邊的上端點(diǎn)的y坐標(biāo)；x在ET中表示邊的下端點(diǎn)的x坐標(biāo)，在AEL中則表示邊與掃描線的交點(diǎn)的坐標(biāo)；Δx邊的斜率的倒數(shù)；next指向下一條邊的指針邊的分類表ET是按邊的下端點(diǎn)的y坐標(biāo)對非水平邊進(jìn)行分類的指針數(shù)組。下端點(diǎn)的y坐標(biāo)的值等于i的邊歸入第i類。有多少條掃描線，就設(shè)多少類。同一類中，各邊按x值（x值相等時(shí)，按Δx的值）遞增的順序排列成行這樣，當(dāng)建立了邊的分類表ET后，掃描線算法可按下列步驟進(jìn)行：（1）取掃描線縱坐標(biāo)y的初始值為ET中非空元素的最小序號(hào)。（2）將邊的活化鏈表AEL設(shè)置為空。（3）按從下到上的順序?qū)v坐標(biāo)值為y的掃描線（當(dāng)前掃描線）執(zhí)行下列步驟，直到邊的分類表ET和邊的活化鏈表都變成空為止。1）如邊分類表ET中的第y類元素非空，則將屬于該類的所有邊從ET中取出并插入邊的活化鏈表中，AEL中的各邊按照x值（當(dāng)x值相等時(shí)，按Δx值）遞增方向排序。2）若相對于當(dāng)前掃描線，邊的活化鏈表AEL非空，則將AEL中的邊兩兩依次配對，即1，2邊為一對，3，4邊為一對，依次類推。每一對邊與當(dāng)前掃描線的交點(diǎn)所構(gòu)成的區(qū)段位于多邊形內(nèi)，依次對這些區(qū)段上的點(diǎn)（象素）按多邊形屬性著色。3）將邊的活化鏈表AEL中滿足y=ymax的邊刪去。4）將邊的活化鏈表AEL剩下的每一條邊的x域累加Δx，即x:=x+Δx。5）將當(dāng)前的掃描線的縱坐標(biāo)值y累加1，即y:=y+1。子程序如下：/**********************手工建立五角星的分類表：*********************/voidCreatET(floatx[5],floaty[5],floata[5],floatb[5]){intn;Edge*e,*h;n=(int)(y[3]+0.5);e=(Edge*)malloc(sizeof(Edge));e->ymax=(int)(b[3]+0.5);e->x=x[3];e->deltax=(a[3]-x[3])/(b[3]-y[3]);h=(Edge*)malloc(sizeof(Edge));h->ymax=(int)(b[2]+0.5);h->x=x[3];h->deltax=(a[2]-x[3])/(b[3]-y[3]);e->nextEdge=h;h->nextEdge=NULL;EL[n]=e;n=(int)(b[2]+0.5);e=(Edge*)malloc(sizeof(Edge));e->ymax=(int)(b[1]+0.5);e->x=x[2];e->deltax=(a[1]-x[2])/(b[1]-y[2]);h=(Edge*)malloc(sizeof(Edge));h->ymax=(int)(b[4]+0.5);h->x=x[4];h->deltax=(a[4]-x[4])/(b[4]-y[4]);e->nextEdge=h;h->nextEdge=NULL;EL[n]=e;n=(int)(b[1]+0.5);e=(Edge*)malloc(sizeof(Edge));e->ymax=(int)(y[1]+0.5);e->x=a[1];e->deltax=(x[1]-a[1])/(y[1]-b[1]);h=(Edge*)malloc(sizeof(Edge));h->ymax=(int)(y[0]+0.5);h->x=a[4];h->deltax=(x[0]-a[4])/(y[0]-b[4]);e->nextEdge=h;h->nextEdge=NULL;EL[n]=e;n=(int)(b[0]+0.5);e=(Edge*)malloc(sizeof(Edge));e->ymax=(int)(y[1]+0.5);e->x=a[0];e->deltax=(x[1]-a[0])/(y[1]-b[0]);h=(Edge*)malloc(sizeof(Edge));h->ymax=(int)(y[0]+0.5);h->x=a[0];h->deltax=(x[0]-a[0])/(y[0]-b[0]);e->nextEdge=h;h->nextEdge=NULL;EL[n]=e;}/****************填充********************/voidFillin(Edge*AEL,intbottom,inttop){Edge*e;Edge*p,*q;intn,m;AEL=(Edge*)malloc(sizeof(Edge));AEL->x=-1;AEL->nextEdge=NULL;for(n=bottom;n<top;n++){p=EL[n];while(p){e=AEL;q=AEL->nextEdge;while(q){if(p->x<q->x)break;q=q->nextEdge;e=e->nextEdge;}q=p->nextEdge;p->nextEdge=e->nextEdge;e->nextEdge=p;p=q;}q=AEL->nextEdge;p=AEL;q=AEL->nextEdge;m=1;while(q){if(q->ymax==n){p->nextEdge=q->nextEdge;e=q;q=q->nextEdge;free(e);}else{if(p!=AEL&&m%2==0){line((int)(p->x+0.5),n,(int)(q->x+0.5),n);p->x+=p->deltax;q->x+=q->deltax;}p=p->nextEdge;q=q->nextEdge;m++;}}}}程序調(diào)用：GetST(x,y,a,b,50);move(x,y,a,b,100,120);n=(int)(y[3]+0.5);m=(int)(y[1]+0.5);CreatET(x,y,a,b);Fillin(AEL,n,m);掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。與逐點(diǎn)判斷算法相比，掃描線算法充分利用了相鄰象素之間的連貫性，避免了對象素的逐點(diǎn)判斷和反復(fù)求交的運(yùn)算，達(dá)到了減少了計(jì)算量和提高速度的目的。3.區(qū)域填充區(qū)域填充指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的。表示方法有：內(nèi)點(diǎn)表示、邊界表示。3.1遞歸填充遞歸算法可實(shí)現(xiàn)如下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()********************** */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() *************************/該算法缺點(diǎn)：(1)有些象素會(huì)入棧多次，降低算法效率；棧結(jié)構(gòu)占空間。(2)遞歸執(zhí)行，算法簡單，但效率不高，區(qū)域內(nèi)每一象素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存。3.2掃描線算法目標(biāo)：減少遞歸層次，適用于邊界表示的4連通區(qū)域。算法思想：在任意不間斷區(qū)間中只取一個(gè)種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當(dāng)前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復(fù)進(jìn)行這個(gè)過程，直到所保存的個(gè)區(qū)段都填充完畢。(1)初始化：堆棧置空。將種子點(diǎn)（x，y）入棧。(2)出棧：若?？談t結(jié)束。否則取棧頂元素（x，y），以y作為當(dāng)前掃描線。(3)填充并確定種子點(diǎn)所在區(qū)段：從種子點(diǎn)（x，y）出發(fā)，沿當(dāng)前掃描線向左、右兩個(gè)方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點(diǎn)坐標(biāo)為xl和xr。(4)并確定新的種子點(diǎn)：在區(qū)間[xl，xr]中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的象素。若存在非邊界、未填充的象素，則把每一區(qū)間的最右象素作為種子點(diǎn)壓入堆棧，返回第（2）步。上述算法對于每一個(gè)待填充區(qū)段，只需壓棧一次；因此，掃描線填充算法提高了區(qū)域填充的效率。子程序如下：voidScanLineFill4(intx,intY,intoldColor,intnewColor){intxLeft,xRight,y,i;boolisLeftEndSet,spanNeedFill;SElemType*span;SqStack*s;/*填充并確定種子點(diǎn)(x,y)所在的區(qū)段*/i=x;y=Y;while(getpixel(i,y)==oldColor)/*向右填充*/{putpixel(i,y,newColor);i++;}span->xRight=i-1;/*確定區(qū)段右邊界*/i=x-1;while(getpixel(i,y)==oldColor)/*向左填充*/{putpixel(i,y,newColor);i--;}span->xLeft=i+1;/*確定區(qū)段左邊界*//*初始化*/SetStackEmpty(s);span->y=y;PushStack(s,*span);/*將前面生成的區(qū)段壓入堆棧*/while(!IsStackEmpty(s))/*終止判斷*/{/*出棧*/PopStack(s,span);/*處理上面掃描線*/i=span->xLeft;while(i<=xRight){spanNeedFill=false;while(getpixel(i,y)==oldColor)/*向右填充*/{if(!spanNeedFill){spanNeedFill=true;if(!isLeftEndSet){isLeftEndSet=true;xLeft=i;}}putpixel(i,y,newColor);i++;}if(spanNeedFill){span->y=y;span->xLeft=xLeft;span->xRight=i-1;PushStack(s,*span);/*將區(qū)段壓入堆棧*/isLeftEndSet=false;spanNeedFill=false;}while(getpixel(i,y)!=oldColor)i++;}/*endofwhile(i<xRight)*/}/*endofwhile(!isStackEmpty())*/}/*endofScanLineBoundaryFill4()*//*處理下面的掃描線*/voidScanLineFill3(intx,intY,intoldColor,intnewColor){intxLeft,xRight,y,i;boolisLeftEndSet,spanNeedFill;SElemType*span;SqStack*s;/*填充并確定種子點(diǎn)(x,y)所在的區(qū)段*/i=x;y=Y;while(getpixel(i,y)==oldColor)/*向右填充*/{putpixel(i,y,newColor);i++;}span->xRight=i-1;/*確定區(qū)段右邊界*/i=x-1;while(getpixel(i,y)==oldColor)/*向左填充*/{putpixel(i,y,newColor);i--;}span->xLeft=i+1;/*確定區(qū)段左邊界*//*初始化*/SetStackEmpty(s);span->y=y;PushStack(s,*span);/*將前面生成的區(qū)段壓入堆棧*/while(!IsStackEmpty(s))/*終止判斷*/{/*出棧*/PopStack(s,span);/*處理下面掃描線*/y=span->y-1;xRight=span->xRight;i=span->xLeft;