简易的光栅化渲染器

本文是一个完整的图形学入门实践课程，目前还在更新中，GitHub已开源。理论上本文项目需要20-30个小时完成。不知道为啥我的网站统计字数也有问题。

主要内容是完全手撸一个光栅化渲染器。本文会从头复习图形学以及C++的相关知识，包括从零构造向量模版库、光栅化原理解释、图形学相关基础算法解释等等内容。

另外原作者的的透视矩阵部分是经过一定程度的简化的，与虎书等正统做法不同。我会先按照原文ssloy老师的思想表达关键内容，最后按照我的想法完善本文。并且，原项目中的数学向量矩阵库写得不是很好，我专门开了一章一步步重构这个库。

原项目链接：https://github.com/ssloy/tinyrenderer

本项目链接：https://github.com/Remyuu/Tiny-Renderer

[TOC]

0 简单的开始

五星上将曾经说过，懂的越少，懂的越多。我接下来将提供一个tgaimage的模块，你说要不要仔细研究研究？我的评价是不需要，如学。毕竟懂的越多，懂的越少。

在这里提供一个最基础的框架🔗，他只包含了tgaimage模块。该模块主要用于生成.TGA文件。以下是一个最基本的框架代码：

// main.cpp
#include "tgaimage.h"

const TGAColor white = TGAColor(255, 255, 255, 255);
const TGAColor red   = TGAColor(255, 0,   0,   255);
const TGAColor blue = TGAColor(0, 0, 255, 255);

int main(int argc, char** argv) {
    TGAImage image(100, 100, TGAImage::RGB);
    // TODO: Draw sth
    image.flip_vertically(); // i want to have the origin at the left bottom corner of the image
    image.write_tga_file("output.tga");
    return 0;
}

上面代码会创建一个100*100的image图像，并且以tga的格式保存在硬盘中。我们在TODO中添加代码：

image.set(1, 1, red);

代码作用是在(1, 1)的位置将像素设置为红色。output.tga的图像大概如下所示：

1.1 画线

这一章节的目标是画线。具体而言是制作一个函数，传入两个点，在屏幕上绘制线段。

第一关：实现画线

给定空间中的两个点，在两点(x0, y0)(x1, y1)之间绘制线段。

最简单的代码如下：

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { 
    for (float t=0.; t<1.; t+=.01) { 
        int x = x0 + (x1-x0)*t; 
        int y = y0 + (y1-y0)*t; 
        image.set(x, y, color); 
    } 
}

第二关：发现BUG

上面代码中的.01其实是错误的。不同的分辨率对应的绘制步长肯定不一样，太大的步长会导致：

所以我们的逻辑应该是：需要画多少像素点就循环Draw多少次。最简单的想法可能是绘制x1-x0个像素或者是y1-y0个像素：

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    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);
    }
}

上面代码是最简单的插值计算。但是这个算法是错误的。画三条线：

line(13, 20, 80, 40, image, white); 
line(20, 13, 40, 80, image, red); 
line(80, 40, 13, 20, image, blue);

白色线看起来非常好，红色线看起来断断续续的，蓝色线直接看不见了。于是总结出以下两个问题：

1. 理论上说白色线和蓝色线应该是同一条线，只是起点与终点不同

2. 太“陡峭”的线效果不对

接下来就解决这个两个问题。

此处“陡峭”的意思是(y1-y0)>(x1-x0)

下文“平缓”的意思是(y1-y0)<(x1-x0)

第三关：解决BUG

为了解决起点终点顺序不同导致的问题，只需要在算法开始时判断两点x分量的大小：

if (x0>x1) {
    std::swap(x0, x1); 
    std::swap(y0, y1); 
}

为了画出没有空隙的“陡峭”线，只需要将“陡峭”的线变成“平缓”的线。最终的代码：

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    if(std::abs(x0-x1)<std::abs(y0-y1)) { // “陡峭”线
        if (y0 > y1) { // 确保从下到上画画
            std::swap(x0, x1);
            std::swap(y0, y1);
        }
        for (int y = y0; y <= y1; y++) {
            float t = (y - y0) / (float) (y1 - y0);
            int x = x0 * (1. - t) + x1 * t;
            image.set(x, y, color);
        }
    }
    else { // “平缓”线
        if (x0 > x1) { // 确保从左到右画画
            std::swap(x0, x1);
            std::swap(y0, y1);
        }
        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);
        }
    }
}

如果你想测试你自己的代码是否正确，可以尝试绘制出以下的线段：

line(25,25,50,100,image,blue);
line(25,25,50,-50,image,blue);
line(25,25,0,100,image,blue);
line(25,25,0,-50,image,blue);

line(25,25,50,50,image,red);
line(25,25,50,0,image,red);
line(25,25,0,0,image,red);
line(25,25,0,50,image,red);

line(25,25,50,36,image,white);
line(25,25,50,16,image,white);
line(25,25,0,16,image,white);
line(25,25,0,36,image,white);

第四关：优化前言

目前为止，代码运行得非常顺利，并且具备良好的可读性与精简度。但是，画线作为渲染器最基础的操作，我们需要确保其足够高效。

性能优化是一个非常复杂且系统的问题。在优化之前需要明确优化的平台和硬件。在GPU上优化和CPU上优化是完全不同的。我的CPU是Apple Silicon M1 pro，我尝试绘制了9,000,000条线段。

发现在line()函数内，image.set();函数占用时间比率是38.25%，构建TGAColor对象是19.75%，14%左右的时间花在内存拷贝上，剩下的25%左右的时间花费则是我们需要优化的部分。下面的内容我将以运行时间作为测试指标。

第五关：Bresenham's 优化

我们注意到，for循环中的除法操作是不变的，因此我们可以将除法放到for循环外面。并且通过斜率估计每向前走一步，另一个轴的增量error。dError是一个误差积累，一旦误差积累大于半个像素（0.5），就对像素进行一次修正。

// 第一次优化的代码
void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    if(std::abs(x0-x1)<std::abs(y0-y1)) { // “陡峭”线
        if (y0>y1) {
            std::swap(x0, x1);
            std::swap(y0, y1);
        }
        int dx = x1 - x0;
        int dy = y1 - y0;
        float dError = std::abs(dx / float(dy));
        float error = 0;
        int x = x0;
        for (int y = y0; y <= y1; y++) {
            image.set(x, y, color);
            error += dError;
            if (error>.5) {
                x += (x1>x0?1:-1);
                error -= 1.;
            }
        }
    }else { // “平缓”线
        if (x0>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;
        int y = y0;
        for (int x = x0; x <= x1; x++) {
            image.set(x, y, color);
            error += dError;
            if (error>.5) {
                y += (y1>y0?1:-1);
                error -= 1.;
            }
        }
    }
}

没有优化用时：2.98s

第一次优化用时：2.96s

第六关：注意流水线预测

在很多教程当中，为了方便修改，会用一些trick将“陡峭”的线和“平缓”的线的for循环代码整合到一起。即先将“陡峭”线两点的xy互换，最后再image.set()的时候再换回来。

// 逆向优化的代码
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);