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