[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的值是否需要改变。
这个值的变化由直线方程给出，在这里我们仅使用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
- slope < 0只需要对begin和end加上符号，最后set的时候再变回来即可
- 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点
最后记得，反转一下y轴，因为bmp图像中的y轴方向是向下的
结果
