计算机图形学直线段生成绘制的实现算法
- 格式：pdf
- 大小：132.79 KB
- 文档页数：6
计算机图形学直线段⽣成绘制的实现算法
实验⼆直线段⽣成绘制的实现算法
班级 10信计专接本学号 20100504008 姓名吴晓楠分数
⼀、实验⽬的和要求：1.了解计算机图形学的原理、⽅法和应⽤。
2.熟悉直线的⽣成算法，掌握直线的绘制
3.实现C语⾔编写图形程序。学会了解VC++的基本应⽤同时了解TC图形
环境配置，学习简单的图形画法，并⽐较画法的优劣，尝试在计算机实
现，得到图形，验证⽐较图形。
⼆、实验内容：1、掌握直线段的⽣成算法，并⽤C/WIN-TC/VC++实现算法，包括中点法⽣成
直线，微分数值法⽣成直线段等。2、编程实现DDA算法、Bresenham算法、中点画线法绘制直线段
三、实验结果分析1、⽣成直线的DDA算法
算法思想：⼀个坐标轴上以单位间隔增量，决定另⼀个坐标轴上最靠近线段路径的对应整数值。假定x2﹣x1的绝对值⼤于y2﹣y1的绝对值，取x为⼀个象素单位长，即x 每次递增⼀个象素，然后利⽤下式计算相应的y值：yk+1﹦yk﹢△y﹦yk﹢m·△x 对于|m|＞1的线段，可通过计算由Y⽅向的增量△y引起的改变来⽣成直线：xk+1﹦xk﹢△x﹦xk﹢m·△y
⽣成直线的DDA算法思想是源⽤初中直线的⽅程得出来的，⽽⽣成直线的中点算法是通过将DDA算法的⽅程式改为隐函数形式，然后通过与中点的⽐较确定该取的像素，绘制图线。/* DDA */
#include
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;
}
}main()
{
int a,b,c,d,e;
int graphdriver=DETECT;
int graphmode=0;
initgraph(&graphdriver,&graphmode,""); cleardevice();
a=0;
b=100;
c=200;
d=300;
e=200;
linedda(a,b,c,d,e);
getch();
closegraph();
}运⾏结果：
VC++环境：
#include
#include
// 四舍五⼊
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, 100, 100, 478, RED);
// 按任意键退出
getch();}
2、Bresenham直线算法是⽤来描绘由两点所决定的直线的算法，它会算出⼀条线段在 n 维光栅上最接近的点。这个算法只会⽤到较为快速的整数加法、减法和位元移位，常⽤于绘制电脑画⾯中的直线。是计算机图形学中最先发展出来的算法。Bresenham画法与中点法相似，都是通过每列象素中确定与理想直线最近的像素来进⾏直线的扫描的转换的。通过各⾏、各列的象素中⼼构造⼀组虚拟⽹格线的交点，然后确定该列象素中与此交点最近的像素。该算法的巧妙之处在于可以采⽤增量计算，使得对于每⼀列，只需要检查⼀个误差项的符号，就可以确定该列的所有对象。
根据直线的斜率确定选择变量在X⽅向上或在Y⽅向上每次递增⼀个单位，另⼀变量的增量为0或1，它取决于实际直线与最近⽹格点位置的距离，这⼀距离称为误差。设第k步的误差为ek，选取上⾯象素点后的积累误差为：ek+1﹦ek﹢（m﹣1）选取下⾯的象素点后的积累误差为：ek+1﹦ek﹢m/* Bresenham */程序代码如下：
#include
#include
// 使⽤ 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 为步长else
y += s2; // 当斜率 > 1 时，选取 y 为步长p += 2 * dy;
}
}
// 主函数
void main()
{
initgraph(640, 480);
// 测试画线
Line_Bresenham(10, 100, 100, 478,BLUE);
Line_Bresenham(10, 478, 638, 1, RED);
// 按任意键退出
getch();
}运⾏结果如下：
3、⽣成直线的中点算法算法思想：
中点算法主要是利⽤椭圆的正负划分性，利⽤已知或以求出的点，根据递推关系来判断下⼀个点的位置。
中点算法有效地消除了DDA浮点运算效率低下的问题，将直线的斜率m转化为可加的数，然后通过中点来确定要选择的点，这样使得中点算法的效率⼤⼤提⾼，使之成为被图形软件⼴泛采⽤的算法之⼀。
代码如下：#include
#include
// 使⽤中点算法画任意斜率的直线（包括起始点，不包括终⽌点）
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;
else
d += 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;
else
x += cx, d += d2;
y += cy;
putpixel(x, y, color);
}
}
}
// 主函数
void main()
{
initgraph(640, 480);
// 测试画线
Line_Midpoint(100, 50, 100, 478, GREEN);
Line_Midpoint(1, 478, 638, 1, BLUE);
// 按任意键退出
getch();}
结果分析：1、该程序实现了三种算法的直线段绘制
2、⽐较三种算法的结果：
像素逼近效果由好到差依次为：Bresenham算法、DDA算法、中点算法执⾏速度由快到慢依次为：中点算法、DDA算法、Bresenham算法
