企业官网建设流程全解析

1. 为什么我要从画直线开始啃计算机图形学

很多人学计算机图形学，第一反应是去搞三维渲染、写Shader、玩光线追踪，觉得那样才够酷。但我自己踩过的坑告诉我，跳过光栅化基础直接上高级话题，结果就是遇到问题只能靠试参数，根本不知道画面为什么对、为什么错。直线Bresenham算法恰恰是光栅化里最经典、最值得反复咀嚼的一个点，它解决的问题非常具体：在像素这种离散网格上，怎么用整数运算快速画出一条看起来“直”的线。

这个内容适合谁？如果你正在上计算机图形学课程、要做课程实验，或者你是做嵌入式图形、游戏引擎底层、甚至自己写小工具画图表的人，只要涉及“把数学上的线变成屏幕上的像素”，Bresenham就绕不开。它不需要你有很深的数学功底，核心只用到了初中水平的直线方程和一点点递推思想，但里面蕴含的“用增量代替乘法”“用误差项决定下一个像素”的思路，是理解整个光栅化体系的钥匙。

我这篇会从算法为什么这么设计讲起，把推导过程一步步拆开，再给出可以直接跑的MATLAB实现，最后把我调试时遇到的坑和排查方法整理出来。你跟着走一遍，不只是抄到一份代码，而是真正理解每一行在干什么。

2. 直线光栅化的核心矛盾与Bresenham的设计思路

2.1 为什么不能直接用直线方程逐点求值

最朴素的想法是：给定起点(x0,y0)和终点(x1,y1)，我让x从x0走到x1，每步加1，然后代入直线方程y = kx + b算出对应的y，再四舍五入取整。这个做法逻辑上没错，但问题在于每一步都要做一次浮点乘法和一次加法，而且k和b都是浮点数。在早期计算机上，浮点运算代价极高；即便在今天，如果要画几百万条线，这种开销也不容忽视。

更麻烦的是，当直线很陡（斜率绝对值大于1）时，x每加1，y可能跳好几个像素，画出来的线会出现明显的断裂或空洞。所以逐点求值法不仅慢，还在斜率较大时画质很差。这就引出了两个核心需求：一是尽量用整数运算替代浮点运算，二是要根据斜率方向选择主轴，保证每一步在主轴方向上都前进一个像素，避免断线。

2.2 Bresenham的核心洞察：误差项的递推

Bresenham算法的精妙之处在于，它不去算真实的y值，而是维护一个“误差项”，用来判断当前像素离理想直线偏了多少，下一个像素应该往哪个方向走。我打个生活化的比方：你在一排格子纸上画线，理想直线从格子中心穿过，你每往右走一格，就看看理想线是更靠近当前这一行的格子，还是更靠近上面那一行的格子，然后决定要不要往上抬一格。这个“更靠近谁”的判断，就是误差项在做的事。

具体来说，假设斜率在0到1之间，x是主轴。我们从(x0,y0)开始，每步x加1。理想直线在x+1处的y值是y + k。我们当前画在整数y上，那么误差就是理想y和当前y的差。如果这个误差超过了0.5，说明理想线已经更靠近y+1了，我们就该把y加1，同时把误差减去1。这个误差的更新只涉及加法和减法，k虽然一开始是浮点，但通过两边同乘2dx，可以把整个判断变成纯整数运算。这就是Bresenham能做到全整数运算的关键。

2.3 为什么这个思路优于DDA

DDA（数字微分分析器）也是直线光栅化的常见方法，它的做法是每步给x和y分别加上增量，本质还是浮点加法。DDA的优点是直观，缺点是每步都有浮点累加，而且累加次数多了会有精度漂移。Bresenham用误差项递推，误差项本身是整数，不存在漂移问题，而且每步只有几次整数加减和一次比较，速度更快。我在实际对比中，画同样数量的线，Bresenham的实现耗时大约是DDA的一半左右，线越长优势越明显。

