Jump to content
  • Advertisement

Archived

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

A. Buza

Bresenham for Dummies

This topic is 6493 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!