World's fastest line algorithm (EFLA) Beats Wu and Bresenham

2660 views

None

Dec 13, 2001, 8:48:38 AM12/13/01
to
Due to the popularity of the Extremely Fast Line Algorithm (EFLA),
it was benchmarked against the most popular (Bresenham) and the

Bresenham is the standard line algorithm that has been in use for many
many years. Wu is the most advanced (published that is) algorithm
today and uses symmetric double-step.

These algorithms are important because they are not CPU instruction
dependent (i.e. multiplatform, 64, 32 or 16 bit architectures, and no
assembly speedups).

The Extremely Fast Line Algorithm is unique in that it has no branch
instructions inside the main loop. In addition, the algorithm is
extremely
simple, with a very tiny loop.

EFLA actually beat both Bresenham and Wu line algorithms in a
rigourous
benchmark consisting of 1 million lines on standard Pentium III
machines.

Details on the benchmark are available at...
http://www.edepot.com/algorithm.html

Also available on that URL are:
Source for the Extremely Fast Line Algorithm.
Source for the benchmark.
Source for Wu.
Source for Bresenham.

Gernot Hoffmann

Dec 14, 2001, 7:38:48 AM12/14/01
to
poh...@aol.com (None) wrote in message news:<12124e47.01121...@posting.google.com>...

> Due to the popularity of the Extremely Fast Line Algorithm (EFLA),
> it was benchmarked against the most popular (Bresenham) and the
> most advanced (Wu) algorithm today.
> ...

Thanks for the test, looks convincing.
Wu code is terrible - seems to be an explicite handling of
all different cases and exceptions. In my opinion also bad
for short vectors because of the basic control logic.
The benchmark test shows very similar results, but your
code is the winner.
How are the results if you execute the procedures without
pixel drawing ? This would reveal the features of the algo-
rithms themselves.
Did you test random vectors in bounding boxes ?
E.g. 10, 100, 500 width for the box length.
Did you test forward/reverse match (retracing)?

Best regards ---Gernot Hoffmann

Gernot Hoffmann

Dec 14, 2001, 1:22:52 PM12/14/01
to
hoff...@fho-emden.de (Gernot Hoffmann) wrote in message news:<a815dbcf.01121...@posting.google.com>...

> poh...@aol.com (None) wrote in message news:<12124e47.01121...@posting.google.com>...
> > Due to the popularity of the Extremely Fast Line Algorithm (EFLA),
> > it was benchmarked against the most popular (Bresenham) and the
> > most advanced (Wu) algorithm today.
> > ...
>
Investigation continued, here for EFL-D:

The algorithm uses a simulation of float by 32-bit Integer
(ShiftLeft 16, ShiftRight 16). I wouldnæ„’ call this a "clean"
programming style. Some numbers, e.g. the increments, need the
32-bit Integer number space, but itæ„€ not allowed to use pixel
coordinates in the whole space.
This is of course an academic objection, but I still believe
that fundamental algorithms should be "clean".

I have converted the source code into Pascal, which requires
some modifications.
So, the next objections are based on the assumption, that the
conversion is correct. If not, then I apologize in advance.

a) the algorithm doesnæ„’ deliver the same results as Bresenham
(represented by two other programs) under all circumstances.
Note: the only allowed deviation is the location of transition
points by one pixel - the ">" or ">=" definition.
b) the forward/reverse match (retracing)is wrong -
I observe offsets not only at transition points but on the
whole line.

Best regards ---Gernot Hoffmann

Message has been deleted

Ian Kemmish

Dec 20, 2001, 1:58:29 PM12/20/01
to
says...

>The Extremely Fast Line Algorithm is unique in that it has no branch
>instructions inside the main loop. In addition, the algorithm is
>extremely
>simple, with a very tiny loop.

Well, that claim is definitely false, since the DDA-based line drawing
algorithm I wrote for the Whitechapel MG-1 in February 1985 didn't have any
either, primarily because conditional branches on the NS32000 series were so
abysmally slow. And I'm 100% certain I wasn't the first, either.

In fact, I'd go so far as to say that if you see *any* DDA-based algorithm that
has a conditional branch inside the inner loop, it's been implemented wrong:-).

> EFLA actually beat both Bresenham and Wu line algorithms in a
> rigourous

What's the likelihood that someone who's too lazy to read a few basic texts is
going to understand or be able to construct decent synthetic benchmarks?

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ian Kemmish 18 Durham Close, Biggleswade, Beds SG18 8HZ, UK
usene...@eeyore.dircon.co.uk Tel: +44 1767 601 361
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Behind every successful organisation stands one person who knows the secret
of how to keep the managers away from anything truly important.

Gernot Hoffmann

Dec 20, 2001, 5:25:38 PM12/20/01
to
usene...@eeyore.dircon.co.uk (Ian Kemmish) wrote in message news:<pxqU7.6\$%h2....@news.dircon.co.uk>...

> says...
> >The Extremely Fast Line Algorithm is unique in that it has no branch
> >instructions inside the main loop. In addition, the algorithm is
> >extremely
> >simple, with a very tiny loop.
>
> Well, that claim is definitely false, since the DDA-based line drawing
> algorithm I wrote for the Whitechapel MG-1 in February 1985 didn't have any
> either, primarily because conditional branches on the NS32000 series were so
> abysmally slow. And I'm 100% certain I wasn't the first, either.
>
.......
> Ian Kemmish
...

OK, gentlemen:
LetÂ´s listen to Jack Bresenham in his publication
"Pixel Processing Fundamentals, IEEE Computer Graphics and
Applications, January 1996": (sorry - no URL)
Here is a piece of nearly not understandable pseudocode for a four
quadrant line drawing algorithm without endpoint swapping, which is
also correct for retracing. This algorithm uses a branch, as usual.
DidnÂ´t Mr.Bresenham know the state of the art ?

I had tested the world fastest algorithm: IMO itÂ´s simply wrong,
though perhaps fast. Why didnÂ´t we get a reply here ?

Best regards ---Gernot Hoffmann

None

Dec 20, 2001, 5:56:32 PM12/20/01
to
usene...@eeyore.dircon.co.uk (Ian Kemmish) wrote in message news:<pxqU7.6\$%h2....@news.dircon.co.uk>...
> says...
> >The Extremely Fast Line Algorithm is unique in that it has no branch
> >instructions inside the main loop. In addition, the algorithm is
> >extremely
> >simple, with a very tiny loop.
>
> Well, that claim is definitely false, since the DDA-based line drawing
> algorithm I wrote for the Whitechapel MG-1 in February 1985 didn't have any
> either, primarily because conditional branches on the NS32000 series were so
> abysmally slow. And I'm 100% certain I wasn't the first, either.
>
> In fact, I'd go so far as to say that if you see *any* DDA-based algorithm that
> has a conditional branch inside the inner loop, it's been implemented wrong:-).

Did you implement your algorithm in assembly, whereby
it is dependent on the instruction set? Please list the source.

I did a check on all the algorithms, including "DDA line algorithms", and
all of them had a branch instruction in them. The only exception is EFLA.
Please list a URL with its source.

And note that you agree EFLA's branchless main loop is a good thing.

Some info: Wu and Bresenham algorithms are both have DDA components.
In fact all algorithms these days
use DDA. DDA just means digital differential analysis. DDA can be used
in circles, like addition can be used in circles. The algorithm is what
counts. DDA is just a term saying, as an analogy, use digital instead
of analog.

And EFLA beat Wu and Bresenham... http://www.edepot.com/algorithm.html

I have another line algorithm that is faster than EFLA, but it uses
a different technique, with a builtin optimizer. Look for it in another
post. EFLA is unique in that it has an extremely tiny loop without branches.
The algorithm is also not tied to hardware (no assembly and memory layout
specifics).

Because you have claimed EFLA's uniqueness is false, its your turn
to provide the source to the line algorithm in Whitechapel MG-1.

gordy

