安徽建筑工业学院计算机图形学实验报告院（系）名称：专业：班级：姓名：学号：指导老师：实验一实现任意直线的中点画线算法【实验目的】掌握直线的中点画线算法；【实验环境】VC++6.0【实验内容】利用任意的一个实验环境，编制源程序，实现直线的中点画线法。

【实验原理】假定直线斜率k在0~1之间，当前象素点为（x p,y p），则下一个象素点有两种可选择点P1（x p+1,y p）或P2（x p+1,y p+1）。

若P1与P2的中点（x p+1,y p+0.5）称为M，Q为理想直线与x=x p+1垂线的交点。

当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。

这就是中点画线法的基本原理。

图2.1.2 中点画线法每步迭代涉及的象素和中点示意图下面讨论中点画线法的实现。

过点(x0,y0)、(x1, y1)的直线段L的方程式为F(x,y)=ax+by+c=0，其中，a=y0-y1, b=x1-x0, c=x0y1-x1y0，欲判断中点M在Q点的上方还是下方，只要把M代入F（x，y），并判断它的符号即可。

为此，我们构造判别式:d=F(M)=F(x p+1, y p+0.5)=a(x p+1)+b(y p+0.5)+c当d<0时，M在L(Q点)下方，取P2为下一个象素；当d>0时，M在L(Q点)上方，取P1为下一个象素；当d=0时，选P1或P2均可，约定取P1为下一个象素；注意到d是x p, y p的线性函数，可采用增量计算，提高运算效率。

若当前象素处于d 0情况，则取正右方象素P1(x p+1, y p),要判下一个象素位置，应计算d1=F(x p+2, y p+0.5)=a(x p+2)+b(y p+0.5)=d+a，增量为a。

若d<0时，则取右上方象素P2(x p+1, y p+1)。

要判断再下一象素，则要计算d2= F(x p+2, y p+1.5)=a(x p+2)+b(y p+1.5)+c=d+a+b ，增量为a＋b。

画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b，因F(x0, y0)=0，所以d0=a+0.5b。

由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。

因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法程序。

【实验程序】void Midpoint Line (int x0,int y0,int x1, int y1,int color){ int a, b, d1, d2, d, x, y；a=y0-y1； b=x1-x0；d=2*a+b；d1=2*a；d2=2* (a+b)；x=x0；y=y0；drawpixel(x, y, color);while (x<x1){ if (d<0) {x++；y++； d+=d2; }else {x++； d+=d1;}drawpixel (x, y, color);} /* while */} /* mid PointLine */举例：用中点画线方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。

a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 ,x y d0 0 11 0 -32 1 33 1 -142 552 15 2.1.3 中点画线法实验二实现任意一种线段的裁剪算法以及多边形裁剪算法【实验目的】1、掌握直线段裁剪的基本原理；2、掌握多边形裁剪的基本原理；【实验环境】VC++6.0【实验内容】编制程序，完成直线段和多边形的裁减过程。

【实验原理】1．算法基本思想对每条直线段p1(x1,y1)p2(x2,y2)分三种情况处理：(1) 直线段完全可见，“简取”之。

(2) 直线段完全不可见，“简弃”之。

(3) 直线段既不满足“简取”的条件，也不满足“简弃”的条件，需要对直线段按交点进行分段，分段后重复上述处理。

2．算法步骤(1) 编码对于任一端点(x,y)，赋予一个4 位的二进制码D3D2D1D0。

编码规则如下：若x<wxl，则D0=1，否则D0=0；若x>wxr，则D1=1，否则D1=0；若y<wyb，则D2=1，否则D2=0；若y>wyt，则D3=1，否则D3=0。

(2) 裁剪先求出端点p1 和p2 的编码code1 和code2，然后：若code1|code2=0，对直线段应简取之。

若code1&code2≠0，对直线段可简弃之。

若上述两条件均不成立。

则需求出直线段与窗口边界的交点。

在交点处把线段一分为二，其中必有一段完全在窗口外，可以弃之。

再对另一段重复进行上述处理，直到该线段完全被舍弃或者找到位于窗口内的一段线段为止。

(3) 求交假定直线的端点坐标为(x1,y1)和(x2,y2)左、右边界交点的计算上、下边界交点的计算。

3．算法实现(1) 输入直线段的两端点坐标：p1(x1,y1)、p2(x2,y2)，以及窗口的四条边界坐标：wyt、wyb、wxl 和wxr。

(2) 对p1、p2 进行编码：点p1 的编码为code1，点p2 的编码为code2。

(3) 若code1|code2=0，对直线段应简取之，转(6)；否则，若code1&code2≠0，对直线段可简弃之，转(7)；当上述两条均不满足时，进行步骤(4)。

(4) 确保p1 在窗口外部：若p1 在窗口内，则交换p1 和p2 的坐标值和编码。

(5) 按左、右、上、下的顺序求出直线段与窗口边界的交点，并用该交点的坐标值替换p1 的坐标值。

