光栅化算法-Bresenham算法
光栅化算法-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\) 。对于两个顶点，可以确定一条直线方程，设为 \(y=kx+b\) ，其中 \(k=\frac{\Delta y}{\Delta x}\) 。当 \(0<k<1\) 时，绘制直线时将从 \(x\) 轴开始取样。设置当前绘制的顶点为 \(P_{k}(x_{k},y_{k})\) ，那么下一次绘制的顶点可能为 \(P_{k+1}(x_{k}+1,y_{k})\) 或 \(P_{k+1}(x_{k}+1,y_{k}+1)\) 。
为了确定下一次绘制的顶点，我们引入一个决策参数 \(p\) 。先定义两个距离参数 \(d_{lower}=y(x_{k}+1)-y_{k}\) 和 \(d_{upper}=y_{k}+1-y(x_{k}+1)\) ，然后定义决策参数 \(p = \Delta x(d_{lower}-d_{upper})\) 。如果决策参数 \(p>0\) ，那么 \(d_{lower}>d_{upper}\) ，此时下一个绘制的顶点为 \(P_{k+1}(x_{k}+1,y_{k}+1)\) ；如果决策参数 \(p<0\) ，那么 \(d_{lower}<d_{upper}\) ，此时下一个绘制的顶点为 \(P_{k+1}(x_{k+1},y_{k})\) 。
根据定义，我们可以得到决策参数 \(p\) 的递推方程和初始参数 \(p_{1}\)：
当 \(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; // 计算下一个决策参数
}
}
}