注意：Bresenham的整数化推导有一个前提，就是主轴方向的步长固定为1。如果你的直线斜率绝对值大于1，必须交换x和y的角色，让y当主轴，否则误差项的推导不成立，画出来的线会错乱。

3. 从零推导Bresenham的整数递推公式

3.1 设定前提与符号约定

我们先把问题限定在斜率0 ≤ k ≤ 1的情况，起点(x0,y0)，终点(x1,y1)，且x1 > x0。令dx = x1 - x0，dy = y1 - y0，显然dy ≤ dx。每一步x增加1，y要么不变，要么增加1。我们用一个决策变量p来指导y是否增加。

设当前像素是(xi, yi)，理想直线在xi+1处的y值是yi + dy/dx。我们比较这个理想值和yi + 0.5的大小：如果理想值大于yi + 0.5，说明应该取yi+1；否则取yi。这个0.5就是半个像素的阈值。

3.2 决策变量的初始值与递推关系

把上面的比较两边同乘2dx，去掉浮点：判断条件变成2dy > dx时取yi+1。我们定义决策变量p = 2dy - dx。当p > 0时，取yi+1，并且新的p变为p + 2dy - 2dx；当p ≤ 0时，取yi，新的p变为p + 2dy。

初始时，在x0处，理想y就是y0，第一个决策针对x0+1，代入可得p0 = 2dy - dx。这样整个算法就只剩整数加法和比较了。我建议你拿一张纸，把dx=5、dy=3的情况手动推一遍，走五步，看看p的变化和y的取值，推完你就彻底懂了。

3.3 处理所有八种方向的通用化

上面只处理了0到1斜率、x递增的情况。实际直线可能朝八个方向：x递增或递减、y递增或递减、斜率绝对值大于1或小于1。通用化的做法是：先判断|dx|和|dy|哪个大，大的那个作为主轴。然后根据x和y的增减方向设置步进符号sx和sy（+1或-1）。如果x是主轴，就按上面的公式递推，y按sy方向在需要时步进；如果y是主轴，就把x和y的角色互换，公式形式完全一样。

这里有个容易搞混的点：当y是主轴时，决策变量里的dx和dy要互换位置。我见过不少人直接套用x主轴的公式，结果画陡线时全是错的。记住一句话：公式里的“dx”永远指主轴方向的跨度，“dy”指副轴方向的跨度。

4. MATLAB实现：从函数封装到逐行注释

4.1 函数接口设计与参数说明

我习惯把Bresenham封装成一个函数，输入起点终点坐标和图像矩阵，输出画好线的矩阵。这样方便在脚本里反复调用，也方便和MATLAB自带的画线函数做对比。接口设计如下：

function img = bresenham_line(img, x0, y0, x1, y1, color) % img: 输入图像矩阵（灰度或RGB） % x0,y0: 起点坐标（整数） % x1,y1: 终点坐标（整数） % color: 线条颜色值，灰度图传标量，RGB传1x3向量

坐标我采用图像坐标系，即左上角为原点，x向右，y向下。这一点很重要，因为MATLAB的矩阵索引是(row, col)，row对应y，col对应x，写代码时千万别搞反。我一开始就因为这个把线画到了镜像位置，排查了半天。

4.2 核心循环的完整实现

下面是核心实现，我把每一步的意图都写在注释里：

dx = abs(x1 - x0); dy = abs(y1 - y0); sx = sign(x1 - x0); sy = sign(y1 - y0); % 判断主轴 if dx >= dy % x为主轴 p = 2*dy - dx; y = y0; for x = x0:sx:x1 img(y+1, x+1, :) = color; % +1是因为MATLAB索引从1开始 if p > 0 y = y + sy; p = p + 2*dy - 2*dx; else p = p + 2*dy; end end else % y为主轴，交换角色 p = 2*dx - dy; x = x0; for y = y0:sy:y1 img(y+1, x+1, :) = color; if p > 0 x = x + sx; p = p + 2*dx - 2*dy; else p = p + 2*dx; end end end

