On Sat, 23 Oct 1999 09:03:57 -0700, mark hahn <hahndo@teleport.com>
wrote:

>I went through looking for this kind of thing a few years ago. Now that
>most graphic cards support line drawing, polygon drawing, etc. trying to
>find the algorithm for something simple can be pretty frustrating. You
>want to look in older (pre 1985 or so) computer graphics textbooks. The
>algorithm you want for line drawing is called Breshenham's (spelling
>probably wrong).
>
>There are also a couple of older Microsoft Press books on the EGA card
>that have decent C source for that sort of thing.

There's a whole class of algorithms, sometimes referred to as digital
differential analysers (DDA).  These algorithms do some apriori
analysis to model how to calculate successive points by adding
increments to their x and y components, proportional to their rates of
change.  Sounds worse than it often is, but these algorithms are great
for lines, circles, and ellipses in cases where floating point
calculations are expensive to perform.

The line has a general form of an equation:

  1)    y = m*x + b

In graphing lines, though, you are usually presented with (x1,y1) and
(x2,y2).  So, let's do the computations in those terms.  'm' is the
slope of the line,

  1a)   m = (y2-y1) / (x2-x1)
  1b)   b = y1-m*x1 = y1 - x1*[(y2-y1)/(x2-x1)]

The tricky viewpoint in a DDA is to rewrite equation 1 into a slighly
different form:

  2)    0 = F(x,y) = P*x + Q*y + R

In this case, we've defined a new function, F(x,y), which is always
zero for all values of x and y that are on the line, y=m*x+b.  I think
you can figure out that in comparing these two equations, you'd find
that P=m, Q=-1, and R=b.  Let's substitute:

  3)    0 = F(x,y)
         = [(y2-y1)/(x2-x1)]*x - y + y1 - x1*[(y2-y1)/(x2-x1)]
         = [(y2-y1)/(x2-x1)]*x - (y-y1) - x1*[(y2-y1)/(x2-x1)]

For fancy integer computations, it would be handy if those nasty
divisors were removed.  So multiply both sides by (x2-x1) and get:

  4)    (x2-x1)* 0 = (x2-x1) * F(x,y) = f(x,y)
        0 = (y2-y1)*x - (y-y1)*(x2-x1) - x1*(y2-y1)

Notice that we have a new function, f(x,y), which is still always
equal to zero when the point, (x,y), is on the line.  It's just that
the positive and negative values computed for points that are not
exactly on the line now have a different magnitude, but still have the
same sign as before.  In other words, SGN(f(x,y)) = SGN(F(x,y)).

Now let's attempt to reorganize equation 4 back into the form found in
equation 2.

  5)    0 = f(x,y) = p*x + q*y + r
         = (y2-y1)*x - (y-y1)*(x2-x1) - x1*(y2-y1)
         = [y2-y1]*x + [-1*(x2-x1)]*y + [(x2-x1)*y1 + -1*x1*(y2-y1)]

thus,

  6a)   0 = f(x,y) = p*x + q*y + r, where:
          dx = x2 - x1
          dy = y2 - y1
          p = dy
          q = -dx
          r = dx*y1 - dy*x1
  6b)   0 = f(x,y) = (x-x1)*dy - (y-y1)*dx

Now, it's what happens when the values of x and y happen to fall off
of the line that makes this method interesting.  (Keep in mind that
the same kind of thing can be written for circles, too.)

In the above form, f(x,y) is zero at any point on the line, positive
at any point below the line, and negative at any point above it.  You
should be able to intuitively see this by noticing that in the second
equation, where q=-1, larger y values will cause the equation to "go
more negative."  If you imagine that (x,y) is sitting exactly on the
line and f(x,y) is exactly zero there, then if you move the point off
of the line slowly in the positive Y direction (to the region "above"
the line), then the equation will tend in the negative direction.
Above is negative, below is positive, zero is right on.

