简易的光栅化渲染器

本文是一个完整的图形学入门实践课程，目前还在更新中，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);
        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++) {
        if (steep) {
            image.set(y, x, color);
        } else {
            image.set(x, y, color);
        }
        error += dError;
        if (error>.5) {
            y += (y1>y0?1:-1);
            error -= 1.;
        }
    }
}

没有优化用时：2.98s

第一次优化用时：2.96s

合并分支用时：3.22s

惊奇地发现，竟然有很大的性能下降！背后的原因之一写在了这一小节的标题中。这是一种刚刚我们的操作增加了控制冒险（Control Hazard）。合并分支后的代码每一次for循环都有一个分支，可能导致流水线冒险。这是现代处理器由于预测错误的分支而导致的性能下降。而第一段代码中for循环没有分支，分支预测可能会更准确。

简而言之，减少for循环中的分支对性能的提升帮助非常大！

值得一提的是，如果在Tiny-Renderer中使用本文的操作，速度将会进一步提升。这在Issues中也有相应讨论：链接🔗。

第七关：浮点数整型化

为什么我们必须用浮点数呢？在循环中我们只在与0.5做比较的时候用到了。因此我们完全可以将error乘个2再乘个dx（或dy），将其完全转化为int。

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

没有优化用时：2.98s

第一次优化用时：2.96s

合并分支用时：3.22s

第二次优化用时：2.96s

优化程度也较为有限了，原因是在浮点数化整的过程中增加了计算的次数，与浮点数的计算压力相抵消了。

1.2 三维画线

在前面的内容中，我们完成了Line()函数的编写。具体内容是给定屏幕坐标上的两个点就可以在屏幕中绘制线段。

第一关：加载.obj

首先，我们创建model类作为物体对象。我们在model加载的.obj文件里可能会有如下内容：

v 1.0 2.0 3.0

v表示3D坐标，后面通常是三个浮点数，分别对应空间中的x, y, z。上面例子代表一个顶点，其坐标为 (1.0, 2.0, 3.0)。

当定义一个面（f）时，你引用的是先前定义的顶点（v）的索引。

f 1 2 3
f 1/4/1 2/5/2 3/6/3

上面两行都表示一个面，

• 第一行表示三个顶点的索引

• 第二行表示顶点/纹理坐标/法线的索引

在这里我提供一个简单的 .obj 文件解析器 model.cpp 。你可以在此处找到当前项目链接🔗。以下是你可能用到的model类的信息：

• 模型面数量：i<model->nfaces()

• 获取第n个面的三个顶点索引：model->face(n)

• 通过索引获取顶点三维坐标：model->vert()

本项目使用的.obj文件的所有顶点数据已做归一化，也就是说v后面的三个数字都是在[-1, 1]之间。

第二关：绘制

在这里我们仅仅考虑三维顶点中的(x, y)，不考虑深度值。最终在main.cpp中通过model解析出来的顶点坐标绘制出所有线框即可。

for (int i=0; i<model->nfaces(); i++) { 
    std::vector<int> face = model->face(i); 
    for (int j=0; j<3; j++) { 
        Vec3f v0 = model->vert(face[j]); 
        Vec3f v1 = model->vert(face[(j+1)%3]); 
        int x0 = (v0.x+1.)*width/2.; 
        int y0 = (v0.y+1.)*height/2.; 
        int x1 = (v1.x+1.)*width/2.; 
        int y1 = (v1.y+1.)*height/2.; 
        line(x0, y0, x1, y1, image, blue); 
    } 
}

这段代码对所有的面进行迭代，将每个面的三条边都进行绘制。

第三关：优化

将不必要的计算设置为const，避免重复分配释放内存。

const float halfWidth = screenWidth / 2.0f;
const float halfHeight = screenHeight / 2.0f;

