光栅图形学(3)-Bresenham画线算法

文章目录[x]
  1. 1:算法介绍
  2. 2:步骤
  3. 3:代码实现
  4. 4:参考

 

 

FBI WARNING:本文含有数学公式,如显示异常请刷新页面

算法介绍


注:本文讨论的情况都是斜率在[0, 1)之间的情况

如图所示,第k步绘制在了 $ (x_k, y_k) $ 的位置,此时下一个像素只能在 $ (x_{k+1},y_k) $ 和 $ (x_{k+1},y_{k+1}) $ 之间选择。如下,

\begin{equation}
\begin{cases}
&x_{next} = x_k + 1 \\
&y_{next} = \begin{cases}
y_{k} & d_1 - d_2 < 0 \\
y_{k+1} & d_1 - d_2 > 0
\end{cases}
\end{cases}
\end{equation}

由上图可得: $$ d_1 = y - y_k \quad d_2 = y_k  + 1 - y \quad y = mx_{k+1}+b \quad m=\frac{\Delta y}{\Delta x} \quad x_{k+1}=x_k+1 $$ 所以

\begin{equation}
\begin{split}
d_1 - d_2 &= (y - y_k) - (y_k  + 1 - y) \\
&= y - y_k - y_k - 1 + y \\
&=2y - 2y_k - 1 \\
&=2\cdot(mx_{k+1} + b) - 2y_k - 1 \\
&=2mx_{k+1} + 2b - 2y_k - 1 \\
&=2\frac{\Delta y}{\Delta x}\cdot x_{k+1} + 2b - 2y_k - 1 \\
\Delta x(d_1-d_2) &= 2\Delta y\cdot x_{k+1} + 2\Delta x\cdot b - 2\Delta x\cdot y_k - \Delta x \\
\Delta x(d_1-d_2) &= 2\Delta y\cdot x_k + 2\Delta y + 2\Delta x\cdot b - 2\Delta x\cdot y_k - \Delta x \\
\Delta x(d_1-d_2) &= 2\Delta y\cdot x_k - 2\Delta x\cdot y_k + 2\Delta y + 2\Delta x\cdot b - \Delta x \\
令G &= 2\Delta y + 2\Delta x\cdot b - \Delta x \quad(G为常数)\\
则令p_k &= 2\Delta y\cdot x_k - 2\Delta x\cdot y_k + G \\
故p_{next}-p_k &= (2\Delta y\cdot x_{next} - 2\Delta x\cdot y_{next} + G) -(2\Delta y\cdot x_k - 2\Delta x\cdot y_k + G) \\
&= 2\Delta y\cdot (x_k + 1) - 2\Delta x\cdot y_{next} - 2\Delta y\cdot x_k + 2\Delta x\cdot y_k \\
&=2\Delta y - 2\Delta x\cdot y_{next} + 2\Delta x\cdot y_k
\end{split}
\end{equation}

由于 $ y_{next} $ 有两种情况,故分类讨论,

当$ p_k < 0  $时, 根据式(1)可知

\begin{equation}
\begin{split}
p_{k+1} - p_k &= 2\Delta y - 2\Delta x\cdot y_k + 2\Delta x\cdot y_k \\
&= 2\Delta y
\end{split}
\end{equation}

当$ p_k > 0  $时, 根据式(1)可知

\begin{equation}
\begin{split}
p_{k+1} - p_k &= 2\Delta y - 2\Delta x\cdot y_{k+1} + 2\Delta x\cdot y_k \\
&= 2\Delta y - 2\Delta x\cdot (y_k + 1) + 2\Delta x\cdot y_k \\
&= 2\Delta y - 2\Delta x
\end{split}
\end{equation}

此时只需要再推导出初始的 $ p_1 $ 即可推导出后面所有的 $ p $,由式(2)可得 $$ p_k = 2\Delta y\cdot x_k - 2\Delta x\cdot y_k + G  $$ 故

\begin{equation}
\begin{split}
p_1&= 2\Delta y\cdot x_1 - 2\Delta x\cdot y_1 + 2\Delta y + 2\Delta x\cdot b - \Delta x \\
因为 y &= mx + b,所以 b =  y - \frac{\Delta y}{\Delta x}\cdot x \quad 故 \\
p_1&= 2\Delta y\cdot x_1 - 2\Delta x\cdot y_1 + 2\Delta y + 2\Delta x\cdot (y_1 - \frac{\Delta y}{\Delta x}\cdot x_1 ) - \Delta x \\
p_1&= 2\Delta y - \Delta x
\end{split}
\end{equation}

步骤


  1. 得到输入信息x1,y1,x2,y2
  2. 计算 dx, dy
  3. 若dx > dy,则继续下面的步骤
  4. 计算初始 p = 2 * dy - dx
  5. 当x1 <= x2时,执行循环6 7 8
  6. putpixel
  7. 如果p > 0,则 p += 2dy - 2dx,否则p += 2dy
  8. x += 1

代码实现


// Bresenham's Line Drawing Algorithm
void Rasterizer::DrawLine(Vector2 from, Vector2 to, Color& c)
{
	int x, y, dx, dy, dx2, dy2, p;
	x = from.x;
	y = from.y;

	dx = to.x - from.x;
	dy = to.y - from.y;

	dx2 = dx << 1;
	dy2 = dy << 1;

	// m < 1 && m == 0
	if (dx > dy)
	{
		p = dy2 - dx;
		while (x <= to.x)
		{
			DrawPixel(x, y, c);
			if (p > 0)
			{
				p -= dx2;
				y++;
			}

			p += dy2;
			x++;
		}
	}
	else // m >= 1, m不存在, from==to
	{
		p = dx2 - dy;
		while (y <= to.y)
		{
			DrawPixel(x, y, c);
			if (p > 0)
			{
				p -= dy2;
				x++;
			}

			p += dx2;
			y++;
		}
	}
}

 

 

 

参考


Bresenham's Line Drawing Algorithm
直线扫描转换算法-Bresenham算法

注:强烈推荐看第一个视频,简直是业界良心,推导十分严谨。第二个视频是中国大学MOOC的视频,是PPT讲课,且十分跳跃,感觉根本不是面向初学者的,真不知道这么讲的意义何在。大概就是 因为1+1=2,所以7 * 8 = 56,的感觉,直接从头就到尾了,中间的数学证明部分为零。

 

顺便点个赞吧

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像