Click here to Skip to main content
Click here to Skip to main content

Tagged as

Modified Bresenham's Line Drawing Algorthm

, 16 Aug 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
A modified version of the Bresenham's line drawing algorithm

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

darkoman
Software Developer (Senior) Elektromehanika d.o.o. Nis
Serbia Serbia
He has a master degree in Computer Science at Faculty of Electronics in Nis (Serbia), and works as a C++/C# application developer for Windows platforms since 2001. He likes traveling, reading and meeting new people and cultures.

Comments and Discussions

 
GeneralMy vote of 1 Pinmemberpocoulet2-Sep-13 5:51 
QuestionOnly half of the story ... [modified] PinmemberStefan_Lang19-Aug-13 3:08 
QuestionTwo ways to make it faster PinmemberYvesDaoust19-Aug-13 0:47 
BugCode is not robust Pinmemberpuzsol18-Aug-13 22:21 
SuggestionIt can be even more fast... PinmemberEmilio Garavaglia18-Aug-13 4:34 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 16 Aug 2013
Article Copyright 2013 by darkoman
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid