从决策参数到像素密度：圆与椭圆光栅化的工程实现

1. 从直线到曲线：为什么画圆不能直接硬算坐标

在软件渲染这条路上走到“画圆”这一步的，大概都经历过一个看似简单、动手就翻车的时刻。直线光栅化只要处理一个斜率，稍微花点心思就能把 Bresenham 写得又快又漂亮；可一旦换成圆，第一反应往往是——用圆的直角坐标方程，x 从 -r 扫到 r，每一个 x 算出 y，把点画出来不就行了？

这个思路我刚接触时也试过，结果画出来的东西根本不像圆。不是因为数学错了，而是因为光栅化要的是一个离散像素网格上的“形状近似”，不是连续坐标系里的函数图像。

1.1 用 y = f(x) 硬算，像素点会稀疏到没法看

先看最简单的做法。圆的隐式方程是 x² + y² = r²，改写成显式函数就是 y = ±√(r² - x²)。如果让 x 每次加 1，对每个整数 x 计算 y，会得到什么？

在 x 接近 0 的地方，也就是圆的最顶部和最底部，曲线的切线几乎是水平的，dy/dx 接近 0，所以 x 每步进 1，y 的变动很小，画出来的点挨得很密；可一旦靠近 x 接近 r 的位置，也就是圆的两侧，切线近乎垂直，dy/dx 趋向无穷大，x 稍微挪一步，y 就剧烈跳变。相邻两个像素之间的弧长差距可以拉到好几倍，最后圆的两侧会出现明显的稀疏缺口和台阶状断裂。

更麻烦的是，显式方程涉及开方运算。每个点都要算一次浮点平方根，对一个半径几百像素的圆来说，就是上千次 sqrt，性能完全没法看。嵌入式设备或者无 GPU 的软件渲染环境里，这种写法基本等于直接卡死。

1.2 隐式方程才是光栅化的正确坐标系

正确的思路是把圆看成一条“隐式曲线”，而不是一个“显式函数”。用 f(x, y) = x² + y² - r² 来描述：点在圆上时 f = 0，点在圆内时 f < 0，点在圆外时 f > 0。这个形式有几个明显的好处。

其一，它天然把“判断”变成了符号比较，而不需要真正算出坐标。其二，光栅化本质上是一个迭代逼近的过程：从圆上的某个已知像素出发，每一步在几个候选像素里挑一个更接近圆的，关键在于怎么判断“更接近”。隐式方程给了我们一个天然的度量标准，f 的绝对值越小，说明像素中心点离真实曲线越近。

不过说实话，“选离曲线更近的像素”这个描述听着简单，真正工程化落地还需要一个更聪明的机制，也就是增量思想。

1.3 增量思想：光栅化的核心是让每步都“便宜”

直线 Bresenham 之所以快，是因为它把误差项做成了递推式——每走一步只需要做几次整数加减法和比较，不涉及乘除、开方、浮点数。画圆要快，也必须走同样的路子。

这里的核心思路是：当前这一步的误差值，可以基于上一步的误差值加一个增量得到，而这个增量只跟当前坐标有关，是常数或简单的一次多项式。于是我们不需要每步重新代入圆的方程做平方计算，只需要维护一个决策参数，每次沿着扫描方向走一格，然后根据这个参数的符号决定下一步往哪走。

听起来抽象，下一节我完整推导一遍中点画圆法，把每一步的数学依据和代码都写清楚。掌握了这个，椭圆光栅化也只是同一套思路加一个分支条件，不会再有从零开始的挫败感。

2. 中点画圆法：一个决策参数搞定一个像素点

中点画圆法，也叫 Bresenham 画圆算法，是软件光栅化里最经典的做法之一。它不直接计算像素点到圆心的距离，而是通过判断“两个候选像素的中点”是在圆内还是圆外，来决定选哪个像素。这个方法只依赖整数运算，没有开方，没有浮点乘除，每一轮循环只有几次整数加法和一次比较。

2.1 决策参数的几何意义

假设当前已经确定了某个像素点 (x_k, y_k) 在圆上，并且只考虑第一象限从正上方往右下走的这段圆弧。下一个像素只可能是正右方的 E 点 (x_k + 1, y_k)，或者右下方的 SE 点 (x_k + 1, y_k - 1)。两个候选点谁更接近圆？这要比较它们各自到真实圆弧的距离。

