World's fastest line algorithm (EFLA) Beats Wu and Bresenham
None
it was benchmarked against the most popular (Bresenham) and the
most advanced (Wu) algorithm today.
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
> 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.
Your code is very short.
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
> 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.
> > ...
>
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
Ian Kemmish
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
> In article <12124e47.01121...@posting.google.com>, poh...@aol.com
> 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
> 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.
Otherwise, your claim is false.
gordy
> 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
> 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.
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?
> 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
the reason why your assumptions about processor architecture aren't
interesting.
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.
Gernot Hoffmann
> ....
> 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
Very interesting link, good page.
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
> > 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?
>
> 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
>
> > 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
> 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.
> 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.
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
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
....
> 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
news:a815dbcf.01122...@posting.google.com...
> 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 Eberly
ebe...@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com
Christian Lange
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 ;)
See this link: http://www.edepot.com/baseencryption.html
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
and the "most accurate [Blackjack] implementation in the world".
Don
"Christian Lange" <cla...@nybro.dk> wrote in message news:3C25350F...@nybro.dk...
Mike
> > 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?
> > 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.
> > 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
> > 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.
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
> > 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.
> 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?
> 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
> 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
> See this link: http://www.edepot.com/baseencryption.html
Wow. This is *really* embarrassing.
--
Nemo ne...@20000.org
Gernot Hoffmann
Sorry, correction:
http://www.fho-emden.de/~hoffmann/triangle04122001.pdf
G.Hoffmann
Gernot Hoffmann
> news:a815dbcf.01122...@posting.google.com...
> > 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
> 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
and license your code to Microsoft? You could make millions!
Gernot Hoffmann
> 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
> 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
> 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
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
> 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)
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 ,
about the retracing.
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
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
> news:a815dbcf.01122...@posting.google.com...
> > 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
> And he has also made the "most powerful calculator in the world"
> and the "most accurate [Blackjack] implementation in the world".
>
> Don
http://www.edepot.com/win95.html
http://www.edepot.com/blackjack.html
Charles R. Bond
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
> 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
> news:12124e47.01121...@posting.google.com...
Charles R. Bond
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
> 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
subjective. should the algorithm consistently start with one of the
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
>
> > > 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.
Your statement here indicates...
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
> > 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.
Then post your source again.
None
> "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
> 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. Note your agreement that EFLA
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
>
> 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 ;)
>
> See this link: http://www.edepot.com/baseencryption.html
>
> 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
>http://www.edepot.com/win95.html
>http://www.edepot.com/blackjack.html
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
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
addressable unit of memory).
> 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
Btw. your source in the webpage had broken #include -statements, had to fix
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
about this very many times-- look at your algorithm from that perspective:
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
like. Now you did what I advices you well ahead in advance not to do, 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
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. Note your agreement that EFLA
> is the FASTEST line algorithm in the benchmark...
Please do not misrepresent my findings. I found that your code is both
slower than Bresenham and plots the wrong pixels.
> 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 prefer to plot the correct pixels. This is not subjective or cosmetic. Alwaysplot the pixel nearest
to the intended line.
> I remember you tried to compare a pixel by pixel routine to a graphics card.
> Is this the same technique?
>
You misunderstood the comparison. I compared the compiler output of yourroutine to that of Bresenham.
The compiler output is the code which is
actually executed. If it takes more processor cycles, it takes longer. See how
simple???
Anyway, you now have the results of my tests using your code and the
benchmark you provided. It does NOT show your algorithm is faster!
It shows it is slower than Bresenham on an AMD K6-2 running at
450 MHz with 64M memory. If you have a problem with the results,
don't shoot the messenger. It's your code, your benchmark, you lose.
Mike
> At least. Mr. None publishes his algorithms, whereas others boast much
> (Mr.Mike in #9) but publish nothing.
*ahem* Exactly what 'boast' did I make? All I've ever claimed was
that Mr. None's approach has been taken before and that he still has
much room for improvement. I never said anything to the effect of "I
know how to write a world-class line rasterizer"; I've simply pointed
out the more obvious holes. Personally, I think CRAP would beat the
pants off anything I would come up with on my own.
None
> poh...@aol.com (None) wrote:
>
> >http://www.edepot.com/win95.html
> >http://www.edepot.com/blackjack.html
>
> 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.
Actually, the cut is not needed because they only exist so
that players who think the dealer may have a method of looking
at the first few cards in the shoe after shuffle can cheat.
Since there is no shoe, looking at the first few cards are irrelevant.
And with the option to set the number of shuffle times, an increase
can be the option used to emulate the cut.
>
> Q: Is that all that is wrong with blackjack?
> A: NO!, When the player busts, the dealer should NOT continue
> dealing to himself.
Not true. Other players, or other hands might still be in progress.
The dealer must always continue dealing until all hands and all
other players are done.
>
> 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.
Yes, that is why the shuffle mark is settable on the main screen.
For different decks, simply set the shuffle mark desired.
>
> 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.
Not true. The dealer should continue dealing to other hands and other
players.
The features....
Initial money you possess.
Minimum Bet
Maximum Bet
Number of decks
Shuffle Mark
Shuffle Times
Blackjack Pay:Bet ratio
Maximum hands (splitting)
Dealer hits soft 17
Double Down
Split Ace
Even Money
Insurance
Surrender
1:1 pay on split blackjack
one card on split ace.
leaving table.
http://www.edepot.com/blackjack.html
None
>
> 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.
I agree that many people just boast. Your comments about Mr. Mike
is true, but I believe he is in the same league as Charles (Bond). Boasts
amount to nothing without proof. As a test... ask him to provide
sources or benchmarks. His first response was "analysis" is benchmark.
Now his response is the sources are proprietary, and can't be examined.
I believe both can benefit from your advice.
> A cool analysis of published algorithms would be a good style, and this
> concerns especially wellknown methods which proved now to be wrong ,
> about the retracing.
> Tutorial material is often partly wrong in the first pass (I really know
> this), but in the long run the mistakes should be corrected.
Although they are offered as educational material. Learning
something wrong the first time is detrimental to the person learning
the material. The learning curve usually is aggressively increased
with wrongful introductory material. Besides, Mr. Mike mentioned the
material is from 1996, so it must have had a number of years and passes where
it was used as tutorial material. What he has failed to do was analyze the
material he was presenting (the URL in this case), in this case as you
pointed out it had numerous errors and the branchless version at the top
did not even work for vertical lines.
None
> 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:
You have not provided a proper benchmark. What is lacking are as follows...
1) Source to Wu.
2) Source to Bresenham
3) Source to EFLA
4) Source to your code.
5) Source to benchmark.
I have provided all for anyone to run on their machines. EFLA beat
both Wu and Bresenham. In fact, you can see the exact data at...
http://www.edepot.com/algorithm.html
In plain daylight you can examine the sources to see that they all
call the same putpixel routine. You can examine the main loop.
You can examine the routines to draw in all different directions.
You can examine the benchmark data (lines total, lines drawn, and
lines per second).
There are no normalizing. No skewing of data. No hiding of data.
Everything is there. A simple press of the compile button on any
compiler will compile the sources and run on any machine for self benchmark.
So simply do as follows...
Provide a proper benchmark. What are lacking are as follows...
1) Source to Wu.
2) Source to Bresenham
3) Source to EFLA
4) Source to your code.
5) Source to benchmark.
For more advice see the thread response to Jukka on how to provide
accurate benchmark data. You need to make sure that the environment is
correct (all using the same putpixel call). Make sure they are the same type
(all not dependent on hardware). Make sure all data is provided (the raw
data like lines drawn, number of seconds, and lines per second).
Or did you copy him and modify the sources yourself so that your code
or other code uses inlined pixel calls and direct video memory sets and
leave other using the actual pixel call? And I find it odd that Jukka
is at least able to provide the source to his benchmark, and yet you
have provided nothing. If you are trying to compare apples and oranges again,
like comparing pixel-to-pixel functions to graphics cards, then your statements
amount to nothing to boasts and nothing more.
EFLA, on the other hand has been benchmarked. The url is at
http://www.edepot.com/algorithm.html
EFLA beat both Bresenham and Wu.
The sources to Wu, Bresenham, EFLA, and the benchmark are all provided
at that URL. Included are data showing the actual lines drawn, the
time taken, and lines per second. In addition, the actual benchmark
source can been seen.
None
> 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. Note your agreement that EFLA
> > is the FASTEST line algorithm in the benchmark...
>
> Please do not misrepresent my findings. I found that your code is both
> slower than Bresenham and plots the wrong pixels.
If you think one is wrong, simply add the .5 round either
up or down and you have what you think is correct.
As for the benchmark with both Bresenham and Wu, again the URL is
at http://www.edepot.com/algorithm.html
EFLA beat both Wu and Bresenham.
Included are sources for Wu, Bresenham, and EFLA and the benchmark for
anyone to compile and benchmark. You have yet to provide any sources.
Is there a reason why?
>
> > 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 prefer to plot the correct pixels. This is not subjective or cosmetic. Alwaysplot the pixel nearest
> to the intended line.
But you did not answer the question. Both have the same starting and
ending point. But plot differently. Which is correct?
>
> > I remember you tried to compare a pixel by pixel routine to a graphics card.
> > Is this the same technique?
> >
>
> You misunderstood the comparison. I compared the compiler output of yourroutine to that of Bresenham.
> The compiler output is the code which is
> actually executed. If it takes more processor cycles, it takes longer. See how
> simple???
Not true, you failed to provide the source to the supposedly "compiler output".
You hinted at the hand optimization with statements of "like" and "should".
In addition, cycle count based on instruction set do not indicate actually
cycles needed to plot the whole line. Only the actual running of the
program does this. The pipeline shaves off cycles when run. Perhaps this
is why you declined to provide the sources or the benchmark for the program
when run? Because EFLA beat both Wu and Bresenham. The data
is at http://www.edepot.com/algorithm.html
>
> Anyway, you now have the results of my tests using your code and the
> benchmark you provided. It does NOT show your algorithm is faster!
> It shows it is slower than Bresenham on an AMD K6-2 running at
> 450 MHz with 64M memory. If you have a problem with the results,
> don't shoot the messenger. It's your code, your benchmark, you lose.
You have failed to provide the sources to...
Wu, Bresenham, EFLA, your code, and the benchmark.
Jukka did you one better and posted the source, but as you can see...
he modified the code so that
only his "crap" algorithm used the inlined video memory sets while the
others use the plain put pixel routine. He had to do this to skew
the data so that his algorithm won. function calls and inlined function
calls are about 5 to 10 times difference in performance. Just
like you tried to compare a pixel-to-pixel function call to a graphics
card and tried to pass off that as a legitimate benchmark.
Christian Lange
None wrote:
> 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 ;)
> >
> > See this link: http://www.edepot.com/baseencryption.html
> >
> > 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.
There have been no (brute force) attacks on your algorithm because it is so insanely stupid
(excuse my "french") that no-one (except maybe yourself) has ever encrypted any vulnerable
data with it ;)
To "Mr. None": I will not ever answer your comment to this post since it will surely be
waisted on someone like you.
To all others: i'm sorry if i have do not use 100% correct english in this post, but I am
sure you will have fewer troubles understanding it that "Mr. None"
Best regards
Christian Lange
Christian Lange
> 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 ;)
> >
> > See this link: http://www.edepot.com/baseencryption.html
> >
> > 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.
Hmm. try posint your "findings" to sci.crypt...... I think they will laugh as much about
your "encryption" as all of us laugh of your "line draing"....
BTW the "-marks is used to signal that what is in-between is a joke.
And "Mr. None"'s new DDA algorithm (which he invented all by him self) is violating my
patent on addition ;)
To all others: I seldomly post to news groups, but this is to much.... If my posts are to
tough, please let me know (I'm not trying to offend anyone - and "Mr. None" doesn't seem to
be offended by anything, not even facts ;) - so I hope that I'm on safe ground yet)
Best regards
Christian Lange
Christian Lange
"Charles R. Bond" wrote:
> I knew you'd be back. But why not shun the naysayers in the newsgroup
> and license your code to Microsoft? You could make millions!
Hmmm, if we all get together we can make some even more bad code to sell
them..... Then "Mr None" will not have a chance ;)
Best regards
Christian Lange
None
> > 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.
Any algorithm can be tuned for specific hardware. Just like you can find
speedy instructions to a specific type of hardware and only use those
in your algorithm. But then this is just a test of how good you are
in using those instruction sets or architecture, not how good the
algorithm is. If the hardware becomes obsolete, then so is the algorithm.
Are you saying Wu and Bresenham are on the wrong track because they
both are not hardware dependent like EFLA?
>
>
> > 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.
Although I have yet to see you provide to proof to this...
Yes, and so is EFLA for pipelined superscalar CPUs. And the bonus is
that if the hardware is obsolete, the algorithm still works on any
platform that is not obsolete. And EFLA beat Bresenham.
>
>
> > 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
> addressable unit of memory).
I am sure the hardware implementors will optimize for their graphics card
accordingly. Or add speedy previously non-existing pieces of logic to
speed up slow parts. But you see, at that level the hardware is
available and sometimes changed to adapt to purpose. Do you see voodoo
cards being sold these days in high quantities? Obsolete right?
The algorithms on them are obsolete also. But Wu, Bresenham, and EFLA
is still out there chugging along awaiting implementation on the next great
hardware. Why? because they are not video memory layout specific, nor
instruction set specific.
>
>
> > 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).
EFLA does not need the redundant octant checking. Only initial conditions
are needed. If you take a look at EFLA, you will find that is is extremely
tiny in the loop and setup. And note that because EFLA is subpixel accurate,
Bond objects to this. I see you and him are on a disagreement on this.
EFLA, being subpixel accurate is indeed a good thing. As now you can
round up or down to suite that particular line your wish...
**
***
***
or
***
***
**
>
> 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.
Yes, there are many ways. For EFLA, a simple line addtion will round it up
or down. Additionally, if required a line can ALWAYS
start from *** instead of ** either going left or right. (the same
with vertical versions).
The problem with this is that if you are drawing a star explosion...
** **
*** ***
*** ***
o
*** ***
*** ***
** **
looks better than...
** ***
*** ***
*** **
o
*** **
*** ***
** ***
the latter may meet certain triangulation characteristics if
you do a redundant triangle retrace for two triangles next to each other,
but it is not consistent for people who need to draw simple consistent shapes
like the X above that has the initial point near the "o".
>
>
> > 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
Right, and they can also see that Wu, Bresenham, and EFLA all use the pixel
call function, while yours skips this and does video memory set....
Different environment, wrongful result.
>
> Btw. your source in the webpage had broken #include -statements, had to fix
> them, because they were empty in the source you provided, FYI.
All the #include needed are provided. if you think they are broken then I
refer you to the person who coded the original benchmark. The
algorithms to the EFLA, WU, and BRESENHAM do not require any #include statements
.
>
>
> > 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
> about this very many times-- look at your algorithm from that perspective:
> HOW CAN WE MAKE A COMPETITIVE IMPLEMENTATION OF IT.
I have another version that has a built in optimizer. That one is
even faster, even using the same pixel call. But even the EFLA here
is faster than Wu and Bresenham.
>
> 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.
>
But you already stated that you were able to double the speed already.
Anyone can simply inline the pixel call.
>
> > 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.
And those are answered before as well, and I will not repeat here either.
>
>
> > 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.
Modifications of the code to EFLA, Wu, and Bresenham makes them not
EFLA, not Wu, and not Bresenham. They are published using the same
environment (non-hardware dependent). They are judged in that context.
If you are not able to beat their strength on the bases of that environment,
your benchmark data is not correct and is invalid.
>
>
> > 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
> like. Now you did what I advices you well ahead in advance not to do, 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 only reflects the overhead from the stack management.
Similarly the overhead of a function call or inlining. As mentioned before
inlining and non-inlining is the difference between 5 and 10 times the
performance.
Make your algorithm use the same putpixel call, and then come back and
see how strong it is.
>
>
> > 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.
It was not my benchmark. It was done by a third party. If you wish to
critique how the algorithms perform under a specific operating system
or environment that is getting out of the hand. All of them run on the
same benchmark, the same OS, and the same hardware (the environment),
and all use the putpixel call. Blaming the the same environment under the
same condition for all three algorithms is moot.
>
>
> > 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.
that is just it, you provided handicap to other programs based on the
modifications to the environment. You needed to change the original published
algorithms like Wu and Bresenham to work under the new hardware dependency.
This ends up invalidating their algorithms (as well as EFLA), as this is
now YOUR handicap to the programs, and benchmarks now do not reflect accurate
result.
>
>
> > 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.
The importance of the benchmark is the speed of the algorithm, not the
speed of the put pixel routine (whether inlined, or not, or directly
to a specific video memory layout). Why is is so hard to simply try
to implement an algorithm using the call and beat the three algorithms?
Why resorts to tricks and sleigh of hand by making only certain algorithms
use the same pixel routine, while yours bypasses it?
Mikko E. Mononen
>The algorithms on them are obsolete also. But Wu, Bresenham, and EFLA
>is still out there chugging along awaiting implementation on the next great
>hardware. Why? because they are not video memory layout specific, nor
>instruction set specific.
and quote from your web site:
"Branch instructions cause significant CPU cycle delays as the pipeline
gets flushed of all instructions during a mispredicted branch. This delay
is very significant as modern superscalar CPU's have longer and longer
pipelines. A pipeline containing 10 stages would reduce 10 cycles per loop
if there are no branch instructions that causes a pipeline flush."
Arent you shooting your own feet here? You make major assumptions about
the hardware, but then when other people does those assumptions (refering
to the putpixel fight) then you try to nail them down?
Your code is supposed to be fast if the brach is slow on the hardware.
That's the fact your superfastlinesthigie is based on. What if the
braching is free on the target platform and division takes three seconds?
Then Mr. B's algo may beat yours.
My final statement is that you cannot make world fastest line algorithm
without stating the platform. You just can't compare theory in this case.
Bresenham's line algorithm is based on the fact that division was very
very slow back then. I haven't investigated Wu's algorith into detail so I
only guess that it's purpose is to draw as good lines as possible and also
avoid the division. And finally your algo uses the fact that on current
hardware division is faster than it used to be and also that branching
kills the code cache. So there's your hardware independency. So if you are
so worried about the cache why didnt you also optimize your code for
read/write cache as well? Jukka's CRAP also did took care of that.
Also I dont understand why you have to bash your "invention" so much? I
hate the attitude that someone claims somethign being his/hers own even if
almost everybody is using it but none has claimed to be his/hers own idea.
Yep... I do puke when I read my slashdot and see that someone has
patendeted the "using a rolling device to browse hypertext content"
shit...
just my 0.02 euros... or something.
--memon
.ps. This is pointless, life sucks, I'll shut up.
Jukka Liimatta
> Are you saying Wu and Bresenham are on the wrong track because they
> both are not hardware dependent like EFLA?
I have not suggested such a thing, you have a wild imagination.
> 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
Aha. And how is it supposed to time the algorithm, if plotting the pixel in
slowest possible way (putpixel) is taking 2/3 of the time, or worse, more?
> Yes, and so is EFLA for pipelined superscalar CPUs. And the bonus is
> that if the hardware is obsolete, the algorithm still works on any
> platform that is not obsolete. And EFLA beat Bresenham.
Aha, whatever, I'm not using bresenham myself, and btw. you can write
branchless bresenham, so it is "for pipelined superscalar CPU" too. This is
a shining example how you don't really listed on other posters, you're too
much concentrated around yourself.
<lot of crap deleted about how hardware 3D accelerators should be
implemented.. it's obvious the poster does not have a clue about the
subject>
> > It does work for all different directions, all 8 octants are covered,
and
>
> EFLA does not need the redundant octant checking. Only initial conditions
> are needed. If you take a look at EFLA, you will find that is is
extremely
Neither does CRAP, I just mentioned that all 8 octant are *tested* and found
to be working. You asked if it was working or not, I replied yes, it is
working, then you attack the code for "testing for all octants", no, the
code does not test all octants. I did.
> tiny in the loop and setup. And note that because EFLA is subpixel
accurate,
> Bond objects to this. I see you and him are on a disagreement on this.
> EFLA, being subpixel accurate is indeed a good thing. As now you can
> round up or down to suite that particular line your wish...
This shows you don't understand what subpixel accuracy is, how DARE you
speak with authority on subjects you don't clearly have any understanding
whatsoever. Your linedrawing is not subpixel accurate, because...
efla(..., int x1, int y1, int x2, int y2...
Integer line endpoints cannot be subpixel accurate by definition, which is,
that the decimal coordinates of the endpoints are taken into account. Well,
if (0.5,0.5) are the decimal coordinates at both ends, then the line
bounding box width and height are integers, no decimals. Subpixel accuracy
in practise means, that if either endpoints moves even a fraction, say, 0.05
pixels in any direction, the scanconversion takes this into account.
But whatever, I'm just wasting breath, you aren't LISTENING.
> the latter may meet certain triangulation characteristics if
> you do a redundant triangle retrace for two triangles next to each other,
> but it is not consistent for people who need to draw simple consistent
shapes
> like the X above that has the initial point near the "o".
First of all, line algorithms are NOT used for scanconverting polygons or
triangles, because they are inefficient for the purpose.
***
***
***
That is what a line algorithm would do to an edge, where we want:
*
*
*
The scanline between left and right edge is filled, there is NO need for
line algorithm to scan all pixels in an edge.
> Right, and they can also see that Wu, Bresenham, and EFLA all use the
pixel
> call function, while yours skips this and does video memory set....
> Different environment, wrongful result.
You're timing putpixel() not line algorithm, wondering why the results are
all in same ballpark, the differences between EFLA, bresenham, wu, etc. is
in range of 10% ... while mine is over 300% faster, why is that?
> > Btw. your source in the webpage had broken #include -statements, had to
fix
> > them, because they were empty in the source you provided, FYI.
>
> All the #include needed are provided. if you think they are broken then I
> refer you to the person who coded the original benchmark. The
> algorithms to the EFLA, WU, and BRESENHAM do not require any #include
statements
No, they are NOT provided at all. W/O all three I fixed, the benchmark does
not compile at all. In your page the source has:
#include
#include
#include
.. as it is above, the code didn't even compile, so I had to fix it. Really.
Why can't you accept responsibility for code which you have posted on your
website. The code is supposed to compile, yet it does not, so you're wrong,
period.
> I have another version that has a built in optimizer. That one is
> even faster, even using the same pixel call. But even the EFLA here
> is faster than Wu and Bresenham.
EFLA can be faster than those, but it's slower than CRAP, too bad for you.
> But you already stated that you were able to double the speed already.
> Anyone can simply inline the pixel call.
Yes, by me, not by you. I want you to write competitive version of the EFLA.
I have shown what performance can be expected in real-world from a line
algorithm. You haven't yet delivered.
Why it is so hard to just go and fix your implementation? Why do you have to
whine to me like I hurt your feelings very bad, wouldn't it be easier to go
and fix your line drawing code and then come here and show me once and for
all! Then I would be embarassed and go back to the hole where I crawled
from!
But no.. you just have to make a public display, instead of coming back and
beating CRAP! (hey, wouldn't it be nice if I renamed CRAP into MEAT? ;-)
> Modifications of the code to EFLA, Wu, and Bresenham makes them not
> EFLA, not Wu, and not Bresenham. They are published using the same
> environment (non-hardware dependent). They are judged in that context.
> If you are not able to beat their strength on the bases of that
environment,
> your benchmark data is not correct and is invalid.
Oh good grief. The runlength slice line drawing is designed to draw the
spans the line consists of in a single internal loop, avoiding ANY overhead
whatsoever in the most performance critical section of the code.
Tearing that code open, and converting the address to (x,y) coordinate pair,
only to re-generate the address from them would be very stupid. I refuse to
be stupid. How do you even suggest such stupidity?
For the record, that's how the "line algorithm" works- the raster position
in buffer+(y*pitch+x) is internal to the algorithm. This will not get
"obsolete", as you say, very quickly as long as memory is used to implement
rasters.
> > 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 only reflects the overhead from the stack management.
> Similarly the overhead of a function call or inlining. As mentioned
before
> inlining and non-inlining is the difference between 5 and 10 times the
> performance.
Heh, heh, no it doesn't... this is results for the version where the call to
pixel() was inlined. Quote: "Here's the premilinary results, pixel() inlined
in EFLA:"
Can't read english? The pixel() was inlined (by moving the code INSIDE EFLA,
not using inline keyword in C++ because that does not guarantee inlining).
So i my opinion it does very well reflect how EFLA performs.
If you want to get competitive, get rid of the (x,y) position -- if your
algorithm ALLOWS -- which is, I repeat, the whole point.
> Make your algorithm use the same putpixel call, and then come
> back and see how strong it is.
Heh, that's THE lamest advice I ever heard. I told you twice in this reply,
and for the 3rd (hopefully last time) point it out to you that you're timing
pixel() function, not your line algorithm there.
Best results can be achieved if the two, line control and pixel() are
integrated into one control structure. I told you so days ago, now you see
the theory in action. You even suggested people in this NG wouldn't deliver,
but all talk. Well, sorry to disappoint you, mate.
Even if this is "comp.graphics.algorithms", it doesn't mean most readers
wouldn't be interested in practical applications of the algorithms-- that's
what we're here for, to discuss algorithms, but ones which don't implement
well, are not interesting for most of us.
But you have a fair chance of proving your algorithm now in a real world
situation. Why don't you seize the opportunity?
> It was not my benchmark. It was done by a third party. If you wish to
> critique how the algorithms perform under a specific operating system
You seem to endorse it by posting it to your website. Don't try to crawl out
of this so easily.
> > 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.
>
> that is just it, you provided handicap to other programs based on the
> modifications to the environment. You needed to change the original
published
> algorithms like Wu and Bresenham to work under the new hardware
dependency.
Euhm... handicap means to give advantage, not to take it away. I begin to
suspect you don't even understand english. ;-)
btw. I have done this for bresenham ages ago, and hell, I can do it again if
you so like. I attempted it for EFLA for fairness sake's too, but it was
very, very hard to do. This is why I am criticizing it to begin with. The
control structure is simple looking, but try to implement it efficiently..
oh boy you're in for a surprise!
Btw... that's why I did PLEA you to implement it yourself, afterall, who am
I to prove your algorithm. It's your job. Write as fast version of EFLA you
can, and I will fix the Bresenham (atleast) meanwhile.
Like I said before, it's YOUR job, not mine.
> This ends up invalidating their algorithms (as well as EFLA), as this is
> now YOUR handicap to the programs, and benchmarks now do not reflect
accurate
> result.
Heh.... if only you used the word handicap correctly the above would not
look so funny. ;-)
> The importance of the benchmark is the speed of the algorithm, not the
> speed of the put pixel routine (whether inlined, or not, or directly
So why you time the putpixel(), then? It's taking most of the time there
anyway.
> to a specific video memory layout). Why is is so hard to simply try
> to implement an algorithm using the call and beat the three algorithms?
Because it's stupid.
> Why resorts to tricks and sleigh of hand by making only certain algorithms
> use the same pixel routine, while yours bypasses it?
Those are no tricks or sleight-of-hand, if you apply display the buffer in
screen you will notice lines will be drawn, correctly. There is no
sleight-of-hand there .. no hardware specific tricks, even, it's vanilla c++
code.
Regarding why I made only CRAP the way it is, the anwer is simply: because
it's what I wrote. I given you plenty of time to improve yours, what is it
now, two days? Three days?
--
Jukka
Benji
Jukka,
You are wasting your precious time, really.
None will never understand any of your explanations. All we can do is to let
him believe he's the best while we all know he isnt. Thats all we can do for
him.
Benji.
Jukka Liimatta
Update on the EFLA vs. Bresenham, here's the modified test, which does
implement Bresenham in fashion discussed earlier in this thread.
-----------------
Performance:
-----------------
Mr.None's EFLA: 2165.909 lps
Mr.None's Bresenham: 2209.456 lps
Jukka's Modifications to above: 8833.922 lps
Off-the-record, modified EFLA gets ~ 4000 lps, but Mr.None propably has
insight of his own how to get better performance out of the algorithm (if he
doesn't, this thread is in vain).
-----------------
Conclusion:
-----------------
EFLA is slowest, which is very much against the spirit of the topic of this
thread.
His benchmark so far tests the performance of his putpixel() function, it
seems, if the performance difference between two implementations of
Bresenham from the same stock code is to be believed.
-----------------
Proposal:
-----------------
Mr.None should write implementation of EFLA which is efficient to verify his
claims in real-world implementation of line drawing. Simply: NO ONE uses
putpixel() in performance critical rasterization code if knows better.
--
Jukka
Jukka Liimatta
No, I get kicks out of this. This is trolling w/o actually trolling. ;-)
> None will never understand any of your explanations. All we can do is to
let
> him believe he's the best while we all know he isnt. Thats all we can do
for
> him.
The EFLA *algorithm* is one of the simplest I seen in my life, I am
criticizing that it does not apply well in real-world implementations.
His only chance at this point is that it can be efficiently implemented in
hardware, because the address calculation for pixel can be integrated in the
circuitry for some additional space on the chip. While this is true,
practise shows that the chip implementors are not very likely to do this --
current commercial mainstread implementations actually draw lines with two
triangles. ;-)
Even if this is not the most efficient solution (two triangles), they do it
anyway. Because:
- it works well enough
- saves space on the chip
And above everything, if his algorithm is so amazing, that it takes very
little silicon, which this is all about, then it's ridiculous that
implementing it requires extra space. Also, that the algorithm is not
feasible as-is for implementation in software either, doesn't leave me much
imagination to figure where it could be useful at.
It's his job to prove it can actually deliver, we cannot test his claims for
hardware designers point of view (yet, I'm sure he will let us know when it
is possible), so we must use software implementation as common ground
everyone can participate in. He has all the same chances everyone else has
for writing fast code, and more, as he claims to have the fastest algorithm
available to date -- so I cannot see how I am being unfair as he claims. ;-)
Btw. thanks for the suggestion, it was very wise but I want to see where
this is going.
--
Jukka
Jukka Liimatta
> implement Bresenham in fashion discussed earlier in this thread.
Oh, right... the code..
www.liimatta.org/misc/EFLAvsWORLD.cpp
--
Jukka
Jukka Liimatta
> the data so that his algorithm won. function calls and inlined function
Incorrect analysis. And also, Bresenham is faster for me aswell, from
sources you provide in your webpage. So you lose also in your own benchmark.
Mike tested on K6-2, I tested on Pentium2 and Pentium4. That's three
different processors where the Bresenham was faster than EFLA. Anyone can
download the benchmark from your homepage (?) and come to the same
conclusions.
Also, I didn't have to "skew" the data, I get the same input as you do. I
get the endpoints to the line and color to draw with. Same data as you get
in, yet, my routine comes back in fraction of the time yours takes. It's
fair and square benchmark. If you feel treated badly, improve your code, get
rid of the putpixel() to get a benchmark which actually means something.
I admit currently I win because my code is good, and yours isn't good. But
you can improve yours, instead of pointing flaws in my code ( what flaws?
It's faster than yours ;-), improve your own code. Spend some time with the
compiler instead of complaining everyone else is being unfair or
mis-treating the benchmark.
Between the call to the line function and and returning from there, I can do
whatever I please to draw the line as quickly as possible.
> calls are about 5 to 10 times difference in performance.
This is simply NOT true, the performance increase from "inlining" the
pixel() function does not given EVEN 100% speed increase. You haven't even
tried, have you?
--
Jukka
None
Here is the math part if you missed it...
Now tell me, how do you brute force this?
NP
In math there are problem domains called NP (Non-Polynomial). There
are also the concepts of tractable and intractable problem domains.
Tractable problems are problems you can solve using brute force, which
is essentially permutating through all the values of a problem until a
solution is found. (This is very similar to permutating through the
values of an encryption key until you get the right one).
Intractable problems are problems that cannot be solved using brute
force techniques (i.e. you are not able to permutate through the
values because of certain infinite properties associated with the
values). It does not matter how fast or how many computers you use, it
is not solvable using brute force attacks (in essence, an NP problem).
In intractable NP problems, it is not possible to permutate through
the values because going from one value to the next may be a step
requiring an exponential or infinite mini-steps. In addition,
sometimes you do not know the keyspace you are traversing, thus you
must begin at ground zero.
In Base Encryption (with its use of dynamic operators, dynamic
operations, and dynamic bases, it is not possible to permutate through
the values. There are an infinite combinations of operators (its
dynamic, and there is not fixed number of them, and there is no fixed
maximum number of operations you can use) which can be used for the
algorithm. This is in addition to symbol remapping and base conversion
algorithms.
You can use billions and billions of computers, and it is still not
tractable.
To illustrate how NP intractable problems look like, I will give some
examples...
How many games are out there? Infinite (more are being created every
day).
What order can you play two games? Infinite (because you can replay
one game, then go to game two, and come back to game one, and keep
playing until next year, or maybe after ten years)
What order can you play all the games? NP (you are combining the two
problems with infinite domains. Going from one game to the next is
dependent on an infinite value that you cannot permutate through.
When you have infinite with infinite (like the example above), no
number of computers in the world short of infinite can solve it (and
even then you have no guarantee of reaching an answer).
In the example above if you fix the number of games in existence (lets
say two), you still have an infinite number of orders of playing them.
If you fix the order of playing the games (lets say only sequentially
from game one to game two), it is also infinite because there is no
finite number of games.
When you put them together, it becomes simply intractable.
Now map this analogy with the order of operators, number of operators,
the base (to infinity), the conversion algorithm used between base,
the symbol set of the original base to the destination base, the
symbol remapping strategies, you have an intractable problem. It is
NP, and no amount of computers in the world could break it. Even the
one-time pad relied on just one symbol space!
This is very similar to the Heisenberg uncertainty principle and the
quantum mechanic duality problem. The more you know one value, the
less you know the other. The more you can pinpoint the location, the
less you know about the speed. And vice versa.
See: Heisenberg, W.
"The Perceptible content of the Quantum Theoretical Kinematics and
Mechanics"
"Uber den anschaulichen Inhalt der quantentheoretischen Kinematik und
Mechanik"
Zeitschrift fur Physik 43, 172-198 1927.
(Heisenberg was somewhat disturbed by his discovery that simultaneous
observations of complementary quantities cannot be both infinitely
accurate, and went to Copenhagen to discuss this with Niels Bohr, who
argued Heisenberg to publish.)
See: Heisenberg, W.
"Die Rolle der Unbestimmtheitsrelationen in der mordernen Physik"
Monatshefte fur Mathematik und Physik 38, 365-372, 1931.
Cracking Base Encryption: Fruitless Effort
To crack Base Encryption, you need to guess...
The Base of the cyphertext (now did he use base 26? or standard ASCII,
or some large base with duplicates? Or a small English subset of
Chinese Unicode?)
The Base of the plaintext (now did he use base 26? or standard ASCII,
or some large base with duplicates? Or a small English subset of
Chinese Unicode?)
The conversion algorithm used to convert between the above two bases.
(numerical base conversion like Virtual Calc 2000? Or another type of
conversion?)
The Symbol Remapping. Any substitutions used?
The actual algorithm used. (shift, rotate, add, 1/x, a dynamically
generated one?)
The order. Was the Symbol Remapping done before or after Base
Conversion?
Immune from brute-force-attacks
In addition to the exponential permutation time of dynamic key
lengths, another property of Base Encryption that thwarts Brute-Force
attacks is the inability to test against the engine to see if you have
the right key. < Because the algorithms can be dynamic, and multiple
algorithms can derive the same You don't know when you have found the
answer. It is immune from brute-force-attacks on the basis the
INABILITY for you test against the engine and know when you have the
right key.
Charles R. Bond
None wrote:
> You have not provided a proper benchmark. What is lacking are as follows...
>
> 1) Source to Wu.
> 2) Source to Bresenham
> 3) Source to EFLA
> 4) Source to your code.
> 5) Source to benchmark.
>
Wrong. I used the benchmark and code downloaded fromyour website.
> I have provided all for anyone to run on their machines. EFLA beat
> both Wu and Bresenham. In fact, you can see the exact data at...
> http://www.edepot.com/algorithm.html
>
> In plain daylight you can examine the sources to see that they all
> call the same putpixel routine. You can examine the main loop.
> You can examine the routines to draw in all different directions.
> You can examine the benchmark data (lines total, lines drawn, and
> lines per second).
>
> There are no normalizing. No skewing of data. No hiding of data.
> Everything is there. A simple press of the compile button on any
> compiler will compile the sources and run on any machine for self benchmark.
>
> So simply do as follows...
> Provide a proper benchmark. What are lacking are as follows...
>
> 1) Source to Wu.
> 2) Source to Bresenham
> 3) Source to EFLA
> 4) Source to your code.
> 5) Source to benchmark.
>
I ran your benchmark with your code and got the results Iposted. Your code was slower than Bresenham.
> For more advice see the thread response to Jukka on how to provide
> accurate benchmark data. You need to make sure that the environment is
> correct (all using the same putpixel call). Make sure they are the same type
> (all not dependent on hardware). Make sure all data is provided (the raw
> data like lines drawn, number of seconds, and lines per second).
>
> Or did you copy him and modify the sources yourself so that your code
> or other code uses inlined pixel calls and direct video memory sets and
> leave other using the actual pixel call? And I find it odd that Jukka
> is at least able to provide the source to his benchmark, and yet you
> have provided nothing. If you are trying to compare apples and oranges again,
> like comparing pixel-to-pixel functions to graphics cards, then your statements
> amount to nothing to boasts and nothing more.
>
I downloaded your benchmark and ran it with your code. Your codewas slower than Bresenham.
> EFLA, on the other hand has been benchmarked. The url is at
> http://www.edepot.com/algorithm.html
>
> EFLA beat both Bresenham and Wu.
>
> The sources to Wu, Bresenham, EFLA, and the benchmark are all provided
> at that URL. Included are data showing the actual lines drawn, the
> time taken, and lines per second. In addition, the actual benchmark
> source can been seen.
>
I downloaded that exact code with all the sources and ran them asprovided. All the sources for the
benchmark and the line draw
algorithms (except my algorithm which is not releveant) are posted
on your website.
> >
> > 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.
I rest my case.
Charles R. Bond
None wrote:
> I agree that many people just boast. Your comments about Mr. Mike
> is true, but I believe he is in the same league as Charles (Bond). Boasts
> amount to nothing without proof. As a test... ask him to provide
> sources or benchmarks. His first response was "analysis" is benchmark.
> Now his response is the sources are proprietary, and can't be examined.
> I believe both can benefit from your advice.
An analysis is a perfectly legitimate comparison tool. I never said ananalysis was the same as a benchmark. The only
proprietary source is
my own which is not an issue in this thread. Please issue a correction on
your statement that sources for benchmarks have not been provided.
I used your sources and your benchmark as downloaded from your
website for the benchmarking. I used a 450MHz AMD K6-2 with
64meg ram. Your code ran slower than Bresenham, and plotted the
wrong pixels. The sources I used for that comparison were posted
by you on your website. They are not secret and I have not modified
them.
None
> On 25 Dec 2001 01:30:17 -0800, None <poh...@aol.com> wrote:
>
> >The algorithms on them are obsolete also. But Wu, Bresenham, and EFLA
> >is still out there chugging along awaiting implementation on the next great
> >hardware. Why? because they are not video memory layout specific, nor
> >instruction set specific.
>
> and quote from your web site:
> "Branch instructions cause significant CPU cycle delays as the pipeline
> gets flushed of all instructions during a mispredicted branch. This delay
> is very significant as modern superscalar CPU's have longer and longer
> pipelines. A pipeline containing 10 stages would reduce 10 cycles per loop
> if there are no branch instructions that causes a pipeline flush."
>
>
> Arent you shooting your own feet here? You make major assumptions about
> the hardware, but then when other people does those assumptions (refering
> to the putpixel fight) then you try to nail them down?
Not true. Major assumptions on the hardware need not be existent.
The algorithm runs fine on any hardware platform. It won't break if
ran on a hardware missing a piece of architecture (the pipeline for example).
The existence of the pipeline (and the length of the pipeline) adds a
performance increase because of the lack of branch instructions inside
the main loop. This offers two advantages... One is that the algorithm
is portable. The other is that it takes advantage of existing pipelines
if they exist, but wont break if not.
>
> Your code is supposed to be fast if the brach is slow on the hardware.
> That's the fact your superfastlinesthigie is based on. What if the
> braching is free on the target platform and division takes three seconds?
> Then Mr. B's algo may beat yours.
>
> My final statement is that you cannot make world fastest line algorithm
> without stating the platform. You just can't compare theory in this case.
Aww, here is where you are coming around. You can state any platform.
The algorithm is what is being benchmarked, not the hardware. If you
were benchmarking the hardware, you need only use instruction sets that
are fast on the given piece of hardware. In this case, you are tuning an
algorithm specific to the hardware. But this product ends up being
a benchmark on how good a person knows the speedy instructions on the
hardware, not the actual algorithm itself. And EFLA has extremely fast
addition and shifting in variation D, which wont be bogged down by
slow divisions.
Because Wu, EFLA, and Bresenham are hardware independent, you can state
ANY hardware. The algorithm's strengths come into play, and that is
what is being benchmarked.
Mr. B. as in the Mr. Bond that tried to compare a pixel-by-pixel function
to a graphics card and calling that a fair benchmark? I believe Jukka
is way better in this case. Jukka was able to provide the source,
and actually ran the code. Whereas Mr. Bond simply used an "analysis"
without actually running it and called that a benchmark. Jukka was also
able to provide helpful commentary on the technique he used to speed up
the algorithm, thus benefitting the comp.graphics.algorithms discussion,
whereas Mr. Bond has yet to provide the source to Foley, Other, and any
algorithm he has benchmarked. I do give Bond the credit of conceding
that EFLA is the Fastest instead of the slowest though.
>
> Bresenham's line algorithm is based on the fact that division was very
> very slow back then. I haven't investigated Wu's algorith into detail so I
> only guess that it's purpose is to draw as good lines as possible and also
> avoid the division. And finally your algo uses the fact that on current
> hardware division is faster than it used to be and also that branching
> kills the code cache. So there's your hardware independency. So if you are
> so worried about the cache why didnt you also optimize your code for
> read/write cache as well? Jukka's CRAP also did took care of that.
Are you speaking about EFLA variation D whereby it uses only addition
and shifting? Also, the code cache (if existing) is not only taken
advantaged of because of the short loop, the pipeline is taken advantaged
of because of the lack of branch instructions that cause pipeline flush
during a misprediction branch.
>
>
> Also I dont understand why you have to bash your "invention" so much? I
> hate the attitude that someone claims somethign being his/hers own even if
> almost everybody is using it but none has claimed to be his/hers own idea.
> Yep... I do puke when I read my slashdot and see that someone has
> patendeted the "using a rolling device to browse hypertext content"
> shit...
Maybe people get upset that they do not realize Digital Differential
Analysis is not specific to line algorithms and that EFLA, Wu, and
Bresenham also use digital transcription?
Chet Simpson
[cut a bunch of drivel that doesn't deserve a reply]
>> Q: Is that all that is wrong with blackjack?
>> A: NO!, When the player busts, the dealer should NOT continue
>> dealing to himself.
>
>Not true. Other players, or other hands might still be in progress.
In the case of YOUR game, there is only one player other than the
house/dealer. In this instance, once that player has gone bust, the
hand is over. Since there are no other players to challenge the dealer
his hand has already one and he goes on to the next hand.
>The dealer must always continue dealing until all hands and all
>other players are done.
There's only one player. Once the player has bust, he's done, hence
the game is over. REad the book, visit some gambling halls, but either
fix it or stop claiming it's the most accurate implementation - as
it's not.
>> 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.
>
>Yes, that is why the shuffle mark is settable on the main screen.
>For different decks, simply set the shuffle mark desired.
The game allows you to set a fixed location for the shuffle mark. IF
you were going for accuracy you would vary that fixed location with a
random approximation in order to vary the game.
>> 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.
>
>Not true. The dealer should continue dealing to other hands and other
>players.
You really need to research blackjack more. One a player receives a
blackjack or goes bust (and he has been paid or his money taken) his
cards are collected and he is considered a non-player. In the case of
your game, the dealer is the only one left and has no players to beat,
therefore he does not deal to at least a 17 or bust. He does not deal
to himself at all - period.
>The features....
Yes, I know the features, and I obviously already know the web site as
I checked it out so there's no reason for you to post them yet again.
As much as I would like to engage in this discussion, it has no
bearing in C.G.A.
Rasmus Christian Kaae
> 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...
no offence, but i (and severeal other demo-scene coders) used fixedpoint
linedrawers back in the days where they were usefull (meaning before
hardwareaccelleration took over the 3d-market). maybe we didn't bother
writing scientific documents on this subject (for one, i was around 15-16
when i did my fixedpoint linefillers). most of these linefillers were based
on a simple Bresenham linefiller (or Wu if you were hardcore and wanted
antialiased lines).
no matter what, i think i'll stick with Mike and claim that you have done
nothing more than writing a benchmark of your optimized linedrawer.
rasmus.
None
EFLA slower than Bresenham?
Here are the actual benchmark data...
Also available at http://www.edepot.com/algorithm.html
Benchmark data: Pentium III 450Mhz, Visual C++ 6.0 Release Build,
Optimizations on...
Algorithm Lines Drawn (x1000) Secs Lines/Sec
Bresenham 1000 182.172 5489.318
EFLA Variation D 1000 170.175 5876.304
Now, independently verified by a third party on a different CPU
architecture.
Benchmark data: PPC 7450 450Mhz, CodeWarrior 7, Optimizations OFF
(Generic PPC)...
Algorithm Lines Drawn (x1000) Secs Lines/Sec
Bresenham 100 7.998 12503.093
EFLA Variation D 100 7.469 13388.354
Benchmark data: PPC 7450 450Mhz, CodeWarrior 7, Optimizations ON
(Generic PPC)...
Algorithm Lines Drawn (x1000) Sec Lines/Second
Bresenham 100 7.998 12503.093
EFLA Variation D 100 7.469 13388.354
Benchmark data: PPC 7450 450Mhz, CodeWarrior 7, Optimizations on (G3
instructions)...
Algorithm Lines Drawn (x1000) Sec Lines/Sec
Bresenham 100 7.918 12629.427
EFLA Variation D 100 7.431 13457.389
Benchmark data: PPC 7450 450Mhz, CodeWarrior 7, Optimizations on (G4
instructions)...
Algorithm Lines Drawn (x1000) Sec Lines/Sec
Bresenham 100 7.753 12898.334
EFLA Variation D 100 7.229 13832.781
Looks like EFLA beat Bresenham on multiple platforms.
You were saying?
Also, you neglected to provide the benchmark data...
Remember, the CPU, the compiler, and lines drawn, the time (seconds),
and the lines/sec.
These are output of the benchmark. Do not fudge with them. Do
not plug-and-play algorithms.
And, as Jukka mentioned... EFLA is subpixel accurate.
Jukka Liimatta
*ahem*, no I didn't... hint: integer endpoints..
--
Jukka
None
I find this odd. EFLA beats Wu and Bresenham, and you are concentrating
on who is best? Looks like some sort of jealousy in play here.
Perhaps there is a hidden reason why you do not like the figures below?
Algorithm Lines Drawn (x1000) Secs Lines/Second
Bresenham 1000 182.172 5489.318
Wu 1000 172.598 5793.810
Benji
news:12124e47.01122...@posting.google.com...
Yes. Bresenham was my uncle! Dammit, you got me there...
Please dont copy-paste your benchmark to all your postings, it really doesnt
make you more credible. Instead read what other ppl write and, at least, try
to understand it. Nobody says your benchmark is faked but you say that
everybody else that get different results is faking. Dont be a child, there
are different architectures and there may be different results. Also all you
can say is that in the benchmark YOU wrote and DONT allow to modify and with
YOUR results EFLA is the fastest. It doesnt make it the fastest in real
world application as you probably arent able to modify your code to be
faster than bresenham2 that jukka provided.
You probably still wont get it but at least, I tried.
Benji.
Alexander Voronin
Ghm... What is enhanced there in benchmark? ;) OK.. Thanx anyway -
you've not cleared my name at all there. Can you please insert one more
test - with my FixedPoint line algorithm there? ;) I still dont believe
that Bresenham is faster... :)
Alexander Voronin
Alexander Voronin
>
> 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.
>
> 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.
>
And by the way... Fastest? ;) You've forgot my example of fixed point
line in benchmark... Screenshot:
[root@Saturn lines]# ./a.out 100
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed
Point with 100 loops...
Made 400000 lines in 7.360 seconds, avg 54347.826 lps
Examining: fixed_point_line, Simpliest fixed point algorithm with 100
loops...
Made 400000 lines in 7.330 seconds, avg 54570.259 lps
Examining: bresenham, Bresenham Line Algorithm with 100 loops...
Made 400000 lines in 9.710 seconds, avg 41194.645 lps
Examining: wu, Wu Line Algorithm with 100 loops...
Made 400000 lines in 8.390 seconds, avg 47675.805 lps
[root@Saturn lines]#
Oups... :) 200 lps but worth it... ;)
Alexander Voronin
None
> > others use the plain put pixel routine. He had to do this to skew
> > the data so that his algorithm won. function calls and inlined function
>
> Incorrect analysis. And also, Bresenham is faster for me aswell, from
> sources you provide in your webpage. So you lose also in your own benchmark.
Sorry, some again? 5 independent test cases.
Processors: AMD, Intel, PowerPC...
Compilers: MINGW (GNU), MSVC++, Intel C++, CodeWarrior...
Operating Systems: Linux, Win98, Win2000.
*** BENCHMARK 1 ***
PPC 7450/733Mhz, compiler CodeWarrior 7
optimizations on, specific 7450 (G4) instructions
Examining: bresenham, Bresenham Line Algorithm with 100 loops...
Made 100000 lines in 7.753 seconds, avg 12898.334 lps
Examining: wu, Wu Line Algorithm with 100 loops...
Made 100000 lines in 9.374 seconds, avg 10667.265 lps
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point
with 100 loops...
Made 100000 lines in 7.229 seconds, avg 13832.781 lps
*** BENCHMARK 2 ***
AMD 950 MHz with Intel C++,
Examining: bresenham, Bresenham Line Algorithm with 100 loops...
Made 100000 lines in 5.798 seconds, avg 17247.326 lps
Examining: wu, Wu Line Algorithm with 100 loops...
Made 100000 lines in 7.081 seconds, avg 14122.298 lps
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point
with 100 loops...
Made 100000 lines in 5.648 seconds, avg 17705.382 lps
*** BENCHMARK 3 ***
MINGW (based on GCC 2.95.3-5) with -O3 switch and _inlined_
pixel() routine (well, I guess that MINGW would inline it by itself
anyway), Duron 850MHz, Windows 98, GeForce2MX-400.
Examining: bresenham, Bresenham Line Algorithm with 100 loops...
Made 100000 lines in 11.210 seconds, avg 8920.606 lps
Examining: wu, Wu Line Algorithm with 100 loops...
Made 100000 lines in 32.070 seconds, avg 3118.179 lps
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed
Point with 100 loops...
Made 100000 lines in 10.270 seconds, avg 9737.098 lps
*** BENCHMARK 4 ***
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed
Point with 100 loops...
Made 400000 lines in 7.360 seconds, avg 54347.826 lps
Examining: bresenham, Bresenham Line Algorithm with 100 loops...
Made 400000 lines in 9.710 seconds, avg 41194.645 lps
Examining: wu, Wu Line Algorithm with 100 loops...
Made 400000 lines in 8.390 seconds, avg 47675.805 lps
Note: that is a very accurate assessment.
*** BENCHMARK 5 ***
And, of course...
http://www.edepot.com/algorithm.html
Algorithm Lines Drawn (x1000) Secs Lines/Sec
Bresenham 1000 182.172 5489.318
Wu 1000 172.598 5793.810
EFLA Variation D 1000 170.175 5876.304
xxxxxxxxxxxxxxxxxxxxx
None
> I ran your benchmark with your code and got the results Iposted. Your code was slower than Bresenham.
Looks like you are trying to protect Bresenham. Must be the reason
you lied about the data and the benchmark. I have examined your
previous posts.
Here they are... your AMD benchmark.
> None 1165.490 lines per second
> Wu 876.991 line per second
> Bres 1175.548 lines per second
> Bond 1193.850 lines per second
>
After asking for you to provide lines total and especially total
times taken. You refused. (Which shows you probably had a hard
time coming up with legitimate values? Running the program provides
more than just lps, but total lines, and total seconds)
Here is your response finally...
> I posted the number of lines elsewhere. It was 1 million lines. You canfigure out the time yourself.
Well, 1 mil/1165.490 lps from your "benchmark" figures equals 858.008
seconds.
Now lets examine a true benchmark on AMD processor provided by a third
party...
Examining: bresenham, Bresenham Line Algorithm...
5.798 seconds, avg 17247.326 lps
Thats 17247.326 lps compared to 1165.490 lps. Lps stays in the same
range
no matter the number of lines drawn. And those seconds do look
way different don't they, by a factor of more than 100 times!!!
(not 10, but 100!!!).
Looks like this is what you resort to when you cannot come up with
facts to uphold your statements?
As for EFLA beating Bresenham, visit
http://www.edepot.com/algorithm.html
Benchmark data: Pentium III 450Mhz, Visual C++ 6.0 Release Build,
Optimizations on...
Algorithm Lines Drawn (x1000) Secs Lines/Sec
Bresenham 1000 182.172 5489.318
Wu 1000 172.598 5793.810
EFLA Variation D 1000 170.175 5876.304
Even Wu beat Bresenham... by a HUGE factor.
> I rest my case.
Donald Graft
add the contrary results to the list that he appends to almost
every email.
Don
"None" <poh...@aol.com> wrote in message news:12124e47.01122...@posting.google.com...
Kilgore Trout
> > slower than Bresenham and plots the wrong pixels.
>
> If you think one is wrong, simply add the .5 round either
> up or down and you have what you think is correct.
>
Shouldn't your algorithm handle that? When he says "wrong", he means that
there is a pixel which is closer to the actual mathematical line than the
pixel which your algorithm choses. It isn't subjective in anyway.
Benchmarks don't really mean a whole lot if the algorithm isn't plotting the
correct pixels.
And if your algorithm really is as fast as you say, why don't you write up
an article about it and submit it to a journal to be published?
Kev
None
> As an impartial observer, I am wondering why None does not
> add the contrary results to the list that he appends to almost
> every email.
>
> Don
The reason is because the only contrary results are those missing data,
or highly suspicious of tampering.
Did you not notice there were something wrong with Mr. Bond's benchmark?
He never posted lines total and total time taken. And he
refused to provide them. Even asking others to calculate the time.
I find that odd. Well after obtaining results from another AMD
benchmark, we find that his lps was off a factor of 10 and the seconds
off a factor of 100!!
Charles R. Bond
> The reason is because the only contrary results are those missing data,
> or highly suspicious of tampering.
> Did you not notice there were something wrong with Mr. Bond's benchmark?
> He never posted lines total and total time taken.
I posted the total lines in my first post on your benchmark, datedMon. 24, Dec. 2001, 10:20:59 -- that's lie #1
for you in this post.
> And he
> refused to provide them.
I never refused to provide any of the data I collected. That's lie#2 for you in this post.
> Even asking others to calculate the time.
I never asked anyone to calculate the time. I simply said that ifyou wanted that number you could calculate it
yourself. It's
redundant and irrelevant because total lines and lines per second
completely specify it. That's lie #3 for you in this post.
> I find that odd. Well after obtaining results from another AMD
> benchmark, we find that his lps was off a factor of 10 and the seconds
> off a factor of 100!!
>
Gotcha! If I never posted total lines, HOW DO YOU KNOW THATTHE LPS OR TOTAL TIME WAS OFF??? That's a blatant
contradiction!
At the risk of stating the obvious, one benchmark does not "cancel"
another. The data I posted was NOT tampered with in any way.
I ran your benchmark EXACTLY as posted on your website, on a
hardware platform which I specified, using the default parameters
you set (1 million lines) and merely posted my results.
None
> None wrote:
>
> > The reason is because the only contrary results are those missing data,
> > or highly suspicious of tampering.
> > Did you not notice there were something wrong with Mr. Bond's benchmark?
> > He never posted lines total and total time taken.
>
> I posted the total lines in my first post on your benchmark, datedMon. 24, Dec. 2001, 10:20:59 -- that's lie #1
> for you in this post.
>
> > And he
> > refused to provide them.
>
> I never refused to provide any of the data I collected. That's lie#2 for you in this post.
Not true. You were asked repeatly for the source for cycle counts of
"Foley" and "Other". You refused to provide the total time from your
benchmark, even though the benchmark lists them in its output. This
has been asked multiple times, and to this date you ask people to calculate
it, rather then list it yourself.
>
> > Even asking others to calculate the time.
>
> I never asked anyone to calculate the time. I simply said that ifyou wanted that number you could calculate it
> yourself. It's
> redundant and irrelevant because total lines and lines per second
> completely specify it. That's lie #3 for you in this post.
See below...
>
> > I find that odd. Well after obtaining results from another AMD
> > benchmark, we find that his lps was off a factor of 10 and the seconds
> > off a factor of 100!!
> >
>
> Gotcha! If I never posted total lines, HOW DO YOU KNOW THATTHE LPS OR TOTAL TIME WAS OFF??? That's a blatant
> contradiction!
Not true, see below...
>
> At the risk of stating the obvious, one benchmark does not "cancel"
> another. The data I posted was NOT tampered with in any way.
> I ran your benchmark EXACTLY as posted on your website, on a
> hardware platform which I specified, using the default parameters
> you set (1 million lines) and merely posted my results.
Not tampered? Look below...
Here is your statement...
> None 1165.490 lines per second
> Wu 876.991 line per second
> Bres 1175.548 lines per second
> Bond 1193.850 lines per second
>
> ... on a 450 MHz AMD K6-2 with 64M ram.
>
After repeatedly asking for total lines and total time taken. In another post...
>
> I posted the number of lines elsewhere. It was 1 million lines. You canfigure out the time yourself.
Ok, lets examine your data taking in account of EFLA...
1 Million lines at 1165.490 lines/sec
Thats equals to 858.008 seconds
What is wrong with this data?
Here is another independent benchmark using the AMD CPU.
Extremely Fast Line Algorithm-addition fixed Point
5.648 seconds, avg 17705.382 lps
17705.382 lps compared to 1165.490 lps?
858.008 seconds is also way out of proportion.
The lps stays in the same range for any number of lines.
Who is lying?
This is similar behavior of you trying to compare a pixel-by-pixel algorithm to
a graphics card.
Curious
> > I never refused to provide any of the data I collected. That's lie#2 for
you in this post.
>
> Not true. You were asked repeatly for the source for cycle counts of
> "Foley" and "Other". You refused to provide the total time from your
> benchmark, even though the benchmark lists them in its output. This
> has been asked multiple times, and to this date you ask people to
calculate
> it, rather then list it yourself.
>
> >
> > > Even asking others to calculate the time.
> >
> > I never asked anyone to calculate the time. I simply said that ifyou
wanted that number you could calculate it
> > yourself. It's
> > redundant and irrelevant because total lines and lines per second
> > completely specify it. That's lie #3 for you in this post.
>
> See below...
see bit more below for math lesson #1 ;)
As i see it, absolutely nothing WRONG... 1165.490 * 858.008 = 999999.744 =
million lines? Ever learned maths? borrow friends fingers, ask someone help
counting with yout toes if nothing else helps...
Ever occured that ones who have slower CPU would end up running test hell of
a lot longer, now did it?
> Here is another independent benchmark using the AMD CPU.
> Extremely Fast Line Algorithm-addition fixed Point
> 5.648 seconds, avg 17705.382 lps
>
>
> 17705.382 lps compared to 1165.490 lps?
Shows only fact that other benchmark was RUN in AMD ATHLON cpu, and other
in AMD k6-2 that is hell of a LOT slower...
Don't you get that simple fact that every different CPU does NOT give same
result? What is so hard to understand in that?
> 858.008 seconds is also way out of proportion.
> The lps stays in the same range for any number of lines.
>
> Who is lying?
Most likely neither one is...
It still does NOT make anyone that gets different results than your
"independent benchmarks" as LIAR if they do not get same results on
different CPU:s... this Benchmark is platform dependant. Simple fact that is
shown by varying results done with different compilers and run in different
CPU:s...
> This is similar behavior of you trying to compare a pixel-by-pixel
algorithm to
> a graphics card.
NO... it's simple behaviour of trying believe resuts do NOT vary from
platform to other...
None
> > And, as Jukka mentioned... EFLA is subpixel accurate.
>
> *ahem*, no I didn't... hint: integer endpoints..
Yes you did...
Me:
> Does it work in all different directions? Does it behave like the
> bad code in the URL posted by Mike? Does it retrace correctly?
Jukka:
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,
Charles R. Bond
> > I never refused to provide any of the data I collected. That's lie#2 for you in this post.
>
> Not true. You were asked repeatly for the source for cycle counts of
> "Foley" and "Other".
Mr. None, (or may I just call you Zero?), my statement above said that I"never refused to provide any of the data I
collected." That is a TRUE
statement. As far as providing the source for Foly, you must consult
Foley for that. His text is a standard text for which I provided a citation,
but I will not post copyrighted code. It isn't relevant anyway. Neither
is my "other" code. Your looking for diversions and distractions now...
> You refused to provide the total time from your
> benchmark, even though the benchmark lists them in its output. This
> has been asked multiple times, and to this date you ask people to calculate
> it, rather then list it yourself.
Sorry to bust your bubble, but never in any of my posts did I ask anyoneto calculate it. I only said that if you
wanted it, you could calculate it from
the total lines and lines per second which I had already posted. It is redundant
and totally determined by the previously posted data, so it will have no
effect on any benchmark. Stop crying about irrelevant details.
Again I had already posted the total lines, and did regarded the total timeas an obvious consequence of the total
lines and lines per second.
>
>
> >
> > I posted the number of lines elsewhere. It was 1 million lines. You canfigure out the time yourself.
I though you said I *refused* to post the total number of lines. Areyou crazy? Now you have found one of the posts
where I provided
it, (there are others), and you still claim I refused to provide it! Now
you quote it yourself from my post and still claim I refused to
provide it! What a laugh....
> Ok, lets examine your data taking in account of EFLA...
>
> 1 Million lines at 1165.490 lines/sec
> Thats equals to 858.008 seconds
>
> What is wrong with this data?
>
> Here is another independent benchmark using the AMD CPU.
> Extremely Fast Line Algorithm-addition fixed Point
> 5.648 seconds, avg 17705.382 lps
>
> 17705.382 lps compared to 1165.490 lps?
>
> 858.008 seconds is also way out of proportion.
> The lps stays in the same range for any number of lines.
>
> Who is lying?
You are.
> This is similar behavior of you trying to compare a pixel-by-pixel algorithm to
> a graphics card.
My advice to you is to find someone who is more ignorant or dishonest thanyou to argue with -- if you can find one.
Jukka Liimatta
>
> Yes you did...
NO, I did not. I know what subpixel accuracy is..
> It does work for all different directions, all 8 octants are covered, and
Not related.
> 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,
No, my code does NOT handle subpixel precision issues, neither does yours. I
wrote mine to be as accurate as yours, nothing more.
The executable (www.liimatta.org/po-han-lin2.exe is subpixel accurate). Your
nor my code being benchmarked here is NOT subpixel accurate, atleast with in
the form they are written now (integer line endpoints).
Even if the "machinery" inside would be, the interface loses all fractional
coordinate information at endpoints, and that means we are not subpixel
accurate. Decimals in interpolation are not relevant to the topic (except
required in conjunction with the endpoint handling for the whole total to be
considered sba..).
In short: you're wrong and your claims are ridiculous.
--
Jukka
Charles R. Bond
> > After repeatedly asking for total lines and total time taken. In another post...
CB wrote:
> Again I had already posted the total lines, and did regarded the total timeas an obvious consequence of the total
> lines and lines per second.
>
Mr. Zero, quoting from a CB post.
> > > I posted the number of lines elsewhere. It was 1 million lines. You canfigure out the time yourself.
>
CB wrote:
> I though you said I *refused* to post the total number of lines. Areyou crazy? Now you have found one of the posts
> where I provided
> it, (there are others), and you still claim I refused to provide it! Now
> you quote it yourself from my post and still claim I refused to
> provide it! What a laugh....
>
Mr. Zero wrote:
> > Ok, lets examine your data taking in account of EFLA...
> >
> > 1 Million lines at 1165.490 lines/sec
> > Thats equals to 858.008 seconds
> >
> > What is wrong with this data?
> >
Amazing. After all your insistence (see your above statementsand previous quotes) that I had refused to provide the
total
lines, it turns you *did* know that I had posted them. So much
for your integrity. And it turns out that my assumption that you
knew how to divide was correct. But just in case that was as
burdensome as you suggest, here are the other times:
EFLA 858.9 sec
Bres 850.7 sec
Wu 1140.3 sec
What's wrong with this data? You don't like it. That's what's
wrong with it. My test was run on a Fujitsu laptop, with the
450MHz AMD K6-2 and which is notoriously slow. So
what? Your algorithm is machine independent, isn't it?
> > Here is another independent benchmark using the AMD CPU.
> > Extremely Fast Line Algorithm-addition fixed Point
> > 5.648 seconds, avg 17705.382 lps
> >
> > 17705.382 lps compared to 1165.490 lps?
> >
> > 858.008 seconds is also way out of proportion.
> > The lps stays in the same range for any number of lines.
> >
> > Who is lying?
>
> You are.
>
> > This is similar behavior of you trying to compare a pixel-by-pixel algorithm to
> > a graphics card.
>
> My advice to you is to find someone who is more ignorant or dishonest thanyou to argue with -- if you can find one.
By the way, thanks for the compliment about my providingcycle counting data (not pixel counting) -- which was on your
*original* fastest code in the world. Please see the Intel
developer's website and the AMD developer's website for
more information on using instruction pairing and cycle counting
to analyze and/or optimize critical code. It is quite informative
to examine the machine code output by the compiler to see
what instruction sequence will actually be executed. Of course,
only grownups will understand this arcane subject, so I'll leave
it out of future posts so you can stay in your sandbox.
Marco Nelissen
> "Donald Graft" <neu...@attbi.com> wrote in message news:<W6%W7.11899$7p6.1...@rwcrnsc51.ops.asp.att.net>...
>> As an impartial observer, I am wondering why None does not
>> add the contrary results to the list that he appends to almost
>> every email.
>>
>> Don
>
> The reason is because the only contrary results are those missing data,
> or highly suspicious of tampering.
Sorry for jumping in so late in this *very* interesting thread.
Here are the results from running your benchmark on BeOS R5, compiled
with gcc, running on P-II 350:
nice:/tmp$ ./benchmark
Examining: bresenham, Bresenham Line Algorithm with 1000 loops...
Made 1000000 lines in 555.129 seconds, avg 1801.383 lps
Examining: wu, Wu Line Algorithm with 1000 loops...
Made 1000000 lines in 500.107 seconds, avg 1999.572 lps
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point with 1000 loops...
Made 1000000 lines in 528.641 seconds, avg 1891.643 lps
As you can see, your code is slower than Wu.
Since your benchmark took a little too much time for me to wait for it
to run multiple times, I changed the loopcount to 10, and repeated the
experiment:
nice:/tmp$ ./benchmark 10
Examining: bresenham, Bresenham Line Algorithm with 10 loops...
Made 10000 lines in 5.524 seconds, avg 1810.282 lps
Examining: wu, Wu Line Algorithm with 10 loops...
Made 10000 lines in 4.952 seconds, avg 2019.386 lps
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point with 10 loops...
Made 10000 lines in 5.275 seconds, avg 1895.735 lps
This confirms that indeed, Wu is faster than your algorithm.
Now, the above is with optimization turned OFF. With optimization ON,
we get:
nice:/tmp$ ./benchmark 10
Examining: bresenham, Bresenham Line Algorithm with 10 loops...
Made 10000 lines in 3.680 seconds, avg 2717.391 lps
Examining: wu, Wu Line Algorithm with 10 loops...
Made 10000 lines in 4.369 seconds, avg 2288.853 lps
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point with 10 loops...
Made 10000 lines in 3.595 seconds, avg 2781.641 lps
Surprisingly, both Bresenham and efla become a lot faster (but are still
pretty much equal), but Wu hardly gets any faster. On a hunch, I decided
that cache-thrashing might be the reason (since Wu access the pixels
differently), and so I changed the 'pixel' function to do nothing.
Running this with a loopcount of 100 yielded some interesting results:
ce:/tmp$ ./benchmark 100
Examining: bresenham, Bresenham Line Algorithm with 100 loops...
Made 100000 lines in 7.212 seconds, avg 13865.779 lps
Examining: wu, Wu Line Algorithm with 100 loops...
Made 100000 lines in 1.448 seconds, avg 69060.773 lps
Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point with 100 loops...
Made 100000 lines in 2.364 seconds, avg 42301.184 lps
As you see, your algorithm is now significantly faster than Bresenham,
but Wu is once again the winner. Your algorithm was only faster because
of the way the framebuffer was layed out in memory, combined with the
way in which each of the algorithms accesses the framebuffer. You can
therefore hardly claim that your algorithm is the fastest processor
and framebuffer independant line-algorithm, can you?
I guess the moral of the story is that in a real-world implementation,
where you *do* have information about the framebuffer and you can
optimize for it, your algorithm is most likely NOT the fastest.
As someone else pointed out, you have one branch per pixel (the loop
branch itself). Wu has a worst case of 3/4 branch per pixel, and a
best case of 1/2 branch per pixel. Obviously Wu scores better here.
Since I'm pointing out the flaws in your reasoning, let me also point
out the flaw in your "unbreakable" encryption algorithm, which you
claim is invulnerable to brute-force attacks. You claim it is not
susceptible to such attacks because the encryption key and method
are variable. Well, that is really no different from me sending you
a block of data encrypted with a traditional encryption method, but
not telling you which one. Since you don't know which encryption
method was used, you would have to try ALL of them, including
every single variation imaginable. Sounds remarkably like your
method, doesn't it? And yet it uses "traditional" encryption
methods.
Marco
Pascal
> out the flaw in your "unbreakable" encryption algorithm, which you
> claim is invulnerable to brute-force attacks. You claim it is not
> susceptible to such attacks because the encryption key and method
> are variable.
Like the nazi's ENIGMA ?
If I remember correctly if was cracked by brute force on computers years
after WWII.
(It was not cracked during the war, but by putting their hand on an captured
ENIGMA machine US and British secret services were able to understand German
messages).
Pascal
Markku S
> Like the nazi's ENIGMA ?
>
> If I remember correctly if was cracked by brute force on computers years
> after WWII.
> (It was not cracked during the war, but by putting their hand on an captured
> ENIGMA machine US and British secret services were able to understand German
> messages).
Enigma was not a 'security by obscurity'-solution. Getting the machine
helped them figure the algorithm out, but as they didn't have the
encryption keys they had to crack it. (The codebreaker machine used during
the war, was a precursor of modern computers)
http://www.turing.org.uk/turing/ will probably tell the rest.
--
/"\ /
\ / ASCII Ribbon Campaign / Why and how to CROSSPOST:
X Against HTML Mail / malibutelecom.fi/yucca/usenet/xpost.html
/ \ /
None
>
> Amazing. After all your insistence (see your above statementsand previous quotes) that I had refused to provide the
> total
> lines, it turns you *did* know that I had posted them.
This is not true. You have purposely posted your lps without the
lines nor seconds. Afterwards, you posted the lines on a separate
post, and asked people to do the calculation themselves. This is
a distraction from your goal of preventing an analysis of it.
The benchmark program provided the data as output,
So much
> for your integrity. And it turns out that my assumption that you
> knew how to divide was correct. But just in case that was as
> burdensome as you suggest, here are the other times:
>
> EFLA 858.9 sec
> Bres 850.7 sec
> Wu 1140.3 sec
Well, finally, we got the data. See, it can be done even by you,
just need a little coaxing. But there are some problems. You see this
was hand calculated, and not the output of the benchmark. How do we
know you did not even tamper with the seconds? The original benchmark
was accurate to three decimal places. But lets say that we let this go...
>
> What's wrong with this data? You don't like it. That's what's
> wrong with it. My test was run on a Fujitsu laptop, with the
> 450MHz AMD K6-2 and which is notoriously slow. So
> what? Your algorithm is machine independent, isn't it?
Here is another result on your AMD platform...
Bresenham Line Algorithm:
5.798 seconds, avg 17247.326 lps
Wu Line Algorithm
7.081 seconds, avg 14122.298 lps
Extremely Fast Line Algorithm-addition fixed Point
5.648 seconds, avg 17705.382 lps
You have a laptop that is 10 times slower? That is a lot compared to
2 or three times. And those seconds. 800 seconds compared to single
digit seconds... That is about 100 times or more in difference.
>
> By the way, thanks for the compliment about my providingcycle counting data (not pixel counting) -- which was on your
> *original* fastest code in the world. Please see the Intel
> developer's website and the AMD developer's website for
> more information on using instruction pairing and cycle counting
> to analyze and/or optimize critical code. It is quite informative
> to examine the machine code output by the compiler to see
> what instruction sequence will actually be executed.
Perhaps if you provided the data upfront then it would be informative.
Here is the original post... tell me where I mentioned pixel counting...
You need to provide the test case source, as well as the source
for the Foley and Other. If you are listing cycle counts, then
you definitely need to provide the assembly and C source so that
we are sure that the translation is correct and there were no
wrongful translations or missing lines. Anyone can claim
any cycle count, but to be sure that it is correct, the source
and assembly translation needs to be provided. You also need
to provide the hardware you are using as well as the software
used. (or are you translating this by hand? In this case how
do we know your assembly is correct?)
If one code use CPU registers and another uses main memory, and
all others are the same, then the CPU register will beat the
one using the main memory. All three codes must use the same
technique. If one uses CPU register, then all three must use
CPU register. Please provide these details (source and assembly
and cycle breakdown for all three should do) along with the benchmark
and source of the test and you will see that when all three conditions
are the same, the EFLA is the fastest).
Here is the URL: http://www.edepot.com/algorithm.html
Don't forget to provide your hardware and compiler (assembly and C) details
as well.
None
This confirms EFLA is faster than Bresenham, but not far behind Wu
even though EFLA is not yet optimized. Note that in this non-optimized
compiler routine, EFLA is not far behind. Note also that EFLA
has not been optimized in the algorithm either. For example, Wu
uses symmetry and double-step, whereas EFLA D is just purely algorithm,
without even getting into algorithm optimizations. (not just optimized
machine code)
>
> nice:/tmp$ ./benchmark 10
> Examining: bresenham, Bresenham Line Algorithm with 10 loops...
> Made 10000 lines in 3.680 seconds, avg 2717.391 lps
>
> Examining: wu, Wu Line Algorithm with 10 loops...
> Made 10000 lines in 4.369 seconds, avg 2288.853 lps
>
> Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point with 10 loops...
> Made 10000 lines in 3.595 seconds, avg 2781.641 lps
>
When machine code optimized, it looks like EFLA is number 1.
>
> Surprisingly, both Bresenham and efla become a lot faster (but are still
> pretty much equal), but Wu hardly gets any faster. On a hunch, I decided
> that cache-thrashing might be the reason (since Wu access the pixels
> differently), and so I changed the 'pixel' function to do nothing.
Wait. The pixel function already had nothing. What did you put in it
the first time?
> Running this with a loopcount of 100 yielded some interesting results:
>
> ce:/tmp$ ./benchmark 100
> Examining: bresenham, Bresenham Line Algorithm with 100 loops...
> Made 100000 lines in 7.212 seconds, avg 13865.779 lps
>
> Examining: wu, Wu Line Algorithm with 100 loops...
> Made 100000 lines in 1.448 seconds, avg 69060.773 lps
>
> Examining: efla_addition, Extremely Fast Line Algorithm-addition fixed Point with 100 loops...
> Made 100000 lines in 2.364 seconds, avg 42301.184 lps
>
> As you see, your algorithm is now significantly faster than Bresenham,
> but Wu is once again the winner. Your algorithm was only faster because
> of the way the framebuffer was layed out in memory, combined with the
> way in which each of the algorithms accesses the framebuffer. You can
> therefore hardly claim that your algorithm is the fastest processor
> and framebuffer independant line-algorithm, can you?
Did you modify the benchmark source from that on the site?
There was no framebuffer in there. Can you provide the source for your
benchmark?
>
> I guess the moral of the story is that in a real-world implementation,
> where you *do* have information about the framebuffer and you can
> optimize for it, your algorithm is most likely NOT the fastest.
> As someone else pointed out, you have one branch per pixel (the loop
> branch itself). Wu has a worst case of 3/4 branch per pixel, and a
> best case of 1/2 branch per pixel. Obviously Wu scores better here.
Aww.. but in this case, someone is doing the optimization, and the
technique of optimization must be taken into account. The end result
would be a test of how good an algorithm runs using the skills of the
coder. It would not be a test of the algorithm's strengths.
>
> Since I'm pointing out the flaws in your reasoning,
The reasoning is still true. You indicated some reference to
buffer and emptying of putpixel code. This shows there was some
difference in benchmark source. I suggest you provide the source
so people can see what were the modifications.
> let me also point
> out the flaw in your "unbreakable" encryption algorithm, which you
> claim is invulnerable to brute-force attacks. You claim it is not
> susceptible to such attacks because the encryption key and method
> are variable. Well, that is really no different from me sending you
> a block of data encrypted with a traditional encryption method, but
> not telling you which one. Since you don't know which encryption
> method was used, you would have to try ALL of them, including
> every single variation imaginable. Sounds remarkably like your
> method, doesn't it? And yet it uses "traditional" encryption
> methods.
This is not a graphics forum, but I will answer it once here, but
continuing would be interrupting the discussion...
Suppose you have a plain text. An infinite amount of algorithms can
derive that plain text. Which algorithm is correct?
>
> Marco
Marco Nelissen
> When machine code optimized, it looks like EFLA is number 1.
But Bresenham is not far behind, just like efla is not far behind Wu
in the first test. Relatively speaking, the difference is actually less
(efla is 6% slower than Wu in the first test, but bresenham is only 3%
slower than efla in the 3rd test)
>> Surprisingly, both Bresenham and efla become a lot faster (but are still
>> pretty much equal), but Wu hardly gets any faster. On a hunch, I decided
>> that cache-thrashing might be the reason (since Wu access the pixels
>> differently), and so I changed the 'pixel' function to do nothing.
>
> Wait. The pixel function already had nothing. What did you put in it
> the first time?
Nothing, the pixel function, in the code that I downloaded from your site,
looked like this:
void pixel ( int x, int y, UByte clr ) {
frame_buffer[ y * fb_width + x] = clr;
}
That's not nothing, it's a memory access. For my test I took that
memory access out, like this:
void pixel ( int x, int y, UByte clr ) {
// frame_buffer[ y * fb_width + x] = clr;
}
> Did you modify the benchmark source from that on the site?
Yes.
> There was no framebuffer in there.
Yes there was:
/* ---------------------------------- */
/* Virtual frame buffer. */
/* You can use pixel routine to set */
/* it or direct access it */
/* ---------------------------------- */
#define fb_width 1000
#define fb_height 1000
static UByte frame_buffer[fb_width * fb_height];
Don't you know your own benchmark?
> Can you provide the source for your
> benchmark?
It's the same as the one at http://www.edepot.com/linebenchmark.html
except I commented out the body of the pixel() function as shown above.
> Aww.. but in this case, someone is doing the optimization, and the
> technique of optimization must be taken into account. The end result
> would be a test of how good an algorithm runs using the skills of the
> coder. It would not be a test of the algorithm's strengths.
You are dodging the issue. Looking at *just* the algorithm, Wu is
faster. When you also measure framebuffer-access, for the particular
framebuffer layout included in *your* benchmark, then your method
is faster. You therefore cannot claim that your method is faster
independent of the cpu or framebuffer, because I have shown that
the framebuffer access is a major factor in your benchmark, and
when taken out also takes away the advantage of your algorithm.
> The reasoning is still true. You indicated some reference to
> buffer and emptying of putpixel code. This shows there was some
> difference in benchmark source. I suggest you provide the source
> so people can see what were the modifications.
Please have another look at the code for YOUR benchmark
(http://www.edepot.com/linebenchmark.html) which you refer
to on YOUR webpage (http://www.edepot.com/algorithm.html).
It includes a virtual framebuffer, and a pixel() function
that accesses it.
> This is not a graphics forum,
Actually, it is: comp.graphics.algorithms
> Suppose you have a plain text. An infinite amount of algorithms can
> derive that plain text. Which algorithm is correct?
This is security through obscurity. Nothing new. Your encryption
method is as "unbreakable" as any other method.
Marco
Jukka Liimatta
> lines nor seconds. Afterwards, you posted the lines on a separate
> post, and asked people to do the calculation themselves. This is
> a distraction from your goal of preventing an analysis of it.
> The benchmark program provided the data as output,
Don't be childish. I know you oriental folks have a fetish about not "losing
face", but just get on with it.. your algorithm is the fastest, isn't that
what you were convinced about even before you bothered to post here.
Don't let us western Devils to discourage you from your efforts, we are just
plain evil!
--
Jukka
Antonio Martos
> > Bres 850.7 sec
> > Wu 1140.3 sec
>
> Well, finally, we got the data. See, it can be done even by you,
> just need a little coaxing. But there are some problems. You see this
> was hand calculated, and not the output of the benchmark. How do we
> know you did not even tamper with the seconds? The original benchmark
> was accurate to three decimal places. But lets say that we let this go...
LOL...
You are funny, Mr None.
Curious
> Here is another result on your AMD platform...
WRONG... not his AMD platform, someone elses, HE had k6-2 and these numbers
plainly shows that THESE are from way faster CPU, so that means most likely
AMD Athlon ...
>
> Bresenham Line Algorithm:
> 5.798 seconds, avg 17247.326 lps
>
> Wu Line Algorithm
> 7.081 seconds, avg 14122.298 lps
>
> Extremely Fast Line Algorithm-addition fixed Point
> 5.648 seconds, avg 17705.382 lps
>
> You have a laptop that is 10 times slower? That is a lot compared to
> 2 or three times. And those seconds. 800 seconds compared to single
> digit seconds... That is about 100 times or more in difference.
And DO you have any knowledge speed differences in AMD k6-2 CPU, and AMD
Athlon for example? MHZ numbers do not tell whole tale of CPU speed anyway.
Besides your test gives out number LINES / Second... so think about it what
is WRONG in that... Slower CPU, slower numbers you get, no? That comes
simple fact that CPU:s are not same speed, no? ;)
Let's assume that numbers (lines / second) are 10 times SMALLER in one
second on slower system... So if that same test goes on 10 second that means
there's difference of 10 x 10 in total lines drawn = 100... No? and that
tells that SLOWER system would simply spend 100 times more time doing test,
no?
< SNIP A LOT MORE >
None
>
> Let's assume that numbers (lines / second) are 10 times SMALLER in one
> second on slower system... So if that same test goes on 10 second that means
> there's difference of 10 x 10 in total lines drawn = 100... No? and that
> tells that SLOWER system would simply spend 100 times more time doing test,
> no?
Something wrong with your math here...
Even if it takes 10 times slower on one system than another (per one second).
Let A=Time for system ONE
B=Time for system TWO (A * 10)
Total time for 10 seconds...
A=A*10
B=(A*10)*10
B is still only 10 times longer (slower). You forgot that time does not
stop for system A, when you are concentrating on system B, and vice-versa.
Here is another analogy. Suppose you were bicycling...
Two bicycles.
One has circumference of 1 meter (suppose).
Another has circumference of 10 meters (suppose).
If you let both run for 10 revolutions each, how much farther is one compared
to the other?
The first would be 1x10=10.
The second would be 10x(10)=100.
So the second travels not 100 times farther, but only 10 times farther. That
is because when you are looking at cycle number 2, you forgot that cycle
number 1 was also moving.
None
> Don't be childish. I know you oriental folks have a fetish about not "losing
> face", but just get on with it.. your algorithm is the fastest, isn't that
> what you were convinced about even before you bothered to post here.
>
> Don't let us western Devils to discourage you from your efforts, we are just
> plain evil!
Nope. Personal attacks ignored.
Suggestion: Take a break from the net, your dark side is showing.
None
Not as funny as this thread being the longest on this forum...
Curious
READ what is said...
Don't just JUMP there in "babbling mode" try babble some fuzz and hide
facts, YOUR facts you provided...
Take calculator there while you "walk" through this explanation.
Do the math while you read...
> Here is another analogy. Suppose you were bicycling...
> Two bicycles.
>
> One has circumference of 1 meter (suppose).
> Another has circumference of 10 meters (suppose).
>
> If you let both run for 10 revolutions each, how much farther is one
compared
> to the other?
>
> The first would be 1x10=10.
> The second would be 10x(10)=100.
>
> So the second travels not 100 times farther, but only 10 times farther.
That
> is because when you are looking at cycle number 2, you forgot that cycle
> number 1 was also moving.
this analogy don't APPLY on this case... see below some explanations and
wake up and smell the coffee...
YOURSELF earlier SAID that....
> Ok, lets examine your data taking in account of EFLA...
>
> 1 Million lines at 1165.490 lines/sec
> Thats equals to 858.008 seconds
>
>What is wrong with this data?
>Here is another independent benchmark using the AMD CPU.
>Extremely Fast Line Algorithm-addition fixed Point
>5.648 seconds, avg 17705.382 lps
that data SHOWS that there were in LATER "your independent AMD" test
17705.382 * 5.648 = roughly 100000 lines, YES or NO?)
that also shows that there were in Mr Bonds test 1165.490 * 858.008 =
roughly 1000000 lines, YES, or NO? = 10 x MORE lines total compared your
"independednt AMD test", YES or NO?
that shows Mr Bonds test was having 900000 lines more, YES or NO?
if computer A manages draw 1165.490 lines / second, and computer B manages
draw 17705.382 lines / second, that leaves fact that...
computer A = 100000 / 17705.382 = 5.648 no?
notice... __YOUR___ "independend AMD" test scores claimed that! Tests that
were not MILLION lines in test, but 100000 instead if you can do simple
multiplication, YES, or NO?
and
computer B = 1000000 / 1165.490 = roughly about 858.008 seconds, YES or
NO? cause Mr Bond test witn his k6 run FULL million lines, where your
"independed AMD test" ran only 100000 lines = 1/10th of HIS test, YES or NO?
That leaves fact that Mr Bonds test would taken with SAME "only" 100000
lines about 85.8 seconds, simple maths tell that, but because HIS test
results were whole FULL MILLION line test _while_ your claimed "independed
AMD test" drew only 1/10th of that amount of lines, it would taken already
on that claimed "independent AMD test" aproximately 50,832sec (9 * 5.648
sec) MORE to do whole 1000000 lines test, YES, or NO?
So you can Try what ever bullshitting you want... but that does NOT leave
that faster AMD computer "run" rest MISSING 900000 lines compared Bond's
test (see your analogy up), when YOU compare from faster computers 100000
lines test to 1000000 on his SLOWER computer... YES, or NO?
If there were difference of speed about 15 times, and then SLOWER system
had draw about 900000 lines more it is very NORMAL that there is way over
100 times difference in test results (150 times maybe? some MORE math...
858.008 / 5.648 = 151.914) , YES or NO?
Simple math even ape should manage tells you that much, but then again I
guess you need bit evolving do that kinda math anyway if you haven't get
that idea by now... Hopefully this new year provides that evolving to you...
Still, DO math above and see DIFFERENCE...
I rest my case here, happy new year...
Jukka Liimatta
> facts, YOUR facts you provided...
Yeah, and about timing methods.. he claims the "putpixel()" is a constant
which will "cancel out", like this:
(A+X) - (B+X) = A - B
This only leaves the time of algoritm to be compared, but he never does the
subtraction, he displayes the times of:
print A+X
print B+X
.. so what we see as results, include the X, he says it cancels out (sure it
does, if you compare at the overall times, you can see some are a bit
faster, some a bit slower).
What if I add sleep(10) into the putpixel(), and yet claim that the X still
cancels out. Now the test takes 167 minutes for all cases, +- few seconds.
;-) Now it turns up that all line draw routines to appear to be the SAME
SPEED (+- few seconds, which is a few millionth of a difference in runtime,
which doesn't make the speed differences very obvious). But this is the way
he thinks it should be timed.
Then... he claims CRAP is beater, if we did time it the way he still
suggests is the best way to time ,it would be order of magnitude faster. How
does he thank for finally getting EFLA into correct ballpark of performance?
;-) If not for this thread, which he claims is funny to be so long, he would
still think EFLA-A,B and C were world's fastest algorithms. This newsgroup
basicly is responsible for the EFLA-C, for which *he* takes the credit.
Amazing!
Also, he claims he can do something and other people can not. When other
people do it, he discredits them (with no proof) and does not do it himself.
Very concinving.
All in all, he should thank the newsgroup on his knees that we told him that
algorithms like EFLA-C (lineDDA) existed for a long, long time before. If
you take lineDDA, and scale other axis so that the step there is precisely
1.0 along the axis, it's EFLA right there. And that is precisely how I seen
DDA always implemented in practical solutions, ie. where lines actually need
to be drawn fast.
He still takes credit for all of that, though... pretty shameless. ;-)
--
Jukka
Jukka Liimatta
> > You are funny, Mr None.
>
> Not as funny as this thread being the longest on this forum...
You're absolute correct for once. ;-)
--
Jukka
Jukka Liimatta
Yeah, I can see they are.
> Suggestion: Take a break from the net, your dark side is showing.
I'm not your apprentice, my Master is The Emperor Palpatine. ;-)
--
Jukka
Curious
> Yeah, and about timing methods.. he claims the "putpixel()" is a constant
> which will "cancel out", like this:
>
> (A+X) - (B+X) = A - B
>
> This only leaves the time of algoritm to be compared, but he never does
the
> subtraction, he displayes the times of:
> print A+X
> print B+X
>
> .. so what we see as results, include the X, he says it cancels out (sure
it
> does, if you compare at the overall times, you can see some are a bit
> faster, some a bit slower).
Yes, what makes one think that why putpixel is not taken out totally to see
what changes it would bring in result when now there is only algorithm
against algorithm...
> What if I add sleep(10) into the putpixel(), and yet claim that the X
still
> cancels out. Now the test takes 167 minutes for all cases, +- few seconds.
> ;-) Now it turns up that all line draw routines to appear to be the SAME
> SPEED (+- few seconds, which is a few millionth of a difference in
runtime,
> which doesn't make the speed differences very obvious). But this is the
way
> he thinks it should be timed.
yes, more there is timed OTHER than algorithm code, more less meaning real
algorithm has from total time because it's time it takes becomes smaller and
smaller from whole result.
Besides when doing benchmarking ATLEAST he should do series of benchmarks to
see how much times differ to know what's possible error in times. not just
one run.
< SNIP >
> Also, he claims he can do something and other people can not. When other
> people do it, he discredits them (with no proof) and does not do it
himself.
> Very concinving.
hehe :) You would not believe how much laughs i had when i was reading whole
thread and how he accuse everyone faking results if they differ from
anything that he wants point out.
> All in all, he should thank the newsgroup on his knees that we told him
that
> algorithms like EFLA-C (lineDDA) existed for a long, long time before. If
> you take lineDDA, and scale other axis so that the step there is precisely
> 1.0 along the axis, it's EFLA right there. And that is precisely how I
seen
> DDA always implemented in practical solutions, ie. where lines actually
need
> to be drawn fast.
Yes, someone pointed him DDA straight from book :) that gave good laugh
when he didn't even see it draws any direction :)) heh looks like he lacks
some knowledge in programming aswell not to see "EFLA" be just DDA splitted
to draw different those X / Y basically... most likely because of one INC to
get rid of that way...
> He still takes credit for all of that, though... pretty shameless. ;-)
Yea, well, there's always someone doing that anyway ;)
> --
> Jukka