[openbeos] Re: The Scientific Method aka BresenhamNewsletter Article
- From: "Martin Krastev" <blue@xxxxxxxxx>
- To: openbeos@xxxxxxxxxxxxx
- Date: Mon, 9 Jun 2003 16:42:57 +0300
"Michael Noisternig" <michael.noisternig@xxxxxxxxx> wrote:
> Whether it's a _serious_ problem is probably subjective. Fact is that
> the slope code doesn't draw the line entirely correctly.
hmm, i'd say exactly the opposite - it's a fact that one of the fundamental
problems
of fractional arithmetics is LSB errors, whereas whethert the slope code draws
correctly is rather subjective :)
>> 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?
'round(0.5) = 1' is just a convention, it's not a matter of precision. so i was
asking
why you maintained that at x = 5, y should be 1. but from your last post i see
that we
actually agree it is irrelevant.
>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.
yes, it's a common reqirement for line plotters. how it's achieved, though, is
another matter. i'll address it further below.
> > 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.
you're right, Bresenham would not show an order-dependent variance in the
output - i got carried away (actually had in mind one of my own differential-
comparator-based line plotters which i recall to exibit order-dependent
variances)
- my bad.
>>>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.
see my comments at the end of this post.
>>>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
ok, i formulated my question erroneously (as the division variant does produce
.5 indeed).
what i actually meant to say was: why do you think that in general the division
variant is more
accurate than the slope variant? but if all you meant is that it just handles
consistently the
'.5-transient' cases then yes - it does. but it's prone to the finite
representation problem
of fractionals just as well (i.e. (2*1)/10 is as erroneously represented in fp
as 2 * 1/10 is)
but let's get back to the order invariance question. and the fact is the
question is pretty much
non-standing. why? because line plotters often, and in some particular cases
_mandatory_,
draw lines in one direction only, regardless of the order the verices were
passed in. i.e. lines
are treated not as vectors but as non-directional primitives, and as such line
plotters are
free to decide in what order to draw them. so, what finally matters w/ line
plotters/edge
evaluators is numerical precision, which condition i believe we both agree is
well satisfied.
-blu
ps:
"Michael Noisternig" <michael.noisternig@xxxxxxxxx> wrote:
>Actually it makes no difference whether you do it Mr. Phipps' way or
>your linear function way because the _absolute_ error is the same in
>both cases. The multiplication in your linear function also multiplies
>the error in the LSB which then is the same as the accumulated error by
>subsequent additions.
the absolute error would be the same if we can guarantee that the slope
is a always a _rational_ number.
Other related posts:
