计算机图形学实验一

1、实验一 二维根本图元的生成与填充实验目的1. 了解并掌握二维根本图元的生成算法与填充算法。2. 实现直线生成的 DDA算法、中点算法和 Bresenham算法。3. 实现圆和椭圆生成的 DDA和中点算法，对几种算法的优缺点有感性认识。二.实验内容和要求1. 选择自己熟悉的任何编程语言,建议使用VC+6.0。2. 创立良好的用户界面，包括菜单，参数输入区域和图形显示区域。3. 实现生成直线的 DDA算法、中点算法和 Bresenham算法。4. 实现圆弧生成的中点算法。5. 实现多边形生成的常用算法，如扫描线算法，边缘填充算法。6. 实现一般连通区域的基于扫描线的种子填充算法。7. 将生成算法以

2、菜单或按钮形式集成到用户界面上。8. 直线与圆的坐标参数可以用鼠标或键盘输入。6.可以实现任何情形的直线和圆的生成。实验报告1 用户界面的设计思想和框图。2 各种实现算法的算法思想。3 算法验证例子。4上交源程序。直线生成程序设计的步骤如下:为编程实现上述算法，本程序利用最根本的绘制元素如点、直线等，绘制图形。如图1-1所示，为程序运行主界面， 通过选择菜单及下拉菜单的各功能项分别完成各种对应算 法的图形绘制。图1-1根本图形生成的程序运行界面2 创立工程名称为“根本图形的生成单文档应用程序框架1启动VC,选择“文件 | “新建菜单命令，并在弹出的新建对话框中单击“工程 标签。2选择MFC A

3、ppWizard(exe)，在“工程名称编辑框中输入“根本图形的生成作为工程名称，单击“确定按钮，出现Step 1对话框。3选择“单个文档选项，单击“下一个按钮，出现Step 2对话框。4接受默认选项，单击“下一个按钮，在出现的Step 3Step 5对话框中，接受默认选项，单击“下一个按钮。5在Step 6对话框中单击“完成按钮，即完成“根本图形的生成应用程序的所有 选项，随后出现工程信息对话框记录以上步骤各选项选择情况，如图1-2所示，单击“确定按钮，完成应用程序框架的创立。图1-2 信息程序根本3 .编辑菜单资源设计如图1-1所示的菜单项。在工作区的ResourceView标签中，单击M

4、enu项左边“ + , 然后双击其子项IDR_MAINFRAME ，并根据表1-1中的定义编辑菜单资源。此时 VC已自 动建好程序框架，如图 1-2所示。表1-1菜单资源表菜单标题菜单项标题标示符ID直线DDA算法生成直线ID DDALINEBresenham算法生成直线ID BRESENHAMLINE中点算法生成直线ID MIDPOINTLINE4 添加消息处理函数利用 ClassWizard建立类向导为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择 CMyView，根据表1-2建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。表1-2菜单项的消息处

5、理函数菜单项ID消息消息处理函数ID_DDALINECONMMANOnDdalineID MIDPOINTLINECONMMANOnMidpointlineID BRESENHAMLINECONMMANOnBresenhamline5 程序结构代码，：/ DDA算法生成直线void CMyView: OnDdaline()CDC* pDC=GetDC(); /获得设备指针int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0);/ 定义直线的两端点，直线颜色int x,y;float dx, dy, k;dx=(float)(xb-xa), dy=(floa

6、t)(yb_ya);k=dy/dx, y=ya;if(abs(k)<1)for (x=xa;x<=xb;x+)pDC->SetPixel (x,int(y+0.5),c);y=y+k;if(abs(k)>=1)for (y=ya;y<=yb;y+)pDC->SetPixel (int(x+0.5),y,c);x=x+1/k;ReleaseDC(pDC);说明：1以上代码理论上通过定义直线的两端点，可得到任意端点之间的一直线，但由于一般屏幕坐标采用右手系坐标，屏幕上只有正的x, y值，屏幕坐标与窗口坐标之间转换知识请参考弟3早。2注意上述程序考虑到当k 1的情

7、形x每增加1，y最多增加1;当k>1时，y每增加1, x相应增加1/k。在这个算法中，y与k用浮点数表示，而且每一步都要对y进行四舍五入后取整。/中点算法生成直线void CMyView:OnMidpointline()CDC* pDC=GetDC();int xa=300, ya=200, xb=450, yb=300,c=RGB(0,255,0);float a, 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

