[TinyRenderer] Chapter1 p3 Line

(注:本小节不是对划线算法事无巨细的证明,如果你需要更加系统的学习,请跳转至文末的参考部分)
如果你是一名曾经学习过图形学基础的学生,那么你一定对画线算法稔熟于心,中点划线算法,Bresenham算法。其中,现代光栅化器中使用最多的就是Bresenham算法,它以去除了除法和浮点运算而著称。

但如果现在让你看下面的这段代码,你能否把它和Bresenham算法联系起来呢?

void Segment::draw(const Point2i begin, const Point2i end, const RGBPixel& color, BMPImage& image)
{
    int x0 = begin.x;
    int y0 = begin.y;
    int x1 = end.x;
    int y1 = end.y;

    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sx = (x0 < x1) ? 1 : -1;
    int sy = (y0 < y1) ? 1 : -1;
    int error = dx - dy;

    while (true)
    {
        image.set(x0, y0, color);

        if (x0 == x1 && y0 == y1)
            break;
        int e2 = 2 * error;
        if (e2 > -dy)
        {
            error -= dy;
            x0 += sx;
        }
        if (e2 < dx)
        {
            error += dx;
            y0 += sy;
        }
    }
}

如果你可以顺利地说出每行代码的含义,那么恭喜你,你已经完全掌握了Bresenham算法,你可以跳过本小节,进行下一小节的学习。
但如果你还有所异或,那么相信我,看完本小节,你必定有所收获。

本节目标

在光栅化渲染器中加入画线功能

分析

首先,让我们考虑一种再简单不过的场景,你从一个初始点begin出发,从左向右,沿着斜率在0~1的直线到达end

这是一个Bresenham算法的基础场景,在这个场景中,我们可以通过中点划线算法知道存在一个判断依据,用于确定在每次遍历时y的值是否需要改变。

这个值的变化由直线方程给出,在这里我们仅使用beginend给出。(具体论证请翻阅参考)
还记得我们的假设场景么?在这个场景下:

assert: (x0 < x1) and ((y1 – y0) < (x1 – x0))
δx = x1 – x0;
δy = y1 – y0;
incrE = 2 * δy;
incrNE = 2 * (δy - δx);
d = 2 * δy – δx;

保持x递增的同时,判断y是否改变。
d<0 -> d += incrE
else -> d += incrNE and ++y

现在我们得到了在斜率为0~1的时候的Bresenham算法,且begin.x<end.x
那么对于其他场景呢?

  1. begin.x > end.x
  2. slope < 0 or slope > 1
  3. 平行于坐标轴的方向

解决方案:

  1. 只需要将begin和end两个点做一下交换即可
  2. slope < 0 or slope > 1
    1. slope < 0只需要对begin和end加上符号,最后set的时候再变回来即可
    2. slope > 1这个更加简单,只需要交换xy即可
  3. 平行于轴体的方向只需要特判一下进行处理,而且这样效率更高
实现

实际上TinyRenderer的实现思路也是如此:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { 
    bool steep = false; 
    if (std::abs(x0-x1)<std::abs(y0-y1)) { 
        std::swap(x0, y0); 
        std::swap(x1, y1); 
        steep = true; 
    } 
    if (x0>x1) { 
        std::swap(x0, x1); 
        std::swap(y0, y1); 
    } 
    int dx = x1-x0; 
    int dy = y1-y0; 
    int derror2 = std::abs(dy)*2; 
    int error2 = 0; 
    int y = y0; 
    for (int x=x0; x<=x1; x++) { 
        if (steep) { 
            image.set(y, x, color); 
        } else { 
            image.set(x, y, color); 
        } 
        error2 += derror2; 
        if (error2 > dx) { 
            y += (y1>y0?1:-1); 
            error2 -= dx*2; 
        } 
    } 
} 

而这种实现还可以转化成下面的这种写法,就是上面我们提到的方法,更加优雅,不需要特判条件,使用统一变量。

实现

void Segment::draw(const Point2i begin, const Point2i end, const RGBPixel& color, BMPImage& image)
{
    int x0 = begin.x;
    int y0 = begin.y;
    int x1 = end.x;
    int y1 = end.y;

    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    // 决定决策会落在坐标系四个方位中的哪一个
    int sx = (x0 < x1) ? 1 : -1;
    int sy = (y0 < y1) ? 1 : -1;
    // 维护error,用于决策下一个点的位置
    int error = dx - dy;

    while (true)
    {
        image.set(x0, y0, color);

        if (x0 == x1 && y0 == y1)
            break;
        int e2 = 2 * error;
        // 每次迭代会进行两次决策,共同决定下一个点是在一个角落中的哪一个
        // 如果在x轴上的误差较大
        if (e2 > -dy)
        {
            error -= dy;
            x0 += sx;
        }
        // 如果在y轴上的误差较大
        if (e2 < dx)
        {
            error += dx;
            y0 += sy;
        }
    }
}

误差判别的依据,B,C点

最后记得,反转一下y轴,因为bmp图像中的y轴方向是向下的

结果

Reference

  1. # Lesson 1: Bresenham’s Line Drawing Algorithm
  2. Bresenham.pdf
  3. # wiki Bresenham's line algorithm

热门相关:弃妃不承欢:腹黑国师别乱撩   夫人每天都在线打脸   以身为饵的她   巨星小甜妻:前夫,请出局   极品明君