I found the explanation in Computer Graphics: Princepals and Practice very good...it derives the whole thing. It's a bit long for me to type in here though...
The basic idea is to keep the error as a fraction, so when the nominator becomes larger than the denominator (the value is then greater than one), another incrementation is necessary.

You need both cases seperate, where dx > dy and dx < dy, but the cases are reflective. so where dx < dy, then we know that y increments by one exactly, but x may or may not. If we were not doing Brensham's alg, then we would increment x by dx/dy every increment of y. But, in order to keep all integers, we never do the division. Instead, we create a varible called 'error'. Add to this error dx every y increment, and when it is greater than dy, it's time to add 1 to x, and subtract dy from the error. Hope that helps...it may not be Brensham's exactly but it is an incremental line algorithm very similar.


Mike

Edited by - Vetinari on October 4, 2000 11:17:39 PM

computer graphics principles and practice is a good book but a bit pricey I got it on sale about a year ago for 95$ US

I got it on ebay for $31 + $3 shipping, in very good condition. There is usually a copy up every week or so. Or it''s $70 at amazon.


Mike

Here's how I normally do Bresenham, if you want code:

    void BLine (int x1, int y1, int x2, int y2, int color){  int error;  // Error term  int xdelta, ydelta;  // Rise and run  int xpel, ypel;  // Current pixel to plot// Determine slope of line  xdelta = x2 - x1;  ydelta = y2 - y1;  error = 0; xpel = x1; ypel = y1;// More vertical than horizontal slope - that is, rise is more// than run  if (ydelta > xdelta) {    while (ypel <= y2) {      putpixel (xpel,ypel,color);  // Generic plotting function      ypel++;      error += xdelta;  // Add the run to each pixel      if (error >= ydelta) {  // Overflow handling        error -= ydelta;        xpel++;      }    }  } else {// .// . Same as other block, only flip your x's and y's// .  }}    

That should do it. Just for reference, there's no range checking, and x1 and y1 MUST be less than x2 and y2 for it to work.

How I figure overflow is this: Lets have a line from say, (50,50) to (100,150). That makes the slope 1/2. So, we add 1 to the error term and move down 1 (inc. Y by 1). If the error overflows (that is, equals 2) we correct it and move right 1.

... I hope I wasn't confusing

EDIT: I used the wrong tags for the source code.

WhoopA, the Official Kicker of Butts

--- Home Page, visit at your own risk!
The future is not set. There is no fate, but what we make of ourselves.
Everywhere I look, I see rabbits. Maybe I should take down all my Sailor Moon stuff.

Edited by - WhoopA on October 4, 2000 12:58:01 AM

WhoopA - if you initilize error to ydelta/2, instead of zero, you force rounding, makes a slightly more exact line...


Mike