实现OpenGL渲染器原理篇(二)——三角形栅格化和后向面剔除

最近在Github上复现了一个渲染器render的项目：
Github链接：tiny render

我希望在博客上可以记录自己的学习过程，博客主要分为两大类：《原理篇》和《语法篇》。
原理篇则主要讲的是——实现渲染器过程中所需要的算法知识。
语法篇则主要讲的是——实现渲染器过程中使用到的C++的语法知识。

总结一下重点，这样后面的文章就不用看了。

因为通过Bresham直线算法画好各种三角形框架后，接下来要做的就是填充三角形。
填充三角形古老的方法则是line sweeping。原则有：（1）按三角形的y坐标对三角形的顶点进行排序；
（2）同时栅格化三角形的左右两边
（3）在左右边界点之间画一条水平线段
三角形的三条边也是边界。三个顶点按y坐标升序排列。line sweeping是专门为单线程CPU运行而设计的。使用bbox的好处是很容易地检查一个点是否属于2D三角形(或任何凸多边形)。
重心坐标也可以(https://zhuanlan.zhihu.com/p/149836719)，而且可以作为新的光栅化例程。

基于一个给定的三角形，遍历其边界框的所有像素。对于每个像素，都需要计算出这个像素的重心坐标。如果这个像素具有至少一个负分量，那么这个像素点就会出现在三角形的外部。

barycentric()函数计算出了在给定三角形中P点的坐标。

triangle()函数则是第一步，计算了一个边界框，这个边界框由2点来描述，分别是左下角的点和右上角的点，这个边框是一个长方形，长方形就会有夹角，为了找到长方形的呢些夹角(corners)，我们遍历三角形的所有顶点，并从中选择最大/最小坐标。
接下来加入了三角形边界框的裁剪，让处在screen外的三角形消失，从而来画一个三角形。

本blog中定义了一个Vec3f变量v，来存储顶点值(vertex)，这个顶点值的用处是赋值给世界坐标变量world_coordinates，然后计算法线向量n。法线向量再和光照方向相乘，得到光强（sin90 = 1, cos90 = 0）。
在相同的光照强度下，与光线方向垂直的多边形被照得最亮，多边形与光矢量平行，则光照为零。（因为多边形的法线和光线平行，然后光照是光矢量和法线的点积，也就是cos0 = 1）
三角形的法向量可以简单地计算为它两边的外积。

内积

外积

如果多边形与光矢量平行，则光照为零。

一、填充三角形 Filling triangles

model

上次我们绘制了三维模型的丝网(wire mesh)。
这次，我们将填充多边形或三角形。

事实上，OpenGL几乎对任何多边形都进行了三角剖分，因此无需考虑复杂的情况。

二、老旧的方法：line sweeping

大家好，今天我们的任务是画一些2维的三角形。
这次任务的重点是画好一个填充的三角形。

大家的代码可能一开始是这样的：

void triangle (Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) 
{
    line (t0, t1, image, color);
    line (t1, t2, image, color);
    line (t2, t0, image, color);
}

//...

Vec2i t0[3] = {Vec2i(10, 20), Vec2i(20, 50), Vec2i(70, 100)};
Vec2i t1[3] = {Vec2i(88, 99), Vec2i(78, 99), Vec2i(77, 123)};
Vec2i t2[3] = {Vec2i(45, 65), Vec2i(32, 20), Vec2i(99, 66)};

//调用上面写的triangle函数
triangle(t0[0], t0[1], t0[2], image, green);
triangle(t1[0], t1[1], t1[2], image, red);
triangle(t2[0], t2[1], t2[2], image, blue);
//为啥t0一行，t1一行，t2一行。。。

上述代码得到的结果如下：

画了3个三角形

代码中的疑问：Vec2i(10, 70)中的10和70对应的是ctor中的u和v，Vec2这个struct中定义了x和y，但是ctor中没有x和y相关的。

所以不知道u、v和x、y有什么关系？可以等价吗？

上面的代码做了改变，但是很简单，为代码的初始调试提供了三个三角形。
当我们在triangle()这个function中调用line()这个函数的时候，我们将会得到三角形的轮廓。

那么，如何画一个填充好的三角形呢？准则如下：

对称性：图片不应该依赖于传递给绘图函数的顶点的顺序
如果两个三角形有两个公共顶点，由于四舍五入的栅格化，它们之间应该没有孔洞。
通常，使用Line Sweeping要注意：
- 按三角形的y坐标对三角形的顶点进行排序
- 同时栅格化三角形的左右两边
- 在左右边界点之间画一条水平线段

不过学到这里，有点疑问：哪个线段是左段，哪个线段是右段？此外，三角形中有三个线段。

那么好，介绍完了 line sweeping 的步骤，我们可以开始工作了——

大家可以假设你们有三角形的三个点：t0, t1, t2。这三个点按y坐标升序排列，

然后，边界A在t0和t2之间，边界B既在t0和t1之间, 然后也在t1和t2之间。

t0到t1, t1到t2是绿色的，t2到t0是红色的

上图中，边界A(t2->t0)是红色的，边界B(t0->t1, t1->t2)是绿色的。
生成上图的代码如下：

void triangle (Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color)
{
    //对3个顶点排序，t0 t1 t2从下到上，也就是冒泡排序
    if (t0.y > t1.y)
        std::swap(t0, t1);
    if (t0.y > t2.y)
        std::swap(t0, t2);
    if (t1.y > t2.y)
        std::swap(t1, t2);
    
    line (t0, t1, image, color);
    line (t1, t2, image, color);
    line (t2, t0, image, color);
    
    //上面的line写错了
    line (t0, t1, image, green);
    line (t1, t2, image, green);
    line (t2, t0, image, red);
}

大家看上面的图可以发现一个小问题：边界B是由两部分组成的。
让我们通过水平切割来绘制三角形的下半部分。

void triangle (Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color)
{
    if (t0.y > t1.y)
        std::swap(t0, t1);
    if (t0.y > t2.y)
        std::swap(t0, t2);
    if (t1.y > t2.y)
        std::swap(t1, t2);
    
    int total_height = t2.y - t0.y;
    
    for (int y = t0.y; y <= t1.y; y++)
    {
        int segment_height = t1.y - t0.y;//why this line code 放在了for loop里面
        
        float alpha = float(y - t0.y) / total_height;
        float beta = float(y - t0.y) / segment_height;
        
        Vec2i A = t0 + (t2 - t0) * alpha;
        Vec2i B = t0 + (t1 - t0) * beta;
        
        image.set(A.x, y, red);
        image.set(B.x, y, green);
    }
}

// 行14的code写错了，应该是 int segment_height = t1.y - t0.y + 1;
// t1 - t0 后要 加1 的目的 是防止 行17的分母为0
// 行16 17 等式 右边 的 float 应该带上括号，(float)

代码中的注意点：

计算出total_height，segment_height(注意segment_height加1是为了不等于0)。

枚举y，初值为t0.y，终值为t1.y。

通过total_height和segment_height，计算一个 $\alpha$ 和 $\beta$ 。再通过 $\alpha$ 和 $\beta$ ，根据点t0和t2或t1的关系，画出边界A和B(A和B是类Vec2i的对象)。

大家注意一下：线段是不连续的。

上次，大家画直线的时候，大家都努力地获得连续的线段。

在这里，大家不需要为旋转图像而烦恼，之前是怎么做的呢？——交换xy。

这次为什么不用考虑这个了呢？

因为后面大家要做的是填充三角形。

如果我们通过水平线连接对应的点对，那么不连续的裂缝将会自动消失。

像下面这样：(这个文档中没有代码，所以用了教程中的图)

没有gap的三角形

接下来，大家继续画三角形的第二部分，也就是三角形的上半部分。

实现这个可以通过再增加一个loop来完成——

void triangle (Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor, color)
{
    if (t0.y > t1.y) 
        std::swap(t0, t1);
    if (t0.y > t2.y)
        std::swap(t0, t2);
    if (t1.y > t2.y)
        std::swap(t1, t2);
    
    // int total_height = t2.y -t1.y;
    int total_height = t2.y - t0.y;
    
    for (int y = t0.y; y <= t1.y; y++)
    {
        int segment_height = t1.y - t0.y + 1;
        
        float alpha = (float) (y - t0.y) / total_height;
        float beta = (float) (y - t0.y) / segment_height;
        //没太懂定义这俩希腊字母的目的是啥
        
        Vec2i A = t0 + (t2 - t0) * alpha;
        Vec2i B = t0 + (t1 - t0) * beta;
        
        if (A.x > B.x)
            std::swap(A, B);
        for (int j = A.x; j <= B.x; j++)
        {
            image.set(j, y, color);
        }
    }
    
    for (int y = t1.y; y <= t2.y; y++)
    {
        int segment_height = t2.y - t1.y + 1;
        
        // float alpha = (float) (y - t1.y) / total_height;
        //// total_height应该永远是从t0开始算起的
        float alpha = (float) (y - t0.y) / total_height;
        float beta = (float) (y - t1.y) / segment_height;
        
        // Vec2i A = t1 + alpha * (t2.y - t1.y);
        Vec2i A = t0 + alpha * (t2 - t0);
        //// (t2 - t0) 具体是个什么值？？上面都是(t2.y - t1.y)这种
        // Vec2i B = t1 + beta * (t2.y - t1.y);
        Vec2i B = t1 + beta * (t2 - t1);
        
        if (A.x > B.x)
            std::swap(A, B);
        for (int j = A.x; j <= B.x; j++)
        {
            image.set(j, y, color);
        }
    }
}

代码的内容添加：

如果A.x比B.x大，交换A和B。

三角形上半部分和下半部分的划分是通过y来划分的。
然后在两个枚举y的循环中，再嵌套一个枚举A.x到B.x的循环。

效果图如下：

填充后的三角形

到了这里，大家也许已经满足了，但是为了让日后提高代码性能时更加方便且可维护更强，并且在画三角形的上半部分时，不再采用同样的代码，将code更改如下：

void triangle (Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color)
{
    if (t0.y == t1.y && t0.y == t2.y)
        return;
    
    if (t0.y > t1.y)
        std::swap(t0, t1);
    if (t0.y > t2.y)
        std::swap(t0, t2);
    if (t1.y > t2.y)
        std::swap(t1, t2);
    
    int total_height = t2.y - t0.y;
    
    for (int i = 0; i < total_height; i++)
    {
        bool second_half = i > (t1.y - t0.y) || t1.y == t0.y;
        
        int segment_height = second_half ? (t2.y - t1.y) : (t1.y - t0.y);
        
        float alpha = (float) i / total_height;
        float beta = (float) (i - (second_half ? (t1.y - t0.y) : 0)) / segment_height;
        
        Vec2i A = t0 + (t2 - t0) * alpha;
        Vec2i B = second_half ? t1 + (t2 - t1) * beta : t0 + (t1 - t0) * beta;
        
        if (A.x > B.x)
            std::swap(A, B);
        for (int j = A.x; j <= B.x; j++)
        {
            image.set(j, y, color);
        }
    }
}

上述代码的核心(也可以说是填充三角形的核心)有以下几点——

定义了一个下标i，i的意义表示的是y坐标上的高度差。

定义了一个bool型变量，second_half，它来根据i到了哪个阶段，是第一阶段(t0.y_{t1.y)还是第二阶段(t1.y}t2.y)。

定义了2个系数 $\alpha$ 和 $\beta$ ，其中——
$\alpha$ 为计算totalheight时候的系数，也就是向量A；
$\beta$ 为计算segmentheight时候的系数，也就是向量B，向量B是由2部分组成的，是绿色的，向量A则是1部分组成，是红色的。忘记了可以看下图——

t0到t1, t1到t2是绿色的，t2到t0是红色的

因为i表示的是y坐标的高度差，所以在最后画图的时候，当遍历x坐标的时候，要将i放进set()函数中进行绘制(外层循环y坐标，内层嵌套循环x坐标，一步一步地来绘图)。代码如下：

for (int i = 0; i < total_height; i++)
{
   ...
   for (int j = A.x; j <= B.x; j++)
       {
           image.set(j, t0.y + i, color);
       }
}

三、新颖的方法

好，到了这里，大家可以看到，上述的实现并不复杂，但是关于Line Sweeping的源码有些凌乱。
并且这个设计方法是专门为单线程CPU运行而设计的。为了解决这个矛盾，先来看看下面这段伪码。

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);
        }
    }
}

