【光栅化渲染器】（九）改进光栅化

现在我们的渲染管线已经基本具备了所有的要素，但是作为光栅化渲染器，我们目前的光栅化算法太过老旧，扫描线算法简单高效，但难以并行化（毕竟操作的单位是一条线），并且在实现时还存在由于多次插值的精度损失导致的多个三角形间存在接缝等问题。因此现在已经不被使用，之前在图形学中我们学习过另一种光栅化方法，这节我们来讨论该方法的一些具体实现细节。

1 边界函数算法

关于边界函数算法，原理同样非常简单，就是用点和三角形三个顶点连线的向量叉乘来判断点是否在三角形内部，具体可以查看之前的笔记【计算机图形学】（三）光栅化，其中还包含了 C++ 代码实现。我们先照搬过来：

/*
  Vector3f* _v存储三角形的三个顶点坐标，顶点顺序为逆时针
*/
static bool insideTriangle(int x, int y, const Vector3f* _v)
{   
    //用像素中心坐标判断
    Vector3f p(float(x) + 0.5, float(y) + 0.5, 1);
    //向量AB和AC叉乘的纵坐标
    float signofTrig = (_v[1].x() - _v[0].x()) * (_v[2].y() - _v[0].y()) - (_v[1].y() - _v[0].y()) * (_v[2].x() - _v[0].x());
    //向量AB和AP叉乘的纵坐标
    float signOfAB = (_v[1].x() - _v[0].x()) * (p.y() - _v[0].y()) - (_v[1].y() - _v[0].y()) * (p.x() - _v[0].x());
    //向量CA和CP叉乘的纵坐标
    float signOfCA = (_v[0].x() - _v[2].x()) * (p.y() - _v[2].y()) - (_v[0].y() - _v[2].y()) * (p.x() - _v[2].x());
    //向量BC和BP叉乘的纵坐标
    float signOfBC = (_v[2].x() - _v[1].x()) * (p.y() - _v[2].y()) - (_v[2].y() - _v[1].y()) * (p.x() - _v[2].x());
    bool d1 = (signOfAB * signofTrig > 0);
    bool d2 = (signOfCA * signofTrig > 0);
    bool d3 = (signOfBC * signofTrig > 0);
    return d1 && d2 && d3;
}

所谓边界函数实际上就是上述代码中的 (signOfAB * signofTrig > 0) 等这三个判断条件，因为这个条件判断了点和三角形的一条边界的位置关系，因此被称为边界函数。根据边界函数经过推导可以看出每次移动一个像素得到的边界函数和之前的边界函数的差值是固定的，具体推导过程可以查看图形学底层探秘 - 更现代的三角形光栅化与插值算法的实现与优化，因此我们不需要每次都计算叉乘，只需要在前一次的结果上加上差值即可。

另一个问题是，我们对每个三角形的 Bounding Box 内的像素进行遍历来判断其是否在三角形内部，那么至少会有一半的像素不在三角形内而造成计算浪费，因此出现了分块优化算法，即将 Bounding Box 进行分块，然后只判断每块四个角上的像素是否在三角形内，如果每块的四个像素都在三角形内部或者外部，其他像素就不需要再进行判断了，如果四个像素部分在内部部分在外部就执行正常的算法在块内逐像素判断。这个方法对于占屏幕面积较大的三角形优化效果明显，但如果是小三角形或是斜长的细三角形，反而不如不分块来得快。而且，太大的分块会进一步降低小三角形的绘制效率，而太小的分块又变回了逐像素算法，因此分块的大小需要仔细的权衡。

2 重心插值

扫描线算法中使用线性插值就可以确定片元的各种属性值，而在边界函数算法中需要使用重心插值，关于重心坐标我们之前的笔记中也有具体的推导：【计算机图形学】（六）着色中的第4部分。

在实现中我们如何计算重心坐标呢？首先整个三角形的面积可以通过：
$$
S_{\Delta} = \frac{1} {2}a·b·sin\theta
$$
来计算，也就是三角形两条边叉乘得到的向量模的一半，以 AB 和 BC 边为例，三角形的面积为：
$$
S_{\Delta} = \frac{1} {2}(A_xB_y - A_yBx + B_xC_y - B_yCx + C_xA_y - C_yAx)
$$
而我们的三个边界函数相加：
$$
F_{AB}(P) + F_{BC}(P) + F_{CA}(P) = A_xB_y - A_yBx + B_xC_y - B_yCx + C_xA_y - C_yAx
$$
刚好是三角形面积的二倍，即：
$$
\frac{F_{AB}(P) + F_{BC}(P) + F_{CA}(P)} {2S_{\Delta} } = 1
$$
而重心坐标就是小三角形面积和整个三角形面积的比值，因此我们可以直接通过边界函数得到点 P 的重心坐标：
$$
\alpha = \frac{F_{AB}(P)} { {2S_{\Delta} } },\beta = \frac{F_{BC}(P)} { {2S_{\Delta} } },\gamma = \frac{F_{CA}(P)} { {2S_{\Delta} } }
$$
这样整个光栅化算法就完成了。需要注意的是重心插值和之前的线性插值一样，都需要进行透视插值校正，即在透视除法中将所有属性都除以 w 值，最后在片元着色器之前再乘以 w 值恢复。关于透视插值校正我们将在下一节详细讨论。