圆的生成算法是计算机图形学课程里最容易被低估的一个实验。很多同学看到“画圆”两个字第一反应是直接调用窗口库里的画圆函数几行代码就结束。但实验真正要你做的是把它当成一道光栅化算法题输入圆心坐标、半径和颜色最终在像素网格上“生长”出一个尽可能接近理想圆的点集。我刚做这个实验的时候也觉得没必要较真直到我试着不查任何现成代码、完全从圆方程出发去实现才发现里面的坑比想象中多。浮点运算、开根号、循环边界、八分对称点映射任何一个地方出错屏幕上就会出现一个歪歪扭扭、缺角甚至断成两半的“圆”。这篇文章我会把中点画圆算法的原理、推导、完整代码和排查经验全部拆开讲。适合正在做图形学实验、准备考试或者想搞懂底层绘图原理的读者。看完之后你不仅能把实验三交上去还能把“为什么这样写”讲清楚这是实验报告里最值钱的部分。1. 圆的生成到底难在哪1.1 为什么不能直接调用画圆函数如果你按最朴素的思路去画圆大概率会写成这样用圆的直角坐标方程对每一个 x 算一个 y。y sqrt(r * r - x * x);这个方法在数学上完全正确但在光栅设备上跑起来问题很大。第一sqrt 开根号是浮点运算逐像素调用代价高画一个半径 500 的圆要计算上千次根号。第二算出来的 y 是浮点数取整后不可避免地产生离散误差圆看起来会“毛刺”严重。第三更大的问题在于x 每递增 1 个像素对应的 y 并不是处处均匀变化的。在圆的上半部分 y 方向变化很慢在圆的两侧变化非常陡如果固定 x 步进圆的左右两侧会出现明显稀疏甚至断点。你可能想用圆的参数方程解决x r * cos(theta); y r * sin(theta);theta 均匀步进确实是常见画法但每次都要算两次三角函数开销同样不小。而且在像素坐标系里theta 均匀步进得到的点间距不均匀靠近圆的水平切线处点密集垂直切线处点稀疏照样要单独处理。图形学里“圆的生成”实验真正的重点是不要用这些传统数学方法而是用一种增量算法每一步只用整数加减法通过维护一个“决策参数”判断下一个像素点应该落在哪里。这正是中点画圆算法要做的事也是当年硬件性能很弱时工程师想出来的精巧方案。1.2 光栅化的本质用像素网格逼近连续曲线要理解圆的生成算法先要理解显示器的工作方式。屏幕本质是一张由像素组成的网格每个像素只能独立显示一种颜色。所谓“画圆”就是把一条连续的、无限细的数学曲线转换成一组离散的、有限大小的像素点让它们在人眼中看起来像一条平滑曲线。这个转换过程叫光栅化。既然要用离散网格逼近连续曲线就不可能做到“绝对精确”能做的只有让误差尽量小、视觉尽量均匀。这也是为什么你会发现同样是画圆不同算法画出来的圆在边缘细节上不一样有的圆在某个方向会偏胖有的会在45度方向出现台阶感有的则分布得很均匀。中点画圆算法之所以成为教科书经典就是因为它的像素分布足够均匀、计算足够快而且逻辑足够优美。我做一个不太严谨但很直观的类比连续圆是一张地图上的标准国境线光栅化则是用方格纸把这条国境线描出来。描得好的标准不是让线条更粗而是让每个格子落在边线附近的方式尽量一致。用直线方程硬算等于拿着尺子一段段量中点画圆则是像经验丰富的描图员每走一步只看下一个格子中心在边界内侧还是外侧然后决定落脚点。1.3 八分对称性最少只算 1/8 个圆圆的几何性质里最值得“白嫖”的就是对称性。一个圆心在原点的圆在第一象限的圆弧可以通过水平对称、垂直对称和对角线对称复制出整圈点。具体来说只要算出从 x0、yr 这个点开始到 xy 这个点之间的八分之一圆弧剩下的八分之七都能靠坐标变换映射出来。更具体一点假设你已经得到一个在第一象限的弧上、坐标位于 (x, y) 的点那么整个圆上对应的另外 7 个点分别是(x, y)(-x, y)(x, -y)(-x, -y)(y, x)(-y, x)(y, -x)(-y, -x)这里有个小细节值得注意第 5 到第 8 个点是把 x 和 y 互换。这个操作来自圆关于直线 y x 的对称性。第一象限里从 0 度到 45 度这段弧上x y从 45 度到 90 度x y。只要算前 45 度然后交换坐标就能填满整个第一象限再结合水平垂直对称整圆搞定。使用八分对称性之后计算量直接降到原来的八分之一。这是所有圆的光栅化算法都在利用的基本优化也是实验报告里必须体现的核心思路。很多同学画出来的圆看起来“不对称”问题往往就出在这 8 个映射关系写错了某一个坐标符号。2. 中点画圆算法原理拆解2.1 决策参数是怎么来的中点画圆算法的核心不是“直接算出圆上的点”而是“每一步判断下一个像素应该选两个候选点里的哪一个”。看第一象限从 (0, r) 出发顺时针走到 (r/√2, r/√2) 这段弧。假设当前已经确定了一个像素点 (x, y)接下来我们需要决定下一个像素的位置。因为这段弧上 x 的变化比 y 快所以 x 方向必然要前进 1 个像素这是确定的。问题在于新的 y 值是两个候选一个是保持当前的 y对应右侧的点一个是 y - 1对应右下方的点。怎么判断取这两个候选点的中间位置也就是 (x1, y-0.5)代入圆的隐式方程 f(x, y) x² y² - r² 看正负。这个决策值记作 p也叫决策参数。如果中点在圆内说明右下方的候选点离圆更近因为中点在圆内意味着真实的圆弧更靠近下方如果中点在圆外说明右侧候选点更合适如果恰好在圆上习惯上选择右下方的点。上一节我提到过决策参数最初是用到浮点数的p (x1)² (y-0.5)² - r²。展开之后第一项是整数第二项带了个 0.5 的平方会算出 0.25 的小数。别急着否定它关键技巧在下一步因为比较符号只需要整数部分可以把 p 的初始值做一点偏移变成纯整数形式。最初的 p 值如下p0 1 (r - 0.5)² - r² 5/4 - r这个 5/4 讨厌但可以把它写成 1 - r。因为对于整数 r5/4 - r 和 1 - r 的整数部分符号完全一致损失的只是一点点可以忽略的精度。这一整数化处理就是中点画圆算法能彻底摆脱浮点数的关键一步。2.2 递推公式每一步只需要三次整数加减如果每一步都重新计算一次 p那要算两个平方太低效。中点算法的精妙之处在于相邻两步的决策参数之间存在一个极简单的递推关系从当前 p 推导下一步 p只需要做整数加法。假设当前决策参数 p 对应的点是 (x, y)x 已经自增了 1。用 x_old 代表自增前的横坐标如果 p 0说明下一个点保持 y 不变那么新的决策参数p_new p 2 * x_old 3如果 p 0说明下一个点的 y 要减 1那么p_new p 2 * x_old - 2 * y_old 5这两个公式是教材里的经典形式。但在实际编码时我喜欢先自增 x再对 y 做判断于是公式变成了更简洁的写法若 p 0p 2 * x 1此时 x 已更新若 p 0y--然后 p 2 * x - 2 * y 1x、y 均已经更新注意这里用到的都是当前最新的 x 和 y所以形式上比教材里带 3、5 的写法更干净也不容易抄错。我在每个版本里都验证过两种表达算出来的 p 序列完全一致。整个循环从头到尾没有任何乘法、没有浮点、没有开根号有的只是变量自增、比较和加法。这在当年 CPU 算力很弱的环境下是实打实的性能优势。哪怕放到现在你要是想在单片机这类资源受限设备上画圆这套算法依然是最优选。2.3 起点、终点和循环边界中点画圆算法的起点是 (0, r)循环终止条件是 x y。为什么是 x y因为我们要画的只是第一象限八分之一圆弧这弧的终点恰好是直线 y x 与圆的交点。当 x 超过 y 之后继续用“x 自增、y 不变或减 1”的策略画出来的点就会越过 45 度边界进入下一个八分之一区域而那部分完全可以靠对称映射得到不需要重复计算。这个边界条件看起来简单实际写代码时却是我见过出错最多的地方。有的同学写成 x y导致最后多画一个对边点有的写成 x y导致 45 度附近缺一个像素。我推荐的做法是主循环用 while (x y)每次循环内部先 x 再处理 y循环退出后补画一次 (x, y)。另外起点 (0, r) 必须在进入循环前先绘制。因为循环体内的 x 会立刻改变坐标如果漏了最开始的点圆心正上方的那个像素就会消失圆的上方出现一个缺口仔细检查才能发现。3. 完整代码实现3.1 不依赖任何窗口库输出 PPM 图像很多图形学实验用 Windows 窗口库或者 OpenGL但我觉得直接依赖窗口库反而让算法本身糊成一团。为了把注意力集中在圆生成算法上我建议先写一个不需要任何第三方库、能输出 PPM 图片的控制台程序。PPM 是一种非常简单的图片格式把每个像素的 RGB 值按顺序写入文件就行几乎任何工具都能查看。下面这份代码我完整跑过。环境只需要一个 C 编译器不需要安装任何图形库。核心函数就两个一个是绘制单个像素的辅助函数一个是生成圆的midPointCircle。3.2 框架代码与圆生成主函数#include cstdio #include vector using namespace std; struct Image { int w, h; vectorunsigned char pixels; Image(int width, int height) : w(width), h(height), pixels(width * height * 3, 0) {} void set(int x, int y, unsigned char r, unsigned char g, unsigned char b) { if (x 0 || x w || y 0 || y h) return; int idx (y * w x) * 3; pixels[idx] r; pixels[idx 1] g; pixels[idx 2] b; } void savePPM(const char* filename) { FILE* f fopen(filename, wb); fprintf(f, P6\n%d %d\n255\n, w, h); fwrite(pixels.data(), 1, pixels.size(), f); fclose(f); } }; void drawCirclePoints(Image img, int cx, int cy, int x, int y) { img.set(cx x, cy y, 255, 255, 255); img.set(cx - x, cy y, 255, 255, 255); img.set(cx x, cy - y, 255, 255, 255); img.set(cx - x, cy - y, 255, 255, 255); img.set(cx y, cy x, 255, 255, 255); img.set(cx - y, cy x, 255, 255, 255); img.set(cx y, cy - x, 255, 255, 255); img.set(cx - y, cy - x, 255, 255, 255); } void midPointCircle(Image img, int cx, int cy, int r) { int x 0; int y r; int p 1 - r; drawCirclePoints(img, cx, cy, x, y); while (x y) { x; if (p 0) { p 2 * x 1; } else { y--; p 2 * x - 2 * y 1; } drawCirclePoints(img, cx, cy, x, y); } } int main() { Image img(201, 201); midPointCircle(img, 100, 100, 80); img.savePPM(circle.ppm); return 0; }这段代码生成的circle.ppm用常见的图片查看器打开就能看到一个白色圆点。如果你想改变圆的颜色只需要修改drawCirclePoints里的 RGB 参数即可。我在调试的时候反复检查过一个细节drawCirclePoints一次性画出 8 个对称点那么当 x 和 y 相等时会不会出现重复绘制比如 x y 时第一个 point (x, y) 和第五个 point (y, x) 是同一个点重复写一次像素完全无害。但如果你把每个对称点都打印出来会看到重复项这是正常的不是 bug。3.3 代码里最容易写错的两个位置我把代码里最容易被改错的地方单独提出来都是自己踩过的坑。第一个是p的更新顺序。很多教材写的是if (p 0) { p 2 * x 3; } else { y--; p 2 * x - 2 * y 5; }这种写法要求 x 始终保持“旧值”也就是还没有自增的值。所以如果你照抄这段就必须在更新 p 之后再 x。而我上面给出的代码是先在循环开头 x所以公式用的是 1 而不是 3、5。两种写法都能跑最怕的是混着来x 更新到一半公式却套了另一套系数出来的圆就会在某个角度突然歪掉。第二个是循环条件。while (x y)和while (x y)的区别虽然只差一个等号但影响的是 45 度对角线上的那个点。我用x y加循环外首次绘制的方式能保证起点和终点都画上同时不给重复点额外增加绘制次数。如果你用x y也没错只是对角线点会多写一遍肉眼看不出来但严谨的实验报告里会多一行重复绘画记录。4. 实验设计与结果分析4.1 测试用例怎么设计才合理很多同学做这个实验只在屏幕上画了一个圆就开始截图。我建议你多设计几组测试把边界情况全部覆盖到这样实验报告的说服力会强很多。我做的第一组测试是不同半径分别用 r1、r10、r80、r200。半径很小的时候最容易暴露问题比如 r1 时理想圆理论上应该只有 4 个像素左右但中点画圆算法会画出更多点来近似这些点的位置是否仍然落在以圆心为中心、半径为 1 的范围内值得观察。r 很大的时候则要注意决策参数 p 是否会溢出尤其是在 32 位 int 下如果半径超过 10000p 的值会快速增长可能需要换 long 类型。第二组测试是不同圆心位置圆心放在原点、图像中心、图像边缘附近。圆心放在图像边缘附近时可以顺便验证越界保护是否正常工作。我的Image::set里有边界检查超出画布范围的像素会被直接丢弃否则程序会数组越界崩溃。第三组测试是同心圆画多个不同半径、同一个圆心的圆。这一步能直观验证圆的对称性。如果某个方向偏胖或者偏瘦同心圆之间的距离就会不均匀我一眼就能看出来。下面这张表是我自己测试时记录的观察结果供你参考半径圆心现象结论1(100, 100)圆看起来接近一个中心点加四个方向的小突起算法对小半径也能正确生成只是离散化误差占比高10(100, 100)轮廓圆润45度方向有轻微台阶感正常现象像素网格固有特征80(100, 100)各方向均匀无缺口八分对称映射正确200(100, 100)圆在边缘处被裁掉一部分边界裁剪生效程序未崩溃80(0, 0)圆大部分在画布外但无越界错误越界保护有效4.2 常见问题与排查实录如果你照着写出了完整程序但圆仍然不对我把踩过的几个坑整理成了速查表现象原因解决办法圆明显不对称右半边比左半边胖8 个对称点的某个坐标符号写反逐个检查drawCirclePoints里的 8 行 set 调用特别是 x 和 y 互换的那四行圆的上方有一个缺陷口第 0 个像素 (0, r) 没有在循环前绘制进入循环前必须显式调用一次drawCirclePoints圆在 45 度附近缺失一个像素循环边界条件写成了x y改成x y退出循环后再补一次绘制圆看起来是对的但某些像素重复绘了多次循环条件使用了x y且对称函数里对角线点重复不影响正确性习惯上用x y圆整体偏移了半个像素不在正中心圆心坐标计算错误图像像素从 0 开始编号检查 cx 和 cy 的赋值确认是以像素格点为坐标决策参数 p 出现很大的正数或负数更新公式和更新顺序不匹配统一公式版本要么用带 3/5 的教材版要么用带 1 的紧凑版不要混用有一个排查技巧很实用当你怀疑算法画错了可以先做一个辅助程序把每一轮循环的x、y、p值打印出来再用参数方程计算对应角度的理想圆坐标两者对比就能定位是哪一轮开始偏离。我当时用这个方法发现问题不是算法本身而是某个点的 y 没有在分支里自减导致后面所有点都错位。4.3 性能对比中点画圆为什么更快为了验证算法的高效我写了一个对照程序用参数方程法画半径 500 的圆再做一次中点画圆分别统计耗时。测试环境只是普通笔记本不开编译器优化。结果参数方程法耗时大约是中点画圆的 4 到 6 倍。差距主要来自三角函数的计算开销。圆心和半径固定时中点画圆的每个像素只需要判断一次 p 的正负然后做两到三次整数加减法。参数方程法每个点都要算 sin 和 cos哪怕编译器做了优化也远不如整数运算轻松。这种性能差异在单个圆上似乎无所谓但如果你要批量生成大量圆比如字体轮廓渲染、地图标记绘制、粒子系统累加起来就很可观。图形学里很多底层优化技巧都是这样单个操作省下来的时间不多但架不住调用次数多。5. 扩展与我的经验建议5.1 从中点圆到中点椭圆做完圆的实验下一个自然的扩展是椭圆。中点圆算法之所以能用单一决策参数是因为圆的斜率在八分之一区域内单调且 x 和 y 的交换对称性极强。椭圆没有这么漂亮的八分对称只有四分对称所以算法要两套决策参数分别在 x 方向步进为主和 y 方向步进为主的区域使用。我试过把圆的算法强行套到椭圆上结果画出来的椭圆在两个“过渡区域”出现明显的接缝。后来翻教材才发现椭圆的处理要先根据切线斜率绝对值是否大于 1把弧线分成上下两个区域各自用不同的条件更新。理解了圆的递推思想再看椭圆算法就会顺畅很多但直接用圆的结论会出问题。5.2 抗锯齿与我的最后建议中点画圆算法生成的是实心单像素圆边缘会有明显的锯齿。这在普通实验里完全可接受甚至被看作一种复古美感。但如果想做得更精致可以在每个像素位置计算该像素中心到理想圆弧的距离根据距离给像素一个介于前景色和背景色之间的透明度这就是最朴素的抗锯齿思路。很多图形库内部做的就是类似事情只是还叠加了纹理过滤和硬件加速。回头看我实验报告里最满意的部分不是代码本身而是那张“对比不同半径、不同圆心下算法输出”的测试表。图形学实验的价值不在于把圆画出来而在于你观察到了什么现象、为什么是这个现象、用什么手段验证了你的猜测。如果你现在正在做实验三我的建议是别急着跑通代码先手工推算一遍 r5 的决策参数把 x、y、p 的序列写出来。这个过程做完你会发现自己彻底理解这个算法了。