Line drawing

gistfile1.txt

Need this stuff lots of times, so here's a collection of line drawing algorithms.

http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_4_Spatial_Subdivisions.shtml
http://archive.is/a7xIV#selection-1221.0-1371.47

static void RasterizeHeightFieldLine(const TPoint& p0, const TPoint& p1, int thickness, const std::function<void(int, int)>& atPointCallback)
{
   int x1 = (int)p0.x;
   int y1 = (int)p0.y;
   int x2 = (int)p1.x;
   int y2 = (int)p1.y;
   int x, y, dx, dy, dx1, dy1, px, py, xe, ye, i;
   dx  = x2 - x1;
   dy  = y2 - y1;
   dx1 = abs(dx);
   dy1 = abs(dy);
   px  = 2 * dy1 - dx1;
   py  = 2 * dx1 - dy1;
   if (dy1 <= dx1) {
      if (dx >= 0) {
         x  = x1;
         y  = y1;
         xe = x2;
      }
      else {
         x  = x2;
         y  = y2;
         xe = x1;
      }
      atPointCallback(x, y);
      for (i = 0; x < xe; i++) {
         x = x + 1;
         if (px < 0) {
            px = px + 2 * dy1;
         }
         else {
            if ((dx < 0 && dy < 0) || (dx > 0 && dy > 0)) {
               y = y + 1;
            }
            else {
               y = y - 1;
            }
            px = px + 2 * (dy1 - dx1);
         }
         atPointCallback(x, y);
      }
   }
   else {
      if (dy >= 0) {
         x  = x1;
         y  = y1;
         ye = y2;
      }
      else {
         x  = x2;
         y  = y2;
         ye = y1;
      }
      atPointCallback(x, y);
      for (i = 0; y < ye; i++) {
         y = y + 1;
         if (py <= 0) {
            py = py + 2 * dx1;
         }
         else {
            if ((dx < 0 && dy < 0) || (dx > 0 && dy > 0)) {
               x = x + 1;
            }
            else {
               x = x - 1;
            }
            py = py + 2 * (dx1 - dy1);
         }
         atPointCallback(x, y);
      }
   }
}

static void RasterizeHeightFieldLine2(const btVector3& start, const btVector3& end, const std::function<void(int, int)>& atPointCallback)
{
   float difX = end.getX() - start.getX();
   float difY = end.getZ() - start.getZ();
   float dist = abs(difX) + abs(difY);

   float dx = difX / dist;
   float dy = difY / dist;

   auto cdist = (int)ceil(dist);
   for (int i = 0; i <= cdist; ++i) {
      auto x = floor(start.getX() + dx * i);
      auto y = floor(start.getZ() + dy * i);
      atPointCallback((int)x, (int)y);
   }
}

static void RasterizeHeightFieldLine3(int x0, int y0, int x1, int y1, const std::function<void(int, int)>& atPointCallback)
{
   int kx, ky, c, i;
   x1 -= x0;
   kx = 0;
   if (x1 > 0)
      kx = +1;
   if (x1 < 0) {
      kx = -1;
      x1 = -x1;
   }
   x1++;
   y1 -= y0;
   ky = 0;
   if (y1 > 0)
      ky = +1;
   if (y1 < 0) {
      ky = -1;
      y1 = -y1;
   }
   y1++;
   if (x1 >= y1)
      for (c = x1, i = 0; i < x1; i++, x0 += kx) {
         atPointCallback(x0, y0); // this is normal pixel the two below are subpixels
         c -= y1;
         if (c <= 0) {
            if (i != x1 - 1)
               atPointCallback(x0 + kx, y0);
            c += x1;
            y0 += ky;
            if (i != x1 - 1)
               atPointCallback(x0, y0);
         }
      }
   else
      for (c = y1, i = 0; i < y1; i++, y0 += ky) {
         atPointCallback(x0, y0); // this is normal pixel the two below are subpixels
         c -= x1;
         if (c <= 0) {
            if (i != y1 - 1)
               atPointCallback(x0, y0 + ky);
            c += y1;
            x0 += kx;
            if (i != y1 - 1)
               atPointCallback(x0, y0);
         }
      }
}

template <typename T>
int signum(T val)
{
   return (T(0) < val) - (val < T(0));
}

