天天精选！直线光栅化-Bresenham算法

2023-04-10 21:02:24 来源：博客园

【资料图】

直线光栅化-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\[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; // 计算下一个决策参数        }    }}

关键词：