注意img(y+1, x+1, :) = color这一行，冒号索引是为了兼容灰度图和RGB图。如果是灰度图，color是标量，赋值给一个长度为1的切片没问题；如果是RGB，color是1x3向量，也能正确赋值。这个写法比写两个分支要简洁。

4.3 测试脚本与可视化对比

光有函数不够，得验证。我写了一个测试脚本，随机生成若干条线，用Bresenham画一遍，再用MATLAB内置的insertShape或直接手动置像素画一遍，做逐像素对比。更直观的办法是把Bresenham的结果和理想直线叠加显示：理想直线用高分辨率浮点计算，然后看Bresenham的像素是否都落在理想线附近一个像素范围内。

img = zeros(200, 200); img = bresenham_line(img, 10, 10, 180, 90, 1); img = bresenham_line(img, 10, 190, 180, 20, 1); img = bresenham_line(img, 100, 10, 100, 190, 1); imshow(img);

跑出来你会看到三条线，一条缓斜、一条陡斜、一条垂直。重点看陡斜和垂直那两条，如果y主轴的处理写错了，这两条会明显出问题。我建议你故意把y主轴分支的公式改错，跑一遍看看错误长什么样，这样以后调试时一眼就能认出来。

5. 实操中踩过的坑与排查技巧

5.1 坐标索引偏移导致的整体错位

最常见的坑就是MATLAB索引从1开始，而算法推导从0开始。如果你在循环里直接用img(y, x)，当x或y为0时会报索引越界；如果统一加1但某处忘了加，线就会整体偏移一格。我的经验是：在函数入口处就把坐标转成0基，内部计算全用0基，只在最后写像素时加1。这样逻辑清晰，不容易漏。

5.2 斜率大于1时忘记交换主轴

前面强调过，但还是要再说一遍。我见过一个同学写的版本，所有斜率小于1的线都完美，一旦斜率大于1就画成阶梯状甚至断裂。原因就是他只写了x主轴的分支。排查方法很简单：专门测一条从(0,0)到(10,100)的线，如果画出来y方向有跳变，基本就是这个问题。

5.3 决策变量初始值算错

p0 = 2dy - dx这个公式，在x主轴时是对的。但如果你的推导里用了不同的阈值定义（比如用p = 2dy - dx还是p = dy - dx/2），初始值和递推式会不一样。我建议固定一套推导，不要混用。如果你发现线的前几步就偏了，后面又好像对，那多半是初始值的问题。

5.4 端点处理与循环边界

for x = x0:sx:x1这个循环在sx为负时也能正确工作，因为MATLAB的冒号运算符支持递减。但要小心x0等于x1的情况，此时dx=0，会进入y主轴分支，循环for y = y0:sy:y1正常执行，画出一条垂直线。如果x0=x1且y0=y1，就是一个点，两个分支都能处理，不会出错。我实测过这些边界情况，目前没发现问题。

5.5 常见问题速查表

6. 从直线到更复杂图元：这个算法的延展价值

Bresenham的思想不止能画直线。把误差项递推的思路推广到圆，就是Bresenham画圆算法，利用八对称性只算八分之一圆弧，其余镜像得到。推广到椭圆也有对应的中点椭圆算法。甚至在一些填充算法、抗锯齿算法里，误差项的概念都会反复出现。你把这一个算法吃透，后面学这些会轻松很多。

我自己在做一个简单的二维图表绘制工具时，就是先用Bresenham画坐标轴和网格线，再在上面叠加数据点。因为全是整数运算，在低性能设备上跑起来非常流畅。如果你也有类似需求，这个函数可以直接拿去用，改改颜色和线宽就行。线宽的实现思路是沿法线方向偏移多次画线，不过那就是另一个话题了。

最后分享一个小技巧：调试光栅化算法时，把图像放大到像素级别显示，用imshow(img, 'InitialMagnification', 800)，每个像素都看得清清楚楚，比看整体图容易发现问题得多。我每次调新算法都这么干，效率高很多。