【计算机图形学】基于OpenGL的中点Bresenham算法画直线

2023-04-05

else dx down

学习过三种画直线的方法（DDA、中点Bresenham算法、改进的中点Bresenham算法）后，想着实际操作一下如何能够实现，OpenGL无疑是很好的选择，在老师的推荐下，我尝试着用OpenGL来实现中点Bresenham算法画直线，最后也基本实现了这个功能。如果有不正确或者能更好改进的地方欢迎各

学习过三种画直线的方法（DDA、中点Bresenham算法、改进的中点Bresenham算法）后，想着实际操作一下如何能够实现，OpenGL无疑是很好的选择，在老师的推荐下，我尝试着用OpenGL来实现中点Bresenham算法画直线，最后也基本实现了这个功能。

如果有不正确或者能更好改进的地方欢迎各位大神留言或私信指教。

基本原理：每次在最大位移方向上走一步，而另一个方向是走步还是不走步取决于误差项的判别。（|k|<1时x是最大位移方向，|k|>1时y是最大位移方向）

推导过程：

举0<k<1的例子：首先要写出直线的一般方程，根据基本原理，在最大位移方向上走一步时，另一个方向是否走步取决于误差项（di）的判断。

M点是网格的中点，误差项从图中可以看出，当M点在直线下方时，也就是di<0时，直线靠近上面的B点；当M点在直线上方时，也就是di>0时，直线靠近下面的A点。从而我们可以得到： $x_{i+1}=x_{i}+1; y_{i+1}=\begin{Bmatrix} y_{i}+1 &, &d_{i}<0 \\ y_{i} &, & d_{i}>=0 \end{Bmatrix}$ 这样就画好了一个点。

进行误差项的递推我们可以得到： $d_{i+1}=\begin{Bmatrix} d_{i}+1-k &, &d_{i}<0 \\ d_{i}-k &, & d_{i}>=0 \end{Bmatrix}$ 。

对于di的初始值

做完这些我们就可以得到该算法的步骤是：

1.输入直线的两端点P0(x0,y0)和Pn(xn,yn)；

2.计算初始值△x、△y、d0=0.5-k、x=x0、y=y0；

3.绘制点(x,y)。判断d的符号；

若d<0，则(x,y)更新为(x+1,y+1)，d更新为 d+1-k；

否则(x,y)更新为(x+1,y)，d更新为 d-k。

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

由于式子中包含小数影响速度，所以我们对此进行改进：用2d∆x代替d，这样我们就能得到完整的中点Bresenham算法画直线的步骤啦！

改进之后若d<0，则(x,y)更新为(x+1,y+1)，d更新为d+2∆x-2∆y；

否则(x,y)更新为(x+1,y)，d更新为d-2∆y。

以上只是0<k<1时的情况，还有三种情况请读者自己推导加深印象。

本人的开发环境是VS2022+OpenGL+C#

代码演示：


void MidBresenhamLine(float x0, float y0, float x1, float y1)
{
float dx, dy, d, up, down, x, y, k;
if (x0 > x1)
{
x = x1;
x1 = x0;
x0 = x;
y = y1;
y1 = y0;
y0 = y;
}
x = x0;
y = y0;
dx = x1 - x0;
dy = y1 - y0;
k = dy / dx;//斜率  
putpixel(x, y);
if (k <= 1 && k > 0)//斜率小于等于1且大于等于0的情况
{
//用2*dx*d代替d
d = dx - 2 * dy;
up = 2 * dx - 2 * dy;
down = -2 * dy;
while (x <= x1)
{
x++;//x为最大位移方向
if (d < 0)
{
y++;
d += up;
}
else
{
d += down;
}
putpixel(x, y);
}
 
}
else if (k > 1)//斜率大于1的情况
{
d = 2 * dx - dy;
up = 2 * dx;
down = 2 * dx - 2 * dy;
while (x <= x1)
{
y++;//y是最大位移方向
if (d < 0)
{
d += up;
}
else
{
x++;
d += down;
}
putpixel(x, y);
}
}
else if (k < -1)//斜率小于等于-1的情况
{
d = -2 * dx - dy;
up = -2 * dx - 2 * dy;
down = -2 * dx;
while (x <= x1)
{
y--;//y是最大位移方向
if (d < 0)
{
x++;
d += up;
}
else
{
d += down;
}
putpixel(x, y);
}
}
else if (k <= 0 && k >= -1)//斜率小于0且斜率大于-1的情况
{
d = -dx - 2 * dy;
up = -2 * dy;
down = -2 * dx - 2 * dy;
while (x <= x1)
{
x++;//x为最大位移方向
if (d < 0)
{
d += up;
}
else
{
y--;
d += down;
}
putpixel(x, y);
}
}
}

