#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define SIZE 256

typedef struct { int x, y; } XY;
static XY points[] =
{
   {667,676},
   {688,740},{706,829},{760,852},
   {814,875},{855,755},{834,708},
   {813,661},{733,625},{667,676},
   {0,0},

   {182,764},
   {113,753},{108,886},{182,936},
   {251,982},{373,931},{348,881},
   {324,834},{251,775},{182,764},
   {0,0},

   {293,406},
   {404,499},{491,500},{664,573},
   {837,646},{938,501},{897,433},
   {832,326},{879,290},{793,144},
   {746,64},{620,38},{534,76},
   {394,138},{364,79},{280,122},
   {180,173},{171,304},{293,406},
   {0,0},

   {290,764},
   {260,780},{250,803},{238,830},
   {249,840},{262,848},{275,854},
   {288,824},{302,805},{331,805},
   {331,795},{313,764},{290,764},
   {0,0},

   {638,753},
   {647,768},{658,775},{671,775},
   {654,779},{631,779},{608,779},
   {615,770},{625,760},{638,753},
   {0,0},

   {671,775},
   {684,775},{699,769},{718,756},
   {726,768},{732,780},{738,793},
   {654,842},{641,814},{608,779},
   {620,776},{658,775},{671,775},
   {0,0},

   {279,288},
   {248,300},{283,384},{339,432},
   {312,484},{162,610},{290,764},
   {290,785},{303,805},{331,805},
   {344,805},{360,808},{380,816},
   {563,887},{822,659},{653,599},
   {659,587},{663,578},{668,564},
   {477,482},{436,227},{279,288},
   {0,0},

   {0, 0}
};

/* Interpolate between two points. */
static double Interpolate(double a, double b, double t)
{
   return a + (b - a) * t;
}

int main(int argc, char **argv)
{
   int width = SIZE;
   int height = SIZE;
   unsigned char *image, *w;
   int *range;
   int x, y, p = 0, t, shape_index = 0;
   double ft, scale;

   height += 6 - height % 6;
   image = w = calloc(width * height, 1);
   range = malloc(height * 2 * sizeof(int));
   if( image == NULL || range == NULL )
      return printf("Out of memory\n");
   scale = width / 1024.0;

   while( points[p].x != 0 )
   {
      /* Collect horizontal ranges for each scanline.

         This allows us to draw filled shapes one scanline at a time,
         and the shapes can be both convex and concave as long as each
         scanline is continuous.  We can enforce the continuous requirement
         by tweaking our shapes, saving us the complexity of having to
         write a more featureful rasterizer.                                */
      memset(range, 0, height * 2 * sizeof(int));
      for(; points[p + 1].x != 0; p += 3)
      {
         for(t = 0; t < height * 4; t++)
         {
            ft = (double)t / (height * 4.0);

            /* https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm */
            x = (int)
               Interpolate(
                  Interpolate(
                     Interpolate(points[p].x * scale, points[p+1].x * scale, ft),
                     Interpolate(points[p+1].x * scale, points[p+2].x * scale, ft),
                     ft),
                  Interpolate(
                     Interpolate(points[p+1].x * scale, points[p+2].x * scale, ft),
                     Interpolate(points[p+2].x * scale, points[p+3].x * scale, ft),
                     ft),
                  ft);
            y = (int)
               Interpolate(
                  Interpolate(
                     Interpolate(points[p].y * scale, points[p+1].y * scale, ft),
                     Interpolate(points[p+1].y * scale, points[p+2].y * scale, ft),
                     ft),
                  Interpolate(
                     Interpolate(points[p+1].y * scale, points[p+2].y * scale, ft),
                     Interpolate(points[p+2].y * scale, points[p+3].y * scale, ft),
                     ft),
                  ft);

            if( x > 0 && x < width && y >= 0 && y < height )
            {
               if( range[y * 2] == 0 )
               {
                  range[y * 2] = range[y * 2 + 1] = x;
               }
               else
               {
                  range[y * 2] = range[y * 2] < x ? range[y * 2] : x;
                  range[y * 2 + 1] = range[y * 2 + 1] > x ? range[y * 2 + 1] : x;
               }
            }
         }
      }

      /* Draw scanlines. */
      for(y = 0; y < height; y++)
      {
         if( range[y * 2] != 0 )
         {
            for(x = range[y * 2]; x <= range[y * 2 + 1]; x++)
               image[y * width + x] = shape_index < 3 ? (x + y) & 1 : 1;
         }
      }

      p += 2;
      shape_index++;
   }

   /* Convert to Sixel. */
   for(y = 0; y < height; y += 6)
   {
      for(x = 0; x < width; x++)
      {
         *w++ = 0x3f +
                image[y * width + x] +
                (image[(y + 1) * width + x] << 1) +
                (image[(y + 2) * width + x] << 2) +
                (image[(y + 3) * width + x] << 3) +
                (image[(y + 4) * width + x] << 4) +
                (image[(y + 5) * width + x] << 5);
      }
      *w++ = '-';
      *w++ = '\n';
   }

   /* Output image. */
   puts("\x1bPq");
   fwrite(image, w - image, 1, stdout);
   puts("\x1b\\");
   return 0;
}