FreeLists / openbeos / [openbeos] Re: The Scientific Method aka Bresenham NewsletterArticle

[Michael Noisternig <michael.noisternig@xxxxxxxxx>]

Martin Krastev wrote:
> "Michael Noisternig" <michael.noisternig@xxxxxxxxx> wrote:
>
> [snip]
>
> > The slope 
> > computed by your slope version is quite likely to have an infinite 
> > number of digits, so you already have 1/4 the size of the number 
> > consisting of only the least significant bit as error in average. By 
> > adding the slope in every iteration that error gets accumulated and 
> > there is quite likely to be a case (with not huge line endpoints) were 
> > the total error of the line drawn is bigger than in Bresenham's 
> > algorithm (that means the line is off from the correct one by at least 1 
> > pixel).
> > So the correct way would be to re-compute the other coordinate in every 
> > iteration, e.g. y = y1 + (y2-y1)*x/(x2-x1). Now by that way you also 
> > have very few instructions every iteration but the division hurts badly! 
> > (It's slow!)
>
>
> are you imposing that the division need be performed on _each_ iteration?

That's what I said.

> y = y1 + (y2-y1)*x/(x2-x1)
>
> is a linear function
>
> y = ax + b

That's what it is derived from.

> to keep the error within the precisional error margins of the media used 
> (i.e. not to have
> any additional cumulative error) all you need to do is to use a non-incremental 
> evaluator,
> and you end up with 1x multiplication and 1x addition per iteration, no 
> unit-errors
> whatsoever*, and last but not least you end up with no conditions in the inner 
> loop.

That's not true at all!

I'll give you an example:
Draw a line from (0,0) to (10,1).
With the slope function (and that includes your linear function) you'll 
get a slope of 1/10 = 0.1 in base 10 which is 0.199999999.... in base 
16. Since you only have limited precision (and it doesn't matter how 
much precision you have at _all_ as long as there is a _finite_ number 
of digits) you'll always end up with a number that is smaller than 1/10 
(e.g. by using IEEE 32 bit floats you'll get 0,099999904632568359375).
Now if you evaluate the pixel with x-position 5 using the slope code 
(and it is completely irrelevant whether you take the incremental 
variant or your linear function variant) you'll get a y-position of 
always smaller than 0.5 (for 32 bit floats you'll get 
0,499999523162841796875) which after rounding becomes 0!

I'll do it explicitely for your linear function y = ax + b:
a = 1/10  <-- a < 1/10 due to finite number of digits
y = a*5 + 0  <-- y < 0.5 --> round(y) = 0

Evaluating this point by the division variant or by Bresenham's 
algorithm gives you the right answer 1!

> [snip]
>
> just my 0.02
> -blu

Michael Noisternig