[笔记]从0开始搓一个简单的render

Posted on 2022-04-30 Edited on 2022-06-30 In 图形学

本文的主要内容是对Dmitry V. Sokolov的tinyrender课程的记录和补充.

Step 0：环境搭建

我们需要tgaimage.h来操作TGA文件, model.h来操作模型. 头文件和实现可以在这里找到:

https://github.com/ssloy/tinyrenderer/tree/f6fecb7ad493264ecd15e230411bfb1cca539a12

可以用如下代码来测试:

#include "tgaimage.h"
const TGAColor white = TGAColor(255, 255, 255, 255);
const TGAColor red   = TGAColor(255, 0,   0,   255);
int main(int argc, char** argv) {
        TGAImage image(100, 100, TGAImage::RGB);
        image.set(52, 41, red);
        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;
}

得到一个有红点的TGA文件:

Step 1：画一条直线

朴素算法

我们需要在二维位图上画一条从\((x_0,y_0)\)到\((x_1,y_1)\)的直线.

直线的两点式为: \[ \frac{y - y_0}{y_1 - y_0} = \frac{x - x_0}{x_1 - x_0} \] 因而对任一点\(x\), 有 \[ y = \frac{x - x_0}{x_1 - x_0} \cdot(y_1 - y_0) + y_0 \] 我们只要枚举\(x\), 计算出每个\(x\)对应的\(y\)即可画出直线. 需要注意的是, 这个算法默认\((x_1,y_1)\)在\((x_0,y_0)\)的右上方, 并且绘制时需要枚举\(\Delta x,\Delta y\)中较大的一方以保证线段不会断开.

代码如下:

void Drawer::Line(int x0, int y0, int x1, int y1, TGAColor color) {
    bool flip = 0;
    if(abs(x0 - x1) < abs(y0 - y1)){
        flip = 1;
        std::swap(x0,y0),std::swap(x1,y1);
    }
    if(x0 > x1){
        std::swap(x0,x1),std::swap(y0,y1);
    }
    for(int x = x0;x <= x1;x++){
        double t = (double)(x - x0)/(x1 - x0);
        int y = t * (y1 - y0) + y0;
        if(!flip)set(x,y,color);
        else set(y,x,color);
    }
}

Bresenham直线算法

朴素算法已经能够满足绘图需要, 但是使用了浮点乘法除法, 效率很低.

我们设直线的斜率\(k = \frac{y_1 - y_0}{x_1 - x_0}\), 有 \[ y = (x - x_0) \cdot k + y_0 \] 我们假设当前画笔所在位置的是\((x,y_c)\), 误差为\(E = y- y_c\). 当\(x\)加\(1\)时, \(E\)增加\(k\). 当\(E \ge \frac{1}{2}\)时, 我们需要将\(y_c\)加或减\(1\)同时\(E\)减去\(1\). 这样便避免了每次都要进行的浮点除法运算.

具体来说, 我们只需将不等式的两边乘上\(2 \cdot (x_1 - x_0)\)即可. 此时误差每次增加\(2 \cdot (y_1 - y_0)\). 当\(E \ge (x_1 - x_0)\)时需要将\(y_c\)加或减\(1\)同时\(E\)减去\(2 \cdot (x_1 - x_0)\).

void Drawer::Line(int x0, int y0, int x1, int y1, TGAColor color) {
    bool flip = 0;
    if(abs(x0 - x1) < abs(y0 - y1)){
        flip = 1;
        std::swap(x0,y0),std::swap(x1,y1);
    }
    if(x0 > x1){
        std::swap(x0,x1),std::swap(y0,y1);
    }
    int dx = x1 - x0,dy = y1 - y0;
    int e = 0,de = 2*abs(dy);
    int y = y0;
    for(int x = x0;x <= x1;x++){
        e += de;
        if(e >= dx) {
            e -= dx*2;
            y += (dy > 0?1:-1);
        }
        if(!flip)set(x,y,color);
        else set(y,x,color);
    }
}

Step 2：画一个三角形

扫描线法

我们先用一种十分古老的方法来画一个三角形: 用水平或者竖直的线一行一行地绘制.

在绘制前, 先对三角形的三个顶点按横坐标递增进行排序, 然后标号为\(P_0,P_1,P_2\)(以下默认左下角为坐标原点). 同时将边\(P_0P_1\)标为\(L_0\), \(P_1P_2\)标为\(L_1\), \(P_2P_3\)标为\(L_2\), 如图:

标号后的三角形可按\(x = x_1\)这条直线分割成两部分. 对两部分分别进行绘制即可. 注意处理一下斜率不存在时的细节.

