这篇文章主要分两个部分：第一部分说明 Windows 的绘图环境搭建，实现最基本的画点功能；第二部分介绍 Bresenham 画线算法，实现画线功能。

代码我放在 github 上：DoubleTongTong/SoftRender。以便记录一步步实现的过程。

1. Windows 绘图环境搭建

一开始还是 Windows 窗体那套 API，我们来梳理一下：

1. 在窗口创建之前，我们需要进行窗口类注册，使用 RegisterClass() 函数。它定义窗口的显示特性。

2. 使用步骤 1 注册的窗口类，我们可以使用 CreateWindow() 函数创建一个窗口实例。然后使用 ShowWindow() 函数控制其可见性，让它显示出来。

3. 和窗口相关的所有用户交互和系统事件都是通过消息机制来处理的，所以我们需要写一个主循环来不断获取消息、处理消息。

我们可以通过 PeekMessage() 函数从消息队列种提取消息；并使用 TranslateMessage() 对消息进行预处理和转换；最后使用 DispatchMessage() 函数将消息派发到相应的窗口处理函数（WindowProc，在步骤 1 中绑定）。

这边有一点要说明，GetMessage() 函数也可以从消息队列中获取消息，但是它是阻塞的。当消息队列为空，GetMessage 会一直阻塞，直到有消息可取。

以上就是 Windows 窗体的基本流程，记录在 tag/init_window。这部分的目标是能显示出一个窗体就可以了。

实现画点功能

如果我们要更新控制窗口内容，Windows 上传统的方式是使用 InvalidateRect() 等函数强制触发 WM_PAINT 消息，以达到窗口内容更新。但这种方式基于消息机制，处理速度得不到保证。

我们基于现有的 Windows 机制，实现类似双缓冲的概念。大致思路为，我们创建一块内存区域，当作后台缓冲，在上面更新维护内容；当这块内容绘制好了，我们再把它更新到前台窗口上。

具体的步骤和使用到的 Windows API 为：

1. 使用 CreateDIBSection() 函数创建一个设备独立位图

其原型为：

其中，hdc 是设备上下文的句柄；pbmi 指定位图的维度和颜色格式；usage 指定颜色数据如何解释；ppvBits 返回位图的地址，可以通过它直接读写位图数据；hSection 是指向一个文件映射的对象，这边设置为 NULL，表示为位图分配内存；dwOffset 表示位图从文件对象开始的偏移，这边设置为 0。

2. 选中位图到内存 DC（Device Context，设备上下文）

我们可以使用 CreateCompatibleDC() 函数来创建一个与当前屏幕兼容的内存 DC。然后使用 SelectObject() 函数将 CreateDIBSection 创建的位图对象选中到此内存 DC。

3. 绘图操作

在步骤 1 中我们已经得到了位图的地址，我们可以在上面进行操作，实现画点和画线等功能。

4. 使用 BitBlt() 函数复制内容到屏幕

其原型为：

我们设置源 DC 为步骤 2 中和位图相关的内存 DC；目的 DC 设置为窗口 DC；rop 参数设置为 SRCCOPY 。就可以将位图上的内容复制到屏幕上。

上述的相关操作都说明完了，现在我们开始实现画点功能。如代码清单 1 所示，画点功能的实现很简单，只要更新对应内存中的数据即可。

1. void TRasterizer::SetPixel(int x, int y, TRGB888 color)
2. {
3.     if (x < 0 || x >= m_width || y < 0 || y >= m_height)
4.         return;
5.  
6.     m_pBits[y * m_width + x] = color.ToBGR888();
7. }

因为画点引入了坐标，所以这边需要提及一下，CreateDIBSection 创建的位图大小是基于客户区大小的。而 CreateWindow 指定的大小是窗口的整体大小，在客户区大小上还有标题栏和边框等。

我们这边可以使用 AdjustWindowRect() 函数，根据指定的窗口样式和菜单，计算一个矩形的大小，使得客户区的大小与所指定的矩形相匹配。这样绘图的坐标区域就对应上了。

以上就是画点功能的实现，记录在 tag/init_gdi。如视频 1 所示，我们可以写一个随机颜色点的效果，验证画点功能。

2. Bresenham 画线算法

在第一节中，我们已经实现了画点功能。基于画点功能，我们可以实现画线功能。

