A great Code Editor for Windows
If you haven't used EditPadPro yet, I strongly suggest checking it out. I've been using this editor for years and it is truely the best piece of software I've ever used. It even allows you to link your project to your FTP server and upload files as you are editing them automatically. Just save the file in the editor and it will be uploaded to your server -- no waiting for the file to be uploaded.

I usually never pay for software I find online, but I actually went ahead and upgraded to the full version that unlocks a bunch of features, well worth the $49.95
You can courteously use the Free Evaluation Demo for as long as you want.

Download Now for FREE and
Make your coding life easier


A fully functional demo (only some features are missing)
DirectDraw - 4 - Lines Source code
JUMP TO - dd1 - dd2 - dd3 - dd4 - dd5 - dd6 - dd7

Bresenham's Line-Drawing Algorithm Explained

In this tutorial I will explain how to draw lines using the Bresenham's line-drawing algorithm. And then show you complete line drawing function. For the sake of this series of tutorials I will use the 16-bit mode, so we will be dealing with ushorts(or words) per pixel. I will also use the 16-bit color macro defined in the previous tutorial. The following is an explanation of how the Bresenham's line-drawing algorithm works, rather than exact implementation.

bresenham's line drawing algorithm graph/chart image
bresenham's line drawing algorithm, visually.

Take a look at this image. One thing to note here is that it is impossible to draw the true line that we want because of the pixel spacing(in other words there's not enough precision for drawing true lines on a PC monitor especially when dealing with low resolutions). The Bresenham's line-drawing algorithm is based on drawing an approximation of the true line. The true line is indicated in bright color, and its approximation is indicated in black pixels. In this example the starting point of the line is located exactly at 0, 0 and the ending point of the line is located exactly at 9, 6. The way the algorithm works is this. First it decides which axis is the major axis and which is the minor axis. The major axis is longer than the minor axis. On this picture illustrated above the major axis is the X axis. Each iteration progresses the current value of the major axis(starting from the original position), by exactly one pixel. Then it decides which pixel on the minor axis is appropriate for the current pixel of the major axis. How can you approximate the right pixel on the minor axis that matches the pixel on the major axis? - that's what Bresenham's line-drawing algorithm is all about. And it does so by checking which pixel's center is closer to the true line. On the picture above it would be easy to identify these pixels by eye. I added vertical spans to let you grasp the idea better visually. Take a closer look. The center of each pixel is marked with a dot. The algorithm takes the coordinates of that dot and compares it to the true line. If the span from the center of the pixel to the true line is less or equal to 0.5, the pixel is drawn at that location. That span is more generally known as the error term.

You might think of using floating variables but I assure you the whole algorithm is done in straight integer math with no multiplication or division in the main loops(no fixed point math either). How is it possible? Basically, during each iteration through the main drawing loop the error term is tossed around to identify the right pixel as close as possible to the true line. Let's consider these two deltas between the length and height of the line: dx = x1 - x0; dy = y1 - y0; This is a matter of precision and since we're working with integers you will need to scale the deltas by 2 generating two new values: dx2 = dx*2; dy2 = dy*2; These are the values that will be used to change the error term. Why scale? The error term must be first initialized to 0.5 and that cannot be done using an integer. To confuse you even further, finally the scaled values must be substracted by either dx or dy(the original, unscaled delta values) depending on what the major axis is (either x or y).

It's time for some code. Here is the initialization part.



// This function assumes a 16-bit drawing surface to be already locked
// locking is introduced in the previous tutorial
// lpitch and lpscreen are global
// lpitch - pitch of the locked surface
// lpscreen - points to the first pixel in the locked surface

void Line (int x1, int y1, int x2, int y2, ushort color)
{
		int		dx,		//deltas
            dy,
            dx2,	//scaled deltas
            dy2,
            ix,		//increase rate on the x axis
            iy,		//increase rate on the y axis
            err,	//the error term
            i;		//looping variable

	int pitch = lpitch;

	// identify the first pixel
	ushort *ptr_vid = lpscreen + x1 + (y1 * (pitch >> 1));

	// difference between starting and ending points
	dx = x2 - x1;
	dy = y2 - y1;

	// calculate direction of the vector and store in ix and iy
	if (dx >= 0)
		ix = 1;

	if (dx < 0)
	{
		ix = -1;
		dx = abs(dx);
	}

	if (dy >= 0)
		iy = (pitch >> 1);

	if (dy < 0)
	{
		iy = -(pitch >> 1);
		dy = abs(dy);
	}

	// scale deltas and store in dx2 and dy2
	dx2 = dx * 2;
	dy2 = dy * 2;

All variables are set and it's time to enter the main loop.

        
	if (dx > dy)	// dx is the major axis
	{
		// initialize the error term
		err = dy2 - dx;

		for (i = 0; i <= dx; i++)
		{
			*ptr_vid = color;
			if (err >= 0)
			{
				err -= dx2;
				ptr_vid += iy;
			}
			err += dy2;
			ptr_vid += ix;
		}
	}
	
	else 		// dy is the major axis
	{
		// initialize the error term
		err = dx2 - dy;

		for (i = 0; i <= dy; i++)
		{
			*ptr_vid = color;
			if (err >= 0)
			{
				err -= dy2;
				ptr_vid += ix;
			}
			err += dx2;
			ptr_vid += iy;
		}
	}
} // end of Line(...

Check out the source code for the full implementation of line-drawing on the primary surface. The good thing about this function is even if it can be optimized it is still pretty fast. I did not optimize it for the sake of a clear explanation of how this algorithm performs. But there are quite a few methods of doing so out there, I'm sure you could find some of them on the internet. It is not 100% precise, but it is not very evident in any resolution higher than 320x240. This is really not a problem when you're working in 640x480 or higher resolution. If you want a super-precise line, I would recommend looking up sub-pixel methods either online or in books.

DirectDraw - 4 - Lines Source code
JUMP TO - dd1 - dd2 - dd3 - dd4 - dd5 - dd6 - dd7