Bresenham 算法

1965 年，Bresenham 为数字绘图仪开发了一种绘制直线的算法，该算法同样使用于光栅扫描显示器，被称为 Bresenham 算法。

原理

算法的目标是选择表示直线的最佳光栅位置。Bresenhan 算法在主位移方向上每次递增一个单位。另一个方向的增量为 0 或 1，取决于理想直线于最近网格点的距离，这一距离称为误差项，误差项用 d 表示。

当 $x$ 方向递增一个单位，有 $d=d+k$; 则

$$y_{i+1}=\{\begin{array}{ll}{y}_i+1;& d\ge 0.5\\ y_i& d<0.5\end{array}$$
误差项初始值 $d_0=0$， 如果 $d\ge 0.5$， $y$ 方向递增一个单位并且将 $d$ 减 1.

消除 0.5 的影响

令 $e=d?0.5$. 当 $x$ 方向走一步，有 $e=e+k$, 则

$$y_{i+1}=\{\begin{array}{ll}{y}_i+1;& e\ge 0\\ y_i& e<0.5\end{array}$$

$e_0=?0.5$ , 如果 $e\ge 0$, 则 $e=e?1$

消除浮点数的影响，斜率和 $e$, 进行整数化

当 $0\le k\le 1$， $\Delta x$ 为正
$$e=2\Delta xe=2\Delta x(d?0.5)=?\Delta x+2\Delta xd$$
初始值 $e_0=?\Delta x$
当 x 方向走一步，有 $e+=2\Delta y$

如果 $e\ge 0$ 有

$$\begin{gathered} e=2\Delta x(e?1)=2\Delta xe?2\Delta x \\ e?=2\Delta x \end{gathered}$$

算法

• 设置像素点的颜色
• 读入直线的两个端点坐标
• 取 $e$ 的初始值为 $e_0=?0.5$
• 从起点开始，沿着 $x$ 轴方向每递增一个单位，有 $e+=2\Delta y$
• 当 $\ge 0$ 时，下一个像素更新为 $(x_i+1,y_i+1)$, 同时将 $e$ 更新为 $e?=2\Delta x$, 否则，下一个像素更为 $(x_i+1,y_i+1)$
• 绘制像素点，执行 $x++$ 操作到终点

void BresenhamLine(CDC* pDC, CPoint P0, CPoint P1)
{
	COLORREF crColor = RGB(0, 0, 0);
	int dx = P1.x - P0.x;
	int dy = P1.y - P0.y;
	int e = - dx;
	for (int x=P0.x, y=P0.y; x < P1.x; x++) {
		pDC->SetPixelV(x, y, crColor);
		e += 2 * dy;
		if (e >= 0) {
			y++;
			e -= 2 * dx;
		}
	}
}

整数 Bresenham 算法是一种经典的直线光栅化算法, 使用了最小的计算量，使得单点生成算法已经没有改进的余地。

参考 《计算几何算法与实现》孔令德