刚接触计算机图形学的时候第一次作业就是画直线。当时心里想画一条线还不简单吗两个点一连不就行了等到自己上手做光栅化才发现事情远没那么容易。屏幕上是一个个离散的像素而数学上的直线是连续的怎么用离散的格子去逼近一条连续直线而且还要够快、够好看这就是直线生成算法要做的事。DDA算法和Bresenham算法是两座绕不过去的山。这篇文章我把两个算法的原理推导、代码实现、踩过的坑一次说清楚给正在学图形学或者准备自己写软件渲染器的朋友做个参考。1. 光栅化到底在解决什么问题1.1 从数学直线到屏幕像素在进入具体算法之前先建立一个认知框架。屏幕上所有的图形最终都要落到一个个像素点上这个过程就叫光栅化。显示器是一个像素矩阵每个像素要么亮要么不亮亮起来还有颜色深度之分它没有能力直接画出一条真正的连续直线。所以直线生成算法的本质就是解决一个问题已知线段的两个端点坐标在像素网格上选出一系列像素点让这些点排列起来在人眼看来就是一条直线。这句话看起来简单但细想就有很多讲究。选点太稀了线是断的选点太密了一个像素点重复画浪费性能选点偏了线会歪歪扭扭看起来像锯齿。好的直线生成算法要在精度、速度、资源消耗之间找到平衡点。我当年学到这里的时候犯过一个方向性的错误。我尝试用数学上最直接的方法已知斜率k和截距b从x0到x1循环每算一个y值就画一个点。这个思路本身没错但它有一个致命问题——浮点运算。每一次循环都要做一次浮点数乘法和加法在计算机图形学早期硬件没有FPU的年代这是不可接受的性能灾难。更重要的是当直线斜率大于1时按x步进会导致x方向每走一步y方向要跳好几个像素画出来的点之间出现明显的断口。这两个痛点正好对应了DDA算法产生的历史背景也引申出Bresenham算法对它的全面优化。1.2 算法评价的三个维度既然要对比两种算法就要先有一个统一的评价标准。做图形学的人公认有三个指标准确性生成的像素点跟理想直线之间的误差是否在可控范围内一般要求偏差不超过0.5个像素单位。高效性尽量避免乘除法最好连浮点运算都不要有只用整数加减法。均匀性像素点的分布要均匀。不管斜率是什么线的密度看起来要一致不能有的地方粗有的地方细。拿这三个指标去卡这两个算法就能看出端倪。你说DDA准确性还行均匀性也不错但高效性上输了一筹因为它每一步都逃不掉浮点累加。Bresenham则把操作压到了纯整数的加减比较效率是实打实的提升。这是算法演进的核心驱动力也是我当时理解得最透彻的一条线。2. DDA算法最直观的增量思路2.1 数字微分分析器的核心思想DDA全称是Digital Differential Analyzer翻译过来叫数字微分分析器。这个名字听起来很有距离感但它的思想朴素得不行。数学上我们习惯用y kx b来描述一条直线知道x求y。但这里面有个隐性的乘法操作每次都要算一遍。DDA的聪明之处在于它用增量思想把乘法变成了加法。想象一下你正沿着一条直线走路。你每往前走一小步dxy方向应该跟着走多少答案是dy k * dx。如果你让dx固定为一个像素那么y的增量其实就是k。这样一来计算过程就变成了y_{n1} y_n k每一步只需要做一次浮点加法把乘法彻底消掉了。这就是DDA名字里“微分分析器”的来历——差分方程y_{n1} - y_n k本身就是函数y对自变量x微分关系的离散版本。这个思想在图形学里处处可见。不只是直线曲线的生成、纹理映射里的UV插值、颜色渐变填充用的全是这个套路。搞懂了DDA的增量思想后面学一大堆东西都有如神助。2.2 斜率绝对值大于1时的处理这里有一个新手几乎必踩的坑。如果你拿斜率k小于1的情况去写程序按x方向步进1个像素y方向加k一切正常。但如果斜率是5也就是一条接近垂直的线你还按x方向步进会出现什么情况x每次只加1y却要跳5个像素。最后画出来的点就是稀稀拉拉几个孤立的点点与点之间的间距很大完全连不成一条线跟“密集恐惧症”发作一样。正确的做法是比较dx和dy的绝对值谁大就以谁为步进方向。如果dx dy说明直线更接近水平按x方向步进1y方向增加dy/dx的斜率如果dy dx说明直线更接近垂直按y方向步进1x方向增加dx/dy的倒数斜率。这个“按长轴步进短轴按比例增减”的原则是Bresenham算法里也沿用的核心思想。我称之为“长轴原则”后面推导Bresenham的时候还会用到。2.3 DDA算法代码实现把上面的原理用代码落一遍。为了清晰先处理简单情况再补全通用逻辑。我习惯用类C风格的伪代码因为图形学算法本身不依赖具体语言你用C、C、Python、JavaScript都能套这个逻辑。// DDA直线生成算法 // (x0, y0)为起点, (x1, y1)为终点 void drawLineDDA(int x0, int y0, int x1, int y1) { int dx x1 - x0; int dy y1 - y0; // 长轴原则确定步进方向 int steps abs(dx) abs(dy) ? abs(dx) : abs(dy); // 每步的增量 float xIncrement (float)dx / steps; float yIncrement (float)dy / steps; // 从起点开始 float x x0; float y y0; for (int i 0; i steps; i) { // 四舍五入到最近的像素中心 int px round(x); int py round(y); setPixel(px, py); // 点亮像素 x xIncrement; y yIncrement; } }这里有个细节值得说为什么画点的时候用round四舍五入而不是直接强转int强转int是向下取整。如果计算出的y是2.7你画在2这个像素上跟理想位置的偏差是0.7超过了0.5的误差容忍线。四舍五入之后画在3上偏差只有0.3。别小看这0.3的差距线画出来就是“平滑”和“总是偏一侧”的差别。很多入门代码为了省事直接用强转结果直线的视觉质量肉眼可见地差一截。DDA算法的优点一句话就能概括逻辑简单编码容易可读性好适合教学和理解。缺点就是逃不掉浮点运算。每画一个点都要做浮点加法还要做一次四舍五入。如果画几万条线性能瓶颈立刻暴露出来。而且浮点数的舍入行为在不同硬件平台上有细微差异可能导致同样代码在不同机器上画出不一样的结果。这个缺点正是催生Bresenham算法的直接原因。3. Bresenham算法纯整数运算的胜利3.1 从浮点到整数的优雅跨越Bresenham算法是1962年由Jack Bresenham在IBM工作时提出的。它最核心的贡献是把直线生成过程中的所有浮点运算全部化解为整数加减法和比较操作。这个思路的起点非常巧妙。不管斜率是0.2还是0.8在像素网格上做决策时核心问题只有一个x前进一个像素之后y应该停在当前行还是往上挪一行DDA的做法是算出精确的y值然后四舍五入。Bresenham的脑回路是我不需要知道y精确是多少我只需要知道它离当前像素中心近还是离下一个像素中心近。这个判断可以用纯粹的整数比较来完成。我举个例子帮助理解。假设当前已经画好了点(x, y)现在x方向往前走一步来到x1的位置。这时有两种选择画在y位置或者画在y1位置。设理想直线在x1处的y值跟y的差为d_upper跟y1的差为d_lower。如果d_lower d_upper说明理想点更靠近y1选它否则选y。这个d_lower和d_upper的差值经过一番代数变形之后可以得到一个递推公式。而且巧的是这个递推公式里的参数初始值和每一步的增量全是整数。3.2 决策参数的推导过程这里我推一遍因为理解了推导才能理解代码里那些神秘的参数是从哪来的也才能在遇到问题时自己排查。先约束一个场景斜率k在0到1之间。此时x方向是主轴每一步x都加1y要么不动要么加1。设直线方程为y kx b起点为(x0, y0)。定义决策参数p的初始值为p0 2Δy - Δx其中Δy |y1 - y0|Δx |x1 - x0|。每走一步根据p的正负做判断若p 0说明理想点更靠近当前y行y不变p更新为p 2Δy。若p 0说明理想点更靠近y1行y加1p更新为p 2Δy - 2Δx。整个过程只用到整数加法连一次浮点数计算都没有。初始值p0里连乘除法都没有只有乘2乘2在计算机里就是左移一位那更是快到极致。你可能会问这个2Δy和2Δx是怎么来的为什么偏偏是乘以2这其实是推导过程中消除分母的结果。原始的误差比较式里有一堆分数的加减为了不动浮点运算就通分乘上2Δx分母消掉之后剩下的系数自然就带着因子2。所以那个2不是拍脑袋定的是代数化简的必然结果。我把推导的逻辑链写一下。设当前点为(x_i, y_i)理想线上x_i1处的y值为y k(x_i1) b。定义误差项d_upper y_i 1 - y当前像素上边界到理想点的距离 d_lower y - y_i理想点到当前像素中心的距离判断条件是d_lower - d_upper 0化简后可得到用p_i递推的形式。为了丢掉分数的比较两边乘以2Δx就得到整数的p_i。整个过程不晦涩用心推一遍就通了。如果你第一次接触这个推导建议手写一遍过程。我当年就是在纸上把每一步变换都写出来心里才踏实不然总觉得代码里那几行像变魔术。3.3 Bresenham完整代码实现把推导结果写成代码// Bresenham直线生成算法 // 适用于斜率0 k 1的情况 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; // x方向步进 int sy (y0 y1) ? 1 : -1; // y方向步进 int err dx - dy; // 决策参数 int x x0; int y y0; while (x ! x1 || y ! y1) { setPixel(x, y); int e2 2 * err; if (e2 -dy) { // 沿x方向步进 err - dy; x sx; } if (e2 dx) { // 沿y方向步进 err dx; y sy; } } setPixel(x1, y1); }这个版本的代码有个巧妙之处它同时处理了8个卦限的情况。你没看错不只是第一象限的0到1斜率而是屏幕上任意方向、任意角度的线段都可以用这一套代码画出来。秘密就在sx和sy这两个符号变量里。dx和dy取了绝对值方向由sx和sy控制err的判别逻辑用的是对称形式。这样一来从(x0,y0)到(x1,y1)无论目标在哪个方向都能一路走一路画过去最终到达终点。这个通用版本比我刚才推导时限定的0到1斜率场景要强大得多。不过有一点要注意这个版本的err初始值是dx - dy判别条件是e2 -dy和e2 dx跟第一部分推的p初始值2Δy - Δx在形式上不完全一样。它们本质等价只是换了一种归一化写法。我建议初学者老老实实先把那一套0到1斜率的版本写熟、调通了再上这个通用版本。不然代码简洁了概念容易丢。3.4 为什么Bresenham更快做个简单的复杂度对比。假设要从(0,0)画到(1000, 500)。DDA算法要做1000次浮点加法每次还要把浮点数转成整数做像素坐标。在现代CPU上一次浮点加法大概是几个时钟周期转换还要费额外的指令。1000次或许感觉不明显但如果是游戏引擎每帧画几万条直线这个开销就会被放大到肉眼可见的性能差距。Bresenham算法只需要做1000次整数加法加整数比较。整数运算是几个时钟周期里就能完成的操作在某些没有浮点单元的嵌入式设备或旧的GPU硬件上差别更是天壤之别。还有一个细节值得注意Bresenham不涉及四舍五入操作。浮点四舍五入在硬件层面是一个相对昂贵的操作而Bresenham的判断是通过比较符号位完成的纯粹就是整数比较指令开销极低。我见过有些同学做软件渲染器画了一堆三角形最后发现性能瓶颈居然在直线光栅化里暗藏的浮点运算上。换成纯整数Bresenham之后帧率提升肉眼可见。这种优化看起来微不足道但在图形学领域积少成多就是质的飞跃。4. 两种算法的对比与选型4.1 关键维度对照表给这两种算法做一个全方位的对比方便遇到实际问题时快速选型对比维度DDA算法Bresenham算法核心运算浮点加减法整数加减法比较每步操作一次浮点加法 四舍五入两到三次整数加法/比较速度较慢受浮点性能制约快适合硬件实现精度存在浮点累积误差纯整数误差可控实现难度简单直观中等需理解决策参数适用范围教学、理解增量思想工业界、游戏引擎、硬件光栅化处理任意斜率需长轴判断通用形式自动覆盖抗锯齿扩展可自然扩展需额外设计或引入覆盖系数这里的浮点累积误差值得展开说一说。DDA算法每走一步都做一次浮点加法y的值是逐步累加出来的。累加的次数越多浮点误差就越大。画一条很长的线起点位置的像素是准确的越到终点位置偏差可能越大。而Bresenham的误差是固定的不随线段长度增长而增长因为它的误差项始终围绕0和1的边界做整数比较不会漂移。4.2 实际工程中怎么选在现在的图形学实践中Bresenham算法基本上是默认选择。CPU端的软件光栅化、嵌入式图形库、甚至旧式显卡的硬件光栅化单元都是基于Bresenham或其变体实现的。它的整数运算特性决定了它天然适合硬件电路实现因为整数加减和比较在电路里是极其简单的逻辑。那DDA是不是就没用了也不是。DDA的价值至少体现在两个地方。第一是教学价值。它的增量思想是整个计算机图形学里最基础的思想之一。你理解了DDA后面学Bresenham就顺理成章再学三角形插值、纹理坐标插值也是一脉相承。第二是精度有优势的场景。如果你的算法需要输出亚像素级别的坐标信息而不仅仅是点亮像素格子DDA的浮点计算反而能保留更多的精度信息。比如做一个反锯齿线条算法需要根据像素覆盖面积分配alpha值这时候精确的浮点坐标就有用了。但如果你只是单纯想快速把一条直线画到屏幕上Bresenham几乎总是最佳选择。我还想提一个工程上的细节。现代CPU做浮点运算已经很快了某些时候DDA的性能差距没有那么绝对。但Bresenham还有一个隐性优势它没有浮点数的平台相关性问题。浮点数的舍入策略在不同架构、不同编译器优化级别下可能不同导致同一份代码在不同硬件上画出略微不同的结果。Bresenham是纯整数运算结果完全可复现这在需要像素级一致的渲染管线里比如多人游戏联机回放是很重要的特性。4.3 关于浮点预算的行业背景补充一个背景知识帮助理解为什么当年的人如此执念于消灭浮点运算。在1960年代计算机的浮点运算通常由软件模拟完成根本没有硬件浮点单元。一次浮点乘法的成本可能是几十条甚至上百条整数指令模拟出来的。在这种环境下一个算法如果能用纯整数完成任务性能差距不是百分之几十而是好几倍。所以Bresenham算法的问世在当时是划时代的进步。它让计算机可以在可接受的时间内绘制大量直线直接推动了交互式计算机图形学的发展。现在虽然硬件浮点已经很便宜了但理解这段历史你会发现Bresenham的核心思想——把几何计算转化为整数决策——在现代计算里依然有广泛的迁移价值。5. 实操中的常见问题与排查经验5.1 直线总是出现断点或空隙这是我见过新手报告最多的问题。画出来的线不是连续的中间缺一块。排查方向很明确先检查是不是没有处理斜率绝对值大于1的情况。DDA算法如果没做长轴判断斜率高的时候就必断。Bresenham的通用版本一般不会出这个问题除非你使用的是限定第一象限的简化版。另一个常见原因是循环边界写错了。DDA的循环条件是i steps多画了一个点没事少画一个点就从终点的前一个像素直接跳到了终点视觉上就是断了一截。检查你的循环范围尤其注意steps的计算。5.2 直线端点坐标对不上画出来的线起点和终点跟输入对不上或者看起来方向反了。这个问题的根源多半是符号处理出了问题。在Bresenham通用版本里sx和sy的正确计算是关键。如果sx和sy是固定为1的那么当终点在起点的左边或上方时程序就会往错误的方向画永远到不了终点。我建议调试时可以先用水平线、垂直线、斜率为1的对角线这三类特殊直线来验证。这几类线如果都正确那符号逻辑基本没问题。然后再用非对称斜率比如从(0,100)到(200,0)测试反向情况。5.3 四舍五入导致的结果偏差DDA算法如果不四舍五入而是直接截断画出来的线会整体偏向一边看起来像被“压扁”了一样。这个现象的视觉表现是斜率小于1的线画出来y坐标普遍比理论值偏小斜率大于1的线x坐标普遍偏小。结果是直线好像向原点方向“缩”了。解决办法就是我在DDA代码里写的round函数而不要用int强转。C语言里round是标准库函数可以直接用。如果你在做性能敏感的开发觉得round有开销可以用宏或者内联函数实现四舍五入(int)(x 0.5)正数场景下跟round等价。5.4 决策参数更新错误导致画线抖动Bresenham算法如果更新公式写错了一个典型症状是某些斜率下线条看起来是“颤抖”的一会儿直线一会儿阶梯状。这个问题的核心在p的更新公式。记住口诀p 0时只加2Δyp 0时加2Δy再减2Δx。有些人会把两种情况对应的系数记反或者少减一个量画出来的线就乱套。另外一个容易错的点是判断用的是更新前的p不是更新后的p。代码里通常是先判断再更新顺序反了就会导致决策滞后一步。我见过不少次这种低级但极难肉眼排查的错误。建议手上有调试器时可以把p的每一步输出对照纸面手算的预期值很快就能定位问题。没有调试器也可以用打印大法虽然慢但有效。5.5 画线性能突然变差代码功能正确但性能拉胯这是另一个维度的问题。如果你在Bresenham算法的循环体里做了除法或者浮点运算那性能优势就被打掉了。检查一下是不是把斜率算成了浮点数存起来然后在每一步都乘一遍。这种写法属于“披着Bresenham外衣的DDA”性能跟DDA没差多少。另一个性能隐患是setPixel函数本身。如果每次调用setPixel都要做边界检查、颜色格式转换、甚至内存分配那再快的光栅化算法也救不回来。工程实践中经常是把setPixel做成内联函数去掉所有不必要的检查直接写显存或帧缓冲。我记得一次做嵌入式项目屏幕分辨率很低直线算法本身没问题但setPixel里有一个通用的putPixel函数内部做了裁剪和格式转换画5000条直线直接卡顿。把热点路径上的setPixel单独优化之后帧率立刻翻了好几倍。所以性能问题要放到整个流程里看光栅化算法只是其中一环。6. 从直线到更多这两个算法的延伸价值6.1 圆和椭圆的生成Bresenham算法不仅限于画直线。它最著名的变体之一就是Bresenham画圆算法。思路完全一样利用圆的对称性只算八分之一圆弧然后用决策参数判断下一个像素点应该落在哪里。推导过程也是构造一个误差决策项用整数运算递推。如果这里的直线算法你吃透了画圆算法就是顺水推舟的事。6.2 多边形填充与三角形光栅化3D图形渲染里三角形光栅化的核心就是沿扫描线逐行计算左右边界然后用类似Bresenham的增量思想填充像素。DDA的增量思想在这里以另一种形式出现重心坐标插值。纹理坐标、法线向量、颜色值都要在三角形内部做线性插值。如果你理解了DDA的“每一步做一个增量”的思路那么三角形里“从左边缘到右边缘逐像素插值颜色”就不难理解了。图形学是一个高度依赖“增量思维”的学科。你掌握这两个直线算法等于同时掌握了两把钥匙一把是通过浮点增量理解连续插值的钥匙一把是通过整数决策理解离散光栅化的钥匙。6.3 适合继续深入的方向如果你对这块内容感兴趣我的建议是按这个顺序往下学先实现一遍DDA和Bresenham画出各种斜率、各种长度的直线熟练掌握决策参数的推导过程。然后去看反锯齿直线算法比如吴小林算法它是一种在像素边界上同时点亮两个像素并用灰度分配的技巧能做到视觉上平滑的线。接着可以自己实现一个简单的软件渲染器从画三角形到填色到加深度缓冲一步步搭建。我个人的经验是理论学习再多也容易忘真正上手写一遍光栅化管线那些算法才真正长在脑子里。而直线生成算法就是这个从理论走向实践的完美起点。