Dec 20, 2001, 10:44:21 PM12/20/01
to
> Did you implement your algorithm in assembly, whereby
> it is dependent on the instruction set? Please list the source.
>
> I did a check on all the algorithms, including "DDA line algorithms", and
> all of them had a branch instruction in them. The only exception is EFLA.
> Please list a URL with its source.
>
> And note that you agree EFLA's branchless main loop is a good thing.
..........

someone else had already pointed out that optimizing the line's control loop
is pointless when your calling a function to plot the actual pixel. having
per-pixel function overhead in any lowlevel graphical function such as this
is never acceptable. the branch in other algorithms (which btw is never EVER
implemented as an actual branch) is usually used to optimize the function
for a linear frame buffer. in the typical case of a linear frame buffer the
x inc is the pixel size and the y inc is the frame buffer width.. the branch
in the inner loop would determine x or y, incriment the pointer accordingly
and write the pixel. in your algorithm, x and y are incrimented each time
and a function is called that must recalculate the offset into the
framebuffer and write the pixel.. so which do you think is more efficient?

you seem to be against assembly language but when it comes to making the
fastest _anything_, bottom line is that it wont be an HL implementation.

Mike

Dec 21, 2001, 12:33:53 AM12/21/01
to
poh...@aol.com (None) wrote in message news:<12124e47.01122...@posting.google.com>...

> I did a check on all the algorithms, including "DDA line algorithms", and
> all of them had a branch instruction in them. The only exception is EFLA.
> Please list a URL with its source.

In fact, I did just that. Here's the first result Google returned. I
didn't bother looking at any more:

http://www.cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html

Note that the first attempts use exactly the same algorithm as yours,
sans fixed-point. No branches inside the inner loop.

seen this page, because you plagiarized the Wu source from it. Rather
impolite of you to publish the code on your site without even
bothering to cite the original source, don't you think?

> Some info: Wu and Bresenham algorithms are both have DDA components.
> In fact all algorithms these days
> use DDA. DDA just means digital differential analysis. DDA can be used
> in circles, like addition can be used in circles. The algorithm is what
> counts. DDA is just a term saying, as an analogy, use digital instead
> of analog.
>

Thank you for defining the abbreviation for us. It sounds like you
just looked it up. Other line algorithms use more sophisticated
stepping algorithms than a straight DDA. Your algorithm consists
solely of a loop with a DDA. I hate to break it to you, but your
approach is generally the *first* one anybody bothers trying out
before they event start to optimize. As a matter of fact, I did
pretty much the same thing roughly a year ago to implement a realtime
bitmap stretch. I can't post the source, since it's the property of
my company, but I certainly never thought I had invented anything new.

> I have another line algorithm that is faster than EFLA, but it uses
> a different technique, with a builtin optimizer. Look for it in another
> post. EFLA is unique in that it has an extremely tiny loop without branches.
> The algorithm is also not tied to hardware (no assembly and memory layout
> specifics).
>

No, you have one branch per pixel. That's how loops work. The reason
for using double-step algorithms is that they can draw a line with
fewer loop iterations. Wu, for example, draws four pixels per
iteration, with one or two branches within the loop, giving fewer
total branches than "your" algorithm.

> Because you have claimed EFLA's uniqueness is false, its your turn
> to provide the source to the line algorithm in Whitechapel MG-1.
> Otherwise, your claim is false.
>

No, it's not. It's a DDA, pure and simple. The cleverest thing in
your loop is the use if fixed-point arithmetic, which other people
suggested to you in this newsgroup when they saw you doing horrible
things with floating-point. The page I linked to above tries using
your approach almost as a first attempt.

Here's what the whole thing comes down to:

1. You haven't invented anything new.
2. You won't beat existing software line drawing routines because the
authors had the good sense to draw directly to appropriate memory
addresses rather than indexing the frame buffer with two indices.
They probably also know how to unroll loops - a technique that seems
to have thus far eluded you.
3. Nobody bothers with software line drawing anyway, because graphics
cards do this stuff in hardware anyway. Incidentally, this is also
interesting.
4. Nobody needs a faster line algorithm anyway. Antialiased lines,
lines with subpixel precision, thick lines, curves, and polygons are

Gernot Hoffmann

Dec 21, 2001, 6:55:31 AM12/21/01
to
friedl...@yahoo.com (Mike) wrote in message news:<a509b414.01122...@posting.google.com>...
> ....

> In fact, I did just that. Here's the first result Google returned. I
> didn't bother looking at any more:
>
> http://www.cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html
> ....

> Thank you for defining the abbreviation for us. It sounds like you
> .....

Unfortunately the Bresenham algorithm in Step 3 is wrong:
Retracing error, of course only for some start- and endpoint
configurations.
In Step 4 it is repaired in the Java applet, but I canÂ´t see
where in the code. Any help ?

Best regards --Gernot Hoffmann

None

Dec 22, 2001, 5:20:58 AM12/22/01
to
> poh...@aol.com (None) wrote in message news:<12124e47.01122...@posting.google.com>...
> > I did a check on all the algorithms, including "DDA line algorithms", and
> > all of them had a branch instruction in them. The only exception is EFLA.
> > Please list a URL with its source.
>
> In fact, I did just that. Here's the first result Google returned. I
> didn't bother looking at any more:
>
> http://www.cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html
>
> Note that the first attempts use exactly the same algorithm as yours,
> sans fixed-point. No branches inside the inner loop.

It also does not work. Use the applet at the bottom of it and try
drawing
any vertical line taller than wide. It has a hidden multiplication
in the call, did you notice that?

>
> seen this page, because you plagiarized the Wu source from it. Rather
> impolite of you to publish the code on your site without even
> bothering to cite the original source, don't you think?

I was just thinking the same thing but the other way around. But then
I looked at the Bresenham code and it doesn't look like the one on
http://www.edepot.com/algorithm.html

>
> > Some info: Wu and Bresenham algorithms are both have DDA components.
> > In fact all algorithms these days
> > use DDA. DDA just means digital differential analysis. DDA can be used
> > in circles, like addition can be used in circles. The algorithm is what
> > counts. DDA is just a term saying, as an analogy, use digital instead
> > of analog.
> >
>
> Thank you for defining the abbreviation for us. It sounds like you
> just looked it up. Other line algorithms use more sophisticated
> stepping algorithms than a straight DDA. Your algorithm consists
> solely of a loop with a DDA. I hate to break it to you, but your
> approach is generally the *first* one anybody bothers trying out
> before they event start to optimize. As a matter of fact, I did
> pretty much the same thing roughly a year ago to implement a realtime
> bitmap stretch. I can't post the source, since it's the property of
> my company, but I certainly never thought I had invented anything new.

Well, no one can force you to back up your statements. Many people
here
back down when challenged on their integrity.

We have yet to see the source to the algorithm from the person on this
thread. We also have yet to see the source to "wiley" and "other"
from
another person on the EFLA thread, and saying it was the slowest he
has seen.
And it looks like you also have a reason for not backing up your
claims.

EFLA is out there plain as daylight. It beat Wu and Bresenham. It
has no branches within the loop. And it is not tied to CPU
architectures.

>
> > I have another line algorithm that is faster than EFLA, but it uses
> > a different technique, with a builtin optimizer. Look for it in another
> > post. EFLA is unique in that it has an extremely tiny loop without branches.
> > The algorithm is also not tied to hardware (no assembly and memory layout
> > specifics).
> >
>
> No, you have one branch per pixel. That's how loops work. The reason
> for using double-step algorithms is that they can draw a line with
> fewer loop iterations. Wu, for example, draws four pixels per
> iteration, with one or two branches within the loop, giving fewer
> total branches than "your" algorithm.

The branch is only taken when the loop ends. Within the loop there
are no branches. Wu has a small optimization yes. Look for another
post with an algorithm that is faster than EFLA. (and EFLA is faster
than Wu and Bresenham). The next one has a built-in optimizer.

>
> > Because you have claimed EFLA's uniqueness is false, its your turn
> > to provide the source to the line algorithm in Whitechapel MG-1.
> > Otherwise, your claim is false.
> >
>
> No, it's not. It's a DDA, pure and simple. The cleverest thing in
> your loop is the use if fixed-point arithmetic, which other people
> suggested to you in this newsgroup when they saw you doing horrible
> things with floating-point. The page I linked to above tries using
> your approach almost as a first attempt.

