TinyRenderer 学习笔记02：隐藏面剔除（Z-buffer）

上次我们渲染的结果中，可以看到斯坦福兔子上有一些“脏东西”。

在这里使用african_head.obj这个模型会看的更加明显一些：

可以看到模型的嘴巴和眼睛似乎有着某些问题。这是因为本来应该被遮挡的三角形（比如口腔、眼腔等）被错误的绘制了出来。

解析我们目前的代码不难发现，它根本没有考虑任何有关遮挡/重叠的问题，出现上述错误情况算是情理之内。

画师算法（从后向前）

所谓“画师算法”，指的是像画师一样绘制，从后向前依次绘制所有三角形。对于那些重叠的三角形，他们会被后面新绘制的三角形所覆盖。

这种算法可以十分完美的完成我们想要的效果，没有任何瑕疵。但是稍微有点计算机基础的人都会明白，这个算法做了太多的无用功，结果就是高昂的计算成本。

考虑到我们实现的是一个渲染器，之后的每次相机移动都需要对场景进行重新排序，至于动态场景则更让人崩溃。

最重要的是，不是每次都能确保排序的正确性。

Y/Z-buffer（从前向后）

画师算法存在严重的性能浪费问题，那我们不如反其道而行之——从前向后绘制画面。

这似乎不太好理解，但是正如我一直在说的：所有更易阅读的代码都会存在效率问题。如果你想让你的代码更加高效，那么它几乎一定是不好理解的，不管是从代码的语法层面，还是它背后的原理。

Y-buffer — 简单的二维理解

直接从三维开始并不是一个好的选择，所以我们先从简单的二维情况来理解。

设想一个场景：

从上向下看的样子：

用一个面去切这个场景：

得到中间这一条：

使用之前做好的line()函数可以很简单的绘制这个场景，我们先从侧面来看：

TGAImage scene(width, height, TGAImage::RGB);

// scene "2d mesh"
line(Vec2i(20, 34), Vec2i(744, 400), scene, red);
line(Vec2i(120, 434), Vec2i(444, 400), scene, green);
line(Vec2i(330, 463), Vec2i(594, 200), scene, blue);

// screen line
line(Vec2i(10, 10), Vec2i(790, 10), scene, white);

// 原点在图像的左下角
scene.flip_vertically();
scene.write_tga_file("scene.tga");

结果：

二维光栅化算法

代码很简单，有很多我们熟悉的东西：

// 二维光栅化（ybuffer）
void rasterize(Vec2i p0, Vec2i p1, TGAImage &image, TGAColor color, int ybuffer[])
{
	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;
		// 判断ybuffer的大小，如果小于当前y
		if (ybuffer[x] < y)
		{
			// 当前y设为ybuffer
			ybuffer[x] = y;
			// 绘制像素
			image.set(x, 0, color);
		}
		// 否则，不绘制
	}
}

这里比较值得注意的是数组ybuffer。在主函数中，我们会将其设为负无穷大：

int ybuffer[width];
for (int i = 0; i < width; i++)
{
    // 记得导入极限库 #include <limits>
    ybuffer[i] = std::numeric_limits<int>::min();
}

在函数工作过程中，ybuffer会不断和当前的y进行比较，当发现该像素靠后，则不进行绘制。

我们依次绘制三个颜色的直线：

• 红色：

  • 场景：

    

  • ybuffer：

    

• 绿色：

  • 场景：

    

  • ybuffer

    

• 蓝色：

  • 场景：

    

  • ybuffer：

    

只看场景的结果，其实不一定能意识到发生了什么，但是看到ybuffer的结果就一目了然了。

在ybuffer的结果中，洋红色表示负无穷大，其余部分都以灰色表示，越黑意味着离屏幕越远。

我们正是通过Y-buffer的存在实现了“从前向后”的绘制，或者说，对“隐藏”的像素实现了“剔除”。

Z-buffer — 回到三维

Y-buffer给我们提供了一个简单理解的案例，现在让我们回到三维。

要在二维屏幕上绘制（光栅化）三维模型，Z-buffer必须是二维的，因此有：

int *zbuffer = new int[width*height];

为了方便处理，可以将二维buffer打包成一维buffer：

int idx = x + y*width;

想要获得x和y：