上述伪码的核心是：

通过3个点，和一个寻找边框的函数find_bounding_box()来找到一个边框bbox。这个边框被定义成了一个一维数组表示的向量，bbox是vec2类型的。

遍历边框向量中的每一个像素，然后不断地往形参points中放置像素。

上述伪码的优点是很容易可以找到边界框，因此，使用这段code，可以很容易地检查一个点是否属于2D三角形(或任何凸多边形)。

可以说，上述代码我们是在绘画像素(painting pixel)。

第二个优点是：数千个线程的大规模的并行计算改变了人们的思维方式。

好，大家可以开始了：首先大家需要明白什么是重心坐标。

考虑一个2D三角形的3个顶点ABC和一点P(均使用笛卡尔坐标(xy))。
大家的目标是找到点P相对于三角形ABC的重心坐标，
这意味着我们要寻找到三个数字(1-u-v, u, v)，通过这三个数字，这样大家可以找到的点P如下：
$p = (1-u-v)A + uB + vC$
公式1咋一看有点吓人，其实很简单哈：
想象一下，大家可以分别在顶点ABC上，放置三个权重(1-u-v, u, v)，那么整个系统的重心正好在点P上。

大家则可以这样理解——点P在(斜)基底( $A$ , $\vec{AB}$ , $\vec{AC}$ )上有坐标( $u$ , $v$ )。
$p = A + u\vec{AB}+v\vec{AC}$
所以，经过公式2，大家就可以得到向量 $\vec{AB}, \vec{AC}, and, \vec{AP}$ 。
接下来，大家需要找到两个实数u和v，这两个实数遵守以下约束条件：
$u\vec{AB} + v\vec{AC} + \vec{PA} = \vec{0}$
公式3是一个简单的矢量方程，或者说是一个线性系统，这个系统由两个方程组成，这两个方程组则由两个变量(x和y)组成：

