软光栅|02 画一条直线
用离散的思维考虑问题！
在现实世界我们用笔画一条直线，那它看起来就是光滑的、连续的一条直线，但在计算机世界，如果我们在屏幕上也画一条直线…好吧那看起来也很光滑连续…但你要知道其实这是因为屏幕分辨率比较高，如果我们不断放大图片…那就会像这样：
图一：10%缩放
图二：200%缩放
好吧这其实是用Excel画的，上面那张图看起来已经有一点棱角了，但你们就当他是光滑的吧！能明白意思就好！计算机世界的图像都是以像素为单位绘制的，放大看肯定是会像图二那样，而不是现实世界的连续直线
也因此，像素是没有类似(0.5,0.5)的坐标的，像素是最小单位，必然是整数，只能是(0,0)、(1,1)、(1,2)，注意，像素和数组一样，是从0开始计算的
但我们数学意义上的坐标是完全连续的，假如有一条直线y=x²，我们当然知道当x=0.5时，y=0.25，但注意，这是数学意义上的坐标，并不能直接转为屏幕的像素坐标，需要做截断处理
在这里，我们假设像素的长宽都是1，那么坐标(0.5,0.5)就是(0,0)这个像素的中心，注意，(0.5,0.5)我指的是数学意义上的坐标，而(0,0)我指的是像素坐标，即第一行第一列的那个像素块，这应该不难理解
再次强调，(float,float)坐标是数学意义上的坐标，对于像素来说，只有整数坐标，(0.1,0.9)和(0.9,0.1)，这两个坐标在数学上是完全不同的意义，但如果转为像素坐标，那对于像素来说，他们都属于第一个像素(0,0)，是同一个坐标！！！
假设像素高宽都是1，那么B点是第一像素的中心，此时A点是(0.5,0.1)，那么很显然，A属于第一个像素，我们只要
image.set(1,1,red)
简单的画一条直线
假设有如图这么一条直线y=0.5x
思考一下我们应该如何正确的填充像素呢？
我们可以用以下算法轻松截断像素点
// C(x0,y0) D(x1,y1)，这是数学意义上的坐标，但目前只能是整数值
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color)
{
// t从0累加到1，很明显t是0的时候x就是x0，t是1的时候x是x1，其实这就是个线性插值算法，会根据t的值，在x0到x1之前插值出一个结果，y同理
for (float t=0.; t<1.; t+=0.01)
{
int x = x0 + (x1-x0)*t;
int y = y0 + (y1-y0)*t;
image.set(x, y, color);
}
}
思考：为什么xy要从float类型转为int类型，那不就损失精度了吗？
要的就是损失精度。。利用int类型截断float，假如我们的C是(0,0)，D是(8,4)，当t是0.2的时候，我们会得到一个点P(1.6,0.8)，那么这个值属于哪个像素呢？很明显，属于(1,0)像素，只要(int)P就能得到这个结果，这就是用int截断float的意义所在
这就OK了吗？
虽然这么做确实有一定效果，但思考一个问题，为什么t+=0.01？为什么步长是0.01呢？0.1可不可以，会有什么印象？0.001可不可以，会有什么影响？
如果我需要绘制这样一条直线，C(0,0)，D(1,1)，聪明的同学一眼就能看出，其实说是直线，但这条直线只会有1个像素，理论上我们只要把这一个像素涂上颜色就好了，但如果我们设置步长为0.001，会发生什么问题？
那就是哪怕我们只有一个像素要绘制，我们的循环也会执行1000次！！！而其实这1000次的结果利用int截断后，都是同一个结果那就是(0,0)，这是十分浪费效率的。。
解决方案也很简单，利用直线的两点式定义：
(y-y1) (y2-y1) = (x-x1) (x2-x1)
那只要给定任何一个x坐标，我们就能算出对应的y坐标，然后判断(x,y)属于哪一个像素，并set，并且我们之前是按照数学坐标进行累加的（t+=0.01），现在我们改为像素坐标，每次都移动一个像素的距离
起始位置当然是C，结束位置是D，我们按x轴累加
// C(x0,y0),D(x1,y1)
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
// 这里表示从X0开始，每次移动1个像素，计算对应的y
for (int x=x0; x<=x1; x++)
{
// 这两步看着很迷，其实就是上面两点式转化了一下而已，也就是在求对应的y，可以带入自己验证一下
float t = (x-x0)/(float)(x1-x0);
int y = y0*(1.-t) + y1*t;
image.set(x, y, color);
}
}
举个例子，假设C(0,0)，D(8,4)，最开始我们的x=x0=0，对应的y自然也是0，那么第一个像素点就是(0,0)，然后不断递增x，假如我们此时的x是5，那么会得到y是2.5，利用int截断后，得到的像素点就是(5,2)，看一下图，发现是符合预期的~
运行代码测试一下
#include "tgaimage.h"
// 定义颜色
const TGAColor white = TGAColor(255, 255, 255, 255);
const TGAColor red = TGAColor(255, 0, 0, 255);
int main()
{
TGAImage image(500, 500, TGAImage::RGB);
line(0, 0, 500, 500, image, red);
// 这一步是必须的！注意，再次强调，TGAImage的坐标左上角是(0,0)，垂直翻转的目的是把坐标系转为我们熟悉的三角坐标系，即左下角为原点
image.flip_vertically();
image.write_tga_file("output.tga");
return 0;
}
查看对应的输出图片，不出意外的画应该如图
真的OK了吗？
请思考一下，如上的代码真的没有问题吗？那不妨试试
line(500, 500, 0, 0, image, red);
结果呢？不出意外的画应该是一张空的图片，啥也没有，问题是很显然的
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
// 问题出在这，如果按照这么循环，那默认x0是要比x1小的，如果x0比x1大就会出错误
for (int x=x0; x<=x1; x++)
{
float t = (x-x0)/(float)(x1-x0);
int y = y0*(1.-t) + y1*t;
image.set(x, y, color);
}
}
再解决这个问题之前，其实还有另一个问题，现在我们是默认按照x轴循环计算的，但一定要是x轴吗，只能是x轴吗？
如图，此时如果还按照x轴计算会有什么问题？
会有很大的问题。。因为我们是按照1像素的间距递增的，如果此时还按照x轴循环，那我们只能循环两次，也就是说只有(1,1)像素和(2,6)像素会有颜色，中间会有很多空缺，原因是y轴的增长幅度大于x轴，此时我们应该按照y轴循环才对！！
上述两个问题我们改进一下代码可以同时解决
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
// steep意为陡峭的，其实就是指xy轴的增长幅度，如果x的幅度大，那就不陡峭，如果y的幅度大，那就陡峭。。。
bool steep = false;
// 这里就是判断xy轴哪个轴的步幅更大，我们默认是按照x轴计算的，所以如果y的步幅更大，那就把xy交换就好
if (std::abs(x0-x1)<std::abs(y0-y1))
{
std::swap(x0, y0);
std::swap(x1, y1);
steep = true;
}
// 这里解决的是第一个问题，如果x0比x1小那就会出问题，所以此时我们也要交换一下
if (x0>x1)
{
std::swap(x0, x1);
std::swap(y0, y1);
}
// 然后就是正常循环了，需要注意的是，如果我们steep为1，也就是说我们交换了xy轴，那set的时候也需要反过来
// 举个例子，如果按照上图，我们默认是从(0,0)到(2,6)，此时把xy交换了，那就是从(0,0)到(6,2)了，如果set的时候还是按照(x,y)来set
// 那最终画出来的直线会和图中直线对称的，所以set的时候需要set(y,x)，还不理解的话画一下图就很容易明白了
for (int x=x0; x<=x1; x++) {
float t = (x-x0)/(float)(x1-x0);
int y = y0*(1.-t) + y1*t;
if (steep)
{
image.set(y, x, color);
}
else
{
image.set(x, y, color);
}
}
}
此时我们在尝试一下
line(500, 500, 0, 0, image, red);
现在应该就没有问题了
优化
思考一下，现在代码确实没有问题了，但足够好吗？
我们利用两点式来求坐标，很简单，但你会发现计算量比较大，先求一个t，然后求一个y，而每次计算都涉及好几次加减乘除（大家可能觉得这也就是三四次运算，对于CPU恐怖的运算来来说，当然是小意思，确实没错，如果我们只循环一次的话，那对于CPU来说，3次计算和3000次都啥差别，但注意，在我们之后的绘制中，这个循环数量会非常的恐怖，非常非常大，所以我们要尽可能减少计算量）
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;
// 这个derror其实就是斜率k，应该一下看就看出来了，但它是绝对值
float derror = std::abs(dy/float(dx));
float error = 0;
int y = y0;
for (int x=x0; x<=x1; x++)
{
if (steep)
{
image.set(y, x, color);
}
else
{
image.set(x, y, color);
}
// 这部分需要好好理解
error += derror;
if (error>0.5)
{
y += (y1>y0?1:-1);
error -= 1.;
}
}
}
我们以这张图为例
先看直线AB，很明显斜率K=derorr=0.5，那么error+=derror到底意味着什么呢？其实就是增长幅度罢了。。因为我们的x是固定增长，每次都+1，那么对应的，每次y应该加多少呢？其实就是+error。。可能这么说有点迷，我把公式写出来大家就明白了，首先：dy/dx=k，那很容易得到dy=dx*k，而我们此时的dx固定是1，那么dy就固定是k了，所以每次咱们x+1，error也就是y，就要加上derror也就是k
那么为什么error>0.5时，y才需要+1或者-1呢？看图，这问题其实看图很明显，如图，当x=1时候，error=1/3<0.5，此时y像素还是0，当x=1.5时候（注意这里只是举例，实际上x不可能是1.5，我们每次都+1，x只能是1或者2），error=0.5，此时y像素还是0，但是！一旦x=2，咱们此时的error就会等于2/3>0.5，观察图片很容易知道，此时的y像素坐标已经是1了！
至于y是+1还是-1，那自然是根据斜率的正负来判断
这里留一个问题，为什么error-=1？我们是根据error>0.5来判断y是否需要增加的，但减的时候为什么是-1而不是-0.5呢？其实大家画画图就明白了，关键在于什么时候我们的y像素才真的需要+1
优化之后我们发现，此时的for循环中，只有最多3次加减法了，没有乘法，也没有除法
最后一次优化（…)
目前的算法中存在好几次float变量，我们为什么需要float呢，因为要做除法必须用float。。那换句话，我们可不可以不用除法？
当然是可以的。。
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;
// ==== 以上内容无改动 ====
// 在这里，我们把所有derror相关的变量全部*2dx，然后化简
// (dy/dx)*2dx=2dy
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);
}
// 这里换成derror2
error2 += derror2;
// 0.5*2dx=dx
if (error2 > dx)
{
y += (y1>y0?1:-1);
// 1*2dx=2dx
error2 -= dx*2;
}
}
}
目的就是去除所有的除法，并且连float都没了，Amazing！！！
运行代码测试以下，应该没有问题~