Bresenham for Dummies
I was just wondering if someone could give me a brief (or lengthy, if you want.. ) explanation of bresenham''s line algo, or a page that has one. I think I know whats going on, but I plan on adapting it for a ''shear'' effect for bitmaps, so I''d like to know exactly how it works.
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
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
CG : P & P.. I'll have to pick that up. The book I read (rental, so I couldn't go back and look at the line part) used bresenham for circles, elipses, etc, so I think it all got muddled up in my head. You helped clear it though, so thanks!
Edited by - A. Buza on October 5, 2000 1:14:19 PM
Edited by - A. Buza on October 5, 2000 1:14:19 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
Mike
Here's how I normally do Bresenham, if you want code:
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
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
Mike
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement