刚接触计算机图形学的时候，我有个挺大的疑惑：屏幕上明明是一块一块的像素，为什么能显示斜滑的直线？后来才明白，所谓画直线，本质是一个“选点”的过程。把理想直线映射到一张像素网格上，挑那些离直线最近的像素点亮，视觉上就形成了一条直线。这个“选点”的算法，最常见也最经典的两个，就是DDA算法和Bresenham算法。

如果你正在学图形学基础，或者想自己写一个软件渲染器、小游戏引擎，甚至只是做课程作业，这两条算法都绕不开。它们解决同一个问题：给定起点和终点坐标，快速算出中间一串像素坐标，并且让结果看起来像一条直线。但两条路线的思路和性能差别挺大，一个靠浮点增量，一个靠整数加减，背后体现的其实是计算机图形学里“用效率换精度”和“用整数换速度”两种典型思维。

这篇文章会把两条算法都拆开讲清楚，包括数学原理、推导过程、可复现的代码实现，以及我在实际写代码时踩过的坑和总结的选型经验。不搞玄乎的理论，尽量用大白话把每一步的逻辑说明白。

1. 先聊聊直线光栅化这件事

1.1 光栅显示的本质：像素网格上的近似

无论显示器分辨率多高，最终显示的字、线、面，都是由离散像素组成的。每一条直线都可以用连续数学方程描述，但屏幕只能显示离散的点。想象在一张方格纸上画一条斜线，你可能需要把某些格子涂黑，而这些格子不可能严格组成一条“数学上粗细为0”的直线，只能是一种视觉近似。这个过程在图形学里叫光栅化（Rasterization），直线光栅化就是其中最基础的一环。

由此带来的核心问题是：根据直线的几何方程，每一步应该选哪个像素点？选点选得准，直线看起来就平滑、均匀；选得不准，就会出现“阶梯状”锯齿，或者某些位置明显偏粗、偏细。所以直线生成算法的好坏，直接影响画面质量。

1.2 直线方程的三种常用表达

先从数学源头说起。给定起点(x0, y0)和终点(x1, y1)，最常见的直线方程形式是：

• 斜截式：y = kx + b，其中k为斜率，b为截距。
• 两点式：(y - y0) / (y1 - y0) = (x - x0) / (x1 - x0)
• 隐式方程：F(x, y) = y - kx - b = 0

初学的时候，最容易想到的做法是：遍历x从x0到x1，每次用y = kx + b算出对应的y值，然后四舍五入取整，得到像素坐标。听起来很直接，但问题也很明显：每一次都要做一次浮点乘法、一次浮点加法和一次取整，CPU要付出不小的代价。更麻烦的是，当斜率大于1时，按x步进去采样，相邻像素之间的竖直间隔会大于1，画出来的点会“断开”。所以纯粹用逐点计算是低效且不健壮的。

1.3 评估直线算法的三个标准

任何一条直线生成算法，衡量它好坏基本就看三件事：

1. 速度：需要的运算次数多不多，尤其是浮点运算、乘法运算多不多。
2. 精度：生成的像素点与理想直线之间的偏差够不够小，会不会出现明显失真。
3. 内存/硬件友好性：算法得多大的存储空间？能不能方便地移植到嵌入式和硬件实现？

DDA把增量思想引入直线渲染，避免了每步重复计算乘法和一次方程；Bresenham更进一步，用整数运算代替浮点运算，把误差控制在一个像素以内。理解了这三个标准，你就能看懂为什么后面每步优化都是冲着“减少浮点计算、增加整数运算”去的。

2. DDA算法：用增量思想绕开浮点乘法

2.1 核心原理与公式推导

DDA的全称是Digital Differential Analyzer，数字微分分析器。名字听着有点吓人，其实思路很简单：与其每一步都回代直线方程求y，不如每次只在上一像素的基础上增加一个固定步长。

核心推导过程是这样的。假设直线从(x0, y0)到(x1, y1)，令dx = x1 - x0，dy = y1 - y0。如果dx和dy的绝对值都已知，那么总的步数steps等于|dx|和|dy|中较大的那个。让x方向的单步增量xInc = dx / steps，y方向的单步增量yInc = dy / steps。这样就保证：每一次循环结束时，当前点沿着直线前进的距离相同，无论斜率大于1还是小于1。

