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; int ix1,iy1,ix2,iy2,idx,idy,adx,ady,IncSum; 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; adx=abs(idx); ady=abs(idy); xInc=adx>=ady; pdx=idx>=0; pdy=idy>=0; } //--------------------------------------------------------------------------- void TVT_ParaLine::SetFirst(int& X, int& Y) { if (xInc) { IncSum=adx/2; } else { IncSum=ady/2; } X=ix1; Y=iy1; } //--------------------------------------------------------------------------- bool TVT_ParaLine::NextXY(int& X, int& Y) { bool done; if (xInc) { if ((IncSum+=ady)>=adx) { if (pdy) Y++; else Y--; IncSum-=adx; } if (pdx) { X++; done=X>ix2; } else { X--; done=X<ix2; } } else { if ((IncSum+=adx)>=ady) { if (pdx) X++; else X--; IncSum-=ady; } if (pdy) { Y++; done=Y>iy2; } else { Y--; done=Y<iy2; } } return !done; } //---------------------------------------------------------------------------