The algorithm in the page does not even work for vertical lines. If
you wish to do comparisons, please find sources that actually do work.
But the applet and the overall explanations on that page look
interesting.
The page on EFLA shows evolution also and can be quite educational.

>
> Here's what the whole thing comes down to:
>
> 1. You haven't invented anything new.

EFLA never existed before. So yes it is new. And it is a working
version,
and it is faster than Wu and Bresenham.

> 2. You won't beat existing software line drawing routines because the
> authors had the good sense to draw directly to appropriate memory
> addresses rather than indexing the frame buffer with two indices.
> They probably also know how to unroll loops - a technique that seems
> to have thus far eluded you.

It already "beat existing software line drawing routines". That is
what
benchmarks are for. Look at http://www.edepot.com/algorithm.html

> 3. Nobody bothers with software line drawing anyway, because graphics
> cards do this stuff in hardware anyway. Incidentally, this is also
> interesting.

But it is important because graphic cards start out as software
algorithms.
They implement them. Note that the modern processor cards DO have
pipelines.
In fact 4 of them to do four renderings at one time.

> 4. Nobody needs a faster line algorithm anyway. Antialiased lines,
> lines with subpixel precision, thick lines, curves, and polygons are

All those are just layers above or below line algorithms.

Antialiased lines need line algorithms to locate the pixel before it
can
apply the antialias routine.

subpixel precision is the increasing of precision for the line
algorithm.

Thick lines are just parallel duplicated line algorithms.

Curves utilize line algorithms to connect the dots of the curve.

Polygons are created by line algorithms.

So, in light of these facts, line algorithms are important. Or
are you advocating that comp.graphics.algorithms should not exist?

None

Dec 22, 2001, 5:27:15 AM12/22/01
to
hoff...@fho-emden.de (Gernot Hoffmann) wrote in message news:<a815dbcf.01122...@posting.google.com>...

Apparently, three of them don't work on that page now that you add the
Bresenham. The one at http://www.edepot.com/algorithm.html contains
6 working ones. Do you have 2 working ones on your page?

Gernot Hoffmann

Dec 22, 2001, 8:22:28 AM12/22/01
to
poh...@aol.com (None) wrote in message news:<12124e47.0112...@posting.google.com>...
....

> It also does not work. Use the applet at the bottom of it and try
> drawing
> any vertical line taller than wide. It has a hidden multiplication
> in the call, did you notice that?

I have tested two BresenhamÂ´s which are published since many
years. Both have wrong retracing.
a) Kenny Hoff (1995)
b) The nice website with the applets (mentioned above)
I am very happy since five years with my own method.
http://www.fho-emden.de/~hoffmann/drawf11102001.pdf

Best regards --Gernot Hoffmann

Dave Eberly

Dec 22, 2001, 2:08:35 PM12/22/01
to
"Gernot Hoffmann" <hoff...@fho-emden.de> wrote in message

> I have tested two BresenhamÂ´s which are published since many
> years. Both have wrong retracing.

"Wrong retracing" may not be an issue. I use a
Bresenham's algorithm that does not "retrace" for
software rasterizers to interpolate the vertex attributes
of triangles along edges to set up for scan line
rasterizing. The edges are drawn/interpolated always
from minimum y to maximum y.

Christian Lange

Dec 22, 2001, 8:36:15 PM12/22/01
to
Hi all

I just wanted to mention that "Mr. None" has also invented an un-brekable
encryption algorithm. He even claims that brute force methods can not
break it ;)

And I thougt that things like encryption and verification of encrytion
algorithms was better left to experts in math and crytology... Silly me ;)

Best regards

Christian Lange

Donald Graft

Dec 22, 2001, 11:15:46 PM12/22/01
to
And he has also made the "most powerful calculator in the world"
and the "most accurate [Blackjack] implementation in the world".

Don

"Christian Lange" <cla...@nybro.dk> wrote in message news:3C25350F...@nybro.dk...

Mike

Dec 23, 2001, 1:15:39 AM12/23/01
to
poh...@aol.com (None) wrote in message news:<12124e47.0112...@posting.google.com>...

> > Note that the first attempts use exactly the same algorithm as yours,
> > sans fixed-point. No branches inside the inner loop.
>
>
> It also does not work. Use the applet at the bottom of it and try
> drawing
> any vertical line taller than wide. It has a hidden multiplication
> in the call, did you notice that?
>

These are lecture notes. They're not even an attempt to make an
industrial strength line drawing routine. The multiplication isn't
hidden; it's right there in plain sight, and it's not even the
bottleneck. I'm surprised you jumped all over that without even
noticing the call to round() and the extra float-to-int conversion.
As far as its robustness is concerned, this routine is intended as a
starting point. The author says quite explicitly that it doesn't
work, why it doesn't work, and uses that as a segue into the second
section. Incidentally, your routine has a hidden multiplication as
well. Did *you* notice it?

> > seen this page, because you plagiarized the Wu source from it. Rather
> > impolite of you to publish the code on your site without even
> > bothering to cite the original source, don't you think?
>
> I was just thinking the same thing but the other way around. But then
> I looked at the Bresenham code and it doesn't look like the one on
> http://www.edepot.com/algorithm.html
>

Right. Lecture notes from 1996 are plagiarizing your code. At worst,
this guy is copying from the same source you are.

> > No, you have one branch per pixel. That's how loops work. The reason
> > for using double-step algorithms is that they can draw a line with
> > fewer loop iterations. Wu, for example, draws four pixels per
> > iteration, with one or two branches within the loop, giving fewer
> > total branches than "your" algorithm.
>
> The branch is only taken when the loop ends. Within the loop there
> are no branches. Wu has a small optimization yes. Look for another
> post with an algorithm that is faster than EFLA. (and EFLA is faster
> than Wu and Bresenham). The next one has a built-in optimizer.
>

Which is one branch per pixel. Wu does less than one branch per
pixel.

> > No, it's not. It's a DDA, pure and simple. The cleverest thing in
> > your loop is the use if fixed-point arithmetic, which other people
> > suggested to you in this newsgroup when they saw you doing horrible
> > things with floating-point. The page I linked to above tries using
> > your approach almost as a first attempt.
>
> The algorithm in the page does not even work for vertical lines. If
> you wish to do comparisons, please find sources that actually do work.
> But the applet and the overall explanations on that page look
> interesting.
> The page on EFLA shows evolution also and can be quite educational.
>
>

Yes it does. You just flip the axes, as the author explains quite
clearly. That page is also designed to show evolution, but at least
he skipped over the rather ridiculous implementation which included a
divide as well.

> > Here's what the whole thing comes down to:
> >
> > 1. You haven't invented anything new.
>
> EFLA never existed before. So yes it is new. And it is a working
> version,
> and it is faster than Wu and Bresenham.
>

Again, it's just a DDA. Find me a DDA anywhere which does anything
any less sophisticated than your line drawing algorithm. A linear
interpolation is the simplest possible DDA out there, and you think
you invented it?

> > 2. You won't beat existing software line drawing routines because the
> > authors had the good sense to draw directly to appropriate memory
> > addresses rather than indexing the frame buffer with two indices.
> > They probably also know how to unroll loops - a technique that seems
> > to have thus far eluded you.
>
> It already "beat existing software line drawing routines". That is
> what
> benchmarks are for. Look at http://www.edepot.com/algorithm.html
>
>

No, it doesn't. You posted crippled routines which have no knowledge
of raster layout or optimizations even as basic as loop unrolling.

> > 3. Nobody bothers with software line drawing anyway, because graphics
> > cards do this stuff in hardware anyway. Incidentally, this is also
> > interesting.
>
> But it is important because graphic cards start out as software
> algorithms.
> They implement them. Note that the modern processor cards DO have
> pipelines.
> In fact 4 of them to do four renderings at one time.
>