8、<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),判断下一个像素点的位置，应计算 di=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a ；，其中增量为 a。假设 d<0 时，那么取 右上方像素 P2xp+1, yp+1。再判断下一像素，那么要计算 d2 = F(

9、xp+2, yp+1.5)=a(xp+2)+b(y p+1.5) + c=d+a+b ,增量为 a+b。2 画线从(xo, yo)开始，d 的初值 do=F(xo+1, yo+0.5)=F(x 0, yo，因 F(xo, yo)=0，贝U d0=a+0.5b。3程序中只利用d的符号，d的增量都是整数，只是初始值包含小数，用2d代替d,使程序中仅包含整数的运算。/Bresenham 算法生成直线void CMyView:OnBresenhamline()CDC* pDC=GetDC();int x1=1oo, y1=2oo, x2=35o, y2=1oo,c=RGB(o,o,255);int i

10、,s1,s2,interchange;float x,y,deltax,deltay,f,temp;x=x1;y=y1;deltax=abs(x2-x1);deltay=abs(y2-y1);if(x2-x1>=o) s1=1; else s1=-1;if(y2-y1>=o) s2=1; else s2=-1;if(deltay>deltax)temp=deltax;deltax=deltay;deltay=temp; interchange=1;else interchange=o;f=2*deltay-deltax;pDC->SetPixel(x,y,c);for(

11、i=1;i<=deltax;i+)if(f>=o)if(interchange=1) x+=s1;else y+=s2;pDC->SetPixel(x,y,c);f=f-2*deltax;elseif(interchange=1) y+=s2;else x+=s1;f=f+2*deltay;说明：1以上程序已经考虑到所有象限直线的生成。2Bresenham算法的优点如下： 不必计算直线的斜率，因此不做除法。 不用浮点数，只用整数。 只做整数加减运算和乘2运算，而乘2运算可以用移位操作实现。 Bresenham算法的运算速度很快。圆弧生成程序设计的步骤如下:1创立应用程序框架，

12、以上面建立的单文档程序框架为根底。卫1 4刼归.I图1-3程序主菜单2编辑菜单资源。在工作区的 ResourceView标签中，单击 Menu项 左边“ +，然后双击其子项IDR_MAINFRAME ，并根据表1-3中的定义添加编辑菜单资源。此时建好的 菜单如图1-3所示。表1-3菜单资源表菜单标题菜单项标题标示符ID圆中点画圆ID_MIDPOINTCIRCLEBrese nham 画圆ID BRESENHAMCIRCLE3添加消息处理函数。利用 ClassWizard建立类向导为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择 CMyView，根据表1-4建立如下的消息映射

13、函数，ClassWizard会自动完成有关的函数声明。表1-4菜单项的消息处理函数菜单项ID消息消息处理函数ID MIDPOINTCIRCLECONMMANOnMidpointcircleID BRESENHAMCIRCLECONMMANOnBresenhamcircle4程序结构代码,中点算法绘制圆，如图1-4所示图1-4中点算法绘制圆void CMyView:OnMidpointcircle() / TODO: Add your command handler code hereCDC* pDC=GetDC();int xc=300, yc=300, r=50, c=0;int x,y;f

14、loat d;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

15、),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),(

16、yc-x),c); pDC->SetPixel (xc-y),(yc-x),c);算法绘制圆，如图1-5所示void CMyView:OnBresenhamcircle() / Bresenham CDC* pDC=GetDC();int xc=100, yc=100, radius=50, c=0;int x=0,y=radius,p=3-2*radius;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-

17、>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;elsep=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->SetPixe