线性系统

如果大家不想解线性系统，可以将公式4写成矩阵形式(也是分成了x和y)：

矩阵形式

基于上图的模型，这意味着大家在——
寻找一个与 $(ABx, ACx, PAx)和(ABy, ACy, PAy)$ 同时正交的向量 $(u, v, 1)$ ！

这里给大家一个小的提示，这个是矢量积：

在平面上找到两条直线的交点（这正是我们在这里所做的），通过这个交点，计算出一个cross product(叉积、矢量积)是足够的。

顺便提一下，考考大家：通过两个给定的点，如何找到一个直线方程？

因此，让我们对新的光栅化例程进行编程——
基于一个给定的三角形，遍历其边界框的所有像素。

对于每个像素，大家都需要计算出这个像素的重心坐标。

如果这个像素具有至少一个负分量，那么这个像素点就会出现在三角形的外部。

好，为了大家更加清晰的了解，直接看程序吧：

#include <vector>
#include <iostream>
#include "geometry.h"
#include "tgaimage.h"

const int width = 200;
const int height = 200;

Vec3f barycentric (Vec2i *pts, Vec2i P)  // 在一个给定的三角形中计算P点的坐标
{
    Vec3f u = cross(Vec3f(pts[2][0] - pts[0][0], pts[1][0] - pts[0][0], pts[0][0] - P[0]), Vec3f(pts[2][1] - pts[0][1], pts[1][1] - pts[0][1], pts[0][1] - P[1]));
    // 大家需要注意一点的是，pts 和 P 作为坐标都具有整数值。
    
    if (std::abs(u[2]) < 1)
        return Vec3f(-1, 1, 1);
    // abs(u[2]) < 1 意味着 u[2] = 0，也就是说三角形没有成功生成
    // 因此，返回值需要返回一个负坐标
    
    return Vec3f(1.f - (u.x + u.y) / u.z, u.y / u.z, u.x / u.z);// 1.f是什么啊？
}

