CG_实验2_基本图形元素(直线)生成算法的实现

实验二: 直线的生成算法的实现班级 08信计2班学号 20080502055 姓名分数一、实验目的和要求:1.理解直线生成的原理；2.掌握几种常用的直线生成算法；3.利用C实现直线生成的DDA算法。

二、实验内容:1.了解直线的生成原理2、掌握几种基本的直线生成算法: DDA画线法、中点画线法、Bresenham画线法。

3、仿照教材关于直线生成的DDA算法, 编译程序。

4.调试、编译、运行程序。

三、实验过程及结果分析1.直线DDA算法:算法原理：已知过端点P0（x0,y0）, P1（x1,y1）的直线段L(P0,P1), 斜率为k=(y1-y0)/(x1-x0), 画线过程从x的左端点x0开始, 向x右端点步进, 步长为1个像素, 计算相应的y坐标为y=kx+B。

计算y i+1 = kx i+B=kx i +B+kx=y i +kx当x=1,yi+1=yi+k, 即当x每递增1, y递增k。

由计算过程可知, y与k可能为浮点数, 需要取y整数, 源程序中round(y）=(int)(y+0.5)表示y四舍五入所得的整数值。

（1）程序代码:#include"stdio.h"#include"graphics.h"void linedda(int x0,int y0,int x1,int y1,int color){int x,dy,dx,y;float m;dx=x1-x0;dy=y1-y0;m=dy/dx;y=y0;for(x=x0;x<=x1;x++){putpixel(x,(int)(y+0.5),color);y+=m;setbkcolor(7);}}main(){int a,b,c,d,e;int graphdriver=DETECT;int graphmode=0;initgraph(&graphdriver,&graphmode,"");a=100;b=100;c=200;d=300;e=5;linedda(a,b,c,d,e);getch();closegraph();}运行结果:2.中点画线算法:假定所画直线的斜率为k∈[0,1], 如果在x方向上增量为1, 则y方向上的增量只能在0~1之间。

int dy=yr-y1, dx=xr-x1;
int ie;
/* integer scaled error term */
x=xl; y=yl; /* start at left endpoint */
ie =dx-2 *dy; /* initialize the error term */
while (x <= xr){ /* pixel-drawing loop */
2024/2/22
16
0≤m≤1时Bresenham算法的步骤为：
1. 输入直线的两端点P0(x0,y0)和P1(x1,y1)。
2. 计算初始值△x, △y, d=Δx-2Δy , x=x0, y=y0；
3. 绘制点(x,y)，根据d的符号进行如下操作： 若d<0，则(x,y)更新为(x+1,y+1)，d更新为
yi1
yi yi
1
(di 0) (di 0)
Pa (xi 1, yi 1)
Q
问题：算法结束了吗？ 有无优化的可能？
M (xi 1, yi 1/ 2)
P(xi , yi ) Pb (xi 1, yi )
注意：计算di 的运算量并不小.
2024/2/22
12
误差项的递推 若di<0，有
di1 F ( xi 2, yi 1.5) yi 1.5 m(xi 2) b yi 1.5 m(xi 1) b m di 1 m
M (xi 2, yi 1.5)
Q
M (xi 1, yi 0.5)
P(xi , yi )
2024/2/22
di<0
13
误差项的递推 若di≥0，有
di1 F (xi 2, yi 0.5) yi 0.5 m(xi 2) b yi 0.5 m(xi 1) b m di m

实验二直线段生成绘制的实现算法班级 08信计（2）班学号 20080502085 姓名王景超分数一、实验目的和要求：1.理解基本图形元素光栅化的基本原理2. 掌握一种基本图形元素光栅化算法3. 利用OpenGL实现直线光栅化的DDA算法二、实验内容：1. 根据所给的直线光栅化的示范源程序，在计算机上编译运行，输出正确结果；2. 指出示范程序采用的算法，以此为基础将其改造为中点线算法或Bresenham算法，写入实验报告；3. 根据示范代码，将其改造为圆的光栅化算法，写入实验报告；4. 了解和使用OpenGL的生成直线的命令，来验证程序运行结果。

三、实验结果分析：1．该程序实现了三种算法的直线段绘制2．比较三种算法的结果：像素逼近效果由好到差依次为：B算法、DDA算法、中点算法执行速度由快到慢依次为：中点算法、DDA算法、B算法程序代码如下：/* WIN-TC BGI 图形编程模板*/#include "Conio.h"#include "graphics.h"#define closegr closegraphvoid initgr(void) /* BGI初始化*/{int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果*/registerbgidriver(EGA VGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行*/initgraph(&gd, &gm, "");}/*-----------------------------数值微分法生成直线-----------------------------*/ void LineDDA1(int x0,int y0,int x1,int y1,int color)/*假定x0<x1,直线斜率m<-1*/{int y;float dy,dx,x,m;dx=x1-x0;dy=y1-y0;m=dx/dy;x=x0;for(y=y0;y>=y1;y--){putpixel((int)(x+0.5),y,color);x-=m;}}void LineDDA2(int x0,int y0,int x1,int y1,int color)/*假定x0<x1,直线斜率-1<=m<=1*/{int x;float dy,dx,y,m;dx=x1-x0;dy=y1-y0;m=dy/dx;y=y0;for(x=x0;x<=x1;x++){putpixel(x,(int)(y+0.5),color);y+=m;}}void LineDDA3(int x0,int y0,int x1,int y1,int color)/*假定x0<x1,直线斜率m>1*/{int y;float dy,dx,x,m;dx=x1-x0;dy=y1-y0;m=dx/dy;x=x0;for(y=y0;y<=y1;y++){putpixel((int)(x+0.5),y,color);x+=m;}}/*----------------------------中点算法生成直线--------------------------------*/ void MidPointLine1(int x0,int y0,int x1,int y1,int color){ /*假定x0<x1,直线斜率m<-1*/int dx,dy,incrE,incrNE,d,x,y;dx=x1-x0;dy=y1-y0;d=-2*dx-dy;incrE=-2*dx;incrNE=-2*(dx+dy);x=x0;y=y0;putpixel(x,y,color);while(y>=y1){if(d>0)d+=incrE;else{ d+=incrNE;x++;}y--;putpixel(x,y,color);}}void MidPointLine2(int x0,int y0,int x1,int y1,int color) { /*假定x0<x1,直线斜率-1<m<0*/int dx,dy,incrE,incrNE,d,x,y;dx=x1-x0;dy=y1-y0;d=-(dx+2*dy);incrE=-2*dy;incrNE=-2*(dx+dy);x=x0;y=y0;putpixel(x,y,color);while(x<x1){if(d<=0)d+=incrE;else{ d+=incrNE;y--;}x++;putpixel(x,y,color);}}void MidPointLine3(int x0,int y0,int x1,int y1,int color) { /* 假定x0<x1,直线斜率0<=m<=1 */int dx,dy,incrE,incrNE,d,x,y;dx=x1-x0;dy=y1-y0;d=dx-2*dy;incrE=-2*dy;incrNE=2*(dx-dy);x=x0;y=y0;putpixel(x,y,color);while(x<x1){if(d>0) d+=incrE;else{d+=incrNE;y++;}x++;putpixel(x,y,color);}}void MidPointLine4(int x0,int y0,int x1,int y1,int color){ /*假定x0<x1,直线斜率m>1*/int dx,dy,incrE,incrNE,d,x,y;dx=x1-x0;dy=y1-y0;d=2*dx-dy;incrE=2*dx;incrNE=2*(dx-dy);x=x0;y=y0;putpixel(x,y,color);while(x<x1){if(d<=0)d+=incrE;else{ d+=incrNE;x++;}y++;putpixel(x,y,color);}}/*-------------------------Bresenham算法生成直线-----------------------------*/ BresenhamLine(int x0,int y0,int x1,int y1,int color){int x,y,dx,dy,i;float m,d;dx=x1-x0;dy=y1-y0;m=dy/dx;d=0;x=x0;y=y0;putpixel(x,y,color);for(i=0;i<=dx;i++){d+=m;if(d>=0.5){y+=1;d-=1;}x++;putpixel(x,y,color);}}/*-------------------------------建立坐标系----------------------------------*/ void LineH(int x0,int x1,int y0,int color){int x,y;x=x0; y=y0;while(x<x1){putpixel(x,y,color);x++;}}void LineV(int y0,int y1,int x0,int color){int x,y;x=x0; y=y0;while(y<y1){putpixel(x,y,color);y++;}}int x0,y0,x1,y1,color,dx1,dy1;float m;int main(void){initgr(); /* BGI初始化*//*****此部分添加你自己的代码，例如line(25, 25, 220, 220);circle(100, 100, 50);等等*****//*-------------------------显示各种斜率的直线--------------------------------*/ MidPointLine1(300,400,340,240,125);MidPointLine2(240,340,400,300,255);MidPointLine3(240,300,400,340,255);MidPointLine4(300,240,340,400,255);LineH(240,400,320,255);LineV(240,400,320,255);outtextxy(398,318,">");outtextxy(280,420,"MidPointLine");LineDDA1(180,280,220,120,125);LineDDA2(120,220,280,180,255);LineDDA2(120,180,280,220,255);LineDDA3(180,120,220,280,255);LineH(120,280,200,255);LineV(120,280,200,255);outtextxy(180,300,"LineDDA");BresenhamLine(322,53,430,182,255);outtextxy(330,160,"Bresenham");/*----------------------------程序输入部分-----------------------------------*/ printf("firstpoint x0,y0:\n");scanf("%d,%d",&x0,&y0);printf("lastpoint x1,y1:\n");scanf("%d,%d",&x1,&y1);printf("color:\n");scanf("%d",&color);dx1=x1-x0;dy1=y1-y0;m=dy1/dx1;if(m<-1)MidPointLine1(x0,y0,x1,y1,color);else if(m>=-1&&m<0)MidPointLine2(x0,y0,x1,y1,color) ;else if(m>=0&&m<=1)MidPointLine3(x0,y0,x1,y1,color) ;elseMidPointLine4(x0,y0,x1,y1,color) ;getch(); /* 暂停一下，看看前面绘图代码的运行结果*/ closegr(); /* 恢复TEXT屏幕模式*/return 0;}运行结果：。

实验二直线的生成算法的实现班级 08信计二班学号 20080502086 姓名分数一、实验目的和要求：1、理解直线生成的基本原理2、熟悉直线的生成算法，掌握直线的绘制3、实现直线生成的DDA 中点画法 Bresenham算法4、了解Visual C++等编程环境中常用控件命令与绘图函数，初步掌握在试验设计集成下进行图形处理程序的设计方法二、实验内容：1、了解直线生成的原理直线DDA算法，中点画线算法，Bresenham画线算法2、编程实现DDA算法、Bresenham算法、中点画法绘制直线段三、实验结果分析1.DDA算法// 程序名称：基于 DDA 算法画任意斜率的直线#include <graphics.h>#include <conio.h>// 四舍五入int Round(float x){return (int)(x < 0 ? x - 0.5 : x + 0.5);}// 使用 DDA 算法画任意斜率的直线（包括起始点，不包括终止点）void Line_DDA(int x1, int y1, int x2, int y2, int color){float x, y; // 当前坐标点float cx, cy; // x、y 方向上的增量int steps = abs(x2 - x1) > abs(y2 - y1) ? abs(x2 - x1) : abs(y2 - y1);x = (float)x1;y = (float)y1;cx = (float)(x2 - x1) / steps;cy = (float)(y2 - y1) / steps;for(int i = 0; i < steps; i++){putpixel(Round(x), Round(y), color); // 在坐标 (x, y) 处画一个 color 颜色的点x += cx;y += cy;}}// 主函数void main(){initgraph(640, 480);// 测试画线Line_DDA(100, 1, 1, 478, GREEN);Line_DDA(1, 478, 638, 1, GREEN);// 按任意键退出getch();closegraph();}2.中点算法// 程序名称：基于中点算法画任意斜率的直线#include <graphics.h>#include <conio.h>// 使用中点算法画任意斜率的直线（包括起始点，不包括终止点）void Line_Midpoint(int x1, int y1, int x2, int y2, int color){int x = x1, y = y1;int a = y1 - y2, b = x2 - x1;int cx = (b >= 0 ? 1 : (b = -b, -1));int cy = (a <= 0 ? 1 : (a = -a, -1));putpixel(x, y, color);int d, d1, d2;if (-a <= b) // 斜率绝对值 <= 1{d = 2 * a + b;d1 = 2 * a;d2 = 2 * (a + b);while(x != x2){if (d < 0)y += cy, d += d2;elsed += d1;x += cx;putpixel(x, y, color);}}else // 斜率绝对值 > 1{d = 2 * b + a;d1 = 2 * b;d2 = 2 * (a + b);while(y != y2){if(d < 0)d += d1;elsex += cx, d += d2;y += cy;putpixel(x, y, color);}}}// 主函数void main(){initgraph(640, 480);// 测试画线Line_Midpoint(100, 1, 1, 478,YELLOW);Line_Midpoint(1, 478, 638, 1, YELLOW);// 按任意键退出getch();closegraph();}3. Bresenham 算法// 程序名称：基于 Bresenham 算法画任意斜率的直线#include <graphics.h>#include <conio.h>// 使用 Bresenham 算法画任意斜率的直线（包括起始点，不包括终止点）void Line_Bresenham(int x1, int y1, int x2, int y2, int color){int x = x1;int y = y1;int dx = abs(x2 - x1);int dy = abs(y2 - y1);int s1 = x2 > x1 ? 1 : -1;int s2 = y2 > y1 ? 1 : -1;bool interchange = false; // 默认不互换 dx、dyif (dy > dx) // 当斜率大于 1 时，dx、dy 互换{int temp = dx;dx = dy;dy = temp;interchange = true;}int p = 2 * dy - dx;for(int i = 0; i < dx; i++){putpixel(x, y, color);if (p >= 0){if (!interchange) // 当斜率 < 1 时，选取上下象素点y += s2;else // 当斜率 > 1 时，选取左右象素点x += s1;p -= 2 * dx;}if (!interchange)x += s1; // 当斜率 < 1 时，选取 x 为步长elsey += s2; // 当斜率 > 1 时，选取 y 为步长p += 2 * dy;}}// 主函数void main(){initgraph(640, 480);// 测试画线Line_Bresenham(100, 1, 1, 478, RED);Line_Bresenham(1, 478, 638, 1, RED);// 按任意键退出getch();closegraph();}实验结果分析三种算法运算结果比较：像素逼近效果由好到差依次为：B算法、DDA算法、中点算法执行速度由快到慢依次为：中点算法、DDA算法、B算法。

算法原理
选择表示直线的最佳像素的位置，即用 最靠近直线的网格点来代表这一直线。根据 直线的斜率确定或选择变量x或y每次递增一 个单位，另一个变量y或x每次增量为0或1， 这取决于理论直线段与最近像素点的距离。 避免了低效率的取整运算。
y 设直线段的斜率m∈[0,1]（即倾角≦45°）其 中m=≨y/≨x，则要生成的直线的微分方程为： Yi+1,ri yi - 1
Pu（x i＋1，y i）
(d1 0) (d1 0)
（3-17）
P（xi，yi）
M（x i+1，y i-0.5） Pd（x i＋1，yi－1）
x
图3-13 上半部分像素点的选取
上半部分Ⅰ的递推公式
图3-13中，为了能够继续判断椭圆上的每个点，需要给 出中点偏差判别式d1的递推公式和初始值。
A（0，b）
y向分量 法矢量 C( a 2 /
a 2 b2 , b 2 / a 2 b 2
)
x向分量 B（a，0）
椭圆的中点Bresenham算法的原理：在部分Ⅰ：每次在 主位移x方向上走一步，y方向上退不退步取决于中点偏差判别 式的值；在部分Ⅱ：每次在主位移方向y上退一步，x方向上走 不走步取决于中点偏差判别式的值。
Pk(xk,yk) Pu(xk+1,yk)
M
Pb(xk+1,yk-1)
≥0
f(M)= <0
M点在圆外，取Pb
M点在圆内，取Pu
Bresenham生成圆弧算法
A 我们仍讨论第二个1/8圆。设有半径为R圆心在 坐标原点。 AB为第二个1/8圆的圆弧，圆的方程为： R
x2+y2=R2
Pi-1(xi-1,yi-1)是已选中的点，则下一个点应在 Hi(xi,yi-1)和Li(xi,yi-1-1)选取。 设有圆弧S满足： xHi2+yHi2-Rs2+ xLi2+yLi2-Rs2=0 2-18

实验二：直线生成算法班级 13软件+道铁1班学号 20132110050115姓名丁益1.实验目的a)通过实验，进一步理解直线段扫描转换的DDA算法、中点画线自算法及bresenham算法的基本原理，掌握以上算法生成直线段的基本过程。

b)通过编程，掌握在C/C++环境下完成用DDA算法、中点画线算法及bresenham算法对任意直线段的扫描转换，以及在C/C++环境下完成用中点画圆及椭圆的绘制方法。

