Jump to content
  • Advertisement

Archived

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

baskuenen

Is Bresenham's Line Algorithm acurate?

This topic is 6916 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

Advertisement
I''m not sure that I know what you mean. Since drawing a line on a screen is the process of taking a continuous linear function and rasterizing it to discrete pixels, I would have to say that there aren''t ANY 100% accurate line algorithms.

Now, if you mean something like does drawing from point A to point B color in the exact same pixels as drawing from point B to point A, well, that''s an implementation issue most likely.

Maybe you can be a little bit more specific? Or maybe someone else already knows what you mean and will answer that question for you.

Share this post


Link to post
Share on other sites
Currently I''m drawing my polygons with a linear interpolation using a divide as pre-calc.

Implementation pseudo:
Xdelta = Xbottom-Xtop
Ydelta = Ybottom-Ytop
Xinterpolate = Xdelta/YDelta
Xpos = Xtop
do
{
DrawHorizontalLine...
Xpos += Xinterpolate
}
while(Ydelta--);

Maybe this question is better:
Does the Bresenham algo produce the exact same line as the simple linear implementation?

Share this post


Link to post
Share on other sites
I was always under the impression Bresenham produces other results as other line drawing algo''s.
I''m beginning to get doubts...

Share this post


Link to post
Share on other sites
Actually the Bresenham method works better than your psuedo-code, as yours won''t work for a vertical line, but that''s being a little too picky...

The beauty of the algorithm is that it is completely accurate and only uses integer addition, which is much faster than using floating point divisons (especially when the algorithm was written).

Share this post


Link to post
Share on other sites
In essence Bresenham''s algorithm is the same as your floating point method. Instead of using the x_delta over y_delta as an increment, it uses the number of 1 over y_delta fractions as an increment. (Actually 1 over 2 * y_delta because of rounding on 1/2 instead of chopping.) Considering it doesn''t suffer from floating point error, it''s arguable that Bresenham is *more* accurate than floating point methods.

Share this post


Link to post
Share on other sites
Oke you talked me into it...Bresenham will be implemented...
But here''s the logical next question:

Why not use Bresenham for all your interpolations?

Share this post


Link to post
Share on other sites
Because Bresenham works on the very specific case that you are mapping floating point values with integer endpoints onto integer values over all the values in a range at fixed intervals. In most types of interpolations, at least one of these restrictions is violated.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!