企业官网建设流程全解析

很多人学图形学时，第一次接触的就是DDA算法和中点Bresenham算法，圆和椭圆的绘制也紧随其后。但说句实话，大部分人是靠“背代码”入门的：考试能默写，作业能跑通，图能画出来，就觉得自己会了。直到有次面试官问了我一句：“Bresenham直线算法的决策参数初始值为什么是2dy-dx？如果初始值是dy-dx会发生什么？”我当场愣住了。那一刻我才意识到，自己根本没有理解这些算法背后的几何逻辑，只是记住了公式。

后来我花了一个晚上，把直线、圆、椭圆这三类扫描转换算法的推导过程亲手推了一遍，豁然开朗：它们本质上解决的是同一个问题——如何在一个离散的像素网格上，用尽量少的计算量逼近一条连续的几何曲线。这篇文章就把我当时推明白的东西完整写出来，适合正在学图形学基础的同学，也适合要写嵌入式GUI、裸机图形驱动、或者想理解GPU光栅化底层原理的开发者。我会把每个公式的来历和直觉讲清楚，而不是只丢给你一段能跑的代码。

1. 光栅化的核心矛盾：连续函数与离散像素之间的桥

1.1 直接按直线方程描点会出什么问题

先说最朴素的做法。给你两个端点，要在屏幕上画一条直线，你第一反应肯定是：算出斜率 k，然后从 x0 到 x1 循环，每个 x 都用 y = kx + b 算一个 y，四舍五入后打点。逻辑上没错，但你试过就会发现三个问题。

第一是性能。假设一条从 (0,0) 到 (1000,600) 的线段，你要循环 1000 次，每次执行一次浮点乘法和一次浮点加法。在带FPU的桌面上无所谓，但在入门级MCU上做裸机绘图时，浮点运算慢得令人发指，而且某些单片机干脆没有浮点单元，软件模拟浮点更是一场灾难。

第二是累积误差。你每算一个 y 其实都在做一次 round，四舍五入一次没问题，但 1000 次循环下来，舍入误差可能会累积起来，导致终点附近偏离真正的直线几个像素。这个现象在长线段上肉眼可见。

第三是斜率超过 1 时的断点。当 |k| > 1 时，x 每增加 1，y 的变化超过 1，你的打点是稀疏的，画出来是一条虚线而不是实线。所以第一个结论是：光栅化不是一个“解方程”的问题，而是一个“做决策”的问题——每一步，你都要在两个相邻像素之间选一个离理想曲线最近的点。

1.2 DDA、Bresenham、圆和椭圆背后的同一套思想

如果你把 DDA、中点Bresenham直线、中点画圆、中点椭圆这四个算法摆在一起看，会发现它们的骨架惊人地一致：维护一个可以递推的判定量，每走一步更新它，根据它的符号决定下一个像素选谁。DDA用的是浮点增量，Bresenham把增量做了整数化改造，圆和椭圆只是把“判定量”从直线方程换成了圆方程或椭圆方程而已。

我当年学的时候是把它们当成四个孤立的算法去背的，背得痛苦不堪。后来才明白，它们其实是同一个框架在不同曲线上的特例。这个框架就是“增量误差决策法”：不重复计算，只做增量更新；不做浮点比较，只做符号判断。理解了这条主线，后面所有公式都是水到渠成的事。

2. DDA算法：先解决“计算开销”的增量化思路

2.1 DDA的推导与标准实现

DDA 的中文名是数字微分分析器，思路很直白：相邻像素的 x 坐标差 1，那么 y 坐标的增量就是斜率 k。也就是说，只要你知道上一步的 y_i，下一步的 y_{i+1} = y_i + k，根本不需要每次都做 y = kx + b 的乘法。

关键问题是怎么处理 |k| > 1 的情况。如果斜率的绝对值大于 1，按 x 步进会导致 y 方向跳格太多，所以要反过来：让 y 每次增加 1，x 每次增加 1/k。为了统一这两种情况，最稳妥的写法不是分两个分支，而是取步数 steps 为 dx 和 dy 绝对值中较大的那个，然后 x 和 y 各自按比例递增。

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

