Folding-Hyperspace

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;
}
//---------------------------------------------------------------------------