[openbeos] Re: The Scientific Method aka BresenhamNewsletter Article
- From: "Martin Krastev" <blue@xxxxxxxxx>
- To: openbeos@xxxxxxxxxxxxx
- Date: Sat, 7 Jun 2003 20:23:18 +0300
"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?
y = y1 + (y2-y1)*x/(x2-x1)
is a linear function
y = ax + b
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.
* of course, due to the exponential nature of floats, a serious discrepancy in
the magnitudes
of the slope (a) and the base (b) of the linear function would introduce a
lack-of-precision error.
BUT in case we deal with screen-range magnitudes (i.e. in the < 10's of
thousands) and we use
regular fp32 (i.e. s23e8) we need be concerned.
then of course, using fp interpolation may be performance-suboptimal in the
case when we need
integer output right away - a f2l is not cheap. so it would be better to use
fixed-point versions of
a line segment, circle or ellipse evaluator, but for evaluating polygonal/areal
edges fp is here to stay.
> Now looking at the Bresenham algorithm again it is a very fine and fast
> one. (The only drawback I can think of is the inner comparison in the
> loop; but then again you can get rid of this too by some tricks).
Bresenham is one of the graphics geniuses of the comp. graphics era, his
algorithms are brilliant,
but we should not forget their purpose - to do correct interpolation given the
insufficient
precision of the media _and_ overall-slow arithmetics ops (or just non-present
-- mul) which
were common conditions during the time when his algorithms were developed.
Bresenhanm's
interpolation algorithms, along with several others (e.g. double-step
incremental) are surely
good to be know by the graficians, but using them in practice proves less and
less justified
with time. the list time i used a differential-comparator-based linear
interpolator was ~10
year ago, on my first 486.
just my 0.02
-blu
Other related posts:
