[openbeos] Re: The Scientific Method aka Bresenham NewsletterArticle

  • From: Michael Noisternig <michael.noisternig@xxxxxxxxx>
  • To: openbeos@xxxxxxxxxxxxx
  • Date: Sun, 08 Jun 2003 13:55:19 +0200

Martin Krastev wrote:

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


to overcome this indeed _serious_ problem point arithmetic units (be it fpu's

Whether it's a _serious_ problem is probably subjective. Fact is that the slope code doesn't draw the line entirely correctly.

or software implementations) utilize rounding modes, in our case that would be 'nearest'*

Yes, that is what Bresenham's algorithm uses implicitely.

but at the end we need a lesser precision number (say, a whole nunber) so the 
fact that
we lose precision _in_the_LSB_ of our binary fraction numer don't not move us 
to the least,
as we can avoid _accumulation_ errors.

* which, of course, just reverses the problem - the nearest 
finately-representable
binary fractional number to our original decimal fraction is _inevitably_ 
greater (by mag.)
than the original number (so the problem is actually the inverse of what you 
described).


(e.g. by using IEEE 32 bit floats you'll get 0,099999904632568359375).


that would be 'chop' round mode. let's re-check that using 'neares' rounding mode

0.10000000149011612

You are right, I forgot to round to nearest whole number, but it doesn't matter anyway, because - as I already said - as long as you don't have an infinite number of digits, 0.1 (base 10) cannot be presented exactly in binary system.

So now if 0.1 encoded binary is greater than exactly 0.1, then the problem is just reversed: You'll get y = 1 at x = 5 when line is drawn from (0,0) to (10,1) and y = 0 if it is drawn backwards.



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!


what makes you think that at x-position = 5 y should be = 1?

y = 5*1/10 + 0 = 0.5, round(0.5) = 1, right?

the line is of lenght 11 pixels, x-pos 5 is the middle pixel.

Yes, that's why it doesn't actually matter whether x.5 is rounded to x or x+1. Whichever rounding mode is choosen, it should be taken for all cases, that means the line should look the same when drawn from A to B and from B to A.

use Bresenham to draw it from (0, 0) to (10,1) and then from
(10, 1) to (0, 0) - you may be surprized.

Well, it looks exactly the same, independent from the direction you draw it (I checked with the Windows GDI, so you can tell me the BeOS results ;-]). I was surprised though that 0.5 gets rounded to 0 though. From a mathematical POV it doesn't make a difference though because the error is the same.



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


yes, if the only place you use round() is for the float->int conversion

As I already said, if you round 'a' to the LSB then it becomes > 1/10 and when you draw the line backwards 'y' evaluates to 0 again.



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


hmm, would you elaborate why the division variant would produce 1? 

as above: (5*1)/10 + 0 = 0.5 (exactly!), round(0.5) = 1
or reverse: (-5*1)/10 + 1 = 0.5


-blu

Michael Noisternig


Other related posts:

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