int nfaces = model->nfaces();
for (int i = 0; i < nfaces; ++i) {
    const std::vector<int>& face = model->face(i);
    Vec3f verts[3];

    for (int j = 0; j < 3; ++j) {
        verts[j] = model->vert(face[j]);
    }

    for (int j = 0; j < 3; ++j) {
        const Vec3f& v0 = verts[j];
        const Vec3f& v1 = verts[(j + 1) % 3];

        int x0 = (v0.x + 1.0f) * halfWidth;
        int y0 = (v0.y + 1.0f) * halfHeight;
        int x1 = (v1.x + 1.0f) * halfWidth;
        int y1 = (v1.y + 1.0f) * halfHeight;

        line(x0, y0, x1, y1, image, blue);
    }
}

2.1 三角形光栅化

接下来，绘制完整的三角形，不光是一个个三角形线框，更是要一个实心的三角形！为什么是三角形而不是其他形状比如四边形？因为三角形可以任意组合成为所有其他的形状。基本上，在OpenGL中绝大多数都是三角形，因此我们的渲染器暂时无需考虑其他的东西了。

当绘制完一个实心的三角形后，完整渲染一个模型也就不算难事了。

在Games101的作业中，我们使用了AABB包围盒与判断点是否在三角形内的方法对三角形光栅化。你完全可以用自己的算法绘制三角形，在本文中，我们使用割半法处理。

第一关：线框三角形

利用上一章节完成的line()函数，进一步将其包装成绘制三角形线框的triangleLine()函数。

void triangleLine(Vec2i v0, Vec2i v1, Vec2i v2, TGAImage &image, TGAColor color){
    line(v0.u, v0.v, v1.u, v1.v, image, color);
    line(v0.u, v0.v, v2.u, v2.v, image, color);
    line(v1.u, v1.v, v2.u, v2.v, image, color);
}
...
triangleLine(Vec2i(0,0),Vec2i(25,25),Vec2i(50,0),image,red);

第二关：请你自己画实心的三角形

这一部分最好由你自己花费大约一个小时完成。一个好的三角形光栅化算法应该是简洁且高效的。你目前的项目大概是这样的：链接🔗。

【此处省略一小时】

第三关：扫描线算法

当你完成了你的算法之后，不妨来看看其他人是怎么做的。为了光栅化一个实心三角形，一种非常常见的方法是使用扫描线算法：

1. 按 v（或 y）坐标对三角形的三个顶点进行排序，使得 v0 是最低的，v2 是最高的。

2. 对于三角形的每一行（从 v0.v 到 v2.v），确定该行与三角形的两边的交点，并绘制一条从左交点到右交点的线。

void triangleRaster(Vec2i v0, Vec2i v1, Vec2i v2, TGAImage &image, TGAColor color) {
    if (v0.v > v1.v) std::swap(v0, v1);
    if (v0.v > v2.v) std::swap(v0, v2);
    if (v1.v > v2.v) std::swap(v1, v2);

    // Helper function to compute the intersection of the line and a scanline
    auto interpolate = [](int y, Vec2i v1, Vec2i v2) -> int {
        if (v1.v == v2.v) return v1.u;
        return v1.u + (v2.u - v1.u) * (y - v1.v) / (v2.v - v1.v);
    };

    for (int y = v0.v; y <= v2.v; y++) {
        // Intersect triangle sides with scanline
        int xa = interpolate(y, v0, v2); // Intersection with line v0-v2
        int xb = (y < v1.v) ? interpolate(y, v0, v1) : interpolate(y, v1, v2); // Depending on current half

        if (xa > xb) std::swap(xa, xb);

        // Draw horizontal line
        for (int x = xa; x <= xb; x++) {
            image.set(x, y, color);
        }
    }
}

第四关：包围盒逐点扫描

介绍另一个非常有名的方法，包围盒扫描方法。将需要光栅化的三角形框上一个矩形的包围盒子内，在这个包围盒子内逐个像素判断该像素是否在三角形内。如果在三角形内，则绘制对应的像素；如果在三角形外，则略过。伪代码如下：

triangle(vec2 points[3]) { 
    vec2 bbox[2] = find_bounding_box(points); 
    for (each pixel in the bounding box) { 
        if (inside(points, pixel)) { 
            put_pixel(pixel); 
        } 
    } 
}

想要实现这个方法，主要需要解决两个问题：找到包围盒、判断某个像素点是否在三角形内。

第一个问题很好解决，找到三角形的三个点中最小和最大的两个分量两两组合。

第二个问题似乎有些棘手。我们需要学习什么是重心坐标 （barycentric coordinates ）。

第五关：重心坐标

利用重心坐标，可以判断给定某个点与三角形之间的位置关系。

给定一个三角形ABC和任意一个点P $(x,y)$ ，这个点的坐标都可以用点ABC线性表示。不理解也无所谓，简单理解就是一个点P和三角形三点的关系可以用三个数字来表示，像下面公式这样：

$$P = (1-u-v)A+uB+vC$$

我们把上面的式子解开，得到关于 $\overrightarrow{AB},\overrightarrow{AC}和\overrightarrow{AP}$的关系：

$$P=A+u \overrightarrow{A B}+v \overrightarrow{A C}$$

然后将点P挪到同一边，得到下面的式子：

$$u \overrightarrow{A B}+v \overrightarrow{A C}+\overrightarrow{P A}=\overrightarrow{0}$$

然后将上面的向量分为x分量与y分量，写成两个等式。接下来用矩阵表示他们：

$$\left\{\begin{aligned} {\left[\begin{array}{lll} u & v & 1 \end{array}\right]\left[\begin{array}{l} \overrightarrow{A B}_x \\ \overrightarrow{A C}_x \\ \overrightarrow{P A}_x \end{array}\right]=0 } \\ {\left[\begin{array}{lll} u & v & 1 \end{array}\right]\left[\begin{array}{l} \overrightarrow{A B}_y \\ \overrightarrow{A C}_y \\ \overrightarrow{P A}_y \end{array}\right]=0 } \end{aligned}\right.$$

两个向量点积是0，说明两个向量垂直。右边这俩向量都与 $[u v 1]$ ，说明他们的叉积就是$k[u v 1]$ ，因此轻轻松松解出uv。

梳理一下，当务之急是判断给定的一个点与一个三角形的关系。直接给出结论，如果点在三角形内部，则这三个系数都属于（0,1）之间。直接给出光栅化一个三角形的代码：

Vec3f barycentric(Vec2i v0, Vec2i v1, Vec2i v2, Vec2i pixel){
    // v0, v1, v2 correspond to ABC
    Vec3f u = Vec3f(v1.x-v0.x,// AB_x
                    v2.x-v0.x,// AC_x
                    v0.x-pixel.x)// PA_x
              ^
              Vec3f(v1.y-v0.y,
                    v2.y-v0.y,
                    v0.y-pixel.y);
    if (std::abs(u.z)<1) return Vec3f(-1,1,1);
    return Vec3f(1.f-(u.x+u.y)/u.z, u.y/u.z, u.x/u.z);
}
// 重心坐标的方法 - 光栅化三角形
void triangleRaster(Vec2i v0, Vec2i v1, Vec2i v2, TGAImage &image, TGAColor color){
    // Find The Bounding Box
    Vec2i* pts[] = {&v0, &v1, &v2};// Pack
    Vec2i boundingBoxMin(image.get_width()-1,  image.get_height()-1);
    Vec2i boundingBoxMax(0, 0);
    Vec2i clamp(image.get_width()-1, image.get_height()-1);
    for (int i=0; i<3; i++) {
        boundingBoxMin.x = std::max(0, std::min(boundingBoxMin.x, pts[i]->x));
        boundingBoxMin.y = std::max(0, std::min(boundingBoxMin.y, pts[i]->y));

        boundingBoxMax.x = std::min(clamp.x, std::max(boundingBoxMax.x, pts[i]->x));
        boundingBoxMax.y = std::min(clamp.y, std::max(boundingBoxMax.y, pts[i]->y));
    }

    // For Loop To Iterate Over All Pixels Within The Bounding Box
    Vec2i pixel;
    for (pixel.x = boundingBoxMin.x; pixel.x <= boundingBoxMax.x; pixel.x++) {
        for (pixel.y = boundingBoxMin.y; pixel.y <= boundingBoxMax.y; pixel.y++) {
            Vec3f bc = barycentric(v0, v1, v2, pixel);
            if (bc.x<0 || bc.y<0 || bc.z<0 ) continue;
            image.set(pixel.x, pixel.y, color);
        }
    }
}

barycentric()函数可能比较难理解，可以暂时抛弃研究其数学原理。并且上面这段代码是经过优化的，如果希望了解其原理可以看我这一篇文章：链接🔗。

const int screenWidth  = 250;
const int screenHeight = 250;
...
triangleRaster(Vec2i(10,10), Vec2i(100, 30), Vec2i(190, 160),image,red);

你可以在下面的链接中找到当前项目的代码：链接🔗。

2.2 平面着色Flat shading render

在「1.2 三维画线」中绘制了模型的线框，即空三角形模型。在「2.1 三角形光栅化」中，介绍了两种方法绘制一个“实心”的三角形。现在，我们将使用“平面着色”来渲染小人模型，其中平面着色使用随机的RGB数值。

第一关：回顾

首先将加载模型的相关代码准备好：

#include <vector>
#include <cmath>
#include "tgaimage.h"
#include "geometry.h"
#include "model.h"

...
Model *model = NULL;
const int screenWidth  = 800;
const int screenHeight = 800;
...

// 光栅化三角形的代码
void triangleRaster(Vec2i v0, Vec2i v1, Vec2i v2, TGAImage &image, TGAColor color){
    ...
}

int main(int argc, char** argv) {
    const float halfWidth = screenWidth / 2.0f;
    const float halfHeight = screenHeight / 2.0f;
    TGAImage image(screenWidth, screenHeight, TGAImage::RGB);
    model = new Model("../object/african_head.obj");

    ...// 在此处编写接下来的代码

    image.flip_vertically();
    image.write_tga_file("output.tga");
    delete model;
    return 0;
}

第二关：绘制随机的颜色

下面是遍历获得模型的每一个需要绘制的三角形的代码：

for (int i=0; i<model->nfaces(); i++) { 
    std::vector<int> face = model->face(i); 
    ...
}

当我们获得了所有的面，在每一趟遍历中，将face的三个点取出来并转换到屏幕坐标上，最后传给三角形光栅化函数：

for (int j=0; j<3; j++) {
    Vec3f world_coords = model->vert(face[j]); 
    screen_coords[j] = Vec2i((world_coords.x+1.)*width/2., (world_coords.y+1.)*height/2.); 
}
triangleRaster(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(rand()%255, rand()%255, rand()%255, 255));

第三关：根据光线传播绘制颜色

刚才的随机颜色远远满足不了我们，现在我们根据光线与三角形的法线方向绘制不同的灰度。什么意思呢？看下面这张图，当物体表面的法线方向与光线方向垂直，物体接受到了最多的光；随着法线与光线方向的夹角越来越大，收到光的照射也会越来越少。当法线与光线方向垂直的时候，表面就接收不到光线了。

将这个特性添加到光栅化渲染器中。

Vec3f light_dir(0,0,-1); // define light_dir

for (int i=0; i<model->nfaces(); i++) { 
    std::vector<int> face = model->face(i); 
    Vec2i screen_coords[3]; 
    Vec3f world_coords[3]; 
    for (int j=0; j<3; j++) { 
        Vec3f v = model->vert(face[j]); 
        screen_coords[j] = Vec2i((v.x+1.)*width/2., (v.y+1.)*height/2.); 
        world_coords[j]  = v; 
    } 
    Vec3f n = (world_coords[2]-world_coords[0])^(world_coords[1]-world_coords[0]); 
    n.normalize(); 
    float intensity = n*light_dir; 
    if (intensity>0) { 
        triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(intensity*255, intensity*255, intensity*255, 255)); 
    } 
}

