[openbeos] Re: The Scientific Method aka Bresenham NewsletterArticle

  • From: Michael Noisternig <michael.noisternig@xxxxxxxxx>
  • To: openbeos@xxxxxxxxxxxxx
  • Date: Sat, 07 Jun 2003 20:34:03 +0200

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



Other related posts:

  1. Home
  2. haiku
  3. Archive
  4. 06-2003