写出直线段扫描转换的Bresenham算法，并生成从点P1（0,0）到点P2 (5,2)的直线段，要求写出每一步递推过程
发布网友
发布时间：2022-05-24 21:00
共1个回答
热心网友
时间：2023-11-01 23:10
没分？····不过既然我有现成的那就给你吧，不过复制粘贴而已！
Bresenham算法是Bresenham提出的一种光栅线生成算法！DDA算法表面上看起来很有效，并且代码也比较容易实现，但是显示每个像素都需要进行一次浮点数加法运算，而Bresenham算法的最大优点是不需要进行浮点数运算！这是一种精确而有效的光栅线生成算法，该算法仅使用增量整数计算，计算速度比DDA要快，另外，Bresenham算法还可用于显示圆和其他曲线，这里暂时只显示直线！
与DDA一样，我们假设线段的两个端点坐标是整数值（x0,y0）（xEnd,yEnd）,且斜率m满足0<=m>=1! 坐标轴的垂直轴表示扫描线位置，水平轴标识像素列，假设以单位x间隔取样，需要确定下一个每次取样时两个可能的像素位置中的哪一个更接近于线路径！
从给定线段的左端点（x0,y0）开始,逐步处理每个后继列（x位置），并在其扫描线y值最接近线段的像素处描出一点，假如已经确定要显示的像素在（xk,yk），那么下一步就要确定在列xk+1=xk+1上绘制哪个像素，是在位置(xk+1,yk)还是在(xk+1,yk+1)
在取样位置xk+1，我们使用dlower和pper来标识两个像素与数学上线路径的垂直偏移，在像素列xk+1处的直线上的y坐标根据直线方程可计算得：
y=m(xk+1)+b
那么可求得：
dlower=y-yk=m(xk+1)+b-yk
pper=( yk+1)-y= yk+1-m(xk+1)-b
令斜率m=dy/dx,引入决策参数Pk，定义为：
Pk=dx(dlower- pper)
=2dx*xk-2dy*yk+c
C是一个常数，值为2dx+dx(2b-1)
由此可以计算得到
pk+1= Pk +2dy-2dx(yk+1-yk)
其中yk+1-yk取0还是取1取决于参数Pk的符号，Pk为负时取0，Pk非负时取1！
而Pk为负时，下一个要绘制的点就是（xk+1,yk）且pk+1= Pk +2dy
Pk为非负时则下一个要绘制的点就是（xk+1,yk+1）且pk+1= Pk +2dy-2dx
至此，Bresenham算法介绍完毕，以下为某个示例：
#include <gl/glut.h>
#include <math.h>
#include <stdio.h>
void draw_pixel(int ix,int iy)
{
glBegin(GL_POINTS);
glVertex2i(ix,iy);
glEnd();
}
void Bresenham(int x1,int y1,int xEnd,int yEnd)
{
int dx=abs(xEnd-x1),dy=abs(yEnd-y1);
int p=2*dy-dx;
int twoDy=2*dy,twoDyMinusDx=2*dy-2*dx;
int x,y;
if (x1>xEnd)
{
x=xEnd;y=yEnd;
xEnd=x1;
}
else
{
x=x1;
y=y1;
}
draw_pixel(x,y);
while(x<xEnd)
{
x++;
if(p<0)
p+=twoDy;
else
{
y++;
p+=twoDyMinusDx;
draw_pixel(x,y);
}
}
}
void display()
{
glClear(GL_COLOR_BUFFER_BIT);
Bresenham(0,0,400,400);//这是我的线段两端点的坐标，你可以换成Bresenham(0,0,5,2),
//不过估计很短，看不清
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);
}
void main(int argc,char **argv )
{
glutInit(&argc,argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowSize(500,500);
glutInitWindowPosition(200.0,200.0);
glutCreateWindow("CG_test_Bresenham_Line example");
glutDisplayFunc(display);
myinit();
glutMainLoop();
}
程序运行效果如图：