void triangle (Vec2i *pts, TGAImage &image, TGAColor color)
    // triangle() 是如何工作的呢？
    // 首先，它计算出了边框值，由两点描述：左下和右上.
    // 为了找到这些角，我们遍历三角形的顶点并选择最小/最大坐标
    // 还添加了一个带有屏幕矩形的边框剪辑，以便为屏幕外部的三角形节省CPU时间。
{
    Vec2i bboxmin(image.get_width() - 1, image.get_height() - 1);
    // 边界值的最小值为什么要减一呢？
    
    Vec2i bboxmax(0, 0);
    Vec2i clamp(image.get_width() - 1, image.get_height() - 1);
    
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            bboxmin[j] = std::max(0,        std::min(bboxmin[j], pts[i][j]));
            bboxmax[j] = std::min(clamp[j], std::max(bboxmax[j], pts[i][j]));
            // 等号左边是求min，右边则是求max，反之亦然。
            // clamp[j]这个操作没看懂
        }
    }
    
    
    Vec2i P; //定义P点
    for (P.x = bboxmin.x; P.x <= bboxmax.x; P.x++)
    {
        for (P.y = bboxmin.y; P.y <= bboxmax.y; P.y++)
        {
            Vec3f bc_screen = barycentric(pts, P); 
            // 这个是重心坐标的平面吗？
            // 应该是 重心坐标
            if (bc_screen.x < 0 || bc_screen.y < 0 || bc_screen.z < 0)
                continue;
            image.set(P.x, P.y, color);
        }
    }
}