上面代码需要注意的点：

• 三角形法线n的计算

• 判断点积正负

intensity小于等于0的意思是这个面（三角形）背对着光线，摄像机肯定看不到，不需要绘制。

注意到嘴巴的地方有些问题，本应在嘴唇后面的嘴巴内部区域（像口腔这样的空腔）却被画在嘴唇的上方或前面。这表明我们对不可见三角形的处理方式不够精确或不够规范。“dirty clipping”方法只适用于凸形状。对于凹形状或其他复杂的形状，该方法可能会导致错误。在下一章节中我们使用 z-buffer 解决这个瑕疵（渲染错误）。

这里给出当前步骤的代码链接🔗。

3.1 表面剔除

上一章的末尾我们发现嘴巴部分的渲染出现了错误。本章先介绍画家算法（Painters' Algorithm），随后引出 Z-Buffer ，插值计算出需渲染的像素的深度值。

第一关：画家算法（Painters' Algorithm）

这个算法很直接，将物体按其到观察者的距离排序，然后从远到近的顺序绘制，这样近处的物体自然会覆盖掉远处的物体。

但是仔细想就会发现一个问题，当物体相互阻挡时算法就会出错。也就是说，画家算法无法处理相互重叠的多边形。

第二关：了解z-buffer

如果画家算法行不通，应该怎么解决物体相互重叠的问题呢？我们初始化一张表，长宽与屏幕像素匹配，且每个像素大小初始化为无限远。每一个像素存储一个深度值。当要渲染一个三角形的一个像素时，先比较当前欲渲染的像素位置与表中对应的深度值，如果当前欲渲染的像素深度比较浅，说明欲渲染的像素更靠近屏幕，因此渲染。