2.实验内容c)阅读《openGL三维程序设计》（电子书）第二部分第四章，掌握OpenGL基本建模方法，并调试其中程序。

d)参考教材第6章，编程实现整数DDA算法、中点画线法和Bresenham画线法，绘制直线（直线宽度和线型可自定）。

2.1 DDA直线生成2.1.1算法原理已知过端点P0（x0,y0），P1（x1,y1）的直线段L(P0,P1)，斜率为k=(y1-y0)/(x1-x0)，画线过程从x的左端点x0开始，向x右端点步进，步长为1个像素，计算相应的y坐标为y=kx+B。

计算y i+1 = kx i+B=kx i +B+kx=y i +kx当x=1,y i+1=y i+k，即当x每递增1，y递增k。

由计算过程可知，y与k可能为浮点数，需要取y整数，源程序中round(y）=(int)(y+0.5)表示y四舍五入所得的整数值。

2.1.2 算法流程2.1.3 算法实现关键代码#include<GL/glut.h>#include<math.h>void Init(){glClearColor(1.0,1.0,1.0,0.0);glMatrixMode(GL_PROJECTION);gluOrtho2D(0.0,200.0,0.0,150.0);}void lineDDA(int x0,int y0,int xEnd,int yEnd){int dx=xEnd-x0,dy=yEnd-y0,steps,k;float xIncrement, yIncrement, x=x0, y=y0;if(fabs(dx)>fabs(dy))steps=fabs(dx);elsesteps=fabs(dy);xIncrement=float(dx)/float(steps);yIncrement=float(dy)/float(steps);for(k=0;k<steps;k++){x+=xIncrement;y+=yIncrement;glBegin(GL_POINTS);glVertex2i(x,(int)(y+0.5));glEnd();}glFlush();}void myDisplay(void){glClear(GL_COLOR_BUFFER_BIT);glColor3f(1.0,0.0,0.0);lineDDA(50,50,100,120);}int main(int argc,char** argv){glutInit(&argc,argv);glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); glutInitWindowPosition(100,100);glutInitWindowSize(400,400);glutCreateWindow("Hello World");Init();glutDisplayFunc(myDisplay);glutMainLoop();return 0;}2.1.4算法运行示例及中间结果2.2 Brese nham直线生成2.2.1算法原理Bresenham算法的基本原理是：过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。

第 3 章 基本图形元素生成算法
图3.1 中点画线示意图
第 3 章 基本图形元素生成算法
设Q是理想直线与垂直线x=xP+1的交点。 若M 在Q的下方, 则P2离理想直线近, 应取为下一个像素; 否 则应取P1。 为此, 我们构造判别式
d=F(M)=F(xP+1,yP+0.5)=a(xP+1)+b(yP+0.5)+c 当d<0时, M在直线下方, 应取右上方的P2作为下 一个像素; 当d>0时, M在直线上方, 则应取正右方的P1; 当d=0时, 约定取正右方的P1。
根据以上分析, 可得中点画圆法算法如下: void MidPoint -Circle(r, color) int r, clor; { int x, y;
float d; x=0; y=r; d=1.25-r; putpixel(x, y, color); while(x<y)
{ if(d<0) { d+=2*x+3; x++; }
float k, e; dx=x1-x0; dy=y1-y0; k=dy/dx; e=-0.5; x=x0; y=y0;
第 3 章 基本图形元素生成算法
for(i=0; i<=dy; i++) { putpixel(x, y, color); x=x+1; e=e+k; if(e>=0){ y=y+1; e=e-1; } }
第 3 章 基本图形元素生成算法
x++; }
else { e+=(deltax+deltay); deltax+=2; deltay+=2; x++; y--; }

计 算 机 图 形 学
第三章 基本图形元素的生成算法
计 算 机 图 形 学
光栅显示器上显示的图形，称之为光栅图形。光 栅显示器可以看作是一个象素矩阵，在光栅显 示器上显示的任何一个图形，实际上都是一些 像素的集合。由于对一个具体的光栅显示器来 说，象素个数是有限的，象素的颜色和灰度等 级也是有限的，象素是有大小的，所以光栅图 形只是近似的实际图形。如何使光栅图形最完 美地逼近实际图形，便是光栅图形学要研究的 内容。确定最佳逼近图形的像素集合的过程称 为图形的扫描转换或光栅化。
计 算 机 图 形 学
第三章 基本图形元素的生成算法
a)
b)
图3.2 直线的生成
c)
计 算 机 图 形 学
直线的绘制首先要考虑的是绘制的质量。怎样才算高质量？ 当然，看上去要象直线。 ： 1. 画的直线应是直的 2. 线的端点位置应正确 3. 线的浓度应均匀 4. 直线生成的速度要快
第三章 基本图形元素的生成算法
（X1,Y1)的像素点，对应的显示缓冲器地址为： 字节地址= S + ( H / 8 ) * Y1 + ( X1 / 8 ) 的整数部分 字节内的位地址= X1 / 8 的余数 计 算 机 图 形 学
第三章 基本图形元素的生成算法
3.1.2 直线段的生成
数学上的直线是由无数个点构成的集合，显 然，光栅显示器只能近地似显示直线。对 于水平、垂直和45°斜线是可以达到较为 满意的效果的。当我们对直线进行光栅化 时，需要确定最佳逼近该直线的一组象素。 扫描转换直线段就是计算出落在直线段上 或充分靠近它的一串像素，并以此像素近 似代替原连续直线段在屏幕上显示的过程。
第三章 基本图形元素的生成算法
3.1直线的生成算法

