Modified Bresenham's Line Drawing Algorthm

• Download source - 4.5 MB

Introduction

This article is about the small modification of the original Bresenham's line drawing algorithm, considering the base algorithm execution speed.

Background

The Bresenham's line drawing algorithm is very well known method for a line rasterization on the pixelized displays we have today. It calculates the error, that is the distance of the calculated line from the ideal line and rounds it to the neighbouring pixels.

See the image below, which is borrowed from the Wikipedia:

You see how the calculated line, along the x-axis, differs from the ideal line, due to the display pixelization. Only the pixels that cover a part of the ideal line are plotted. The error is calculated as the difference between the original y-axis value for the idel line and the calculated y-axis value of the rasterized line, for each pixel and translated through the x-axis, up to the line end.

The "line slope" is calculated at the beginning, see image below:

And, using this valus, the pixels are interpolated along the x-axsi of the line, by calculating the nearest y-values using the following line equation:

See the code below, taken from the project's source, of the Bresenham's line rendering algorithm:

	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;
	}

So, the algorithm goes from the x0 (starting point on the x-axis) to the x1 (ending point on the x-axis). It calculates the next value for the y and plots the rounded pixel. In the case that the next value of the y is geater then the current one, the current value is incremented, as also the pointer to the image data, so we plot the correct pixel in the next loop pass.

According to the original algorithm definition, this is correct for plotting of lines only in the first octant, where the slope goes from 0 to 1. The modifications are available (here on the CodeProject also) for extending this to any slope value.

The Current Work

The main question here is - how to speed this a bit? There are improvements of this algorithm considering the arithmetic that involve the fixed-point calculations and the low level assembler programming.

Just to be known, this algorithm is very fast and simple. So, how to increase its native speed? All other improvements could be applied also to this modified version - it will get only more faster.

The most simple solution is to render the pixel streams and not just the single pixels. Nothing special, right? Correct, and here is how it is implemented in this project:

	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;
	}

So, we are going here along the y-axis, and not along the x-axis like in the original algorithm. And, for each line segment, we are calculating how many pixels are up to that point. We subtract the total pixels rendered up to this point and the difference is the pixels stream that covers that line segment. Then we render the pixels stream in the inner loop, which is faster then rendering single pixels which have the same y-value.

This is the key-point of the algorithm speed up.

Please see the image below of the demo application screenshot:

Here are rendered the exactly 150 lines using original and modified version of the Bresenham's line drawing algorithm. The output is identical and the speed difference is significant.

The Limitations

There are some limitations of this approach. The first one is the length of the line. For shorter lines, the modified version will be slower then the original one. Also, the line slope is critical here. For the lines that have the slope above the 0.5 the modified version will slower down, possible to the speed of the original algorithm.

But, for the general line, in the first octant where the slope goes from 0 to 1 the total rendering time of the modified version, considering the total number of rendered lines, should be similar to the total rendering time of the original version of the algorithm, or less.

So, the ideal solution could be the algorithm which would combine these two algorithms to get the most of its speed.

Points of Interest

This was just an experiment with the well known subject, and the final results were more or less expected. This work could help in the research of the better and faster line rendering algorithms.