Okay.  Time for a diversion from DDA, so you can take a closer look at
lines.  You need to see why they tend to fall into two different
groups, since you'll need to write two algorithms...

So, let's say you are starting at a point, (x1,y1), and proceeding on
a digitized plane to another point, (x2,y2).  You can, of course, know
that you will need to plot (x1,y1) and (x2,y2), but what should you do
with the points in between?  Well, you know that the x values will
proceed smoothly from x1 to x2 and that the y values will proceed
smoothly from y1 to y2.  Let's look at two sample lines.  (Assume you
are proceeding from x1=2 to x2=5, in both cases.)

  7a)   y = 10 * x
  7b)   y = x / 2

In 7a, you'd plot (2,20), then if you added 1 to x, giving 3, you'd
plot (3,30).  But what about all the points in between???  This is a
steep line, driving rapidly higher in the Y direction, and just
plotting (2,20), (3,30), (4,40), might look good from a distance but
it looks really sparse on a screen!  In order to fill out the points
in between, you'd need to work it from the "other side of the street"
and change from y1=20 to y2=50, by ones.  In this case, you'd compute
(2,20), (2.1, 21), (2.2, 22), and so on.  Although you'd need to round
the x values, at least you'd then get a series of points that would
make a more reasonable line!

In 7b, the situation is the opposite.  Here, it's just fine to go from
(2,1), (3, 1.5), (4, 2), and then to (5, 2.5).  This is because the
slope of the line is much more gentle.

So, you can divy up lines into two types:  lines with slopes who's
absolute values are greater than one, where ABS(y2-y1) > ABS(x2-x1),
and lines with slopes less than one, where ABS(y2-y1) < ABS(x2-x1).
Naturally, there are also lines with slopes = 1 or -1, but these can
be handled either way.  Your choice.

Back to the DDA...

Ok.  Now let's take a look at those lines where 0 < (y2-y1) < (x2-x1),
or where the slope is between 0 and 1.  Doing so will keep us focused
on one managable case.  We can generalize later.  Remember that the
following discussion is about a line with a gently positive slope!

You plot your first point on the line as (x1,y1) and then you must
decide between plotting the next point at (x1+1,y1) and (x1+1,y1+1).
Which one you pick depends on whether or not the value of the line at
x=x1+1 is closer to y1 or y1+1.

What is needed now is an equation that will help you decide, at each
step, what action to take to get to the next step.  Take a look at:

  8)    g(x,y) = f(x+1,y+1/2)

Do you see why this equation might help?  What this equation asks is,
"What is the value of the line, f(x,y), at the next x value and
halfway between the current value of y and y+1?"  If this hypothetical
halfway point is below the true line, then the value of g(x,y) will be
positive.  (Remember that the equation is positive for points below.)
If it is above the line, then the value of g(x,y) will be negative.
(Remember that the equation is negative for points above.)  So, if
g(x,y) is negative you choose (x1+1,y1) as the next point to plot and
if it is positive you choose (x1+1,y1+1).

Make sure you understand that clearly before going on.  (It might
really help to have some graph paper handy and to draw some line on it
and work this by hand.)  Now, one more big step and we are home free.

Let's imagine that we don't want to calculate f(x,y) or g(x,y).  If
anything, both these equations are actually worse than just computing
y from equation 1 and all I've done so far is make things more
confusing and harder, not easier.

Okay.  So let's create an integer variable called 'g'.  This variable
will always be the value of current value of g(x,y).  We will need to
compute a new value for 'g' at each step.  The big question is:  "How
much do we add or subtract from 'g' after moving from x1 to x1+1, and
so on?"

Ah!!  Now we have a question that we can solve.  Let's see where that
goes:

  9a)   if next point is (x+1,y) then g = g + (g(x+1,y)-g(x,y))
  9b)   if next point is (x+1,y+1) then g = g + (g(x+1,y+1)-g(x,y))

or,

 10a)   if g < 0 then g = g + (g(x+1,y)-g(x,y))
 10b)   if g >= 0 then g = g + (g(x+1,y+1)-g(x,y))