OpenGL 实验2直线生成算法实现实验2 直线生成算法实现1. 实验目的理解基本图形元素光栅化的基本原理, 掌握一种基本图形元素光栅化算法, 利用0penGL实现直线光栅化的 DDA算法。

2. 实验内容(1)根据所给的直线光栅化的示范源程序, 在计算机上编译运行, 输出正确结果。

(2)指出示范程序采用的算法, 以此为基础将其改造为中点线算法或 Bresenham算法,写入实验报告。

(3)根据示范代码,将其改造为圆的光栅化算法,写入实验报告。

(4)了解和使用OpenGL的生成直线的命令,来验证程序运行结果。

3. 实验原理示范代码原理DDA算法。

下面介绍 OpenGL画线的一些基础知识和glutReshapeFunc （）函数。

(1)数学上的直线没有宽度,但0penGL的直线则是有宽度的。

同时, OpenGL的直线必须是有限长度,而不是像数学概念那样是无限的。

可以认为, OpenGL的“直线”概念与数学上的“线段”接近,它可以由两个端点来确定。

这里的线由一系列顶点顺次连接而成, 有闭合和不闭合两种。

前面的实验已经知道如何绘“点”,那么 OpenGL是如何知道拿这些顶点来做什么呢? 是依次画出来,还是连成线? 或者构成一个多边形? 或是做其他事情? 为了解决这一问题, OpenGL要求:指定顶点的命令必须包含在 glBegin函数之后, glEnd函数之前(否则指定的顶点将被忽略),并由 glBegin来指明如何使用这些点。

例如:glBegin(GL P0INTS) , glVertex2f(0.0f, 0.0f);glVertex2f(0.5f, 0.0f); glEnd();则这两个点将分别被画出来。

如果将 GL_POINTS替换成 GL_LINES,则两个点将被认为是直线的两个端点, OpenGL将会画出一条直线。

还可以指定更多的顶点, 然后画出更复杂的图形。

另一方面, glBegin支持的方式除了 GL_POINTS和 GL_LINES,还有GL LINE STRIP、 GL LINE L0��P、 GL TRIANGLES、 GL TRIANGLE STRIP、 GL TRIANGLE_FAN等几何图元。

由于只用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; • putpixel(x, y, color); • while (x<x1) • { if (d<0) {x++; y++; d+=d2; } • else {x++; d+=d1;} • putpixel (x, y, color); • } /* while */ • } /* mid PointLine */
P2 Q
P=(xp,yp) P1
∴欲判断 M 点是在 Q 点上方还是在 Q 点下方，只需把 M 代入 F(x,y),并检查它的符号。
中点画线法
构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d<0，M在直线(Q点)下方，取右上 方P2； 当d>0，M在直线(Q点)上方，取右方 P1； 当d=0，选P1或P2均可，约定取P1； 能否采用增量算法呢？
批注本地保存成功开通会员云端永久保存去开通
计算机地图制图
• Turbo C提供了非常丰富的图形函数, 所有 图形函数的原型均在graphics. h中，将集成 开发环境Options/Linker中的Graphics lib选 为on, 只有这样才能保证正确使用图形函数。

实验二直线生成算法实现班级 08信计学号 80姓名分数一、实验目的和要求：1、理解直线生成的基本原理2、掌握几种常见的直线的生成算法3、实现直线生成的算法二、实验内容：1.了解直线的生成原理2．掌握几种基本的直线生成算法：DDA算法、bresenham画线法、中点画线法3.实现直线生成的，在屏幕上任意生成一条直线三、实现程序程序1#define pi 3.141592#define MAX(a,b) (a>b)? a:b#define MIN(a,b) (a<b)? a:b#include "graphics.h"#include "math.h"struct rectangle{int xmin;int xmax;int ymin;int ymax;};struct point{float x;float y;};struct point pot[2];struct rectangle rect={150,490,100,380};int x=0,y=0;void zhongxing(int x,int y,int s){ int i;for(i=x-5;i<=x+5;i++){ putpixel(i,y,s);}for(i=y-5;i<=y+5;i++){ putpixel(x,i,s);}}void add(int x,int y,int i){pot[i].x=x;pot[i].y=y;}int clip(float q,float d,float *t0,float *t1){ float r;if(q<0){ r=d/q;if(r>*t1)return(0);else if(r>*t0){ *t0=r;return(1);}}else if(q>0){ r=d/q;if(r<*t0)return(0);else if(r<*t1){ *t1=r;return(1);}}else if(d<0)return(0);return(1);}void liang(struct point * pot,struct rectangle * rect){ float delatx,delaty,t0,t1;t0=0;t1=1;delatx=pot[1].x-pot[0].x;if(clip(-delatx,pot[0].x-rect->xmin,&t0,&t1))if(clip(delatx,rect->xmax-pot[0].x,&t0,&t1)){ delaty=pot[1].y-pot[0].y;if(clip(-delaty,pot[0].y-rect->ymin,&t0,&t1))if(clip(delaty,rect->ymax-pot[0].y,&t0,&t1)){ line((int)(pot[0].x+t0*delatx),(int)(pot[0].y+t0*delaty), (int)(pot[0].x+t1*delatx),(int)(pot[0].y+t1*delaty)); }}}void main(){int driver=DETECT,mode; int i=0,j,key; registerbgidriver(EGAVGA_driver);initgraph(&driver,&mode,"\\tc"); initgraph(&driver,&mode,"\\tc");zhongxing(x,y,4);setcolor(3);rectangle(150,100,490,380);/**/for(;;){ if(bioskey(1)){ key=bioskey(0);if(key==0x4d00){ zhongxing(x,y,0);x+=5;zhongxing(x,y,4);rectangle(150,100,490,380);}if(key==0x011b){printf("esc be press");break;}if(key==0x4b00){ zhongxing(x,y,0);x-=5;zhongxing(x,y,4);rectangle(150,100,490,380);}if(key==0x5000){zhongxing(x,y,0);y+=5;zhongxing(x,y,4);rectangle(150,100,490,380);}if(key==0x4800){zhongxing(x,y,0);y-=5;zhongxing(x,y,4);rectangle(150,100,490,380);}if(key==0x1c0d){ add(x,y,i);circle(x,y,3);i+=1;}if(key==0x3920){liang(pot,&rect);for(j=0;j<2;j++){ pot[j].x=0;pot[j].y=0;}i=0;}}}getch();closegraph();}程序2（1）DDA算法程序实现的完整源程序#include<stdio.h>#include<graphics.h>#include<math.h>#define YS 100000dda_line(int xa,int ya,int xb,int yb,int c){float delta_x,delta_y,x,y;int dx,dy,steps,k;dx=xb-xa;dy=yb-ya;if(abs(dx)>abs(dy)) /*判断步长的方向*/steps=abs(dx); /*steps作为控制数K<1*/elsesteps=abs(dy); /*steps作为控制数K>1*/delta_x=(float)dy / (float)steps; /*值为±1域±1/m*/ delta_y=(float)dy / (float)steps; /*值为±1域±m*/ x=xa;y=ya;putpixel(x,y,c); /*画起点，c为点的颜色*/for(k=1;k<=steps;k++) /*循坏画点成直线*/{x+=delta_x;y+=delta_y;putpixel(x,y,c);delay(YS);}}main(){int x1=250,y1=250,x2=300,y2=300,c=5;int dx,dy,n,k,i,f;int x,y;int gdriver,gmode;gdriver=DETECT;initgraph(&gdriver,&gmode," ");dda_line(x1,y1,x2,y2,c);getch();closegraph();}（2）改进的Bresenham画线算法程序实现的完整源程序#include<stdio.h>#include<graphics.h>#include<math.h>#define YS 100000bresenham_line(int x0,int y0,int x1,int y1,int c){int x,y,dx,dy,e,i;dx=x1-x0;dy=y1-y0;e=-dx;x=x0,y=y0;for(i=0;i<=dx;i++){putpixel(x,y,c++);/*c++不同描点不同颜色*/delay(YS);x++,e=e+2*dy;if(e>0){y++;e=e-2*dx;}}}main(){int x0=100,y0=100,x1=200,y1=200,c=1;int gdriver,gmode;gdriver=DETECT;initgraph(&gdriver,&gmode," ");bresenham_line(x0,y0,x1,y1,c);getch();closegraph();}（3）中点算法实现的完整源程序#include <stdio.h>#include <stdlib.h>#include <math.h>#include <conio.h>#include <graphics.h>#define rad 0.0174532925#define NUMBER 24/*此程序写出的图形，(0,0)在左上方，即以原y轴的负半轴为正，x轴不变，类似于抛物运动。

