LIOLOG

liolok's logs

0%

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 直线算法仅支持斜率区间为 [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); // 笔画粗细
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;
}

测试数据及效果图如下:

推广后的算法效果图

决策参数

但是从简单到复杂的过程中还有一个变化是我不太理解的,那就是决策参数 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 轴向右移动,在这个过程中,我们将误差 e 初始化为 a 并以 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)。但是——我们能够以任意比例缩放误差的步长(还有条件),且并不会影响结果。想想看:目前为止我们以一个像素为单位修正误差(因为起初这很直观),但是这个算法可以使用任意值来修正误差——半个像素、两个像素、π 个像素。

因此,我们只需将初始值及步长 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,因为依赖符号/零标志的判断分支节省了比较操作。我们可以通过改变误差的修正值来实现这一点。同理,不仅修正值的缩放比例可以任意选择,误差的初始值也可以。

我们的判断条件目前是 e > dx,因此将误差初始值偏移 -dx 将使我们能够对 0 进行比较(现在 0 表示 dx 之前的含义,即半个像素)。这个偏移只会影响 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