The hardware is targetted to the task, not to be general-purpose.
found only in processors at least as advanced as the Pentium III, the
applicability to specialized hardware starts going way down.
Incidentally, "pipleline" has a completely different meaning when
you're talking about CPUs versus texture units, but you knew that,
right?

> > 4. Nobody needs a faster line algorithm anyway. Antialiased lines,
> > lines with subpixel precision, thick lines, curves, and polygons are
>
> All those are just layers above or below line algorithms.
>
> Antialiased lines need line algorithms to locate the pixel before it
> can
> apply the antialias routine.
>

Only a small part of the problem. That's why antialiased lines are
more interesting than what you have.

> subpixel precision is the increasing of precision for the line
> algorithm.
>
> Thick lines are just parallel duplicated line algorithms.
>

Running the same DDA multiple times in parallel? Do you have any idea

> Curves utilize line algorithms to connect the dots of the curve.
>

Or more sophisticated DDAs that plot pixels directly instead of
jumping between two different algorithms.

> Polygons are created by line algorithms.
>

Sorry, are you still stuck in the wireframe world?

> So, in light of these facts, line algorithms are important. Or
> are you advocating that comp.graphics.algorithms should not exist?

No, but we do appreciate intellectual honesty around here. First of
all, code optimization does not even fall under the heading of
'algorithms'. From an algorithmic standpoint, simply saying, "I get
fast line-drawing speed faster than my (if you're sticking to that
story) implementations of Bresenham and Wu using a fixed-point linear
DDA," would have described your algorithm and results in their
entirety. What you're doing here is akin to jumping on a mechanical
engineering board and claiming to have invented the wheel, challenging
posters to find patents that show otherwise.

Jukka Liimatta

Dec 23, 2001, 6:33:35 AM12/23/01
to
> Due to the popularity of the Extremely Fast Line Algorithm (EFLA),
> it was benchmarked against the most popular (Bresenham) and the
> most advanced (Wu) algorithm today.

And it was benchmarked against CRAP today!

> EFLA actually beat both Bresenham and Wu line algorithms
> in a rigourous benchmark consisting of 1 million lines
> on standard Pentium III machines.

And CRAP beat EFLA!

> Details on the benchmark are available at...
> http://www.edepot.com/algorithm.html

www.liimatta.org/misc/EFLAvsCRAP.cpp

The CRAP was roughly 4x faster than the EFLA! OMG... it must be the fastest
linedrawing in the UNIVERSE! ;-) ;-)

Come on, Mr.None, take it easy and don't post crap before you atleast TRY to
find out about previous art in line drawing, and this is for non-antialiased
lines, which are NOT interesting at all anyway. Heh, the AA line drawing
routine I use is actually *same speed* as EFLA for AA lines (adjustable
falloff curve, line intensity & color, etc..) ;-)

Merry christmas! ;-)

--
Jukka

Nemo

Dec 23, 2001, 6:30:19 AM12/23/01
to
On 23 Dec, Christian Lange wrote:

Wow. This is *really* embarrassing.

--
Nemo ne...@20000.org

Gernot Hoffmann

Dec 23, 2001, 11:23:37 AM12/23/01
to
"Dave Eberly" <ebe...@magic-software.com> wrote in message news:<TS4V7.75861\$RE3.12...@typhoon.southeast.rr.com>...
Sorry, correction:
http://www.fho-emden.de/~hoffmann/triangle04122001.pdf
G.Hoffmann

Gernot Hoffmann

Dec 23, 2001, 11:21:02 AM12/23/01
to
"Dave Eberly" <ebe...@magic-software.com> wrote in message news:<TS4V7.75861\$RE3.12...@typhoon.southeast.rr.com>...
> "Gernot Hoffmann" <hoff...@fho-emden.de> wrote in message
> > I have tested two BresenhamÂ´s which are published since many
> > years. Both have wrong retracing.
>
> "Wrong retracing" may not be an issue. I use a
> Bresenham's algorithm that does not "retrace" for
> software rasterizers to interpolate the vertex attributes
> of triangles along edges to set up for scan line
> rasterizing. The edges are drawn/interpolated always
> from minimum y to maximum y.

Dave:
I do the same.
http://www.fho-emden.de/~hoffmann/triangle09122001.pdf
Not necessary to have a look, but this document (280kBytes)
shows some results and especially very odd singular cases.

Correct code is just one statement more
and it is an issue, e.g. for wireframe models, where
edges of quadriliterals are drawn for convenience twice.

I know some technical CAD systems which draw many "dirty
pixels". One reason may be the wrong edge scanning by the
line algorithm, the other a not perfect scanline drawing.

Best regards and Merry Christmas ---Gernot Hoffmann

Mike

Dec 23, 2001, 11:43:14 AM12/23/01
to
Nemo <ne...@20000.org> wrote in message news:<a88758ed4a%ne...@20000.org>...

> On 23 Dec, Christian Lange wrote:
>
> > See this link: http://www.edepot.com/baseencryption.html
>
> Wow. This is *really* embarrassing.

Actually, I'd say it goes beyond embarassing to the sublime. If I had
a background in cryptography, I'm sure this would be a source of jokes
for months. Perhaps we have fallen for an extremely gifted troll?

Charles R. Bond

Dec 23, 2001, 3:12:48 PM12/23/01
to
I knew you'd be back. But why not shun the naysayers in the newsgroup

Gernot Hoffmann

Dec 23, 2001, 4:00:53 PM12/23/01
to
"Jukka Liimatta" <jukka.l...@twilight2d.com> wrote in message news:<a04fec\$378\$1...@news.kolumbus.fi>...

> Come on, Mr.None, take it easy and don't post crap before you atleast TRY to
> find out about previous art in line drawing, and this is for non-antialiased
> lines, which are NOT interesting at all anyway. Heh, the AA line drawing
> routine I use is actually *same speed* as EFLA for AA lines (adjustable
> falloff curve, line intensity & color, etc..) ;-)

Perhaps someone can PUBLISH now the best line algorithm
in pseudocode which is fast AND correct.
So far, some of the published methods are wrong and
the very fast and correct ones were not published
(but the appreciated autors had developed them 10 years ago).

Best regards --Gernot Hoffmann

Jukka Liimatta

Dec 23, 2001, 6:59:40 PM12/23/01
to
> Actually, I'd say it goes beyond embarassing to the sublime. If I had
> a background in cryptography, I'm sure this would be a source of jokes
> for months. Perhaps we have fallen for an extremely gifted troll?

Or let regulars at sci.crypt know about new algorithm and see what they
think of it.

--
Jukka

Jukka Liimatta

Dec 23, 2001, 7:24:17 PM12/23/01
to
> Perhaps someone can PUBLISH now the best line algorithm
> in pseudocode which is fast AND correct.

?

> So far, some of the published methods are wrong and
> the very fast and correct ones were not published
> (but the appreciated autors had developed them 10 years ago).

"appreciated authors" .. who are...? Which methods are wrong, and by what
criteria? Incorrect scanconversion? Riddles?

--
Jukka

Charles R. Bond

Dec 23, 2001, 7:29:31 PM12/23/01
to

I don't entirely agree with you that non-antialiased lines are NOT interesting.
However, I think the biggest problem with Mr. None is that he doesn't pay
much attention to detail -- like the actual behavior of his lines, as opposed to

his claims. His latest version, I think its up to D now, simply plots the wrong
pixels for many cases. To wit, when either 'x' or 'y' changes by only one pixel
for the span of the other, his algorithm either doesn't change at all, or
changes
at the wrong place. Try plotting (0,0)(1,9) with his algorithm... Then try,
(0,0)(-1,9).

Gernot Hoffmann

Dec 24, 2001, 8:37:38 AM12/24/01
to
"Charles R. Bond" <cb...@ix.netcom.com> wrote in message news:<3C2676EB...@ix.netcom.com>...