中点法的巧妙之处在于：不需要分别算两个距离，只需要考察 M 点，也就是 (x_k + 2, y_k - 0.5)——不对，这里写仔细一点。E 和 SE 的 x 坐标都是 x_k + 1，区别只在 y。取它们的中点 M = (x_k + 1, y_k - 0.5)，把 M 代入圆的隐式方程：

p_k = f(x_k + 1, y_k - 0.5) = (x_k + 1)² + (y_k - 0.5)² - r²

这个 p_k 就是决策参数。如果 p_k < 0，说明中点在圆内，也就意味着真实圆弧穿过 M 点上方，那么 E 点离圆更近，选 E；如果 p_k ≥ 0，中点在圆外或圆上，真实圆弧在 M 下方，选 SE。

这个判断的几何逻辑很直白：圆的边界把平面分成内外两个区域，候选像素的中点落在哪一侧，决定了真实曲线更偏向哪个候选点。

2.2 误差增量的数学推导

决策参数不能每次都重新算，那就回到了浮点乘方的老路。好在 p_k 的递推关系非常规整。

起点是圆顶部的像素 (0, r)。第一步的决策参数为：

p_0 = f(1, r - 0.5) = 1 + (r - 0.5)² - r² = 1.25 - r

注意这个初值带小数。别急，后面专门讲整数化处理。

从 (x_k, y_k) 出发，如果选了 E 点，新的决策参数是：

p_{k+1} = f(x_k + 2, y_k - 0.5) = (x_k + 2)² + (y_k - 0.5)² - r²

两式相减：

p_{k+1} - p_k = (x_k + 2)² - (x_k + 1)² = 2x_k + 3

也就是说，选了 E 点时，p 的增量是 2x_k + 3，是一个跟当前 x 相关的一次多项式，运算成本只有一次加法和一次移位。

如果选了 SE 点，新决策参数是：

p_{k+1} = f(x_k + 2, y_k - 1.5) = (x_k + 2)² + (y_k - 1.5)² - r²

两式相减：

p_{k+1} - p_k = (x_k + 2)² - (x_k + 1)² + (y_k - 1.5)² - (y_k - 0.5)² = (2x_k + 3) + (-2y_k + 2) = 2x_k - 2y_k + 5

所以每个像素只需要维护一个整数 p，每步做一到两次加法，然后根据 p 的符号决定像素位置和下一步增量。这个递推结构是整个算法的灵魂。

2.3 八分对称性，画 45 度就能得到整圆

圆有八重对称：给定第一象限右上角 0 到 45 度之间的一段圆弧上的点 (x, y)，可以通过镜像得到整个圆上的八个点。

标准做法是只生成第一象限从 (0, r) 到 (r/√2, r/√2) 附近的这段八分之一圆弧，每次输出八个对称点：

• (x, y)、(y, x)
• (-x, y)、(-y, x)
• (-x, -y)、(-y, -x)
• (x, -y)、(y, -x)

循环的终止条件就是 x > y。一旦 x 超过 y，说明已经走过 45 度分界线了，再用同样的增量去走，步进方向就会跟当前斜率不匹配，继续下去只会画出歪的圆弧。

一个容易忽略的细节是：在八分对称的应用中，最后画出的圆在不同角度区域可能会出现“毛刺”或半像素错位，肉眼在低分辨率下尤其明显。严格的中止条件，比如 x >= y 而不是 x > y，能稍微改善这种情况，但根本原因是对称映射时像素中心取整方式不一致。某些工程实现里会刻意对跨 45 度线的像素做一次“修正填充”来消除毛刺。

2.4 整数化处理的工程细节

p_0 = 1.25 - r 里的小数 0.25 怎么处理？如果不处理，整个递推过程就要引入浮点加法，算法优势就没了。

一个标准技巧是把所有 p 值乘以 4。因为递推增量的系数全是整数，乘 4 只是把初值变成 5 - 4r，后续每次的增量变成原来的 4 倍，而符号判断不受影响。这样整个算法就完全脱离了浮点。