直线生成算法的实现1.数字微分法：数字微分法是直线生成算法的一种基本方法，其核心思想是通过对直线的斜率进行离散化处理，从而得到直线上的像素点。

具体步骤如下：步骤1:根据直线的起点和终点坐标，计算直线的斜率k=(y2-y1)/(x2-x1)。

步骤2:根据斜率k的值，判断直线属于四种情况：0<=k<=1、k>1、-1<=k<0、k<-1步骤3:对于不同的斜率范围，采取不同的策略进行像素点的生成。

对于斜率0<=k<=1，直线的横坐标增加1，纵坐标按照斜率增加1，每次增加1后判断纵坐标是否需要增加1对于斜率k>1，直线的纵坐标增加1，横坐标按照1/k增加。

每次增加1后判断横坐标是否需要增加1对于斜率-1<=k<0，直线的横坐标减少1，纵坐标按照斜率减少1，每次减少1后判断纵坐标是否需要减少1对于斜率k<-1，直线的纵坐标减少1，横坐标按照1/，k，减少。

每次减少1后判断横坐标是否需要减少1步骤4:重复步骤3直到直线上所有的像素点都生成完毕。

2. Bresenham算法：Bresenham算法是一种角度固定的画线算法，通过判断像素点与理想直线之间的距离来确定下一个像素点的位置。

具体步骤如下：步骤1:根据直线的起点和终点坐标，计算直线的斜率k=(y2-y1)/(x2-x1)。

步骤2:初始化误差项d=-1/2步骤3:循环直到达到直线的终点。

步骤4:根据斜率k的值，判断直线属于四种情况。

对于0<=k<=1，判断d<k-1/2，如果满足则x坐标加1，否则x、y坐标同时加1对于k>1，判断d<-1/2，如果满足则y坐标加1，否则x、y坐标同时加1对于-1<=k<0，判断d>k+1/2，如果满足则x坐标减1，否则x、y坐标同时加1对于k<-1，判断d>-1/2，如果满足则y坐标减1，否则x、y坐标同时加1步骤5:更新误差项d=d+k。