> I don't entirely agree with you that non-antialiased lines are NOT interesting.
> However, I think the biggest problem with Mr. None is that he doesn't pay
> much attention to detail -- like the actual behavior of his lines, as
> opposed to his claims. His latest version, I think its up to D now, simply
> plots the wrong pixels for many cases. To wit, when either 'x' or 'y'
> changes by only > one pixel for the span of the other, his algorithm either > > doesn't change at all, or changes at the wrong place. Try plotting (0,0)(1,9)
> with his algorithm... Then try 0,0)(-1,9).

Charles:

This is also my observation, letter #3 (if my code conversion is correct).
At least. Mr. None publishes his algorithms, whereas others boast much
(Mr.Mike in #9) but publish nothing.
A cool analysis of published algorithms would be a good style, and this
concerns especially wellknown methods which proved now to be wrong ,
Tutorial material is often partly wrong in the first pass (I really know
this), but in the long run the mistakes should be corrected.

Gernot Hoffmann

Dec 24, 2001, 8:46:42 AM12/24/01
to
"Jukka Liimatta" <jukka.l...@twilight2d.com> wrote in message news:<a05sjf\$j0q\$1...@news.kolumbus.fi>...

About the correctness of line algorithms:
Two algorithms are allowed to differ only in the location of a tran-
sition pixel for some configurations of start and endpoints.
All versions have to follow the rule: no larger deviation from the
straight line than 0.5 pixel.

The "Step 3" algorithm shows wrong retracing:
http://www.cs.unc.edu/~mcmillan/comp136/Lecture6/Lines.html

Pro-Engineer creates many dirty pixels. The scanconversion
is not perfect.

Best regards --Gernot Hoffmann

None

Dec 24, 2001, 12:40:56 PM12/24/01
to
"Dave Eberly" <ebe...@magic-software.com> wrote in message news:<TS4V7.75861\$RE3.12...@typhoon.southeast.rr.com>...
> "Gernot Hoffmann" <hoff...@fho-emden.de> wrote in message
> > I have tested two BresenhamÂ´s which are published since many
> > years. Both have wrong retracing.
>
> "Wrong retracing" may not be an issue. I use a
> Bresenham's algorithm that does not "retrace" for
> software rasterizers to interpolate the vertex attributes
> of triangles along edges to set up for scan line
> rasterizing. The edges are drawn/interpolated always
> from minimum y to maximum y.

I agree with you here. There are different algorithms to suit different
purposes. Take for example a line as follows...

***
***
**

It could also be drawn as...

**
***
***

Should a line always draw using one method? (top or bottom?) Or should it
depend on the initial vertex? For consistency, line algorithms could always
draw with three leading pixels either going right left up or down given
the same slope as above.

This would lead to consistency when multiple lines span out from one point.
You would rather it look like...

** **
*** ***
*** ***
** **

Rather than...

** ***
*** **
*** **
** ***

None

Dec 24, 2001, 12:46:21 PM12/24/01
to
"Donald Graft" <neu...@attbi.com> wrote in message news:<STcV7.698\$r73....@rwcrnsc51.ops.asp.att.net>...

> And he has also made the "most powerful calculator in the world"
> and the "most accurate [Blackjack] implementation in the world".
>
> Don

Charles R. Bond

Dec 24, 2001, 1:08:52 PM12/24/01
to
Now that there has been a benchmarking program supplied it's probably
time for a new thread. However, there's still a few comments worth
reiterating before extensive benchmarking is done.

First, I don't think anyone who works with graphics primitives would
disagree that the prime objective is to plot those pixels which are
closest to an ideal line. The midpoint algorithm, for examples addresses
exactly that as a fundamental goal. Mr. None's algorithm does NOT
meet that objective. If fails with any lines where the span of 'x' and 'y'
are significantly different. The Bresenham algorithm he benchmarked
DOES plot the correct pixels (given the inherent possible one-pixel
error for some cases mentioned earlier). A look at the code reveals
the reason None's code fails, and it's difficult to understand why
anyone would offer his code as a serious contender for a line draw
algorithm.

Second, retracing may or may not be problem. Again there is an
ambiguity in some cases: (0,0)-(1,4) where a pixel may lie at exactly
a half step from the ideal line. This can be solved, of course if it
happens to be of prime importance.

Third, there is an issue of whether the last pixel should be plotted.
For isolated lines the answer is yes. For polylines, it may be no.
As long as the specification for the lines is reasonable and clear,
many published algorithms DO work.

Now to some benchmarking. I took

None

Dec 24, 2001, 1:14:25 PM12/24/01
to
"Morten Ofstad" <morten@innerloop.*nospam*.no> wrote in message news:<9vsvg6\$v5e\$1...@troll.powertech.no>...
> Your EFLA is nothing new... Anyone involved in the demo scene knows this
> technique - I wrote similar code in 68000 assembly around 1992 and I would
> think that anyone interested in scan-conversion has written similar code.
>

The major point of EFLA is to showcase speedy algorithms not dependent on
hardware. For example, video memory layout and cpu instruction sets (like
assembly). Although I believe you that the 68k assembly is fast, it is
an implementation dependent on hardware. It is no longer a portable
algorithm. If the 68k becomes obsolete, so does your source.

But in any case, a good suggestion is to put the source to your code in
68k assembly here. Have you compared its speed to Intel assembly?

> The reasons why it is not interesting is 1) it's not totally accurate and 2)
> the desicion-logic in the other algorithms is easy to implement in hardware,
> so the penalty you see in software implemetations is not an issue.

The accuracy is simply a .5 roundoff. You can either round up or down.
If you wish, one line of code to EFLA will make it accurate for either
rounding up or down (your choice).

But why is Wu and Bresenham not published in assembly? Because they
are general algorithms like EFLA. They all use simple pixel calls.
The actual optimization can happen when you take the compiler output
and diddle with it on the hardware. I am sure you can optimize EFLA
in assembly once you know the hardware used and the instruction set
used as well. Note that once you code in assembly for the 68k, the
algorithm no longer works on any graphics card... because each graphics
card has its own instruction set (their own type of cpu).

>
> You claim that because your performance comparision does not use assembly
> language optimization it is more fair, while in fact the reverse is true -
> if it was using assembly language optimization, you would never code the
> desicion logic in Wu or Bresenham using conditional branches. I am not
> familiar with x86 architecture, but both MIPS and 68K have instructions like
> 'set less-than' that can be used to implement branchless desicion logic.

Yes, once you have the final hardware specifications, you can use fast
algorithms and implement them on it. optimizations can then happen at
that level. Perhaps you can start a thread on optimized EFLA in
assembly, and then compare the results with other algorithms in assembly.
(but you would have to state the CPU used, and then the algorithm would
be tied directly to that CPU for that implementation).

>
> Additionaly, scan-line conversion without anti-aliasing is not really being
> researched anymore because all interesting ideas have already been
> discussed...

Research or not, interesting or not, this is comp.graphics.algorithms.
Perhaps what you are saying is that...

1) you only like research'able algorithms
2) you believe "scan-line conversion without anti-aliasing" is not researched
3) you only like algorithms that are considered interesting to you

But in any case, could you post the "similar code in 68000 assembly?"
I am sure it would be up for interesting analysis

>
> m.
>
> "None" <poh...@aol.com> wrote in message

Charles R. Bond

Dec 24, 2001, 1:20:59 PM12/24/01
to
Sorry, the last post got away from me...

Anyway, I took the benchmark program provided by a
previous poster and ran a million lines (the default)
for None's code, Bresenham's, Wu's code, and my own.
The platform was a 450 MHz AMD K6-2 with 64M
memory. I normalized the results to treat None's code
as a reference, because I think the line count in the
benchmark is improperly scaled. The scale here is the
number of lines per second, relative to None's:

None 1.000
Bres 1.009
We 0.752
Bond 1.024

Thus, in my benchmark, both Bresenham and my own code
outperformed None's. Furthermore, they both plot the right
pixels, which none's code does not.

I also ran a benchmark at a reduced line count (by entering
100 on the command line.) The results are:

None 1.000
Bres 1.006
Wu 0.748
Bond 1.021

Now, I have no interest in publishing my own code, because
it is proprietary. However, since in my tests Bresenham
outperformed None it doesn't really matter. My purpose
here is compare and evaluate. I'm not making any claims
other than that I performed the tests on the platform above
using the software provided and I will certify these results.

