DDA与Bresenham：直线光栅化中的像素选点算法

刚接触计算机图形学的时候我有个挺大的疑惑屏幕上明明是一块一块的像素为什么能显示斜滑的直线后来才明白所谓画直线本质是一个“选点”的过程。把理想直线映射到一张像素网格上挑那些离直线最近的像素点亮视觉上就形成了一条直线。这个“选点”的算法最常见也最经典的两个就是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 评估直线算法的三个标准任何一条直线生成算法衡量它好坏基本就看三件事速度需要的运算次数多不多尤其是浮点运算、乘法运算多不多。精度生成的像素点与理想直线之间的偏差够不够小会不会出现明显失真。内存/硬件友好性算法得多大的存储空间能不能方便地移植到嵌入式和硬件实现DDA把增量思想引入直线渲染避免了每步重复计算乘法和一次方程Bresenham更进一步用整数运算代替浮点运算把误差控制在一个像素以内。理解了这三个标准你就能看懂为什么后面每步优化都是冲着“减少浮点计算、增加整数运算”去的。2. DDA算法用增量思想绕开浮点乘法2.1 核心原理与公式推导DDA的全称是Digital Differential Analyzer数字微分分析器。名字听着有点吓人其实思路很简单与其每一步都回代直线方程求y不如每次只在上一像素的基础上增加一个固定步长。核心推导过程是这样的。假设直线从(x0, y0)到(x1, y1)令dx x1 - x0dy y1 - y0。如果dx和dy的绝对值都已知那么总的步数steps等于|dx|和|dy|中较大的那个。让x方向的单步增量xInc dx / stepsy方向的单步增量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每次只增加1y却要跳好几步生成的点之间就有很大的空洞。反过来按y步进y每次加1x每次增加一个较小的分数就能保证点与点在屏幕上基本连续。所以取较大值就是“沿着变化更剧烈的轴均匀采样”。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为0yInc为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 1x每次递增1。假设当前像素是(x_i, y_i)那么下一步x_i1 x_i 1候选的y只有两种要么还是y_i要么是y_i 1。问题变成怎么判断该选下方点还是上方点这里自然的想法是比较直线实际经过的位置也就是在x_i1处理想直线的y值离这两个候选像素的中点多远。这个中点坐标是(x_i 1, y_i 0.5)。把中点代入直线的隐式方程F(x, y) y - kx - b如果结果为负说明中点在直线上方直线更靠近下方的y_i点选y_i如果结果为正或0选y_i1。这样就把选点问题转换成了符号判断问题。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_{i1} p_i 2Δy当p_i 0时选上方点且p_{i1} 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 直观对照表为了方便你快速了解两者差异我把核心对比整理成一张表对比项DDA算法Bresenham算法主要运算浮点加法、取整整数加法、比较是否有浮点依赖是否误差来源浮点累加误差几乎没有累积误差单步计算量较大很小实现复杂度简单中等适合硬件实现一般非常合适典型应用场景教学、快速原型软件渲染、嵌入式、硬件光栅器这张表的核心结论是如果只是临时画一条线两者差别不大但如果要在一个高性能循环里大量画线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甚至8Kdx和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否则性能优势全没了。