Bresenham 算法

2023-12-24 15:58:23

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

原理

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

在这里插入图片描述

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

y i + 1 = { y i + 1 ; d ≥ 0.5 y i d < 0.5 y_{i+1} = \begin{cases} y_i + 1; &\quad d \geq 0.5\\ y_i &\quad d < 0.5 \end{cases} yi+1?={yi?+1;yi??d0.5d<0.5?
误差项初始值 d 0 = 0 d_0 = 0 d0?=0, 如果 d ≥ 0.5 d \geq 0.5 d0.5 y y y 方向递增一个单位并且将 d d d 减 1.

在这里插入图片描述
消除 0.5 的影响

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

y i + 1 = { y i + 1 ; e ≥ 0 y i e < 0.5 y_{i+1} = \begin{cases} y_i + 1; &\quad e \geq 0\\ y_i &\quad e < 0.5 \end{cases} yi+1?={yi?+1;yi??e0e<0.5?

e 0 = ? 0.5 e_0 = -0.5 e0?=?0.5 , 如果 e ≥ 0 e \geq 0 e0, 则 e = e ? 1 e = e -1 e=e?1

在这里插入图片描述

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

0 ≤ k ≤ 1 0 \leq k \leq 1 0k1 Δ x \Delta x Δx 为正
e = 2 Δ x e = 2 Δ x ( d ? 0.5 ) = ? Δ x + 2 Δ x d e = 2 \Delta x e = 2 \Delta x (d-0.5) = -\Delta x + 2 \Delta x d e=xe=x(d?0.5)=?Δx+xd
初始值 e 0 = ? Δ x e_0 = -\Delta x e0?=?Δx
当 x 方向走一步,有 e + = 2 Δ y e += 2 \Delta y e+=y

如果 e ≥ 0 e \geq 0 e0

e = 2 Δ x ( e ? 1 ) = 2 Δ x e ? 2 Δ x e ? = 2 Δ x e = 2 \Delta x (e-1) = 2 \Delta x e - 2 \Delta x \\ e -= 2 \Delta x e=x(e?1)=xe?xe?=x

算法

  • 设置像素点的颜色
  • 读入直线的两个端点坐标
  • e e e 的初始值为 e 0 = ? 0.5 e_0 = -0.5 e0?=?0.5
  • 从起点开始,沿着 x x x 轴方向每递增一个单位,有 e + = 2 Δ y e += 2 \Delta y e+=y
  • ≥ 0 \geq 0 0 时,下一个像素更新为 ( x i + 1 , y i + 1 ) (x_i + 1, y_i + 1) (xi?+1,yi?+1), 同时将 e e e 更新为 e ? = 2 Δ x e -= 2 \Delta x e?=x, 否则,下一个像素更为 ( x i + 1 , y i + 1 ) (x_i + 1, y_i +1) (xi?+1,yi?+1)
  • 绘制像素点,执行 x + + x++ 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 算法是一种经典的直线光栅化算法, 使用了最小的计算量,使得单点生成算法已经没有改进的余地。

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

文章来源:https://blog.csdn.net/weixin_43862398/article/details/135172074
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。