int x = idx % width;
int y = idx / width;

我们需要做的，就是遍历所有三角形，然后和zbuffer进行比对，只绘制“靠前”的像素。

唯一的困难在于，如何计算我们要绘制的像素的z值。在Y-buffer中，我们这样实现：

int y = p0.y*(1.-t) + p1.y*t;

这里的t是什么？

事实上，$(1-t,t)$是点$P(x,y)$相对于线段p0，p1的重心坐标：(x,y)=p0*(1-t)+p1*t。

我们的想法是，采用三角形光栅化的重心坐标版本，对于我们想要绘制的每个项目，只需要将其重心坐标乘以我们光栅化三角形顶点的z值。

修改后的重心坐标算法：

// 重心坐标
Vec3f barycentric(Vec3f A, Vec3f B, Vec3f C, Vec3f P)
{
	// 计算叉积
	Vec3f s[2];
	for (int i = 2; i--;)
	{
		s[i][0] = C[i] - A[i];
		s[i][1] = B[i] - A[i];
		s[i][2] = A[i] - P[i];
	}
	Vec3f u = cross(s[0], s[1]);
	// 不要忘记u[2]是整数。如果它是零，那么三角形ABC是退化的
	if (std::abs(u[2]) > 1e-2)
		// 返回重心坐标
		return Vec3f(1.f - (u.x + u.y) / u.z, u.y / u.z, u.x / u.z);
	// 在这种情况下产生负坐标，它将被光栅化器丢弃
	return Vec3f(-1, 1, 1);
}

加入zbuffer的三角形光栅化算法：

// 三角形光栅化（重心坐标）
void triangle(Vec3f *pts, float *zbuffer, TGAImage &image, TGAColor color)
{
	Vec2f bboxmin(std::numeric_limits<float>::max(), std::numeric_limits<float>::max());
	Vec2f bboxmax(-std::numeric_limits<float>::max(), -std::numeric_limits<float>::max());
	Vec2f 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.f, std::min(bboxmin[j], pts[i][j]));
			bboxmax[j] = std::min(clamp[j], std::max(bboxmax[j], pts[i][j]));
		}
	}
	Vec3f P;
	// 遍历，找出三角形内的点。
	// 遍历x
	for (P.x = bboxmin.x; P.x <= bboxmax.x; P.x++)
	{
		// 遍历y
		for (P.y = bboxmin.y; P.y <= bboxmax.y; P.y++)
		{
			// 重心坐标
			Vec3f bc_screen = barycentric(pts[0], pts[1], pts[2], P);
			// 是否在边界内
			if (bc_screen.x < 0 || bc_screen.y < 0 || bc_screen.z < 0)
				continue;
			P.z = 0;
			for (int i = 0; i < 3; i++)
				P.z += pts[i][2] * bc_screen[i];
			// 使用zbuffer判断是否渲染
			if (zbuffer[int(P.x + P.y * width)] < P.z)
			{
				zbuffer[int(P.x + P.y * width)] = P.z;
				image.set(P.x, P.y, color);
			}
		}
	}
}

在主函数中调用：

for (int i = 0; i < model->nfaces(); i++)
{
    std::vector<int> face = model->face(i);
    Vec3f pts[3];
    Vec3f world_coords[3];
    for (int i = 0; i < 3; i++)
    {
        pts[i] = world2screen(model->vert(face[i]));
        Vec3f v = model->vert(face[i]);
        world_coords[i] = v;
    };
    // 计算每一个三角形的法向量
    Vec3f n = cross((world_coords[2] - world_coords[0]), (world_coords[1] - world_coords[0]));
    // 归一化法向量
    n.normalize();
    // 计算光线强度
    float intensity = n * light_dir;
    // 如果光线强度大于0
    if (intensity > 0)
    {
        // 依据光线强度，绘制填充三角形
        triangle(pts, zbuffer, image, TGAColor(intensity * 255, intensity * 255, intensity * 255, 255));
    }
    // triangle(pts, zbuffer, image, TGAColor(rand() % 255, rand() % 255, rand() % 255, 255));
}

结果：

可以看到，我们的斯坦福兔子上面已经没有“脏东西”了。用african_head.obj可以看的更清楚：

可以看到，内部空腔都被正确的渲染。