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 每步进 1y 的变动很小画出来的点挨得很密可一旦靠近 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_{k1} f(x_k 2, y_k - 0.5) (x_k 2)² (y_k - 0.5)² - r²两式相减p_{k1} - p_k (x_k 2)² - (x_k 1)² 2x_k 3也就是说选了 E 点时p 的增量是 2x_k 3是一个跟当前 x 相关的一次多项式运算成本只有一次加法和一次移位。如果选了 SE 点新决策参数是p_{k1} f(x_k 2, y_k - 1.5) (x_k 2)² (y_k - 1.5)² - r²两式相减p_{k1} - 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² 1a 是半长轴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) 出发生成下一点只是在候选点的选择上略有不同——由于斜率小于 1x 每步必加 1y 保持不变或减 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 点x1, y否则选 SE 点x1, y-1。仿照圆的做法对两个分支做差分选 E 时 p1_{k1} - p1_k 2b²x_{k1} b² 2b²(x_k 1) b²选 SE 时 p1_{k1} - 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 每步必减 1x 保持不变或加 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 点x1, y-1否则选 S 点x, y-1。差分结果选 E 时 p2_{k1} - p2_k 2b²(x_k 1) - 2a²(y_k - 1) b²选 S 时 p2_{k1} - 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 三种方案的性能与效果对比方案单点计算量约正确性适用场景显式方程 y√(r²-x²)每次 sqrt 浮点像素密度不均不推荐压缩圆法整数加比较像素堆积、法线偏离近似轮廓/装饰中点椭圆法整数加比较精确推荐通用显式方程方案的问题不只是慢。半径越大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 度的正弦表然后通过对称性生成整圆。这个方法每帧要做一次查表和两三次整数乘法比中点法慢但胜在代码简单而且直接得到的是“均匀角度分布”的像素点。对于动画里需要椭圆沿轨道运动的场景它还更容易扩展。一句话总结我的选择静态轮廓用中点椭圆法动态运动轨迹用查表参数法视觉近似用压扁法而显式方程法除了教学演示基本可以永远排除在工程之外。