## Fast Line Draw Method

Many years ago (around 1984) I got my very first Motorola VME-10 development system. It ran a real-time OS named VersaDOS and could multi-task if you wanted to hook several CRT terminals up to it. It was based on the 68010 CPU and had a fairly nice graphics system. I used it for all my program development and had it feeding source code into our Computer Automation LSI-2 Naked Mini to compile programs because the CA only had floppy drives and an OS that didn't support folders. Supporting multiple jobs for many customers on a flat file system is not fun and trying to keep all the source code on a flat directory was impossible. The VME-10 had a multi-user file system to allow separate accounts and could feed the CA to compile code while I worked on other jobs. Of course, this was all due to some custom programs I came up with to automate the systems.

One day I decided to have some fun so I wrote some line and circle drawing routines that directly addressed the pixel locations as Motorola didn't provide any primitive graphic operations. This line drawing method I came up with is similar to Bresenham's line algorithm except it uses only integer math and works for lines in all directions. It is based on the equation for a line, converted to an integer differential analyzer. Such line drawing methods are useful if you need to quickly process pixels along an arbitrary line in an image.

Consider the equation of a line for pixels (x, y) from (0, 0) to (10, 1). We can calculate y from x by using y = y1 + x*dy/dx for x from x1 = 0 to x2 = 10 where dy = 1 and dx = 10. Because pixels are expressed as integer locations, we need to use trunc(y + 0.5) to get the line to increment at the center. This works only for dx>=dy and dx>=0 and dy>=0. In C we would write:

```const int x1=0;
const int x2=10;
const int y1=0;
const int y2=1;
const double dx=x2-x1;
const double dy=y2-y1;
double y;
int iy;

for (int ix=x1;ix<=x2;ix++)
{
y=y1+ix*dy/dx;
iy=trunc(y+0.5);
plot(ix,iy);
}
```

This can be converted to simple addition in this way:

```const double slope=dy/dx;
ix=x1;
y=y1+0.5;

while (ix<=x2)
{
plot(ix,trunc(y));
y=y+slope;
ix++;
}
```

Now the trick is to convert this so we don't need to work with y. We do this by introducing a ysum value. Instead of working directly with y, we only increment iy when we accumulate each slope total of 1:

```const double s=dy/dx;
ix=x1;
iy=y1;
double ysum=0.5;

while (ix<=x2)
{
plot(ix,iy);
ysum=ysum+s;
if (ysum>=1.0)
{
ysum=ysum-1.0;
iy++;
}
ix++;
}
```

This still isn't all integer mode, so we see that we can use all integers if we multiply everything related to ysum by dx:

```const int idx=x2-x1;
const int idy=y2-y1;
ix=x1;
iy=y1;
int ysum=idx/2;

while (ix<=x2)
{
plot(ix,iy);
ysum=ysum+idy;
if (ysum>=idx)
{
ysum=ysum-idx;
iy++;
}
ix++;
}
```

Work this out for all line directions and add steering logic and you have my method. For another way of doing this see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm.

Here is a modern C++ class definition for a parametric line with the drawing methods:

```//---------------------------------------------------------------------------
#ifndef LineDrawH
#define LineDrawH

//---------------------------------------------------------------------------
// parametric line class
class TVT_ParaLine
{
private:
bool xInc,pdx,pdy;
protected:
public:
// this constructs an integer based line from (X1, Y1) to (X2, Y2)
TVT_ParaLine(int X1, int Y1, int X2, int Y2);

/*
fast interpolation of pixels along line
example use:
SetFirst(X,Y);
do {
(process pixel X,Y here)
} while (NextXY(X,Y));
*/
void SetFirst(int& X, int& Y);
bool NextXY(int& X, int& Y);
};
//---------------------------------------------------------------------------

#endif

```

Here is the implementation of the class:

```//---------------------------------------------------------------------------
#include "LineDraw.h"
#include <math.h>
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
TVT_ParaLine::TVT_ParaLine(int X1, int Y1, int X2, int Y2)
{
ix1=X1;
iy1=Y1;
ix2=X2;
iy2=Y2;
idx=X2-X1;
idy=Y2-Y1;
pdx=idx>=0;
pdy=idy>=0;
}
//---------------------------------------------------------------------------
void TVT_ParaLine::SetFirst(int& X, int& Y)
{
if (xInc)
{
}
else
{
}
X=ix1;
Y=iy1;
}
//---------------------------------------------------------------------------
bool TVT_ParaLine::NextXY(int& X, int& Y)
{
bool done;

if (xInc)
{
{
if (pdy) Y++; else Y--;
}
if (pdx)
{
X++;
done=X>ix2;
}
else
{
X--;
done=X<ix2;
}
}
else
{
{
if (pdx) X++; else X--;
}
if (pdy)
{
Y++;
done=Y>iy2;
}
else
{
Y--;
done=Y<iy2;
}
}
return !done;
}
//---------------------------------------------------------------------------

```