TinyRenderer学习笔记02：三角形光栅化和背面剔除

填充三角形

L1中，我们成功的绘制了一个三角形线框，但是这显然是不够的。

到时候人家问你：“为什么你的Renderer只能渲染线框呢？”

你就：“啊对对对！”

在L0和L1中，我们完成了点和线的绘制。但是如果我们想要渲染一个模型的话，我们还必须解决面的渲染绘制问题。

老派做法：扫线算法

我们已经在L1中实现过line()了，我们的方法实际上是绘制L0中的点，只要点足够多就能练成线。

在面这里很容易就可以类比到，用L1中的line()绘制线，只要线足够多就可以连成面。

不过在此之前，我们先完成一个三角形绘制算法。

为了更好的适配我们的三角形绘制算法，我们需要修改一下line()。

这并没有改变line()的逻辑和性能，只是变量名及使用上的一些变化：

// 修改过的画线算法 原理相同
void line(Vec2i p0, Vec2i p1, TGAImage &image, TGAColor color)
{
    bool steep = false;
    if (std::abs(p0.x - p1.x) < std::abs(p0.y - p1.y))
    {
        std::swap(p0.x, p0.y);
        std::swap(p1.x, p1.y);
        steep = true;
    }
    if (p0.x > p1.x)
    {
        std::swap(p0, p1);
    }

for (int x = p0.x; x <= p1.x; x++)
    {
        float t = (x - p0.x) / (float)(p1.x - p0.x);
        int y = p0.y * (1. - t) + p1.y * t;
        if (steep)
        {
            image.set(y, x, color);
        }
        else
        {
            image.set(x, y, color);
        }
    }
}

一个简单的三角形绘制函数：

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, 70),   Vec2i(50, 160),  Vec2i(70, 80)}; 
Vec2i t1[3] = {Vec2i(180, 50),  Vec2i(150, 1),   Vec2i(70, 180)}; 
Vec2i t2[3] = {Vec2i(180, 150), Vec2i(120, 160), Vec2i(130, 180)}; 
triangle(t0[0], t0[1], t0[2], image, red); 
triangle(t1[0], t1[1], t1[2], image, white); 
triangle(t2[0], t2[1], t2[2], image, green);

输出结果：

现在我们已经绘制出了三个三角形，那么我们该如何填充它呢？

一个好的三角形填充算法必须具备以下特点：

它必须十分快速 - 我们完成的是一个实时渲染器；
它应该是对称的 - 不应该依赖传递给绘图函数的顶点顺序；
如果两个三角形有两个共同的顶点，由于光栅化的原因，它们之间不应该有漏洞。

我们可以增加更多的要求，不过我们现在就用这些要去来做，传统上使用的扫弦算法：

按y坐标对三角形顶点进行排序；
同时光栅化三角形的左边和右边；
在左边和右边之间画出一条水平线。

我们现在反过头来再想一想该如何去绘制三角形。

如果我们有三个顶点：t0, t1, t2，它们按照y坐标的升序排列。那么边界A就在t0和t2之间，边界B在t0和t1之间，以及t1和t2之间。

代码类似这样：

// 三角形绘制函数2
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color)
{
    // 将顶点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, green);
    line(t1, t2, image, green);
    line(t2, t0, image, red);
}

输出的结果：

这里边界A是红色的，边界B是绿色。

一般情况下，边界B是两条边组成的，让我们依据边界B的顶点水平切割出三角形的下半部分：

// 三角形绘制函数3
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color)
{
    // 将顶点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);
    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;
        // 小心不要除以0
        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);
    }
}

绘制的结果：

很容易注意到，其中的一些边出现了漏洞。在line()中我们使用了转置绘制的方法避免这个问题，但是在这里这确是必须的。

因为我们的最终目的是绘制面，我们之后要用水平线连接相应的点对，到时候我们就会得到一个完美的面，只需要在三角形绘制的for循环中再添加一个水平绘制循环：

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;
    // 小心不要除以0
    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++)
    {
        // 注意，由于 int casts t0.y+i != A.y 
        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-t0.y)/total_height; 
    // 小心不要除以0
    float beta  = (float)(y-t1.y)/segment_height;
    Vec2i A = t0 + (t2-t0)*alpha; 
    Vec2i B = t1 + (t2-t1)*beta; 
    if (A.x>B.x) std::swap(A, B); 
    for (int j=A.x; j<=B.x; j++) { 
        // 注意，由于 int casts t0.y+i != A.y 
        image.set(j, y, color);
    } 
}

