Line Drawing Algorithm Explained
by Tom Ootjers

Now I'm sure that of all of you who are reading this have drawn lines before, and some of you have probably even created a basic line drawing routine. If you attempted to do this on your own, without looking on the Internet for the help of the programming community, (as I did for my first line drawing procedure) you probably made a fairly inefficient algorithm that did the job, just not very quickly. Then, sooner or later, you heard about the Bresenham line algorithm. After trying it out you decided that this was the one you would be using from now on, and that was that. I however, couldn't stand not knowing how it worked, so before long I was attempting to figure out how the Bresenham algorithm was put together. After looking at a couple of lines, I began to see some strange patterns develop, and voila! I suddenly had the Bresenham algorithm all written out. Now I am going to let you in on that deepest of secrets (at least I think it's a secret, since I haven't seen anyone else explain his algorithm yet), and tell you how to draw lines using only integer values.

Before we begin however, we must ask ourselves the question, what is a line? Now in general a line is just 2 points that are connected. However, we are going to need to be a little more specific than that. Our lines must start on integer values (how else are we going to be using only integers?), and we only need to draw the points of the line that occur on integer values (since pixels only come in integer values, and we will be using pixels to display our line). For now we are going to limit ourselves to one type of line (there are 8 types in total), all the other types can be derived from this one as will be shown a little later. In this line of ours, the x and y of the first point are less than or equal to the x and y of the second point, and the difference in x's is greater than or equal to the difference in y's.

Now before we see how to draw lines using integers, we are going to discover how to do it using real numbers (decimal for all you non-mathematicians out there). First however, I am going to define a couple of terms. I will be referring to the coordinates of the first point as x1 and y1, and the coordinates of the second point (take a wild guess) as x2 and y2. The difference between the x's (x2 - x1) will be called deltax, and the difference between the y's (y2 - y1) will be called deltay. To draw our line we are going to be using the standard line formula y = mx + b, where x and y are the coordinates of the pixel, m is the slope (deltay / deltax) of the line, and b is 0. Actually, x and y aren't really the coordinates of the pixel, the pixel's true coordinates are x1 + x and y1 + y. Now, in order to find out what x-values need to be used in our equation, you need to recall that deltax is greater than or equal to deltay. This means that there is at least one x-value for every y-value (for everyone out there saying that there will be ONLY 1 x-value for every y-value since our equation generates a unique y-value for every x-value, when I say y-value I really mean ROUNDED y-value, since pixels only come on integer intervals), therefore the x-values that need to be used are 0 to deltax. Now here is some code to demonstrate what I've just been saying.

deltax = x2 - x1;                   // The difference in the x's
deltay = y2 - y1;                   // The difference in the y's
m = deltay / deltax;                // The slope of the line (with deltax > 0)
for (x = 0; x <= deltax; x++)
{
  y = m * x;                        // Calculate the y-value
  PutPixel(x + x1, round(y) + y1);  // Draw the current pixel
}

Now I would like you to note that since we are adding x1 to x for every x-value anyway, we might as well start the loop at x = x1, and go until x <= x2. Doing this would mess up the y-value however (different values would be used in our equation), so I suggest that since y is increasing by a fixed amount each time (namely m), we should start it off at y1, and then add m to it for every iteration through the loop. Here is the modified code.

deltax = x2 - x1;           // The difference in the x's
deltay = y2 - y1;           // The difference in the y's
m = deltay / deltax;        // The slope of the line (with deltax > 0)
y = y1;                     // Start y off at the first pixel value
for (x = x1; x <= x2; x++)
{
  PutPixel(x, round(y));    // Draw the current pixel
  y += m;                   // Calculate the next y-value
}

Now that everybody knows how to draw lines using real numbers, we can move on to drawing lines using integers. Now if you will note that m is a fraction (deltay / deltax), and that when you add two fractions together you add the numerators (the top), while the denominators (the bottom) stay constant. Also, when the numerator becomes greater than or equal to the denominator, you subtract the denominator from the numerator and increase the number in front of the fraction by one. Using this method you can use integers rather than decimals by keeping track of the numerator for the y, and adding deltay (the top part of m) to it for each iteration of the loop, checking if it is greater than deltax (the bottom part of m) and decreasing it by deltax while increasing the current y by one if it is. Now this will work fine except for one slight problem, the y's will be rounded at every whole number rather than at the halfway point.

To correct this you can start the numerator off at half the denominator (deltax). Now if you are very observant (and realize that at this point we are no longer using decimal numbers), you may be saying that this will work fine when deltax is an even number, but when it is odd we will be truncating the decimal place. Well that is correct, but it turns out that it doesn't matter. If you think about it for a second you will realize that since we will be comparing the numerator to a whole number value (deltax), it doesn't matter if we don't include the decimal. Now that you are all scratching your heads, wondering what the heck I'm talking about, I'll give you some code to look at (hopefully it will help you to figure it out).

