**2D Line Technique Examined**

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.

**ADD takes 1 cycle (for 8, 16, and 32 bits)****SUB takes 1 cycle (for 8, 16, and 32 bits)****MUL takes 13 cycles (for 8, 16, and 32 bits)****DIV takes 16 (for 8 bits), 24 (for 16 bits), and 40 (for 32 bits)**

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:

*y = (mn / md) * x + b*

*(md * y) = (mn * x) + (b * md)*

*(md * y) - (mn * x) = (b * md)*

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:

*(d/dx)(md * y) - (d/dx)(mn * x)= 0*

*md * (dy/dx) - mn = 0*

*md * dy - mn * dx = 0*

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 *y*s 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.

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