1. 这些基础算法到底解决了个什么问题计算机图形学入门第一道坎不是渲染管线不是着色器而是最底层的“在屏幕上把几何图形变成像素”。游戏里的一条线、一个圆、一个椭圆的边框表面上都是数学公式但屏幕是一格一格的像素点阵不可能像纸上画图那样直接连线。你只能决定每个像素是亮还是不亮亮哪个颜色。这个过程在图形学里叫光栅化Rasterization。而DDA、中点Bresenham这类算法就是历史上为了高效完成光栅化所设计的一套经典思路。它们的共同点是把连续曲线离散成像素坐标。区别在于谁更快、谁更准、谁只用整数运算这在当年的硬件条件下是生死之别。这篇文章我打算把画直线、画圆、画椭圆的算法原理和代码都过一遍包括推导过程、边界情况、我实际写代码时踩过的坑。内容以C语言风格的伪代码为主但你完全可以用任意语言复现。适合两类人看一是刚学图形学、被教材推导绕晕的学生二是做嵌入式图形界面、需要手动绘制点线而不想引入重量级图形库的开发者。为什么到现在还要学这些几十年前的算法因为很多嵌入设备、低端MCU上根本没有GPU你要靠CPU在帧缓冲区里一个一个像素地写这时候一个浮点乘法都可能成为性能瓶颈。DDA和Bresenham的核心理念——用递推代替重复计算用整数避免浮点开销——至今仍然适用。2. 先聊聊DDA算法最直观的等步长逼近2.1 核心思路把线段切成若干小段DDA的全称是Digital Differential Analyzer数字微分分析器。名字听着唬人思路却特别简单既然直线两端点已知那我算出x方向和y方向各自的变化量然后按某个步长一步步从起点走到终点每走一步取整画一个像素。具体做法是设起点为(x0, y0)终点为(x1, y1)计算dx x1 - x0dy y1 - y0。取steps max(|dx|, |dy|)也就是两个方向中变化量更大的那个作为总步数。计算每步增量xInc dx / stepsyInc dy / steps。从起点开始循环steps次每次都让x xIncy yInc然后round(x)和round(y)就是当前要画的像素坐标。为什么要取max(|dx|, |dy|)而不是|dx|不是|dy|这是为了保证每一步在x或y方向至少前进一个像素。如果用|dx|作为步数当直线特别陡、|dy|远大于|dx|时y方向每步增量会大于1结果就是y方向跳点画出来的线会断断续续。取最大值可以保证较慢的那个方向每一步增量不超过1线条连续。2.2 代码实现和效果void drawLineDDA(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 xInc (float)dx / steps; float yInc (float)y0 ? (float)dy / steps : (float)dy / steps; // 实际取(float)dy / steps float x x0; float y y0; for (int i 0; i steps; i) { setPixel(round(x), round(y)); x xInc; y yInc; } }你看这个实现里每画一个点只做两次浮点加法非常轻量。但问题也很明显round()取整本身有开销而且靠浮点数累积走几百步后误差会慢慢变大。每次循环要维护浮点坐标最终画出来的点可能和真实直线有偏差。实际测试中画一条几十像素的短线肉眼根本看不出误差。但画一条几千像素的长线或者用它在屏幕上反复重绘动态图形累积误差和浮点取整的不稳定性就会暴露出来。所以DDA非常适合快速原型、教学演示、以及对精度要求不高的简单图形场景。但如果你做的是对性能敏感的绘制引擎或者硬件不支持浮点运算那就要上Bresenham了。3. 中点Bresenham画线把浮点干掉用误差项递推3.1 数学思想点到直线的“符号距离”中点Bresenham画线也叫Bresenham中点算法的核心思想是在每次迭代时不直接计算下一个点的精确坐标而是判断“下一个像素应该选右边的点还是右上方的点”。判断依据是把候选像素的中点代入直线方程看它在直线的哪一侧。先限定最简单的场景斜率k在 0 到 1 之间且x0 x1。这种情况下每走一步x必然加1y要么不变要么加1。假设当前点是(x, y)下一个点的两种可能是(x1, y)和(x1, y1)我们取它们的中点(x1, y0.5)。把直线方程写成隐式形式F(x, y) ax by c 0。对于线段从(x0,y0)到(x1,y1)有a y1 - y0 dyb -(x1 - x0) -dxc dx * y0 - dy * x0由代入起点得到如果F(M) 0说明中点在直线上方真实直线更接近下方的(x1, y)因此选它如果F(M) 0说明中点在直线下方或线上真实直线更接近上方的(x1, y1)因此选它。为了避免每次计算F(M)都要做浮点乘法和加法可以使用增量思想从当前点到下一点F值的变化是可以预先算好的常数或简单表达式。3.2 递推公式推导设定当前像素为(x, y)判别式为p F(x1, y0.5)。代入得p dy*(x1) - dx*(y0.5) c为了化成整数两边乘2p 2*dy*x - 2*dx*y 2*dy - dx 2*c我们只关心p的符号所以常数2*c不影响判断可以纳入初始值实际推导中初始判别式取p0 2*dy - dx然后递推如果p 0选(x1, y)那么下一点的判别式为p_next F(x2, y0.5) p 2*dy如果p 0选(x1, y1)那么下一点的判别式为p_next F(x2, y1.5) p 2*dy - 2*dx整理成代码逻辑void drawLineBresenham(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; // 这里的err相当于2dx-2dy的简化形式 while (true) { setPixel(x0, y0); if (x0 x1 y0 y1) break; int e2 2 * err; if (e2 -dy) { err - dy; x0 sx; } if (e2 dx) { err dx; y0 sy; } } }上面这个版本是所有Bresenham画线里最经典、最通用的写法。它不限定斜率不限定方向靠sx和sy控制方向一次同时判断x和y是否前进。你会发现这个版本没有用p0 2*dy - dx那套教材式写法而是用err dx - dy然后每次判断e2 -dy和e2 dx其实是同一套递推公式的等价形式。3.3 为什么推荐用通用版而不是斜率限定版教材上一般先推导0到1斜率的版本然后告诉你其他斜率用交换xy、反向遍历来处理。理论上可以但很容易出bug。比如斜率大于1时必须把y作为主位移方向x每步可能不动或加1斜率是负数时要处理反向。每换一种情况就要改一遍代码。而通用版把判断条件统一成了“x和y各自是否要加步进”用一个err同时记录两个方向的误差。本质上err的正负决定了是先走x方向还是先走y方向。实测下来这个写法不仅代码短而且几乎不需要考虑边界情况除了dx0或dy0这种退化直线其他场景都直接适用。3.4 性能分析Bresenham画线每个点只做整数加减法一次比较没有浮点没有取整没有乘法。在CPU上这比DDA快一个量级。在MCU上优势更大因为很多MCU根本没有浮点单元浮点运算要用软件模拟慢得离谱。如果你要在嵌入式设备上画线Bresenham是默认选择。4. 把思路扩展到圆和椭圆中点法全面升级4.1 圆的对称性八分圆法画圆比画线更复杂一点但对称性帮了大忙一个圆关于x轴、y轴、两条对角线都对称所以只要算出第一象限里从(0, R)到(R/√2, R/√2)这45度弧线上的点其余7个部分就能通过坐标变换全部生成。为什么只画45度而不是90度因为在这45度范围内x每步加1y每步要么不变要么减1正好是0到-1之间的斜率适合用Bresenham式判断。如果超过45度斜率绝对值超过1就要换y为主步进方向代码会更麻烦。所以统一只处理45度。4.2 中点画圆法从差商到整数递推圆的隐式方程为F(x, y) x² y² - R² 0圆心在原点。取第一象限45度弧当前点为(x, y)下一个点可能是(x1, y)和(x1, y-1)取中点(x1, y-0.5)代入Fp F(x1, y-0.5) (x1)² (y-0.5)² - R²初始点(0, R)代入得p0 1 R² - R 0.25 - R²?这里必须展开算一遍F(1, R-0.5) 1 (R-0.5)² - R² 1 R² - R 0.25 - R² 1.25 - R为了完全避免小数取p0 1 - R因为1.25 - R在整数判断时和1 - R的符号完全一样多出来的0.25不影响正负判断。这也是教材上常见的写法。接下来递推如果p 0选(x1, y)则p_next F(x2, y-0.5) p 2x 3如果p 0选(x1, y-1)则p_next F(x2, y-1.5) p 2x - 2y 5循环条件x y因为一旦x y就过了45度线。每次画点时同时画8个对称点void drawCircleMidpoint(int centerX, int centerY, int radius) { int x 0; int y radius; int p 1 - radius; while (x y) { setPixel(centerX x, centerY y); setPixel(centerX y, centerY x); setPixel(centerX - x, centerY y); setPixel(centerX - y, centerY x); setPixel(centerX x, centerY - y); setPixel(centerX y, centerY - x); setPixel(centerX - x, centerY - y); setPixel(centerX - y, centerY - x); if (p 0) { p 2 * x 3; } else { p 2 * (x - y) 5; y--; } x; } }4.3 从圆到椭圆两个区域的切换椭圆的中点法比圆麻烦一点因为椭圆没有圆的八对称性只有四对称性而且不同位置处“x方向变化快”和“y方向变化快”的分界点不同。标准椭圆方程F(x, y) b²x² a²y² - a²b² 0其中a是半长轴b是半短轴。第一象限内从(0, b)到(a, 0)这条弧线前半段x变化主导后半段y变化主导所以算法要分成两个区域区域1斜率绝对值小于1即x每步加1y可能减1也可能不变。此时判断点(x1, y-0.5)代入椭圆方程的符号。区域2斜率绝对值大于1即y每步减1x可能加1也可能不变。此时判断点(x0.5, y-1)的符号。关键在于确定切换条件。实际上可以在区域1的递推过程中检测梯度向量的变化。区域1的梯度为(∂F/∂x, ∂F/∂y) (2b²x, 2a²y)。当2b²x 2a²y时x方向的变化已经主导不过来需要切换到区域2。代码里可以在每次循环里判断2*b*b*x 2*a*a*y满足则继续区域1否则进入区域2。具体的初始判别式和递推公式如下区域1初始点(0, b)判别式p1 b² - a²*b a²/4为了整数化常用4*b² - 4*a²*b a²来避免小数。递推时如果p1 0p1 2*b²*(2*x 3)如果p1 0p1 2*b²*(2*x 3) - 4*a²*(y - 1)同时y--区域2初始判别式要在区域1结束点重新计算取(x0.5, y-1)代入椭圆方程乘4消掉小数。递推时如果p2 0p2 a²*(-4*y 3)只需要考虑y--后的增量这里需要根据推导小心处理。如果p2 0p2 4*b²*(x1) - 4*a²*(y-1) a²? 稍微有点绕我在实际代码中更推荐直接用浮点中点法见下文。实话说椭圆的中点Bresenham推导很容易在区域切换处写错而且不同资料符号不一致。如果你只是要画椭圆边框我建议不要死磕纯整数版本用下面这个简化方案更省心参数方程法x a*cos(t)y b*sin(t)从t0到t2π取足够多的采样点然后调用Bresenham画线连接相邻点。这个方法简单、通用、不容易出错而且可以轻松画旋转椭圆、扇形。参数方程法唯一的缺点是计算量大要算三角函数的浮点运算。但对现代CPU来说几十个点的三角函数等于忽略不计。只有在极其苛刻的嵌入式环境才值得去优化成纯整数版本。4.4 对比表格三种曲线算法的取舍算法运算类型每步主要操作适用场景缺点DDA画线浮点加法和取整2次浮点加法 round快速原型、教学、对精度不敏感浮点累积误差、依赖浮点单元中点Bresenham画线整数加减比较2次整数加减 2次比较嵌入式、性能敏感、长线段推导稍绕但实现短中点画圆整数加减比较2次整数加减 8个像素写入圆锐利、无锯齿、性能佳只针对标准圆中点画椭圆整数加减比较区域切换判断复杂标准椭圆区域切换容易错参数方程画椭圆浮点三角函数每次计算sin/cos任意椭圆、旋转椭圆、快速实现CPU占用略高但现代设备无所谓5. 实操环节把这几个算法用到真实渲染里5.1 从单条线到连续多边形光会画一条线不够实际项目里要画的是一个矩形框、三角形、多边形甚至一个带边框的仪表盘。我的做法是写一个统一的基础层先实现setPixel(x, y, color)底层就是往帧缓冲区framebuffer[y * width x]写值。再实现drawLine、drawCircle、drawEllipse全部基于setPixel。最后组合成drawRect、drawTriangle、drawPolygon这类高阶接口。这样一层层往上叠代码复用率高而且所有算法可以随时替换底层实现而不影响上层逻辑。5.2 实操在480x320的嵌入式屏幕上画动态仪表盘我之前在一个小屏幕上做简易仪表盘需要一个转速指针本质上就是从圆心出发按角度画一条动态直线。因为角度随时在变指针每一帧都要重新画一遍如果用浮点反三角函数计算终点再调用直线算法整个流程的瓶颈在于三角函数和浮点运算而不是直线算法本身。这时候Bresenham直线部分非常快瓶颈主要在角度转换。我的优化思路是预计算一张角度到(cos, sin)的查找表表大小按1度或0.5度分度指针更新时直接查表避免实时调用三角函数。这算是Bresenham之外的另一层经典优化——空间换时间。5.3 实操圆角矩形的实现画圆角矩形时圆角部分就是四段90度圆弧。如果直接用中点画圆算法就必须对圆心坐标做偏移并限制画弧角度。比较麻烦。我的方案是先画四条直线边框然后在四个角调用drawCircle的“部分对称”逻辑或者直接用参数方程采样90度弧线上的点用drawLine连起来。对于嵌入式UI来说参数方程法的性能完全够用。做UI控件时还有一个细节填充。填充比描边复杂简单方案是扫描线填充也就是对每一行y计算该行与图形的交点然后按交点区间上色。对于圆、椭圆可以通过反解方程求交点不需要逐像素判断。6. 常见问题与调试技巧我踩过的坑6.1 直线端点不闭合用Bresenham通用版画线时如果循环条件写错比如while (x0 ! x1 || y0 ! y1)写在setPixel之后会导致最后一个像素漏画。我在第一次写的时候就把终点画丢了排查了半天。正确的做法是先把起点画上然后循环里先判断是否到达终点再决定是否break。标准写法就是我前面代码里的先setPixel然后判断if (x0 x1 y0 y1) break;。6.2 圆的八对称坐标写错画圆时的八个对称点很容易因为符号写错导致漏画或重画。我建议不要一次性写出全部8个而是先写四个轴对称点(±x, ±y)再写四个对角对称点(±y, ±x)。而且x和y千万不要搞混我见过很多新手在(centerX y, centerY x)和(centerX x, centerY y)这两行上翻车。6.3 判断式p的正负符号搞反中点法里p的正负和选点方向的对应关系依赖F的定义。如果直线方程写成F(x,y) dy*x - dx*y c符号和推导就不一样。我自己调试时发现与其死记硬背不如把初始点代入验证一遍。比如画圆到(0, R)附近p0 1 - R明显是负数R大于1时此时下一个点应该选下面的点不对应该是y保持不变x加1。你看p为负数时不在直线上方要对得上。每次写完代码先自己拿一个小半径比如半径5在紙上演算一遍比肉眼debug快得多。6.4 浮点DDA的圆不圆问题有些同学偷懒用DDA思路画圆把角度从0到2π分成steps份每步计算x centerX r*cos(angle)和y centerY r*sin(angle)然后取整画点。当steps太少时像素点之间会拉出空隙steps太多时坐标取整后大量重复点。最好的做法是采样点数参考圆的周长比如steps 2 * π * r但用整数画圆算法就没这个烦恼。6.5 填充和描边混淆如果只是描边中点法很完美。但如果你想要实心圆千万别用逐行判断距离的方式比如if (x*x y*y r*r)去扫描整个外接矩形那虽然也能实现但每个像素要做乘法慢。更好的方案是用中点圆算法生成每一行的左右边界然后画横线填充。这样就把圆的填充复杂度从O(r²)降到了O(r)。7. 一点经验之谈这几个算法看起来属于“古董级”知识但它们的核心思想在今天的图形学里依然无处不在增量计算、避免浮点、利用对称性、空间换时间。最早我是在一个芯片自带的2D加速模块上写驱动硬件只支持画点、画直线和填充矩形圆和椭圆全要软件绕过去。当时我在MCU上调中点画圆算法为几个像素的偏差折腾了一下午。后来想明白了不是算法问题而是像素栅格的坐标系和数学坐标系差了半个像素。屏幕上的像素中心在(x0.5, y0.5)而栅格坐标(x, y)只是索引。当你以(x, y)为圆心画圆时视觉圆心其实偏移了半个像素半径1的圆看起来就会忽大忽小。这个问题在低分辨率屏幕上尤其明显。如果你要做高质量的2D渲染建议在算法之上再做一层抗锯齿比如FXAA或简单的SSAA但如果你只是画GUI边框、画示意图形Bresenham系算法会让你的程序轻快到飞起。我个人的习惯是教学和验证用DDA生产代码用Bresenham画椭圆用参数方程采样Bresenham连线画圆用中点法。这套组合我用了很久几乎没有再为“画线画圆”这种基础功能操过心。你完全可以把这些代码封装成一个独立的图形基础库在项目里一次性写好后面所有绘制需求都调它值得做。
