• ### Announcements

#### Archived

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

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

Mike

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

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 on other sites
WhoopA - if you initilize error to ydelta/2, instead of zero, you force rounding, makes a slightly more exact line...

Mike

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627658
• Total Posts
2978484

• 10
• 12
• 22
• 13
• 33