Drawing floating-point lines with Bresenham
Thomas Kindler
I've written a graphics library that supports fast Bresenham line
drawing. I can give an integer starting point, integer number of
pixels, error increments for minor/major steps, and an initial error
value for the first pixel to draw.
Now I would like to draw lines with floating-point endpoints.
Does anyone know how to initialize the error terms to correctly draw
lines with non-integer endpoints?!
A link to an actual implementation in a graphics library would be nice!
(There _should_ be some driver code out there as many hardware
accelerators seem to be integer-bresenham only).
thanks for your help,
Thomas Kindler
Dave
> I've written a graphics library that supports fast Bresenham line
> drawing. I can give an integer starting point, integer number of
> pixels, error increments for minor/major steps, and an initial error
> value for the first pixel to draw.
>
> Now I would like to draw lines with floating-point endpoints.
>
> Does anyone know how to initialize the error terms to correctly draw
> lines with non-integer endpoints?!
Take a look at http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Generalization
Dave
ti_chris
an antialised lines in which case this algorithm is not ideal for
(although there are extensions of it that supports it). Bresenham is
also a very well known algorithm, but also one of the slowest (except
the naive method) that you can run with. I would suggest understand
the algorithm instead of copy/pasting it from somewhere (or use a
library that already does this). It should be pretty obvious how to
do what you are looking for once the math is understood.
Thomas Kindler
Hi Chris!
> I'm not sure what you are using this for.
It's a graphics library for a small embedded controller with a 128x64
LCD (black & white only, no grayscales).
> But chances are, you want an antialised lines in which case this
> algorithm is not ideal for [..]
No. I do not want antialiasing. I'd like to draw Bresenham lines, but
with floating-point endpoints.
(This really matters if you try to draw animated 3d graphics, which look
jerky if you round the endpoints before drawing the lines).
--
"Zuse, Zuse" sprach die Tante, als das Rechenzimmer brannte.
Thomas Kindler
That article doesn't solve my problem. I can already draw arbitrary
lines with integer endpoints (and even do correct clipping, without
changing the slope of the clipped line).
The question was how to initialize the error terms for a normal, integer
bresenham, if the line is given in floating-point coordinates.
Kaba
> Hi!
>
> I've written a graphics library that supports fast Bresenham line
> drawing. I can give an integer starting point, integer number of
> pixels, error increments for minor/major steps, and an initial error
> value for the first pixel to draw.
>
> Now I would like to draw lines with floating-point endpoints.
>
> Does anyone know how to initialize the error terms to correctly draw
> lines with non-integer endpoints?!
I don't. However, you could go up to the roots:
"Algorithm for computer control of a digital plotter"
by J.E.Bresenham
That's the paper introducing Bresenham's line algorithm. Google finds
it. Maybe you can derive the initial error term based on the paper.
I'm using another algorithm that I think is called the midpoint line
algorithm.
cr88192
"Thomas Kindler" <mail...@t-kindler.de> wrote in message
news:g5kt1t$jp5$1...@news01.versatel.de...
> ti_chris wrote:
>
> Hi Chris!
>
>> I'm not sure what you are using this for.
>
> It's a graphics library for a small embedded controller with a 128x64 LCD
> (black & white only, no grayscales).
>
>> But chances are, you want an antialised lines in which case this
> > algorithm is not ideal for [..]
>
> No. I do not want antialiasing. I'd like to draw Bresenham lines, but with
> floating-point endpoints.
>
> (This really matters if you try to draw animated 3d graphics, which look
> jerky if you round the endpoints before drawing the lines).
>
my thoughts here:
rather than using bresenham (really, this IS an integer algo...), make use
of native floating point stepping.
in this case, calculate the number of steps (in terms of horizontal or
vertical pixels), and the linear distance traveled in each step (a
floating-point vector).
this way, for each step, it is possible to calculate the real-valued
pixel-position, which can then be rounded to the exact pixel.
some amount of jerkiness is likely inevitable with a display as described.
actually, depending on the type of graphics, it may almost make sense to
draw a grayscale version in memory, and then dither it to the screen
(however, this could work ok for some things, and look like total crap for
others...).
hoff...@fho-emden.de
cr88192 schrieb:
> my thoughts here:
> rather than using bresenham (really, this IS an integer algo...), make use
> of native floating point stepping.
> in this case, calculate the number of steps (in terms of horizontal or
> vertical pixels), and the linear distance traveled in each step (a
> floating-point vector).
>
> this way, for each step, it is possible to calculate the real-valued
> pixel-position, which can then be rounded to the exact pixel.
>
> some amount of jerkiness is likely inevitable with a display as described.
Yes, how true.
Why the heck should such a low quality graphic 128x64
be better if processed by float and additional rounding ?
The generic float algorithm is easily programmed (speed
issues ignored, and of course NOT a Bresenham algo).
Therefore it would be interesting to show the benefits of
such a float line drawer.
http://www.fho-emden.de/~hoffmann/drawf11102001.pdf
Best regards --Gernot Hoffmann
Kaba
> Yes, how true.
>
> Why the heck should such a low quality graphic 128x64
> be better if processed by float and additional rounding ?
>
> The generic float algorithm is easily programmed (speed
> issues ignored, and of course NOT a Bresenham algo).
> Therefore it would be interesting to show the benefits of
> such a float line drawer.
It's called subpixel accuracy, and as the OP says, this delivers a much
smoother animation when the movement is slow. Drawing a line with
slightly different subpixel positions makes a difference. In my opinion
low resolution only emphasizes its importance.
Thomas Kindler
> cr88192 schrieb:
>> my thoughts here:
>> rather than using bresenham (really, this IS an integer algo...), make use
>> of native floating point stepping.
>> in this case, calculate the number of steps (in terms of horizontal or
>> vertical pixels), and the linear distance traveled in each step (a
>> floating-point vector).
>>
>> this way, for each step, it is possible to calculate the real-valued
>> pixel-position, which can then be rounded to the exact pixel.
>>
>> some amount of jerkiness is likely inevitable with a display as described.
>
> Yes, how true.
Ah, not really. Imagine a simple analog-style voltage meter on that
display. If you only draw integer endpoint coordinates, the needle will
jump and jerk from value to value.
If you draw it with subpixel-accurate endpoints, the needle will move
much more smoothly (you get that rolling-steps effects).
> Why the heck should such a low quality graphic 128x64
> be better if processed by float and additional rounding ?
See above. 128x64 is big enough for analog-style needle displays, etc..
> The generic float algorithm is easily programmed (speed
> issues ignored, and of course NOT a Bresenham algo).
Why "of course NOT"?
The Bresenham algo can display arbitrary lines. This is also needed when
clipping lines, as the clipped points will almost never end up on
integer coordinates. (I already implemented slope-correct clipping,
i.e. lines that look exactly the same whether clipped or not).
Non-integral endpoints should just be a matter of setting up the error
value correctly.
Some old graphics chips were integer-bresenham-only. The Amiga's Blitter
is a nice example -- there must be someone who did lines with
non-integral endpoints on that machine.
Kenneth Sloan
The trick is to understand what the "error term" means. Look carefully
at the code and figure this out. Then, it should be obvious how to
initialize.
--
Kenneth Sloan Kennet...@gmail.com
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
Thomas Kindler
> Thomas Kindler wrote:
>> Hi!
>>
>> I've written a graphics library that supports fast Bresenham line
>> drawing. I can give an integer starting point, integer number of
>> pixels, error increments for minor/major steps, and an initial error
>> value for the first pixel to draw.
>>
>> Now I would like to draw lines with floating-point endpoints.
>>
>> Does anyone know how to initialize the error terms to correctly draw
>> lines with non-integer endpoints?!
>
> I don't. However, you could go up to the roots:
>
> "Algorithm for computer control of a digital plotter"
> by J.E.Bresenham
>
> That's the paper introducing Bresenham's line algorithm. Google finds
> it. Maybe you can derive the initial error term based on the paper.
>
Cool! And I could even download it for free.
That's the problem with basic stuff like this. Everyone knows some version
of the algorithm, the basic idea is thaught everywere, but no one can point
to a good (and fully correct) implementation.
The sad thing is that all the original papers are available online, but all
of them require me to be a member of the ACM or IEEE :-/
Getting the Cohen-Sutherland clipping to work while preserving the slope of
the original line was an adventure in it's own right.. I didn't find a
single lecture that explains the error-term update, because it always seems
to be "out of scope" for a graphics course. (I finally found a good
explanation in the x.org library code).
--
"Zuse, Zuse" sprach die Tante, als das Rechenzimmer brannte
Kaba
> The sad thing is that all the original papers are available online, but all
> of them require me to be a member of the ACM or IEEE :-/
Yes, it's frustrating. Being associated with some university (student or
worker) is one way out of this problem. If you are in one, see if you
can get access to the articles through them.
About the starting error term. I managed to derive it from the paper.
But maybe you want to try this yourself first, so I won't spoil the
fun:)
cr88192
> hoff...@fho-emden.de wrote:
>> cr88192 schrieb:
>>> my thoughts here:
>>> rather than using bresenham (really, this IS an integer algo...), make
>>> use
>>> of native floating point stepping.
>>> in this case, calculate the number of steps (in terms of horizontal or
>>> vertical pixels), and the linear distance traveled in each step (a
>>> floating-point vector).
>>>
>>> this way, for each step, it is possible to calculate the real-valued
>>> pixel-position, which can then be rounded to the exact pixel.
>>>
>>> some amount of jerkiness is likely inevitable with a display as
>>> described.
>>
>> Yes, how true.
>
> Ah, not really. Imagine a simple analog-style voltage meter on that
> display. If you only draw integer endpoint coordinates, the needle will
> jump and jerk from value to value.
>
> If you draw it with subpixel-accurate endpoints, the needle will move much
> more smoothly (you get that rolling-steps effects).
>
in that case, it is not entirely clear to my why the ordinary
(integer-based) algo doesn't work so well (unless you are doing something
funky, like drawing very long lines or such...).
>> Why the heck should such a low quality graphic 128x64
>> be better if processed by float and additional rounding ?
>
> See above. 128x64 is big enough for analog-style needle displays, etc..
>
>> The generic float algorithm is easily programmed (speed
>> issues ignored, and of course NOT a Bresenham algo).
>
> Why "of course NOT"?
>
if the algo is fundamentally changed, it is not the same algo.
bresenham is, as specified, a set of integer operations.
doing, say, a calculated number of steps with a floating-point stepping
algo, is technically a different algo (bresenham means bresenham, and is a
specific way for drawing lines, but it is not a synonym for "line drawing"
in general).
> The Bresenham algo can display arbitrary lines. This is also needed when
> clipping lines, as the clipped points will almost never end up on integer
> coordinates. (I already implemented slope-correct clipping, i.e. lines
> that look exactly the same whether clipped or not).
>
typically, you would do clipping prior to rounding (except for when clipping
to the edge of the screen or similar, but usually this is just a check of
not plotting the pixel if not on-screen).
the general idea then is that the line algo is used only to draw the final
line, and is rounded to the correct coords as a final step, not in the
middle somewhere.
> Non-integral endpoints should just be a matter of setting up the error
> value correctly.
>
possibly, but for the most part it should not make much difference.
> Some old graphics chips were integer-bresenham-only. The Amiga's Blitter
> is a nice example -- there must be someone who did lines with non-integral
> endpoints on that machine.
>
yeah, but they would have probably rounded at the last second as well...
it sounds to me like maybe you are probably doing something "weird" to make
the line drawing less accurate.
hoff...@fho-emden.de
Kaba schrieb:
The OP cannot draw a line with slightly different subpixel positions -
his LCD has fixed pixel position in a grid (opposed to an
oscilloscope)..
a) End point positions are rounded. Pure Bresenham. This is the
optimal
solution because all pixels are as near as possible to the ideal line.
b) End point positions are not rounded. Line pixels are calculated by
float.
Then all points are rounded. Because the end points are rounded, the
remaining pixels are either the same as Bresenham's, or their
positions
are different to. In this case the solution is not optimal.
Note: the OP can draw only by black and white, and it's a single
pixel
line. Subpixel calculation would be useful for drawing thick lines by
different
grays.
If I should be wrong, then I'm asking politely for a graphical
example,
which shows the benefit of float calculations in this application.
Best regards --Gernot Hoffmann
Kaba
> If I should be wrong, then I'm asking politely for a graphical
> example,
> which shows the benefit of float calculations in this application.
Here's an example.
http://kaba.hilvi.org/Cga/subpixel_lines.png
For me, the sampling point of a pixel (x, y) is at (x + 0.5, y + 0.5).
Going left to right, the lines differ only on the subpixel y position of
the left end-point. The subpixel positions are 0.1, 0.3, 0.5, 0.7, 0.9.
The 0.5 corresponds to the integer algorithm (matches with a sampling
point).
Going bottom to top, the lines differ only on the subpixel y position of
the right end-point with the same subpixel positions as above.
The x:s of both end points of all lines coincide with half integers.
Rounding the end-points to sampling points would result in the line
segments all looking exactly like the one at the center. In animation
the difference is quite dramatic. Current graphics hardware implements
subpixel accuracy. Subpixel accuracy is not useful just for lines but
for any shapes, like polygons and circles.
Jens Dierks
> If I should be wrong, then I'm asking politely for a graphical
> example,
> which shows the benefit of float calculations in this application.
For example, 3 lines with the endpoint.y value increased
by 0.5, with rounded endpoints:
########################
########################
############
############
without rounding:
########################
##################
######
############
############
ti_chris
easilly achieve greyscale (still) with a black and white device if you
modulate the way you render the pages. aka: If you constantly flip
between 2 screens, you can achieve 4 colors (black, white, light gray,
dark gray). Essentially, it goes by saying that if the pixel is lit
all half the time, you can achieve a (half black/half white) pixel
which is gray. if the pixel is on 75% of the time, you can achieve a
darker version of it and etc.
Anyhow I digress, I would suggest using fixed points. It sounds like
you found an answer to your question either way.
Thomas Kindler
> Cool. I don't know if this is a personal project or not.
Yes, it's personal.. a graphics library for small micro-controllers and
cheap LCDs - to be released under the GPL.
> But you can easilly achieve greyscale (still) with a black and white
> device if you modulate the way you render the pages.
> aka: If you constantly flip between 2 screens, you can achieve 4 colors
> (black, white, light gray, dark gray).
I know ;) But this only works well if you can synchronize to the LCD's
refresh clock (which is not always possible). Otherwise, you'll get some
ugly stripes.
Kaba
> if the algo is fundamentally changed, it is not the same algo.
> bresenham is, as specified, a set of integer operations.
>
> doing, say, a calculated number of steps with a floating-point stepping
> algo, is technically a different algo (bresenham means bresenham, and is a
> specific way for drawing lines, but it is not a synonym for "line drawing"
> in general).
I disagree, if I may:)
In my opinion the key ideas of the Bresenhams algorithm are that:
* the cases are divided into octants
* noticing that the comparison of the distances of the pixel sampling
points to the line segment (1) can be replaced by comparison along the
y-axis (2)
* noticing that actually you can compare the midpoint of the two
candidate pixels to the line segment along y-axis. (3)
* noticing that the comparison is unchanged under multiplication by a
positive number
* noticing that you can track the result of the comparison incrementally
That this algorithm results in integer operations if the endpoints end
up at sampling points is a plus. But if I just generalized the algorithm
to handle non-sampling point end positions, then it would be plain
plagiarism to call it anything else than Bresenhams line algorithm.
Footnotes:
Bresenham uses (3). It is easy to show that (1) is equivalent to (2).
However, it is not at all clear to me that (2) is equivalent to (3).
I'll leave that to another post.
cr88192
"Kaba" <no...@here.com> wrote in message
news:MPG.22e9e6f03...@news.cc.tut.fi...
oh, ok, but it is different than what I had assumed.
I had figured, a floating-point draw function would be sort of like this:
if(fabs(e.x-s.x)>fabs(e.y-s.y))
{
n=(int)rint(fabs(e.x-s.x));
dir=(e-s)/n;
for(i=0; i<n; i++)
{
pt=s+dir*i;
//draw pixel
}
}else
{
n=(int)rint(fabs(e.y-s.y));
dir=(e-s)/n;
for(i=0; i<n; i++)
{
pt=s+dir*i;
//draw pixel
}
}
which I would think would be regarded as something rather different than
bresenhams...
> --
> http://kaba.hilvi.org
Kaba
> Now I would like to draw lines with floating-point endpoints.
>
> Does anyone know how to initialize the error terms to correctly draw
> lines with non-integer endpoints?!
Here's a working implementation drawing lines with Bresenham with
subpixel accuracy:
http://kaba.hilvi.org/Cga/subpixelbresenhamfloat.html
Note that when I derived the formulas I ended up having the decision
variable the negative of the one usually used and that is reflected in
the code. Well, no big deal.
That version uses floating point in the loops. However, what if one
converts the variables to fixed point just before the loop? That gives
us:
http://kaba.hilvi.org/Cga/subpixelbresenhamfixed.html
With the 16 fixed decimal bits used, this gives pixel-identical results
with the floating point version at least in the following image:
Kaba
> Here's a working implementation drawing lines with Bresenham with
> subpixel accuracy:
And here's the derivation. Note that the decision variable is, by
accident, negative of the one usually used.
The Bresenham line algorithm for drawing line segments.
This is a generalized version for floating point end points,
derived here.
Our task is to the generate integer sequences
x(i) and y(i) such that the set {(x(i), y(i))}
forms a one-pixel wide line segment from
(xStart, yStart) to (xEnd, yEnd).
We take the sampling point of a pixel (x, y) to
be at (x + u, y + v). For example if u, v = 0.5,
then the sampling point of the pixel (0, 0) is at
(0.5, 0.5).
Let
dx = xEnd - xStart
dy = yEnd - yStart
The algorithm separates into cases based on which
octant the end point is with respect to the start point.
The octants are numbered as:
\2|1/
3\|/0
--+--
4/|\7
/5|6\
Assume |dx| >= |dy|. This takes care
of octants 0, 3, 4 and 7. We will deal
with the other octants later.
We start tracing from the pixel (x(0), y(0))
that has the sampling point closest to (xStart, yStart).
From here, we perform either of the
two steps:
1) x(i + 1) = x(i) + tx, y(i + 1) = y(i) + ty1
2) x(i + 1) = x(i) + tx, y(i + 1) = y(i) + ty2
where
(tx, ty1, ty2) is one of
{(1, 0, 1), (1, 0, -1), (-1, 0, 1), (-1, 0, -1)}.
We choose the one that will keep us closer to the line.
This simple procedure is repeated to trace the whole line
segment.
The distance of a pixel to the line is measured as the
distance of its sampling point to the line. Thus the
comparison to select between the two cases is:
distance((x(i) + u + tx, y(i) + v + ty1), line) <=
distance((x(i) + u + tx, y(i) + v + ty2), line)
If this comparison yields true, the option 1 is chosen.
Otherwise option 2 is chosen. However, this is inefficient.
Let
a(i) = x(i) + u
b(i) = yStart + ((x(i) + u) - xStart) * (dy / dx)
Then (a(i), b(i)) traces out points from the line
with a(i) horizontally at the sampling points.
Because of similar triangles, we can equivalently compare the
distances of the sampling points to the line along the y-axis:
|(y(i) + v + ty1) - b(i + 1)| <= |b(i + 1) - (y(i) + v + ty2)|
This is much faster, but the absolute values
still block the way to an efficient implementation.
Fortunately, we see that there is still one more equivalent
comparison. Rather than comparing the distances of the two candidate
points
to the line segment, we can compare the position of their
midpoint to the line segment (along y-axis):
((y(i) + v + ty1) + (y(i) + v + ty2)) / 2 <= b(i + 1)
<=>
(y(i) + v + ty1) + (y(i) + v + ty2) <= 2 b(i + 1)
<=>
(y(i) + v + ty1) - b(i + 1) <= b(i + 1) - (y(i) + v + ty2)
Thus, the absolute values can be removed!
Rather than comparing directly (left <= right), we compare the sign
of the difference (left - right <= 0):
s'(i)
= (y(i) + v + ty1) - b(i + 1)) - (b(i + 1) - (y(i) + v + ty2))
= 2(y(i) + v) - 2b(i + 1) + (ty1 + ty2)
= 2(y(i) + v) - 2(yStart + (x(i + 1) + v - xStart) * (dy / dx)) + (ty1 +
ty2)
= 2(y(i) + v) - 2(yStart + (x(i) + tx + v - xStart) * (dy / dx)) + (ty1
+ ty2)
= 2(y(i) + v) - 2b(i) - 2 tx (dy / dx) + (ty1 + ty2)
If s'(i) <= 0, then we choose the option that increases s'(i).
Otherwise we choose the option that decreases s'(i).
Because dx is positive, and thus does not change the sign
of s', we can as well multiply s' by dx to avoid division.
s(i)
= s'(i) * dx
= 2(y(i) + v)dx - 2b(i)dx - 2 tx dy + (ty1 + ty2)dx
We now notice:
If option 1 is chosen, then
s(i + 1)
= 2(y(i + 1) + v)dx - 2b(i + 1)dx - 2 tx dy + (ty1 + ty2)dx
= 2(y(i) + v)dx + 2 ty1 dx - 2b(i)dx - 2 tx dy - 2 tx dy + (ty1 + ty2)dx
= s(i) + 2 ty1 dx - 2 tx dy
Similarly, if option 2 is chosen, then
s(i + 1)
= s(i) + 2 ty2 dx - 2 tx dy
Thus the values for s(i) can be computed
incrementally. However, s(0) must be computed directly:
s(0)
= 2y(0)dx - 2b(0)dx - 2 tx dy + ((ty1 + ty2) + 2v)dx
= 2y(0)dx - 2(yStart * dx + ((x(0) + u) - xStart) * dy) - 2 tx dy +
((ty1 + ty2) + 2v)dx
= 2((y(0) + v) - yStart)dx - 2((x(0) + u) - xStart)dy - 2 tx dy + (ty1 +
ty2) dx
Notice that if xStart = x(0) + u and yStart = y(0) + v (the
start point is at a sample point), then
s(0) = -2 tx dy + (ty1 + ty2) dx
If in addition (xEnd, yEnd) is at a sample point,
then the whole algorithm runs on integer arithmetic.
The octants 1, 2, 5, and 6 with |dx| < |dy| can be derived
by simply exchanging x and y in all formulas.
This has the effect of reflecting the plane
w.r.t the line (1, 1).
Thus the sAdd1, sAdd2 and s(0) can be obtained from
the following reflection pairs by exchanging x and y:
Octant 1 <-> Octant 0
Octant 2 <-> Octant 7
Octant 5 <-> Octant 4
Octant 6 <-> Octant 3
Summary
-------
sNormal =
2((y(0) + v) - yStart)dx - 2((x(0) + u) - xStart)dy - 2 tx dy + (ty1 +
ty2) dx
sReflected =
2((x(0) + u) - xStart)dy - 2((y(0) + v) - yStart)dx - 2 ty dx + (tx1 +
tx2) dy
Octant 0:
(1, 0) => sAdd1 = -2 dy
(1, 1) => sAdd2 = -2 dy + 2 dx
s(0) = sNormal + -2 dy + dx
Octant 1 (reflected octant 0):
(0, 1) => sAdd1 = -2 dx
(1, 1) => sAdd2 = -2 dx + 2 dy
s(0) = sReflected + (-2 dx + dy)
Octant 3:
(-1, 0) => sAdd1 = 2 dy
(-1, 1) => sAdd2 = 2 dy + 2 dx
s(0) = sNormal + 2 dy + dx
Octant 6 (reflected octant 3):
(1, -1) => sAdd1 = 2 dx + 2 dy
(0, -1) => sAdd2 = 2 dx
s(0) = sReflected + (2 dx + dy)
Octant 4:
(-1, 0) => sAdd1 = 2 dy
(-1, -1) => sAdd2 = 2 dy - 2 dx
s(0) = sNormal + 2 dy - dx
Octant 5 (reflected octant 4):
( 0, -1) => sAdd1 = 2 dx
(-1, -1) => sAdd2 = 2 dx - 2 dy
s(0) = sReflected + (2 dx - dy)
Octant 7:
(1, 0) => sAdd1 = -2 dy
(1, -1) => sAdd2 = -2 dy - 2 dx
s(0) = sNormal + (-2 dy - dx)
Octant 2 (reflected octant 7):
(-1, 1) => sAdd1 = -2 dx - 2 dy
( 0, 1) => sAdd2 = -2 dx
s(0) = sReflected + (-2 dx - dy)
Hans-Bernhard Bröker
> ti_chris wrote:
>> Cool. I don't know if this is a personal project or not.
> Yes, it's personal.. a graphics library for small micro-controllers and
> cheap LCDs - to be released under the GPL.
Looks like you just contradicted the thread subject. "Small
microcontrollers" and "floating-point" don't mix.
Thomas Kindler
Hey, it's 2008 ;) For updating a few analog-style meters or similar, an AVR
with emulated FP is more than fast enough. Of course, you would use
fixed-point math where performance matters.
--
"Zuse, Zuse" sprach die Tante, als das Rechenzimmer brannte
Daniel Pitts
> Hi!
>
> I've written a graphics library that supports fast Bresenham line
> drawing. I can give an integer starting point, integer number of
> pixels, error increments for minor/major steps, and an initial error
> value for the first pixel to draw.
>
> Now I would like to draw lines with floating-point endpoints.
>
> Does anyone know how to initialize the error terms to correctly draw
> lines with non-integer endpoints?!
if I remember correctly, the Error term is some integer between 0 and
one delta. Normally the error term starts at zero, but you can probably
find a simple formula to adjust the initial value based on the decimal
portion of the floating point numbers. What that formula is, I couldn't
say, but I would expect it to be fairly straight-forward to find.
Alternatively, you can apply the Bresenham algorithm, but use floating
point pixel values for the whole darn thing. Not as fast, but it would
probably work.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
David Combs
Thomas Kindler <thomas....@gmx.de> wrote:
...
>
>The sad thing is that all the original papers are available online, but all
>of them require me to be a member of the ACM or IEEE :-/
>
>Getting the Cohen-Sutherland clipping to work while preserving the slope of
>the original line was an adventure in it's own right.. I didn't find a
>single lecture that explains the error-term update, because it always seems
>to be "out of scope" for a graphics course. (I finally found a good
>explanation in the x.org library code).
>
>--
>"Zuse, Zuse" sprach die Tante, als das Rechenzimmer brannte
>www.microsoft-hellhounds.de, www.bredobrothers.de
So, you do NOW understand it.
Perhaps you could write-up your understandings, now that you've
spent so much time and brain-power on it.
Especially all the "ah-ha" moments, when you cursed:
So why the xxxx didn't they explain it to me that way
back in school! Sure would have made it easier for *everyone*
(well, at least us of only "ordinary" intelligence) to understand!
Then file it somewhere that people (ie google) can find it.
(Get Eberly to proof it, then maybe he'll put it on *his* site!)
David