void Drawer::Triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAColor color) {
    int x0,y0,x1,y1,x2,y2;
    std::vector<std::pair<int,int> >top = {{t0.u,t0.v},{t1.u,t1.v},{t2.u,t2.v}};
    std::sort(top.begin(),top.end());
    std::tie(x0,y0) = top[0];
    std::tie(x1,y1) = top[1];
    std::tie(x2,y2) = top[2];
    int mx = std::max(x1,x2);
    double k0 = (double)(y1 - y0)/(x1 == x0?1:x1 - x0);
    double k1 = (double)(y2 - y1)/(x2 == x1?1:x2 - x1);
    double k2 = (double)(y2 - y0)/(x2 == x0?1:x2 - x0);
    for(int x = x0;x <= x2;x++){
        int yc2 = (x - x0) * k2 + y0;
        if(x <= x1){
            int yc0 = (x - x0) * k0 + y0;
            Line(x,yc0,x,yc2,color);
        }
        else{
            int yc1 = (x - x1) * k1 + y1;
            Line(x,yc1,x,yc2,color);
        }
    }
}

重心坐标系

一般定义

设\(V_1,...,V_n\)是\(n\)维向量空间\(V\)中单纯形的顶点, 对于\(V\)中任意一点\(P\), 有 \[ (\sum_{i = 1}^n \lambda_i)\cdot P = \sum_{i = 1}^n \lambda_i \cdot V_i \] 则系数\(\lambda_1,...,\lambda_n\)称为\(P\)关于\(V_1,...V_n\)的重心坐标. 一般规定\(\sum_{i = 1}^n \lambda_i = 1\), 此时称为正规化的重心坐标. 以下讨论的重心坐标均为正规化的.

二维平面中的重心坐标系

定义

二维平面上, 单纯形为三角形. 假设给出一三角形\(\Delta ABC\)和三角形所在平面上的一点\(P\), 则\(P\)可被如下重心坐标表示: \[ P = \alpha A + \beta B + \gamma C \] 考虑下图(来源见链接):

将\(\vec{AB},\vec{AC}\)作为坐标系, 可以得到 \[ \begin{align} P =& A + \beta(\vec{AB}) + \gamma(\vec{AC})\\ =& A + \beta(B - A) + \gamma(C - A)\\ =& (1 - \beta - \gamma)A + \beta B + \gamma C \end{align} \] 这样便可以从坐标系的角度来解释重心坐标, 同时能得到 \[ \alpha = 1 - \beta - \gamma \]

求解:解方程组

