【计算机图形学】三种直线扫描算法,孰优孰劣

绘制线宽为一个像素的直线的三个常用算法:数值微分 (DDA) 发,中点画线法,Bresenham 算法,孰优孰劣?

本文使用glut

前言

在数学中,直线是没有宽度的,是由无数个点构成的集合,但是在显示器上,一切图像都是由像素构成的,都被光栅化了

光栅化用 Adobe 的话来说就是栅格化,没错,就是把矢量图形转化成像素点的过程,这个在 Photoshop 中经常用到

而直线也不例外,同样是由像素构成,像素始终是有宽度的,除非没有角度,否则永远不可能做到真正的直,我们能做的就是使其无限逼近

数值微分法(DDA)

P0(x0,y0)P_0(x_0,y_0)P1(x1,y1)P_1(x_1,y_1) 的直线,算出斜率 k=dydxk=\frac{dy}{dx}

从左端开始,向右端步进,步长为 1,xi+1=xi+1x_{i+1}=x_i+1yi+1=yi+ky_{i+1}=y_i+k,当然,可没有小数坐标的像素点,我们需要取整,形成新的坐标 (xi+1,int(yi+k))(x_i+1,int(y_i+k)),绘制该点,直到 xi=x1x_i=x_1

步进其实就是一步一步走,这里每步是一个像素点

一般来说,y 取整的时候会加 0.5,因为强制类型转换来取整并不是四舍五入,而是直接把小数舍了,这样误差会很大。加 0.5 就很好的利用了取整规则,也用不着引入 math 头文件,很巧妙,如果是负数,减 0.5 即可

我们需要考虑三种情况

  • kk 不存在,也就是 dx=0dx=0 的情况,先比较一下两点的高低,从低点往上绘制,把中间的绘制出来就行
  • k1|k|\leq1,这也是最常见的情况,我们使用 xx 来步进,(x+1,y+k)(x+1,y+k)
  • k>1|k|>1,使用 yy 来步近,(x+1k,y+1)(x+{1\over k},y+1),可能你会问为什么同样使用 xx 来步进。如果继续使用 xx 来步进,k|k| 已经超过 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
void DDALine(int x0, int y0, int x1, int y1)
{
float dx = x1 - x0;
float dy = y1 - y0;
if (dx)
{
float x = 0.0;
float y = 0.0;
float k = dy / dx;
if (k <= 1 && k >= -1) // |k| < 1
{
y = y0;
for (x = x0; x <= x1; x++)
{
glVertex2i(x, int(y + 0.5));
y += k;
}
} else // |k| > 1
{
k = 1 / k;
if (y0 < y1) // k > 1
{
x = x0;
for (y = y0; y <= y1; y++)
{
glVertex2i(int(x + 0.5), y);
x += k;
}
}
else // k < -1
{
x = x1;
for (y = y1; y <= y0; y++)
{
glVertex2i(int(x + 0.5), y);
x += k;
}
}
}
}
else // k 不存在
{
int x = x0;
int y = 0;
y = (y0 <= y1) ? y0 : y1;
int d = abs(y0 - y1);
while (d >= 0)
{
glVertex2i(x, y);
d--;
y++;
}
}
}

优缺点

由于有浮点数运算与取整,该算法不利于硬件实现,效率偏低,好处就是破罐子破摔,支持了所有斜率

中点画线法

数值微分法用的是横截式,而中点画线法就是用的一般式 ax+by+c=0ax+by+c=0,其中 a=y0y1a=y_0 - y_1b=x1x0b=x_1 - x_0,这个好像是初中学的吧
中点画线法同样采用了增量思维,xx 向右步进,如何让获得下一点的坐标呢,假设斜率是 (0,1)(0,1)


很明显,在这个斜率范围内,下一个点只有两个可能,要么在旁边 P1P_1,要么是旁边的上面 P2P_2

有一个判断标准,如果把 P1P_1P2P_2 的中点 MM,也就是划线的地方,带入直线方程,大于 0 就代表中点在直线上方,选 P1P_1,小于 0 就选 P2P_2,等于零就刚好是 MM 点了,这时候 P1P2P_1P_2 都可以,约定一下取上还是取下就好了,这样来说,误差相对要小很多

那如何判中点带入的结果呢,假设起点就是 P(x0,y0)P(x_0,y_0),起点肯定在线上,有 ax0+by0+c=0ax_0+by_0+c=0,那么下一点的中点必然是 M(x0+1,y0+0.5)M(x_0+1, y_0+0.5),带入方程,得到一个表达式 d=a(x0+1)+b(y0+0.5)+cd=a(x_0 + 1)+b(y_0 + 0.5)+c,化一下简就成了 d=a+0.5bd=a+0.5b,我们只需要判断 dd 的正负即可,大于 0 取下面,小于 0 取上面,等于 0 都可以取

那再下一个中点呢,需要根据当前选取的这一点为基础,如果选择了y+1y+1,那么d=a(x0+1+1)+b(y0+1+0.5)d = a(x_0 + 1 + 1) + b(y_0 + 1 + 0.5), 增量d1d_1就是a+ba+b

如果选择了yy,也就是下面这一点,yy没有增加,那么d=a(x0+1+1)+b(y0+0.5)d = a(x_0 + 1 + 1) + b(y_0 + 0.5), 增量d2d_2就是aa

