改进的 Bresenham 直线绘制算法

• 下载源代码 - 4.5 MB

引言

本文介绍了对原始 Bresenham 直线绘制算法进行的小改动，旨在考虑基本算法的执行速度。

背景

Bresenham 直线绘制算法是一种非常著名的在当今像素化显示器上进行直线光栅化的方法。它计算误差，即计算出的直线与理想直线之间的距离，并将其四舍五入到相邻像素。

请参阅下图，该图来自维基百科:

您可以看到，由于显示器的像素化，计算出的直线在 x 轴上与理想直线有所不同。 只有覆盖理想直线一部分的像素才会被绘制。 误差计算为理想直线的原始 y 轴值与光栅化直线的计算 y 轴值之间的差值，对于每个像素，并沿 x 轴平移，直到直线结束。

“线斜率”在开始时计算，见下图

并且，使用这个值，像素通过以下直线方程在直线的 x 轴上进行插值，通过计算最接近的 y 值

请参阅以下代码，该代码取自 Bresenham 直线渲染算法的项目源代码

	void CLineRendererProjectView::DrawBresenhamLine(int x0, int y0, int x1, int y1, COLORREF color)
	{
		double s = GetTime();

		int bpp = m_bmp.bmBitsPixel / 8;
		int dx = x1 - x0;
		int dy = y1 - y0;
		double k = (double)dy / (double)dx;

		DWORD color2 = _RGB(GetRValue(color), GetGValue(color), GetBValue(color));

		double y = (double)y0;
		int yi = y0;
		DWORD dwOffset = (y0 * m_bmp.bmWidth) + x0;
		LPDWORD lpData = (LPDWORD)m_lpBits;
		lpData += dwOffset;
		for (int x=x0; x<x1; x++)
		{
			(*lpData) = color2;

			y += k;

			if ((int)(y+0.5) > yi)
			{
				lpData += m_bmp.bmWidth;
				yi++;
			}

			lpData++;
		}

		double e = GetTime();

		m_fTimeBresenham = e - s;
	}

因此，该算法从 x0（x 轴上的起点）到 x1（x 轴上的终点）。它计算 y 的下一个值并绘制四舍五入的像素。 如果 y 的下一个值大于当前值，则当前值递增，并且图像数据的指针也递增，因此我们在下一个循环传递中绘制正确的像素。

根据原始算法的定义，这仅对于在第一象限绘制直线是正确的，其中斜率从 0 变为 1。 有修改可用于将其扩展到任何斜率值（此处也在 CodeProject 上）。

当前工作

这里的主要问题是——如何稍微加速它？ 考虑到涉及定点计算和低级汇编程序设计，该算法有所改进。

需要知道的是，该算法非常快速和简单。 那么，如何提高其原生速度呢？ 所有其他改进也可以应用于此修改版本——它只会变得更快。

最简单的解决方案是渲染像素流，而不仅仅是单个像素。 没什么特别的，对吧？ 正确，这就是本项目中实现的方式

	void CLineRendererProjectView::DrawModifiedBresenhamLine(int x0, int y0, int x1, int y1, COLORREF color)
	{
		double s = GetTime();

		int dx = x1 - x0;
		int dy = y1 - y0 + 1;

		double offset = 0.5;
		int total = 0;
		int len = 0;
		double k_inv = (double)dx / (double)dy;
		if (dy == 1)
		{
			offset = 1.0;
		}
		else
		{
			k_inv = (double)dx / (double)(dy - 1);
		}

		DWORD color2 = _RGB(GetRValue(color), GetGValue(color), GetBValue(color));

		DWORD dwOffset = (y0 * m_bmp.bmWidth) + x0;
		LPDWORD lpData = (LPDWORD)m_lpBits;
		lpData += dwOffset;

		for (int y=y0; y<=y1; y++)
		{
			len = (int)(offset * k_inv + 0.5);
			len = len - total;
			if ((total+len) > dx)
			{
				len = dx - total;
			}
			for (int x=0; x<len; x++)
			{
				(*lpData) = color2;
				lpData++;
			}
			total += len;
			lpData += m_bmp.bmWidth;
			offset += 1.0;
		}

		double e = GetTime();

		m_fTimeModifiedBresenham = e - s;
	}

因此，我们在这里沿 y 轴前进，而不是像原始算法那样沿 x 轴前进。 并且，对于每个线段，我们正在计算到该点的像素数量。 我们减去到目前为止渲染的总像素数，差值是覆盖该线段的像素流。 然后，我们在内循环中渲染像素流，这比渲染具有相同 y 值的单个像素更快。

这是加速算法的关键点。

请参阅下面演示应用程序的屏幕截图

这里使用原始和修改后的 Bresenham 直线绘制算法渲染了正好 150 条直线。 输出结果相同，但速度差异显着。

局限性

这种方法存在一些局限性。 第一个限制是线的长度。 对于较短的线，修改后的版本将比原始版本慢。 此外，线斜率在此处至关重要。 对于斜率高于 0.5 的线，修改后的版本将变慢，可能会降至原始算法的速度。

但是，对于第一象限中斜率从 0 变为 1 的通用线，考虑到渲染线的总数，修改后版本的总渲染时间应该与原始算法版本的总渲染时间相似，或更少。

因此，理想的解决方案可能是将这两个算法结合起来以获得最大速度的算法。

关注点

这只是对众所周知主题的实验，最终结果或多或少是预期的。这项工作可以帮助研究更好，更快的直线渲染算法。