软光栅渲染器（一） Bresenham’s Line Drawing Algorithm | 路人乙の小窝

路人乙の小窝

我若安好，万事大吉

0%

软光栅渲染器（一） Bresenham’s Line Drawing Algorithm

发表于 分类于

前言

图形学一直是我感兴趣的方向，但一直苦于找不到方向入门。之前看到很多图形学相关视频下有同学推荐过TinyRenderer的项目，很多老师也推荐过入门要手写一个软光栅渲染器，于是我就开始跟着wiki做了。

项目介绍

Tinyrenderer是ssloy为教学目的准备的开源项目，旨在帮助学生以纯cpp代码，几乎不依赖外部库，实现一个软光栅渲染器。ssloy大神提供了很详细的wiki（以及未更新完的v2版本），我跟着v2版本完成了前面的内容实现，跟着v1版本完成了其余的部分。

至于什么是软光栅渲染器，来看看AI的解释：

软光栅渲染器，也称为软渲染器，是指不依赖于图形硬件（如GPU）加速，而是完全通过CPU来完成渲染过程的渲染器。

它主要用于学习和理解渲染流程，或者在特定场景下（如不需要实时渲染）进行图像生成。

软光栅渲染器是一种基于CPU的渲染器，主要用于学习和理解渲染原理，以及在非实时渲染场景下使用。虽然速度较慢，但对于理解图形渲染的底层机制非常有帮助。

对于我自己的实现，肯定和ssloy大神提供的源代码有很多的区别，但是这些区别只在细节的实现上，整体算法思路肯定是我去遵循他的来做。

一、环境配置

虽然说要尽量不依赖外部库，但是图像生成的具体操作其实对这门课程没有任何益处。所以ssloy大神提供了tgaimge.h和tgaimage.cpp，通过简单的调用就可以生成一副.tga格式的图片。

我电脑上没有adobe photoshop以外的可以读tga格式的文件，因此我用AI写了一个 tgareader 用于查看tga图片。

下面是tgaimage库提供的一些编辑tga图片的方法：

1
2
3
4
5
6
7
8
// 实例化一个tgaimage类，width和height为图片大小，RGBA为颜色格式
TGAImage img(width, height, TGAImage::RGBA);	

// 在(x, y)处绘制一个颜色为color的点
img.set(x, y, color)；
    
// 导出tga格式图片(参数为文件路径)
img.write_tga_file("data/out/test.tga");

在第一节课应该只需要用到这三个方法。

此外，我使用c++20标准，以clion作为IDE。

二、线段绘制

第一步从绘制一条线段开始。我们需要设计一个函数，以两个点的坐标为输入，最后在img上绘制一条线段。

大体框架：

1
2
3
void line(Point p0, Point p1, TGAImage& img, TGAColor c) {	// 其中Point是我自己写的类
    //	TODO：
}

想法一：

对于给定的两个点，我们可以在其中进行均匀采样（因为线段也可以看作一些点的集合）。

我们把直线写成参数方程的形式：
$$
\begin{cases}
x = x_1 + t(x_2 - x_1) \\
y = y_1 + t(y_2 - y_1)
\end{cases}
\quad \text{其中} \quad t \in [0,1]
$$
我们选择一个小的步长，以0.02举例，最后可以在两点之间连出100个点，当图片分辨率较小时可以看到一条清晰的直线。

遇到的问题：

  1. 当两点过远时（比如相距200像素），渲染出的结果会有明显的间断；
  2. 当两点很近时（比如相距只有5像素），会执行很多次多余的img.set()操作；
  3. 对于同样的两个点，根据采样方向的不同，最后会得到完全不同的两条线段；

想法二：

在想法一中，我们对于不同长度的线段使用了相同的采样间距，可以看出遇到的所有问题都和这一步有关系。

如何调整？

由于线段中的每个像素在x/y方向上应该是连续的，我们可以将t转化为x的函数，并在区间[x1,x2]对x采样，计算得到
$$
\begin{cases}
t = \dfrac{x - x_1}{x_2 - x_1} \\[2ex]
y = y_1 + t(y_2 - y_1)
\end{cases}
\quad \text{其中} \quad x \in [x_1, x_2]
$$
这样随着线段长度的变化，线段显示的像素数也随之改变。

