企业官网建设流程全解析

直线扫描转换算法（DDA、中点、Bresenham）实现——从原理到代码一次讲透

想先从自己画的第一条直线说起。当年刚接触图形学，满脑子都是"画一条竖线不是很简单吗"，直到亲手打开一个像素点阵画布才意识到：真实显示器上的"直线"根本不是数学意义上的连续线，而是由一堆离散像素拼出来的阶梯状图案。这篇内容要做的就是拆解三种最经典的直线扫描转换算法——DDA、中点画线、Bresenham，用最直白的语言把每一步推导和代码讲清楚。适合刚学图形学的新手、做嵌入式GUI或低层图形库的开发者，以及任何想知道"这两个像素点之间到底怎么选"的人。把这三种算法的底层逻辑吃透，后面画圆、画椭圆、多边形填充全都是同一套思路，一通百通。

1. 光栅化到底在解决什么问题

1.1 直线的数学表达和像素表达差了多远

数学课上我们写y = kx + b，这是一条无限细的连续直线，上面有无数个点。但在屏幕上画线，能用的坐标只有整数，像素点阵是离散的，你只能从有限个格子里面选一些格子来"近似"这条线。比如从 (0,0) 到 (5,2)，数学上的直线经过很多非整数坐标位置，可像素只有 (1,1)、(2,1)、(3,2) 这些可选。

这个"离散化逼近"的过程就叫扫描转换，也就是光栅化。核心矛盾是：像素坐标只能是整数，但直线经过的真实坐标是实数。所以算法必须回答同一个问题：每一步往哪个方向走？两个候选像素选哪个？

1.2 三个算法的统一本质：做决策

DDA、中点画线、Bresenham表面上是三种不同的算法，本质上都在做同一件事：沿着某个主方向走一个像素，然后决定另一个方向是否需要加一。区别只在于"决策方式"不同。

• DDA：用浮点增量直接计算，每次都算出下一个点的实际坐标，然后取整。
• 中点画线：构造一个直线隐式方程，用中点的符号来判断选哪个像素。
• Bresenham：维护一个整数误差项，用误差的正负来做唯一决策。

理解到这一层，三种算法就不再是三个孤立的知识点，而是同一个问题在不同约束下的三种解法。下面的内容会沿着这个思路，一个算法一个算法拆开来看。

2. 准备工作：先限定斜率为0到1的八分之一圆弧

2.1 为什么只讨论斜率在[0,1]之间的直线

所有图形学教材第一步都会先限定：假设直线斜率k满足0 ≤ k ≤ 1。这看起来像偷懒，其实是个很聪明的策略。斜率在0到1之间时，直线的特点是：每往右走一个像素（x方向加1），y方向要么不变，要么加1，一个方向是确定的，另一个方向是两选一，问题被大大简化。

有人会问：那斜率大于1、负数或者倒着画怎么办？答案是：用对称性做坐标变换。斜率大于1时交换x和y，负斜率时取绝对值，终点x小于起点x时交换端点。所有情况都能映射到0 ≤ k ≤ 1的基准场景上。后面的代码部分会补上完整的归一化处理。

2.2 主位移方向和增量单位的理解

在斜率0到1的场景里，主位移方向永远是x方向，每次x += 1，然后看y是否需要+1。这样每步横坐标都是精确的整数，只有纵坐标需要做决策。这个"主方向"概念很重要，因为三种算法里所有的递推、误差项、判别式，本质都是在追踪"纵向偏移量"——也就是当前真实直线位置和已选像素位置之间的差距。

理解了这个基线，下面可以正式开始推算法了。

3. DDA算法：最直观的浮点增量画法

3.1 DDA的核心思想

DDA全称是 Digital Differential Analyzer，直译是数字微分分析器。它做的事情非常简单：既然真实直线上相邻两个点的x坐标差1，y坐标的增量就是斜率k，那么我直接从起点开始，每次x += 1，y += k，然后把y取整作为像素坐标。

举个例子，从 (0,0) 到 (5,2)，斜率就是0.4。起点y=0.0取整得到第0行像素；第二步y=0.4取整还是第0行；第三步y=0.8取整是第1行；第四步y=1.2取整是第1行；第五步y=1.6取整是第2行。每一步都是确定性的，完全线性。

这套逻辑的优点是极好理解，缺点也直接摆在脸上：每一步都有浮点加法和取整。当年CPU没有FPU的时候，浮点运算是非常昂贵的操作，在低端嵌入式设备上简直是灾难。而且浮点数有精度问题，连续几千步的累加会导致误差堆积，末尾的像素位置可能偏出一两个格。

3.2 DDA的代码实现

