3. 直线插补的Bresenham算法实现

任务目标

在RTOS运动控制场景中，实现基于Bresenham算法的直线插补器，输出各轴步进脉冲序列；与DDA算法对比，验证其整数运算带来的效率优势及精度特性。

核心实现

// bresenham_line.h
#ifndef BRESENHAM_LINE_H
#define BRESENHAM_LINE_H

#include <stdint.h>

typedef struct {
    int32_t x0, y0;      // 起点
    int32_t x1, y1;      // 终点
    int32_t steps;       // 总步数
    uint8_t x_dir;       // X方向：1正，0负
    uint8_t y_dir;       // Y方向：1正，0负
    int32_t err;         // 误差项
    int32_t dx, dy;      // 增量值
    int32_t x, y;        // 当前点
    uint8_t is_steep;    // 是否|dy|>|dx|
} bresenham_t;

// 初始化插补器
void bresenham_init(bresenham_t *b, int32_t x0, int32_t y0, int32_t x1, int32_t y1);

// 计算下一步应运动的轴，返回位掩码：bit0=X，bit1=Y
uint8_t bresenham_step(bresenham_t *b);

#endif

// bresenham_line.c
#include "bresenham_line.h"

void bresenham_init(bresenham_t *b, int32_t x0, int32_t y0, int32_t x1, int32_t y1) {
    b->x0 = x0; b->y0 = y0;
    b->x1 = x1; b->y1 = y1;
    b->x = x0; b->y = y0;
    b->dx = (x1 > x0) ? (x1 - x0) : (x0 - x1);
    b->dy = (y1 > y0) ? (y1 - y0) : (y0 - y1);
    b->x_dir = (x1 >= x0) ? 1 : 0;
    b->y_dir = (y1 >= y0) ? 1 : 0;
    b->is_steep = (b->dy > b->dx) ? 1 : 0;

    if (b->is_steep) {
        int32_t tmp = b->dx; b->dx = b->dy; b->dy = tmp;
    }
    b->err = 2 * b->dy - b->dx;
    b->steps = b->dx;  // 总步数 = 长轴长度
}

uint8_t bresenham_step(bresenham_t *b) {
    uint8_t mask = 0;
    if (b->steps <= 0) return 0;  // 插补完成

    if (b->is_steep) {
        // 长轴为Y
        if (b->y_dir) b->y++; else b->y--;
        mask |= 0x02;
        if (b->err >= 0) {
            if (b->x_dir) b->x++; else b->x--;
            mask |= 0x01;
            b->err -= 2 * b->dx;
        }
    } else {
        // 长轴为X
        if (b->x_dir) b->x++; else b->x--;
        mask |= 0x01;
        if (b->err >= 0) {
            if (b->y_dir) b->y++; else b->y--;
            mask |= 0x02;
            b->err -= 2 * b->dx;
        }
    }
    b->err += 2 * b->dy;
    b->steps--;
    return mask;
}

// 测试与对比（PC端验证用）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bresenham_line.h"

// DDA参考实现（浮点）
void dda_line(int32_t x0, int32_t y0, int32_t x1, int32_t y1, int32_t *out_x, int32_t *out_y, int *n) {
    int32_t dx = x1 - x0, dy = y1 - y0;
    int32_t steps = (abs(dx) > abs(dy)) ? abs(dx) : abs(dy);
    float x_inc = (float)dx / steps;
    float y_inc = (float)dy / steps;
    float x = x0, y = y0;
    *n = steps + 1;
    for (int i = 0; i <= steps; i++) {
        out_x[i] = (int32_t)(x + 0.5f);
        out_y[i] = (int32_t)(y + 0.5f);
        x += x_inc; y += y_inc;
    }
}

int main() {
    // 测试用例：从(0,0)到(17,5)
    int32_t x0=0, y0=0, x1=17, y1=5;
    bresenham_t b;
    bresenham_init(&b, x0, y0, x1, y1);

    printf("Bresenham路径:\n");
    int bx[100], by[100], bn = 0;
    bx[bn]=b.x; by[bn]=b.y; bn++;
    uint8_t m;
    while ((m = bresenham_step(&b)) != 0) {
        bx[bn]=b.x; by[bn]=b.y; bn++;
    }
    for (int i=0; i<bn; i++) printf("(%d,%d) ", bx[i], by[i]);
    printf("\n总点数: %d\n", bn);

    // DDA对比
    int dx_[100], dy_[100], dn;
    dda_line(x0, y0, x1, y1, dx_, dy_, &dn);
    printf("DDA路径:\n");
    for (int i=0; i<dn; i++) printf("(%d,%d) ", dx_[i], dy_[i]);
    printf("\n总点数: %d\n", dn);

    // 效率对比：执行100万次插补
    clock_t t1 = clock();
    for (int i=0; i<1000000; i++) {
        bresenham_init(&b, 0,0, 100, 37);
        while (bresenham_step(&b) != 0);
    }
    clock_t t2 = clock();
    printf("Bresenham 100万次耗时: %ld ms\n", (t2-t1)*1000/CLOCKS_PER_SEC);

    t1 = clock();
    for (int i=0; i<1000000; i++) {
        int ox[200], oy[200], on;
        dda_line(0,0, 100,37, ox,oy,&on);
    }
    t2 = clock();
    printf("DDA 100万次耗时: %ld ms\n", (t2-t1)*1000/CLOCKS_PER_SEC);

    return 0;
}

编译与运行

gcc -O2 -o bresenham_test bresenham_line.c test_main.c -lm
./bresenham_test

验证方法

• 精度验证：对比Bresenham与DDA输出的坐标序列。两者在整数网格上应完全一致（因DDA四舍五入后与Bresenham选择的最优像素点相同）。观察输出，确认从(0,0)到(17,5)的路径点一致。
• 效率验证：程序打印两种算法各执行100万次插补的耗时。Bresenham仅用整数加减和比较，DDA需浮点乘除，预期Bresenham耗时显著更短（实际数值取决于硬件，以本机打印为准）。
• 正确性检查：终点坐标必须精确到达(17,5)，且路径点满足直线误差不超过0.5像素。

RTOS集成说明

在RTOS环境中，将bresenham_step()放入定时器中断或高优先级任务中，每次调用返回的掩码表示本周期应驱动的轴。例如mask=0x01时X轴发一个脉冲，mask=0x03时XY轴同时发脉冲。插补完成时返回0，可触发运动结束事件。

与DDA对比结论

• 精度：Bresenham与DDA（四舍五入取整后）在整数网格上生成的路径点完全一致，均满足最大偏差0.5像素。
• 效率：Bresenham每步仅需2~3次整数加法与1次比较；DDA每步需浮点乘法与加法各1次，且涉及浮点转整型。在无FPU的MCU上，Bresenham优势更明显。
• 适用性：Bresenham适合步进电机脉冲控制；DDA因浮点运算更适合带FPU的高端处理器或需要速度连续插补的场景。