简介这份文档面向计算机图形学初学者与图形编程入门者聚焦Bresenham算法在光栅化绘图中的完整实现帮助读者理解如何用整数运算高效生成直线、圆与椭圆的像素表示。内容涵盖DDA数字微分分析器、中点Bresenham画线、改进Bresenham算法、八分法绘制圆以及四分法绘制椭圆并给出OpenGL环境下putpixel、glBegin、glColor3f等函数的配合用法代码中保留了各算法的判别式推导与坐标输出便于对照调试。资源包共1个doc文件约31KB以文档形式集中呈现算法原理与可运行示例代码适合作为课程实验或自学参考。目前已有202人学习读者可借此掌握从浮点增量到整数判别的优化思路理解不同斜率与象限下的分支处理并迁移到嵌入式或低级图形编程场景中。1. 从整数像素到连续图形Bresenham 算法到底在算什么屏幕上的直线从来不是数学意义上的直线。你调用line(0, 0, 13, 5)显卡最终点亮的是一串离散像素中间必然有取舍第 3 列该落在第 2 行还是第 3 行浮点 DDA 算法用y k累加再四舍五入能画对但每步一次浮点加法加一次取整在早期硬件上代价高且误差会随步数累积。Bresenham 的价值在于它把“下一个像素选哪个”化归为一个只做整数加减和比较的递推式全程不碰浮点也不做乘除。这套思路最早用于绘图仪和光栅显示器今天依然活在 GPU 光栅化、嵌入式 LCD 驱动、激光打标路径规划里。标题里同时出现直线、圆和椭圆是因为三者共享同一套骨架先写出理想曲线的隐式方程再考察“当前像素”与“理想曲线”的偏差用误差项的符号决定走哪一步。直线是误差项最简单的一维情形圆靠八对称把计算量压到八分之一椭圆则要处理两个区域和更复杂的增量更新。适合谁读写过 C/C 或 Python 图形代码、想搞懂光栅化底层、或者需要在无浮点单元的单片机上画图的人。2. Bresenham 画直线的整数递推与代码落地2.1 从浮点 DDA 到整数误差项设直线起点(x0, y0)、终点(x1, y1)先约定0 dy dx即斜率在 0 到 1 之间x 每步加 1y 要么不动要么加 1。理想直线方程写成F(x, y) dy·x - dx·y C 0。对当前像素(x, y)下一个候选是(x1, y)和(x1, y1)把两点代入F谁离 0 近就选谁。关键一步不去算两个F值再比较而是维护一个决策变量d 2·dy·(x1) - 2·dx·y (2·dy - dx)这类形式不同教材常数项写法不同本质等价。当d 0选正右方像素d 0选右上方像素然后按规则更新d选右方d 2·dy选右上方d 2·(dy - dx)初始d 2·dy - dx。全程只有整数加法2·dy和2·(dy - dx)可以预先算好存成常量。2.2 可复现的 Python 实现def bresenham_line(x0, y0, x1, y1): 返回从 (x0,y0) 到 (x1,y1) 的像素坐标列表支持任意方向 points [] dx abs(x1 - x0) dy abs(y1 - y0) sx 1 if x0 x1 else -1 # x 方向步进 sy 1 if y0 y1 else -1 # y 方向步进 err dx - dy # 初始误差项等价于 2*dy-dx 的变形 x, y x0, y0 while True: points.append((x, y)) if x x1 and y y1: break e2 2 * err if e2 -dy: # 误差偏向 x走 x err - dy x sx if e2 dx: # 误差偏向 y走 y err dx y sy return points这段是“全象限通用版”用err dx - dy和e2 2*err把上面d的两种更新合并成两个独立判断好处是不用先交换端点、不用分八种情况写八段代码。逻辑说明e2 -dy表示当前误差允许 x 前进e2 dx表示允许 y 前进两个判断可能同时成立于是走出对角线步这正是斜率接近 1 时该有的行为。参数说明sx、sy只取 ±1负责把第一象限的推导镜像到其余象限err的初值dx - dy决定了第一步的倾向若dx dy斜率小于 1则err 0第一步优先走 x。2.3 参数怎么调、边界怎么处理参数/场景取值说明dx 0垂直线通用版能处理e2 dx恒成立y 每步都走dy 0水平线e2 -dy恒成立x 每步都走端点相同单像素循环第一次就 break返回一个点斜率 1无需特判通用版自动让 y 走得更频繁常见坑很多教材版要求先保证dx dy并交换 x、y忘了交换就会画出错误结果用float存err虽然结果对但丢掉了整数算法的意义在 MCU 上应坚持int。若要做抗锯齿Bresenham 本身不提供灰度需要改用 Wu 算法或对相邻像素按误差加权。3. 圆与椭圆的 Bresenham对称性、两区域与增量更新3.1 圆的八对称与决策变量圆心(xc, yc)、半径r只推导第一象限从(0, r)到(r/√2, r/√2)的八分之一弧其余七个对称点靠(±x, ±y)和(±y, ±x)直接镜像。理想圆方程F(x, y) x² y² - r²。从(x, y)出发候选是(x1, y)和(x1, y-1)决策变量取中点形式d F(x1, y-0.5) (x1)² (y-0.5)² - r²为避免小数两边乘 4 或改用d 4·((x1)² (y-0.5)² - r²)的整数版本。更新规则d 0选(x1, y)d 4·x 6d 0选(x1, y-1)d 4·(x - y) 10初始d 3 - 2r这是乘 4 化简后的常见形式。终止条件是x y因为过了 45° 线就进入下一段对称区。3.2 椭圆的两区域划分椭圆(x/a)² (y/b)² 1a为长半轴。它不像圆那样一个决策变量走到底因为曲率在变化靠近 y 轴顶部时 y 方向变化快靠近 x 轴右侧时 x 方向变化快。分界点是切线斜率为 -1 处即2·b²·x 2·a²·y也就是b²·x a²·y。区域一b²·x a²·yx 每步加 1y 可能减 1。决策变量基于F(x1, y-0.5)更新量含2·b²·x这类项。 区域二b²·x a²·yy 每步减 1x 可能加 1。决策变量基于F(x0.5, y-1)。def bresenham_ellipse(a, b, xc0, yc0): 第一象限椭圆弧a 为 x 半轴b 为 y 半轴 pts [] x, y 0, b a2, b2 a * a, b * b # 区域一 d1 b2 - a2 * b 0.25 * a2 # 乘 4 可转整数这里保留浮点便于阅读 dx 2 * b2 * x dy 2 * a2 * y while dx dy: pts.append((x, y)) if d1 0: x 1 dx 2 * b2 d1 dx b2 else: x 1 y - 1 dx 2 * b2 dy - 2 * a2 d1 dx - dy b2 # 区域二 d2 b2 * (x 0.5) ** 2 a2 * (y - 1) ** 2 - a2 * b2 while y 0: pts.append((x, y)) if d2 0: y - 1 dy - 2 * a2 d2 a2 - dy else: y - 1 x 1 dx 2 * b2 dy - 2 * a2 d2 dx - dy a2 return pts逻辑说明区域一用dx dy作为切换条件dx、dy分别是F对 x、y 的偏导相关量正好对应切线斜率。区域二的d2用(x0.5, y-1)的中点形式。参数说明a、b必须为正整数若a b退化成圆两区域代码仍能跑但直接用圆的版本更快。实际工程里常把0.25*a2这类项整体乘 4 转成整数避免浮点代价是变量范围变大32 位下a到几千仍安全。3.3 对称填充与性能取舍画整圆或整椭圆时对第一象限每个(x, y)生成八个或四个对称点用putpixel写入。若要做实心填充不要对每个 y 再跑一遍直线算法直接按扫描线在xc ± x之间水平填充复杂度从 O(n²) 降到 O(n)。性能上Bresenham 每像素约 2 到 4 次整数加法比sin/cos查表法省内存比逐点浮点开方快一个数量级。嵌入式场景里把2*b2、2*a2提成寄存器变量能再省一次内存访问。4. 排错、验证与嵌入式落地技巧4.1 用像素覆盖率验证正确性判断实现对不对别靠肉眼看“像不像”。写个校验对直线检查相邻输出点的|Δx| 1且|Δy| 1且所有点满足|dy·x - dx·y C|不超过max(dx, dy)/2。对圆检查每个点到圆心距离与r的偏差不超过 0.5 像素。下面这段可直接跑def check_circle(pts, r, tol0.5): bad [(x, y) for x, y in pts if abs((x*x y*y) ** 0.5 - r) tol] return len(bad) 0, bad若返回False先看d的初值符号是否写反再看更新量里4*x6有没有漏乘。椭圆最常见的错是区域切换条件写成dx dy导致弧线在 45° 附近出现折角。4.2 定点化与溢出边界MCU 上没有 FPU 时把椭圆代码里的0.25*a2改成整体乘 4D1 4*b2 - 4*a2*b a2更新量同步乘 4。此时D1最大量级约4*a2*ba b 1000时约 4×10⁹超过 32 位有符号上限需要int64或把a、b限制在 500 以内。这是实际项目里最容易翻车的地方PC 上跑得好好的烧进板子画大椭圆就花屏八成是溢出。提示先用小半径r5、a8,b5打印 ASCII 点阵确认形状再放大参数测溢出比直接上屏调试快得多。4.3 与现有图形库的衔接若项目已用 framebuffer 或 LCD 驱动Bresenham 输出的是坐标序列写入前要处理裁剪对直线用 Cohen-Sutherland 先裁到视口再跑 Bresenham避免画到屏幕外触发越界写。对圆和椭圆先判断包围盒是否与视口相交不相交直接跳过。批量绘制时把putpixel换成写显存指针加偏移比函数调用快数倍。最后若需要亚像素精度或抗锯齿Bresenham 的整数骨架仍可复用只需在误差项上做加权混合这也是很多矢量渲染器保留它的原因。本文还有配套的精品资源点击获取