My Algorithms
Extremely Fast Line Algorithm
Copyright
2001, By Po-Han Lin
POHANL@YAHOO.COM
The Extremely Fast Line
Algorithm (EFLA) is a homebrew algorithm that is extremely simple and
fast.
EFLA beats the most popular (Bresenham) and advanced (Wu's
Symmetric Double-Step) algorithms that are not CPU instruction dependent (i.e.
multiplatform, 64, 32 or 16 bit architectures, and no assembly
speedups)
There are four variations of the Extremely Fast Line Algorithm.
They use division, multiplication, addition, and addition with fixed point. Each
of these do not contain any branch instructions within the loop. Branching is a
source of significant slowdown on current pipelined superscalar CPU's. 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.
Here is the source for Extremely Fast Line
Algorithm (division, multiplication, and addition variations all
included)...
Extremely Fast
Line Algorithm Variation A (Division)
Extremely Fast Line Algorithm Variation
B (Multiplication)
Extremely Fast Line Algorithm Variation
C (Addition)
Extremely Fast
Line Algorithm Variation D (Addition Fixed Point)
Included in the
EFLA algorithms are functions to generate rectangles and squares. The square
algorithm uses second vertex to determine the square in a clockwise
fashion.
EFLA Variation D beats the most popular algorithm
(Bresenham) and the most advanced one (Wu) with or without compiler
optimizations turned on.
Benchmark data: Pentium III 450Mhz, Visual C++
6.0 Release Build, Optimizations on...
| Algorithm |
Lines Drawn (x1000) |
Seconds |
Lines Per Second |
| DDA |
1600 |
529.101 |
3023.997 |
| Bresenham |
1600 |
83.220 |
19226.147 |
| Wu |
1600 |
75.949 |
21066.767 |
| EFLA Variation D |
1600 |
65.914 |
24274.053 |
The source for the benchmark:
Benchmark Source
The
source for Bresenham, Wu, and DDA:
Bresenham Line
Algorithm
Wu Line
Algorithm
DDA Line
Algorithm
Return to Shareware
Depot