OpenGL中Bresenham直线算法及其决策参数

简单版本

教材P17简单版本的Bresenham直线算法的C++代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
/*简单版本的Bresenham算法核心代码*/
void bresenhamLineOriginal(int x0, int y0, int x1, int y1)
{
int x = x0, dx = (x1 - x0);
int y = y0, dy = (y1 - y0);
for (float k = (float)dy / dx, e = -0.5; x < x1; ++x)
{
glVertex2i(x, y);
e = e + k;
if (e >= 0) { ++y; --e; }
}
}

测试数据及效果图如下:

简单版本的Bresenham直线算法效果图

推广算法

从上图及其测试数据可以看出, 简单形式的Bresenham直线算法仅支持斜率区间为[0,1]的直线, 而且还有x0 <= x2这样一个隐含条件.
如何推广到任意直线, 下面简单说一下:

  • 去掉x0 <= x2隐含条件, 只需要将横坐标的原步长1加上x1-x0的符号即可;
  • 把斜率区间[0,1]推广到[-1,1] 只需要将纵坐标的原步长1加上y1-y0的符号即可;
  • 把斜率区间从[-1,1]推广到任意, 只需要在斜率绝对值大于1时变换横纵坐标轴即可.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<GL\GLUT.H>

/*求绝对值*/
inline int abs(int a) { return (a < 0 ? -a : a); }

/*取符号, 正为1, 负为-1, 零为0*/
inline int sign(int a) { return ((a > 0) ? 1 : (a < 0 ? -1 : 0)); }

/*交换数值*/
inline void swap(int &a, int &b) { int temp = a; a = b; b = temp; }

/*Bresenham画线, 起点为(x0,y0), 终点为(x1,y1)*/
void BresenhamLine(int x0, int y0, int x1, int y1)
{
enum { X, Y, XY };//枚举0, 1, 2, 提高可读性

/*XY坐标距离distance, 用于更新决策参数dp*/
int d[XY] = { abs(x1 - x0),abs(y1 - y0) };

/*XY坐标差符号sign, 用于更新坐标光标cur*/
int s[XY] = { sign(x1 - x0),sign(y1 - y0) };

/*考虑是否变换坐标轴, 以处理斜率绝对值大于1的直线*/
bool flag = (d[X] < d[Y]);//斜率绝对值大于1则需要变换
if (flag) swap(d[X], d[Y]);//需要变换则交换XY轴坐标距离

int cur[XY] = { x0,y0 };//cursor, 坐标光标, 初始化为起点
int dp = 2 * d[Y] - d[X];//decision parameter, 决策参数
for (int i = 0; i <= d[X]; ++i)//光标遍历, 逐个画点
{
glVertex2i(cur[X], cur[Y]);
if (dp >= 0)//判断决策参数
{
cur[!flag] += s[!flag];//更新纵坐标(若未变换)
dp -= 2 * d[X];//修正决策参数
}
cur[flag] += s[flag];//更新横坐标(若未变换)
dp += 2 * d[Y];//更新决策参数
}
}

void display()
{
glClearColor(1.0, 1.0, 1.0, 0.0);//白色背景
glClear(GL_COLOR_BUFFER_BIT);//填充背景色
glColor3f(0.0, 1.0, 1.0);//蓝绿色笔画
glPointSize(5.0f);//笔画粗细5
glBegin(GL_POINTS);//开始绘制

BresenhamLine(64, 128, 64, 128);//点

BresenhamLine(000, 000, 000, 500);//k不存在
BresenhamLine(250, 000, 250, 500);//k不存在
BresenhamLine(500, 000, 500, 500);//k不存在
BresenhamLine(000, 000, 500, 000);//k=0
BresenhamLine(000, 250, 500, 250);//k=0
BresenhamLine(000, 500, 500, 500);//k=0
BresenhamLine(000, 000, 500, 250);//k=0.5
BresenhamLine(000, 250, 500, 500);//k=0.5
BresenhamLine(000, 000, 500, 500);//k=1
BresenhamLine(000, 250, 500, 000);//k=-0.5
BresenhamLine(000, 500, 500, 250);//k=-0.5
BresenhamLine(000, 500, 500, 000);//k=-1

glEnd();//结束绘制
glFlush();
}