中点Bresenham算法的优点是：

不用计算直线的斜率，不做除法；
不考虑浮点数，只考虑整数；
只做整数加减法和乘2运算，乘2运算可以用硬件移位实现；
算法速度快并适用于硬件实现。

缺点在我看来就是精度不如DDA

完整代码示例：


#include<stdio.h>
#include<math.h>
#include<GL/glut.h>
 
void init()
{
glClearColor(1.0, 1.0, 1.0, 1.0);//表示清除颜色设为白色
glMatrixMode(GL_PROJECTION);//操作投影矩阵
gluOrtho2D(0.0, 30.0, 0.0, 30.0);//正射投影（二维图像投影到二维平面上），左下角x为0，左上角x为30，右下角y为0，右上角y为30
}
void putpixel(float x, float y)//画点
{
glColor3f(0.0, 0.0, 1.0);//画的点的颜色：蓝色
glPointSize(5.0f);//设置点的大小
glBegin(GL_POINTS);//表示单个顶点
glVertex2i(60+x, 80+y);//定义顶点，2代表二维有代表参数列表参数的个数，f代表浮点型
glEnd();//与glBegin搭配使用
glFlush();//强制刷新
}
void MidBresenhamLine(float x0, float y0, float x1, float y1)
{
float dx, dy, d, up, down, x, y, k;
if (x0 > x1)
{
x = x1;
x1 = x0;
x0 = x;
y = y1;
y1 = y0;
y0 = y;
}
x = x0;
y = y0;
dx = x1 - x0;
dy = y1 - y0;
k = dy / dx;//斜率  
putpixel(x, y);
if (k <= 1 && k > 0)//斜率小于等于1且大于等于0的情况
{
//用2*dx*d代替d
d = dx - 2 * dy;
up = 2 * dx - 2 * dy;
down = -2 * dy;
while (x <= x1)
{
x++;//x为最大位移方向
if (d < 0)
{
y++;
d += up;
}
else
{
d += down;
}
putpixel(x, y);
}
 
}
else if (k > 1)//斜率大于1的情况
{
d = 2 * dx - dy;
up = 2 * dx;
down = 2 * dx - 2 * dy;
while (x <= x1)
{
y++;//y是最大位移方向
if (d < 0)
{
d += up;
}
else
{
x++;
d += down;
}
putpixel(x, y);
}
}
else if (k < -1)//斜率小于等于-1的情况
{
d = -2 * dx - dy;
up = -2 * dx - 2 * dy;
down = -2 * dx;
while (x <= x1)
{
y--;//y是最大位移方向
if (d < 0)
{
x++;
d += up;
}
else
{
d += down;
}
putpixel(x, y);
}
}
else if (k <= 0 && k >= -1)//斜率小于0且斜率大于-1的情况
{
d = -dx - 2 * dy;
up = -2 * dy;
down = -2 * dx - 2 * dy;
while (x <= x1)
{
x++;//x为最大位移方向
if (d < 0)
{
d += up;
}
else
{
y--;
d += down;
}
putpixel(x, y);
}
}
}
 
void ChangeSize(GLsizei w, GLsizei h) {
if (h == 0)
h = 1;
glViewport(0, 0, w, h);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
if (w <= h)
glOrtho(0.0f, 250.0f, 0.0f, 250.0f * h / w, 1.0, -1.0);
else
glOrtho(0.0f, 250.0f * w / h, 0.0f, 250.0f, 1.0, -1.0);
}
void display()
{
glClear(GL_COLOR_BUFFER_BIT);
MidBresenhamLine(0, 0, 120, 80);//在此处修改点的位置
}
int main(int argc, char** argv)
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowSize(400, 400);//画图窗口大小
glutInitWindowPosition(0, 0);//在显示屏上的位置：（0，0）代表左上角
glutCreateWindow("中点bresenham算法画直线");//窗口名称
glutDisplayFunc(display);//调用display函数绘制窗口
init();
glutReshapeFunc(ChangeSize);
glutMainLoop();
return 0;
}