我见过另一种做法，初值直接用 1 - r，判断条件改成 p < -0.25，这样在做最后一轮比较时会出问题，因为 p 可能累积出各种非整数余量。乘 4 是最省心的，遇到 p_0 是 1.25 这类分数，一律先对齐再判断。

下面是完整可跑的核心循环，只依赖画点函数：

void drawCircleMidpoint(int cx, int cy, int r) { int x = 0; int y = r; int p = 5 - 4 * r; /* 4 * (1.25 - r) */ while (x <= y) { drawPixel(cx + x, cy + y); drawPixel(cx + y, cy + x); drawPixel(cx - x, cy + y); drawPixel(cx - y, cy + x); drawPixel(cx + x, cy - y); drawPixel(cx + y, cy - x); drawPixel(cx - x, cy - y); drawPixel(cx - y, cy - x); x++; if (p < 0) { p += 4 * (2 * x + 1); /* 对应 2x_k + 3 的4倍增量 */ } else { y--; p += 4 * (2 * x - 2 * y + 1); /* 对应 2x_k - 2y_k + 5 的4倍增量 */ } } }

注意这里的增量形式。因为我先把 p 乘了 4，所以在循环体里 x 已经先加了 1，增量公式里的 x_k + 1 就变成了当前的 x，需要相应调整写法。上面代码里 p += 4 * (2 * x + 1) 对应 E 点增量，p += 4 * (2 * x - 2 * y + 1) 对应 SE 点增量，都是 x 自增之后的值，推导时留意这个先后顺序就行。

这个版本没有任何乘方运算，也没有浮点值，即便在几十 MHz 的 MCU 上也能轻松画出小半径圆。

3. 椭圆光栅化：先把圆形算法的“八对称”忘掉

椭圆的光栅化，难度比圆高一个台阶。很多人以为“把圆压扁一点不就行了”，我在第 4 节会详细讲为什么这条路有坑。这里先讲正规做法——中点椭圆法。它的推导思路和画圆一脉相承，但有两个关键差异：椭圆只有四重对称，而且必须分成两个区域来处理。

3.1 为什么椭圆不能直接套用中点画圆法

标准椭圆方程是 x²/a² + y²/b² = 1，a 是半长轴，b 是半短轴。为了去掉除法，乘以 a²b² 得到隐式形式：

f(x, y) = b²x² + a²y² - a²b² = 0

椭圆只有 x 轴和 y 轴两条对称轴，也就是只支持四对称，不能像圆那样用一个八分之一圆弧生成全部像素。

更重要的是，椭圆在不同位置的切线斜率变化不均匀。在第一象限右上角那一段弧线上，靠近顶点 (0, b) 的位置，切线接近水平，此时沿 x 方向步进是合理的；但靠近 (a, 0) 的位置，切线接近垂直，继续沿 x 方向步进就会造成像素点越来越稀疏，刚才讲圆的显式方程问题时的那一幕会再次上演。

3.2 两区域分割点：梯度方向决定步进方向

正确做法是把第一象限的椭圆弧分成两段：区域 1 从顶部 (0, b) 到某一点，这一段曲线斜率绝对值小于 1，适合沿 x 方向步进；区域 2 从该点到右侧 (a, 0)，斜率绝对值大于 1，适合沿 y 方向步进。

关键在于怎么找切换点。用隐式方程求导，椭圆上 (x, y) 处的切线斜率为 dy/dx = -(b²x)/(a²y)。令斜率绝对值为 1，得到 b²x = a²y。这个条件意味着梯度向量 (2b²x, 2a²y) 的两个分量相等，恰好是斜率绝对值等于 1 的几何时刻。

工程实现里不需要解这个方程的精确位置，而是在区域 1 的迭代过程中，每步都检查一下当前 (x, y) 是否满足 b²x ≥ a²y。一旦满足，说明已经越过斜率 1 的分界点，立刻切换到区域 2。按区域 1 的步进方式继续走下去，就会在 x 方向过度采样。

3.3 区域1与区域2的决策参数推导

区域 1 的递推和圆的思路一致，每一步从当前像素 (x_k, y_k) 出发生成下一点，只是在候选点的选择上略有不同——由于斜率小于 1，x 每步必加 1，y 保持不变或减 1。

