计算机图形学技术笔记~直线Bresenham算法

研究内容：

（1）基于图形设备的基本图形元素的生成算法，如用光栅图形显示器生成直线、圆弧、二次曲线、封闭边界内的图案填充等。

布雷森汉姆直线Bresenham算法：

(1) 利用距离误差大小比较判断符号；

(2) 推导递推公式；

(3) 不必计算直线斜率，不用浮点数；

(4) 只用整数加减法和乘2运算，乘2运算可以用硬件移位实现；

代码笔记：

#include <iostream>
#include <vector>

struct Point2D
{
    int x;
    int y;
    Point2D(int x = 0, int y = 0) : x(x), y(y) {}
};

void swap(int& x, int& y) {
    int temp = x;
    x = y;
    y = temp;
}

std::vector<Point2D> lineBresenham(int x0, int y0, int x1, int y1)
{
    int dx = x1 - x0;
    int dy = y1 - y0;

    int dir;
    if (dx * dy >= 0) {
        dir = 1;
    }
    else {
        dir = -1;
    }
    std::vector<Point2D> points;
    // a 象限
    if (std::abs(dx) > std::abs(dy)) {
        if (dx < 0) {
            swap(x0, x1);
            swap(y0, y1);
            dx = -dx;
            dy = -dy;
        }
        int p1 = (2 * (dy * dir) - dx);
        int c1 = 2 * dy * dir;
        int c2 = 2 * ((dy * dir) - dx);
        while (true) {
            points.emplace_back(x0, y0);
            if (x0 == x1 && y0 == y1) break;
            x0 += 1;
            if (p1 > 0) {
                p1 += c2;
                y0 += dir;
            }
            else {
                p1 += c1;
            }
        }
    }
    else {    // b 象限
        if (dy < 0) {
            swap(x0, x1);
            swap(y0, y1);
            dx = -dx;
            dy = -dy;
        }
        int p1 = (2 * (dx * dir) - dy);
        int c1 = 2 * dx * dir;
        int c2 = 2 * ((dx * dir) - dy);
        while (true) {
            points.emplace_back(x0, y0);
            if (x0 == x1 && y0 == y1) break;
            y0 += 1;
            if (p1 > 0) {
                p1 += c2;
                x0 += dir;
            }
            else {
                p1 += c1;
            }
        }
    }
    return std::move(points);
}