None

Dec 24, 2001, 1:24:09 PM12/24/01
to
hoff...@fho-emden.de (Gernot Hoffmann) wrote in message news:<a815dbcf.01121...@posting.google.com>...
> hoff...@fho-emden.de (Gernot Hoffmann) wrote in message news:<a815dbcf.01121...@posting.google.com>...
> > poh...@aol.com (None) wrote in message news:<12124e47.01121...@posting.google.com>...

> > > Due to the popularity of the Extremely Fast Line Algorithm (EFLA),
> > > it was benchmarked against the most popular (Bresenham) and the
> > > most advanced (Wu) algorithm today.
> > > ...
> >
> Investigation continued, here for EFL-D:
>
> The algorithm uses a simulation of float by 32-bit Integer
> (ShiftLeft 16, ShiftRight 16). I wouldnÂ´t call this a "clean"
> programming style. Some numbers, e.g. the increments, need the
> 32-bit Integer number space, but itÂ´s not allowed to use pixel
> coordinates in the whole space.
> This is of course an academic objection, but I still believe
> that fundamental algorithms should be "clean".

yes, it would be an academic issue, the "clean"ness that is.

>
> I have converted the source code into Pascal, which requires
> some modifications.
> So, the next objections are based on the assumption, that the
> conversion is correct. If not, then I apologize in advance.
>
> a) the algorithm doesnÂ´t deliver the same results as Bresenham
> (represented by two other programs) under all circumstances.
> Note: the only allowed deviation is the location of transition
> points by one pixel - the ">" or ">=" definition.

Could you please post the pascal version here?
The location of transition is based on .5 roundoff. either up or down.
a single line to EFLA would make it round the way you think is "correct"
(up or down)..

> b) the forward/reverse match (retracing)is wrong -
> I observe offsets not only at transition points but on the
> whole line.

for lines like...

***
***
**

and

**
***
***

you can vote on which is more correct. consistency could also be
above? If you were to draw a star exploding from a point (or a x-fighter)...

*** ***
*** ***
** **
** **
*** ***
*** ***

would look better than...

*** **
*** ***
** ***

** ***
*** ***
*** **

So the correctness is subjective depending on the needs. EFLA plots
lines, and the algorithm at http://www.edepot.com/algorithm.html
does that and beat Wu and Bresenham without dependencies on hardware
and assembly speedups.

>
> Best regards ---Gernot Hoffmann

None

Dec 24, 2001, 2:46:57 PM12/24/01
to
> poh...@aol.com (None) wrote in message news:<12124e47.0112...@posting.google.com>...
>
> > > Note that the first attempts use exactly the same algorithm as yours,
> > > sans fixed-point. No branches inside the inner loop.
> >
> >
> > It also does not work. Use the applet at the bottom of it and try
> > drawing
> > any vertical line taller than wide. It has a hidden multiplication
> > in the call, did you notice that?
> >
>
> These are lecture notes. They're not even an attempt to make an
> industrial strength line drawing routine. The multiplication isn't
> hidden; it's right there in plain sight, and it's not even the
> bottleneck. I'm surprised you jumped all over that without even
> noticing the call to round() and the extra float-to-int conversion.
> As far as its robustness is concerned, this routine is intended as a
> starting point. The author says quite explicitly that it doesn't
> work, why it doesn't work, and uses that as a segue into the second
> section. Incidentally, your routine has a hidden multiplication as
> well. Did *you* notice it?

Can you point out that multiplication?

http://www.edepot.com/lined.html

There are only shifts and addition, which are faster than
float-to-int and muliplication.

If you are defending your post, then you should provide something that
works. Fix the algorithm in the URL if you must. The algorithm you
pointed out does not work. Simply draw a vertical line in the applet
below it (the first algorithm), it creates dots instead of a line
right?
So EFLA is unique. It works,
and it is branchless within the loop. And it beat Wu and Bresenham
without dependency on hardware instruction sets or memory layouts.
Wu and Bresenham also are not dependent on assembly and memory
layouts.

>
> > > I don't know why you bothered lying about this last bit; I know you've
> > > seen this page, because you plagiarized the Wu source from it. Rather
> > > impolite of you to publish the code on your site without even
> > > bothering to cite the original source, don't you think?
> >
> > I was just thinking the same thing but the other way around. But then
> > I looked at the Bresenham code and it doesn't look like the one on
> > http://www.edepot.com/algorithm.html
> >
>
> Right. Lecture notes from 1996 are plagiarizing your code. At worst,
> this guy is copying from the same source you are.

I believe you are in the same league as Mr. Bond here. In his case,
he mentioned that EFLA was the slowest algorithm, and provided false
analysis to deride an algorithm that actually beat Wu and Bresenham.
He also tried to compare a pixel by pixel algorithm to a graphics
card. In addition, he has failed to provide a benchmark, nor the
source to "foley" and "other" when challenged. Why?

Because the truth is...

EFLA beat both Wu and Bresenham (algorithms not dependent on hardware
implementations). Mr. Bond could not provide the source because
people could
see the truth that EFLA is the FASTEST he has seen...

The benchmark is at http://www.edepot.com/algorithm.html

>
>
> > > No, you have one branch per pixel. That's how loops work. The reason
> > > for using double-step algorithms is that they can draw a line with
> > > fewer loop iterations. Wu, for example, draws four pixels per
> > > iteration, with one or two branches within the loop, giving fewer
> > > total branches than "your" algorithm.
> >
> > The branch is only taken when the loop ends. Within the loop there
> > are no branches. Wu has a small optimization yes. Look for another
> > post with an algorithm that is faster than EFLA. (and EFLA is faster
> > than Wu and Bresenham). The next one has a built-in optimizer.
> >
>
> Which is one branch per pixel. Wu does less than one branch per
> pixel.

If you examine the benchmark (run it on your machine if you must),
EFLA beat Wu. Besides, the loop is for the whole line, and within
the loop there are no branches for EFLA. For Wu, there are at least
2 or 3 per loop cycle.

>
> > > No, it's not. It's a DDA, pure and simple. The cleverest thing in
> > > your loop is the use if fixed-point arithmetic, which other people
> > > suggested to you in this newsgroup when they saw you doing horrible
> > > things with floating-point. The page I linked to above tries using
> > > your approach almost as a first attempt.
> >
> > The algorithm in the page does not even work for vertical lines. If
> > you wish to do comparisons, please find sources that actually do work.
> > But the applet and the overall explanations on that page look
> > interesting.
> > The page on EFLA shows evolution also and can be quite educational.
> >

> > > Here's what the whole thing comes down to:
> > >
> > > 1. You haven't invented anything new.
> >
> > EFLA never existed before. So yes it is new. And it is a working
> > version,
> > and it is faster than Wu and Bresenham.
> >
>
> Again, it's just a DDA. Find me a DDA anywhere which does anything
> any less sophisticated than your line drawing algorithm. A linear
> interpolation is the simplest possible DDA out there, and you think
> you invented it?

Perhaps you do not know the meaning of DDA. It means Digital
Differential
Analysis. It does not apply strictly to lines. In fact it is used
in circles, elipses, etc. Wu and Bresenham both use DDA. To say
DDA is used in Wu, Bresenham, and EFLA is correct. To say that EFLA
is DDA is false. EFLA utilizes addition and other components to
implement
a fast line algorithm.

>
> > > 2. You won't beat existing software line drawing routines because the
> > > authors had the good sense to draw directly to appropriate memory
> > > addresses rather than indexing the frame buffer with two indices.
> > > They probably also know how to unroll loops - a technique that seems
> > > to have thus far eluded you.
> >
> > It already "beat existing software line drawing routines". That is
> > what
> > benchmarks are for. Look at http://www.edepot.com/algorithm.html
> >
> >
>
> No, it doesn't. You posted crippled routines which have no knowledge
> of raster layout or optimizations even as basic as loop unrolling.

Perhaps if "it doesn't" can you explain why the benchmark indicates
it still "beat existing software line drawing routines" like Wu and
Bresenham?

I believe you are copying Mr. Bond's technique of denial.
The benchmark indicates EFLA beat Wu and Bresenham, EFLA is the
Fastest.
You still say "No, it doesn't".

Mr. Bond says EFLA is the slowest.
EFLA beat Wu and Bresenham.

Note: Wu is the most advanced (published that is) algorithm, while
Bresenham is the most popular. They are not dependent on hardware,
nor video memory layout. EFLA is also not dependent on hardware, nor
video memory layout. EFLA beat both of them in the benchmark at
http://www.edepot.com/algorithm.html

So "Yes, it (EFLA) does" beat Wu and Bresenham. Further comments?

>
> > > 3. Nobody bothers with software line drawing anyway, because graphics
> > > cards do this stuff in hardware anyway. Incidentally, this is also
> > > the reason why your assumptions about processor architecture aren't
> > > interesting.
> >
> > But it is important because graphic cards start out as software
> > algorithms.
> > They implement them. Note that the modern processor cards DO have
> > pipelines.
> > In fact 4 of them to do four renderings at one time.
> >
>
> The hardware is targetted to the task, not to be general-purpose.
> When you claim that your routine takes advantage of processor features
> found only in processors at least as advanced as the Pentium III, the
> applicability to specialized hardware starts going way down.

Right, so when algorithms are dependent on assembly and video memory
layout,
the usefulness of the algorithm is decreased.

But in the case of EFLA and Wu and Bresenham, not having features
specific
to a hardware does not break the algorithm. For example, not having
pipelined
architectures does not break EFLA. But algorithms dependent on
video memory layout and assembly would break the algorithm if it were
to be run on different CPU's or different video memory layout.

EFLA takes advantage of features on the hardware if available. If not
available, it still works.

> Incidentally, "pipleline" has a completely different meaning when
> you're talking about CPUs versus texture units, but you knew that,
> right?

Perhaps you can elaborate the "different" meaning between CPU
pipelines
and texture unit pipelines. Or did you get confused and thought
the 4 texture units are a pipeline?

>
> > > 4. Nobody needs a faster line algorithm anyway. Antialiased lines,
> > > lines with subpixel precision, thick lines, curves, and polygons are
> > > about as low-level as anybody cares about right now.
> >
> > All those are just layers above or below line algorithms.
> >
> > Antialiased lines need line algorithms to locate the pixel before it
> > can
> > apply the antialias routine.
> >
>
> Only a small part of the problem. That's why antialiased lines are
> more interesting than what you have.

1) You think antialiased lines are more interesting than line
algorithms.

Ok noted.

Antialiased lines still need line algorithms to locate the pixel

before it can apply the antialias routine.

>

> > subpixel precision is the increasing of precision for the line
> > algorithm.
> >
> > Thick lines are just parallel duplicated line algorithms.
> >
>
> Running the same DDA multiple times in parallel? Do you have any idea
> what you're talking about here?

line algorithm begin
loop
plot(x,y)
plot(x,y-1)
plot(x,y+1)
end loop
line algorithm end.

see the parallel duplication within the line algorithm?

>
> > So, in light of these facts, line algorithms are important. Or
> > are you advocating that comp.graphics.algorithms should not exist?
>
> No, but we do appreciate intellectual honesty around here. First of
> all, code optimization does not even fall under the heading of
> 'algorithms'.

So you are saying that assembly and video memory layout should not
fall under comp.graphics.algorithms? I believe Mr. Bond and Jukka
would dissagree with you.

None

Dec 24, 2001, 3:11:15 PM12/24/01
to
"Jukka Liimatta" <jukka.l...@twilight2d.com> wrote in message news:<a04fec\$378\$1...@news.kolumbus.fi>...

> > Due to the popularity of the Extremely Fast Line Algorithm (EFLA),
> > it was benchmarked against the most popular (Bresenham) and the
> > most advanced (Wu) algorithm today.
>
> And it was benchmarked against CRAP today!
>
>
> > EFLA actually beat both Bresenham and Wu line algorithms
> > in a rigourous benchmark consisting of 1 million lines
> > on standard Pentium III machines.
>
> And CRAP beat EFLA!
>
>
> > Details on the benchmark are available at...
> > http://www.edepot.com/algorithm.html
>
> www.liimatta.org/misc/EFLAvsCRAP.cpp
>
>
> The CRAP was roughly 4x faster than the EFLA! OMG... it must be the fastest
> linedrawing in the UNIVERSE! ;-) ;-)
>

The algorithm you have described has a dependency on video memory layout.
EFLA, Wu, and Bresenham utilizes a pixel call and are not dependent on
video memory layouts. Or are you dissagreeing with Mike and that algorithms
should only contain hardware dependent routines?

But what you can do to fix it...

All video memory sets should call a pixel function instead like Wu, EFLA,
and Bresenham. Test to make sure it works and draws correctly.
Does it work in all different directions? Does it behave like the
bad code in the URL posted by Mike? Does it retrace correctly?
Is the benchmark exaggerated without source for verification (as Mr.
Bond tried)? After it is fixed, post the source so others can run for
verification. Anyone can look at the source now and note that the routine
you posted does not even call the pixel routine. If you wish to inline
the function call, inline all of the algorithms it is in comparison with.
pixel calls use up stack management time. What you have tried to do
is compare inlined and non-inlined code. Anyone with basic compiler
knowledge knows that inlined functions forgoes the stack handling and ends up
speeding up algorithms many times compared to non-inlined functions.

This is the same technique Mr. Bond tried. He compared pixel to pixel
algorithms with a graphics card. Shame on you.

Again, simply modify your algorithm (the one you copied from Abrash), to
utilize the same pixel call (not inlined) as Wu and Bresenham and EFLA.

None

Dec 24, 2001, 3:12:57 PM12/24/01
to
hoff...@fho-emden.de (Gernot Hoffmann) wrote in message news:<a815dbcf.01122...@posting.google.com>...

> "Jukka Liimatta" <jukka.l...@twilight2d.com> wrote in message news:<a05sjf\$j0q\$1...@news.kolumbus.fi>...
> > > Perhaps someone can PUBLISH now the best line algorithm
> > > in pseudocode which is fast AND correct.
> ?
> > > So far, some of the published methods are wrong and
> > > the very fast and correct ones were not published
> > > (but the appreciated autors had developed them 10 years ago).
> >
> > "appreciated authors" .. who are...? Which methods are wrong, and by what
> > criteria? Incorrect scanconversion? Riddles?
>
> About the correctness of line algorithms:

This correctness is subjective, as Dave Eberly pointed out.

None

Dec 24, 2001, 3:19:55 PM12/24/01
to
"Charles R. Bond" <cb...@ix.netcom.com> wrote in message news:<3C2676EB...@ix.netcom.com>...
> I don't entirely agree with you that non-antialiased lines are NOT interesting.
> However, I think the biggest problem with Mr. None is that he doesn't pay
> much attention to detail -- like the actual behavior of his lines, as opposed to
>
> his claims.

Yes, the claims are true. EFLA beat both Wu and Bresenham.
is the FASTEST line algorithm in the benchmark...

http://www.edepot.com/algorithm.html

His latest version, I think its up to D now, simply plots the wrong
> pixels for many cases. To wit, when either 'x' or 'y' changes by only one pixel
> for the span of the other, his algorithm either doesn't change at all, or
> changes
> at the wrong place. Try plotting (0,0)(1,9) with his algorithm... Then try,
> (0,0)(-1,9).
>

What you are noting here is simple round of .5
You can either round up or down. A single line change will make EFLA
plot up or down. As an example...

xxx
xxx
xx

xx
xxx
xxx

Which do you prefer? Simply add the single line and you get to choose.
Just because you subjectively prefer one over the other does not necessarily
mean one is correct or retraces correctly.

I remember you tried to compare a pixel by pixel routine to a graphics card.
Is this the same technique?

None