增量一直是整数,唯一的浮点数是一开始的 dd,为了避免浮点运算,我们可以乘一个 2,因为我们只需要判断 dd 的正负号,乘法不会影响其正负性,增量我们也乘一个 2

算的时候这样算,但理解的时候就不用乘 2 了

代码

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
void MidpointLine(int x0, int y0, int x1, int y1)
{
int x, y, a, b;
int d, d1, d2;
x = x0;
y = y0;
a = y0 - y1;
b = x1 - x0;

d = 2 * a + b;
d1 = 2 * a;
d2 = 2 * (a + b);

glVertex2i(x, y);
while (x<x1)
{
if (d<0)
{
x++;
y++;
d += d2;
} else
{
x++;
d += d1;
}
glVertex2i(x, y);
}
}

优缺点

这个算法的优点

  • 不必计算直线之斜率,因此不做除法
  • 不用浮点数,只用整数
  • 只做整数加减法和乘 2 运算,而乘 2 运算可以用硬件移位实现

缺点也很明显,不计算斜率就只能处理斜率为 (0,1)(0,1) 的情况,一旦算了斜率,用到了浮点数,这个算法就没意义了,并且讨论起来比较麻烦,一般只用在 (0,1)(0,1) 的情况个

Bresenham 算法

最常用的算法,很有意思,算是综合了上面两种算法的优点
假设斜率是 (0,1)(0,1)

第一个点肯定在像素点上,下一个点同样只有两个选择,这时我们的判断依据不再是代入中点了,而是根据斜率 kk 的大小,只要 k>0.5k>0.5,那必然取上面那个点,等于 0 随便取,约定一下就行

这有点像上台阶,中间还有个板子,板子能自动把你升上去。 k>0.5k>0.5,说明腿长,一下跨到板子上了,可以往上一步走。如果 k<0.5k<0.5,没跨到板子上,那岂不是一直上不去,当然不会,还有一个空中停留的功能,dd 可以记录离台阶的距离,注意这不是离第一块台阶的距离,而是你脚下的那一块,所以你每上去一个台阶,dd 都会减一

除了第一步是靠腿长,后面的我们只关心 dd 的大小,只要 d>0.5d>0.5,只要坚持不懈照样可以上去

腿长的那位上去第一阶台阶后,她的高度可能还是负的,因为名义上被那块板子驮上去了,但高度实际上没变,反而还减了 1,下一步就没那么简单了

哈哈,大概就是这么个意思

为了让计算更简单,每次都比较 0.5 多没意思,新加一个变量 e=d0.5e=d-0.5ee 只要大于 0 就代表上台阶了

不算斜率有没有办法呢,当然有,在 Bresenham 算法中,e 只需要判断正负号就行,而乘法不影响正负,我们可以令新的 e=2edx=dxe^\prime = 2edx=-dx,同理 k=2kdx=2dyk^\prime= 2kdx= 2dy

对于任意斜率,我们需要分 k>1|k|>1k<1|k|<1 进行讨论,唯一的区别就是,如果 k>1|k|>1,也就是腿特别长,一下可以跨好几阶,这个我们就需要换个方向,交换dxdxdydy,总之,坡度不能太陡,否则就需要换个方向

另外,k的正负其实影响不大,直接用绝对值就行

代码

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
81
82
83
84
85
86
87
88
void BresenhamLine(int x0, int y0, int x1, int y1)
{
int x, y, dx, dy;
x = x0;
y = y0;
dx = x1 - x0;
dy = y1 - y0;
float k = dy / dx;
float e = -0.5;
for (int i = 0; i <= dx; i++)
{
glVertex2i(x, y);
x++;
e += k;
if (e >= 0)
{
y++;
e--;
}
}
}

// 改进后
void BresenhamLine(int x0, int y0, int x1, int y1)
{
int x, y, dx, dy, e;
x = x0;
y = y0;
dx = x1 - x0;
dy = y1 - y0;
e = -dx;

for (int i = 0; i <= dx; i++)
{
glVertex2i(x, y);
x++;
e += 2 * dy;
if (e >= 0)
{
y++;
e -= 2 * dx;
}
}
}

// 终极版本,适用于所有斜率
void BresenhamLine(int x0, int y0, int x1, int y1)
{
int x, y, dx, dy, s1, s2
x = x0;
y = y0;
dx = abs(x1 - x0);
dy = abs(y1 - y0);
s1 = x1 > x0 ? 1 : -1;
s2 = y1 > y0 ? 1 : -1;
bool interchange = false; // 默认不互换 dx、dy

if (dy > dx) // 当斜率大于 1 时,dx、dy 互换
{
int temp = dx;
dx = dy;
dy = temp;
interchange = true;
}

int e = -dx;

for(int i = 0; i < dx; i++)
{
glVertex2i(x, y);

if (!interchange)
x += s1;
else
y += s2;
e += 2 * dy;

if (e >= 0)
{
if (!interchange)
y += s2;
else
x += s1;
e -= 2 * dx;
}

}
}
文章作者: ourongxing
文章链接: https://orxing.top/post/d6824d87.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 OURONGXING

评论