你第一次在光栅屏幕上画完一个“圆”的时候多半会盯着它愣两秒明明数学公式里圆是完美对称的屏幕上出来的却是一圈阶梯状的小方块而且某些位置还明显“胖”了一点。计算机图形学里的圆的生成算法就是用来解决这个矛盾的——怎么让离散的像素网格尽可能逼近连续的圆同时让计算足够快、好实现。这也是图形学实验里最经典的入门题目之一适合刚学完直线生成、想过渡到曲线光栅化的同学也适合想做图像处理或游戏渲染但需要补一补底层原理的人。这个实验表面上只做一件事给定圆心和半径输出一组像素坐标来显示一个圆。但真正写起来背后涉及坐标系变换、整数化优化、对称性利用、像素误差控制一大堆问题。我当初做这个实验时一开始天真地用了三角函数逐点描点结果圆是画出来了程序却卡得让人想砸电脑而且放大后还能看到一堆不对称的缺口。后来老老实实把中点画圆算法啃了一遍才发现原来“快”和“准”是可以同时做到的。1. 实验需求与算法选型思路1.1 这个实验到底要解决什么问题先明确一下输入输出。实验的输入通常是圆心坐标xc, yc和半径 r输出是一组屏幕像素坐标集合这些像素在视觉上应当构成一个圆。注意这里说的“视觉上构成圆”和数学意义上的圆是有区别的因为屏幕由离散像素组成我们只能选择那些距离真实圆最近、且能保持轮廓连续的像素点。圆的数学表达有三种常用形式。第一种是隐式方程 F(x, y) x² y² - r² 0这种形式适合做判别判断某一点相对圆的位置第二种是显式方程 y ±sqrt(r² - x²)可以逐点算出坐标但存在两个问题一是每次都要算平方和开方浮点开销大二是当 x 接近 r 时y 的变化率趋近无穷大采样点会变得稀疏画出来边缘会出缺口。第三种是参数方程 x r·cosθy r·sinθθ从0到360度遍历这个最容易理解但三角函数计算代价更高而且步长取不好会重复点或漏点。我们最终选用的中点画圆算法核心思想其实是从隐式方程出发利用“当前点和下一个候选点之间的中点位置”来决定下一个像素到底落在哪里。它最大的优点是整个决策过程只涉及整数加法和比较没有乘法没有浮点运算尤其适合在没有FPU的老式硬件或需要海量绘制的场景下使用。1.2 方案选型为什么不是直接算坐标很多初学者会问既然参数方程那么直观为什么还要绕一大圈用中点判别法这个问题我当年也问过。答案不在于“能不能画出来”而在于“画出来的代价”。假如半径 r 100用参数方程画圆如果步长取 0.1 度要循环 3600 次每次都要计算 sin 和 cos如果步长取 1 度只需要 360 次三角函数运算但你会发现圆看起来不够连续尤其是大半径时弧线上会出现明显的折线感。而直接用 y sqrt(r² - x²) 计算每取一个 x 都要做一次平方和一次开方在几百个像素的规模下问题不大但放到嵌入式设备或需要逐帧绘制大量图形的场景里这种性能损耗是不划算的。中点画圆算法则把问题转化成了一个“二选一”的决策过程当前位置确定后下一个像素要么向右走一步E要么向右下方走一步SE具体走哪边取决于这两个候选点的中间位置在圆内还是圆外。每次决策只需要做一次整数加法来更新判别值整个圆绘制下来连乘法都很少用。这正是“光栅化算法”的精髓把连续几何问题转化为离散像素的逐步决策问题。我还需要补充一点实验里通常要求至少实现一个算法并对比不同算法的效果。所以选型时不要只挑最简单的写建议把直接代入法、参数方程法和中点画圆法都写一遍用数据说话这样实验报告才有得写。2. 核心原理八对称性与中点判别式推导2.1 八对称性只画八分之一圆弧的秘诀圆是所有图形里对称性最好的一种。任意一个圆关于圆心水平、垂直以及45度、135度方向共八条对称轴都是镜像对称的。这意味着只需要计算出第一象限中从0, r到r/√2, r/√2这一段八分之一圆弧上的点其余七个部分的点都可以通过坐标变换直接映射出来。假设我们计算出了某个点x, y那么在八个象限位置上的对应点分别是区域坐标变换第一区0°~45°(x, y)第二区45°~90°(y, x)第三区90°~135°(-y, x)第四区135°~180°(-x, y)第五区180°~225°(-x, -y)第六区225°~270°(-y, -x)第七区270°~315°(y, -x)第八区315°~360°(x, -y)这套映射关系是整个算法性能的基石。把计算量缩小到八分之一后即使是运行在慢速设备上的纯软件渲染也能获得不错的帧率。映射实现时只需注意一点当 x 和 y 相等时也就是在45度角边界处两个相邻区域会映射出同一个点必须在代码里避免重复绘制否则像素颜色叠加会带来不必要的开销。2.2 决策参数的推导判别式是怎么来的中点画圆算法的核心是维护一个决策参数 d。我们以圆心在原点、半径为 r 的第一象限八分之一圆弧为例来推导。圆函数定义为F(x, y) x² y² - r²这个函数的性质很明确点在圆内时 F 0点在圆上时 F 0点在圆外时 F 0。假设当前已经确定了像素点 P(xp, yp)下一步需要从两个候选点中选择一个E(xp1, yp)向右和 SE(xp1, yp-1)向右下。我们取这两个候选点的中点 M(xp1, yp - 0.5)代入圆函数计算 F(M)。如果 F(M) 0说明中点位于圆内部这意味着真实圆弧更靠近右边的点 E所以下一个像素应选 E如果 F(M) 0说明中点位于圆外部圆弧更靠近右下方的点 SE所以下一个像素应选 SE如果 F(M) 0理论上两者都满足约定统一取 E或者统一取 SE结果差别不大。基于这个规则定义决策参数 d F(M)然后推导递增公式。初始时圆弧起点是 (0, r)所以第一个中点 M 的坐标是 (1, r - 0.5)代入圆函数得到d0 1² (r - 0.5)² - r² 1 r² - r 0.25 - r² 1.25 - r后续更新采用递推方式。如果当前 d 0选了 E 点下一个中点是 (xp2, yp - 0.5)新的决策参数为d_new (xp2)² (yp - 0.5)² - r²将它与当前 d 做差可得d_new d 2xp 3如果当前 d ≥ 0选了 SE 点下一个中点是 (xp2, yp - 1.5)同理可得d_new d 2xp - 2yp 5这两个递推公式是整个算法的骨架接下来的代码只是按这个骨架逐点推进而已。2.3 从浮点到整数判别式整数化的关键一步细心的你应该发现了初始判别式 d0 1.25 - r 里面有小数这与“纯整数运算”的目标矛盾。解决办法是不直接使用 d 本身的数值而是定义一个新的整数变量 e d - 0.25。因为我们在决策时只关心 d 的符号不关心它的大小减去 0.25 不会改变符号正负。于是初始参数变为e0 d0 - 0.25 1 - r对应的更新规则也相应调整d 0 时取 E同时 e 增加 2x 3d ≥ 0 时取 SE同时 e 增加 2x - 2y 5。在实际编码时为了代码可读性通常仍用 d 命名但初始值直接赋成 1 - r。这样整个算法从初始化到结束全程都是整数运算彻底摆脱了浮点依赖这也是它能在各类嵌入式平台和早期显卡渲染管线上长期占有一席之地的根本原因。3. 实操过程与核心环节实现3.1 核心函数画圆算法完整实现接下来直接给出可以抄作业的核心函数代码。为了通用我用 C 语言风格来写并把画点操作抽象出来方便你适配自己用的图形库或窗口框架。void drawCircle(int xc, int yc, int r) { int x 0; int y r; // 使用整数化后的初始判别式 e 1 - r int d 1 - r; // 画出八个对称点 drawCirclePoints(xc, yc, x, y); // 循环条件在第一象限内 x 增加、y 减少当 x y 时已越过45度线 while (x y) { if (d 0) { // 中点位于圆内选择 E 点 d 2 * x 3; x; } else { // 中点位于圆外或圆上选择 SE 点 d 2 * (x - y) 5; x; y--; } drawCirclePoints(xc, yc, x, y); } } void drawCirclePoints(int xc, int yc, int x, int y) { setPixel(xc x, yc y); setPixel(xc - x, yc y); setPixel(xc x, yc - y); setPixel(xc - x, yc - y); setPixel(xc y, yc x); setPixel(xc - y, yc x); setPixel(xc y, yc - x); setPixel(xc - y, yc - x); }这段代码最关键的地方在于理解 setPixel 调用为什么放在 while 循环的出口处以及为什么每轮更新完坐标就立刻画点。原因是我们每次计算出的 (x, y) 本身就是当前已确定的圆弧点立刻通过对称映射绘制出来即可不需要像直线算法那样区分“先决策再画还是先画再决策”。注意循环条件是while (x y)这保证我们只处理从正上方 (0, r) 到45度对角线 (r/√2, r/√2) 之间的弧段。一旦 x y说明已经越过了45度线再继续计算就会与对称映射重复。3.2 坐标变换与显示集成从数学坐标到屏幕坐标上面的函数假设圆心在坐标原点且 y 轴向上为正。但大多数图形库和屏幕坐标系的 y 轴是向下为正的原点在左上角。因此真正显示时还得做一步坐标变换。以圆心为 (cx, cy) 的情况为例屏幕上的实际绘制坐标应该是(cx xi, cy - yi)其中 (xi, yi) 是算法算出的数学坐标系下的点。如果你用的是标准 Windows GDI 或类似接口直接把这个换算合并到 setPixel 的实现里即可。不过要注意如果你的窗口做了缩放适配物理像素和逻辑像素之间可能存在比例差异这个我们后面在“圆变形”的问题里细说。另外圆心 (cx, cy) 本身也应该是整数。当你从鼠标事件拿到的是浮点坐标时最简单的处理方案是四舍五入取整。这样做对大半径圆几乎没有视觉影响但如果你画的是半径只有两三个像素的小圆取整误差会被放大圆看起来可能就变成了斜方块。这种情况我会建议把整个绘制过程放在一个更高分辨率的离屏位图上进行再整体缩放显示。3.3 实验参数记录不同半径与圆心位置的处理做实验报告时建议固定圆心分别测试半径 r 5、20、100、500 四组数据把计算出的像素点数、肉眼观察到的对称性、以及程序运行耗时记录下来。具体来说当 r 5 时圆只有寥寥数十个像素八对称映射后可能只有约32个像素点此时很容易看出锯齿这是正常的物理限制。当 r 100 时肉眼看到的圆已经比较平滑但放大到像素级仍然能看到阶梯。当 r 500 时算法循环次数约为500次整个绘制过程肉眼无法察觉耗时但如果你用直接开方的方法每次循环的浮点运算开销会明显变大。圆心位置对算法没有任何额外影响因为参数只和半径相关圆心只承担平移作用。但要注意当圆心坐标接近屏幕边缘时对称映射可能产生负坐标或者超出画布范围最终被画到看不见的区域。实践中需要做边界裁剪或者在贴图前判断目标坐标是否在有效范围内。4. 实验数据验证与误差分析4.1 常见算法性能对比为什么中点法最快这个实验最值得做的事就是把几种画圆算法拉出来做横向对比。我实测过一组数据在普通桌面环境下用同一套软件渲染管线绘制半径 100 的圆算法主要运算循环次数相对耗时视觉质量隐式方程逐点扫描平方、开方、比较约200高边缘有缺口参数方程步长1°三角函数360次360中连续但略粗DDA画圆浮点加法约100较低较好中点画圆整数加法和比较约100最低最佳需要解释一下为什么中点画圆的循环次数只有大约100次因为我们只画八分之一圆弧从 (0, r) 到 (r/√2, r/√2)x 每步加1总共大约 r/√2 ≈ 71 步加上初始点共约71个点。而参数方程360次循环是完整圆周每次还要乘以半径和三角函数。相比之下中点法无论从计算量还是存储需求上都胜出一截。实际测试中我用中点画圆法同时绘制上千个随机位置的圆帧率依然稳定。但如果换成参数方程法一旦圆的数目突破两百个画面就开始明显掉帧。这在实际游戏粒子系统或地图标注绘制中就是天壤之别。4.2 像素级误差为什么边缘会有锯齿和不对称理论上只要初始判别式和递推公式正确画出来的圆一定是对称的。但在我的实验里第一次跑出来的圆明显出现了“右上和左下不对称”的情况。排查后发现问题出在 setPixel 的坐标处理上——我在画对称点的时候没有考虑到屏幕坐标 y 轴翻转导致下方两个象限的点其实被映射到了错误的位置。这个坑在验证图形时最难发现问题因为你第一眼看到圆还在但放大后才发觉下半部分半径跟上半部分不一致。锯齿则是光栅化的必然结果。每个像素方块是正方形的要逼近连续的圆弧边缘一定会呈阶梯状。要减轻锯齿效果可以引入超采样抗锯齿SSAA在4倍分辨率下绘制再按比例缩小回原分辨率边缘会平滑很多。或者简单做灰度覆盖即根据像素被圆覆盖的百分比来设置透明度视觉上柔和但坐标计算会复杂一些这里暂不展开。5. 常见问题与排查技巧实录5.1 圆变成了椭圆或扁圆这是最常见的现象。原因基本集中在两个一是屏幕像素本身的物理宽高比不是1:1二是你的绘图坐标系在横纵方向上的缩放系数不一致。比如很多窗口系统的默认坐标系是 y 轴单元格高度大于 x 轴宽度同样是“50个像素”纵向看起来会比横向长。解决思路是统一坐标缩放。可以在初始化时读取图像或屏幕的 DPI 信息计算出横纵缩放比然后把圆的半径在 y 方向乘上该比例因子。如果你只是做实验最简单的方法是强制用正方形窗口并把窗口客户区的高宽设成一致。验证是否修正好的办法是画一个圆心在中心的圆测量左右边界和上下边界到中心像素的距离在相同像素数下应该相等。5.2 圆有明显的缺口或局部消失如果你是照着网上某段代码写的且画出来的圆在某个象限缺了一块多半有这几种可能第一对称映射的坐标变换写错了比如应该用(xc - x, yc - y)的地方写成了(xc x, yc - y)这会导致右下象限的点错误地覆盖到右上象限。第二循环终止条件写成了while (x y)这样会在 x y 时把对角线上的点重复绘制两次虽然可见性不受影响但如果你在绘制前有“像素是否已写”的判断逻辑重复绘制可能会导致某些点被跳过。第三setPixel中做了越界裁剪而你的圆心离边界太近某几个对称点超出了画布范围被裁剪掉了视觉上就会像缺了一块。处理越界问题的标准做法不是直接丢弃超界点而是用裁剪算法算出可视区域内的部分。但对本实验而言你只需要保证圆心离边界距离大于半径即可。5.3 画大圆时卡顿明显如果你用中点画圆法还卡顿问题几乎不可能是算法本身而多半出在显示刷新策略上。常见的错误是每次 setPixel 都直接调用系统绘图接口而系统接口内部会做大量的状态检查和缓冲区同步画一个半径1000的圆要调用几千次系统函数性能自然灾难。正确做法是先把所有计算出的像素点写入一个内存缓冲区比如位图对象等全部点都写完之后一次性把缓冲区整体刷新到屏幕上。我把这个改进应用到实验里之后绘制效率提升了近两个数量级。这个思路对所有图形学实验都适用。5.4 圆太小或者太细看不清当半径小于等于3时中点画圆算法画出来的其实不是圆而是几个孤立像素点和直角状方块这是分辨率限制下的正常结果任何算法都无法改变。如果你需要在屏幕上突出显示小圆可以在此基础上增加线宽支持即每个算法计算出的像素点不是画一个点而是画一个以该像素为中心的3x3或5x5小方块视觉上相当于给圆加粗了。实现起来很简单setPixel 里多画一个矩形即可。6. 实验扩展从圆到椭圆与填充6.1 椭圆的中点算法推广如果你把圆的实验吃透了那么椭圆的中点算法几乎不需要额外学。椭圆的隐式方程是 F(x, y) b²x² a²y² - a²b²其中 a 是长半轴b 是短半轴。由于椭圆只有四个对称方向不是八个所以需要区分两个区域在区域1中x 的增长速度大于 y 的变化主要决策是 E 还是 SE在区域2中y 的变化占主导主要决策是 S 还是 SE。两个区域的判别式初始值和递推公式都不同推导思路和圆完全一致都是取候选点中点代入椭圆方程判断正负。6.2 圆的填充与扫描线算法有时候实验要求做的不是画圆轮廓而是填充圆。核心思路有两条路可以走一是先用中点画圆算法算出轮廓上的所有像素然后对每条水平扫描线找出左右两个端点像素把中间的所有像素填充掉二是直接用种子填充算法从圆心开始不断向上下左右扩散直到碰到边界颜色为止。前者计算可控、效率高更适合作为圆的扩展实验后者实现简单但需要显式的栈或队列来管理种子点否则递归深度容易爆栈。6.3 加一个鼠标交互拖动画圆实验做完后如果你还有余力可以写一个最简单的鼠标交互按下鼠标左键记录圆心拖动过程中不断根据当前鼠标位置计算半径并调用 drawCircle 预览松开鼠标确定最终圆。整个逻辑不复杂但能让实验报告从“静态算法”升级为“完整交互应用”展示效果会好很多。有一点要注意拖动过程中会不断重绘整个圆一定要先清空画布再画新的圆否则旧圆会残留在屏幕上形成残影。继续沿用中点画圆的核心代码不需要、也不会改到算法内部。计算的半径用两点间距离公式这一步可以用整数平方代替开方来比较大小只需保持排序一致性即可。写到这里这个实验的核心已经全部过了一遍。最后说一个我自己的笨经验一开始我为了验证算法正确性想出各种测试用例结果在半径只有2的小圆上反复纠结了很久因为怎么看怎么像“四个点围成方块”一度怀疑算法写错了。后来才意识到光栅化的本质就是用离散像素去逼近连续图形关键是明确“这个算法在哪些尺度下是有效的”。做图形学实验最重要的不是背公式改代码而是理解每个像素的取舍依据。你把这个圆的实验吃透之后再去学椭圆生成、多边形填充、甚至 GPU 渲染管线里的三角形光栅化会发现底层逻辑全都是一脉相通的。