[TinyRenderer] Chapter1 p3 Line

news/2024/9/30 23:27:44

（注：本小节不是对划线算法事无巨细的证明，如果你需要更加系统的学习，请跳转至文末的参考部分）
如果你是一名曾经学习过图形学基础的学生，那么你一定对画线算法稔熟于心，中点划线算法，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的值是否需要改变。

这个值的变化由直线方程给出，在这里我们仅使用begin和end给出。（具体论证请翻阅参考）
还记得我们的假设场景么？在这个场景下：

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
那么对于其他场景呢？

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

解决方案：

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

实现

实际上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点