改进的Bresenham算法

这里不仔细讲原理，只是把我写的算法发出来，跟大家分享下，如果有错误的话，还请大家告诉我，如果写的不好，也请指出来，一起讨论进步。

算法步骤:

(1) 输入直线的两端点P0 (x0, y0)和P1 (x1, y1)。

(2) 计算初始值dx, dy, e = -dx, x = x0, y = y0。

(3) 绘制点 (x, y)。

(4) e更新为e+2 * dy。判断e的符号，若e > 0, 则(x, y)更新为(x+1, y+1)， 同时将e更新为e-2*dx；否则(x, y)更新为(x+1, y)。

(5) 当直线没有画完时，重复步骤(3)和(4)否则结束。

水平、垂直和|k| = 1的直线可以直接装入帧缓冲存储器面无须进行画线算法处理。下面是我的算法，如有错误请指出。

#include <GL/freeglut.h>
void init (void)
{
glClearColor (0.0f, 0.0f, 0.0f, 1.0f);
}void drawLine (int x1, int y1, int x2, int y2)
{
int x, y, dx, dy, e;
// k does not exist
if (x1 == x2)
{
if (y1 < y2)
{
y = y1;
glBegin (GL_POINTS);
while (y <= y2)
{
glVertex2i (x1, y);
++ y;
}
glEnd ();
} // if (y1 < y2)
else
{
y = y2;
glBegin (GL_POINTS);
while (y <= y1)
{
glVertex2i (x1, y);
++ y;
}
glEnd ();
}
} // if (x1 == x2)
else if (y1 == y2) // k = 0
{
if (x1 < x2)
{
x = x1;
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y1);
++ x;
}
glEnd ();
} // if (x1 < x2)
else
{
x = x2;
glBegin (GL_POINTS);
while (x <= x1)
{
glVertex2i (x, y1);
++ x;
}
glEnd ();
}
}
else
{
if (x1 > x2)
{
int temp = x1;
x1 = x2;
x2 = temp;
temp = y1;
y1 = y2;
y2 = temp;
}
x = x1;
y = y1;
dx = x2 - x1;
dy = y2 - y1;
// k = 1
if (dx == dy)
{
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
++ x;
++ y;
}
glEnd ();
}
else if (dx == -dy) // k = -1
{
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
++ x;
-- y;
}
glEnd ();
}
else if (dy > dx)// k > 1
{
glBegin (GL_POINTS);
dx <<= 1;
e = - dy;
dy <<= 1;
y = y1 > y2 ? y2 : y1;
int maxY = y1 > y2 ? y1 : y2;
while (y <= maxY)
{
glVertex2i (x, y);
++ y;
e += dx;
if (e > 0)
{
++ x;
e -= dy;
}
}
glEnd ();
}
else if (dy > 0)// 0 < k < 1
{
e = -dx;
dx <<= 1;
dy <<= 1;
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
++ x;
e += dy;
if (e > 0)
{
e -= dx;
++ y;
}}
glEnd ();
}
else if (-dy < dx)// 0 > k > -1
{
e = -dx;
dx <<= 1;
dy <<= 1;
glBegin (GL_POINTS);
while (x <= x2)
{
glVertex2i (x, y);
++ x;
e += dy;
if (e < 0)
{
-- y;
e += dx;
}
}
glEnd ();
}
else if (-dy > dx) // k < -1
{
e = dy;
dx <<= 1;
dy <<= 1;
glBegin (GL_POINTS);
y = y1 > y2 ? y1 : y2;
int minY = y1 > y2 ? y2 : y1;
while (y >= minY)
{
glVertex2i (x, y);
-- y;
e += dx;
if (e > 0)
{
++ x;
e += dy;
}
}
glEnd ();
}
}
}void display (void)
{
glClear (GL_COLOR_BUFFER_BIT);
glColor3f (1.0f, 0.0f, 0.0f);
// Vertical line
drawLine (0, -200, 0, 200);
// Horizontal line
drawLine (-200, 0, 200, 0);
// k = 1 line
drawLine (-200, -200, 200, 200);
// k = -1 line
drawLine (-200, 200, 200, -200);
// k = 1/2 line
drawLine (200, 100, -200, -100);
// k = 2 line
drawLine (-100, -200, 100, 200);
// k = -1/2 line
drawLine (-200, 100, 200, -100);
// k = -2 line
drawLine (-100, 200, 100, -200);drawLine (30, 120, 10, 70);drawLine (10, 70, 30, 10);drawLine (30, 10, 60, 50);drawLine (60, 50, 80, 10);drawLine (80, 10, 120, 80);drawLine (120, 80, 70, 80);drawLine (70, 80, 30, 120);glutSwapBuffers ();
}void reshape (int w, int h)
{
glViewport (0, 0, (GLsizei) w, (GLsizei) h);
glMatrixMode (GL_PROJECTION);
glLoadIdentity ();
if (w <= h)
{
gluOrtho2D (-600.0, 600.0, -600.0 * (GLfloat) h / (GLfloat) w, 600.0 * (GLfloat) h / (GLfloat) w);
}
else
{
gluOrtho2D (-600.0 * (GLfloat) w / (GLfloat) h,600.0 * (GLfloat) w / (GLfloat) h, -600.0, 600.0);
}
glMatrixMode (GL_MODELVIEW);
glLoadIdentity ();
}
void keyboard (unsigned char key, int x, int y)
{
switch (key)
{
case 27: // 'VK_ESCAPE'
exit (0);
break;
default:
break;
}
}
int main (int argc, char ** argv)
{
glutInit (&argc, argv);
glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGB);
glutInitWindowSize (600, 600);
glutCreateWindow ("optimized Bresenham line");
init ();
glutReshapeFunc (reshape);
glutDisplayFunc (display);
glutKeyboardFunc (keyboard);
glutMainLoop ();
return 0;
}