Tags bresenham, line, algorithm Bresenham's Line Drawing Algorithm 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.
This is the Bresenham's line algorithm represented by a visual diagram explaining precision of the actual line vs. the pixels representation of the line, and the problem at hand.
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.
Chat group
Discord
Support