int main(int argc, char ** argv)
{
    TGAImage frame(200, 200, TGAImage::RGB);
    Vec2i pts[3] = {Vec2i(10, 10), Vec2i(100, 30), Vec2i(190, 160)};
    
    triangle(pts, frame, TGAColor(255, 0, 0)); // 点、框架、颜色
    
    frame.flip_vertically();
    frame.write_tga_file("framebuffer.tga");
    
    return 0;
}

代码中的问题：

首先这次的triangle()函数进行了重写。加入了3个Vec2i变量，还都是数组，分别是bboxmin, bboxmax, clamp。在定义的时候有疑问，也就是宽度和高度为什么要减1呢？——

    Vec2i bboxmin(image.get_width() - 1, image.get_height() - 1);    // 宽度和高度为什么要减1呢？
    Vec2i bboxmax(0, 0);
    Vec2i clamp(image.get_width() - 1, image.get_height() - 1);

接下来有一个嵌套双层for循环应该是初始化赋值，只是我不明白为什么width和height要减1。

clamp函数是什么意思？

bboxmin(bboxmax)[0], bboxmin(bboxmax)[1]代表什么意思？

pts[3][2]又是什么意思？为什么求bboxmin是max，bboxmax又是min?

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            // 为什么i是0 1 2，j是0 1呢？
            // bboxmin、bboxmax、clamp三个变量好像都是数组
            // 那么可能就是用struct Vec2中的union中的raw[2]来实例化
            bboxmin[j] = std::max(0, std::min(bboxmin[j], pts[i][j]));
            bboxmax[j] = std::min(clamp[j], std::max(bboxmax[j], pts[i][j])); // 为什么是拿bboxmax
                                                                                // 和pts来取大小？
        }
    }

上述代码中，还有一些问题——

为什么i是0 1 2，j是0 1呢？

bboxmin、bboxmax、clamp三个变量好像都是数组

那么可能就是用struct Vec2中的union中的raw[2]来实例化

为什么是拿bboxmax和pts来取大小？

接下来，则是又加了一个双层嵌套for循环进行遍历像素——
其中，定义了2维向量P；这一段是算2维向量P在边框中遍历像素，将向量P的x和y分量就想象成像素；bc_scrren存储的就是每一个特定像素的重心坐标

2维向量P的x和y分量在边框bboxmin和bboxmax中不断枚举
bboxmin和bboxmax是边界框的最大最小值，不过也是数组，不太明白bboxmax[0], bboxmax[1]代表什么?

