edepot World Religion Music Money Games Stores Forums Feedback Search Sitemap

Algorithms Repository




Extremely Fast Line Algorithm


Copyright (c) 2005, By Po-Han Lin
Contact and Feedback
Fast Computer Graphics Line-Drawing Algorithms
Fast Line Algorithms (Computer Graphics Line-Drawing)
Freely useable in non-commercial applications as long as credits to Po-Han Lin and a link to http://www.edepot.com/algorithm.html is provided in source code (whether released to public or not) and the credit and link URL can be seen in running compiled executable. Commercial applications please inquire about licensing the algorithms.
Thanks to Ruud, Gordy, and Eric Grange for tips and pointers. Also to Alexander for the benchmark.
The Extremely Fast Line Algorithm (EFLA) is a homebrew line drawing 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 five released variations of the Extremely Fast Line Algorithm. They use division, multiplication, addition, and addition with fixed point, and variation with some precalculations. 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)

Extremely Fast Line Algorithm Variation E (Addition Fixed Point With Precalculations)

For small displays (like cell phones):
Extremely Fast Line Algorithm Variation E (Addition Fixed Point With Precalculations: 256x256 Resolution)


Note: For EFLA A to D, the algorithm is optimized for multi-line segments (similar to Window's LineTo where the ending pixel is not plotted). In EFLA-D and E the fixed point accuracy can be increased for longer lines. The special small mobile device display version (256x256) has 0x80 and 8 bits of fixed point accuracy. Standard displays can use the 0x8000 and 16 bits of fixed point accuracy. Accuracy of fixed point can be changed for specialized versions via the fixed point number (8 or 16) and the rounding (0x80 or 0x8000) accordingly. For example 8 bits of accuracy accounts for 256x256, 9 bits for 512x512, 10 bits for 1024x1024, 16 bits for 65536x65536 displays.


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 E 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, Default Maximum Speed Optimization...
AlgorithmLines Drawn (x1000)SecondsLines Per Second
DDA1600504.4763171.608
Bresenham160080.44619889.117
Wu160072.89521949.378
EFLA Variation E160063.80125077.976

The source for the benchmark:
Benchmark Source

The source for Bresenham, Wu, and DDA:
Bresenham Line Algorithm
Wu Line Algorithm
DDA Line Algorithm


Over the years after posting this on the internet, I've gotten some inquiries from people who are not knowledgeable about line algorithms, DDA, and fixed point, so I will summarize it here. EFLA is not DDA. EFLA is a line algorithm. Just like Bresenham is not DDA. It is a line algorithm. Just because something uses fixed point or DDA does not mean any line algorithm that uses either is a DDA or a fixed point. Nor does it mean every line algorithm that uses fixed point or DDA are the same. DDA just means digital differential analysis, and is like a tool. That is not a line algorithm. There is no DDA line algorithm (but some like to call it DDA because it uses it, even I have provided a DDA based line algorithm in the benchmark). You can use DDA for line algorithm, but you still need to invent the algorithm. You can use DDA for ANYTHING, including circles. Even Bresenham uses DDA, but people don't call it DDA. EFLA is called EFLA. If you are the type of people who are not able to code, don't just copy and steal other's work. Respect the rights of inventors and copyrighters. Besides legal consequences, it is not right. Imagine if one day you created a piece of work, and others remove your name from it and replace it with their own.

Programs and Games using the EFLA line algorithm for Sony PSP


These homebrew games using EFLA line algorithm can run on the Sony PSP (Playstation Portable) off of the memory stick.

Ceres 1.1 "asteroids" clone for firmware 1.0 and 1.5
LuLines 1.1 line segments for firmware 1.0
AgenaWorld 1.1 "homeworld" clone for firmware 1.0 and 1.5


Simplest (and smallest code size) Maze Generator

 By: Po-Han Lin
fractal maze generator

world's smallest, simplest, maze generator

It uses what I call fractal maze generation. Fractal in a sense that, like genetics, a few genes creates complex organisms. And similarly, one line of decision making code makes a whole maze. The rest are just loops deciding on how big is the maze. It uses just two ascii characters (forward and back slash). By permutating between these two characters a fancy maze can be made. Total is about 5 lines of code for the maze generation. Source included.
Fractal Maze Generator source (Project Hosting at Google Code)

Direct Download (zip file)

Think EFLA and the fractal maze algorithm are cool? Check out this Arbitrary Precision Calculator that supports arbitrary base.


Shortest Path Algorithm

By: Po-Han Lin
Here is a homebrew two-pass shortest path algorithm for a small sim game in development. If you use this algorithm please link to this webpage on a site and give credits in the program.
The algorithm has two passes. There is a M x N matrix, each marked as empty. Destination is marked (for example X). First pass is to mark all empty adjacent nodes to X (or to nodes already connected with direction) to 1. Second pass is to connect nodes with 1 to its neighbor that is already connected (those with a direction.) If there are two or more nodes, loop through clockwise and choose the first node with a direction (or in a fixed predetermined sequence of selection). In the examples below the clockwise check starts with the E (east) direction. Nodes can be connected only if they are walkable (those marked as 1 in the first pass). Note that it can be 1 or any number. The number 1 is used in this case, but in the program 255 is used (fits within a byte value). The nodes are built up in successive row passes and the robot simply finds out which node they are on and look up which direction to take. If it is 1 or 0 (empty) then don't yet because there is no shortest path or the path is not possible. In the example below, assume all surroundings are walkable. It looks like a big square field as a result. In reality, in the program you can have non-walkable terrain which the first pass will not mark if it is not walkable. Also assumed is that one walkable node adjacent to another walkable node is always walkable from one to the other, and doors do not exist. In the program there may exist in the future doors that block a connection. To support this feature, simply have the first pass check if doors are closed and not mark it if it is.

X=destination

Initial Matrix
.....
.....
..X..
.....
.....

First pass:Second Pass
.....
..1..
.1X1.
..1..
.....
.....
..S..
.EXW.
..N..
.....

First pass:Second Pass
..1..
.1S1.
1EXW1
.1N1.
..1..
..S..
.ESS.
EEXWW
.ENW.
..N..


This example above does not allow diagonal movement. If you want diagonal movements, substitute directions with NW NE SW SE and make sure during the first pass diagonal adjacent nodes are checked and filled in with the number 1 if walkable.
Note that this two pass algorithm is made for use by a small number of robots and on a dynamic terrain that is being changed all the time. Another version allows for unlimited robots but that version does not perform well for dynamic terrains.
A small game demo for windows was made (it was originally made to be a shoe store game). Please read the readme.txt inside the zip file for instructions on installing and to play with the robot's behavior using this algorithm. To download visit the middle of the page of: Shoes Game