三角光栅化

通过之前的Bresenham画线算法，最简单的方式便是通过三组两两点的直线算法来实现画出三角形

在三角形之间通过平行的扫描线进行渲染

一个好的光栅化算法需要做到以下几点

  • 简单快速
  • 不会受到输入的数据顺序的影响
  • 如果两个三角形有公共点，那么这两个三角形之间重合的部分不能有断点之类出现

算法思路

光栅化的过程，扫描线算法line sweeping：

  1. 将三角形的点根据y的值按照升序进行排列
  2. 将三角形分成平顶和平底两部分
  3. 扫描线进行渲染

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 - t1.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;

		// 检查A，B位置
		if (A.x > B.x)std::swap(A, B);
		// 扫描
		for (int j = A.x; j <= B.x; j++)
		{
			// 从t0开始
			image.set(j, t0.y + i, color);
		}
	}
}

包围盒和重心坐标

重心坐标

在2D坐标系中，给定三角形ABC，存在一点p，有系数u,v使得

P = (1-u-v) * P1 + u * P2 + v * P3

通过连立方程组我们可以得到

  • w1 = 1 - w2 - w3
  • Px = w1 * P1x + w2 * P2x + w3 * P3x
  • Py = w1 * P1y + w2 * P2y + w3 * P3y

进行变换得到

  • w1 = 1 - w2 - w3
  • Px - P3x = w1 * (P1x - P3x) + w2 * (P2x - P3x)
  • Py - P3y = w1 * (P1y - P3y) + w2 * (P2y - P3y)

令C = P-P3, A = P1-P3, B = P2-P3， 可得

  • Cx = w1 * Ax + w2 * Bx
  • Cy = w1* Ay + w2 * By
  • w3 = 1 - w1 - w2

最后解出方程组可得，三个解是与对应的三角形面积成比例的，因此可以先用叉乘计算三角形面积，再求面积的比值

算法思路

  • 首先查找包围盒
  • 遍历包围盒中的点
    • 判断点是否在三角形中
    • 对三角形内的点进行光栅化

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Vec3f barycentric(Vec2i *pts, Vec2i 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]));
	// 如果不是三角形，那么直接返回一个不合法的值
	if (std::abs(u[2]) < 1) return Vec3f(-1, 1, 1);
    // 除u.z是为了归一
	return Vec3f(1.f - (u.x + u.y) / u.z, u.y / u.z, u.x / u.z);
}

void triangle(Vec2i *pts, TGAImage& image, TGAColor color) {
	// 设置包围盒
	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]));
		}
	}
}