这个版本的妙处在于，steps 自动覆盖了 |k| <= 1 和 |k| > 1 两种情况。比如斜率小于 1 时，dx 大于 dy，steps 就等于 dx，x 每步递增 1，y 每步递增不足 1；斜率大于 1 时反过来，y 每步递增 1，x 每步递增不足 1。它和“按单位步长推进”的原始定义完全等价，但代码简洁得多。

2.2 浮点累积误差与整型平台的成本问题

DDA 虽然比直接代入方程快，但它有两个隐患。第一是浮点累积误差。xIncrement 和 yIncrement 本身是浮点数，每步累加一次，循环几百上千次之后，误差会逐渐累积，导致最后的像素位置和理想位置出现偏移。这个问题在绘制超长线段时尤其明显。第二是平台适配问题。在没有FPU的微控制器上，float 运算需要软件库模拟，一次浮点加法的开销能顶几十条整数指令。你在电脑上跑 DDA 没感觉，换到裸机环境就卡得肉眼可见。

所以说，DDA 更像是一个“刚好够用”的中间方案：它把重复计算降成了增量计算，但没摆脱浮点。要让算法做到纯粹的高效，必须完全去掉浮点，这就引出了中点Bresenham直线算法。它的核心思路是把“算 y 在哪”变成“判断中点在哪一侧”，所有运算都是整数加减法。

3. 中点Bresenham直线算法：决策参数的几何直觉

3.1 中点判别的几何依据：隐式直线怎么用

先限定在最经典的场景：斜率在 0 到 1 之间。假设当前已经选定像素 P = (x_i, y_i)，那么下一个像素只可能是两个候选之一：右边的 E = (x_i+1, y_i) 或者右上方的 NE = (x_i+1, y_i+1)。问题转化为：真实直线从当前点前进一个像素后，在 y 方向上更接近 y_i 还是 y_i+1？

Bresenham 的聪明之处在于，它不直接算这个“更接近”，而是看一个中间点——E 和 NE 中间的那个点 M = (x_i+1, y_i+0.5)。把 M 代入直线方程，如果 M 在真实直线的下方，说明直线在 M 的上面，NE 更接近直线；如果 M 在直线的上方，说明直线在 M 的下面，E 更接近。这个“拿中点做裁判”的思路，就是“中点算法”这个名称的来源。

直线需要写成隐式形式从 F(x,y) = dy·x - dx·y + C = 0 来理解。F 值有三个状态：等于 0 说明点在直线上，大于 0 说明点在直线的一侧，小于 0 说明在另一侧。这里 C 的具体值不重要，因为递推过程中都会被消掉，只要保证初始点代入后 F = 0 即可。重要的是符号。

3.2 决策参数 d 的递推与整数化改造

定义判定量 d_i = F(x_i + 1, y_i + 0.5)。把 E 和 NE 两个候选分别代入更新后的 M 点，就可以得到 d 的递推关系。

如果 d_i < 0，说明中点在直线上方，选 E，处理完下一轮时，点的 x 坐标又加 1，而 y 没有变。代入计算可得 d_{i+1} = d_i + dy。

如果 d_i >= 0，说明中点在直线下方或线上，选 NE，此时 x 和 y 都加 1，代入推得 d_{i+1} = d_i + dy - dx。

问题来了：dy 和 dx 是整数，但 d 的初始值里还藏着一个 0.5 的系数。d_0 取初始点推进一个像素后的中点，最终会得到 d_0 = dy - 0.5·dx。这里带着 0.5 做递推，本质上还是浮点。解决办法是把整个 d 乘以 2，让判定量变成 2dy - dx，递推也同步乘 2。于是得到教科书里最经典的 Bersenham 整数版本：