遇到的问题：

  1. 如果x变化比较平缓，而y变化比较陡峭，那么线段会有更多的间隔(尤其是计算t时如果x2==x1，可能会发生除零错误)
  2. 如果x2 < x1，线段不会被渲染。但这是一个小问题，只要在采样前加个小小的判断就可以解决。

想法三：Bresenham’s Line Drawing Algorithm

使用和想法二类似的想法，但是我们不直接对x或y采样，而是进行一个小小的判断，找出变化陡峭的一方，如果为y，则反转图像。

这样理解起来可能比较复杂，我绘制了一个简单的框图，可能方便理解一点：

[后来发现图画错了，那我先咕一咕]

在第一个判断中，我们选取了变化陡峭的方向作为遍历方向，因为我们希望每一个x/y值都可以对应至少一个像素，最后的线段才看上去是连续的。如果y的变化更为陡峭，我们交换x和y，实现的效果就是看着是枚举x，实际上枚举y，只要在绘制时绘制(y, x)而不是(x, y)即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void line(Point p0, Point p1, TGAImage& img, TGAColor color) {	// 绘制直线
	int x0 = p0.x, y0 = p0.y, x1 = p1.x, y1 = p1.y;
	bool steep = false;

	if(std::abs(x0 - x1) < std::abs(y0 - y1)) {
		std::swap(x0, y0);
		std::swap(x1, y1);
		steep = true;
	}

	if(x0 > x1) {
		std::swap(x0, x1);
		std::swap(y0, y1);
	}

	float y = y0;

	for(int x = x0; x <= x1; ++x) {
		if(steep) img.set(y, x, color);
		else img.set(x, y, color);

		y += static_cast<float>(y1 - y0) / (x1 - x0);
	}
}

我的工作到此为止了。

可以看到ssloy大神在代码中还加入了一些简单的优化，比如将y设置为int型，根据error的变化来修改y，将if改为三目运算符，能减小一些常数。具体的变化ssloy大神在wiki页面做了详细的实验和结果演示。

结论：

In the past, floating-point operations were significantly more expensive than integer ones (or even entirely inaccessible). This is why Jack Elton Bresenham developed his all-integer rasterization algorithm in the 1960s. As seen in my experiments, integers can still be faster than floating-point computations (this round is more efficient than the previous one), but the performance gain is marginal. Today, integer operations are not always more efficient than floating-point calculations — it depends on the context.

Nevertheless, mastering these techniques remains valuable. As mentioned earlier, this section serves mainly as a historical tribute to Professor Bresenham. His algorithm is elegant, and the discovery of all-integer rasterization was truly ingenious.

过去，浮点运算比整数运算要昂贵得多（甚至完全无法使用）。这就是杰克·埃尔顿·布雷斯南在 20 世纪 60 年代开发了他全部使用整数的光栅化算法的原因。正如我在实验中所见，整数运算仍然可以比浮点计算更快（这一轮比上一轮更高效），但性能提升微乎其微。如今，整数运算并不总是比浮点计算更高效——这取决于具体情境。

然而，掌握这些技巧仍然很有价值。如前所述，本节主要作为对布雷斯南教授的历史致敬。他的算法非常优雅，全整数光栅化技术的发现确实非常巧妙。

Homework: wireframe rendering

wiki页面的最后有一个作业部分，创建一个线框渲染。

说实话看到这个作业的第一眼我是非常震惊的,因为到目前为止我们只学过最简单的绘制直线，但是现在要做的是渲染一个模型的线框。

img

但是静下来思考后，发现事情也没那么困难：线框也是由线构成的，只要将obj模型中的每一条线都绘制出来，就可以得到一个很完美的线框。

我没有使用github项目提供的model.h，而是自己实现了一个模型类用来读取模型，并绘制。我会在整个tinyrenderer项目学习完成后将我的代码上传到github，下面是我作业的一个结果，我个人还是比较满意的

image-20250808165055648

我很可爱，请给我钱qwq