static void RasterizeHeightFieldLine4(double y1, double x1, double y2, double x2, const std::function<void(int, int)>& atPointCallback)
{
   int x = (int)x1, y = (int)y1;
   int endX = (int)x2, endY = (int)y2;

   // deltaX and Y is how far we have to move in ray direction until we find a new cell in x or y direction
   // y = u + t * v, where u=(x1,x2) and v=(stepX,stepY) is the direction vector
   const double gridCellWidth = 1, gridCellHeight = 1;

   double deltaX = gridCellWidth / abs(x2 - x1);
   int    stepX  = (int)signum(x2 - x1);
   // frac(tmp) = tmp - (int) tmp
   double tmp  = x1 / gridCellWidth;
   double maxX = deltaX * (1.0 - (tmp - (int)tmp));

   double deltaY = gridCellHeight / abs(y2 - y1);
   int    stepY  = (int)signum(y2 - y1);
   tmp           = y1 / gridCellHeight;
   double maxY   = deltaY * (1.0 - (tmp - (int)tmp));

   bool reachedY = false, reachedX = false;

   // trace primary ray
   while (!(reachedX && reachedY)) {
      if (maxX < maxY) {
         maxX += deltaX;
         x += stepX;
      }
      else {
         maxY += deltaY;
         y += stepY;
      }

      atPointCallback(y, x);

      if (stepX > 0.0) {
         if (x >= endX)
            reachedX = true;
      }
      else if (x <= endX) {
         reachedX = true;
      }

      if (stepY > 0.0) {
         if (y >= endY)
            reachedY = true;
      }
      else if (y <= endY) {
         reachedY = true;
      }
   }
}

static void RasterizeHeightFieldLine5(float x1, float z1, float x2, float z2, const std::function<void(int, int)>& atPointCallback)
{
#define SIGN(x) (x > 0 ? 1 : (x < 0 ? -1 : 0))
#define FRAC0(x) (x - floorf(x))
#define FRAC1(x) (1 - x + floorf(x))

   float y1 = 0.0f;
   float y2 = 0.0f;

   float tMaxX, tMaxY, tMaxZ, tDeltaX, tDeltaY, tDeltaZ;
   int   voxel[3] = { 0, 0, 0 };

   int dx = SIGN(x2 - x1);
   if (dx != 0)
      tDeltaX = fmin(dx / (x2 - x1), 10000000.0f);
   else
      tDeltaX = 10000000.0f;
   if (dx > 0)
      tMaxX = tDeltaX * FRAC1(x1);
   else
      tMaxX = tDeltaX * FRAC0(x1);
   voxel[0] = (int)x1;

   int dy = SIGN(y2 - y1);
   if (dy != 0)
      tDeltaY = fmin(dy / (y2 - y1), 10000000.0f);
   else
      tDeltaY = 10000000.0f;
   if (dy > 0)
      tMaxY = tDeltaY * FRAC1(y1);
   else
      tMaxY = tDeltaY * FRAC0(y1);
   voxel[1] = (int)y1;

   int dz = SIGN(z2 - z1);
   if (dz != 0)
      tDeltaZ = fmin(dz / (z2 - z1), 10000000.0f);
   else
      tDeltaZ = 10000000.0f;
   if (dz > 0)
      tMaxZ = tDeltaZ * FRAC1(z1);
   else
      tMaxZ = tDeltaZ * FRAC0(z1);
   voxel[2] = (int)z1;

   while (true) {
      if (tMaxX < tMaxY) {
         if (tMaxX < tMaxZ) {
            voxel[0] += dx;
            tMaxX += tDeltaX;
         }
         else {
            voxel[2] += dz;
            tMaxZ += tDeltaZ;
         }
      }
      else {
         if (tMaxY < tMaxZ) {
            voxel[1] += dy;
            tMaxY += tDeltaY;
         }
         else {
            voxel[2] += dz;
            tMaxZ += tDeltaZ;
         }
      }
      if (tMaxX > 1 && tMaxY > 1 && tMaxZ > 1)
         break;
      atPointCallback(voxel[0], voxel[2]);
   }
}

static void RasterizeHeightFieldLine6(int x0, int y0, int x1, int y1, float wd, const std::function<void(int, int)>& atPointCallback)
{
   int   dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
   int   dy = abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
   int   err = dx - dy, e2, x2, y2; /* error value e_xy */
   float ed  = dx + dy == 0 ? 1 : sqrt((float)dx * dx + (float)dy * dy);

   for (wd = (wd + 1) / 2;;) { /* pixel loop */
      atPointCallback(x0, y0);
      e2 = err;
      x2 = x0;
      if (2 * e2 >= -dx) { /* x step */
         for (e2 += dy, y2 = y0; e2 < ed * wd && (y1 != y2 || dx > dy); e2 += dx)
            atPointCallback(x0, y2 += sy);
         if (x0 == x1)
            break;
         e2 = err;
         err -= dy;
         x0 += sx;
      }
      if (2 * e2 <= dy) { /* y step */
         for (e2 = dx - e2; e2 < ed * wd && (x1 != x2 || dx < dy); e2 += dy)
            atPointCallback(x2 += sx, y0);
         if (y0 == y1)
            break;
         err += dx;
         y0 += sy;
      }
   }
}