18、l(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_MAI

19、NFRAME ，并根据表1-7中的定义添加编辑菜单资源。此时建好的菜单如图1-18所示。图1-17 程序界面表1-7菜单资源表菜单标题菜单项标题标示符ID区域填充多边形扫描填充ID SCANFILL种子填充ID_SEEDFILL冥件瞧聊爲童豪冶宜屿圆相叵城壤床曹貼知3笫过巴归轴减填充图1-18 程序主菜单3添加消息处理函数。利用 Classwizard建立类向导为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择 CMyView，根据表1-8建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。表1-8菜单项的消息处理函数菜单项ID消息消息处理函数ID SCA

20、NFILLCONMMANOnScanfillID SEEDFILLCONMMANOnSeedfill4添加程序结构代码。 在“适当位置添加以下黑体字局部代码:typedef struct /建立边表结构int num, ymin,ymax;float xmin,xmax,dx; Edge;class CMyView : public CViewprotected: / create from serialization onlypublic:Cpoint ptset7;Edge edge7,edge17,newedge1;在OnDraw()函数中添加如下黑体字局部代码。void CMyView

21、:OnDraw(CDC* pDC)CMyDoc* pDoc = GetDocument();绘制要填充的多边形ASSERT_VALID(pDoc);CPen newpen(PS_SOLID,1,RGB(255,O,O);CPen *old=pDC->SelectObject(&newpen); pDC->TextOut(2O,2O,"pDC->TextOut(2O,5O,"双击鼠标左键，岀现需填充的多边形，点击相关功能菜单实现 区域填充");进行种子填充，需用鼠标右键，单击多边形内一点，作为开始 填充的种子点");pDC->

22、;SelectObject(old);在菜单项的消息处理函数实体中添加以下黑体字局部代码。void CMyView:OnScanfill() / 扫描线算法进行多边形区域填充，如图1-19所示CDC* pDC=GetDC();CPen newpen(PS_SOLID,1,RGB(O,255,O);CPen *old=pDC->SelectObject(&newpen); int j,k,s=O;int p5; /每根扫描线交点int pmin,pmax;for(int i=0;i<6;i+)edgei.dx=(float)(spti+1.x-spti.x)/(spti+1.

23、y-spti.y);if(spt【i.yv=spt【i+1.y) edgei.num=i; edgei.ymin=spti.y; edgei.ymax=spti+1.y; edgei.xmin=(float)spti.x; edgei.xmax=(float)spti+1.x;建立边表图1-19扫描线算法区域填充pmax=spti+1.y;pmin=spti.y;elseedgei.num=i;edgei.ymin=spti+1.y;edgei.ymax=spti.y;edgei.xmax=(float)spti.x;edgei.xmin=(float)spti+1.x;pmax=spti.y

24、;pmin=spti+1.y;for(int r=1;r<6;r+) / 排序 edge(yUpper ， xIntersect) for(int q=0;q<6-r;q+)if(edgeq.ymin<edgeq+1.ymin)newedge0=edgeq; edgeq=edgeq+1; edgeq+1=newedge0;for(int scan=pmax-1;scan>pmin+1;scan-)int b=0;k=s;for(j=k;j<6;j+)判断与线段相交if(scan>edgej.ymin)&&(scan<=edgej.yma

25、x)/if(scan=edgej.ymax)if(sptedgej.num+1.y<edgej.ymax)b+; pb=(int)edgej.xmax; if(sptedgej.num-1.y<edgej.ymax) b+;pb=(int)edgej.xmax; if(scan>edgej.ymin)&&(scan<edgej.ymax) b+; pb=(int)(edgej.xmax+edgej.dx*(scan-edgej. ymax);pDC->LineTo(sptedge0.num.x,sptedge0.num.y);if(scan<

26、=edgej.ymin)/s=j;if(b>1)for(int u=1;u<b;u+)pDC->MoveTo(pu+3,scan);u+;pDC->LineTo(pu,scan);pDC->SelectObject(old);说明：双击，出现需填充的多边形，单击相关功能菜单实现区域填充。void CMyView:OnSeedfill() /种子算法进行多边形区域填充，如图 1-20所示图1-20种子算法区域填充CWindowDC dc (this);int fill=RGB(0,255,0);int boundary=RGB(255,0,0);CPoint pt=

27、s_point;int x,y,p0,pmin,pmax;/求多边形的最大最小值for(int m=1;m<7;m+)for(int n=0;n<7-m;n+)if(sptn.y<sptn+1.y)p0=sptn.y;sptn=sptn+1;sptn+1=p0;pmax=spt0.y,pmin=spt6.y;x=s_point.x;y=s_point.y;for(;yvpmax+1;y+)int current=dc.GetPixel(x,y);while(current!=boundary )&&(current!=fill)dc.SetPixel(x,y,fill);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.