软光栅渲染器（二） Triangle rasterization

前言

在上一课我们已经实现了3d模型的线框渲染，现在我们希望为他填色，也就是说每个三角形都是实心的。

问题简化

为了完成这一目的，先来考虑一个简单的子问题：如何绘制一个三角形？

我们用类似上一章的参数结构，给定三个点的坐标，一个TGAImage的引用，以及一个颜色，要求绘制一个实心的三角形

1
2
3

void triangle(Point p0, Point p1, Point p2, TGAImage& img, TGAColor color) {
    // TODO:
}

obj格式的模型提供了顶点的三维坐标和每个三角形所的三个顶点的索引，在上一节课我们已经能够成功的将obj格式模型转化为我们自己定义的model类，如果有这样一个可以绘制三角形的函数，我们绘制模型中的每一个三角形，就可以得到一个完整的模型。

方法一 Scanline rasterization

参考上一章节绘制线段的想法，我们在区间[x0, x1]中遍历x（或者遍历y，这里以x为例），计算相应的y，并在屏幕中绘制。此时我们是将线段拆成了一个个像素。同样的，对于一个三角形，我们可以遍历y，然后计算出每个y值对应的x0和x1，绘制对应的线段，由一段段线段构成我们所需要的三角形。

这就是传统的扫描线做法。

将三角形三个点按照y坐标升序排列（可以用冒泡排序很快完成）；
在第二个点处水平分割三角形，应该能得到两个三角形；
分别在两个三角形处计算边界，填充像素。

扫描线做法原理很简单，看上去也不难，但实际写起来会有很多细节和繁琐的计算。

方法二 Modern rasterization approach

对于任何一个三角形，我们可以找到一个AABB（轴对齐包围盒）将其包裹住，我们可以遍历AABB中的每一个像素，判断其是否在三角形内部，如果是，则将该点像素填色。

这个方法看上去比扫描线更容易理解，但是看上去会对更多点产生判断，为什么现代更多用这种方法？

:bulb:提示：

AABB（Axis-Aligned Bounding Box）方法 比传统扫描线方法快，核心原因在于 计算范围更集中，逻辑更简单，内存访问模式更高效。

Massively parallel computations running in thousands of threads, even on regular consumer hardware, fundamentally change the way we approach problems.

在扫描线算法中，不同行的扫描是有顺序存在的。但在AABB算法中，所有点之间没有依赖，可以并行计算加速。

所以现在我们有一个更简单，更好理解，更好写代码的方法可以实现三角形的绘制。我们只需要计算minx、miny、maxx、maxy，然后在这个范围内枚举(x, y)即可。

下一个问题：如何判断某个像素点p要不要填色？（如何判断像素点p是否在三角形内？）

考虑重心坐标

$P = \alpha A + \beta B + \gamma C$，如果 $\alpha,\ \beta,\ \gamma$ 中存在任意一者为负数，则认为P不在三角形内；
三个参数可以由子三角形的面积除以整个三角形的面积得到；
三角形的面积可以利用向量叉乘去求。

三角形面积：

1
2
3

float signed_area(Point p0, Point p1, Point p2) {
	return .5 * (p1.x - p0.x) * (p2.y - p0.y) - .5 * (p2.x - p0.x) * (p1.y - p0.y);
}

三个参数：

1
2
3

float alpha = signed_area(p, p1, p2) / total_area;
float beta 	= signed_area(p0, p, p2) / total_area;
float gamma = signed_area(p0, p1, p) / total_area;

整个绘制三角形的函数：

void triangle(Point p0, Point p1, Point p2, TGAImage& img, TGAColor color) {	// 绘制三角形
	int minx = std::min({p0.x, p1.x, p2.x});
	int maxx = std::max({p0.x, p1.x, p2.x});
	int miny = std::min({p0.y, p1.y, p2.y});
	int maxy = std::max({p0.y, p1.y, p2.y});

	float total_area = signed_area(p0, p1, p2);
#pragma omp parallel for
	for(int x = minx; x <= maxx; ++x) {
		for(int y = miny; y <= maxy; ++y) {
			Point p(x, y);
			float alpha = signed_area(p, p1, p2) / total_area;
			float beta 	= signed_area(p0, p, p2) / total_area;
			float gamma = signed_area(p0, p1, p) / total_area;
			if(alpha < 0 || beta < 0 || gamma < 0) continue;
			img.set(x, y, color);
		}
	}
}

结果

现在回头看看之前的线框渲染的作业，因为涂成纯色也不合适，为了更好的观察一眼效果，我们可以对每个三角形随机填色。

结果如下图：

其实可以看到面部有很多错误，这是因为很多背面的面片被错误覆盖到了正面之上，这一错误会在下次课被改正。

这一章节涉及到的数学有关内容，可以在wiki页面找到ssloy大神给出的一些解释。