So, just compute the two parts (remember to look back to equation 6a
and 6b to find out the values of 'p' and 'q'):

 11a)   g(x+1,y)-g(x,y)
         = f(x+2,y+.5)-f(x+1,y+.5)
         = [p*(x+2) + q*(y+.5) + r]-[p*(x+1) + q*(y+.5) + r]
         = [p*(x+2) - p*(x+1)] + [q*(y+.5) - q*(y+.5)] + [r - r]
         = p*[(x+2) - (x+1)] + 0 + 0
         = p*[(x - x) + (2 - 1)]
         = p*[0 + 1]
         = p
         = dy
 11b)   g(x+1,y+1)-g(x,y)
         = f(x+2,y+1.5)-f(x+1,y+.5)
         = [p*(x+2) + q*(y+1.5) + r]-[p*(x+1) + q*(y+.5) + r]
         = [p*(x+2) - p*(x+1)] + [q*(y+1.5) - q*(y+.5)] + [r - r]
         = p*[(x+2) - (x+1)] + q*[(y+1.5) - (y+.5)] + 0
         = p*[(x - x) + (2 - 1)] + q*[(y - y) + (1.5 - .5)]
         = p*[0 + 1] + q*[0 + 1]
         = p + q
         = dy - dx

If you look at 'g' and decide to plot (x+1,y), then add (dy) to 'g' to
get the next 'g'.  If you look at 'g' and decide to plot (x+1,y+1),
then add (dy-dx) to 'g' to get the next 'g'.

Whoops!  What is the initial value for 'g'?  Well, the starting value
for 'g' is just g(x1,y1).  (We'll need to refer back to equation 6 for
more information, too:)

 12)    g(x1,y1) = f(x1+1,y1+.5)
         = (x1+1-x1)*dy - (y1+.5-y1)*dx
         = dy - .5*dx

Oh, oh!  The .5 in that initial value is a bad thing.  So go back and
multiply everything by 2.  (This won't hurt our purposes, because we
are only testing our decision variable, 'g', for positive or negative,
not for any particular value.  2 times a positive number is still
positive, 2 times a negative number is still negative.)

So the initial value of 'g' will be (2*dy-dx) and when you look at 'g'
and decide to plot (x+1,y), add 2*(dy) to 'g' to get the next 'g' and
when you look at 'g' and decide to plot (x+1,y+1), then add 2*(dy-dx)
to 'g' to get the next 'g'.

All the above was designed for slopes between 0 and 1.  We've made
some assumptions that won't be true for all possible lines.  You will
need to make some small adjustments to cover all the bases.  These
gentle-sloped lines used x as the independent variable.  For the steep
slopes, you need to use y as the independent variable.  This means
that your line drawing algorithm will break down into two basic
routines, one for x as the independent and one for y as the
independent.  You may also want to handle special cases for vertical
and horizontal lines, and possibly even lines with slopes of exactly 1
and -1.

Jon

------------------

Subject: Re: Line drawing routines for embedded lcd control.
Date: Mon, 25 Oct 1999 11:04:03 +0200
From: "David Brown" <david.nospam@westcontrol.com>
Organization: NetPower Int AS
Newsgroups: comp.arch.embedded

You're going to have to do some work (and thinking :-) to turn this into
C-code, but this is exactly the way to do generalized line drawing.  I
implemented the same algorithm myself in assembly, many years ago.

A couple of extra little hints - optomize special cases, such as horizontal
and vertical lines.  It might also be worth thinking about extensions, such
as wide or dotted lines.  There are some code complexity / code size / run
time tradeoffs from taking advantage of up to 8-way symmetries.

And once you have thuroughly understood Jon's excellent explanation, you
might like to adapt it to draw circles :-)

For the really keen, a good book is "Computer Graphics: Principles and
Practice" (Addison Wesly), by Foley, vanDam, Feiner and Hughes.  I think it
is in its third edition now.  It starts off with the anamoty of the eye, and
works right through to state-of-the-art ray tracing.

