Line, and more than line

在计算机图形学的几何分支中,直线和曲线都属于隐式表示(Implicit Represent)的几何组件,我们需要一些高效的方式将这些图形以较高的质量绘制到屏幕上。

布雷森汉姆算法

虽然是相对朴素的算法,但是布雷森汉姆算法至今仍有着较高的使用率。

算法的基本想法是通过斜率来不断累积一个error,每当error的值超过一个阈值(0.5)的时候就在另一个方向上进行长度为1像素的前进,最终绘制出一根在屏幕上连续的直线。

4Foeg0.png

核心代码如下:

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
int x0 = line[0][0], y0 = line[0][1], x1 = line[1][0], y1 = line[1][1];
bool steep = abs(y1 - y0) > abs(x1 - x0);
if (steep) {
swap(x0, y0);
swap(x1, y1);
}
if (x0 > x1) {
swap(x0, x1);
swap(y0, y1);
}
float dx = x1 - x0;
float dy = abs(y1 - y0);
float err = 0;
float derr = dy / dx;
int ystep = y0 < y1 ? 1 : -1;
int y = y0;
for (int x = x0; x <= x1; x++) {
if (steep) {
image.set_white_alpha(y, x);
} else {
image.set_white_alpha(x, y);
}
err += derr;
if (err > 0.5f) {
y += ystep;
err -= 1.0f;
}
}

布雷森汉姆算法允许我们以较高的效率(去浮点化)地绘制一条效果尚可的直线,不过缺点也很明显,绘制出的直线上分布着许多锯齿,如果希望得到一条质量较高的直线,则需要用到另一个算法。

吴小林算法

布雷森汉姆算法虽然可以让我们绘制出连续的直线,但是效果却有些不忍直视,曲线的四周遍布着各种锯齿

46SsEQ.png

使用布雷森汉姆算法绘制的直线

46SyNj.png

使用吴小林算法绘制的直线

吴小林算法通过直线周围绘制一些透明度非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
auto fpart = [](float x) { return x - floorf(x); };
auto rfpart = [&fpart](float x) { return 1 - fpart(x); };
int x0 = line[0][0], y0 = line[0][1], x1 = line[1][0], y1 = line[1][1];
bool steep = abs(y1 - y0) > abs(x1 - x0);
if (steep) {
swap(x0, y0);
swap(x1, y1);
}
if (x0 > x1) {
swap(x0, x1);
swap(y0, y1);
}
float dx = x1 - x0;
float dy = abs(y1 - y0);
float gradient = dy / dx;
if (dx == 0.0) {
gradient = 1.0;
}

int xend = round(x0);
int yend = y0 + gradient * (xend - x0);

float xgap = rfpart(x0 + 0.5f);
int xpxl1 = xend;
int ypxl1 = (int)yend;

if (steep) {
image.set_white_alpha(ypxl1, xpxl1, rfpart(yend) * xgap);
image.set_white_alpha(ypxl1 + 1, xpxl1, fpart(yend) * xgap);
} else {
image.set_white_alpha(xpxl1, ypxl1, rfpart(yend) * xgap);
image.set_white_alpha(xpxl1, ypxl1 + 1, fpart(yend) * xgap);
}
float intery = yend + gradient;

xend = round(x1);
yend = y1 + gradient * (xend - x1);
xgap = fpart(x1 + 0.5);
int xpxl2 = xend;
int ypxl2 = (int)(yend);
if (steep) {
image.set_white_alpha(ypxl2, xpxl2, rfpart(yend) * xgap);
image.set_white_alpha(ypxl2 + 1, xpxl2, fpart(yend) * xgap);
} else {
image.set_white_alpha(xpxl2, ypxl2, rfpart(yend) * xgap);
image.set_white_alpha(xpxl2, ypxl2 + 1, fpart(yend) * xgap);
}

// main loop
if (steep) {
for (int x = xpxl1 + 1; x <= xpxl2 - 1; x++) {
image.set_white_alpha((int)(intery), x, rfpart(intery));
image.set_white_alpha((int)(intery) + 1, x, fpart(intery));
intery = intery + gradient;
}
} else {
for (int x = xpxl1 + 1; x <= xpxl2 - 1; x++) {
image.set_white_alpha(x, (int)(intery), rfpart(intery));
image.set_white_alpha(x, (int)(intery) + 1, fpart(intery));
intery = intery + gradient;
}
}

总结

直线绘制其实并不是计算机图形学中相关知识的直接体现,但是属于是一个非常有意思的话题,所以出了一篇博客来说说。

作者

Hyiker Hu

发布于

2021-09-12

更新于

2021-09-26

许可协议

评论