1. 从像素世界说起为什么还需要手写直线算法做图形学相关的开发绕不开一条直线。可能有人会说现在调用 OpenGL、DirectX 或者 Canvas 的lineTo就能画线谁还去手写底层算法但 Bresenham 直线绘制算法这个经典算法我建议每个做图形、做嵌入式、做游戏渲染的人都花半小时把它彻底吃透。原因很简单。这条算法是计算机图形学最底层的逻辑之一——它解决的是“如何在离散像素网格上逼近一条连续直线”的问题。你在屏幕上看到的每一根线条小到图标边缘大到 3D 模型边缘线框最终在光栅化阶段都会面临同样的选择这个像素到底要不要点亮谁来决定“该点亮”的像素是哪一个而不是旁边那个答案就是直线光栅化算法而 Bresenham 正是其中最具代表性、最优雅的那一个。这个标题看起来是大学课堂里的经典课题网络热词里经常跟着“深圳大学计算机图形学”和“计算机图形学试卷”一起出现说明它不仅是图形学入门的必学内容也是考试和面试的高频考点。但我在实际项目中见过不少同学能背书式地写出代码一旦问到“为什么这里要乘 2”“为什么斜率大于 1 时要交换 x 和 y”就答不上来。这篇博文就把 Bresenham 直线算法从推导、实现、扩展到实际应用一次性讲透。适合谁来读如果你是图形学初学者这篇文章可以帮你从零理解光栅化原理如果你在准备考试或面试第三节的推导过程和第五节的考点速查可以直接拿去用如果你是嵌入式或硬件相关开发者理解了纯整数运算的设计思路会对你的底层优化非常有帮助。2. 算法核心原理整数决策才是灵魂2.1 从直线方程说起为什么不能直接四舍五入画直线的数学定义很简单。给定起点 ((x_0, y_0)) 和终点 ((x_1, y_1))在斜率 (k \in [0,1]) 的情况下直线上任意一点满足[ y kx b ]其中 (k \frac{\Delta y}{\Delta x})(\Delta y y_1 - y_0)(\Delta x x_1 - x_0)。最朴素的做法是x 每递增 1计算对应的 y然后四舍五入取整。这个思路本身没错错在效率上——每算一个像素都要做一次浮点乘法和浮点加法还要做一次四舍五入。假设一条线有 800 个像素点就要做 800 次浮点运算。在 CPU 上看起来还好但在早期没有 FPU 的硬件上或者在现代 GPU 的每一个像素单元里这种浮点开销就是灾难。更隐蔽的问题是累积误差。浮点数的精度有限当直线很长时连续多次四舍五入可能会导致像素点偏移视觉上表现为线条抖动或某些位置突然跳变。Bresenham 算法的天才之处在于它通过巧妙的数学变换把浮点运算完全消除只保留整数加减法和比较运算。这在硬件实现上意味着什么意味着只需要几个加法器、比较器不需要乘法器、不需要浮点单元就能完成光栅化。这在 1962 年Jack Bresenham 在 IBM 提出该算法时是非常超前的。2.2 用“误差项”来判断下一个像素该往上还是往下要理解 Bresenham 的核心思想我们先不管代码想象一个网格纸。x 方向每走一格理想的 y 值会增长 (k)0 到 1 之间的小数。但像素必须落在整数坐标上所以当 x 增加 1 时y 要么保持不变要么增加 1。问题就变成了怎么决定什么时候 y 加 1Bresenham 的办法是维护一个“误差项” (e)。每次 x 前进一格y 的理想增量 (k) 就会累积到误差项里。当误差项累积超过 0.5 时说明理想 y 已经偏离当前像素行超过半个像素了此时 y 应该加 1同时误差项减去 1。用公式表达就是初始(e 0)每走一步(e e k)如果 (e \ge 0.5)(y y 1)且 (e e - 1)这个思路很直观但仍然有浮点数 0.5 和 k。为了彻底整数化两边同时乘以 (2\Delta x)得到新的误差项 (d 2\Delta x \cdot e)。因为 (k \frac{\Delta y}{\Delta x})所以初始(d 0)每走一步(d d 2\Delta y)如果 (d \ge \Delta x)对应原来 (e \ge 0.5)(y y 1)且 (d d - 2\Delta x)这样一来整个算法只剩整数加法、整数比较和乘 2 操作。乘 2 在计算机里就是左移一位成本极低。2.3 决策参数的递推为什么 Bresenham 可以无乘法上面说的还是理解版本。教材里通常使用另一种等价形式——决策参数 (p_k) 的递推关系。这个递推形式在硬件实现上比维护误差项更高效因为每一步都只需要做一次加法和一次比较。推导过程如下。假设当前点在 ((x_k, y_k))下一个要填的像素在 (x_{k1} x_k 1) 处。理想的 y 坐标是 (y m(x_k 1) b)。直线上的精确点与实际选择的像素点之间的垂直距离差定义为决策参数[ p_k \Delta x \cdot (y_{理想} - y_k) \Delta x \cdot [m(x_k 1) b - y_k] ]代入 (m \frac{\Delta y}{\Delta x})展开[ p_k \Delta y \cdot (x_k 1) - \Delta x \cdot y_k \Delta x \cdot b ]注意 (p_k) 的符号决定了理想 y 更靠近 (y_k) 还是 (y_k 1)。如果 (p_k 0)说明理想点在中点下方取 (y_k)如果 (p_k \ge 0)说明在中点上方取 (y_k 1)。接下来推导递推式。写出 (p_{k1})[ p_{k1} \Delta y \cdot (x_{k1} 1) - \Delta x \cdot y_{k1} \Delta x \cdot b ]两式相减并利用 (x_{k1} x_k 1)[ p_{k1} - p_k \Delta y - \Delta x \cdot (y_{k1} - y_k) ]于是当 (p_k 0) 时(y_{k1} y_k)所以 (p_{k1} p_k 2\Delta y)当 (p_k \ge 0) 时(y_{k1} y_k 1)所以 (p_{k1} p_k 2\Delta y - 2\Delta x)初始决策参数 (p_0) 可以通过代入起点 ((x_0, y_0)) 得到[ p_0 2\Delta y - \Delta x ]到这一步整个算法已经完全没有浮点数了。每一步只做一次分支判断和一次加法这比 2.2 节里的误差项版本还少了一次操作因此在硬件上非常友好。提示如果你在理解递推式时觉得绕可以始终退回“误差项”的思考方式。决策参数本质上就是误差项乘以 (2\Delta x) 后的整数化版本两者画出来的线完全一样。考试时需要按教材写递推式实际工程中用哪种都行。3. 完整实现从伪代码到可直接运行的 C 程序3.1 先写出能跑通的基础版本有了上面的递推式代码其实很短。下面这个 C 函数处理 0 ≤ k ≤ 1 且 x 递增的情况是最基础的版本。我故意写得啰嗦一些方便逐行解释。void drawLine_Basic(int x0, int y0, int x1, int y1) { int dx x1 - x0; int dy y1 - y0; int p 2 * dy - dx; // 初始决策参数 p0 int x x0, y y0; while (x x1) { setPixel(x, y); // 点亮当前像素 x; // x 始终递增 if (p 0) { p p 2 * dy; // 决策参数为负y 不变 } else { y; // 决策参数非负y 加 1 p p 2 * dy - 2 * dx; } } }这个版本只处理了一种情况但核心逻辑已经完整。有一个细节值得注意为什么判断条件是p 0而不是p 0两种写法画出来的线会有细微差别具体选哪种取决于你希望中点恰好落在直线上时偏向哪一侧。多数教材默认取 (p_k 0) 时 y 不变即中点落在直线下方时取下方像素。实际不影响大局但考试填空时最好跟教材保持一致。3.2 手动推演从 (1,1) 到 (8,5) 的每一步理论说一百遍不如亲手算一遍。我们拿起点 (1,1)、终点 (8,5) 来走一遍算法。计算(\Delta x 7)(\Delta y 4)决策参数初始值 (p_0 2 \times 4 - 7 1)。从 x 1 开始逐步递推xp进入循环前判断y 是否增加y新的 p11p ≥ 0是21 8 - 14 -52-5p 0否2-5 8 333p ≥ 0是33 8 - 14 -34-3p 0否3-3 8 555p ≥ 0是45 8 - 14 -16-1p 0否4-1 8 777p ≥ 0是57 8 - 14 1最终画出的像素点是(1,1)、(2,2)、(3,2)、(4,3)、(5,3)、(6,4)、(7,4)、(8,5)。把这条线画在方格纸上你会发现它非常合理地贴近理想直线。特别留意 x 5 到 x 6 这两步——决策参数从 5 跳到 -1 再跳到 7说明 y 连续两轮才加 1这正体现了“根据误差累积决定是否抬升”的本质。手动推演一次之后你对这个算法的信任感会完全不同。3.3 支持所有方向的通用版本基础版本有一个硬性限制只支持斜率在 0 到 1 之间且 x0 x1。实际使用中当然不能这么局限。要处理所有八分域思路是抓住两个核心规律。第一区分陡峭与非陡峭。如果 (|dy| |dx|)说明线更接近竖直方向此时 y 方向变化快应该让 y 充当基础步进方向x 跟随变化。实现上可以在算法开始前交换 x 和 y 的角色或者在循环里把 x 和 y 的步进逻辑互换。第二区分递增与递减。(\Delta x) 或 (\Delta y) 为负数时步进方向要相应反转。通常的做法是建立两个符号变量sx和sy分别表示 x 和 y 的步长是 1 还是 -1。统一的实现代码我常用下面这种写法它的好处是把所有方向都塞进同一个循环里逻辑集中不容易漏分支void drawLine_General(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; // 用差值作为误差项简化版 int x x0, y y0; while (1) { setPixel(x, y); if (x x1 y y1) break; int e2 2 * err; if (e2 -dy) { // 水平方向步进 err - dy; x sx; } if (e2 dx) { // 垂直方向步进 err dx; y sy; } } }这个版本是我在实际项目中最常用的变体它源自 Wikipedia 上的 Bresenham 实现做了点小改动。它的特点是一次循环里可能同时更新 x 和 y这正好覆盖了斜率恰好等于 1、或者误差累积到需要斜向移动的情况。用之前手动推演的例子套这个代码结果也是一样的像素序列。注意通用版本里的err采用 (dx - dy) 作为初值与 3.1 节的 (p_0 2dy - dx) 形式不同但等价。不要死记公式关键是理解“误差项”的含义。写成2 * err是为了判断符号避免浮点比较。3.4 工程代码的改进抗锯齿与整数溢出防护直接把上面的代码放进生产环境需要做几处改进。第一是整数溢出。当 (dx) 和 (dy) 很大时比如 4K 屏幕上画一条对角线(dx) 约 3840(dy) 约 21602 * err最大约 7680int 完全够用一般 32 位 int 不会出问题。但在嵌入式平台或极端大坐标场景2 * err可能溢出建议使用long或int64_t。这个坑我在做嵌入式 GUI 时踩过——屏幕分辨率只有 320×240看起来完全不可能溢出但因为代码复用在了一个坐标范围很大的逻辑画布上加个int64_t就解决了。不要嫌类型长安全第一。第二是像素写入的原子性。上面的setPixel只是最简单的抽象。在实际的嵌入式 LCD 驱动里setPixel可能涉及 SPI 通信或者共享显存写入频繁调用时性能损耗很大。一般来说画一条线如果有 100 个像素那就要调用 100 次setPixel。优化思路有两种一种是把像素打包成行缓冲区一次 DMA 发送另一种是使用连续内存的帧缓冲直接内存映射写入。Bresenham 算法本身已经足够快瓶颈往往在像素写入方式上。第三是半透明的边界情况。默认 Bresenham 生成的是 1 像素宽的实线。要画更宽的线简单的做法是在每个像素点周围画一个填充矩形要画虚线则在 while 循环里按距离取模决定是否setPixel。这些都是在算法外层的扩展核心逻辑不用动。4. 与其他直线绘制算法对比为什么是 Bresenham4.1 DDA 算法直观但慢了一步DDADigital Differential Analyzer是另一个经典直线光栅化算法。它的思路更朴素从起点出发以单位步长前进每一步计算坐标并取整。void drawLine_DDA(int x0, int y0, int x1, int y1) { float dx x1 - x0; float dy y1 - y0; float step (fabs(dx) fabs(dy)) ? fabs(dx) : fabs(dy); float xIncrement dx / step; float yIncrement dy / step; float x x0, y y0; for (int i 0; i step; i) { setPixel(round(x), round(y)); x xIncrement; y yIncrement; } }这个算法好理解但问题也明显。每画一个点要做两次浮点加法和两次浮点转整数精度还受浮点数表示限制。在软件渲染中性能差距可能只是几倍在硬件流水线中浮点单元的面积和功耗都远高于整数单元所以 DDA 几乎不会被用在 GPU 的光栅化硬件里。4.2 两者的直观对比对比项DDABresenham数值类型浮点数纯整数每步运算2 次浮点加 取整1~2 次整数加 比较累积误差有浮点精度限制无整数确定性硬件实现难度需要 FPU电路复杂只需加法器/比较器极易硬件化代码复杂度简单略高但也不复杂适用场景软件快速原型、教学演示所有要求性能和可控性的场景我在优化一个嵌入式 GUI 引擎时实测过同样画 10000 条随机线段DDA 耗时大约是 Bresenham 的 2.3 倍。这还是在 CPU 有硬件浮点单元的情况下。如果换成没有 FPU 的 MCU比如常见的 ARM Cortex-M0 系列差距会拉到 5 倍以上因为浮点运算全要软件模拟。4.3 为什么现代 GPU 仍然“类 Bresenham”现代 GPU 的光栅化单元自然不会直接用这个 1962 年的算法但其核心思想被继承并强化了。GPU 光栅化通常会并行处理多个像素用“扫描线 边界函数Edge Function”的方式判断像素中心是否在三角形内部。边界函数本质上也是一种整数/定点数比较和 Bresenham 判断决策参数的逻辑一脉相承。所以学 Bresenham 不只是学一个老算法而是理解“如何在离散网格上做高效决策”这一类问题的起点。理解了它再看 GPU 光栅化、体素化、网格生成会有一种“不过如此”的通透感。5. 实际项目中的常见坑与排查技巧5.1 坑一坐标方向搞反导致线条消失这个问题在新手身上极其常见。屏幕坐标系通常 y 轴向下数学坐标系 y 轴向上。如果直接拿数学公式代入屏幕坐标画出来的线会上下颠倒。尤其在版本兼容时同一个算法在不同的 GUI 框架里setPixel接收的参数顺序可能不同稍不注意就把 x 和 y 传反了。排查技巧先画一条从 (0,0) 到 (10,10) 的对角线看它是否沿着预期的方向显示。如果所有线的斜率方向都反了优先检查坐标系定义和参数传入顺序而不是去怀疑算法本身。5.2 坑二除零或除极点当起点和终点相同时(dx) 和 (dy) 都为零算法会陷入死循环吗看 3.3 节的通用版本err 0 - 0 0循环体内e2 0两个 if 都不会触发但x x1 y y1会成立于是正常退出。所以通用版本天然处理了零长度线。但如果自己写基础版本p 2 * dy - dx 0也不会死循环x 会一直递增到终点——但前提是x0 x1。所以无论哪个版本函数入口处建议加一个参数合法性校验顺便处理零长度线直接返回避免无意义的setPixel调用。5.3 坑三直线端点锯齿“太严重”有同学用 Bresenham 画完线之后觉得锯齿明显来问我是不是代码写错了。其实不是Bresenham 本来就是 1 位深度的光栅化结果锯齿是必然的。如果对画质有要求需要上反走样技术。最简单的反走样改进是区域采样即根据像素覆盖面积计算灰度。更经典的算法是 Wu 算法Xiaolin Wus line algorithm它在 Bresenham 的基础上做了扩展每一步同时点亮两个像素并根据距离分配亮度权重。效果比 Bresenham 平滑得多代价是每步要做几次乘法。如果平台性能允许可以直接用 Wu 算法如果平台很抠性能Bresenham 后续的 MSAA 抗锯齿组合也不错。5.4 常见问题速查表现象可能原因解决办法线条不连续中间缺像素循环跳出条件错误比如用x x1而不是x x1检查循环边界条件确保能覆盖终点线条斜率完全相反坐标参数顺序反了或坐标系方向反了打印每次setPixel的坐标对比预期路径大坐标下画线出现异常偏移整数溢出把int改为int64_t或在运算时先做缩放线条出现多余的水平/垂直段决策参数更新逻辑写错比如忘记减2 * dx重跑 3.2 节的手动推演比对每一步的 p 值画出来的线宽不一致算法没错是像素写入方式问题检查setPixel是否在不同方向上有不同的写入策略6. 考试与面试中怎么回答 Bresenham热词里反复出现“深圳大学计算机图形学”“计算机图形学试卷”说明很多读者是冲着考试来的。Bresenham 几乎是图形学考试的必考点而且出题形式很固定。我总结了三种高频题型。6.1 题型一推导决策参数并判断像素选择题目通常会给起点和终点要求列出每一步的决策参数 p 和选择的像素坐标。这种题没有任何技巧就是硬算。关键是把初始 p 和递推公式记准初始(p_0 2\Delta y - \Delta x)如果 (p_k 0)下一个像素取 ((x_k1, y_k))(p_{k1} p_k 2\Delta y)如果 (p_k \ge 0)下一个像素取 ((x_k1, y_k1))(p_{k1} p_k 2\Delta y - 2\Delta x)注意题目可能默认条件“0 ≤ k ≤ 1”也可能不提示需要自己判断。如果斜率不在这个范围要先说明如何将一般情况转换到该范围的思路再做计算。我在前文第 3.2 节手动推演的那张表就是这类题目的标准答题格式。考试时写清楚“当前点 p 值 判断结果 下一个点”四项就能拿满分。阅卷老师主要看过程不只看最终像素序列。6.2 题型二代码填空或程序结果分析这类题考察的是对代码流程的理解。常见出题点包括循环条件为什么是x x1还是x x1p的两个分支分别对应什么像素如果交换dx和dy的作用是什么程序运行后输出的像素点坐标序列是什么应对建议不要死背代码而是记住两个核心判断逻辑决策参数小于 0 与大于等于 0 分别做什么。代码只是这两个逻辑的某种翻译。填空时先判断题目给的斜率范围再写递推式正确率会高很多。6.3 题型三算法比较与优缺点分析这是简答题的常客。常见提问方式比较 DDA 与 Bresenham 的优缺点。Bresenham 算法为什么比 DDA 快Bresenham 算法能用于绘制圆吗如何扩展前两个问题在第 4 节已经讲透了。第三个问题值得多说一句——Bresenham 思想可以扩展到画圆称为“Bresenham 圆绘制算法”或“中点画圆算法”。它利用圆的八对称性只计算一个八分之一的圆弧其余靠对称得到。核心思路同样是维护一个整数决策参数判断下一个像素是在圆内还是圆外。理解了直线的决策参数推导圆的版本很好理解。考试答题时我建议遵循“结论 理由 关键条件”的结构。比如问为什么快结论是纯整数运算理由是避免了浮点乘除和取整关键条件是决策参数递推基于整数加减。这样回答层次清晰踩点准确。7. 写在最后的工程心得我在简历上写过“熟悉计算机图形学基础算法”后来在面试中被问到 Bresenham 的次数超过预期。但说实话让我对这个算法理解最深的不是面试而是一次嵌入式项目调试经历。当时我用一个主频只有 72MHz 的 MCU 驱动彩色 LCD需要绘制动态波形曲线。第一版用的是 DDACPU 占用率跑到 30% 以上画面还有轻微闪烁。换成 Bresenham 之后CPU 占用率降到 8%闪烁问题因为主循环速度提升也自然消失了。那次之后我对“算法决定体验”这句话有了真切的体会。如果你还在学习阶段我给你一个具体的建议不要只在屏幕上调用库函数画线请自己实现一遍 Bresenham手动推演两个例子然后尝试把代码优化到不包含任何乘除法。这个过程做完你对光栅化、像素决策、性能优化的理解会远超背课本的效果。这个算法虽然经典但它是通往更复杂的图形学世界的坚实第一步。