将点带入重心坐标的定义, 可以得到: \[ \left \{ \begin{array}{cccc} x_p = (1 - \beta - \gamma) x_a + \beta x_b + \gamma x_c \\ y_p = (1 - \beta - \gamma) y_a + \beta y_b + \gamma y_c \end{array} \right. \] 提取出\(\beta \space \gamma\): \[ \left \{ \begin{array}{cccc} x_p - x_a = \beta(x_b - x_a) + \gamma (x_c - x_a)\\ y_p - y_a = \beta(y_b - y_a) + \gamma (y_c - y_a) \end{array} \right. \] 转化为矩阵形式: \[ \left[ \begin{array}{} x_b - x_a & x_c - x_a\\ y_b - y_a & y_c - y_a \end{array} \right] \left[ \begin{array}{} \beta \\ \gamma \end{array} \right] = \left[ \begin{array}{} x_p - x_a\\ y_p - y_a \end{array} \right] \] 这样便可求解出\(\beta \space \gamma\)进而求出\(\alpha\)

求解:向量叉积

把坐标系的表达式变换一下: \[ \beta \vec{AB} + \gamma \vec{AC} + \vec{PA} = 0 \] 拆开后: \[ \left \{ \begin{array}{cccc} \beta\vec{AB}_x + \gamma \vec{AC}_x + \vec{PA}_x = 0\\ \beta\vec{AB}_y + \gamma \vec{AC}_y + \vec{PA}_y = 0 \end{array} \right. \] 转化为矩阵形式: \[ \left[ \begin{array}{} \beta & \gamma & 1 \end{array} \right] \left[ \begin{array}{} \vec{AB}_x\\ \vec{AC}_x\\ \vec{PA}_x \end{array} \right] = 0\\ \left[ \begin{array}{} \beta & \gamma & 1 \end{array} \right] \left[ \begin{array}{} \vec{AB}_y\\ \vec{AC}_y\\ \vec{PA}_y \end{array} \right] = 0\\ \] 从几何意义考虑, 这相当于\([\beta ,\gamma,1]\)这个向量和后两个向量分别垂直. 因而我们求出后两个向量的叉积(假设结果为\([x,y,z]\)), 则\([\frac{x}{z}, \frac{y}{z},1]\)等于\([\beta,\gamma,1]\).

需要注意\(z = 0\)的特殊情况, 根据叉乘的定义, 此时有\(\vec{AB}_x \cdot \vec{AC}_y - \vec{AB}_y \cdot \vec{AC}_x = 0\), 即\(\vec{AB} \cdot \vec{AC} = 0\), 说明\(ABC\)三点共线. 这时返回一个任意的负重心坐标即可.

求解:三角形面积

如图, 假设三角形面积分别为\(S_A,S_B,S_C\). 则 \[ \alpha = \frac{S_A}{S_A+S_B+S_C}\\ \beta = \frac{S_B}{S_A+S_B+S_C}\\ \gamma = \frac{S_C}{S_A+S_B+S_C} \]

应用

重心坐标有很多应用, 在这里我们能用到的结论是: 若\(\alpha,\beta,\gamma\)均大于\(0\), 则点\(P\)在三角形\(\Delta ABC\)的内部; 若\(\alpha,\beta,\gamma\)有一个等于\(0\), 则点\(P\)在三角形的边上; 若\(\alpha,\beta,\gamma\)有两个等于\(0\), 则点\(P\)在三角形的顶点上.

在绘图时, 用一个最小的矩形包围住三角形, 再枚举并判断每个点是否在三角形内部即可. 下面的代码采用了向量叉积法:

Vec3f Drawer::Barycentric(const Vec2i (&vertex)[3],const Vec2i & P){
    Vec3f result =  //cal cross
            Vec3f(vertex[1].x - vertex[0].x,vertex[2].x - vertex[0].x,vertex[0].x - P.x) ^
            Vec3f(vertex[1].y - vertex[0].y,vertex[2].y - vertex[0].y,vertex[0].y - P.y);
    if(fabs(result.z) < 1)return Vec3f(-1,1,1);
    result.x /= result.z,result.y /= result.z;
    return {(float)1.0 - result.x - result.y,result.x,result.y};
}
void Drawer::Triangle(const Vec2i (&vertex)[3],const TGAColor & color) {
    int lx = std::max(std::min({vertex[0].x,vertex[1].x,vertex[2].x}),0),rx = std::min(std::max({vertex[0].x,vertex[1].x,vertex[2].x}),get_width()-1);
    int ly = std::max(std::min({vertex[0].y,vertex[1].y,vertex[2].y}),0),ry = std::min(std::max({vertex[0].y,vertex[1].y,vertex[2].y,}),get_height()-1);
    for(int x = lx;x <= rx;x++){
        for(int y = ly;y <= ry;y++){
            Vec3f bary = Barycentric(vertex,Vec2i(x,y));
            bool out = (bary.x < 0 or bary.y < 0 or bary.z < 0);
            if(!out)set(x,y,color);
        }
    }
}

使用tinyrender提供的模型来测试一下我们的三角形绘制程序(先给每个面一个随机颜色):

加上一点阴影并剔除背面的三角形:

Step 3 ：z-buffer

现在我们需要考虑剔除掉不能被我们看见的像素(Step 2通过Back-face culling剔除了一些面, 但是仍然不正确, 例如嘴部整个消失了). z-buffer的思想是维护一个像素点在待渲染平面上的一个距离buffer, 每次用离相机更近的点来剔除已经存在的点. z-buffer的实现非常简单, 下面主要讨论如何求每个点距相机的距离.

首先考虑一维的情形. 假设我们要绘制从\(A(x_0,y_0)\)到\(B(x_1,y_1)\)的一条线段, 当前绘制到点\(P(x,y)\), 摄像机的视角与\(y\)轴的反方向相同:

在绘制时我们要通过\(x\)坐标计算出\(y\)来. 不难得到 \[ \frac{y - y_0}{y1 - y_0} = \frac{x - x_0}{x_1 - x_0} \] 我们设\(\beta = \frac{x - x_0}{x_1 - x_0}\), 则有 \[ y = (1 - \beta)y_0 + \beta y_1 \] 是不是很熟悉? \(\alpha = 1 - \beta\)和\(\beta\)就是\(P\)关于线段\(AB\)的重心坐标(一维单纯形是线段). 我们将其推广到二维, 便能求出三角形每个点距离相机的距离\(z\): \[ z = \alpha z_0+ \beta z_1 + \gamma z_2 \]

void Drawer::Triangle(const Vec3i (&vertex)[3],const TGAColor & color,double * zbuffer) {
    const double eps = -1e-6;//防止三角形接合处有未绘制的点
    int lx = std::max(std::min({vertex[0].x,vertex[1].x,vertex[2].x}),0),rx = std::min(std::max({vertex[0].x,vertex[1].x,vertex[2].x}),get_width()-1);
    int ly = std::max(std::min({vertex[0].y,vertex[1].y,vertex[2].y}),0),ry = std::min(std::max({vertex[0].y,vertex[1].y,vertex[2].y,}),get_height()-1);
    for(int x = lx;x <= rx;x++){
        for(int y = ly;y <= ry;y++){
            Vec3f bary = Barycentric(vertex,Vec2i(x,y));
            if(bary.x < eps or bary.y < eps or bary.z < eps)continue;
            int idx = x + y * get_width();
            double z = bary.x * vertex[0].z + bary.y * vertex[1].z + bary.z * vertex[2].z;
            if(zbuffer[idx] < z){
                zbuffer[idx] = z;
                set(x,y,color);
            }
        }
    }
}

效果如下:

Step 4: 透视投影(WIP)

这一部分tinyrender讲得很含糊而且不直观, 所以直接按照GAMES101的内容去实现. 本节只讲述实现. obj文件格式可以在https://en.wikipedia.org/wiki/Wavefront_.obj_file找到.

透视投影的实现似乎有问题, 先鸽了

Step 5:相机

写的不是很满意, 也鸽了