而这张表，我们称之为：Z-Buffer。

第三关：创建Z-Buffer

理论上说创建的这个 Z-Buffer 是一个二维的数组，例如：

float **zbuffer = new float*[screenWidth];
for (int i = 0; i < screenWidth; i++) {
    zbuffer[i] = new float[screenHeight];
}
...
// 释放内存
for (int i = 0; i < screenWidth; i++) {
    delete[] zbuffer[i];
}
delete[] zbuffer;

但是，我认为这太丑陋了，不符合我的审美。我的做法是将二维数组打包变成一个一维的数组：

int *zBuffer = new int[screenWidth*screenHeight];

最基本的数据结构，取用的时候只需要：

int idx = x + y*screenWidth;
int x = idx % screenWidth;
int y = idx / screenWidth;

初始化zBuffer可以用一行代码解决，将其全部设置为负无穷：

for (int i=screenWidth*screenHeight; i--; zBuffer[i] = -std::numeric_limits<float>::max());

第四关：整理当前代码

要给当前的triangleRaster()函数新增 Z-Buffer 功能。

我们给pixel增加一个维度用于存储深度值。另外，由于深度是float类型，如果沿用之前的函数可能会出现问题，原因是之前传入的顶点都是经过取舍得到的整数且不包含深度信息。而且需要注意整数坐标下的深度值往往不等于取舍之前的深度值，这个精度的损失带来的问题是在复杂精细且深度值波动很大的位置会出现渲染错误。但是目前可以直接忽略，等到后面进行超采样、抗锯齿或者其他需要考虑像素内部细节的技术时再展开讲解。

因此，为了后期拓展的方便，我们将之前涉及pixel的Vec2i代码换为Vec3f类型，并且每一个点都增加一个维度用于存储深度值。