Dec 24, 2001, 3:27:32 PM12/24/01
to
Christian Lange <cla...@nybro.dk> wrote in message news:<3C25350F...@nybro.dk>...
> Hi all
>
> I just wanted to mention that "Mr. None" has also invented an un-brekable
> encryption algorithm. He even claims that brute force methods can not
> break it ;)
>
>
> And I thougt that things like encryption and verification of encrytion
> algorithms was better left to experts in math and crytology... Silly me ;)
>
> Best regards
>
> Christian Lange

Well, to this day, since the release, there has not been a single
brute-force attack or even a method of attack (theory) that is successful
against this type of encryption. Why? Because all existing Encryptions
utilize fixed cypherblocks. You can brute force those. But you cant
brute force dynamic algorithms. Just like you can't brute force
one-time-pad. So best regards to you also :) Read the math part in it.
If you understand that part, you understand the meaning of "brute force"
when applied to dynamic algorithms.

Chet Simpson

Dec 24, 2001, 3:30:57 PM12/24/01
to
poh...@aol.com (None) wrote:

Much like everything else this simple minded troll (aka 'none') has
spewed here, his blackjack implementation is also incorrect.

Q: What is wrong with his implementation of blackjack?
A: There is no cut.

Q: Is that all that is wrong with blackjack?
A: NO!, When the player busts, the dealer should NOT continue
dealing to himself.

Q: Is that all that is wrong with blackjack?
A: NO!, The shuffle mark is NOT exact, has varying placement, and
is different depending on decks used.

Q: Is that all that is wrong with blackjack?
A: NO!, When the player receives a blackjack the dealer should
NOT continue dealing to himself.

As to his quotes.....

"You WON'T find a blackjack program technically as accurate to the
original as this program."

Yes you will. In the Hoyle game pack and even online.

Jukka Liimatta

Dec 24, 2001, 5:19:34 PM12/24/01
to
> The algorithm you have described has a dependency on video memory layout.

No it doesn't. It just supports variable pitch, this means the code can be
adapted, but not limited to, directly writing into videomemory. If algorithm
meant for rasters doesn't implement well for physical raster implementation
(ie. memory), you're then on wrong tracks.

> EFLA, Wu, and Bresenham utilizes a pixel call and are not dependent on
> video memory layouts. Or are you dissagreeing with Mike and that
algorithms

Except brensenham is engineered in a way that when the implementation are
dependent on (video) memory layouts, they are feasible to implement
efficiently.

> All video memory sets should call a pixel function instead like Wu, EFLA,

When putpixel() is seen in "high performance" software implementation, that
shold be the first warning sign. What is done in hardware is entirely
different matter, as there the cost is not speed, but space. I doubt
hardware implementors will want to spend silicon (area) for calculations
which are reduntant (next pixel in horizontal direction is in the next

> Does it work in all different directions? Does it behave like the
> bad code in the URL posted by Mike? Does it retrace correctly?

It does work for all different directions, all 8 octants are covered, and
borders for both horizontal, vertical and diagonal lines are handled
correctly. The algorithm is old-school "lines begin and end at centers of
pixels", which is what yours does aswell. The modified bresenhman I posted
week ago was subpixel accurate, this is the same accuracy yours is, for the
fairness sake and as an example how EFLA could still be improved (4x of
speed increase to go).

Also, as the "correct retracing" point here has been raised on this thread,
for triangles/polygons, though, this is what a decent scanconverter should
indeed be aware of. This is called "subpixel accuracy", it simple means that
pixels is drawn, if it's center is inside the higher precision edge. This is
very cheap and easy to arrange in decent implementation.

1. adjust the x-coordinate at the top of edge so that it's at center of the
pixel in y-direction. Now when we advance to the next line, we can simply
add "1.0" to the y-coordinate when interpolating, and the x-coordinate is
always relative to the center of the pixel in y-direction.. so the decision
now if the pixel is inside or outside the edge is trivial-- choosing correct
rouding will take care of the issue automatically, choosing correct width
for the span to be drawn.

2. since the *drawn* edges are shifted (for "free"!) inside the drawn pixels
at edges, the gradients must be corrected to match the shifted edges. This
is called "subtexel accuracy".

With "subpixel" and "subtexel" keywords search engines can give much more
detailed information on the subject. The way I do subpixel and texel
correction is unorthodox compered to the most methods which are published in
various places. I use the "spatial correction" technique which is less
documented than the traditional methods, but the principle is still the
same.

> Is the benchmark exaggerated without source for verification (as Mr.
> Bond tried)? After it is fixed, post the source so others can run for

Exaggerated in what way, those are concrete results. You and everyone can
compile and run the code whenever it is most convenient for you:

www.liimatta.org/misc/EFLAvsCRAP.cpp

them, because they were empty in the source you provided, FYI.

> verification. Anyone can look at the source now and note that the routine
> you posted does not even call the pixel routine.

Ofcourse it does not, that's how graphics algorithms are implemented in the
real-world, where people want fastest possible performance. I told you
that's the way to do it. I know it's unfair for your routine, but I told
HOW CAN WE MAKE A COMPETITIVE IMPLEMENTATION OF IT.

That's what this all comes down to in the end of the day: implementations.
Can yours be implemented so that it can beat 10-year old code or not. Like I
said, the ball's in your court- you have to prove it can be done, as I
didn't find immediately very efficient way to implement EFLA with addressing
logic embedded into the control loop. But it's not my job anyway, it's
yours.

> If you wish to inline the function call, inline all of the algorithms it
is in comparison with.

I did time EFLA with inlining for the pixel plotting, it did not help very
much. The problem is something completely different, I pointed out these
flaws in multiple replies aswell. I am not addicted to repeating myself over
and over again.

> pixel calls use up stack management time. What you have tried to do
> is compare inlined and non-inlined code.

Hey, it's your code.. improve it and beat mine, though, an advance warning
that inlining won't do EFLA much good, it's still some way off the
performance target.

> Anyone with basic compiler knowledge knows that inlined functions forgoes
> the stack handling and ends up speeding up algorithms many times compared
> to non-inlined functions.

I have more than basic compiler knowledge. I have said many, many times that
if you want to profile your code fairly, write it in a way that you don't
have to complain I have unfair advantage. I told you: "don't come whining to
me if...", you can check my previous contributions to the thread if you
did that anyway, didn't you?

Here's the premilinary results, pixel() inlined in EFLA:

EFLA: 2205.100 lines/sec
CRAP: 8250.825 lines/sec

The inlining didn't help much, like I predicted. Fix your code and repost
it, then we can continue the discussion.

> This is the same technique Mr. Bond tried. He compared pixel to
> pixel algorithms with a graphics card.

No I didn't. I adapted the "crap" into your benchmarking sourcecode. You did
draw 1,000,000 lines into 1000x1000 buffer in system memory. It was your own
benchmark, don't troll the blame on me.

> Shame on you.

Why, because I have common sense where implementing graphics algorithms go?
I have shared my knowledge in this thread, I gave you more handicap than you
deserve.

> Again, simply modify your algorithm (the one you copied from Abrash), to
> utilize the same pixel call (not inlined) as Wu and Bresenham and EFLA.
> Then post your source again.

No, you modify yours to access memory as memory, not 2D array-- that's what
everyone I know does, sooner or later. That's my whole POINT-- your
algorithm is not well implementable efficiently. If you want to prove me
wrong, implement it as well as you can, and don't handicap it with arbitrary
restrictions like you have now done.

Then we will have a fair comparison, but my point is not fairness, it's that
my proposed implementation can be unfairly implemented efficiently while
yours cannot.

--
Jukka

Charles R. Bond

Dec 24, 2001, 8:24:57 PM12/24/01
to

None wrote:

> "Charles R. Bond" <cb...@ix.netcom.com> wrote in message news:<3C2676EB...@ix.netcom.com>...
> > I don't entirely agree with you that non-antialiased lines are NOT interesting.
> > However, I think the biggest problem with Mr. None is that he doesn't pay
> > much attention to detail -- like the actual behavior of his lines, as opposed to
> >
> > his claims.
>
> Yes, the claims are true. EFLA beat both Wu and Bresenham.
> Your confirmation is noted this time.