David Brown

--------------------

Subject: Re: Line drawing routines for embedded lcd control.
Date: Mon, 25 Oct 1999 08:58:18 -0700
From: Jon Kirwan <jkirwan@easystreet.com>
Organization: New World Computing Services
Newsgroups: comp.arch.embedded

On Mon, 25 Oct 1999 11:04:03 +0200, "David Brown"
<david.nospam@westcontrol.com> wrote:

>You're going to have to do some work (and thinking :-) to turn this into
>C-code, but this is exactly the way to do generalized line drawing.  I
>implemented the same algorithm myself in assembly, many years ago.

I didn't want to just write the routine, here.  It's far better to
understand it and to be able to apply it in new situations.  But yup,
it will take a bit of thinking still.  However, far and away, I did
the lions share of it in the post.  What's left, in terms of
implementation is a piece of cake, really.

>A couple of extra little hints - optomize special cases, such as horizontal
>and vertical lines.

Hehe.  I even said as much in the last paragraph of my post, saying,
"You may also want to handle special cases for vertical and horizontal
lines, and possibly even lines with slopes of exactly 1 and -1."

>It might also be worth thinking about extensions, such
>as wide or dotted lines.  There are some code complexity / code size / run
>time tradeoffs from taking advantage of up to 8-way symmetries.

Yup!  Good points.

>>And once you have thuroughly understood Jon's excellent explanation, you
>might like to adapt it to draw circles :-)

Exactly!  Adapting it to circles is pretty easy, all things
considered.  Symmetry about the 45-degree lines allow 8-way drawing,
so all you need to do is develop one octant's code and just plot the
various +/- combinations.  It's unrotated ellipse code (4-way only, so
more code), rotated ellipses and the generalized conic equation,
instead, or handling "start and stop" points on a conic, that makes
this stuff really tedious.

>For the really keen, a good book is "Computer Graphics: Principles and
>Practice" (Addison Wesly), by Foley, vanDam, Feiner and Hughes.  I think it
>is in its third edition now.  It starts off with the anamoty of the eye,
and
>works right through to state-of-the-art ray tracing.

Haven't read it, myself.  I do plan to buy it soon, though.  I've read
from a few that there are a few mistakes, but that it is an excellent
resource.  I derived my own set of equations from just seeing an
overview of the approach and that was enough of a hint to deduce the
rest.  (Kind of like, "Wow!  I get it, now.  Cripes that's neat.  Hmm.
Let me think about this...."  It's one of those wonderful little
puzzles with practical applications.)

Jon

-------------------

Subject: Re: Line drawing routines for embedded lcd control.
Date: Mon, 25 Oct 1999 19:13:50 +0200
From: "David Brown" <david.nospam@westcontrol.com>
Organization: NetPower Int AS
Newsgroups: comp.arch.embedded

Jon Kirwan wrote in message ...
>On Mon, 25 Oct 1999 11:04:03 +0200, "David Brown"
><david.nospam@westcontrol.com> wrote:
>
>>You're going to have to do some work (and thinking :-) to turn this into
>>C-code, but this is exactly the way to do generalized line drawing.  I
>>implemented the same algorithm myself in assembly, many years ago.
>
>I didn't want to just write the routine, here.  It's far better to
>understand it and to be able to apply it in new situations.  But yup,
>it will take a bit of thinking still.  However, far and away, I did
>the lions share of it in the post.  What's left, in terms of
>implementation is a piece of cake, really.

I actually ment "you" as in the original poster - you (Jon) have done the
thinking, so there Ken can do the coding himself.

>
>>A couple of extra little hints - optomize special cases, such as
horizontal
>>and vertical lines.
>
>Hehe.  I even said as much in the last paragraph of my post, saying,
>"You may also want to handle special cases for vertical and horizontal
>lines, and possibly even lines with slopes of exactly 1 and -1."
>