void dda_line(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 = dx / (float)steps; float yIncrement = dy / (float)steps; float x = x0; float y = y0; for (int i = 0; i <= steps; i++) { plot(round(x), round(y)); x += xIncrement; y += yIncrement; } }

一个值得注意的细节是：不要直接写x += 1或y += k，而是先算出总的步数steps，再计算每一步的增量。这样不管斜率是0.2还是5，steps始终是像素网格上较长方向要走的总步数，代码天然兼容任意斜率的直线。上面这版代码我已经把"任意方向"处理掉了，但要注意取整时用round，因为C语言里强制类型转换(int)y是截断，不是四舍五入。截断会导致像素点整体往下偏移一格，视觉上线条明显偏斜。

3.3 DDA的精度和性能边界

DDA在实际项目里已经很少直接用了，但它的价值在于帮助建立"增量计算"的直觉。每走一步只做一次加法（加上一个固定增量），这是后面所有优化算法的雏形。后面的中点算法和Bresenham算法，优化的核心目标就是干掉这个浮点累加。

我实测过DDA画一条5000像素长的直线，在古老设备模拟器里能明显感觉到像素点尾部抖动，这就是浮点累加误差的直观体现。所以DDA适合教学、适合快速原型验证，但如果你要做的是工业级图形库，请继续往下看。

4. 中点画线算法：用几何符号代替浮点运算

4.1 从隐式方程到中点判别式

中点画线算法的思路比DDA高级一个层次：它不再计算实际坐标，而是判断"当前候选两个像素的中点，在直线的哪一侧"。

这要用到直线隐式方程：

F(x, y) = a*x + b*y + c = 0

对任意点(x,y)，把这个点的坐标代入F(x,y)，得到的结果有三种情况：

• F(x,y) = 0：点在直线上
• F(x,y) > 0：点在直线下方
• F(x,y) < 0：点在直线上方

现在假设已知当前像素是(xi, yi)，主方向确定往右走。下一个像素只有两种可能：右边相邻的(xi+1, yi)，或者右上方的(xi+1, yi+1)。取这两个候选像素的中点(xi+1, yi+0.5)，代入直线方程：

• 如果中点位于直线下方，说明真实直线离右上方的像素更近，应该选(xi+1, yi+1)；
• 如果中点位于直线上方，说明真实直线离右边像素更近，应该选(xi+1, yi)。

决策就靠这一个F(xi+1, yi+0.5)的符号完成。整个过程完全没有浮点坐标相乘，只剩符号比较。

4.2 判别式的递推实现

如果每一次都重新计算F(xi+1, yi+0.5)，虽然工作量不大，但还是有乘法。中点算法的精髓在于：F的增量是固定的，可以线性递推。

定义判别式d = F(xi+1, yi+0.5)，分两种情况推导：

情况一：d < 0，选右上像素(xi+1, yi+1)下一个要判断的点是(xi+2, yi+1.5)。新旧判别式相减：

d_new - d_old = F(xi+2, yi+1.5) - F(xi+1, yi+0.5) = a * 1 + b * 1 = a + b

情况二：d ≥ 0，选右边像素(xi+1, yi)下一个判断点变为(xi+2, yi+0.5)：

d_new - d_old = F(xi+2, yi+0.5) - F(xi+1, yi+0.5) = a

也就是说，每次只需要给d加上一个常量a+b或者a，就可以得到下一步的判别式，连乘法都省了。起点初始判别式也不再直接算中点坐标，而是用直线两端点的系数代进去。

为了进一步避免小数，算法两边同时乘以2，d的初始值和增量都变成整数。具体推导可以参照教材，这里只展示最终代码：