定义区域 1 的决策参数为 M1 = f(x_k + 1, y_k - 0.5)，代入隐式方程：

p1_k = b²(x_k + 1)² + a²(y_k - 0.5)² - a²b²

若 p1_k < 0，中点在椭圆内，选 E 点（x+1, y）；否则选 SE 点（x+1, y-1）。仿照圆的做法，对两个分支做差分：

选 E 时： p1_{k+1} - p1_k = 2b²x_{k+1} + b² = 2b²(x_k + 1) + b²

选 SE 时： p1_{k+1} - p1_k = 2b²(x_k + 1) + b² - 2a²(y_k - 1) = 2b²x_k + 3b² - 2a²y_k + 2a²

初值 p1_0 = f(1, b - 0.5) = b² + a²(b - 0.5)² - a²b²。

区域 2 的步进方向变了：y 每步必减 1，x 保持不变或加 1。决策参数取中点 M2 = (x_k + 0.5, y_k - 1)，即：

p2_k = b²(x_k + 0.5)² + a²(y_k - 1)² - a²b²

若 p2_k < 0，说明中点在椭圆内，选右侧的 E 点（x+1, y-1）；否则选 S 点（x, y-1）。差分结果：

选 E 时： p2_{k+1} - p2_k = 2b²(x_k + 1) - 2a²(y_k - 1) + b²

选 S 时： p2_{k+1} - p2_k = -2a²(y_k - 1) + a² = -2a²y_k + 3a²

区域 2 的初值，用区域 1 切换时最后一次迭代得到的 (x_k, y_k) 直接代入 p2 公式计算。

这两套决策参数各自维护一个整数（或乘 4 后的整数），交界处重新初始化一次即可。写出来的代码长一点，但每一轮循环的运算量和画圆基本持平。

4. 偷懒方案：把圆“压扁”成椭圆，行不行

正规的中点椭圆法虽然严谨，但推导和编码都比画圆复杂不少。很多人在实际项目里会想：我直接用中点画圆法画一个圆，然后把所有像素点按 y 坐标缩放 b/a 倍，不就是一个椭圆了吗？先不说视觉上成不成立，这个方案的数学后果得掰扯清楚。

4.1 均匀缩放带来的像素密度问题

“压扁”在数学上是一个仿射变换：从圆心出发，把每个点的 y 坐标乘以缩放因子 s = b/a。圆上的均匀参数点在变换后依然均匀分布在椭圆上——这里的“均匀”指的是参数意义上的均匀。

但光栅化关心的不是参数均匀，而是弧长均匀。圆上相邻像素之间的弧长在压扁后发生了方向性变化：水平方向的间距保持不变，垂直方向却全部缩短了 s 倍。结果就是椭圆在上下两端（原本圆的最顶部和最底部）的像素点变得异常密集，而左右两侧和原来一样稀疏。如果 s 远小于 1，比如画一个扁扁的椭圆，顶部会明显出现“堆积”的像素簇。

对只画轮廓的场景，比如 UI 上的一个装饰性椭圆外框，这个密度不均通常能忍；但如果你是在做图形学实验，比如要沿椭圆弧均匀分布地放置标记点、做文字排版或测量弧长，这种方案就没法用了。

4.2 法线方向失真才是真正的坑

比像素密度更隐蔽的问题发生在法线方向。

圆在某个像素点处的法线，指向圆心方向。压扁变换之后，如果你只是把这个法线向量也做相同的 y 缩放并归一化，得到的向量并不是椭圆在该点的真实法线。

原因在于仿射变换不保持角度。圆上的所有点都满足“半径垂直于切线”，但压扁之后，原本 90 度的关系被破坏了。你算出来的“伪法线”和真实椭圆的法线之间存在一个角度偏差，这个偏差在椭圆的长轴和短轴附近的中间区域最大，可以达到好几度甚至十几度。

做纯轮廓绘制无所谓，但凡是需要根据表面法线计算光照、反射、阴影偏移的场景——比如在一个 2.5D 渲染器里用椭圆当某种粒子的外形，或者做椭圆的描边加宽——用缩放圆的伪法线就会让效果明显不对劲。我干脆在 3.5 节里单独说明：如果只是描边，问题不大；带光照和偏移就老老实实算真法线。