实验一直线生成算法一、实验目的及要求：1．学习C语言的基本绘图方法；2. 实习直线基本生成算法；3．了解光栅图形显示器的工作原理和特点；4．掌握课本所介绍的图形算法的原理和实现。

5. 基于光栅图形显示器，在c环境中使用基本图形生成算法画根粗细不同的直线。

1.）写出完整的DDA画线算法程序，使其可以画任意直线；2.）写出完整的中点画线算法程序，使其可以画任意直线；3．）写出完整的Breaenham画线程序，使其可以画任意直线；二、理论基础：1、DDA算法：实现的关键是如何步进和步进的方向：步进的正或负，决定能否正确的到达终点。

步进的大小：它控制了变化最大的步进，令其为单位步进，而另一个方向的步进必小于1 ，这样不论斜率|m|≤1否，都会使直线的亮度均匀。

依公式：则下一点坐标为：2、中点画法：假设x坐标为xp的各像素点中，与直线最近者已确定，为（xp,yp)。

那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)或右上方的P2（xp+1,yp+1)两者之一。

再以M表示P1与P2的中点，即M=（xp+1,yp+0.5)。

又设Q是理想直线与垂直线x=xp+1的交点。

若M在Q的下方，则P2离直线近，应取为下一个像素；否则应取P1。

3、Bresenham算法：假设我们需要由 (x0, y0) 这一点，绘画一直线至右下角的另一点(x1, y1)，x,y分别代表其水平及垂直座标。

在此我们使用电脑系统常用的座标系，即x座标值沿x轴向右增长，y座标值沿y轴向下增长。

因此x及y之值分别向右及向下增加，而两点之水平距离为x1 − x0且垂直距离为y1-y0。

由此得之，该线的斜率必定介乎于1至0之间。

而此算法之目的，就是找出在x0与x1之间，第x行相对应的第y列，从而得出一像素点，使得该像素点的位置最接近原本的线。

三、算法设计与分析：1、DDA算法：(1)已知过端点P0 (x0, y0), P1(x1, y1)的直线段L ：y=kx+b(2)直线斜率为 :k=(y1-y0)/(x1-x0)(3)Xi+1=Xi+ε*ΔXYi+1=Yi+ε*ΔY 其中，ε=1/max(|ΔX|,|ΔY|)max(|ΔX|,|ΔY|)= |ΔX| (|k|<=1)|ΔY| (|k|>1)(4)|k|<=1时：Xi+1=Xi+(或-)1Yi+1=Yi+(或-)k|k|>1时：Xi+1=Xi+(或-)1/kYi+1=Yi+(或-)1这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。

实验二 直线的生成算法的实现班级 08信计2班 学号 59 姓名 分数一、实验目的和要求1.理解直线生成的基本原理。

2.掌握几种常用的直线生成算法。

3.利用Visual C++实现直线生成的DDA 算法。

二、实验内容1.了解直线的生成原理，尤其是Bresenham 画线法原理。

2.掌握几种基本的直线生成算法：DDA 画线法、Bresenham 画线法、中点画线法。

3.利用Visual C++实现直线生成的DDA 算法，在屏幕上任意生成一条直线。

三、实验步骤1.直线的生成原理：（1）DDA 画线法也称数值微分法，是一种增量算法。

是一种基于直线的微分方程来生成直线的方法。

（2）中点画线法原理以下均假定所画直线的斜率[0,1]k ∈，如果在x 方向上的增量为1，则y 方向上的增量只能在01之间。

中点画线法的基本原理是：假设在x 坐标为p x 的各像素点中，与直线最近者已经确定为(,)p p P x y ，用小实心圆表示。

那么，下一个与直线最近的像素只能是正右方的1(1,)p p P x y +，或右上方的2(1,1)p p P x y ++，用小空心圆表示。

以M 为1P 和2P 的中点，则M 的坐标为(1,0.5)p p x y ++。

又假设Q 是理想直线与垂直线1p x x =+的交点。

显然，若M 在Q 的下方，则2P 离直线近，应取2P 为下一像素点；若M 在Q 的上方，则1P 离直线近，应取1P 为下一像素点。

（3）B resenham 画线法原理直线的中点Bresenham 算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。