int main(int argc, char **argv)
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowPosition(200, 200);
glutInitWindowSize(500, 500);
glutCreateWindow(argv[0]);
glutDisplayFunc(display);
gluOrtho2D(0.0, 500.0, 0.0, 500.0);
glutMainLoop();
return 0;
}

测试数据及效果图如下:

推广后的Bresenham直线算法效果图

决策参数

但是从简单到复杂的过程中还有一个变化是我不太理解的, 那就是决策参数dp(也就是原代码中的e). 初始值从-0.5改为2 * d[Y] - d[X], 步长从斜率k改为2 * d[Y], 大于零时的修正值从-1改为2 * d[X]. 这是为什么呢.


以下是解答部分:

opengl - Bresenham line algorithm - where does the decision parameter come from? - Stack Overflow

以下是原答案的个人翻译:

Bresenham算法只进行整数运算. 主要思想在于尽量减少直线方程增量估值的计算.
该算法非常简单. 我们从直线方程入手:
f(x) = y = a*x +b
(目前假设0 <= a < 1). 当我们向右移一个像素时, 我们得到:
f(x+1) = a * (x+1) + b = f(x) + a
但是对于一般的直线来讲, ay都不会是整数. 所以我们不妨引入一个"误差". 我们一直沿x轴向右移动. 在这个过程中, 我们初始化误差ea并以a步进, 用于决定每右移一个像素后, 是否要上移一个像素. 如果我们的误差高于0.5个像素(条件), 那就沿y轴上移一个像素, 此后再将误差值减小1个像素(修正值). 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
float e=a;
float y=y1;
int x=x1;
while(x<=x2) {
SetPixel(x,y);
x++;
if (e > 0.5) {
y++;
e=e+a-1;
}
else {
e=e+a;
}
}

(请注意, 我们将误差e初始化为a而不是0, 因为我们在绘制像素之后才做出决定, 并且在绘制第一个像素之前并不需要检验e > 0.5这一条件, 因为起点总是恰好在直线上.)
现在, 我们已经更进一步了. 但仍有两点有悖于整数运算: 0.5, 还有a(也就是dy/dx). 但是: 我们能够以任意比例缩放误差的步长(还有条件), 且并不会影响结果. 想想看: 目前为止我们以1像素为单位修正误差(因为起初这很直观), 但是这个算法可以使用任意值来修正误差——半个像素, 两个像素, π个像素.
因此, 我们只需将初始值及步长a缩放为2*dy, 条件0.5缩放为dx, 修正值1缩放为2*dx即可摆脱上面的两个分数! (从某种意义上说, 此处的关键在于我们使用的不是算法中的常数, 而是直线的导出函数). 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int e=2*dy;
int y=y1;
int x=x1;
while(x<=x2) {
SetPixel(x,y);
x++;
if (e > dx) {
y++;
e=e+2*dy - 2*dx;
}
else {
e=e+2*dy;
}
}

现在, 我们的目的达成了: 只有整数参与运算. (这里需要注意的一点是: 从float改用int的同时, 直线的端点自动折合成了整数坐标----整数端点是Bresenham算法的先决条件, 同时也是其局限性).
此外, 还有一个缺陷: 条件含有变量. 如果以一个常量作为条件进行对比, 计算会更加高效, 而最理想的条件是常量0, 因为依赖符号/零标志的判断分支节省了比较操作. 我们可以通过改变误差的修正值来实现这一点. 同理, 不仅修正值的缩放比例可以任意选择, 误差的初始值也可以. 下面我们来看看如何修改初始值以使条件变为常量0:
我们的条件目前是e > dx, 因此将误差初始值偏移-dx将使我们能够对0进行比较(现在0表示dx之前的含义, 即0.5像素). 这个偏移只会影响e的初始值和条件, 并且条件中所有的步长都和以前一样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int e=2*dy-dx;
int y=y1;
int x=x1;
while(x<=x2) {
SetPixel(x,y);
x++;
if (e > 0) {
y++;
e=e+2*dy - 2*dx;
}
else {
e=e+2*dy;
}
}

看, 2*dy-dx这样出现了 ;)


参考

测试数据参考: https://blog.csdn.net/demonliuhui/article/details/52985949

推广算法参考: Generalized Bresenham's Line Drawing Algorithm using OpenGL