barycentric函数返回的是点P的矢量方程式；bc_screen直译是重心的屏幕，但是看到Vec3f；说明bc_screen是一个三维浮点型向量。

bc_screen这个三维向量任意一个分量小于0都不可以。
如果这个像素的重心坐标具有至少一个负分量，那么这个像素点就会出现在三角形的外部

接下来，加进去一个barycentric()函数。问题如下：
这里，pts传的是指针，也许是因为pts是一个数组
Vec3f则是代表三维向量，这里说明，重心是一个三维向量，u也是一个三维向量
这里还没有定义cross()函数，和二维数组pts[][]的两维，各代表什么意思？
这里为什么只有u没有v，u到底是什么？

上面这些问题一直没搞明白，还是先放下吧。。。

大神的博客中，给出了一些解释：

barycentric()函数计算出了在给定三角形中P点的坐标。
triangle()函数则是第一步，计算了一个边界框，这个边界框由2点来描述，分别是左下角的点和右上角的点，这个边框是一个长方形，长方形就会有夹角，为了找到长方形的呢些夹角(corners)，我们遍历三角形的所有顶点，并从中选择最大/最小坐标。
接下来加入了三角形边界框的裁剪，让处在screen外的三角形消失，从而来画一个三角形。

四、平面着色渲染

大家现在已经知道如何用空三角形绘制模型。
那么接下来大家需要掌握的是如何用随机的颜色填充它们——这将帮助大家了解如何编码填充三角形。

在看这些之前，先给大家扫扫盲——

什么是屏幕坐标系，什么又是世界坐标系？
首先，看一个对各种坐标系的大概讲解。说到了，世界坐标系就是个3D模型的坐标系，屏幕坐标系则是当前电脑屏幕上的2D坐标系，是基于像素在电脑上的分辨率来定的。
接下来，在Youtube上听了一门课——

世界坐标系和Device坐标系

从上图可以看到，在世界坐标系中可以开一个窗口，这个窗口就是右边的viewport。
当然，上面说的不全面，刚找到一篇比较详细的：坐标系，里面摆了一张图——

从世界坐标系到屏幕坐标系

有一张图感觉说得很简洁：

从世界坐标系到屏幕坐标系

这张图的注解：the screen coordinate system is a 2D Cartesian coordinate system. It marks the centre of the canvas. The image plane is infinite, but the canvas actually delimits the surface over which the image of the scene will be drawn onto. The canvas size can have any size. In this example, it is two units long in both dimension (as with every Cartesian coordinate system, the screen coordinate system's axes have unit length)。

好，接下来，我们看看如何用随机的颜色来填充三角形，先看看代码——

for (int i = 0; i < model->nfaces(); i++)
{
    std::vector<int> face = model->face(i);
    
    Vec2i screen_coords[3];
    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.);
    }
    
    triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, TGAColor(rand() % 255, rand() % 255, rand() % 255, 255));
}

上述代码中，我们遍历所有的三角形，将世界坐标转换为屏幕坐标，最后画一个三角形——

小丑头

这个小丑头的代码和下图的代码有什么不同的。
首先当然是颜色了，小丑头的颜色的随机的，下图的颜色是根据光照强度来定的。
接下来呢，下图多定义了一个Vec3f变量v，来存储顶点值(vertex)，这个顶点值的用处是赋值给世界坐标变量world_coordinates，然后计算法线向量n。法线向量再和光照方向相乘，得到光强。从而可以来替代小丑色，使用光照的颜色，好看一些。

不知道大家对于上图是否感觉有些像小丑的颜色，下面我们来去掉它，然后加上一些灯光效果。

大家先来看看如何设置光照方向从而让光照强度体现地最大——

垂直方向

亚平行方向

通过上面两张图，显而易见——

在相同的光照强度下，与光的方向垂直的多边形被照得最亮。
如果多边形与光矢量平行，则光照为零。
(解释一下:光照强度等于光矢量与给定三角形法线的标量积。)
三角形的法向量可以简单地计算为它两边的外积。

另外，在这门课上，我们将对颜色进行线性计算。但是（128,128,128）颜色的亮度不及（255、255、255）的一半。我们将忽略伽玛校正，并容忍我们颜色的亮度不正确。

但是点积可以是负的。这是什么意思？这意味着光线来自多边形的后面。
如果场景建模良好(通常是这种情况)，我们可以简单地丢弃这个三角形。这使我们能够快速删除一些不可见的三角形，这叫做后脸剔除。

背部剔除

请注意，口腔的内部空腔位于嘴唇的顶部。这是因为我们对不可见三角形的粗糙剪裁:它只适用于凸形。下次在对z缓冲区进行编码时，将消除此伪像。

最后这次这张图的核心代码是这样：

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)); 
    } 
}

我来解释一下吧——

nfaces()返回的就是.obj文件中f的行数。face(i)返回的就是第i行f，也就是第i个face。

这个for循环从第1行f开始，进入到每一行f当中，进入每一行f中，遍历这行f中的3组顶点（j=0,1,2）

嵌套for循环中的每定义一个新的v，都是v那行中的12/55/7，face[j]就是face[0]/face[1]/face[2]。代表的是3种顶点的索引号，返回顶点的索引号。

所以v每次循环被重新定义，它一会是v，下来是vt，下来是vn。然后3个顶点v/vt/vn形成了screen_coords和world_coords。screen_coords[0]/[1]/[2]就是v/vt/vn的屏幕坐标点，然后这3个屏幕坐标点，画一个triangle。

world_coords[0]/[1]/[2]则是每一行f的v/vt/vn，所以说法线向量n是通过v/vt/vn求出来的。n = (vn - v)^(vt - v)，这个就是法线向量n的算法。最后光强intensity就是color颜色，来画最终的图。

那么这篇博客，主要做了什么呢？

标题是三角形栅格化和后向面剔除，这里的栅格化，就是所谓的填充三角形，因为可能画出来的三角形存在gap，所以只要一行一行地填充像素进去，有gap也不影响。

其中算法中，有两个参数， $\alpha$ 和 $\beta$ ，这两个系数其实就是在计算y的比例，然后计算整体向量的比例。接下来，就是先递增y画点，一起画线段A和B，最后通过得到的A和B，画出填充好的三角形，填充的颜色可以任意选。

还有一个画三角形的算法——计算出边框，边框形成后，就是要画的三角形属于的长方形，遍历这个长方形(也就是边框)中的每一个像素。判断该像素的位置在不在三角形里面，如果在，就画这个像素点，不在就不画。
那么如何判断一个点是否在三角形中呢？——重心法

学习之初，我整理了每节课中代码的变化，现在看来用处不大，但是删了可惜，大家有需要的可以看看哈~~

这篇博客用到的代码文件的变化是这样的：

tgaimage.h (初始导入)
tgaimage.cpp (初始导入)
african_head.obj (线框渲染)
geometry.h (线框渲染)
main.cpp (朴素线段追踪)->(线段追踪、减少划分的次数)->(线段追踪：all
integer Bresenham)->(线框渲染)->(better test triangles)->(三角
形绘制routine)->(背面剔除 + 高洛德着色)
model.cpp (线框渲染)
model.h (线框渲染)

解释一下上述文件括号中的文字——
只有tgaimage.h/.cpp这两个文件是从初始导入到Lesson1最后的线框渲染过程中没有变化过的，所以一直显示是初始导入。
main.cpp变化较多，从一开始的简单的线段追踪，到减少划分次数的线段追踪，再到所有integer Bresenham的线段追踪，直到最后的线段渲染。
剩下的，.obj文件、geometry.h文件、model.h/.cpp文件都是在线框渲染时一起出来的。其中model时用来test测试的。

最后编辑于：2021.12.20 21:49:12

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 201,552评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,666评论 2赞 377
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,519评论 0赞 334
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,180评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,205评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,344评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,781评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,449评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,635评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,467评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,515评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,217评论 3赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,775评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,851评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,084评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,637评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,204评论 2赞 341

实现OpenGL渲染器原理篇(二)——三角形栅格化和后向面剔除

一、填充三角形 Filling triangles

二、老旧的方法：line sweeping

三、新颖的方法

四、平面着色渲染

推荐阅读更多精彩内容