光栅图形学(2)-中点画线算法

文章目录[x]
  1. 1:算法介绍
  2. 2:推导

 

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

算法介绍


 

名词解释:
理想直线:数学意义上的直线,即直接从绘制的起始点连接至终止点
中点:下一步绘制时可供选择的两点的中点
目标点:即下一步要绘制的点

如图所示,如要绘制一条从点 $ P1 到 P2 $ 的点,可以先判断中点在理想直线的方向,由此可得理想直线与哪边更近,从而决定下一步要绘制的是哪个点。若是上图的情况,那么在第一步时,下一个要绘制的点应该是点 $ (3,2)  和 (3, 3) $中的一个,此时中点在理想直线的上方,说明理想直线离点 $ (3, 2) $ 更近,所以应该绘制 $ (3,2) $这个点

 

推导


设斜率 = m

此算法使用的是直线方程的一般式即 $ Ax + By + C = 0 $,其中 $ A = -\Delta y \quad B = \Delta x  \quad C = -B\times\Delta x$

设 $ d $ 为 将中点代入到直线方程中的结果

设 $ m_0 $ 为第一个中点, $  d_0 (x_{m0},y_{m0}) $ 为将 $ m_0 $ 代入到直线方程中的结果,以此类推

设$ P1(x_1, y_1) $ 为起始点

当 m >= 0 && m <= 1 时,如图一所示

\begin{equation}
y_{new} = \begin{cases}
y_{old} & d \geqslant 0 \\
y_{old} + 1 & d < 0
\end{cases}
\end{equation}

\begin{equation}
\begin{split}
d_0&=f(x_{m0},y_{m0}) \\
&= f(x_1 + 1, y_1 + 0.5)\\
&=A(x_1 + 1) + B (y_1+0.5) + C \\
\end{split}
\end{equation}

假设 $ d_0 < 0 $
\begin{equation}
\begin{split}
d_1&=f(x_{m1},y_{m1}) \\
&=f(x_1+2,y_1+1.5) \\
&=A(x_1+2)+B(y_1+1.5)+C \\
&=A(x_1+1)+B(y_1+0.5)+C+A+B \\
&=d_0+A+B
\end{split}
\end{equation}

假设 $  d_0 \geqslant 0 $
\begin{equation}
\begin{split}
d_1&=f(x_{m1},y_{m1}) \\
&=f(x_1+2,y_1+0.5) \\
&=A(x_1+2)+B(y_1+0.5)+C \\
&=A(x_1+1)+B(y_1+0.5)+C+A \\
&=d_0+A
\end{split}
\end{equation}

\begin{equation}
\therefore \begin{cases}
d_{NE}=A+B & (d<0, d_{NE}即为d东北的增量) \\
d_E=A & (d \geqslant 0, d_E即为d东的增量)
\end{cases}
\end{equation}

推导 $ d_0 $
\begin{equation}
\begin{split}
d_0&=A(x_1+1)+B(y_1+0.5)+C \\
&=A x_1 + By_1 + C + A + 0.5B \\
&\because Ax_1 + By_1 + C = f(x_1,y_1) = 0 \\
&\therefore d_0 = A + 0.5B \\
&又因为此算法只关心 d  的符号,所以可以将 d_0 以 2d_0 来代替,\\
&从而取消浮点数,具体请直接看代码注释
\end{split}
\end{equation}

 

代码实现:

void DDA::DrawLineByMidPoint(Vector2 from, Vector2 to)
{
	int a, b, d0, x, y;

	float dx = to.x - from.x;
	float dy = to.y - from.y;
	float m = dy / dx;

	x = from.x;
	y = from.y;

	// Ax + By + C =0
	// a=-△y, b=△x, c=-B(△x)
	a = -dy; b = dx;

	if (m >= 0 && m <= 1)
	{
		int d0 = (a << 1) + b;   // 本应该是 d  = A + 0.5B。 但是我们只需要d的符号,而不关心其数值,所以可以用 2d = 2A + B来代替,故可以写成 d0 = 2 * A + B;
		int dE = a << 1;		 // 本应该是 dE = a + b,同上理, dE = 2 * (a + b)
		int dNE = (a + b) << 1;	 // 本应该是 dNE = a,同上理, dE = 2a

		//qLog("x=%d,y=%d\n", x, y);
		m_RenderSystem->GetRasterizer()->DrawPixel(x, y, Color::blue);
		while (x < to.x)
		{
			x += 1;
			if (d0 < 0)
			{
				d0 += dNE;
				y += 1;
			}
			else
			{
				d0 += dE;
			}

			//qLog("x=%d,y=%d\n", x, y);
			m_RenderSystem->GetRasterizer()->DrawPixel(x, y, Color::blue);
		}
	}
}

 

当 m > 1 时

\begin{equation}
x_{new} = \begin{cases}
x_{old} + 1 & d \geqslant 0 \\
x_{old} & d < 0
\end{cases}
\end{equation}

\begin{equation}
\begin{split}
d_0&=f(x_{m0},y_{m0}) \\
&= f(x_1 + 0.5, y_1 + 1)\\
&=A(x_1 + 0.5) + B (y_1+1) + C \\
\end{split}
\end{equation}

假设 $  d_0 < 0 $
\begin{equation}
\begin{split}
d_1&=f(x_{m1},y_{m1}) \\
&=f(x_1+0.5,y_1+2) \\
&=A(x_1+0.5)+B(y_1+2)+C \\
&=A(x_1+0.5)+B(y_1+1)+C+B \\
&=d_0+B
\end{split}
\end{equation}

假设 $  d_0 \geqslant 0 $
\begin{equation}
\begin{split}
d_1&=f(x_{m1},y_{m1}) \\
&=f(x_1+1.5,y_1+2) \\
&=A(x_1+1.5)+B(y_1+2)+C \\
&=A(x_1+0.5)+B(y_1+1)+C+A+B \\
&=d_0+A+B
\end{split}
\end{equation}

\begin{equation}
\therefore \begin{cases}
d_{NE}=A+B & (d\geqslant0, d_{NE}即为d东北的增量) \\
d_N=B & (d < 0, d_N即为d北的增量)
\end{cases}
\end{equation}

推导 $ d_0 $
\begin{equation}
\begin{split}
d_0&=A(x_1+0.5)+B(y_1+1)+C \\
&=A x_1 + By_1 + C + 0.5A + B \\
&\because Ax_1 + By_1 + C = f(x_1,y_1) = 0 \\
&\therefore d_0 = 0.5A + B \\
&又因为此算法只关心 d  的符号,所以可以将 d_0 以 2d_0 来代替,\\
&从而取消浮点数,具体请直接看代码注释
\end{split}
\end{equation}

代码实现(接上部分):

else if (m > 1)
{
	d0 = a + (b << 1);
	int dN = b << 1;
	int dNE = (a + b) << 1;

	//qLog("x=%d,y=%d\n", x, y);
	m_RenderSystem->GetRasterizer()->DrawPixel(x, y, Color::blue);
	while (y < to.y)
	{
		y += 1;

		if (d0 < 0)
		{
			d0 += dN;
		}
		else
		{
			d0 += dNE;
			x += 1;
		}

		//qLog("x=%d,y=%d\n", x, y);
		m_RenderSystem->GetRasterizer()->DrawPixel(x, y, Color::blue);
	}
}

 

m >= -1 && m < 0

m < -1

好多啊 不想写了。

 

参考文献:

任意斜率的中点画线算法
直线扫描转换算法-中点

点赞

发表评论

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