4.3 什么场景下可以接受压扁方案

倒也不是说压扁方案一无是处。它最大的优势是实现成本极低：判断一个点是否在椭圆内部也很快，但“画”比“判断”麻烦一些。把它列到工程权衡里，有几个适用场景：

• 半径比例接近 1 的椭圆，即接近圆的形状，密度问题和法线偏差都很小；
• 对精度要求不高、只需要视觉近似的大背景装饰；
• 性能极其紧张，且不需要精确法线信息的极简渲染环境。

我自己的原则是：能接受“看起来像”，就压扁；只要后续需要围绕椭圆做任何几何计算，就走中点椭圆法。

5. 实际测试与工程里的取舍

理论推导写了这么多，最终还是要落到代码里跑一跑。我拿一个纯软件渲染的模拟环境做了对比测试，分别用朴素开方法、压扁画圆法、中点椭圆法画了半径 200 的圆和 400×200 的椭圆，记录每帧耗时和像素覆盖率。

5.1 三种方案的性能与效果对比

显式方程方案的问题不只是慢。半径越大，sqrt 计算越密集，且稀疏点的问题越严重。中点椭圆法的耗时主要花在维护两套决策参数和切换区域的判断上，平均每个像素多一两次整数比较，在软件渲染器里几乎感知不到差异，但轮廓和密度都明显更均匀。

5.2 抗锯齿怎么做最划算

圆和椭圆这类高阶曲线，锯齿感比直线更扎眼，尤其是在低分辨率屏幕上做大半径图形时。抗锯齿方案无非两类。

其一是几何近似抗锯齿，也就是把每个像素当作一个正方形区域，计算曲线穿过的面积占比，然后以比例为 alpha 填充。这个思路对圆和椭圆都可以解析推导，但公式比较复杂，而且到第二象限要重新推导对称关系，工程量大。

其二是超采样，也是最推荐的做法。不需要动光栅化核心，直接用中点法把每个像素的多个采样点都跑一遍，或者更高效的做法是先画出原始轮廓位图，再对边缘像素做一次 4x 或旋转网格采样。旋转网格采样比规则网格效果好，因为它在水平和垂直方向各偏移 0.5 个像素，能同时抑制横竖两个方向的锯齿。实测下来，边缘采样密度 4x 的旋转网格，视觉质量已经接近 16x 规则网格，代价却小得多。

5.3 我在实际工程里的取舍经验

最后分享一点个人经验，属于那种不跑几个项目不会留意的细节。

第一，区域切换点别用解析解硬算。网上有些资料会给出椭圆区域 1 和 2 切换点的解析坐标公式，算出来后作为循环边界。但光栅化过程中像素是离散的，解析切换点往往落在两个像素之间，直接硬切容易出现一条像素宽的“断痕”。更稳的做法是按照梯度条件 b²x ≥ a²y 在循环里动态判断，让切换点落在第一个满足条件的像素上。

第二，整数化时要格外小心除法。中点椭圆法的隐式方程里有 b² 和 a² 这些乘积项，半径很大时这些项会迅速膨胀。比如 800×600 的椭圆，a²、b² 直接到几十万量级，决策参数的中间值可能到百万级。如果你用的是 16 位整数，早就溢出了。要么用 32 位甚至 64 位整数，要么在计算前对 a、b 同时做约分处理。这个坑我实际踩过，画大半径椭圆时出现奇怪的弧线断裂，排查半天才发现是整数溢出。

第三，如果只是画轮廓，其实还有更轻量的方案——参数方程法，用角度步进加正余弦查表。预计算一张 0 到 90 度的正弦表，然后通过对称性生成整圆。这个方法每帧要做一次查表和两三次整数乘法，比中点法慢，但胜在代码简单，而且直接得到的是“均匀角度分布”的像素点。对于动画里需要椭圆沿轨道运动的场景，它还更容易扩展。

一句话总结我的选择：静态轮廓用中点椭圆法，动态运动轨迹用查表参数法，视觉近似用压扁法，而显式方程法，除了教学演示，基本可以永远排除在工程之外。