Marlin 固件中的 Bresenham 步进算法从整数画线原理到过采样实现【免费下载链接】MarlinMarlin is a firmware for RepRap 3D printers optimized for both 8 and 32 bit microcontrollers. Marlin supports all common platforms. Many commercial 3D printers come with Marlin installed. Check with your vendor if you need source code for your specific machine.项目地址: https://gitcode.com/GitHub_Trending/ma/Marlin导读Bresenham 算法是 Marlin 步进电机控制的核心它把一条数学直线例如 X 轴 1000 步、Y 轴 413 步的目标运动映射为每个步进定时周期内各轴走一步 / 不走的离散决策且全程只用整数运算没有任何浮点开销。本文以 docs/Bresenham.md 为主干从经典 Bresenham 画线原理出发逐步推导出 Marlin 实际使用的整数判据与误差更新式再延伸讲解 Marlin 的过采样Oversampling扩展如何提升低速多轴运动的时序分辨率并对照 Marlin/src/module/stepper.cpp、Marlin/src/module/stepper.h 与 Marlin/src/libs/bresenham.h 中的真实实现说明这套理论是如何在步进中断里落地执行的。读完本文你将掌握Bresenham 算法如何用纯整数实现步进脉冲分配Marlin 的delta_error/advance_dividend/advance_divisor三个变量分别对应算法中的哪个量过采样因子如何提升多轴低速运动的时间分辨率以及 Marlin 在经典算法之上加入了哪些工程化变体输入整形、线性提前等。一、经典 Bresenham 算法整数化的直线栅格化1.1 问题设定第一正八分区的二选一决策考虑在栅格上画一条线段并限制其斜率满足0 m 1。如果绘图程序每步都使x递增 1那么画出点(x,y)之后下一个点的选择只有两种绘制(x1, y)绘制(x1, y1)。因此在第一正八分区first positive octant内画线问题被归结为每一步在两个候选点之间二选一。下图展示了绘制(x,y)后程序面临的局面y1 --------------* | / | / | / | / | yem*--------- | /| ^ | | / | |m | | / | | | | / | v | | ye*----|----- |mε | /| | ^ | | / | | |ε | | / | | | | |/ | | | v y *-------------------- x x1该示意图摘自 docs/Bresenham.md原作者为赫尔辛基大学的线算法讲义。1.2 误差 ε 的引入绘制(x,y)时程序实际上在理想直线与步进电机分辨率之间做折中通常栅格上无法精确定位数学意义上的直线点因此每个y纵坐标都伴随一个误差 ε——真实数学y值应为y ε且-0.5 ε 0.5。当x前进到x1时真实y值增加一个斜率m。我们选择绘制(x1, y)的条件是y ε m y 0.5否则绘制(x1, y1)。这样即可保证数学线段与实际绘制之间的总误差最小。新点产生的误差可回写进 ε用于下一轮x2决策。误差更新有两种可能若选择(x1, y)ε[new] (y ε m) - y否则ε[new] (y ε m) - (y 1)由此得到一个避免取整运算的 DDA数字微分分析算法用误差变量 ε 控制绘制ε 0, y y[1] for x x1 to x2 do Plot point at (x,y) if (ε m 0.5) ε ε m else y y 1, ε ε m - 1 endif endfor1.3 整数化把浮点斜率消掉上述流程仍使用浮点。现在把判据两边同时乘以Δx再乘以 2ε m 0.5 ε Δy/Δx 0.5 2.ε.Δx 2.Δy Δx不等式中的所有量现在都是整数。令ε ε·Δx判据变为2.(ε Δy) Δx误差更新规则同样可以改写为ε形式。浮点更新式ε ε m ε ε m - 1两边同乘Δxε.Δx ε.Δx Δy ε.Δx ε.Δx Δy - Δx即ε ε Δy ε ε Δy - Δx于是得到 Bresenham 的纯整数画线算法ε 0, y y[1] for x x1 to x2 do Plot point at (x,y) if (2.(ε Δy) Δx) ε ε Δy else y y 1, ε ε Δy - Δx endif endfor关键结论原文原话值得强调这是纯整数算法因此高效快乘以 2 可以用左移位实现前提约束0 m 1。二、为什么需要过采样时序分辨率问题2.1 Bresenham 不丢步但存在时间分辨率瓶颈Bresenham 算法不会丢步也不会累积误差。但存在一个概念性问题——时间分辨率time resolution设主轴major axis即需要产生最多步进脉冲的轴含挤出机与次轴的步数之比不是整数那么 Bresenham 在主轴运动的某些点上必须决定是否让次轴动一步。这个决策被安排在整段主轴运动之中使得主轴走完全程时次轴也恰好走完自己的全部步数并且次轴的步进被均匀分布在主轴运动全程上——从步数比例的角度看是完美均衡的。2.2 离散决策点的问题但正如文档指出的Bresenham 的决策点是离散的它只能在主轴恰好动一步的那个瞬间决定次轴动或不动而这个瞬间通常不是时间轴上的理想位置。当运动很慢、且各轴步数相近但不相等时问题会恶化决策点分布非常稀疏决策点之间存在很大的时间间隔次轴的运动在时间上变得一簇一簇的而不是平滑均匀的。这在 3D 打印场景中会表现为低速、多轴联动例如直线打印中 X 与 E 联动挤出时挤出脉冲与运动脉冲在时间上不均匀影响挤出质量和表面光洁度。2.3 过采样的思路解决方案是过采样不让 Bresenham 只按X 轴整数步进做决策而是按 X 轴的分数增量做决策。设r为把 X 轴一个整数增量再细分的份数m Δy/Δx increment of y due to the increment of x1每当 X 轴前进1/rY 轴理论上应前进m·1/r。同样受分辨率限制有两种选择绘制(x(1/r), y)绘制(x(1/r), y1)。决策时保持误差最小-0.5 ε 0.5。令m/r为x前进1/r时y的增量决策条件为y ε m/r y 0.5 ε m/r 0.5 [1]决策后的误差更新决策 A次轴不动ε[new] ε m/r [2]决策 B次轴动一步ε[new] ε m/r - 1 [3]2.4 过采样的整数化推导把m ΔY/(ΔX·r)代入决策不等式 [1]ε ΔY/(ΔX*r) 0.5两边乘以2.Δx.r2.ΔX.ε.r 2.ΔY ΔX.r定义ε 2.ε.ΔX.r则判据变为ε 2.ΔY ΔX.r [4]误差更新规则两边乘以2.r.ΔX。对决策 Aε[new] ε 2.ΔY [6]对决策 Bε[new] ε 2.ΔY - 2.ΔX.r [7]汇总对应 docs/Bresenham.md 的结论框条件方程 ε 2.ΔY ΔX.r [4] 误差更新方程 ε[new] ε 2.ΔY [6] ε[new] ε 2.ΔY - 2.ΔX.r [7]与经典算法一样决策不等式 [4] 与更新方程 [6][7] 全部是整数值运算完全不需要浮点算术。三、过采样 Bresenham 的参考实现文档 docs/Bresenham.md 给出了可直接使用的 C 参考实现。注意其中的命名约定divisor即主轴步数stepsXdividend即次轴步数stepsYadvanceDivisor/advanceDividend是预计算好的 2 倍缩放量errorAccumulator是误差累加器初始化为-divisor * rate与 Marlin 中delta_error 初始化为负的步事件总数的做法一脉相承。class OversampledBresenham { private: long divisor, // stepsX dividend, // stepsY advanceDivisor, // advanceX advanceDividend; // advanceY int errorAccumulator; // Error accumulator public: unsigned int ticker; OversampledBresenham(const long inDividend, const long inDivisor, int rate) { ticker 0; divisor inDivisor; dividend inDividend; advanceDivisor divisor * 2 * rate; advanceDividend dividend * 2; errorAccumulator -divisor * rate; } bool tick() { errorAccumulator advanceDividend; const bool over errorAccumulator 0; if (over) { ticker; errorAccumulator - advanceDivisor; } return over; } };对照推导结果逐行核对advanceDividend dividend * 2对应更新式 [6] 中的 2.ΔYadvanceDivisor divisor * 2 * rate对应更新式 [7] 中的- 2.ΔX.rerrorAccumulator 0对应决策式 [4] 的ε 2.ΔY ΔX.r把不等式移项后ε的初值取-ΔX.r即-divisor * rate从而用一次符号判断替代一次比较。tick()每次返回true表示次轴需要走一步。这个类的使用方式就是按过采样后的细粒度时钟节拍驱动主轴同时用tick()决定次轴。四、Marlin 中的 Bresenham 落地实现4.1 通用模板Bresenham类Marlin 在 Marlin/src/libs/bresenham.h 中实现了一个模板化的通用版本用于一组值/计数器一起 tick的场景。核心成员static T divisor, value[Cfg::SIZE], dir[Cfg::SIZE], dividend[Cfg::SIZE], counter[Cfg::SIZE];divisor主轴步数对应算法中的Δxdividend各次轴步数对应Δycounter误差计数器对应ε但 Marlin 把它初始化为负值dir方向±1value累加位置值。关键成员函数// 将计数器初始化为 -(divisor/2)即把误差预置到“半格”处实现四舍五入式决策 FORCE_INLINE static void prime(const uint8_t index) { counter[index] -(divisor / 2); } // 每 tick 一次先加 dividend再判断是否越界 FORCE_INLINE static bool tick1(const uint8_t index) { counter[index] dividend[index]; return counter[index] 0; } // tick 的完整版若越界则 value 前进一个方向并回退 divisor FORCE_INLINE static void tick(const uint8_t index) { if (tick1(index)) { value[index] dir[index]; back(index); } }注意两个工程细节初值-(divisor / 2)对应文档中误差范围-0.5 ε 0.5、选择更近栅格点的取整语义。将计数器预置在半格负方向等价于把经典算法ε Δy Δx的决策变成counter 0的符号判断省去一次比较。back()回退越过阈值后把计数器减去divisor实现更新式 [7] 的ε ε Δy - Δx中的-Δx部分。该模板还提供init/reinit的重载同 divisor、同方向、数组形式的批量初始化、report()调试输出通过SERIAL_ECHOPGM打印dividend/divisor与计数器/值以及static_assert要求T必须是有符号类型static_assert(signtest 0, Bresenham type must be signed!)因为算法依赖符号判断。所有热点函数都标注了FORCE_INLINE与__O3优化属性以满足步进中断对执行时间的苛刻要求。4.2 步进器Stepper中的 Bresenham 应用真正驱动电机的 Bresenham 逻辑位于 Marlin/src/module/stepper.cpp。文件头部注释明确写道Marlin uses the Bresenham algorithm. For a detailed explanation of theory and method see ...第 26-27 行并在 Marlin/src/module/stepper.h 中声明了对应变量delta_errorBresenham 误差累加器即理论中的ε按轴存储见 stepper.h 第 487 行附近的注释 Delta error variables for the Bresenham line traceradvance_dividend按轴保存的2 × steps对应更新式 [6] 的 2.ΔYadvance_divisor2 × step_event_count对应- 2.ΔX。块block执行前的初始化stepper.cpp// Initialize Bresenham delta errors to 1/2 delta_error -int32_t(step_event_count); TERN_(HAS_ROUGH_LIN_ADVANCE, la_delta_error delta_error); // Calculate Bresenham dividends and divisors advance_dividend (current_block-steps 1).asInt32(); advance_divisor step_event_count 1;注意这里的移位技巧steps 1与step_event_count 1直接实现乘以 2与文档强调的乘法可以用左移实现完全对应delta_error初始化为-step_event_count配合PULSE_PREP中的符号判断实现无浮点、无乘除的每周期决策。ISR 中每个定时周期的脉冲判定stepper.cpp// Determine if a pulse is needed using Bresenham #define PULSE_PREP(AXIS) do{ \ int32_t de delta_error[_AXIS(AXIS)] advance_dividend[_AXIS(AXIS)]; \ if (de 0) { \ step_needed.set(_AXIS(AXIS)); \ de - advance_divisor_cached; \ } \ delta_error[_AXIS(AXIS)] de; \ }while(0)这段宏正是算法核心的逐字落地de delta_error advance_dividend⇔ε ε 2.ΔY更新式 [6] 的加步if (de 0)⇔ 文档参考实现中的over errorAccumulator 0de - advance_divisor_cached⇔ε ε - 2.ΔX更新式 [7] 的回退部分返回step_needed给后续PULSE_START/PULSE_STOP宏用于真正拉高/拉低 STEP 引脚stepper.cpp。主轴事件计数step_event_count是块内主轴步数最多的轴的步事件总数delta_error按每个轴独立累加从而让各次轴在主轴全程上均匀分布步进——这正是文档第 2 节描述的次轴步进均匀分布在主轴运动全程的直接体现。4.3 过采样在 Marlin 中的实际应用过采样并非纸上谈兵。在 Marlin/src/module/stepper.h 中有static uint8_t oversampling_factor; // Oversampling factor (log2(multiplier)) to increase temporal resolution of axis // ... static constexpr uint8_t oversampling_factor 0; // Without smoothing apply no shift实际定义随编译配置选择其一启用相关特性时oversampling_factor为可调变量否则恒为 0。对应地stepper.cpp 在块初始化时按过采样因子缩放时间基准// Based on the oversampling factor, do the calculations step_event_count current_block-step_event_count oversampling_factor; oversampling_factor即乘以2^factor——把主轴事件计数放大r 2^factor倍从而把 Bresenham 的决策点时间分辨率提高r倍。加速度/减速度的转折点同样缩放accelerate_before/decelerate_start也 oversampling_factor见 stepper.cpp保证梯形速度曲线的时间轴与过采样后的步进时间轴一致。这与文档中以分数增量1/r驱动主轴、以r细分决策点的过采样定义严格对应。低速多轴联动如直线打印时 X 与 E 联动挤出正是文档所述决策点稀疏、时间间隔大的典型场景过采样在此场景下能显著改善挤出脉冲在时间上的均匀性。4.4 线性提前Linear Advance的 Bresenham 变体Marlin 的粗略线性提前rough linear advance让挤出机步进搭便车在 Bresenham 时序上。块执行前把la_delta_error delta_error同步初始化见 4.2 节代码并在 ISR 中用独立的la_dividend对应 E 轴步数对挤出步进计数#if HAS_ROUGH_LIN_ADVANCE if (la_active step_needed.e) { // Dont actually step here, but do subtract movements steps // from the linear advance step count step_needed.e false; la_advance_steps--; } #endifstepper.cpp。即当主 Bresenham 决定 E 轴该走一步时若线性提前处于激活状态则先不真正发脉冲而是从线性提前的步数余额中扣除E 轴的最终脉冲由 LA ISR 在稍后的时刻按更精确的挤出时机补发详见 stepper.cpp 的注释 Apply Bresenham algorithm so that linear advance can piggy back on。SMOOTH_LIN_ADVANCE模式下则完全接管 E 轴步进step_needed.e false。这展示了 Bresenham 架构的开放性主决策流保持不变算法产生的步进机会可以按需被其他子系统截取、延迟或重新调度。4.5 输入整形Input Shaping的二级 Bresenham另一个值得一提的应用是输入整形ZV / ZVD shaping。它利用 Bresenham 的误差累加机制实现了次级 Bresenham主 Bresenham 决定某轴需要一步后PULSE_PREP_SHAPING宏用独立的shaping_x/y/z.delta_errorint16_t模 128 的计数器见 stepper.h与factor1/factor2再算一次判断该步是正向主脉冲还是反向回波echo#define PULSE_PREP_SHAPING(AXIS, DELTA_ERROR, DIVIDEND) do{ \ int16_t de DELTA_ERROR (DIVIDEND); \ const bool step_fwd de (64 HYSTERESIS(AXIS)), \ step_bak de -(64 HYSTERESIS(AXIS)); \ if (step_fwd || step_bak) { \ de step_fwd ? -128 : 128; \ ... } \ else \ step_needed.clear(_AXIS(AXIS)); \ DELTA_ERROR de; \ }while(0)stepper.cpp。其判据de 64/de -64、回退±128的结构与经典 Bresenham 的累加-越界-回退完全同构只是把比例缩放到模 128 的框架内。这印证了文档结尾的论断Bresenham 的结构足够通用可以经微小改造就支撑出全新的高级特性。五、总结从数学到固件的完整链路把本文的推导与实现串起来可以看到一条清晰链路数学基础栅格画线中每步二选一用误差 ε 最小化与理想直线的偏差docs/Bresenham.md 前四节整数化把ε m 0.5乘以2Δx消去浮点得到ε ε 2Δy、ε ε 2Δy - 2Δx的纯整数更新式乘 2 用左移实现过采样扩展把主轴细分r份判据变为ε 2Δy Δx·r用r倍的时间分辨率解决低速多轴联动时决策点稀疏的问题参考实现即文档末尾的OversampledBresenham类Marlin 落地Bresenham模板Marlin/src/libs/bresenham.h提供通用计数器步进器Marlin/src/module/stepper.cpp中delta_error、advance_dividend、advance_divisor三变量 PULSE_PREP宏完成逐周期决策oversampling_factor通过移位实现时间基准细分线性提前与输入整形则在主算法之上以截取步进机会 / 二级 Bresenham的方式扩展功能。给开发者的三个关键提醒想深入理解步进时序先读 stepper.cpp 的PULSE_PREP、PULSE_START、PULSE_STOP三组宏它们是 Bresenham 决策到真实脉冲的最后一公里调试步进分布问题时可利用Bresenham::report()bresenham.h打印各轴的dividend/divisor与计数器状态若自行修改运动控制逻辑务必保持delta_error的符号判断语义 0越界与初始化为负半程的预置方式否则会破坏四舍五入取整特性并引入系统性误差。【免费下载链接】MarlinMarlin is a firmware for RepRap 3D printers optimized for both 8 and 32 bit microcontrollers. Marlin supports all common platforms. Many commercial 3D printers come with Marlin installed. Check with your vendor if you need source code for your specific machine.项目地址: https://gitcode.com/GitHub_Trending/ma/Marlin创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