伪代码表达就是：

x = x0 y = y0 for i = 0 to steps: 在(round(x), round(y))处画点 x += xInc y += yInc

为什么要在|dx|和|dy|中取最大值作为steps？这是为了保证步长的合理性。假设一条线斜率极大，dy远大于dx。如果还按x方向步进，x每次只增加1，y却要跳好几步，生成的点之间就有很大的空洞。反过来按y步进，y每次加1，x每次增加一个较小的分数，就能保证点与点在屏幕上基本连续。所以取较大值就是“沿着变化更剧烈的轴均匀采样”。

2.2 C语言实现与要点说明

下面给出一个可以直接运行的C语言实现。我这里默认像素绘制函数是setPixel，屏幕坐标为整数。

#include <math.h> #include <stdlib.h> void drawLineDDA(int x0, int y0, int x1, int y1) { float dx = x1 - x0; float dy = y1 - y0; float steps = fabsf(dx) > fabsf(dy) ? fabsf(dx) : fabsf(dy); float xInc = dx / steps; float yInc = dy / steps; float x = x0; float y = y0; for (int i = 0; i <= steps; i++) { setPixel(roundf(x), roundf(y)); x += xInc; y += yInc; } }

有几个细节需要特别留意：

• 当dx为0时，steps等于|dy|，xInc为0，yInc为1或-1，代码能正确地画出一条竖直直线，不需要单独特判。
• roundf取整比强转int更稳妥。C语言里(int)(y + 0.5)也能达到四舍五入效果，但对负数要格外小心，建议直接用roundf。
• steps要声明为float，否则dx / steps会变成整数除法，导致结果错误。

我初学的时候在这里吃过亏，把steps写成float，但xInc、yInc却用int类型接收，结果画出来的线完全靠左、靠右偏移。DDA的核心就在于用浮点数保存每一步的增量，用int类型保存中间结果，等于白算。

2.3 DDA的优缺点分析

先说优点：实现非常简单，思想直观，不容易写出逻辑错误。它天然支持任意方向、任意斜率的直线，不需要把情况拆分成八分法来处理。另外，它每一步只做加法，不再做乘法和解方程，比最朴素的y = kx + b逐点计算快得多。

再说缺点，这部分在实际项目中很致命：

• 浮点累加误差。每步都做浮点加法，跑几千步后，误差会慢慢累积，导致直线的末端位置偏移，视觉上就是终点对不上。
• 取整误差。即使单步浮点误差很小，roundf每次仍会引入一个像素内的偏差，累计后可能让线条在某些区域看起来粗细不均。
• 性能瓶颈。浮点加法和取整运算还是比整数运算贵，尤其在嵌入式设备或老式GPU上，浮点单元非常金贵。

所以，DDA适合作为教学入门和快速原型验证，如果在追求极致性能的底层渲染代码里直接用，往往不是最优选择。

3. Bresenham算法：纯整数运算的经典方案

3.1 从“选哪边”到“决策参数”

Bresenham算法由Jack Bresenham在1965年提出，核心目标就是摆脱浮点运算和乘法，只靠整数加法和比较就能选出正确的像素点。它的思路可以理解成“每一步都做一次小决策”。

先考虑最简单的情况：斜率在0到1之间，即0 <= k <= 1，x每次递增1。假设当前像素是(x_i, y_i)，那么下一步x_i+1 = x_i + 1，候选的y只有两种：要么还是y_i，要么是y_i + 1。问题变成：怎么判断该选下方点还是上方点？

这里自然的想法是：比较直线实际经过的位置，也就是在x_i+1处理想直线的y值，离这两个候选像素的中点多远。这个中点坐标是(x_i + 1, y_i + 0.5)。把中点代入直线的隐式方程F(x, y) = y - kx - b，如果结果为负，说明中点在直线上方，直线更靠近下方的y_i点，选y_i；如果结果为正或0，选y_i+1。这样就把选点问题转换成了符号判断问题。

3.2 决策常量的递推推导

接下来要做的是把这个判断变成增量形式。定义决策参数p_i = Δx * (y_i - y0) - Δy * (x_i - x0)，其中Δx = x1 - x0，Δy = y1 - y0，都是整数。用中点条件代入整理，可以推出：

