直线光栅化-Bresenham算法

Bresenham算法

对于两个顶点 \(P_{1}(x_{1},y_{1})\) 和 \(P_{2}(x_{2},y_{2})\) 满足 \(\Delta x =x_{2}-x_{1}>0\) 且 \(\Delta y=y_{2}-y_{1}>0\) 。设两点确定的直线方程的斜率为 \(k=\frac{\Delta y}{\Delta x}\) 。当 \(0<k<1\) 时，从 \(x\) 轴开始取样，决策参数递推方程为：

\[p_{1}=2\Delta y-\Delta x \]

\[p_{k+1}=\left\{\begin{matrix} p_{k}+2\Delta y-2\Delta x,p_{k}\ge0 \\ p_{k}+2\Delta y,p_{k}<0 \end{matrix}\right. \]

当 \(p_{k}\ge0\) 时 \(y_{k+1}=y_{k}+1\) ，当 \(p_{k}<0\) 时 \(y_{k+1}=y_{k}\) 。

当 \(k>1\) 时，则交换 \(x\) 和 \(y\) 变量，则变换后的直线方程斜率 \(k'=\frac{1}{k}\in(0,1)\)，此时归结为上述情况。

对于一般的直线光栅化算法，只需根据坐标系象限的对称性修改上述参数即可。

C++/OpenGL实现

下述代码为Bresenham算法绘制任意直线的C++/OpenGL代码实现：

void drawLineBresenham(GLint x1, GLint y1, GLint x2, GLint y2) {
    int deltaX = x2 - x1, deltaY = y2 - y1;
    double k = 1.0 * deltaY / deltaX;
    deltaX = abs(deltaX), deltaY = abs(deltaY);
    if (k < -1 || 1 < k) { // 斜率小于-1或大于1则交换x和y变量
        int tt = abs(deltaX); deltaX = abs(deltaY); deltaY = tt;
    }
    int p = (deltaY << 1) - deltaX; // 决策参数
    int dp1 = (deltaY << 1) - (deltaX << 1), dp2 = (deltaY << 1); // 缓存递推时常量
    int dx = (x1 < x2) ? 1 : -1, dy = (y1 < y2) ? 1 : -1; // 绘制方向
    int count = deltaX; // 绘制次数
    glVertex2i(x1, y1);
    if (-1 < k && k < 1) {
        for (int i = 1; i < count; i++) {
            x1 += dx; y1 += (p >= 0) ? dy : 0; // 计算下一个坐标
            glVertex2i(x1, y1);
            p += (p >= 0) ? dp1 : dp2; // 计算下一个决策参数
        }
    } else {
        for (int i = 1; i < count; i++) {
            x1 += (p >= 0) ? dx : 0; y1 += dy; // 计算下一个坐标
            glVertex2i(x1, y1);
            p += (p >= 0) ? dp1 : dp2; // 计算下一个决策参数
        }
    }
}