给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为：0b kx y y)F(x,=--= （3-1）构造中点偏差判别式d 。

b x k y y x F y x F d i i i i M M -+-+=++==)1(5.0)5.0,1(),(⎩⎨⎧≥<+=+)0( )0( 11d y d y y i i i(1) 当d<0时b x k y y x F d i i i i i -+-+=++=+)2(5.1)5.1,2(1k d k b x k y i i i -+=-+-+-+=11)1(5.0⑵ 当d ≥0时b x k y y x F d i i i i i -+-+=++=+)2(5.0)5.0,2(1k d k b x k y i i i -=--+-+=)1(5.02.实现前面所述的各种直线生成算法，包括DDA 算法、中点生成算法、Bresenham 生成算法等。

图 3-7 项目的风格、原文件注释和 MFC 库类型
图 3-8 通知 MFC 产生的类名称
3．1．3 输入源程序进行程序设计
应用程序项目工程建立以后，就为应用程序的开发建立了一个框架，这是不输入任何
-- 5
程序代码，对该项目程序进行编译和运行，可以生成一个完整的窗口程序。用户根据项目工 程中的不同类，输入自己设计的程序代码，完成用户的程序设计。
实验 1 Visual C++图形程序设计
一、实验目的
Visual C++是在 Microsoft C 的基础上发展而来的，随着计算机软、硬件技术的快速发展， 如今 Visual C++已成为集编辑、编译、运行、调试于一体功能强大的集成编程环境。本章以 Visual C++ 6.0 为对象，主要介绍 Visual C++集成编成环境的使用、图形设备接口和常用图 形程序设计、鼠标编程以及菜单设计等基础，目的是通过对 Visual C++的学习，掌握 Visual C++图形程序设计的方法，为计算机图形学原理部分的算法实现提供程序工具和方法。
用当前的画刷颜色填充区域
***
FrameRect()
绘制矩形边界
**
FrameRgn()
绘制区域边界
**
GetBKColor()
获取背景颜色
*****
GetCurrentBitmap() 获取所选位图的指针
**
GetCurrentBrush()
获取所选画刷的指针
***
GetCurrentFont()
第一个问题是建立什么类型的应用程序，有三个选项：单个文档（Single document）、 多重文档（Multiple document）和基本对话（Dialog based）。单个文档应用程序主窗口中只 有一个窗口，多重文档可以在主窗口中开多个子窗口，基本对话主窗口是一个对话框。例中 选择单个文档，单击“确定”，进入下一个问题，如图 3-4 所示。

实验 2 直线生成算法实现1. 实验目的理解基本图形元素光栅化的基本原理, 掌握一种基本图形元素光栅化算法, 利用0penGL 实现直线光栅化的DDA 算法。

2. 实验内容(1) 根据所给的直线光栅化的示范源程序, 在计算机上编译运行, 输出正确结果。

(2) 指出示范程序采用的算法, 以此为基础将其改造为中点线算法或Bresenham 算法,写入实验报告。

(3) 根据示范代码,将其改造为圆的光栅化算法,写入实验报告。

(4) 了解和使用OpenGL 的生成直线的命令,来验证程序运行结果。

3. 实验原理示范代码原理DDA 算法。

下面介绍OpenGL 画线的一些基础知识和glutReshapeFunc( ) 函数。

(1)数学上的直线没有宽度,但0penGL 的直线则是有宽度的。

同时, OpenGL 的直线必须是有限长度，而不是像数学概念那样是无限的。

可以认为，OpenGL的“直线”概念与数学上的“线段” 接近,它可以由两个端点来确定。

这里的线由一系列顶点顺次连接而成, 有闭合和不闭合两种。

前面的实验已经知道如何绘“点” ，那么OpenGL 是如何知道拿这些顶点来做什么呢? 是依次画出来，还是连成线? 或者构成一个多边形? 或是做其他事情? 为了解决这一问题， OpenGL 要求:指定顶点的命令必须包含在gIBegin函数之后,glEnd函数之前(否则指定的顶点将被忽略)，并由glBegin 来指明如何使用这些点。

例如:glBegin(GL P0INTS) ，glVertex2f(0.0f， 0.0f);glVertex2f(0.5f， 0.0f);glEnd();则这两个点将分别被画出来。

如果将GL_POINTS替换成GL_LINES则两个点将被认为是直线的两个端点，OpenGL将会画出一条直线。

还可以指定更多的顶点，然后画出更复杂的图形。

另一方面,gIBegin 支持的方式除了GL_POINTS和GL_LINES还有GL LINE STRIP GL LINEL0O P、GL TRIANGLE S GL TRIANGLE STRIP GL TRIANGLE_FA等几何图元。

实验二基本图形（元）生成技术（一）直线生成算法一、实验目的在一个图形系统中，基本图形（也称为图元、图素等）的生成技术是最基本的，任何复杂的图形都是由基本图形组成的，基本图形生成的质量直接影响该图形系统绘图的质量。

所以，需要设计出精确的基本图形生成算法，以确保图形系统绘图的精确性。

本次实验的目的就是验证直线生成的三种扫描算法，并要求对基本算法进行扩充和改进，包括：利用Visual C++实现三种直线生成算法，验证算法的正确性；二、实验任务1．理解三种直线生成算法思想，写出实现程序；2．添加鼠标功能，实现交互式画直线程序；3．将10个像素作为步距单位，编出Bresenham算法的示例。

三、基本知识和实验步骤任务一：实现DDA画线程序实验步骤：1．建立一个DDALine的工程文件；2．添加ddaline()成员函数方法：在工作区中选择CLASSVIEW类窗口，右击CDDAlineView类，选择“add member function…”，定义如下的成员函数：void ddaline(CDC* pDC,int x0,int y0,int x1,int y1,COLORREF color);3．编写自定义的成员函数ddaline()程序void CDDALineView::ddaline(CDC* pDC, int x0, int y0, int x1, int y1, COLORREF color) {int length,i;float x,y,dx,dy;length=abs(x1-x0);if (abs(y1-y0)>length)length=abs(y1-y0);dx=(x1-x0)/length;dy=(y1-y0)/length;x=x0+0.5;y=y0+0.5;for (i=1;i<=length;i++){pDC->SetPixel((int)x,(int)y,color);x=x+dx;y=y+dy;}}4．编写OnDraw()函数void CDDALineView::OnDraw(CDC* pDC){CDDALineDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);// TODO: add draw code for native data hereddaline(pDC,100,100,400,100,RGB(255,0,0));ddaline(pDC,400,100,400,400,RGB(0,255,0));ddaline(pDC,400,400,100,400,RGB(0,0,255));ddaline(pDC,100,400,100,100,RGB(255,255,0));ddaline(pDC,100,100,400,400,RGB(255,0,255));ddaline(pDC,100,400,400,100,RGB(0,255,255));}}5．编译、调试和运行程序，查看程序结果。