也即在交点s 处把线段一分为二，并去掉p1s 这一段。

考虑到p1 是窗口外的一点，因此可以去掉p1s。

转(2)。

(6) 用直线扫描转换算法画出当前的直线段p1p2。

(7) 算法结束。

【实验程序】一：Cohen-Sutherland线段裁剪算法#include <gl/glut.h>//#include <gl/wingdi.h> /* SetPixel() */#include <math.h>#include <stdio.h>/////////////////////////////////////////////////////////////////// ////////const winLeftBitCode=0x1;const winRightBitCode=0x2;const winBottomBitCode=0x4;const winTopBitCode=0x8;/////////////////////////////////////////////////////////////////// ////////class wcPt2D{ public:GLfloat x,y; };/////////////////////////////////////////////////////////////////// ////////inline int inside(int code){return int (!code);}/////////////////////////////////////////////////////////////////// ///////inline int reject(int code1,int code2){return int (code1&code2);}/////////////////////////////////////////////////////////////////// //////inline int accept(int code1,int code2){return int (!(code1|code2));}//////////////////////////////////////////////////////////////////// /////GLubyte encode(wcPt2D pt,wcPt2D winMin,wcPt2D winMax){GLubyte code=0x00;if(pt.x<winMin.x)code=code|winLeftBitCode;if (pt.x>winMax.x)code=code+winRightBitCode;if(pt.y<winMin.y)code=code|winBottomBitCode;if(pt.y>winMax.y)code=code|winTopBitCode;return (code);}//////////////////////////////////////////////////////////////////// ////////void swapPts(wcPt2D *p1,wcPt2D *p2){wcPt2D tmp;tmp=*p1;*p1=*p2;*p2=tmp;}/////////////////////////////////////////////////////////////////// ///////void swapCodes(GLubyte *c1,GLubyte *c2){GLubyte tmp;tmp=*c1; *c1=*c2;*c2=tmp;}/////////////////////////////////////////////////////////////////// /////void draw_pixel(int ix,int iy/*,int value*/){glBegin(GL_POINTS);glVertex2i(ix,iy);glEnd();}/////////////////////////////////////////////////////////////////// /////int inline round(const float a){return int (a+0.5);}/////////////////////////////////////////////////////////////////// //////void lineDDA(int x0,int y0,int x_end,int y_end,double a,double b,double c){glColor3f(a,b,c);int dx=x_end-x0;int dy=y_end-y0;int steps,k;float xIncrement,yIncrement,x=x0,y=y0;if(abs(dx)>abs(dy))steps=abs(dx);elsesteps=abs(dy);xIncrement=float (dx)/float (steps);yIncrement=float (dy)/float (steps);draw_pixel(round(x),round(y));for (k=0;k<steps;k++){x+=xIncrement;y+=yIncrement;draw_pixel(round(x),round(y));}}//////////////////////////////////////////////////////////////////// ////////////////void lineClipCohSuth(wcPt2D winMin,wcPt2D winMax,wcPt2D p1,wcPt2D p2) {GLubyte code1,code2;GLint done=false,plotLine=false;GLfloat m;while(!done){code1=encode(p1,winMin,winMax);code2=encode(p2,winMin,winMax);if(accept(code1,code2)){done=true;plotLine=true;}elseif(reject(code1,code2))done=true;else{if(inside(code1)){swapPts(&p1,&p2);swapCodes(&code1,&code2);}if(p2.x!=p1.x)m=(p2.y-p1.y)/(p2.x-p1.x);if(code1&winLeftBitCode){p1.y+=(winMin.x-p1.x)*m;p1.x=winMin.x;}elseif(code1&winRightBitCode){p1.y+=(winMax.x-p1.x)*m;p1.x=winMax.x;}elseif(code1&winBottomBitCode){if(p2.x!=p1.x)p1.x+=(winMin.y-p1.y)/m;p1.y=winMin.y;}elseif(code1&winTopBitCode){ if(p2.x!=p1.x)p1.x+=(winMax.y-p1.y)/m;p1.y=winMax.y;}}}if(plotLine)lineDDA(round(p1.x),round(p1.y),round(p2.x),r ound(p2.y),0.0,0.0,1.0);}//////////////////////////////////////////////////////////////////// ///////////////////void display(){glClear(GL_COLOR_BUFFER_BIT);wcPt2DwinMin,winMax,p1,p2,q1,q2,t1,t2,m1,m2;//裁剪窗口winMin.x=80;winMin.y=100;winMax.x=290;winMax.y=500;/*lineDDA(80,100,80,450,1.0,0.0,0.0);lineDDA(80,100,290,100,1.0,0.0,0.0);lineDDA(290,100,290,450,1.0,0.0,0.0);lineDDA(80,450,290,450,1.0,0.0,0.0);*//* //全图winMin.x=0;winMin.y=000;winMax.x=500;winMax.y=500;*////////////////////////p1.x=0;p1.y=0;p2.x=400;p2.y=400;//////////////////////q1.x=0;q1.y=0;q2.x=100;q2.y=400;//////////////////////t1.x=100;t1.y=400;t2.x=400;t2.y=400;//////////////////////m1.x=300;m1.y=200;m2.x=100;m2.y=400;//只显示裁剪框内的线段lineClipCohSuth(winMin,winMax,p1,p2);lineClipCohSuth(winMin,winMax,q1,q2);lineClipCohSuth(winMin,winMax,t1,t2);lineClipCohSuth(winMin,winMax,m1,m2) ;//显示裁剪框和待剪线段/*lineDDA(300,200,100,400,0.0,0.0,1.0);lineDDA(0,0,100,400,0.0,0.0,1.0);lineDDA(100,400,400,400,0.0,0.0,1.0);lineDDA(0,0,400,400,0.0,0.0,1.0);*/glFlush();}void myinit(){glClearColor(0.8,1.0,1.0,1.0);//glColor3f(0.0,0.0,1.0);glPointSize(1.0);glMatrixMode(GL_PROJECTION);glLoadIdentity();gluOrtho2D(0.0,500.0,0.0,500.0);glViewport(0,0,200,500);}void main(int argc,char **argv ){glutInit(&argc,argv);glutInitDisplayMode(GLUT_SINGLE|GL UT_RGB);glutInitWindowSize(500,500);glutInitWindowPosition(200.0,200.0);glutCreateWindow("CG_test_CG_test_Co hen-Sutherland 线段裁剪算法示例");// glutFullScreen();glutDisplayFunc(display);myinit();glutMainLoop();}稍微修改源程序即可得到以下裁剪框以及被裁剪线段：二：Sutherland_Hodgman多边形裁剪算法#define TRUE 1#define FALSE 0typedef struct {float x, y;} vertex;void intersect(p1, p2, clipboundary, intersectp)vertex p1, p2, *clipboundary, *intersectpt;/* p1和p2为多边形的边的起点和终点，clipboundary为窗口边界，intersectpt中返回边与窗口边界的交点*/{if ( clipboundary[0].y== clipboundary[1].y ) /* 水平边界*/{intersectpt->y = clipboundary[0].y;intersectpt->x = p1.x + (clipboundary[0].y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y);}else /* 垂直边界*/{intersectpt->x = clipboundary[0].x;intersectpt->y = p1.y + (clipboundary[0].x-p1.x)*(p2.y-p1.y)/(p2.x-p1.x);}}int inside(testvertex, clipboundary)vertex testvertex, *clipboundary;/* 如果顶点testvertex在窗口边界clipboundary 的内部，那么返回TRUE；否则返回FALSE */{if ( clipboundary[1].x < clipboundary[0].x ) /* 上边界*/if ( testvertex.y <= clipboundary[0].y )return TRUE;if ( clipboundary[1].x > clipboundary[0].x ) /* 下边界*/if ( testvertex.y >= clipboundary[0].y )return TRUE;if ( clipboundary[1].y > clipboundary[0].y ) /* 右边界*/if ( testvertex.x <= clipboundary[0].x )return TRUE;if ( clipboundary[1].y < clipboundary[0].y ) /* 左边界*/if ( testvertex.y <= clipboundary[0].x )return TRUE;return FALSE;}outputvertex(outvertex, outlength, outvertexlist)vertex outvertex;int *outlength;vertex *outvertexlist/* 向输出顶点序列中输出顶点outvertex */{outvertexlist[*outlength] = outvertex;(*outlength)++;}voidSutherland_Hodgman_Polygon_Clipping(invertexlist, outvertexlist, inlength, outlength, clipboundary) vertex *invertexlist, *outvertexlist;int inlength, *outlength;vertex *clipboundary;/* invertexlist为输入顶点序列，inlength为输入序列长度；outvertexlist为输出顶点序列，outlenght 中返回输出序列长度；clipboundary为窗口边界*/ {vertex s, p, i;int j;*outlength = 0;s = invertexlist[inlength-1]; /* 输入顶点序列的最后一个顶点*/for ( j=0; j<inlength; j++ ){p = invertexlist[j];if ( inside(p,clipboundary) ) /* 情况1和4 */{if ( inside(s,clipboundary) ) /* 情况1 */outputvertex(p,outlength,outvertexlist);else /* 情况4 */{intersect(s,p,clipboundary,&i);outputvertex(i,outlength,outvertexlist);outputvertex(p,outlength,outvertexlist);}}else /* 情况2和3 */{ if ( inside(s,clipboundary) ) /* 情况2 */{intersect(s,p,clipboundary,&i);outputvertex(i,outlength,outvertexlist);}} /* 情况3无输出*/s = p; /* 准备处理下一条边*/}}实验三实现任意一种区域填充算法【实验目的】1、掌握多边形填充的基本原理；2、掌握边界标志算法来实现多边形填充的思想。