Line, and more than line

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

布雷森汉姆算法

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

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

核心代码如下：

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

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

吴小林算法

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

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

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

吴小林算法通过直线周围绘制一些透明度非1的像素来实现直线的平滑化。核心代码如下：

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

总结

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