void Bresenham_Line(int x0, int y0, int x1, int y1) { int dx = x1 - x0; int dy = y1 - y0; int d = 2 * dy - dx; // 初始决策参数 int y = y0; for (int x = x0; x <= x1; x++) { setPixel(x, y); if (d < 0) { d += 2 * dy; // 取 E：右侧像素 } else { y++; d += 2 * (dy - dx); // 取 NE：右上像素 } } }

注意看，这里的 d 乘以 2 之后，初始值从 dy - 0.5dx 变成了 2dy - dx，这样就没有任何浮点了。整个过程只有整数加法、整数比较和一次条件分支。这也就是为什么面试时被问到“为什么初始值是 2dy-dx”，答出“因为中点判定天然带 0.5 的系数，乘 2 消掉了”就能证明你是真懂而不是背公式。

我建议你拿一张方格纸，画一条从 (0,0) 到 (5,2) 的直线，手动迭代几轮，把每次的 d 值写下来。你会亲眼看到 d 的符号就是“下一像素该往哪走”的开关，这个感觉一旦建立，以后就不会再忘记。

3.3 从0到1的斜率限制到全象限推广

上面所有推导都限定在斜率为 0 到 1 的情况，也就是第一卦限。实际画线不可能只画这种斜率，推广方式有两个思路。

第一个思路是八分圆对称。直线从起点到终点，根据 dx 和 dy 的符号，总共落在八个卦限里。如果 |dx| > |dy|，说明以 x 为主步进方向；反之就要交换 x 和 y 的角色，即把“画线”变成“画它的转置线”。方向上的处理用增量的正负来控制，也就是把每一轮的 x 更新和 y 更新变成带符号的移动。

第二种思路是使用另一个等价的 error 对称写法，适用范围更广。它的核心是把误差项 err 定义为 dx - dy，然后每一步同时检查它和 -dy、dx 的关系，决定 x 方向或 y 方向是否推进。这跟上面推导的 d 本质上是一回事，只是视角不同。实践里我倾向于直接用这种对称写法，因为它天然覆盖全象限。

void Bresenham_Line_All(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 (x0 != x1 || y0 != y1) { setPixel(x0, y0); int e2 = 2 * err; if (e2 > -dy) { err -= dy; x0 += sx; } if (e2 < dx) { err += dx; y0 += sy; } } setPixel(x1, y1); }

这段代码里的 err 和前面的 d 虽然形式不同，但判断逻辑等价。它不用考虑斜率分支和象限分支，唯一的注意点是两个 if 不是互斥的——在特定斜率下，x 和 y 可以同时前进，也就是斜率为 1 的情况，这正好是 NE 方向的本质。

4. 中点画圆法：把对称性变成性能优势

4.1 圆的隐式方程与八分圆扫描范围

画圆和画直线最大的不同在于，圆弧不是单调线性变化的，但圆拥有无与伦比的对称性。一个圆心在原点的圆，只要算出第一象限的八分之一圆弧，其他七个八分圆的点都可以通过坐标交换和取负号直接映射出来。这就是经典的中点画圆法的性能来源。

圆的隐式方程是 F(x,y)=x²+y²-R²。代入一个点，如果 F 小于 0，点在圆内；如果 F 大于 0，点在圆外。这个符号判据和中点Bresenham直线里的 F 完全同构。扫描范围选在第二卦限：从 x = 0 开始，y 初始为 R，一直扫描到 x >= y 为止。在这个范围内，圆弧的斜率绝对值不超过 1，适合以 x 为主步进方向。

每个扫描点 (x,y) 可以利用八重对称性映射出 8 个点：(x,y)、(-x,y)、(x,-y)、(-x,-y)、(y,x)、(-y,x)、(y,-x)、(-y,-x)。如果圆心不在原点，只需在最后画点时统一加上圆心偏移 (cx,cy)，比如 setPixel(cx+x, cy+y)。

4.2 决策参数的推导：1.25-R 到整数版 1-R

画圆的判定方法和直线如出一辙。假设当前点 (x,y)，下一个步进的 x 变为 x+1，候选像素是右边的 E=(x+1,y) 和右下方的 SE=(x+1,y-1)。取它们的中点 M=(x+1,y-0.5)，代入圆方程，得到决策参数：

d = F(x+1, y-0.5) = (x+1)² + (y-0.5)² - R²

初始点从 (0,R) 开始，所以 d 的初始值 d0 = F(1, R-0.5) = 1 + (R-0.5)² - R² = 1.25 - R。

这里就是那个很多人背错、面试也常考的地方：为什么书上都写 d = 1 - R？严格来说，当 d0 按浮点计算时，初值是 1.25-R。但 1.25 里的 0.25 会让 d 天生带一个多余的常数。常见做法是把判定量整体减掉 0.25，于是得到 d' = d - 0.25 = 1 - R。但要注意，d' 和 d 的符号并非在任何情况下都完全一致：如果真实 d 恰好等于 0，d' 会变成 -0.25，符号相反。而 d = 0 只有在中点恰好落在圆周上的罕见边界点才会发生，此时取 E 或 SE 对视觉结果几乎无影响，所以教科书普遍直接用 d = 1-R 的整数版本。

继续推递推关系。如果 d < 0，说明中点在圆内，实际圆弧更靠近右侧，选 E，此时 d_next = d + 2x + 3。如果 d >= 0，选 SE，此时 d_next = d + 2(x-y) + 5。完整代码如下：

void drawCirclePoints(int cx, int cy, int x, int y) { setPixel(cx + x, cy + y); setPixel(cx - x, cy + y); setPixel(cx + x, cy - y); setPixel(cx - x, cy - y); setPixel(cx + y, cy + x); setPixel(cx - y, cy + x); setPixel(cx + y, cy - x); setPixel(cx - y, cy - x); } void MidPoint_Circle(int cx, int cy, int R) { int x = 0; int y = R; int d = 1 - R; // 由 1.25 - R 整数化而来 while (x <= y) { drawCirclePoints(cx, cy, x, y); if (d < 0) { d += 2 * x + 3; // 选右点 E } else { d += 2 * (x - y) + 5; // 选右下点 SE y--; } x++; } }

4.3 最后一像素与对称映射的两个细节

细心的读者会发现，while 条件 x <= y 意味着当 x 和 y 相等（约在 45 度位置）时还会画一次点。这个点以及它在其他卦限的映射点，正好补齐了八分圆的最后一刀。如果条件写成 x < y，45 度线上的几个点会被漏掉，造成圆形接缝处的缺口。

另外一个经验是：随着 x 逐渐接近 y，对称映射后的 8 个点里会出现重复打点的情况。比如当 x = y 时，8 个点实际只覆盖了四个不同位置。这在光栅化里完全无害，重复写同一像素不会产生错误，但如果你在做基于像素计数的分析型绘制（比如统计覆盖率），就要注意去重。

调试这个算法时有个小技巧：不要只看最终的圆，而是在循环里把每一步的 d 值和 (x,y) 打印出来。你会看到 d 的符号切换和 E/SE 的选择一一对应，圆弧上的点画出来是一条平滑的锯齿边界。这个手感和直线完全一致，因为决策参数的几何本质就是“符号告诉你在哪一侧”。

5. 中点椭圆算法：从对称到区域的切换

5.1 椭圆与圆的本质差异：四重对称与变斜率

椭圆是圆的“亲戚”，但画起来比圆麻烦得多。原因有两个：第一，椭圆只有四重对称性，也就是 (±x, ±y) 四个象限，没有圆的八重对称，扫描量直接翻倍；第二，椭圆弧上的斜率处处变化，从长轴端点附近接近 0，慢慢过渡到短轴端点附近接近无穷大，因此不能像圆那样全程只用 x 作为主步进方向。

标准写法里，椭圆方程用中心在原点的隐式形式表示：F(x,y) = b²x² + a²y² - a²b²，其中 a 是 x 方向半轴长，b 是 y 方向半轴长。把点代入后，F < 0 在椭圆内，F > 0 在椭圆外，符号判据依然成立。问题只在于：什么时候用 x 步进，什么时候用 y 步进？

5.2 区域1与区域2：在|斜率|=1处切换

对隐式方程求导，可以得到椭圆弧上任意点的斜率 dy/dx = -b²x / (a²y)。这个值看着吓人，其实逻辑很简单：靠近长轴端点时，x 接近 a 而 y 接近 0，斜率的绝对值变得很大，这个时候如果还强行用 x 步进，会产生严重的断点；靠近短轴端点时，x 接近 0 而 y 接近 b，斜率绝对值很小，用 x 步进是合理的。

所以椭圆扫描要分两段。第一段从 (0,b) 出发，椭圆弧的斜率绝对值从 0 逐渐增大，在斜率绝对值恰好等于 1 的地方停下来。这里 x 步进为主，候选点和画圆的 E/SE 一样。第二段从那个切换点继续，一直走到 (a,0)，斜率绝对值大于 1，改用 y 步进为主，候选点变为下方点 S=(x,y-1) 和右下点 SE=(x+1,y-1)。

切换条件的推导用到导数：|dy/dx| <= 1 等价于 b²x <= a²y。为了避免除法和浮点，写成 2b²x <= 2a²y，程序里直接用整数比较。注意这个条件要在每次循环开头判断，一旦不满足就立刻切到第二段的逻辑，不要再使用第一段的递推公式。

5.3 两个决策参数的推导与完整实现

第一段和第二段各自维护一个决策参数 p1 和 p2，推导思路和圆一模一样，只是 F 的系数从 R² 换成了 b² 和 a²，计算会稍显繁琐。

p1 的初始点是 (0,b) 推进后的中点 (1, b-0.5)，代入椭圆方程后得到 p1_0 = b² - a²b + a²/4。注意 a²/4 这一项让初始值还是可能带小数，常见做法是先按浮点初始化，或者用扩大 4 倍的方式处理。为清晰起见，下面的代码用 float 做初始值，之后再参与整数递推，实际跑起来没问题。

区域1里，若 p1 < 0 选右侧点 E，x 加 1 后 p1 增加 2b²x + b²；若 p1 >= 0 选右下点 SE，x 加 1、y 减 1 后 p1 增加 2b²x + b² - 2a²y。注意这里的增量计算要使用更新后的 x 和 y。

进入区域2 时，用区域1最后得到的 (x,y) 重新计算 p2 的初值，公式是 p2 = b²(x + 0.5)² + a²(y - 1)² - a²b²。然后继续递推：若 p2 >= 0，选下方点 S，y 减 1，p2 增加 -2a²y + a²；若 p2 < 0，选右下点 SE，x 加 1、y 减 1，p2 在 S 的基础上再增加 2b²x。最后补画 y 为 0 时的两个轴端点。

void drawEllipsePoints(int cx, int cy, int x, int y) { setPixel(cx + x, cy + y); setPixel(cx - x, cy + y); setPixel(cx + x, cy - y); setPixel(cx - x, cy - y); } void MidPoint_Ellipse(int cx, int cy, int a, int b) { int x = 0; int y = b; float p1 = b * b - a * a * b + a * a / 4.0f; // 区域1：斜率绝对值 <= 1，主步进方向为 x while (2 * b * b * x <= 2 * a * a * y) { drawEllipsePoints(cx, cy, x, y); if (p1 < 0) { x++; p1 += 2 * b * b * x + b * b; } else { x++; y--; p1 += 2 * b * b * x + b * b - 2 * a * a * y; } } float p2 = b * b * (x + 0.5f) * (x + 0.5f) + a * a * (y - 1) * (y - 1) - a * a * b * b; // 区域2：斜率绝对值 > 1，主步进方向为 y while (y > 0) { drawEllipsePoints(cx, cy, x, y); if (p2 >= 0) { y--; p2 += -2 * a * a * y + a * a; } else { x++; y--; p2 += 2 * b * b * x - 2 * a * a * y + a * a; } } // 补上长轴两端点 drawEllipsePoints(cx, cy, a, 0); }

这个代码里最坑的地方是区域1和区域2的 p 初始值计算。p1 好办，直接在循环前用浮点算一次；p2 则必须“继承”区域1循环结束时的 (x,y)，很多人写到这里忘了 p2 要用那个切换点重新代入，而直接在区域1循环外沿用 p1 的公式，画出来的椭圆会从某个地方开始错位。我在实际调试时踩过好几次这个坑，建议你把切换点的数值打印出来对一下。

6. 性能对比与现代化视角：老算法为什么还有价值

6.1 四个算法的关键参数对照

整理一下这几个算法的性格差异，方便你在实际项目里做选型。

可以看到，从DDA到Bresenham的演进，本质是一次“去浮点化”的优化；从直线到椭圆，本质是判定式 F 一轮比一轮复杂，但增量决策的骨架始终没变。性能上，中点画圆比直接按角度采样快得多，因为在 1/8 圆弧的扫描过程中，每步只做整数加减，没有任何三角函数求值和浮点乘除。

6.2 GPU和现代图形库里的“老算法基因”

你可能要问：现在写图形程序谁还自己画像素啊？GPU 光栅化不香吗？香，但 GPU 光栅化器的工作方式，本质上和这里讲的 DDA/Bresenham 是同宗同源。现代光栅化硬件做三角形填充时，内部也必须按像素步进，判断哪些像素覆盖了三角形，然后计算覆盖率。只是在 GPU 里，决策参数换成了各种经过优化的误差递减变量，步进也变成了固定管线里的高速并行电路。

理解这些老算法的直接好处是：你会更容易看懂硬件光栅化的覆盖率计算、亚像素偏移、保守光栅化这些概念。比如反走样的核心其实是对“像素被覆盖了多少”做一个近似，而这个覆盖度问题和中点算法的“判定量在哪一侧”是同一类几何直觉。也就是说，你看到的不是一堆和现实脱节的古董代码，而是现代图形系统底层逻辑的最简模型。

6.3 实际项目里的选型建议

如果你现在要在一个入门级 MCU 上画点简单图形，我的建议是按顺序做选择。第一，能选整数中点算法就不选 DDA，因为整数加法在大部分低端芯片上都能逼近一个时钟周期完成，而浮点加法可能要消耗几十甚至上百个周期。第二，如果只是画直线，直接使用全象限版本的 Bresenham 循环体，封装成一个函数，到处调用；如果要做圆或椭圆，优先复用上面的中点算法，别自己去写三角函数采样。第三，如果平台有硬件浮点单元且图形量不大，退回去用 DDA 也完全可行，代码更短更易维护，性能差异肉眼不可见。

还有一个小建议：在嵌入式项目里，setPixel 本身就是最耗时的部分（往往要操作显存或驱动 LCD 接口），算法再怎么优化，瓶颈大概率不在画点决策上。所以我一般不把这几个算法当成“终极优化”，而是当成“写出可预期、无浮点、不依赖昂贵数学函数”的默认实现。它们的最重要价值，其实是帮你建立一套能迁移到任何图形系统的底层的“像素决策”思维。

最后再分享一个我自己的操作习惯。每次换工作交接图形相关的项目，我都会拿一张白纸，把直线、圆、椭圆三个算法的手动演算各跑一遍，尤其注意 d 和 p 的符号变化轨迹。相比背十遍代码，这个纸面演算半小时，之后记十年都不会忘。如果你正卡在理解 Bresenham 家族算法的阶段，别急着找更多博客和代码片，先拿纸笔把 (0,0) 到 (5,2) 这条直线自己走一遍，把每一步的决策参数写下来，你会感受到算法设计者当年的那个顿悟时刻。