void midpoint_line(int x0, int y0, int x1, int y1) { // 以斜率 0<=k<=1 为例 int dx = x1 - x0; int dy = y1 - y0; // F(x,y) = dy*x - dx*y + c，取 a=dy, b=-dx int a = dy; int b = -dx; int d = 2 * a + b; // 2 * F(x0+1, y0+0.5) int x = x0, y = y0; plot(x, y); while (x < x1) { if (d < 0) { x++; y++; d += 2 * (a + b); } else { x++; d += 2 * a; } plot(x, y); } }

有一个容易出错的点：判别式d的更新量根据a、b计算时，很多教材直接写d += 2*dy - 2*dx或者d += 2*dy，对照上面的推导会发现反直觉。这里的关键是符号约定：a+b在斜率小于1时是负数，所以选右上像素时判别式是变小而不是变大。如果搞反了符号，直线会往相反的方向偏出去。

4.3 中点算法的实际体验

中点算法的核心优势是彻底摆脱了浮点乘法，甚至浮点加法和取整都没了。所有运算都是整数加法，这在所有图形库底层都是巨大胜利。

从视觉效果上讲，在斜率小于1的情况下，中点算法画出来的直线和Bresenham画出来的完全一样，像素选择结果相同。所以这两个算法在结果层面是等价的。它俩的差异主要体现在推导路径和适用场景上。中点算法从"点到直线的距离符号"出发，几何直觉强，后续扩展画圆时可以直接套用（画圆也是用中点构造判别式）；Bresenham是从"误差累积"出发，代码层面更简洁。

5. Bresenham算法：纯整数误差项的极致优化

5.1 误差项视角的重新推导

Bresenham的出发点不是中点符号，而是直接追踪"实际直线高度和像素高度之间的误差"。每次x走一步，对应的真实y值也会往前走，这个真实y值和你当前选的像素y值之差，就是一个误差项e。

仍然假设斜率为0到1，起点在某个点(x, y)。真实直线上x+1处的高度比当前像素y高k（斜率）。如果e + k < 0.5，说明真实位置离下方像素更近，y保持不变；如果e + k ≥ 0.5，说明超过半格了，y需要加1。

为了避免小数，把这个误差项乘以2，再做一次代数变换，把阈值0.5变成0。实际代码中常见的维护变量是p，它的物理意义可以理解成"误差是否过半"的判别值，但它不是正的误差，而是误差的2倍再减去1，所以有人也叫它"决策参数"。

这个推导的终点是以下递推：

初始 p = 2*dy - dx 在每个像素选完后： 如果 p < 0：只有 x 加 1，p 加 2*dy 如果 p ≥ 0：x、y 都加 1，p 加 2*dy - 2*dx

5.2 Bresenham标准实现

void bresenham_line(int x0, int y0, int x1, int y1) { // 以斜率 0<=k<=1 且 x0<x1 为例 int dx = x1 - x0; int dy = y1 - y0; int p = 2 * dy - dx; int x = x0, y = y0; plot(x, y); while (x < x1) { x++; if (p < 0) { p += 2 * dy; } else { y++; p += 2 * dy - 2 * dx; } plot(x, y); } }

对比中点算法的代码，会发现Bresenham的代码更精简：没有系数a、b的概念，直接以dx、dy为核心，初值和增量全由dy、dx算出。这个版本的循环体内只有两个整数加法，一个整数比较，没有乘法、除法、浮点运算，是教科书级别的高效实现。

5.3 处理任意斜率：对称变换的完整版本

实际封装成工具类时不能只写这一个函数。要处理8个卦限的全部情况，推荐做法是在调用入口统一做归一化，而不是在每个算法内部写一堆分支。归一化逻辑如下：

如果 x0 > x1：交换起点和终点（保证 x 方向从左到右） 记录原始坐标；如果 |dx| >= |dy|，按 x 为主方向；否则把 x、y 角色互换 如果斜率是负的，y 的变化方向取反

写成代码，大致是这个框架：

void draw_line_general(int x0, int y0, int x1, int y1) { // 统一为第一卦限方向后送入核心循环 if (abs(x1 - x0) >= abs(y1 - y0)) { if (x0 > x1) swap(x0, x1), swap(y0, y1); int dx = x1 - x0; int dy = y1 - y0; int stepY = (dy >= 0) ? 1 : -1; // 斜率正负方向修正 dy = abs(dy); // 核心 Bresenham，用 stepY 控制 y 的方向 } else { // 交换 x、y 角色，递归调用或镜像调用 draw_line_general(y0, x0, y1, x1); } }

对称变换的思想很通用，如果每一种情况都单独写一版算法，代码会膨胀好几倍，而且每多一份代码就多一批隐藏bug。我见过有人直接把8个分支展开写在同一个函数里，最后自己都分不清哪个分支对应哪个卦限，排查问题时痛苦不堪。

6. 三种算法对比与实战选型

6.1 直观对比表

从运算角度看，中点画线和Bresenham没有本质区别，都是整数加法，速度差异可以忽略。真正拉开差距的是DDA和其他两种算法之间的鸿沟——浮点累加和取整的开销在现代CPU上虽然不明显，但在低端MCU、FPGA、老式嵌入式设备上非常致命。

6.2 实际项目里到底用哪个

如果是做软件光栅化器（比如自己写一个类似CPU渲染器的玩具引擎），直接用Bresenham。为什么？因为它是三者中代码最短、循环体重播最快的，而且不用处理浮点误差，边界情况最少。

如果是学习图形学原理，我觉得三种都要亲手写一遍。DDA帮你理解增量；中点画线帮你建立隐式方程和判别式的直觉，这个直觉在画圆、画椭圆时价值很大；Bresenham则代表工程上"用最少的运算做最多的事"的典型范例。

如果是给FPGA或VLSI设计硬件光栅化器，Bresenham也是首选，因为整数加法器在硬件里实现代价极低，浮点单元则会占用大量逻辑资源。另外，有些硬件设计方案甚至会直接把Bresenham的p值当成插值计数器，顺带生成像素覆盖率，为反走样服务。

6.3 性能实测的一个小结论

我自己做过一次粗略的基准测试：画100万条长度在100到200像素之间的随机直线，在普通PC上DDA、中点、Bresenham三种算法的耗时差异大约在10%到20%之间，现代CPU上并没有传说的那么夸张。但这并不代表DDA"也够用"——在嵌入式CPU、无FPU环境、编译器优化等级低的情况下，差距会拉大到数倍甚至更多。所以选型要结合目标平台，不能只看桌面端的现象。

7. 常见问题与避坑实录

7.1 只能画向右方向的线？归一化忘了做

最典型的一个坑：实现Bresenham只在0 ≤ k ≤ 1范围内有用，一旦进入其他卦限就画错。解决方式就是前面讲的归一化：先判断主方向、交换坐标、做镜像映射。我见过的大部分图形库入门项目，90%的画线bug都出在这一步。建议把"归一化"和"核心算法"拆成两层函数，测试时分别覆盖8个方向，确保每一卦限都正确。

7.2 取整给截断还是四舍五入

在DDA里，很多人直接plot((int)x, (int)y)。(int)是向零取整，负数时会向零方向截断。画一条斜率略大于0的直线没问题，但画负斜率的线时像素会整体偏移，看起来像是被"压扁"。正确的做法是plot(round(x), round(y))或者手写+0.5再截断。Bresenham和中点算法因为全程整数，不存在这个问题。

7.3 判别式的符号写反导致整条线向上偏

中点算法和Bresenham的判别式符号都有"哪一边是正"的约定问题。一个技巧是：先用dx、dy为正、起点在左下、终点在右上的情况手工跑3个点，验证直线走向是否符合预期，如果第一个转折点偏了就调符号。不要试图直接从数学公式里看懂符号，因为不同教材的公式变形不一样，有的乘了2，有的乘了4，有的F(x,y)定义正负方向都不一样。以"能不能跑出正确的点"为准。

7.4 像素点是离散的，看起来总是歪的

初学会觉得 Bresenham 画出来的阶梯效果"不太直"，尤其斜率为0.5左右时阶梯感最强。这个不是算法bug，是光栅显示器的物理特性。如果用户需要更平滑的视觉效果，引入反走样（抗锯齿）技术，比如 Wu 算法（Xiaolin Wu's line algorithm）计算每个像素的覆盖率，让边缘像素降低亮度而不是直接二选一。Bresenham 的误差项可以直接复用到覆盖率计算中，这也是它生命力强的另一个原因。

7.5 别的语言里整型溢出

在坐标范围很大的场景下，2 * dx + 2 * dy可能溢出。16位MCU上尤其明显，坐标值超过约1万就危险。解决办法是使用长整型long或将误差项约束在较小区间内。这个细节很多教程不会提，但做真实硬件开发时经常碰上。

8. 实际使用的一些心得技巧

额外说一个关于扩展的技巧：中点画线的判别式很容易改造成画圆的版本。在圆上，判别式从F(x+1, y-0.5)构造出来，推理过程和直线完全一致。所以如果你想深入掌握这些算法，建议把三种直线的实现和一种画圆的实现放在同一个工程里，对比阅读效果最好。

调试这类光栅化算法时，我习惯先在测试代码里把像素坐标打印成字符矩阵——用一个二维数组，plot时往数组里写#，跑完直接输出纯文本。这样每次改动算法，肉眼扫一遍字符图案就能发现问题，比直接跳到图形窗口里调试直观得多。等到算法基础正确了，再把plot替换成真实的屏幕API。

如果你的图形库需要画虚线，也可以基于Bresenham修改：只需在循环中加一个计数器，偶数段画像素、奇数段跳过即可。这个用途在实际项目里非常常见，比如CAD软件里的辅助线、矩形选框的虚线边框。

最后再强调一个工程经验：给直线扫描转换这类基础几何函数写自动化测试，建议直接覆盖8个卦限、水平线、垂直线、单个像素几种边界情况。图形学里大量bug不是出在算法核心，而是出在边界条件的归一化处理上。把边界测好了，整套画线功能基本就能稳定交付。