Solutions for Assignment 1

Baseline Solution

Here is the code, with comments. Enjoy!

// drawLine (int x1, int y1, int x2, int y2);
// handles first octant:  dx,dy > 0; dy <= dx
int x, y, d;
int twody =  ( y1-y2 ) << 1;   // slope:  dy/dx * 2dx (flipped)
int twodx =  ( x2-x1 ) << 1;   // unit increment:  1 * 2dx

d = -twodx >> 1;  // initially, segment is half a pixel below M
y = y1;
for ( x = x1; x <= x2; x++ ) {
  setPixel (x, y);
  d += twody;
  if ( d >= 0 ) {
    d -= twodx;
    y--;  // decrement y due to screen flip
    }
}

Better Yet

And here is the generalized solution.

// drawLine (int x1, int y1, int x2, int y2);
// handles all 8 octants, all special cases
int x, y, dx, dy, npix;
int xinc, yinc, xup, yup; // advance step; error step
int e, einc, emax;        // error; err inc; err limit

dx = x2-x1;  dy = y2-y1;  // x,y deltas and sign bits
xinc = (dx >= 0) ? 1 : -1;
yinc = (dy >= 0) ? 1 : -1;

if ( (xinc * dx) > (yinc * dy) ) { // loop across x
  npix = (dx * xinc) + 1;          // note:  non-neg
  emax = dx * xinc;
  einc = (dy * yinc) << 1;
  xup = 0;
  yup = yinc;
  yinc = 0; // adv, err steps
  }
else {                             // loop across y
  npix = (dy * yinc) + 1;          // note:  non-neg
  emax = dy * yinc;
  einc = (dx * xinc) << 1;
  yup = 0;
  xup = xinc;
  xinc = 0; // adv, err steps
  }

x = x1;
y = y1;
e = 0;    // error initially zero
while ( npix-- > 0 ) {
  setPixel (x, y);
  x += xinc;
  y += yinc; 
  e += einc; // advance step
  if ( e > emax ) {
    x += xup;
    y += yup;
    e -= emax << 1; // error step
    }
  }