前言
学完GAMES101后，打算学习写一个软渲染器来加深对渲染的理解，了解一下图形管线前前后后都做了哪些工作
但本系列重在说明原理，完整的源代码不会展示出，想了解的请移步至ssloy/tinyrenderer: A brief computer graphics / rendering course (github.com)
Bresenham算法介绍
画线算法有三种，分别是DDA算法、中点算法、Bresenham算法，但为什么我们选择Bresenham算法呢？因为Bresenham算法仅仅使用整数加法、减法和位移，是一种增量误差算法，这些操作省时高效精确，是当前最有效的画线算法。并且，此算法并不局限于直线，圆等其他曲线同样可以画。更重要的是，该算法用于绘图仪等硬件和现代显卡的图形芯片中，以及非常多的软件图形库中都可以看到他的身影。鉴于Bresenham算法的简单高效，因此我们选用他作为实现渲染器的一部分
Bresenham算法思想
在图形学中，屏幕是一个二维数组，数组里的每一个元素都为一个像素,其中每个像素都必须是整数
Bresenham算法是设定一个起点，一个终点，按照起点到终点的顺序，计算直线和垂直网格线的交点，再根据误差项error变量来确定该列两像素点中离此交点最近的那个。也就是说，假设一点(x,y)，若交点并不是在像素点上，那么就会从(x + 1, y)和(x+1, y+1)中去选择一个最合适的点，那么怎么才是最合适的呢？很简单，我们取两点之间的中点，若这个交点在中点上面，则选取(x+1, y+1)；若交点在中点下面，则选取(x+1,y)
Bresenham算法实现
我们假设每次x增加1，y增量为0或1,k为斜率;鉴于每次都需要计算中点且中点是浮点数，过于麻烦，因此我们将误差量设为d = 0,d = d + k( 0 < k 0.5，则d -= 1,y+1
实现如下：
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { bool steep = false; //dy需要小于dx，否则画出的线不够密集，有空隙 if (std::abs(x0-x1)x1) { std::swap(x0, x1); std::swap(y0, y1); } int dx = x1-x0; int dy = y1-y0; //误差值 float derror = std::abs(dy/float(dx)); float error = 0.0; int y = y0; for (int x=x0; x 0.5) { y += ( y1 > y0 ? 1 : -1 ); error -= 1.0; } } } 优化上面的方法其实已经可以实现画线了，但这并不是Bresenham算法的灵魂，它精彩的地方在于仅仅使用整数加减。想想上面这段代码还有什么地方可以优化的？
我们发现 float derror = std::abs(dy/float(dx))和if (error > 0.5)都包含浮点数，Bresenham算法的精髓并没有体现，那么怎么做呢？
我们可以做一种尝试，让初始值e\(0\) = d – 0.5, e = e + k;每当e大于0，e -= 1;但我们会发现还是稍有不足，e、k依旧为浮点数,我们需要想办法消除e、k，怎么做呢？
下面，我们来做另一种尝试。定义一个E = e * 2 * dx代替e,如此e的浮点数0.5即可消除;每走一步有E = (e + k) * 2 * dy = E + 2 * dy，也就是说每次E增加2dy;每当e大于0,E = (e-1) * 2 * dx = E – 2 * dx
代码如下：
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { bool steep = false; if (std::abs(x0-x1)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 dx) { y += (y1>y0?1:-1); error2 -= dx*2; } } } 此时，我们才真正实现了Bresenham算法,加减都是整数简单高效！