[TOC]

参考资料

• 我的练手demo
• Lesson 1 Bresenham’s Line Drawing Algorithm
• 维基百科

算法分析

算法代码

伪代码

function line(x0, x1, y0, y1)
     int deltax := x1 - x0
     int deltay := y1 - y0
     real error := 0
     real deltaerr := deltay / deltax    // 假設deltax != 0（非垂直線），
           // 注意：需保留除法運算結果的小數部份
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if abs (error) ≥ 0.5 then
             y := y + 1
             error := error - 1.0

一般化

void line(Vec2i p0, Vec2i p1, TGAColor color, TGAImage &image) {
    bool steep = std::abs(p1.y - p0.y) > std::abs(p1.x - p0.x);
    if (steep) {
        std::swap(p0.x, p0.y);
        std::swap(p1.x, p1.y);
    }

    if(p0.x > p1.x) {
        std::swap(p0, p1);
    }

    int dy = p1.y - p0.y;
    int dx = p1.x - p0.x;

    float derror = (float )std::abs(dy) / dx;
    float error = 0;
    int yStep = dy > 0 ? 1 : -1;
    float y = p0.y;
    for (int x = p0.x; x <= p1.x; x++) {
        if (steep) {
            image.set(y, x, color);
        } else {
            image.set(x, y, color);
        }

        error += derror;
        if (error > 0.5f) {
            error -=1;
            y += yStep;
        }
    }
}

最佳化

浮点数计算比较慢，换算成整数计算

void line(Vec2i p0, Vec2i p1, TGAColor color, TGAImage &image) {
    bool steep = std::abs(p1.y - p0.y) > std::abs(p1.x - p0.x);
    if (steep) {
        std::swap(p0.x, p0.y);
        std::swap(p1.x, p1.y);
    }

    if(p0.x > p1.x) {
        std::swap(p0, p1);
    }

    int dy = p1.y - p0.y;
    int dx = p1.x - p0.x;

    float derror = (float )std::abs(dy) * 2;
    float delta = dx * 2;
    float error = 0;
    int yStep = dy > 0 ? 1 : -1;;
    float y = p0.y;
    for (int x = p0.x; x <= p1.x; x++) {
        if (steep) {
            image.set(y, x, color);
        } else {
            image.set(x, y, color);
        }

        error += derror;
        if (error > dx) {
            error -= delta;
            y += yStep;
        }
    }
}