PyTinyRenderer软渲染器-02
本节是PyTinyRenderer的第二节，可以把本系列的文章看成是PyTinyRenderer的工程介绍文档，而不是TinyRenderer的Wiki翻译，其实尝试过翻译，但是我发现有时候翻译并不能清晰地表达我的想法，尤其是一些代码上的细节问题，对照原本的C++工程要复现的话需要做很多工作，所以本系列的核心目的也是能够让读者能轻易的复现TinyRenderer这个工程。本节主要实现的部分是三角形光栅化、涉及平面着色、光照模型与背面剔除。
三角形的光栅化
暂时可以先不管三角形的光栅化的概念，我们先来看看如何绘制一个三角形。基于第一节的内容，我们很容易绘制出一个三角形，下面是TinyRenderer的Wiki的三个三角形，我直接拿过来了：
1def triangle(p1: Vec2, p2: Vec2, p3: Vec2, img: MyImage, color):
2 line(p1.x, p1.y, p2.x, p2.y, img, color)
3 line(p1.x, p1.y, p3.x, p3.y, img, color)
4 line(p2.x, p2.y, p3.x, p3.y, img, color)
5
6
7if __name__ == '__main__':
8 width = 200
9 height = 200
10 image = MyImage((width, height))
11 white = (255, 255, 255)
12 red = (255, 0, 0)
13 green = (0, 255, 0)
14 obj = OBJFile('african_head.obj')
15 obj.parse()
16
17 # 三角形三个顶点
18 t1 = [Vec2([10, 70]), Vec2([50, 160]), Vec2([70, 80])]
19 t2 = [Vec2([180, 50]), Vec2([150, 1]), Vec2([70, 180])]
20 t3 = [Vec2([180, 150]), Vec2([120, 160]), Vec2([130, 180])]
21 triangle(t1[0], t1[1], t1[2], image, white)
22 triangle(t2[0], t2[1], t2[2], image, red)
23 triangle(t3[0], t3[1], t3[2], image, green)
24
25 image.save('out.bmp')
一个绘制三角形的算法应该包括以下功能：
-
简单高效，非常快速的就可以绘制完成。
-
应该具有对称性：图片的绘制结果，不应受传递给绘制函数的顶点的顺序影响。
-
如果两个三角形有两个共同的顶点，其实就是这两个三角形在渲染或绘制时，应该紧密相连，没有间隙。
逐行扫线算法
我们可能会提出更多的需求，但可以先做一个出来简单版本。使用传统的扫线方式：
假设某个三角形的三个顶点：p0、p1、p2，按 y 坐标排序，A(红色)、B(绿色)边分别由 p0-p2、p0-p1构成，并且位于p1 p2之间。
1white = (255, 255, 255)
2red = (255, 0, 0)
3green = (0, 255, 0)
4
5def triangle(p0: Vec2, p1: Vec2, p2: Vec2, img: MyImage):
6 if p0.y > p1.y:
7 p0, p1 = p1, p0
8 if p0.y > p2.y:
9 p0, p2 = p2, p0
10 if p1.y > p2.y:
11 p1, p2 = p2, p1
12 line(p0.x, p0.y, p1.x, p1.y, img, green)
13 line(p1.x, p1.y, p2.x, p2.y, img, green)
14 line(p2.x, p2.y, p0.x, p0.y, img, red)
三角形通过水平切割线分成上下两部分，这样的话就可以通过水平扫线的方式的填充这个三角形。先来绘制下半部分：
1def triangle(p0: Vec2, p1: Vec2, p2: Vec2, img: MyImage):
2 if p0.y > p1.y:
3 p0, p1 = p1, p0
4 if p0.y > p2.y:
5 p0, p2 = p2, p0
6 if p1.y > p2.y:
7 p1, p2 = p2, p1
8 line(p0.x, p0.y, p1.x, p1.y, img, green)
9 line(p1.x, p1.y, p2.x, p2.y, img, green)
10 line(p2.x, p2.y, p0.x, p0.y, img, red)
11 # 绘制下半部分
12 # 计算线段的斜率
13 slope0 = (p1.x - p0.x) / (p1.y - p0.y) if p1.y != p0.y else 0
14 slope1 = (p2.x - p0.x) / (p2.y - p0.y) if p2.y != p0.y else 0
15 # 从底部开始绘制
16 for y in range(int(p0.y), int(p1.y) + 1):
17 xs = p0.x + slope0 * (y - p0.y) # 计算扫描线的起始点
18 xe = p0.x + slope1 * (y - p0.y) # 计算扫描线的结束点
19 # 确保 xs < xe
20 if xs > xe:
21 xs, xe = xe, xs
22 # 绘制水平线
23 for x in range(int(xs), int(xe)):
24 img.putpixel((x, y), green)
现在把上半部分也补上:
1white = (255, 255, 255)
2red = (255, 0, 0)
3green = (0, 255, 0)
4
5
6def triangle(p0: Vec2, p1: Vec2, p2: Vec2, img: MyImage):
7 if p0.y > p1.y:
8 p0, p1 = p1, p0
9 if p0.y > p2.y:
10 p0, p2 = p2, p0
11 if p1.y > p2.y:
12 p1, p2 = p2, p1
13 # line(p0.x, p0.y, p1.x, p1.y, img, green)
14 # line(p1.x, p1.y, p2.x, p2.y, img, green)
15 # line(p2.x, p2.y, p0.x, p0.y, img, red)
16 # 绘制下半部分
17 # 计算线段的斜率
18 slope0 = (p1.x - p0.x) / (p1.y - p0.y) if p1.y != p0.y else 0
19 slope1 = (p2.x - p0.x) / (p2.y - p0.y) if p2.y != p0.y else 0
20 # 从底部开始绘制
21 for y in range(int(p0.y), int(p1.y) + 1):
22 xs = p0.x + slope0 * (y - p0.y) # 计算扫描线的起始点
23 xe = p0.x + slope1 * (y - p0.y) # 计算扫描线的结束点
24 # 确保 xs < xe
25 if xs > xe:
26 xs, xe = xe, xs
27 # 绘制水平线
28 for x in range(int(xs), int(xe)):
29 img.putpixel((x, y), green)
30 # 绘制上半部分
31 slope2 = (p2.x - p1.x) / (p2.y - p1.y) if p2.y != p1.y else 0
32 for y in range(int(p1.y), int(p2.y)):
33 xs = p1.x + slope2 * (y - p1.y) # 计算扫描线的起始点
34 xe = p0.x + slope1 * (y - p0.y) # 计算扫描线的结束点
35
36 # 确保 xs < xe
37 if xs > xe:
38 xs, xe = xe, xs
39
40 # 绘制水平线
41 for x in range(int(xs), int(xe)):
42 img.putpixel((x, y), red)
我们可以将这两个循环合并为一个，通过在循环中更改斜率和范围来处理上下两部分。在循环中，我们检查y是否小于p1.y，如果是，我们就在下半部分，否则我们就在上半部分。然后我们根据这个信息计算扫描线的起始点。
1def triangle(p0: Vec2, p1: Vec2, p2: Vec2, img: MyImage):
2 if p0.y > p1.y:
3 p0, p1 = p1, p0
4 if p0.y > p2.y:
5 p0, p2 = p2, p0
6 if p1.y > p2.y:
7 p1, p2 = p2, p1
8 # 计算线段的斜率
9 slope0 = (p1.x - p0.x) / (p1.y - p0.y) if p1.y != p0.y else 0
10 slope1 = (p2.x - p0.x) / (p2.y - p0.y) if p2.y != p0.y else 0
11 slope2 = (p2.x - p1.x) / (p2.y - p1.y) if p2.y != p1.y else 0
12
13 # 从底部开始绘制
14 for y in range(int(p0.y), int(p2.y)):
15 if y < p1.y: # 如果在下半部分
16 xs = p0.x + slope0 * (y - p0.y) # 计算扫描线的起始点
17 else: # 如果在上半部分
18 xs = p1.x + slope2 * (y - p1.y) # 计算扫描线的起始点
19 xe = p0.x + slope1 * (y - p0.y) # 计算扫描线的结束点
20
21 # 确保 xs < xe
22 if xs > xe:
23 xs, xe = xe, xs
24
25 # 绘制水平线
26 for x in range(int(xs), int(xe)):
27 img.putpixel((x, y), green)
当然我们也可以用Tinyrenderer中计算插值的方式来完成，使用alpha和beta两个变量来计算扫描线的起始点和结束点。alpha是用于计算从t0到t2的插值，beta是用于计算从t0到t1或从t1到t2的插值，具体取决于是否在三角形的下半部分或上半部分。
1def triangle(p0: Vec2, p1: Vec2, p2: Vec2, img: MyImage):
2 # 如果点的纵坐标不是按升序排序的，则交换它们
3 if p0.y > p1.y:
4 p0, p1 = p1, p0
5 if p0.y > p2.y:
6 p0, p2 = p2, p0
7 if p1.y > p2.y:
8 p1, p2 = p2, p1
9
10 total_height = p2.y - p0.y
11 if total_height == 0: # 如果三个点在同一水平线上，直接返回
12 return
13
14 for i in range(total_height):
15 second_half = i > p1.y - p0.y or p1.y == p0.y
16 segment_height = p2.y - p1.y if second_half else p1.y - p0.y
17 if segment_height == 0: # 如果上半部分或下半部分的高度为0，跳过这一次循环
18 continue
19 alpha = i / total_height
20 beta = (i - (p1.y - p0.y if second_half else 0)) / segment_height
21 A = p0 + (p2 - p0) * alpha
22 B = p1 + (p2 - p1) * beta if second_half else p0 + (p1 - p0) * beta
23
24 # 确保 A.x < B.x
25 if A.x > B.x:
26 A, B = B, A
27
28 # 绘制水平线
29 for x in range(int(A.x), int(B.x)):
30 img.putpixel((x, p0.y + i), green)
扫线的方式确实可行，但是扫线是一种专为单线程 CPU 编程而设计的古老方法，效率相对较低。
包围盒算法
包围盒算法是一种简单有效的用于绘制三角形的方法，下面我们用包围盒的方式来完成三角形的绘制，我们首先计算出三角形的包围盒，也就是包含三角形的最小矩形。然后，我们遍历包围盒中的每个像素，对于每个像素，我们计算它到三角形三个顶点的向量，然后计算这些向量的叉积。如果所有的叉积都是正的，那么这个像素就在三角形内，我们就将其颜色设为绿色。
让我们看一下下面的伪代码：
1function DrawTriangle(p0, p1, p2, img):
2 // 计算三角形的包围盒
3 minX = max(0, floor(min(p0.x, p1.x, p2.x)))
4 maxX = min(img.width - 1, ceil(max(p0.x, p1.x, p2.x)))
5 minY = max(0, floor(min(p0.y, p1.y, p2.y)))
6 maxY = min(img.height - 1, ceil(max(p0.y, p1.y, p2.y)))
7
8 // 遍历包围盒中的每个像素
9 for x from minX to maxX:
10 for y from minY to maxY:
11 // 计算像素点到三角形三个顶点的向量
12 v0 = p0 - Vec2(x, y)
13 v1 = p1 - Vec2(x, y)
14 v2 = p2 - Vec2(x, y)
15
16 // 计算向量的叉积，以判断像素点是否在三角形内
17 cross0 = v0.cross(v1)
18 cross1 = v1.cross(v2)
19 cross2 = v2.cross(v0)
20
21 // 如果像素点在三角形内，就将其颜色设为绿色
22 if cross0 >= 0 and cross1 >= 0 and cross2 >= 0:
23 img.set_pixel(x, y, green)
这个伪代码只适用于顶点按逆时针顺序给出的三角形。如果顶点是按顺时针顺序给出的，那么我们需要改变叉积的判断条件，将>=改为<=。其实我们完全有更简单的方式来解决这个问题，那就是重心坐标。给定一个包含点 A、B、C 和点 P 的三角形，我们想要找到一个向量 u、v、w，使得：
$$ P = u A + v B + w C $$
换句话说， (u, v, w) 是 P 关于三角形 ABC 的重心坐标。它们满足：u + v + w = 1，u、v 、w均在0-1之间。如果点P位于三角形内部，那么u、v 、w 都大于0，如果位于三角形外部，则至少有一个小于0。可以参考下图：
重心坐标这种方式是一种描述三角形内点的位置的方式，它将每个点表示为三角形顶点的加权平均值。如果一个点的重心坐标坐标的所有分量都大于等于0，那么这个点就在三角形内。这种方法的优点是，它可以直接处理任意形状的三角形，无需担心三角形是顺时针还是逆时针排列的，也无需担心三角形的顶点是否按照特定的顺序排列。
1def triangle_area_2d(a: Vec2, b: Vec2, c: Vec2) -> float:
2 """
3 计算三角形面积
4 """
5 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))
6
7
8def barycentric(A, B, C, P):
9 """
10 计算重心坐标 u, v, w
11 """
12 total_area = triangle_area_2d(A, B, C)
13 u = triangle_area_2d(P, B, C) / total_area
14 v = triangle_area_2d(P, C, A) / total_area
15 w = triangle_area_2d(P, A, B) / total_area
16 return Vec3([u, v, w])
17
18
19def triangle(p0: Vec2, p1: Vec2, p2: Vec2, img: MyImage):
20 min_x = max(0, min(p0.x, p1.x, p2.x))
21 max_x = min(img.width - 1, max(p0.x, p1.x, p2.x))
22 min_y = max(0, min(p0.y, p1.y, p2.y))
23 max_y = min(img.height - 1, max(p0.y, p1.y, p2.y))
24 P = Vec2((0, 0))
25 # 遍历包围盒内的每个像素
26 for P.y in range(min_y, max_y+1):
27 for P.x in range(min_x, max_x+1):
28 # 计算当前像素的重心坐标
29 bc_screen = barycentric(p0, p1, p2, P)
30 # 如果像素的重心坐标的任何一个分量小于0，那么这个像素就在三角形的外部，我们就跳过它
31 if bc_screen.x < 0 or bc_screen.y < 0 or bc_screen.z < 0:
32 continue
33 image.putpixel((P.x, P.y), red)
加载模型并随机着色
我们已经知道如何用空三角形绘制模型。 让我们用随机颜色填充它们。下面的代码有助于我们看到代码是如何填充三角形的：
1if __name__ == '__main__':
2 width = 600
3 height = 600
4 image = MyImage((width, height))
5
6 obj = OBJFile('african_head.obj')
7 obj.parse()
8
9 def random_color():
10 return random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)
11
12 for face in obj.faces:
13 screen_coords = []
14 for j in range(3):
15 v: Vec3 = obj.vert(face[j])
16 screen_coords.append(Vec2([int((v.x + 1) * width / 2), int((v.y + 1) * height / 2)]))
17 triangle(screen_coords[0], screen_coords[1], screen_coords[2], image, random_color())
18 image.save('out.bmp')
背面剔除与光照模型
在强度相同的光照下，与光线方向垂直的多边形面会被照得更亮。我们通过冯氏光照模型很容易得出这样的结论 ：当多边形与光线平行时，接收的光照是 0。其实照明强度等于光向量与给定三角形法线向量的点积，三角形的法线，可以通过三角形两条边做叉积得到。
1if __name__ == '__main__':
2 width = 600
3 height = 600
4 image = MyImage((width, height))
5
6 obj = OBJFile('african_head.obj')
7 obj.parse()
8
9 light_dir = Vec3([0, 0, -1])
10 for face in obj.faces:
11 screen_coords = []
12 world_coords = [None, None, None]
13 for j in range(3):
14 v: Vec3 = obj.vert(face[j])
15 screen_coords.append(Vec2([int((v.x + 1) * width / 2), int((v.y + 1) * height / 2)]))
16 world_coords[j] = v
17 # 计算三角形的法向量和光照强度
18 n: Vec3 = (world_coords[2] - world_coords[0]).cross(world_coords[1] - world_coords[0])
19 n.normalize()
20 intensity = n * light_dir
21 # 负的就剔除掉
22 if intensity > 0:
23 triangle(screen_coords[0], screen_coords[1], screen_coords[2], image,
24 (int(255 * intensity), int(255 * intensity), int(255 * intensity)))
25
26 image.save('out.bmp')
Gamma 矫正
注意，在TinyRenderer中会把颜色的计算视为线性的，然而实际上 (128, 128, 128) 还没有 (255, 255, 255) 一半亮。也就是说，我们忽略 gamma 矫正，并容忍颜色亮度的误差。正常情况下会做一些次方倍率以接近真实情况，比如：
因为Gamma 校正的本质就是就是对图像进行非线性变换，使得图像在人眼看来更接近原始场景。这是因为人眼对亮度的感知是非线性的，我们对暗区域的变化更敏感，对亮区域的变化则不太敏感。通过 Gamma 矫正，我们可以更好地调整图像的暗区和亮区，使其更符合人眼的观察习惯。Gamma 矫正的数学公式通常表示为：
$$ O = I^\gamma $$
其中，O 是输出图像，I 是输入图像，$ \gamma $ 是 Gamma 值。如果 $\gamma < 1$，则会增强图像的暗区，使图像看起来更亮；如果 $\gamma > 1$，则会压暗图像的亮区，使图像看起来更暗。
只有当 intensity 大于0时才会进行 Gamma 矫正，否则直接跳过，就不会产生复数了。
1if __name__ == '__main__':
2 width = 400
3 height = 400
4 image = MyImage((width, height))
5
6 obj = OBJFile('african_head.obj')
7 obj.parse()
8
9 light_dir = Vec3([0, 0, -1])
10 gamma = 2.2 # Gamma 值
11 for face in obj.faces:
12 screen_coords = []
13 world_coords = [None, None, None]
14 for j in range(3):
15 v: Vec3 = obj.vert(face[j])
16 screen_coords.append(Vec2([int((v.x + 1) * width / 2), int((v.y + 1) * height / 2)]))
17 world_coords[j] = v
18 # 计算三角形的法向量和光照强度
19 n: Vec3 = (world_coords[2] - world_coords[0]).cross(world_coords[1] - world_coords[0])
20 n.normalize()
21 intensity = n * light_dir
22 # 负的就剔除掉
23 if intensity > 0:
24 # 进行 Gamma 矫正
25 intensity = intensity ** (1 / gamma)
26 triangle(screen_coords[0], screen_coords[1], screen_coords[2], image,
27 (int(255 * intensity), int(255 * intensity), int(255 * intensity)))
28
29 image.save('out2.bmp')
到目前为止，我们加载了模型，并且成功的做了背面剔除，并且添加了光照，而且跟对人眼特性做了Gamma 校正。但是此时嘴的内腔绘制在了嘴唇的顶部，这是因为我们现有的背面剔除方案仅适用于凸出的形状，在下个章节我们将通过 z-buffer 来解决掉这个问题。