Ghost Town Sage

Fixed Point Line Algorithm

Drawing a straight line on a grid of pixels.

When I created my Pikes Peak Trailguide software back in the 1990's, I needed to draw millions of lines on the screen fast, and they needed to be of assorted styles. There are several common techniques for drawing lines but I didn't like any of them, and I had a hunch that there was a simpler and faster way.
It took two weeks to realize my vague hunch, but I was correct - the technique I came up with is far simpler and faster than any of the more popular methods. And it also lends its self very well to modified line styles such as double, dashed or hashed lines. I filed for a patent on this technique, but was turned down because Silicon Graphics had done something similar.
Originaly posted 2011.

The Point-Slope Formula

First, let's take a quick look at the general concept of drawing lines on a computer screen. Lines & Dots

All techniques that draw lines on a grid of dots use different variations of the point-slope formula to light up the points between two end points.
For example, a line between point (0,0) and (11,3) would draw a dot at coordinates:
(0,0) (1,0) (2,1) (3,1) (4,1) (5,1) (6,2) (7,2) (8,2) (9,2) (10,3) (11,3)

There are three common ways to draw a line.
These examples are written in simplified pascal. They assume the line is moving to the right, and both end points will be plotted.

1. Use the Point-Slope formula on each pixel:
This is the first thing that come's to mind when you're in a pinch, but it's horribly slow. The loop increments the X and calculates the Y with complicated floating point math:

  
   procedure  DrawLine (X1,Y1,X2,Y2)
   for X := X1 to X2 do 
      Y := X * (Y2-Y1) / (X2-X1);
      DrawPixel(X,Y);
   end;

2. Pre-calculate the slope and add it to each point:
Any competent programmer would instinctivly pre-calc the loop, and most optimizing compiliers would do it even if the programmer didn't. This is probably ten times faster and it's pretty easy to implement, but it still has floating point math in the loop.

  
   procedure  DrawLine (X1,Y1,X2,Y2)
   float S := (Y2-Y1) / (X2-X1);
   int Y := Y1;
   for X := X1 to X2 do 
      DrawPixel(X,Y);
      Y := Round (Y + S);
   end;

3. Bresenham's Algorithm:
This is quite a bit faster, and it's the technique used in most compiliers. But nobody writes this off the top of his head, and even some tutorials I've read didn't seem to know why this works. In reality, the concept is simple: Instead of dividing delta-Y by delta-X to get the slope, Bresenham just keeps adding delta-Y until it excedes delta-X then steps down a pixel each time it does. Notice that there is no floating point math.

  
   procedure  DrawLine (X1,Y1, X2,Y2);
      deltaX := X2-X1;
      deltaY := Y2-Y1;
      Yacc := deltaX div 2;
      Y := Y1;
      for  X := X1 to X2  do 
         DrawPixel (X, Y);
         Yacc := Yacc + deltaY;
         if  Yacc >= deltaX  then 
            Y := Y + 1;
            Yacc := Yacc - deltaX;
         end;
      end;
   end;

Those techniques are simple enough, but I needed something faster, more versatile, and would work in RAM. So I took the precalc slope formula above and converted it from floating point numbers to fixed-point fractions, but I did it in a way that is vastly faster than the original.

The Fixed-Point Slope Method

Hold on to your seats people. Lines & Dots

In my fixed-point scheme, I use a 4-byte integer to store a decimal number. The most significant 2 bytes are the 16 bit integer portion, the least significant 2 bytes are the 16 bit fraction. Each count in the 16 bit fraction is 1/65536, so the value 32768 would be 1/2.
Here's the key: if you count upwards through the fractional portion, it will automatically increment the integer portion when the fraction overflows. This allows me to use 16 bit integer math to control the integer or the fraction, and 32 bit integer math to control the whole fixed-point number. It works like magic.

The key to a fixed-point number is Pascal's bizarre variant record:

  
   FourByte = record case integer of
      0 : (A   : int-32),  // A = All 4 bytes 
      1 : (F,I : int-16);  // F = LSW, I = MSW 
   end;

The syntax is actually straight forward:
The variable Y.A is 32 bit whole number.
The variable Y.I is 16 bit integer portion.
The variable Y.F is 16 bit fraction portion.

This magic will allow me to add the slope to the fraction portion, then plot the integer portion without any math in between.
The function would be written in Pascal like this:

  
    1   Procedure  DrawLine (X1,Y1, X2,Y2 : int-16);
    2   var Slope : int-16;
    3       Xpos  : int-16;
    4       Ypos  : FourByte;
    5   begin
    6      Ypos.F := 0;
    7      Ypos.I := Y2-Y1;
    8      Slope  := Ypos.A div (X2-X1);
    9      Ypos.F := 32768;
   10      Ypos.I := Y1;
   11      for  Xpos := X1 to X2  do begin
   12         Array [Xpos, Ypos.I];
   13         Ypos.A := Ypos.A + Slope;
   14      end;
   15   end;

Setting up the loop is a little complicated, but note that within the loop there is only a single addition and plot the pixel. Bresenham's had four operations and plot the pixel. This looks too simple to work.

Here's what's happening, a line at a time:

Lines 6 & 7 load the 16 bit delta-Y into the Most Significant Word of YPos - effectivly multiplying by 65536.
Line 8 divides the 32 bit Ypos by the 16 bit delta-X, the result will be a number between 0 and 65535. This is the Slope, assumed to be a fraction less than one.
Line 9 starts the Y fraction at 1/2. This will cause the counter to round up as the Slope is added.
Line 10 starts the Y integer at the starting pixel value.
Line 11 runs the loop from X1 to X2.
Line 12 uses the integer portion of the Y value to plot the pixel in a 2-dimensional array.
Line 13 adds the 16 bit Slope to the whole Y value. If the result overflows the lower 16 bits, it will automatically increment the upper 16 bits and point to the next pixel.
Line 14 repeats the loop.

As you can see, the whole key to this technique is to add the 16 bit slope to the lower 16 bits of the Y value, thereby incrementing the upper 16 bits and pointing to the next pixel. That whole sentence takes only a single addition! You won't find a simpler or faster way to draw lines on the screen or in RAM. (That key was missed in the Silicon Graphics patent.)

All of these examples will only work if the line is moving to the right and stepping down. To make a functional routine, you will have to use 4 IF's for lines moving right, left, up or down. I think the slope will work if the steps are moving up or down. Try it and see what you think.

Notes:
* These examples are written in Pascal because I do most of my programming in Delphi, which is visual/object Pascal. These variants can be done in other languages by using pointers and typecasts.
* The examples above only work on a line moving to the right and down. Other directions will need to be handled.
* These examples plot both end points of the line, but most programming environments do not plot the final point.
* Nearly all programming languages include a line drawing function, but this technique is still handy in case you need to draw in RAM. I originally wrote this for MS-DOS graphics, which did not include a line function in the API.