Vec3f barycentric(Vec3f A, Vec3f B, Vec3f C, Vec3f P) {
    Vec3f s[2];
    for (int i=2; i--; ) {
        s[i][0] = C[i]-A[i];
        s[i][1] = B[i]-A[i];
        s[i][2] = A[i]-P[i];
    }
    Vec3f u = cross(s[0], s[1]);
    if (std::abs(u[2])>1e-2)
        return Vec3f(1.f-(u.x+u.y)/u.z, u.y/u.z, u.x/u.z);
    return Vec3f(-1,1,1);
}
// 重心坐标的方法 - 光栅化三角形
void triangleRaster(Vec3f v0, Vec3f v1, Vec3f v2, float *zBuffer, TGAImage &image, TGAColor color){
    Vec3f* pts[] = {&v0, &v1, &v2};// Pack
    // Find The Bounding Box
    Vec2f boundingBoxMin( std::numeric_limits<float>::max(),  std::numeric_limits<float>::max());
    Vec2f boundingBoxMax(-std::numeric_limits<float>::max(), -std::numeric_limits<float>::max());
    Vec2f clamp(image.get_width()-1, image.get_height()-1);
    for (int i=0; i<3; i++) {
        boundingBoxMin.x = std::max(0.f, std::min(boundingBoxMin.x, pts[i]->x));
        boundingBoxMin.y = std::max(0.f, std::min(boundingBoxMin.y, pts[i]->y));
        boundingBoxMax.x = std::min(clamp.x, std::max(boundingBoxMax.x, pts[i]->x));
        boundingBoxMax.y = std::min(clamp.y, std::max(boundingBoxMax.y, pts[i]->y));
    }

    // For Loop To Iterate Over All Pixels Within The Bounding Box
    Vec3f pixel;// 将深度值打包到pixel的z分量上
    for (pixel.x = boundingBoxMin.x; pixel.x <= boundingBoxMax.x; pixel.x++) {
        for (pixel.y = boundingBoxMin.y; pixel.y <= boundingBoxMax.y; pixel.y++) {
            Vec3f bc = barycentric(v0, v1, v2, pixel);// Screen Space
            if (bc.x<0 || bc.y<0 || bc.z<0 ) continue;
            // HIGHLIGHT: Finished The Z-Buffer
            //image.set(pixel.x, pixel.y, color);
            pixel.z = 0;
            pixel.z = bc.x*v0.z+bc.y+v1.z+bc.z+v2.z;// 通过重心坐标插值计算当前Shading Point的深度值
            if(zBuffer[int(pixel.x+pixel.y*screenWidth)]<pixel.z) {
                zBuffer[int(pixel.x + pixel.y * screenWidth)] = pixel.z;
                image.set(pixel.x, pixel.y,color);
            }
        }
    }
}

将世界坐标转化到屏幕坐标的函数打包：

Vec3f world2screen(Vec3f v) {
    return Vec3f(int((v.x+1.)*width/2.+.5), int((v.y+1.)*height/2.+.5), v.z);
}

另外，对tgaimage、model和geometry做了一些修改，主要是优化了一些细节。具体项目请查看当前项目分支链接🔗。

3.2 上贴图

啥是贴图呢？就是类似这种奇奇怪怪的图片。

目前我们已经完成了三角形的重心坐标插值得出了三角形内某点的深度值。接下来我们还可以用插值操作计算对应的纹理坐标。

本章基于「3.1 表面剔除」最后的项目完善，本章主要是c++ STL相关操作。

第一关：思路

请首先下载「3.1 表面剔除」最后的项目链接🔗。

首先从硬盘中加载纹理贴图，然后传到三角形顶点处，通过对应的纹理坐标从texture获取颜色，最后插值得到各个像素的颜色。

另外，项目框架的代办清单：

1. 增加model模块中对vt标签的解析

2. 完善model模块中对f标签的解析，具体是获取纹理坐标索引

3. 完善geometry模块的操作符，具体是实现Vec<Dom, f>与float相乘等操作

第二关：加载纹理文件

从硬盘中加载纹理texture，用TGAImage存储。

TGAImage texture;
if(texture.read_tga_file("../object/african_head_diffuse.tga")){
    std::cout << "Image successfully loaded!" << std::endl;
    // 可以做一些图像处理
} else {
    std::cerr << "Error loading the image." << std::endl;
}

第三关：获取纹理坐标

在 model.h 中，在class Model上方创建一个Face结构体用于存储解析后obj中的f标签。f标签有三个值，这里只存储前两个。f标签的三个值分别是顶点索引/纹理索引/法线索引，等后面用到了法线坐标再拓展即可。

struct Face {
    std::vector<int> vertexIndices;
    std::vector<int> texcoordIndices;
    ...
};

然后将model的模版私有属性：

std::vector< std::vector<int> > faces_;

改为：

std::vector<Face> faces_;

同时也修改 model.cpp 下获取 face 的函数：

Face Model::face(int idx) {
    return faces_[idx];
}

实际解析时的函数：

