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;
}
}

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

吴小林算法

作者

Hyiker Hu

发布于

2021-09-12

更新于

2021-09-14

许可协议

评论