PyTinyRenderer软渲染器-03
Z-Buffer算法是计算机图形学中常用的一种隐藏面消除（Hidden Surface Removal）的算法。在渲染3D图形时，有些物体会遮挡住其他物体，使得它们在2D视图中不可见。Z-Buffer算法就是用来确定哪些物体在视图中是可见的，哪些是被遮挡的。上一节中我们虽然渲染出了模型，但是嘴唇凹进去的阴影面缺显示在上层，本次就拿Z-Buffer算法来处理这个问题。
Z-Buffer算法与画家算法
首先想想为什么需要Z-Buffer算法？或者说Z-Buffer算法究竟解决了什么问题？
理论上，我们可以绘制所有的三角形。如果我们按照正确的顺序从后向前绘制，那么前面的面片将覆盖后面的面片。这种方法被称为画家算法。就如下图，你要先画山、再画草坪、再画树，这就是画家算法的最直观的原理呈现：
然而，这种方法的计算成本非常高：每次摄像机移动，我们都需要重新对整个场景进行排序。对于动态场景，这种需求更是复杂。然而，这甚至不是最主要的问题，最主要的问题在于确定正确的绘制顺序并不是固定不变的。
TinyRenderer给出了样例图你可以参考着想象一下，想象一个由三个三角形组成的简单场景: 相机向上向下看，我们将彩色的三角形投射到白色屏幕上，染出来的结果应该像右边这样：
确定蓝色面是位于红色面的前方还是后方？我们发现在这种情况下，画家算法无法给出答案。一种可能的解决方案是将蓝色面分割成两部分，一部分在红色面前，一部分在红色面后。然后再将红色三角形前的部分进一步分割，一部分在绿色三角形前，一部分在绿色三角形后…… 我们可以看到这个问题的复杂性：在包含数百万个三角形的场景中，这样的计算会变得极其繁琐。
我发现TinyRenderer的作者作为一名老师是非常敬业的，很讲究教学方法，这里他提供了一个重要的思想就是降维。
降低一个维度思考问题
暂时丢弃一个维度，沿着黄色平面剪掉上面的场景，此时我们需要考虑的就只有中间这条线的颜色如何填充即可：
针对这三个三角形，我们先绘制一个2D侧视图，其实也能看出来如果我们从上往下看，也就是图中的观察方向，看到的颜色条应该是：黑、红、绿、蓝、绿、蓝、红、黑这样的顺序排列。我们要做的无非就是把我们大脑思考的过程转化为代码即可，先绘图：
1if __name__ == '__main__':
2 width = 800
3 height = 800
4 image = MyImage((width, height))
5
6 line(20, 34, 744, 400, image, red)
7 line(120, 434, 444, 400, image, green)
8 line(330, 463, 594, 200, image, blue)
9
10 image.save('out.bmp')
创建了一个维度为 (width, 1) 的数组 y-buffer，这个数组的元素均用负无穷整数初始化。随后调用了 rasterize() 函数，将这个渲染对象作为参数传入。为了方便观察，创建64个像素高度的Image:
1def rasterize(p0: Vec2, p1: Vec2, img: MyImage, y_img: MyImage, color, buffer):
2 if p0.x > p1.x:
3 p0, p1 = p1, p0
4 for x in range(p0.x, p1.x + 1):
5 _x = p1.x - p0.x
6 if _x == 0:
7 continue
8 # 计算线性插值的参数
9 t = (x - p0.x) / _x
10 # 对 y 值进行线性插值
11 y = int(p0.y * (1 - t) + p1.y * t)
12 # 如果当前像素的 y 值大于 buffer 中存储的 y 值（表示更靠近观察者）
13 if buffer[x] < y:
14 buffer[x] = y
15 depth_color = int(y / 462 * 255)
16 for h in range(0, 64):
17 img.putpixel((x, h), color)
18 y_img.putpixel((x, h), (depth_color, depth_color, depth_color))
19
20
21if __name__ == '__main__':
22 width = 800
23 height = 64
24 image = MyImage((width, height))
25 y_image = MyImage((width, height))
26
27 # -sys.maxsize - 1 最小值
28 y_buffer = [-sys.maxsize - 1] * width
29
30 rasterize(Vec2([20, 34]), Vec2([744, 400]), image, y_image, red, y_buffer)
31 rasterize(Vec2([120, 434]), Vec2([444, 400]), image, y_image, green, y_buffer)
32 rasterize(Vec2([330, 463]), Vec2([594, 200]), image, y_image, blue, y_buffer)
33
34 image.save('out.bmp')
35 y_image.save('y_out.bmp')
简单复习下线性插值的基本原理：在这个场景中，我们已知线段的两个端点（p0和p1），我们想要找到线段上任何一个点的位置。假设我们有两个点 $p0(x_0, y_0)$ 和 $p1(x_1, y_1)$，我们想要找到在这两点连线上的某一点 $P(x, y)$。假设 $P$ 与 $p0$ 在x轴上的距离占整个线段在x轴上的距离的比例是 $t$，那么我们可以计算出 $P$ 的坐标：
$$ x = x_0 + t * (x_1 - x_0) $$ $$ y = y_0 + t * (y_1 - y_0) $$
在这个代码中，我们已经知道了 $x$ 的值（就是我们正在遍历的像素的x坐标），我们的目标是找到对应的 $y$ 值。因此我们可以先计算出 $t$
$$ t = \frac{x - x_0}{x_1 - x_0} $$
然后用 $t$ 来计算 $y$：
$$ y = y_0 * (1 - t) + y_1 * t $$
跟我们预想的黑、红、绿、蓝、绿、蓝、红、黑这样的顺序排列完全一样，而且顺便绘制了y-buffer深度图，颜色越深表示离观察点越远，回想看看上面的侧视图，的确是这样吧，现在让开始回归到3D的场景来思考Z-Buffer算法。
3D场景的Z-Buffer算法
对于二维的情况来说，我们需要Y-Buffer，对于3D场景也是同样的道理，我们需要一个二维数组来作为深度缓冲区。由于二维数组本质上也是个普通数组，所以直接采用如下的方式进行初始化：
1z_buffer = [-sys.maxsize - 1] * width * height
2
3# index、xy之间互相转化也比较方便
4index = x + y * width
5x = idx % width
6y = int(idx / width)
下面是完整的代码：
1def triangle(p0: Vec3, p1: Vec3, p2: Vec3, img: MyImage, z_img: MyImage, color):
2 min_x = max(0, min(p0.x, p1.x, p2.x))
3 max_x = min(img.width - 1, max(p0.x, p1.x, p2.x))
4 min_y = max(0, min(p0.y, p1.y, p2.y))
5 max_y = min(img.height - 1, max(p0.y, p1.y, p2.y))
6 P = Vec2((0, 0))
7 # 遍历包围盒内的每个像素
8 for P.y in range(min_y, max_y+1):
9 for P.x in range(min_x, max_x+1):
10 # 计算当前像素的重心坐标
11 bc_screen = barycentric(p0, p1, p2, P)
12 if bc_screen is None:
13 continue
14 # 如果像素的重心坐标的任何一个分量小于0，那么这个像素就在三角形的外部，我们就跳过它
15 if bc_screen.x < 0 or bc_screen.y < 0 or bc_screen.z < 0:
16 continue
17
18 # 计算当前像素的深度
19 z = p0.z * bc_screen.x + p1.z * bc_screen.y + p2.z * bc_screen.z
20
21 # 检查Z缓冲区，如果当前像素的深度比Z缓冲区中的值更近，那么就更新Z缓冲区的值，并绘制像素
22 idx = P.x + P.y * img.width
23 if z_buffer[idx] < z:
24 z_buffer[idx] = z
25 image.putpixel((P.x, P.y), color)
26 # 绘制深度图z_img
27 depth_color = int(z * 255)
28 if depth_color > 0:
29 z_img.putpixel((P.x, P.y), (depth_color, depth_color, depth_color))
30
31
32if __name__ == '__main__':
33 width = 600
34 height = 600
35 image = MyImage((width, height))
36 # 深度缓冲展示一下
37 z_image = MyImage((width, height))
38
39 # -sys.maxsize - 1 最小值
40 z_buffer = [-sys.maxsize - 1] * width * height
41
42 obj = OBJFile('african_head.obj')
43 obj.parse()
44
45 light_dir = Vec3([0, 0, -1])
46 for face in obj.faces:
47 screen_coords = []
48 world_coords = [None, None, None]
49 for j in range(3):
50 v: Vec3 = obj.vert(face[j])
51 screen_coords.append(Vec3([int((v.x + 1) * width / 2), int((v.y + 1) * height / 2), v.z]))
52 world_coords[j] = v
53 # 计算三角形的法向量和光照强度
54 n: Vec3 = (world_coords[2] - world_coords[0]).cross(world_coords[1] - world_coords[0])
55 n.normalize()
56 intensity = n * light_dir
57 # 负的就剔除掉
58 if intensity > 0:
59 triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, z_image,
60 (int(255 * intensity), int(255 * intensity), int(255 * intensity)))
61
62 image.save('out.bmp')
63 z_image.save('z_out.bmp')
纹理坐标插值
到目前为止，我们渲染的模型都是白模，如何把纹理贴上去呢？
这里有必要复习一下OBJ文件的格式，还记得OBJ文件中的vt吗？ vt：这是一个纹理坐标。它通常是一个二维坐标，表示为(u, v)，用于映射3D模型的表面纹理。例如，vt 0.500 1.000表示一个纹理坐标位于(0.5,1)，所以Z坐标通常都是0。所以需要对之前的OBJ文件读取的类稍加修改：
1from vector import Vec3
2
3
4class OBJFile:
5 def __init__(self, filename):
6 self.filename = filename
7 self.vertices = []
8 self.texture_coords = [] # 添加一个新的列表来存储纹理坐标
9 self.faces = []
10
11 def parse(self):
12 with open(self.filename, 'r') as file:
13 for line in file:
14 components = line.strip().split()
15 if len(components) > 0:
16 if components[0] == 'v':
17 self.vertices.append([float(coord) for coord in components[1:]])
18 elif components[0] == 'vt': # 添加一个新的条件来处理纹理坐标
19 self.texture_coords.append([float(coord) for coord in components[1:]])
20 elif components[0] == 'f':
21 # 修改这里，以便同时存储顶点和纹理坐标的索引
22 self.faces.append([[int(index.split('/')[0]),
23 int(index.split('/')[1])] for index in components[1:]])
24
25 def vert(self, i):
26 """
27 :param i: vertex index
28 :param i: 因为obj文件的顶点索引是从1开始的，所以需要减1
29 :return:
30 """
31 return Vec3(self.vertices[i - 1])
32
33 def texcoord(self, i): # 添加一个新的方法来获取纹理坐标
34 """
35 :param i: texture coordinate index
36 :param i: 因为obj文件的纹理坐标索引是从1开始的，所以需要减1
37 :return:
38 """
39 return Vec3(self.texture_coords[i - 1])
开始贴图，african_head_diffuse.tga 是一个压缩的TGA文件，这里直接使用pillow来读取：
1from PIL import Image
2
3if __name__ == '__main__':
4 width = 600
5 height = 600
6
7 tga: Image = Image.open('african_head_diffuse.tga')
8
9 image = MyImage((width, height))
10
11 # -sys.maxsize - 1 最小值
12 z_buffer = [-sys.maxsize - 1] * width * height
13
14 obj = OBJFile('african_head.obj')
15 obj.parse()
16
17 light_dir = Vec3([0, 0, -1])
18 for face in obj.faces:
19 screen_coords = []
20 world_coords = [None, None, None]
21 uv_coords = [None, None, None]
22 for j in range(3):
23 v: Vec3 = obj.vert(face[j][0])
24 screen_coords.append(Vec3([int((v.x + 1) * width / 2), int((v.y + 1) * height / 2), v.z]))
25 world_coords[j] = v
26 uv_coords[j] = obj.texcoord(face[j][1]) # 获取纹理坐标
27
28 # 计算三角形的法向量和光照强度
29 n: Vec3 = (world_coords[2] - world_coords[0]).cross(world_coords[1] - world_coords[0])
30 n.normalize()
31 intensity = n * light_dir
32 # 负的就剔除掉
33 if intensity > 0:
34 color = tga.getpixel((int(uv_coords[0].x * tga.width), int(uv_coords[0].y * tga.height)))
35 color = (int(color[0] * intensity), int(color[1] * intensity), int(color[2] * intensity))
36
37 triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, color)
38
39 image.save('out.bmp')
我们使用了第一个顶点的纹理坐标来获取颜色，而不是使用所有顶点的纹理坐标来插值颜色。所以模型可能会看起来有些奇怪，因为所有的颜色都是从第一个顶点的纹理坐标开始的。如果我们想要更准确的颜色，需要在 triangle 函数中插值纹理坐标：
1def triangle(p0: Vec3, p1: Vec3, p2: Vec3,
2 uv0: Vec2, uv1: Vec2, uv2: Vec2,
3 intensity, img: MyImage, tga: Image):
4 min_x = max(0, min(p0.x, p1.x, p2.x))
5 max_x = min(img.width - 1, max(p0.x, p1.x, p2.x))
6 min_y = max(0, min(p0.y, p1.y, p2.y))
7 max_y = min(img.height - 1, max(p0.y, p1.y, p2.y))
8 P = Vec2((0, 0))
9 # 遍历包围盒内的每个像素
10 for P.y in range(min_y, max_y+1):
11 for P.x in range(min_x, max_x+1):
12 # 计算当前像素的重心坐标
13 bc_screen = barycentric(p0, p1, p2, P)
14 if bc_screen is None:
15 continue
16 # 如果像素的重心坐标的任何一个分量小于0，那么这个像素就在三角形的外部，我们就跳过它
17 if bc_screen.x < 0 or bc_screen.y < 0 or bc_screen.z < 0:
18 continue
19
20 # 使用重心坐标来插值纹理坐标
21 uv = uv0 * bc_screen.x + uv1 * bc_screen.y + uv2 * bc_screen.z
22 # 使用插值后的纹理坐标来从TGA文件中获取颜色
23 # 此TGA文件是从左上角开始的，所以需要将纵坐标反转
24 color = tga.getpixel((int(uv.x * tga.width), tga.height - 1 - int(uv.y * tga.height)))
25 color = (int(color[0] * intensity), int(color[1] * intensity), int(color[2] * intensity))
26
27 # 计算当前像素的深度
28 z = p0.z * bc_screen.x + p1.z * bc_screen.y + p2.z * bc_screen.z
29
30 # 检查Z缓冲区，如果当前像素的深度比Z缓冲区中的值更近，那么就更新Z缓冲区的值，并绘制像素
31 idx = P.x + P.y * img.width
32 if z_buffer[idx] < z:
33 z_buffer[idx] = z
34 image.putpixel((P.x, P.y), color)
35
36
37def world2screen(v: Vec3) -> Vec3:
38 return Vec3([int((v.x + 1.) * width/2. + .5), int((v.y + 1.) * height/2. + .5), v.z])
39
40
41if __name__ == '__main__':
42 width = 600
43 height = 600
44
45 tga: Image = Image.open('african_head_diffuse.tga')
46
47 image = MyImage((width, height))
48
49 # -sys.maxsize - 1 最小值
50 z_buffer = [-sys.maxsize - 1] * width * height
51
52 obj = OBJFile('african_head.obj')
53 obj.parse()
54
55 light_dir = Vec3([0, 0, -1])
56 for face in obj.faces:
57 screen_coords = []
58 world_coords = [None, None, None]
59 uv_coords = [None, None, None]
60 for j in range(3):
61 v: Vec3 = obj.vert(face[j][0])
62 screen_coords.append(Vec3([int((v.x + 1) * width / 2), int((v.y + 1) * height / 2), v.z]))
63 world_coords[j] = v
64 uv_coords[j] = obj.texcoord(face[j][1]) # 获取纹理坐标
65
66 # 计算三角形的法向量和光照强度
67 n: Vec3 = (world_coords[2] - world_coords[0]).cross(world_coords[1] - world_coords[0])
68 n.normalize()
69 intensity = n * light_dir
70 # 负的就剔除掉
71 if intensity > 0:
72 triangle(screen_coords[0], screen_coords[1], screen_coords[2],
73 uv_coords[0], uv_coords[1], uv_coords[2],
74 intensity, image, tga)
75
76 image.save('out.bmp')
完整代码：
1import sys
2from PIL import Image
3from image import MyImage
4from obj import OBJFile
5from vector import Vec3, Vec2
6
7white = (255, 255, 255)
8red = (255, 0, 0)
9green = (0, 255, 0)
10blue = (0, 0, 255)
11
12
13def triangle_area_2d(a: Vec2, b: Vec2, c: Vec2) -> float:
14 """
15 计算三角形面积
16 """
17 return .5 * ((b.y - a.y) * (b.x + a.x) + (c.y - b.y) * (c.x + b.x) + (a.y - c.y) * (a.x + c.x))
18
19
20def barycentric(A, B, C, P):
21 """
22 计算重心坐标 u, v, w
23 """
24 total_area = triangle_area_2d(A, B, C)
25 if total_area == 0:
26 return None # 或者抛出一个异常，或者返回一个特殊的值
27 u = triangle_area_2d(P, B, C) / total_area
28 v = triangle_area_2d(P, C, A) / total_area
29 w = triangle_area_2d(P, A, B) / total_area
30 return Vec3([u, v, w])
31
32
33def triangle(p0: Vec3, p1: Vec3, p2: Vec3,
34 uv0: Vec2, uv1: Vec2, uv2: Vec2,
35 intensity, img: MyImage, tga: Image):
36 min_x = max(0, min(p0.x, p1.x, p2.x))
37 max_x = min(img.width - 1, max(p0.x, p1.x, p2.x))
38 min_y = max(0, min(p0.y, p1.y, p2.y))
39 max_y = min(img.height - 1, max(p0.y, p1.y, p2.y))
40 P = Vec2((0, 0))
41 # 遍历包围盒内的每个像素
42 for P.y in range(min_y, max_y+1):
43 for P.x in range(min_x, max_x+1):
44 # 计算当前像素的重心坐标
45 bc_screen = barycentric(p0, p1, p2, P)
46 if bc_screen is None:
47 continue
48 # 如果像素的重心坐标的任何一个分量小于0，那么这个像素就在三角形的外部，我们就跳过它
49 if bc_screen.x < 0 or bc_screen.y < 0 or bc_screen.z < 0:
50 continue
51
52 # 使用重心坐标来插值纹理坐标
53 uv = uv0 * bc_screen.x + uv1 * bc_screen.y + uv2 * bc_screen.z
54 # 纹理采样：使用插值后的纹理坐标来从TGA文件中获取颜色
55 # 此TGA文件是从左上角开始的，所以需要将纵坐标反转
56 color = tga.getpixel((int(uv.x * tga.width), tga.height - 1 - int(uv.y * tga.height)))
57 color = (int(color[0] * intensity), int(color[1] * intensity), int(color[2] * intensity))
58
59 # 计算当前像素的深度
60 z = p0.z * bc_screen.x + p1.z * bc_screen.y + p2.z * bc_screen.z
61
62 # 检查Z缓冲区，如果当前像素的深度比Z缓冲区中的值更近，那么就更新Z缓冲区的值，并绘制像素
63 idx = P.x + P.y * img.width
64 if z_buffer[idx] < z:
65 z_buffer[idx] = z
66 image.putpixel((P.x, P.y), color)
67
68
69if __name__ == '__main__':
70 width = 600
71 height = 600
72
73 tga: Image = Image.open('african_head_diffuse.tga')
74
75 image = MyImage((width, height))
76
77 # -sys.maxsize - 1 最小值
78 z_buffer = [-sys.maxsize - 1] * width * height
79
80 obj = OBJFile('african_head.obj')
81 obj.parse()
82
83 light_dir = Vec3([0, 0, -1])
84 gamma = 2.2
85 for face in obj.faces:
86 screen_coords = []
87 world_coords = [None, None, None]
88 uv_coords = [None, None, None]
89 for j in range(3):
90 v: Vec3 = obj.vert(face[j][0])
91 screen_coords.append(Vec3([int((v.x + 1) * width / 2), int((v.y + 1) * height / 2), v.z]))
92 world_coords[j] = v
93 uv_coords[j] = obj.texcoord(face[j][1]) # 获取纹理坐标
94
95 # 计算三角形的法向量和光照强度
96 n: Vec3 = (world_coords[2] - world_coords[0]).cross(world_coords[1] - world_coords[0])
97 n.normalize()
98 intensity = n * light_dir
99 # 负的就剔除掉
100 if intensity > 0:
101 # 带上Gamma校正
102 intensity = intensity ** (1 / gamma)
103 triangle(screen_coords[0], screen_coords[1], screen_coords[2],
104 uv_coords[0], uv_coords[1], uv_coords[2],
105 intensity, image, tga)
106
107 image.save('out_gamma.bmp')
带上Gamma校正后渲染出来的效果很显然看起来更自然：
纹理坐标插值的核心流程：
- 读取纹理坐标：首先，对于每个顶点，我们需要定义一个纹理坐标（通常称为 (u, v) 。这些坐标定义了每个顶点在纹理图像中的位置。在一个三角形中，我们会定义三个这样的坐标。
- 插值计算：对于在三角形内部的每个像素，我们需要知道它在纹理图像中的对应位置。我们可以通过对三个顶点的纹理坐标进行插值来得到这个信息。这个插值过程通常是基于像素到三角形顶点的距离的。我们这里插值过程使用了重心坐标。重心坐标即三角形内部的一个点相对于三角形三个顶点的权重。如果我们知道一个点的重心坐标，我们就可以通过将每个顶点的纹理坐标与对应的权重相乘，然后将结果相加，来得到这个点的纹理坐标。
- 纹理采样：一旦我们有了像素的纹理坐标，就可以从纹理采样样，代码中
tga.getpixel就是在进行纹理采样。 - 像素着色：最后，我们使用从纹理图像中取样得到的颜色来着色像素。光照计算这些都是在纹理坐标插值之后进行的。
到目前为止，我们已经成功地把纹理贴在了模型上，而且通过使用重心坐标来插值纹理坐标，直接就获得了我们期望的效果，而且通过Z-Buffer算法已经很完美的处理了嘴唇凹进去的阴影面缺显示在上层的问题。
本节就先这样，代码我放在这里了： https://github.com/zouchanglin/PyTinyRenderer