else if (!line.compare(0, 2, "f ")) {
//            std::vector<int> f;
//            int itrash, idx;
//            iss >> trash;
//            while (iss >> idx >> trash >> itrash >> trash >> itrash) {
//                idx--; // in wavefront obj all indices start at 1, not zero
//                f.push_back(idx);
//            }
//            faces_.push_back(f);
            Face face;
            int itrash, idx, texIdx;
            iss >> trash;
            while (iss >> idx >> trash >> texIdx >> trash >> itrash) {
                idx--; // in wavefront obj all indices start at 1, not zero
                texIdx--; // similarly for texture indices
                face.vertexIndices.push_back(idx);
                face.texcoordIndices.push_back(texIdx);
            }
            faces_.push_back(face);
        }

接下来解析纹理坐标索引texcoords_。

// model.h
...
class Model {
private:
    ...
    std::vector<Vec2f> texcoords_;
public:
    ...
    Vec2f& getTexCoord(int index);
};
...

// model.cpp
...
Model::Model(const char *filename) : verts_(), faces_(), texcoords_(){
    ...
        else if (!line.compare(0, 3, "vt ")) {
            iss >> trash >> trash;
            Vec2f tc;
            for (int i = 0; i < 2; i++) iss >> tc[i];
            texcoords_.push_back(tc);
        }
    ...
}
...    
Vec2f& Model::getTexCoord(int index) {
    return texcoords_[index];
}

最后就可以通过对应的索引得到纹理坐标了。

tex_coords[j] = model->getTexCoord(face.texcoordIndices[j]);

第四关：通过纹理坐标uv获取对应颜色

获得了纹理坐标后就可以用texture.get(x_pos, y_pos)获取图片（贴图/纹理）的对应像素。注意最后TGAColor使用的是BGRA通道，而不是RGBA通道。

TGAColor getTextureColor(TGAImage &texture, float u, float v) {
    // 纹理坐标限制在(0, 1)
    u = std::max(0.0f, std::min(1.0f, u));
    v = std::max(0.0f, std::min(1.0f, v));
    // 将u, v坐标乘以纹理的宽度和高度，以获取纹理中的像素位置
    int x = u * texture.get_width();
    int y = v * texture.get_height();
    // 从纹理中获取颜色
    TGAColor color = texture.get(x, y);
    // tga使用的是BGRA通道
    return TGAColor(color[2],color[1],color[0], 255);
}

第五关：在光栅化三角形函数中增加贴贴图的功能

增加了四个传参，分别是三个三角形的纹理坐标与纹理。实现细节直接看代码比较直接。

// 带贴图 - 光栅化三角形
void triangleRasterWithTexture(Vec3f v0, Vec3f v1, Vec3f v2,
                               Vec2f vt0, Vec2f vt1, Vec2f vt2,// 纹理贴图
                               float *zBuffer, TGAImage &image,
                               TGAImage &texture){
    ...
    // Find The Bounding Box
    ...

    // For Loop To Iterate Over All Pixels Within The Bounding Box
    Vec3f pixel;// 将深度值打包到pixel的z分量上
    for (pixel.x = boundingBoxMin.x; pixel.x <= boundingBoxMax.x; pixel.x++) {
        for (pixel.y = boundingBoxMin.y; pixel.y <= boundingBoxMax.y; pixel.y++) {
            Vec3f bc = barycentric(v0, v1, v2, pixel);// Screen Space
            if (bc.x<0 || bc.y<0 || bc.z<0 ) continue;
            // HIGHLIGHT: Finished The Z-Buffer
            pixel.z = 0;
            pixel.z = bc.x*v0.z+bc.y+v1.z+bc.z*v2.z;
            Vec2f uv = bc.x*vt0+bc.y*vt1+bc.z*vt2;
            if(zBuffer[int(pixel.x+pixel.y*screenWidth)]<pixel.z) {
                zBuffer[int(pixel.x + pixel.y * screenWidth)] = pixel.z;
                image.set(pixel.x, pixel.y,getTextureColor(texture, uv.x, 1-uv.y));
            }
        }
    }
}

在上面的代码中，你可能会发现乘号竟然报错了，这个问题在下一关马上得到解决。最终在 main() 函数中这样调用：

