计算机图形学实验一

计算机图形学实验一实验一二维基本图元的生成与填充实验目的了解并掌握二维基本图元的生成算法与填充算法。实现直线生成的DDA算法、中点算法和Bresenham算法。实现圆和椭圆生成的DDA和中点算法,对几种算法的优缺点有感性认识。实验内容和要求选择自己熟悉的任何编程语言,建议使用VC++6.0。创建良好的用户界面,包括菜单,参数输入区域和图形显示区域。实现生成直线的DDA算法、中点算法和Bresenham算法。实现圆弧生成的中点算法。实现多边形生成的常用算法,如扫描线算法,边缘填充算法。实现一般连通区域的基于扫描线的种子填充算法。将生成算法以菜单或按钮形式集成到用户界面上。直线与圆的坐标参数可以用鼠标或键盘输入。6.可以实现任何情形的直线和圆的生成。实验报告用户界面的设计思想和框图。各种实现算法的算法思想。算法验证例子。上交源程序。（2）注意上述程序考虑到当k1的情形x每增加1，y最多增加1；当k>1时，y每增加1，x相应增加1/k。在这个算法中，y与k用浮点数表示，而且每一步都要对y进行四舍五入后取整。//中点算法生成直线voidCMyView::OnMidpointline(){CDC*pDC=GetDC();intxa=300,ya=200,xb=450,yb=300,c=RGB(0,255,0);floata,b,d1,d2,d,x,y;a=ya-yb,b=xb-xa,d=2*a+b;d1=2*a,d2=2*(a+b);x=xa,y=ya;pDC->SetPixel(x,y,c);while(x<xb){if(d<0){x++,y++,d+=d2;}else{x++,d+=d1;}pDC->SetPixel(x,y,c);}ReleaseDC(pDC);}说明：（1）其中d是xp,yp的线性函数。为了提高运算效率，程序中采用增量计算。具体算法如下：若当前像素处于d>0情况，则取正右方像素P1(xp+1,yp)，判断下一个像素点的位置，应计算d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；，其中增量为a。若d<0时，则取右上方像素P2（xp+1,yp+1）。再判断下一像素，则要计算d2 =F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5) + c=d+a+b，增量为a+b。（2）画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b，因F(x0,y0)=0，则d0=a+0.5b。（3）程序中只利用d的符号，d的增量都是整数，只是初始值包含小数，用2d代替d，使程序中仅包含整数的运算。//Bresenham算法生成直线voidCMyView::OnBresenhamline(){CDC*pDC=GetDC();intx1=100,y1=200,x2=350,y2=100,c=RGB(0,0,255);inti,s1,s2,interchange;floatx,y,deltax,deltay,f,temp;x=x1;y=y1;deltax=abs(x2-x1);deltay=abs(y2-y1);if(x2-x1>=0)s1=1;elses1=-1;if(y2-y1>=0)s2=1;elses2=-1;if(deltay>deltax){temp=deltax;deltax=deltay;deltay=temp;interchange=1;}elseinterchange=0;f=2*deltay-deltax;pDC->SetPixel(x,y,c);for(i=1;i<=deltax;i++){if(f>=0){if(interchange==1)x+=s1;elsey+=s2;pDC->SetPixel(x,y,c);f=f-2*deltax;}else{if(interchange==1)y+=s2;elsex+=s1;f=f+2*deltay;}}}说明：（1）以上程序已经考虑到所有象限直线的生成。（2）Bresenham算法的优点如下：①不必计算直线的斜率，因此不做除法。②不用浮点数，只用整数。③只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。④Bresenham算法的运算速度很快。圆弧生成程序设计的步骤如下：（1）创建应用程序框架，以上面建立的单文档程序框架为基础。（2）编辑菜单资源。在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-3中的定义添加编辑菜单资源。此时建好的菜单如图1-3所示。图1-3程序主菜单表图1-3程序主菜单菜单标题菜单项标题标示符ID圆中点画圆ID_MIDPOINTCIRCLEBresenham画圆ID_BRESENHAMCIRCLE（3）添加消息处理函数。利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-4建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。表1-4菜单项的消息处理函数菜单项ID消息消息处理函数ID_MIDPOINTCIRCLECONMMANOnMidpointcircleID_BRESENHAMCIRCLECONMMANOnBresenhamcircle（4）程序结构代码，在CMyView.cpp文件中的相应位置添加如下代码。voidCMyView::OnMidpointcircle()//中点算法绘制圆，如图1-4所示{图1-4图1-4中点算法绘制圆CDC*pDC=GetDC();intxc=300,yc=300,r=50,c=0;intx,y;floatd;x=0;y=r;d=1.25-r;pDC->SetPixel((xc+x),(yc+y),c);pDC->SetPixel((xc-x),(yc+y),c);pDC->SetPixel((xc+x),(yc-y),c);pDC->SetPixel((xc-x),(yc-y),c);pDC->SetPixel((xc+y),(yc+x),c);pDC->SetPixel((xc-y),(yc+x),c);pDC->SetPixel((xc+y),(yc-x),c);pDC->SetPixel((xc-y),(yc-x),c);while(x<=y){if(d<0) d+=2*x+3;else{d+=2*(x-y)+5;y--;}x++;pDC->SetPixel((xc+x),(yc+y),c);pDC->SetPixel((xc-x),(yc+y),c);pDC->SetPixel((xc+x),(yc-y),c);pDC->SetPixel((xc-x),(yc-y),c);pDC->SetPixel((xc+y),(yc+x),c);pDC->SetPixel((xc-y),(yc+x),c);pDC->SetPixel((xc+y),(yc-x),c);pDC->SetPixel((xc-y),(yc-x),c);}}voidCMyView::OnBresenhamcircle()////Bresenham算法绘制圆，如图1-5所示{CDC*pDC=GetDC();intxc=100,yc=100,radius=50,c=0;图1-5图1-5Bresenham算法绘制圆while(x<y){pDC->SetPixel(xc+x,yc+y,c);pDC->SetPixel(xc-x,yc+y,c);pDC->SetPixel(xc+x,yc-y,c);pDC->SetPixel(xc-x,yc-y,c);pDC->SetPixel(xc+y,yc+x,c);pDC->SetPixel(xc-y,yc+x,c);pDC->SetPixel(xc+y,yc-x,c);pDC->SetPixel(xc-y,yc-x,c);if(p<0)p=p+4*x+6;else{p=p+4*(x-y)+10;y-=1;}x+=1;}if(x==y)pDC->SetPixel(xc+x,yc+y,c);pDC->SetPixel(xc-x,yc+y,c);pDC->SetPixel(xc+x,yc-y,c);pDC->SetPixel(xc-x,yc-y,c);pDC->SetPixel(xc+y,yc+x,c);pDC->SetPixel(xc-y,yc+x,c);pDC->SetPixel(xc+y,yc-x,c);pDC->SetPixel(xc-y,yc-x,c);}多边形填充程序设计的步骤如下：（1）创建应用程序框架，以上述单文档程序框架为基础，创建如图1-17所示应用程序界面。（2）编辑菜单资源。在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-7中的定义添加编辑菜单资源。此时建好的菜单如图1-18所示。图1-17程序界面表1-7菜单资源表菜单标题菜单项标题标示符ID区域填充多边形扫描填充ID_SCANFILL种子填充ID_SEEDFILL图1-18程序主菜单（3）添加消息处理函数。利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-8建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。表1-8菜单项的消息处理函数菜单项ID消息消息处理函数ID_SCANFILLCONMMANOnScanfillID_SEEDFILLCONMMANOnSeedfill（4）添加程序结构代码。①在“基本图形的生成View.h”适当位置添加以下黑体字部分代码：typedefstruct//建立边表结构{intnum,ymin,ymax;floatxmin,xmax,dx;}Edge;classCMyView:publicCView{protected://createfromserializationonly public:Cpointptset[7];Edgeedge[7],edge1[7],newedge[1]; }②在OnDraw()函数中添加如下黑体字部分代码。voidCMyView::OnDraw(CDC*pDC)//绘制要填充的多边形{CMyDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);CPennewpen(PS_SOLID,1,RGB(255,0,0));CPen*old=pDC->SelectObject(&newpen);pDC->TextOut(20,20,"双击鼠标左键,出现需填充的多边形,点击相关功能菜单实现区域填充");pDC->TextOut(20,50,"进行种子填充,需用鼠标右键,单击多边形内一点,作为开始填充的种子点");pDC->SelectObject(old);}③在菜单项的消息处理函数实体中添加以下黑体字部分代码。voidCMyView::OnScanfill()//扫描线算法进行多边形区域填充，如图1-19所示{CDC*pDC=GetDC(); CPennewpen(PS_SOLID,1,RGB(0,255,0)); CPen*old=pDC->SelectObject(&newpen); intj,k,s=0;图1-19扫描线算法区域填充 intp[5];//每根扫描线交点图1-19扫描线算法区域填充 intpmin,pmax; for(inti=0;i<6;i++)//建立边表 { edge[i].dx=(float)(spt[i+1].x-spt[i].x)/(spt[i+1].y-spt[i].y); if(spt[i].y<=spt[i+1].y){ edge[i].num=i; edge[i].ymin=spt[i].y; edge[i].ymax=spt[i+1].y; edge[i].xmin=(float)spt[i].x; edge[i].xmax=(float)spt[i+1].x; pmax=spt[i+1].y; pmin=spt[i].y; } else{ edge[i].num=i; edge[i].ymin=spt[i+1].y; edge[i].ymax=spt[i].y; edge[i].xmax=(float)spt[i].x; edge[i].xmin=(float)spt[i+1].x; pmax=spt[i].y; pmin=spt[i+1].y; } } for(intr=1;r<6;r++) //排序edge(yUpper，xIntersect) { for(intq=0;q<6-r;q++) { if(edge[q].ymin<edge[q+1].ymin) { newedge[0]=edge[q]; edge[q]=edge[q+1]; edge[q+1]=newedge[0]; } } } for(intscan=pmax-1;scan>pmin+1;scan--) { intb=0; k=s; for(j=k;j<6;j++) { { if(scan==edge[j].ymax) { if(spt[edge[j].num+1].y<edge[j].ymax) { b++; p[b]=(int)edge[j].xmax; } if(spt[edge[j].num-1].y<edge[j].ymax) { b++; p[b]=(int)edge[j].xmax; } } if((scan>edge[j].ymin)&&(scan<edge[j].ymax)) { b++; p[b]=(int)(edge[j].xmax+edge[j].dx*(scan-edge[j].ymax)); } } // if(scan<=edge[j].ymin)// s=j; } if(b>1) { for(intu=1;u<b;u++) { pDC->MoveTo(p[u]+3,scan); u++; pDC->LineTo(p[u],scan); } } } pDC->SelectObject(old); }说明：双击，出现需填充的多边形，单击相关功能菜单实现区域填充。voidCMyView::OnSeedfill()//种子算法进行多边形区域填充，如图1-20所示{CWindowDCdc(this); intfill=RGB(0,255,0);图1-20种子算法区域填充 intboundary=RGB(255,0,0);图1-20种子算法区域填充 CPointpt=s_point; intx,y,p0,pmin,pmax; //求多边形的最大最小值 for(intm=1;m<7;m++) { for(intn=0;n<7-m;n++) { if(spt[n].y<spt[n+1].y) { p0=spt[n].y; spt[n]=spt[n+1]; spt[n+1]=p0; } } } pmax=spt[0].y,pmin=spt[6].y; x=s_point.x; y=s_point.y; for(;y<pmax+1;y++) { intcurrent=dc.GetPixel(x,y); while((current!=boundary)&&(current!=fill)) { dc.SetPixel(x,y,fill); x++; current=dc.GetPixel(x,y); } x=s_point.x; x--; current=dc.GetPixel(x,y); while((current!=boundary)&&(current!=fill)) { dc.SetPixel(x,y,fill); x--; current=dc.GetPixel(x,y); } x=s_point.x; } x=s_point.x; y=s_point.y-1; for(;y>pmin-2;y--) { intcurrent=dc.GetPixel(x,y);while((current!=boundary)&&(current!=fill)) { dc.SetPixel(x,y,fill); x++; current=dc.GetPixel(x,y); }