deltax = x2 - x1;           // The difference in the x's
deltay = y2 - y1;           // The difference in the y's
y = y1;                     // Start y off at the first pixel value
ynum = deltax / 2;          // The starting value for the numerator
for (x = x1; x <= x2; x++)
{
  PutPixel(x, y);           // Draw the current pixel
  ynum += deltay;           // Increase the numerator by the top of the fraction
  if (ynum >= deltax)       // Check if numerator >= denominator
  {
    ynum -= deltax;         // Calculate the new numerator value
    y++;                    // Increase the value in front of the numerator (y)
  }
}

And now you know how to draw lines! What's that? You want me to explain how to draw the other 7 types of lines as well? I suppose I did say that I would explain it, so here goes nothing. The following table divides the lines into the various types. As you can see, they are all very similar.

y = y1;
ynum = deltax / 2;
for (x = x1; x <= x2; x++)
{
  PutPixel(x, y);
  ynum += deltay;
  if (ynum >= deltax)
  {
    ynum -= deltax;
    y++;
  }
}

x = x1;
xnum = deltay / 2;
for (y = y1; y <= y2; y++)
{
  PutPixel(x, y);
  xnum += deltax;
  if (xnum >= deltay)
  {
    xnum -= deltay;
    x++;
  }
}

y = y1;
ynum = -deltax / 2;
for (x = x1; x >= x2; x--)
{
  PutPixel(x, y);
  ynum += deltay;
  if (ynum >= -deltax)
  {
    ynum -= -deltax;
    y++;
  }
}

x = x1;
xnum = deltay / 2;
for (y = y1; y <= y2; y++)
{
  PutPixel(x, y);
  xnum += -deltax;
  if (xnum >= deltay)
  {
     xnum -= deltay;
     x--;
  }
}

y = y1;
ynum = deltax / 2;
for (x = x1; x <= x2; x++)
{
  PutPixel(x, y);
  ynum += -deltay;
  if (ynum >= deltax)
  {
    ynum -= deltax;
    y--;
  }
}

x = x1;
xnum = -deltay / 2;
for (y = y1; y >= y2; y--)
{
  PutPixel(x, y);
  xnum += deltax;
  if (xnum >= -deltay)
  {
    xnum -= -deltay;
    x++;
  }
}

y = y1;
ynum = -deltax / 2;
for (x = x1; x >= x2; x--)
{
  PutPixel(x, y);
  ynum += -deltay;
  if (ynum >= -deltax)
  {
    ynum -= -deltax;
    y--;
  }
}

x = x1;
xnum = -deltay / 2;
for (y = y1; y >= y2; y--)
{
  PutPixel(x, y);
  xnum += -deltax;
  if (xnum >= -deltay)
  {
    xnum -= -deltay;
    x--;
  }
}

Since the 8 line types are all very similar, we can make a generic line routine that will be able to draw all 8 types. Here is the code.

deltax = abs(x2 - x1);        // The difference between the x's
deltay = abs(y2 - y1);        // The difference between the y's
x = x1;                       // Start x off at the first pixel
y = y1;                       // Start y off at the first pixel

if (x2 >= x1)                 // The x-values are increasing
{
  xinc1 = 1;
  xinc2 = 1;
}
else                          // The x-values are decreasing
{
  xinc1 = -1;
  xinc2 = -1
}

if (y2 >= y1)                 // The y-values are increasing
{
  yinc1 = 1;
  yinc2 = 1;
}
else                          // The y-values are decreasing
{
  yinc1 = -1;
  yinc2 = -1;
}

if (deltax >= deltay)         // There is at least one x-value for every y-value
{
  xinc1 = 0;                  // Don't change the x when numerator >= denominator
  yinc2 = 0;                  // Don't change the y for every iteration
  den = deltax;
  num = deltax / 2;
  numadd = deltay;
  numpixels = deltax;         // There are more x-values than y-values
}
else                          // There is at least one y-value for every x-value
{
  xinc2 = 0;                  // Don't change the x for every iteration
  yinc1 = 0;                  // Don't change the y when numerator >= denominator
  den = deltay;
  num = deltay / 2;
  numadd = deltax;
  numpixels = deltay;         // There are more y-values than x-values
}

for (curpixel = 0; curpixel <= numpixels; curpixel++)
{
  PutPixel(x, y);             // Draw the current pixel
  num += numadd;              // Increase the numerator by the top of the fraction
  if (num >= den)             // Check if numerator >= denominator
  {
    num -= den;               // Calculate the new numerator value
    x += xinc1;               // Change the x as appropriate
    y += yinc1;               // Change the y as appropriate
  }
  x += xinc2;                 // Change the x as appropriate
  y += yinc2;                 // Change the y as appropriate
}

And there you have it. You now know how to draw lines using only integer values. Now you may have noticed that I don't do any checking to make sure that the line is showing on the screen, This will be slightly different for different resolutions, and it doesn't have anything to do with the actual line drawing, so I didn't include it. Once you put that in however, you will have a fully functional line drawing routine. And now you know how and why the Bresenham line algorithm works.

Discuss this article in the forums

Date this article was posted to GameDev.net: 1/7/2001
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Algorithms and Data Structures
Sweet Snippets

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!