// main.cpp
...
for (int i=0; i<model->nfaces(); i++) {
    Face face = model->face(i);
    Vec3f screen_coords[3], world_coords[3];
    Vec2f tex_coords[3];
    for (int j=0; j<3; j++) {
        world_coords[j]  = model->vert(face.vertexIndices[j]);
        screen_coords[j] = world2screen(world_coords[j]);
        tex_coords[j] = model->getTexCoord(face.texcoordIndices[j]);
    }
    triangleRasterWithTexture(screen_coords[0], screen_coords[1], screen_coords[2],
                              tex_coords[0],tex_coords[1],tex_coords[2],
                              zBuffer, image, texture);
}
...

第六关：为模板函数添加更多重载符号操作

在写纹理坐标的时候，我们会用到一些操作比如说 Vec2i 类型与 float 浮点数相乘和相除。将下面的代码添加到 geometry.h 的中间部分：

...

template <typename T> vec<3,T> cross(vec<3,T> v1, vec<3,T> v2) {
    return vec<3,T>(v1.y*v2.z - v1.z*v2.y, v1.z*v2.x - v1.x*v2.z, v1.x*v2.y - v1.y*v2.x);
}

// -------------添加内容-------------
template<size_t DIM, typename T> vec<DIM, T> operator*(const T& scalar, const vec<DIM, T>& v) {
    vec<DIM, T> result;
    for (size_t i = 0; i < DIM; i++) {
        result[i] = scalar * v[i];
    }
    return result;
}

template<size_t DIM, typename T> vec<DIM, T> operator*(const vec<DIM, T>& v, const T& scalar) {
    vec<DIM, T> result;
    for (size_t i = 0; i < DIM; i++) {
        result[i] = v[i] * scalar;
    }
    return result;
}

template<size_t DIM, typename T> vec<DIM, T> operator/(const vec<DIM, T>& v, const T& scalar) {
    vec<DIM, T> result;
    for (size_t i = 0; i < DIM; i++) {
        result[i] = v[i] / scalar;
    }
    return result;
}

// -------------添加内容结束-------------

template <size_t DIM, typename T> std::ostream& operator<<(std::ostream& out, vec<DIM,T>& v) {
    for(unsigned int i=0; i<DIM; i++) {
        out << v[i] << " " ;
    }
    return out ;
}

...

这样就完全没问题了，大功告成。当然你也可以在这个链接🔗中找到完整的代码。

4.1 透视视角

上文的内容全部都是正交视角下的渲染，这显然算不上酷，因为我们仅仅是将z轴“拍扁”了。这一章节的目标是学习绘制透视视角。

https://stackoverflow.com/questions/36573283/from-perspective-picture-to-orthographic-picture

第一关：线性变换

缩放可以表示为：

$$\operatorname{scale}\left(s_x, s_y\right)=\left[\begin{array}{cc} s_x & 0 \\ 0 & s_y \end{array}\right] .$$

拉伸可以表示为：

$$\operatorname{shear-x}(s)=\left[\begin{array}{} 1 & s \\ 0 & 1 \end{array}\right] , \operatorname{shear-y}(s)=\left[\begin{array}{} 1 & 0 \\ s & 1 \end{array}\right]$$

旋转可以表示为：

$$\mathbf{R}_\theta=\left[\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]$$

第二关：齐次坐标 Homogeneous coordinates

为什么要引入齐次坐标呢？因为想要表示一个二维变换的平移并不能仅仅使用一个2x2的矩阵。平移并不在这个二维矩阵的线性空间中。因此，我们拓展一个维度帮助我们表示平移。

在计算机图形学中我们使用齐次坐标（Homogeneous Coord）。比如说一个二维的$(x, y)$使用平移矩阵变换到$(x', y')$：

$$\left(\begin{array}{c} x^{\prime} \\ y^{\prime} \\ w^{\prime} \end{array}\right)=\left(\begin{array}{ccc} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{array}\right) \cdot\left(\begin{array}{l} x \\ y \\ 1 \end{array}\right)=\left(\begin{array}{c} x+t_x \\ y+t_y \\ 1 \end{array}\right)$$