• 初始值：p_0 = 2Δy - Δx
• 当p_i < 0时，选下方点，且p_{i+1} = p_i + 2Δy
• 当p_i >= 0时，选上方点，且p_{i+1} = p_i + 2Δy - 2Δx

这里的推导过程虽然看着代数味很重，但结果非常漂亮：整个循环里只有整数乘法（其实都可以写成加法）、整数比较和常数增量。p_i的正负就是决策信号。每步要做的只是两次整数加法和一个分支判断，几乎没有浮点参与。

下面给出针对0 <= k <= 1情况的代码示例：

void drawLineBresenham_0_1(int x0, int y0, int x1, int y1) { int dx = x1 - x0; int dy = y1 - y0; int p = 2 * dy - dx; int y = y0; for (int x = x0; x <= x1; x++) { setPixel(x, y); if (p < 0) { p += 2 * dy; } else { p += 2 * dy - 2 * dx; y++; } } }

代码逐行看下来，循环体内没有做任何浮点转换，也没有除法运算，所以速度比DDA快很多。这也是为什么它在那个浮点运算昂贵的年代成为霸主，直到今天，在很多软渲染器和微控制器驱动中依然能看到它的身影。

3.3 扩展到全部八分方向

现实中的直线可不是只有0到1的斜率，可能是负斜率、竖直方向、水平方向，甚至从右往左画。Bresenham的经典实现通常要配合“八分法对称映射”来完善。

核心处理策略是：

• 按dx和dy的绝对值大小，判断主轴是x还是y。如果|dx| >= |dy|，就沿x方向步进；否则交换x和y的角色，沿y方向步进。
• 按照起终点坐标差值的符号，决定每个方向是递增还是递减。

我给出一个能处理任意方向、非抗锯齿的通用版本，这是实际开发中我比较常用的一种写法：

void drawLineBresenham(int x0, int y0, int x1, int y1) { int dx = abs(x1 - x0); int dy = abs(y1 - y0); int sx = x0 < x1 ? 1 : -1; int sy = y0 < y1 ? 1 : -1; int err = dx - dy; while (1) { setPixel(x0, y0); if (x0 == x1 && y0 == y1) break; int e2 = 2 * err; if (e2 > -dy) { err -= dy; x0 += sx; } if (e2 < dx) { err += dx; y0 += sy; } } }

这个版本的逻辑要点在于err变量保存的是当前点与理想直线之间的偏差，e2则用来同时判断x方向和y方向是否需要更新。它用一个循环统一处理了八种方向，代码量少且健壮。我在项目里画连线图时，基本都是直接复制这个函数，实测很稳。

需要注意的是：这个版本的决策变量与前面0到1斜率版本的p不完全一样，它把dx - dy作为初始偏差，每次用e2分别和-dy、dx比较来更新x和y。两种写法本质相通，都是整数决策，只是一个按斜率分类，一个用偏差统一判断。

4. 两种算法的对比与选型参考

4.1 直观对照表

为了方便你快速了解两者差异，我把核心对比整理成一张表：

这张表的核心结论是：如果只是临时画一条线，两者差别不大；但如果要在一个高性能循环里大量画线，Bresenham的整数运算几乎是唯一选择。

4.2 实际项目中的选择经验

我在写一个模拟项目X的软件渲染器时，一开始用的是DDA，因为写的快，调试起来也省心。但后面画面里的线条一多，性能就明显下滑，尤其在高DPI渲染下，浮点roundf的开销被放大得很厉害。换成Bresenham后，帧率提升肉眼可见。从那以后，凡是渲染循环里需要快速画线的场合，我默认都是Bresenham。

但这不代表DDA一无是处。如果你要做的是给某个可视化演示工具临时画草图，或者代码讲究可读性和易维护性，DDA的简单直白反而是优点。我也见过有人在做自动化测试时用DDA作为“标准答案”，因为它的坐标计算结果更容易被理解和验证。

另外还有一点值得提：DDA的浮点步进，对某些坐标变换场景，比如给直线附加粗细、渐变、透明效果时，反而比Bresenham更灵活。因为Bresenham导出的信息只有“该不该换y”，而DDA天然保留了每一步的小数位置，可以方便地用于后期插值。所以选型没有绝对，要看你手头任务的衡量标准。

5. 实际开发中的常见问题与优化细节

5.1 直线断开、锯齿明显：检查斜率处理

