2D Line Technique Examined

code last updated: 4-21-97
last updated: 5-9-97

Drawing a line is easy because it follows a simple formula: y = m * x + b. If we take the derivative of that in respect to x, we get dy/dx = m. (I'm not going to go over the fundamentals of derivatives in Calculus, so if you don't know what a derivative is, think of it as the slope of a function at a given point. Notice that the derivative of a line is its slope because it has the same slope at every value of x.)

Because we are interested in only dealing with adding, subtracting, and very minimal (if any) multiplication and division when we try to make computer algorithms to draw shapes, I'll update the formula of the line. Instead of just a slope m, we'll have mn (m numerator) and md (m denominator). Now m = mn / md, and we have a new equation of the line: y = (mn / md) * x + b. Also don't forget that m = mn / md = (y1 - y2) / (x1 - x2). This means that mn = y1 - y2 when md = x1 - x2.

To give a reason for our interest in avoiding multiplication and division, I'll quote some cycle counts for addition, subtraction, multiplication, and division operations (in integer mode between two registers) on an Intel 80486 (the name Intel is a registered trademark of Intel Corp.). I obtained these values from theTurbo Assembler Quick Reference Guide by Borland International, Copyright 1991.

The signed versions of multiply and divide can take even more cycles to be computed (surprisingly it looks like IMUL can take substantially longer and IDIV only adds about 4 cycles). MUL takes even longer when involves memory which makes it comparable to the DIV number of cycles. This is why multiply and divide, if possible, are painstakenly weeded out of any fast algorithm.

Another interest we have in making fast algorithms is memory access, but I don't have any numbers of cycles per memory access to look at. It's probably a rule of thumb that as your microprocessor becomes faster, the memory takes more cycles of processor time to be read (unless it is at a similar clock speed as the microprocessor - cache memory).

In our equation of the line, let's suspect that we will be moving across and down. We have three constants b, mb, and mn, and two variables x and y. Doing some algebra, we can find the following:

With our new equation, we notice that the difference of md * y and mn * x, which are both proportional two one of the variables without any additional constants, is equal to a constant. If we take the derivative of our new function, we get the following:

From this we can see what we need to draw a line starting from a given point, because this equation gives us the slope of the line in respect to x and y. For every x we move across, we'll have to balance it with a certain number of ys so that everything is balances around zero.

A good plan at this point is to start on an algorithm to draw a line. I'll write it in C++ because that's the language I use. Before you gripe about the size of the code, it is mostly whitespace and comments which I'm sure you'll appreciate because it makes it easier to read.

void DrawLine(int x1, int y1, int x2, int y2)
   {
   int mn, md;
   int x_move, y_move;
   int x_position, y_position;
   int balance;

   md = x2 - x1;   // Find md.
   if (md < 0)     // If it is negative,
      {
      md = -md;    // Make md positive.
      x_move = -1; // Make x move in a negative direction.
      }
   else            // else
      {
      x_move = 1;  // Make x move in a positive direction.
      }

   mn = y2 - y1;   // Find mn.
   if (mn < 0)     // If it is negative,
      {
      mn = -mn;    // Make mn positive.
      y_move = -1; // Make y move in a negative direction.
      }
   else
      {
      y_move = 1;  // Make y move in a positive direction.
      } 

   x_position = x1;  // Set the starting x position.
   y_position = y1;  // Set the starting y position.

   if (mn < md)          // If the x grows faster than y.
      {
      balance = md;      // Set the balance as positive md.
      }
   else                  // Else
      {
      balance = -(mn);   // Set the balance as negative mn.
      }

   mn = 2 * mn;   // Double mn and md which is the equivalent
   md = 2 * md;   //     of halving balance.

   // While not at the last x and y position, go...
   while ((x_position != x2) || (y_position != y2))
      {
      DrawPointAt(x_position, y_position);   // Draw the point.

      if (balance < 0)  // If the balance leans toward x...
         {
         balance = balance + md;           // Balance x with y.
         y_position = y_position + y_move; // Move y in the correct direction. 
         }

      // Putting this here insures x gets a chance to move each time.
      if (balance >= 0)  // If the balance leans toward y...
         {
         balance = balance - mn;           // Balance y with x.
         x_position = x_position + x_move; // Move x in the correct direction.
         }
      }
   DrawPointAt(x_position, y_position);   // Draw the last point.
   }

Okay, now let's go through this in chunks so that you can see how this algorithm is relatively fast (it can be optimized, but I'll leave that for you to do). The first group of commands defines md which I'll call the y balancing factor and makes sure it is positive and that x will be moving in the correct direction. The second group of commands defines mn which I'll call the x balancing factor and makes sure it is positive and that y will be moving in the correct direction.

The third group defines the starting position. The fourth group takes the largest and most dominant balancing factor and makes it the starting balance. (Notice that I make the y balancing factor positive and x balancing factor negative because each one will be competing, trying to keep balance at zero.) I then multiply md and mn by two as an equivalent for dividing the balancing factor by two. (I used to divide the balancing factor by 2, but that became scary since you could loose some information in the least significant bit.)

Now we enter the loop which continues until we reach the final point. First we draw the point at the position we are at, then change the balance and position as necessary. Think of the x and y as competing forces and when x is in power, y trys to restore balance and moves. Likewise, when y is in power, x trys to restore balance and moves. At the end of the loop we draw the last point (otherwise it gets omitted).

After examining the code, you'll probably see the multiplication and say, "Ah! Ha! I see a place where we can remove quite a few cycles! You made a big mistake!" That's not really a BIG mistake, I meant to do it so the line might look more balanced. Actually we could take those out (I confess), but they translate into shift one bit to the left which only takes at most 3 cycles on the Intel 80486. Hmmm, I didn't realize that before, maybe they would be best left out... that is more than 1 cycle, but I'll let you decide whether to leave them in or not.

I've tested this algorithm and saw that it worked. If you have any questions or problems, please contact me so that I can either fix or clarify something.


joshuacantrell@yahoo.com

(My Home Page) - (My Personal Page) - (My Computer Science Page) - (My Resume)