于是我们得到了：

完整的代码如下：

// 三角形填充
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color)
{
    // 将顶点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);
    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;
        // 小心不要除以0
        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++)
        {
            // 注意，由于 int casts t0.y+i != A.y
            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 - t0.y) / total_height;
        // 小心不要除以0
        float beta = (float)(y - t1.y) / segment_height;
        Vec2i A = t0 + (t2 - t0) * alpha;
        Vec2i B = t1 + (t2 - t1) * beta;
        if (A.x > B.x)
            std::swap(A, B);
        for (int j = A.x; j <= B.x; j++)
        {
            // 注意，由于 int casts t0.y+i != A.y
            image.set(j, y, color);
        }
    }
}

这段代码很好的完成了工作，但是相同的for循环写了两次，我们可以将其写到一个for循环之中。

// 三角形填充2
void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color)
{
    // 垂直与摄像机的三角形就没必要去绘制了
    if (t0.y == t1.y && t0.y == t2.y)
        return;
    // 将顶点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);
    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;
        // 注意，再上述条件下，这里不能除以0
        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++)
        {
            // 注意，由于 int casts t0.y+i != A.y
            image.set(j, t0.y + i, color);
        }
    }
}

得到的结果（我顺便改了颜色）：

老师所采用的方法

扫线算法虽然很简单，但是代码确实有点混乱。而且，它还是一种为单线程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); 
        } 
    } 
}

首先，是三角形的重心。给出一个三角形ABC，我们可以这样寻找它的重心：

其实就是相当于在ABC三个点上放置三个权重 (1-u-v, u, v)。则重心正好在点P上。或者我们可以用这种方式表示：

也就是我们有向量 , 和，我们需要找到符合以下条件实数u和v：

我们可以列出一个简单的向量方程，或者由两个变量组成的线性方程组：

写成矩阵形式：

因此我们其实正在寻找一个同时与 (ABx, ACx, PAx) 和 (ABy, ACy, PAy) 正交的向量 (u, v, 1)。

在平面上找到两条直线的交点，只需要计算一个叉积。

// BUG …

平面着色渲染

我们已经完成了三角形的部分，接下来让我们用随机颜色填充L1中出现的OBJ模型线框。在主函数的绘制部分写入：

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

像往常一样，我们遍历了所有三角形，将世界坐标转换成屏幕坐标，然后绘制填充三角形，于是我们得到了如下结果：

接下来我们要做的就是摆脱这垃圾一样的颜色，创造出一些照明效果。

显而易见的是：在相同光照强度下，三角形面与光照方向正交时，它被照的最亮。

当三角形面与光照方向平行时，它得到的亮度为0。

或者说：照明强度等于光矢量与给定三角形的法线的标量乘积，三角形的法线可以简单地计算为其两边的叉积。

在这个课程中，我们将对颜色进行线性计算。然而 (128,128,128) 颜色的亮度并不是 (255,255,255) 的一半。我们将忽略伽马校正，并容忍我们颜色亮度的不正确性。

// 定义光照方向
Vec3f light_dir(0, 0, -1);
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));
    }
}

于是我们得到结果：

可以注意到渲染出来的结果有着很大的问题，比如嘴巴的内腔是画在嘴唇外面的。这是因为我们对看不见的三角形进行了Dirty Clipping，它只对凸面模型完美的工作，无法解决嵌套问题，

填充三角形

老派做法：扫线算法

老师所采用的方法

平面着色渲染

Recommend

Top picks — 2022 August

NFT Trading Down 99 Percent on Most Popular Marketplace

开放更要放开，OPPO眼中的用户生态并非跑马圈地

苏州预计2025年建成20万个充电桩电动汽车约38万辆

今晚直播丨从Zabbix传统监控到应用可观测平台的演进之路 - 最新活动 - dbaplus社群：...

.NET 7 性能改进 -- 至今为止最快的.NET平台

老板电器发布新物种ROKI数字厨电

Asia Broadband builds on its crypto vision by upgrading the digital architecture...

NASA发布了韦伯太空望远镜的幻影星系图像

Limitations to connect with webi report from SAC Live/import data connection-SAP...

About Joyk