很多初学者写DDA时只处理了|k| <= 1的情况，结果遇到|k| > 1的直线就出现断点。这其实是步进方向选错了。任何实现里都必须根据dx和dy的相对大小选择主轴，DDA用steps取max(|dx|,|dy|)来解决；Bresenham通用版则用abs(dx)和abs(dy)的比较以及e2判断来覆盖。

如果画出来的线看起来“特别粗”，通常是每步连续在相邻两行像素都画了重复点。这种情况更多是坐标系或起点终点定义的问题，可以检查一下起终点是否重复、步进方向是否会影响边界条件。

5.2 整数溢出与起终点反向

决策参数p、err这些值会随着循环不断累加。如果屏幕分辨率很大，比如4K甚至8K，dx和dy可能达到几千甚至上万，2 * dx就可能超过16位int的范围。在嵌入式平台尤其常见，因为那里的int往往是16位。解决方法是改用long或long long，或者在每次累加前将增量除以2来压缩数值范围。但要注意压缩后可能会导致最终偏差阈值判断不准确，所以最稳妥的还是换宽数据类型。

还有一种常见情况是起点和终点顺序颠倒。有些调用方给的x0 > x1，如果不做处理，直接进入只支持从左到右的简单版Bresenham，就会导致循环条件根本不成立，什么都画不出来。通用版本里的sx、sy变量就是为了解决这个问题，一个通过判断起点和终点的位置关系自动设置步进方向。所以写调用代码时，尽量让算法自己适配方向，而不是在外部强行翻转坐标。

5.3 从走直线到抗锯齿：后续扩展

DDA和Bresenham画出来的直线都有明显锯齿，这是像素离散化的固有产物。实际图形应用中，更常见的需求是画平滑抗锯齿线。这时通常会在Bresenham的基础上引入灰度级：根据像素中心与理想直线的距离，计算一个0到1的覆盖度，然后把像素涂成部分透明或部分亮度。

其中最经典的是Wu算法，也就是“双像素抗锯齿算法”。它的思想是：每一列不只点亮一个像素，而是点亮上下两个像素，亮度按距离来分配。这个算法同样是建立在整数决策基础上，相当于Bresenham思想的一个自然延伸。如果你把这两条基础算法吃透了，后面理解Wu抗锯齿会非常轻松。

5.4 性能优化的两个小实践

第一，尽量让Bresenham循环体短小。避免在循环内调用函数，把setPixel内联展开；如果绘制的目标是一个帧缓冲区数组，可以直接写成frameBuffer[y * width + x] = color;，省去函数调用开销。

第二，对于大批量直线渲染，可以用对称映射。前面的Bresenham通用版其实已经隐含了对称性，但如果你针对硬件实现，更常见的做法是只实现第一象限0到1斜率的核心循环，其余七种斜率全部通过坐标交换和取负映射到核心循环。这样做的好处是核心循环可以被极致优化，甚至用指令集加速，而外围只做坐标变换。

我在一个ARM嵌入式项目里写过这种方式。把通用Bresenham换成八分法映射版本后，画线速度提升了大约20%。因为每次循环里分支预测变简单了，而且减少了同时更新x和y的路径。

6. 一点个人心得

如果只是背下这两段代码，过半年再写，多半还是懵。我自己的经验是，DDA的真正价值在于帮你建立“增量计算”的概念，而Bresenham的价值在于那种“用符号判断替代浮点运算”的思路。图形学里很多后续算法，从画圆到多边形填充，再到纹理采样中的双线性插值，都受这两种思想影响很深。

建议你亲自在纸上把Bresenham的决策参数推一遍，哪怕只是0到1斜率的那种简单情况。动手推一遍，比看十篇文章都管用。我当时就是在纸上推了半小时，突然就明白了为什么p要初始化为2dy - dx，为什么累加量分别是2dy和2dy - 2dx。这些东西光靠眼睛看代码，很难真正成为你自己的。

另外，写代码时多留几个测试用例。我习惯把起点、终点设置成各种边界情况：正斜率、负斜率、竖直、水平、反向、跨越大坐标。每改一次算法实现，就跑一遍这些用例，能省下很多调试时间。最后再分享一个小技巧：如果你用的是通用Bresenham版本，记得把err和e2声明成int，别手滑写成float，否则性能优势全没了。