计算机图形学笔记——画直线算法

画线算法主要用来解决如下问题：对于某个直线方程，已知起点重点，计算机如何绘制出这个线段。计算机绘制线段其实就是绘制一系列的像素点。

DDA算法

思路: 对于直线方程

$y = kx + b$

$\Delta x > \Delta y$

实现代码：

	//四舍五入 
	inline int round(float a) {return int(a+0.5f)}  
	
	void lineDDA(int startX, int startY, int endX, int endY)
	{
		float dx = endX - startX;
		float dy = endY - startY;
		float steps = fabs(dx) > fabs(dy) ? fabs(dx) : fabs(dy);
		float incX = dx / steps;
		float incY = dy / steps;

		for (int i = 0; i <= steps; i++)
		{
			float newX = (float)startX + (float)(i) * incX;
			float newY = (float)startY + (float)(i) * incY;
			drawPixel(round(newX), round(newY)); //画像素点
		}
	}

通过代码也可以看到，运算使用了浮点运算,取整，不利于用硬件实现。

Bresenham算法

同DDA算法一样选择步进坐标轴，我们假设步进坐标轴为

$x$

$|k| < 1$

$(x_n, y_n)$

$(x_{n+1}, y_{n+1})$

$x_{n+1} = x_n + 1$

$y_{n+1} < 1$

$(x_n + 1, y_n)$

$(x_n + 1, y_n+1)$

每次绘制下一个点时，我们期望有这样一个变量

$p_n$

$p_n > 0$

$(x_n + 1, y_n+1)$

$(x_n + 1, y_n)$

我们期望绘制的像素点离实际的坐标点距离越小越好，那么两个候选的像素坐标到实际坐标的距离分别为：

$d_{upper}$

$y_n+1 - y_{n+1}$

$d_{lower}$

$y_{n+1} - y_n$

对于直线方程

$y = kx + b$

$\Delta d = d_{lower} - d_{upper} = 2y_{n+1} - 2y_n -1 = 2(kx_{n+1} + b) - 2y_n -1$

其中

$x_{n+1} = x_n + 1$

$\Delta d = 2(kx_n - y_n) + 2k + 2b - 1$

如果

$\Delta d > 0$

$(x_n + 1, y_n+1)$

$\Delta d$

$p_n$

到这一步的式子中，为了消除

$k$

$k = \frac{X_{end} - X_{start}}{ Y_{end} - Y_{start}} = \frac{\Delta y}{\Delta x}$

$\Delta x$

$\Delta x \Delta d = 2(\Delta y x_n - \Delta x y_n) + 2\Delta y + 2b\Delta x - \Delta x = 2(\Delta y x_n - \Delta x y_n) + c$

因为

$\Delta x$

$p_n = \Delta x \Delta d$

进一步，我们可以通过

$p_n$

$p_{n+1}$

$p_{n+1} - p_n = 2(\Delta y(x_{n+1} - x_n) - \Delta x(y_{n+1} - y_n)) = 2(\Delta y - \Delta x(y_{n+1} - y_n))$

其中

$y_n+1$

$y_n$

$0$

$-1$

$$p_{n+1} = \begin{cases} p_n + 2\Delta y &\mbox{p_n \leq 0} \ p_n + 2(\Delta y - \Delta x) &\mbox{p_n > 0} \end{cases}$$

其中：

$p_0 = 2(\Delta y x_n - \Delta x y_n) + c = 2(\Delta y x_n - \Delta x (\frac{\Delta y}{\Delta x} x_0 + b)) + c = 2\Delta y - \Delta x$

下面给出斜率

$|k| < 1$

	void lineBresenham(int startX, int startY, int endX, int endY)
	{
		int x = startX;
		int y = startY;
		if (x > endX) //保证dx > 0
		{
			x = endX;
			endX = startX;
			y = endY;
			endY = startY;
		}
	
		int dx = endX - x;
		int dy = endY - y;
		int p = 2*dy - dx;
	
		drawPixel(x, y);
	
		while(x < endX)
		{
			x++;
			if (p > 0)
			{
				y++;
				p += 2 * (dy - dx);
			}
			else
			{
				p += 2 * dy;
			}
			drawPixel(x, y);
		}
	}

当

$|k|>1$