最朴素直观的画线算法是数值微分法，名字听着比较高端，其实就是我们想的化连续为离散。比如我们需要画从 (0,0) 到 (5,5) 的一条直线，只需要画 (0,0)、(1,1)、(2,2)、(3,3)、(4,4)、(5,5) 这几个点就行了。不是所有的情况对应的点都是整数，这时候只要四舍五入即可。

画线时还需要注意是 x 轴上递增，还是 y 轴上递增。当斜率的绝对值小于等于 1 时，我们在 x 轴上递增取点；大于 1 时，在 y 轴上递增取点。

还有需要考虑的就是指定的点是从左往右画，还是从右往左画。考虑到以上所有需要注意的情况后，我们就可以实现数值微分法的画线函数了。

如代码清单 2 所示，只要两点就能确定斜率，斜率确定了，各方向的遍历增量也就确定了。我们按照各方向增量四舍五入取点即可。因为垂直时斜率为无穷，我们对其单加一个判断。

1. void TRasterizer::DrawLineDifferential(int x1, int y1, int x2, int y2)
2. {
3.     int numSteps;
4.     float deltaX, deltaY;
5.  
6.     int dx = x2 - x1;
7.     int dy = y2 - y1;
8.     float k = (dx == 0) ? std::numeric_limits<float>::infinity() : (float)dy / (float)dx;
9.  
10.     if (dx == 0)
11.     {
12.         deltaX = 0;
13.         deltaY = dy >= 0 ? 1 : -1;
14.         numSteps = abs(dy);
15.     }
16.     else if (fabsf(k) <= 1)
17.     {
18.         deltaX = dx >= 0 ? 1 : -1;
19.         deltaY = deltaX * k;
20.         numSteps = abs(dx);
21.     }
22.     else
23.     {
24.         deltaY = dy >= 0 ? 1 : -1;
25.         deltaX = deltaY / k;
26.         numSteps = abs(dy);
27.     }
28.  
29.     float x = x1, y = y1;
30.     for (int i = 0; i <= numSteps; i++)
31.     {
32.         SetPixel(round(x), round(y), TRGB888(0, 0, 0));
33.         x += deltaX;
34.         y += deltaY;
35.     }
36. }

从代码中我们也可以看到，计算操作都是基于浮点数的，所以会比较耗时。下面介绍 Bresenham 画线算法，它可以使计算都针对整数。

我们先以斜率 \(k\)，\(0 \leq k \leq 1\) 的情况，对 Bresenham 进行说明。因为当 \(x\) 增加 1，且 \(0 \leq k \leq 1\)，所以 \(y\) 上的增量也不会超过 1。根据四舍五入，下一个点的 y 值只有两种情况：

1. 下一个点的 y 值和前一个点的 y 值相同；

2. 下一个点的 y 值为前一个点的 y 值加一；

如何判断选用哪个点，如图 1 所示，只要判断这两个点谁距离真实的点最近。

现在我们开始推导一下，设直线方程为 \(y = kx+b\)。

第 \(i\) 个确认了的点的坐标为 \((x_i,y_i)\)。

下一个 \(i + 1\) 点 \(Q\) 的真实坐标为 \((x_{i+1},kx_{i+1}+b)\)。

情况 1 距离真实点的距离 \(|QS|=kx_{i+1}+b-y_i\)。

情况 2 距离真实点的距离 \(|TQ|=y_i+1-kx_{i+1}-b\)

两者做差值比较 \(E_{i+1}=|QS|-|TQ|=2kx_{i+1}-2y_i+2b-1\)。

可得再下一个点的计算插值为 \(E_{i+2}=2kx_{i+2}-2y_{i+1}+2b-1\)。

当 \(E_{i+1} < 0\)，则选情况 1，\(y_{i+1}=y_i\)。

此时 \(E_{i+2}=2k(x_{i+1}+1)-2y_i+2b-1=E_{i+1}+2k\)。

当 \(E_{i+1} \geq 0\)，则选情况 2，\(y_{i+1}=y_i + 1\)。

此时 \(E_{i+2}=2k(x_{i+1}+1)-2(y_i+1)+2b-1=E_{i+1}+2k-2\)。

总结一下情况：

\(E_{i+2}=\begin{cases}E_{i+1}+2k,& \text{if } E_{i+1} < 0 \\ E_{i+1}+2k-2,& \text{if } E_{i+1} \geq 0 \end{cases}\)

其中 \(k\) 可能是浮点数，不过没关系，\(k=\frac{\Delta y}{\Delta x}\)。\(\Delta x\) 和 \(\Delta y\) 都是整数，两边同乘 \(\Delta x\) 即可消去。

\(\Delta x E_{i+2}=\begin{cases}\Delta x E_{i+1}+2\Delta y,& \text{if } \Delta x E_{i+1} < 0 \\ \Delta x E_{i+1}+2\Delta y-2\Delta x,& \text{if } \Delta x E_{i+1} \geq 0 \end{cases}\)

让等式好看一点，再设 \(E'=\Delta x E\)，得：

\(E'_{i+2}=\begin{cases}E'_{i+1}+2\Delta y,& \text{if } E'_{i+1} < 0 \\ E'_{i+1}+2(\Delta y - \Delta x),& \text{if } E'_{i+1} \geq 0 \end{cases}\)

现在只差最后一步了，需要求出初始项：

\(E'_1=\Delta x E_1=2\Delta y(x_0+1)-2y_0\Delta x+2b\Delta x-\Delta x\)

因为 \(y_0=kx_0+b\)，所以

\(b\Delta x=y_0\Delta x-x_0\Delta y\)

代入 \(E'_1\) 得：\(E'_1=2\Delta y-\Delta x\)

至此 Bresenham 画线算法就推导完毕了。和数值微分法一样，我们也需要考虑斜率的各种情况，以及两点的增长的顺序。

针对斜率考虑：

1. 斜率 \(|k| > 1\)，我们交换 x 和 y 的顺序，这样就能套用斜率 \(|k| < 1\) 时的公式。求出结果后，在画点时再将 x 和 y 的顺序换回来。

2. 上述只考虑了 \(0 \leq k \leq 1\) 的情况，当 \(-1 \leq k \leq 0\) 时，可以再走一遍公式，不难得出结果。

针对增长顺序：

在对斜率处理完毕之后，我们就只针对 \(|k| < 1\) 了。增长顺序就更好处理了，如果 x 是从大到小的，我们把前后两个点交换即可。

1. void TRasterizer::DrawLineBresenham(int x1, int y1, TRGB888 color1, int x2, int y2, TRGB888 color2)
2. {
3.     bool useSwappedXY = std::abs(y2 - y1) > std::abs(x2 - x1);
4.  
5.     // 如果线段斜率绝对值大于 1，则交换 x 和 y
6.     if (useSwappedXY)
7.     {
8.         std::swap(x1, y1);
9.         std::swap(x2, y2);
10.     }
11.  
12.     if (x1 > x2)
13.     {
14.         std::swap(x1, x2);
15.         std::swap(y1, y2);
16.         std::swap(color1, color2);
17.     }
18.  
19.     int deltaX = x2 - x1;
20.     int deltaY = y2 - y1;
21.     int E = 2 * std::abs(deltaY) - deltaX;
22.  
23.     int y = y1;
24.     int yStep = y1 < y2 ? 1 : -1;
25.  
26.     for (int x = x1; x <= x2; x++)
27.     {
28.         float t = deltaX == 0 ? 0 : (float)(x - x1) / (float)deltaX;
29.         TRGB888 interpolatedColor = color1.Lerp(color2, t);
30.  
31.         if (useSwappedXY)
32.             SetPixel(y, x, interpolatedColor);
33.         else
34.             SetPixel(x, y, interpolatedColor);
35.  
36.         if (E < 0)
37.         {
38.             E += 2 * std::abs(deltaY);
39.         }
40.         else
41.         {
42.             E += 2 * (std::abs(deltaY) - deltaX);
43.             y += yStep;
44.         }
45.     }
46. }

代码清单 3 是 Bresenham 画线算法的实现，对着上述的情况分类和公式推导，不难理解代码。

代码中在画线的同时，额外对线的颜色实现了简单的线性插值算法。线性插值和 Bresenham 比起来很好理解，就是加权平均，权重值就是当前点距离第一个点占第一个点距离第二点的比值。

以上就是Bresenham 画线功能的实现，记录在 tag/draw_line。如视频 2 所示，我们可以画各个斜率的直线，验证结果是否正确。