Archived

This topic is now archived and is closed to further replies.

A. Buza

Bresenham for Dummies

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
WhoopA - if you initilize error to ydelta/2, instead of zero, you force rounding, makes a slightly more exact line...


Mike

Share this post


Link to post
Share on other sites