Whoops, so you did.  Clearly it is an important point.

>>It might also be worth thinking about extensions, such
>>as wide or dotted lines.  There are some code complexity / code size / run
>>time tradeoffs from taking advantage of up to 8-way symmetries.
>
>Yup!  Good points.
>
>>>And once you have thuroughly understood Jon's excellent explanation, you
>>might like to adapt it to draw circles :-)
>
>Exactly!  Adapting it to circles is pretty easy, all things
>considered.  Symmetry about the 45-degree lines allow 8-way drawing,
>so all you need to do is develop one octant's code and just plot the
>various +/- combinations.  It's unrotated ellipse code (4-way only, so
>more code), rotated ellipses and the generalized conic equation,
>instead, or handling "start and stop" points on a conic, that makes
>this stuff really tedious.

I derived the code for circles once, but I seem to remember there was no
simple way to extend the algorithm to ellipses or general conics.  In the
particular application, it turned out that even circle drawing was too slow
and was not really necessary on the screen, so I had to give up writing a
complete graphic library and do some real work.

>
>>For the really keen, a good book is "Computer Graphics: Principles and
>>Practice" (Addison Wesly), by Foley, vanDam, Feiner and Hughes.  I think
it
>>is in its third edition now.  It starts off with the anamoty of the eye,
and
>>works right through to state-of-the-art ray tracing.
>
>Haven't read it, myself.  I do plan to buy it soon, though.  I've read
>from a few that there are a few mistakes, but that it is an excellent
>resource.  I derived my own set of equations from just seeing an
>overview of the approach and that was enough of a hint to deduce the
>rest.  (Kind of like, "Wow!  I get it, now.  Cripes that's neat.  Hmm.
>Let me think about this...."  It's one of those wonderful little
>puzzles with practical applications.)
>
>Jon
>
It's a good book.  It was the official reference for the Computer Graphics
course I had as part of my university degree.  The computation deparment
there are very fussy about their books, so it is good stuff.

---------------------

Subject: Re: Line drawing routines for embedded lcd control.
Date: Mon, 25 Oct 1999 11:44:26 -0700
From: Jon Kirwan <jkirwan@easystreet.com>
Organization: New World Computing Services
Newsgroups: comp.arch.embedded

On Mon, 25 Oct 1999 19:13:50 +0200, "David Brown"
<david.nospam@westcontrol.com> wrote:

>I derived the code for circles once, but I seem to remember there was no
>simple way to extend the algorithm to ellipses or general conics.

Ellipses, unrotated, are really pretty easy.  You just can't depend on
the fact that the slopes from 0 to 45 degrees are a mirror of the
slopes from 45 to 90 degrees, though, as you can in the case of a
circle.  Normally, in the circle code, you can use x as the
independent variable for the 45 to 90 degree part of the curve and
just reflect the computations about the 45 degree line to achieve the
0 to 45 degree part of it, without new code.  Additional obvious
reflections get you the other quadrants.  But in the unrotated
ellipse, the part of the curve that belongs to slopes from 0 to 1
(using x as the independent variable) doesn't span from 90 degrees
over to 45 degrees.  It either ends earlier or later than that,
depending on which is the major axis.  This means you need to divide
the first quadrant into two distinct bits of code, one where x is
independent and one where y is independent, and figure out where one
ends and the other begins.  The other three quadrants, though, can be
just symmetrical reflections.  So you need twice the code plus a bit
for the ellipse vs the circle.  Pretty fast, though.

>In the particular application, it turned out that even circle drawing
>was too slow and was not really necessary on the screen, so I had to
>give up writing a complete graphic library and do some real work.

Hehe.  Real world is always a bit less than optimal, isn't it?  Of
course, if you are programming for the newer PPro Family of CPUs, such
as the P II and P III, the floating point is "real fast."  But for
slow, 8-bit and 16-bit integer jobs, DDA is the way to go.

Jon