// jenny.c: generator for tables to perform perspective projection without overhead
// of fixed point multiplications and divisions.  See file percy.c for the code that
// uses the tables, which is what will be run on the Vectrex.  (This code here is
// for Linux and uses floating point to generate the initial table values.)

// We're going to use a lookup table, but a sparse one with linear interpolation between elements.
// At the moment I'm planning to only interpolate between the 3D X values to produce the 2D screen X coordinate,
// and likewise for Y.  I haven't yet decided whether to interpolate for Z or to have all 256 tables, nor
// have I decided whether we need to interpolate in all 3 dimension or just X and Y (or possibly XZ and YZ).
// The design decisions will be based on the compromise between speed of calculation and acceptability of
// the generated image.

//#define TEST_PERSP 1
//#define DEBUG_INTERPOLATION 1
//#define DUMP_TABLES 1
#define TEST_PROGRAM 1

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

typedef   int8_t XYCOORD;
typedef u_int8_t  ZCOORD;
typedef   int8_t  SCREEN;

int scale[64];

float check_sin(float angle) {
#ifdef DEBUG
  fprintf(stdout, "sin(%3.3f (%d)) = %3.3f (%d)\n",
          angle, (int)(angle*256),
          sin(angle), (int)(sin(angle)*256));
#endif
  return sin(angle);
}

float check_cos(float angle) {
#ifdef DEBUG
  fprintf(stdout, "cos(%3.3f (%d)) = %3.3f (%d)\n",
          angle, (int)(angle*256),
          cos(angle), (int)(cos(angle)*256));
#endif
  return cos(angle);
}


void *ckmalloc(int size) {
  void *p = malloc(size);
  if (p == NULL) {
    fprintf(stderr, "%d-byte malloc failed.\n", size);
    exit(EXIT_FAILURE);
  }
  return p;
}

static float screen_dist = 8.0;

void perspectivef(float x, float y, float z, float *pX, float *pY) {
  *pX = screen_dist*x/(z+screen_dist);
  *pY = screen_dist*y/(z+screen_dist);
}

void perspective(XYCOORD x, XYCOORD y, ZCOORD z, SCREEN *X, SCREEN *Y) {
  float Xf, Yf;
  perspectivef((float)x, (float)y, (float)z, &Xf, &Yf);
  *X = (int)Xf; *Y = (int)Yf;
  //if (z == 128 && ((x&15) == 0)) fprintf(stderr, "Persp: x=%d y=%d z=%d -> sX=%d sY=%d\n", x,y,z, *X,*Y);
}

// x table and y table should be the same due to symmetry, because the center
// of the screen (and our world coordinate system, and the viewers eyeball) is
// at 0,0.  So can we use a triangular matrix?
SCREEN ***sx; // , ***sy;  ... sy is identical in content to sx, but with x and y swapped.

static inline SCREEN *lookupxmap(XYCOORD x, XYCOORD y, ZCOORD z, int *N) { // N is the sign of what the value should be.
  *N = 1;
  if (x > 0) {*N = -1; x = -x;}  // symmetric, 0:127 -> 1:-127
  if (y > 0) {*N = -1; y = -y;}
  //fprintf(stderr, "x: %02x  y: %02x  z: %02x\n", x+128,y+128,z);
  return &sx[(x+128)>>4][(y+128)>>4][z>>2];  // map from -128:0 to 0:128
}

#ifdef NEVER
static inline SCREEN *lookupymap(XYCOORD x, XYCOORD y, ZCOORD z, int *N) {
  *N = 1;
  if (x > 0) {*N = -1; x = -x;}  // symmetric, 0:127 -> 1:-127
  if (y > 0) {*N = -1; y = -y;}
  //fprintf(stderr, "x: %02x  y: %02x  z: %02x\n", x+128,y+128,z);
  return &sy[(x+128)>>4][(y+128)>>4][(z+128)>>4];  // map from -128:0 to 0:128
}
#endif

static inline SCREEN lookupx(XYCOORD x, XYCOORD y, ZCOORD z) {
  int N;
  XYCOORD x0 =  (x>>4)   <<4;
  XYCOORD x1 = ((x>>4)+1)<<4; // BEWARE END CASE WHERE +1 WRAPS IN A BYTE.
  int frac = x&15;
  SCREEN *X0 = lookupxmap(x0,y,z,&N);
  SCREEN sX0 = *X0*N;
  if (x == x0) {
#ifdef DEBUG_INTERPOLATION
    fprintf(stderr, "sx [%c%02x][y][z] = %c%02x *\n\n", x <0?'-':' ',  x <0?-x &0xff:x &0xFF, sX0<0?'-':' ', sX0<0?-sX0&0xFF:sX0 &0xFF);
#endif
    return sX0;
  }
  SCREEN *X1 = lookupxmap(x1,y,z,&N);
  SCREEN sX1 = *X1*N;
  if (sX0 == sX1) {
#ifdef DEBUG_INTERPOLATION
    fprintf(stderr, "sx [%c%02x][y][z] = %c%02x *\n\n", x <0?'-':' ',  x <0?-x &0xff:x &0xFF, sX0<0?'-':' ', sX0<0?-sX0&0xFF:sX0 &0xFF);
#endif
    return sX0;
  }
  SCREEN sX = sX0 + (((sX1-sX0)*frac)>>4); // BEWARE INTERMEDIATE VALUES OUTSIDE OF BYTE RANGE.
#ifdef DEBUG_INTERPOLATION
  fprintf(stderr, "sx0[%c%02x][y][z] = %c%02x\n",   x0<0?'-':' ',  x0<0?-x0&0xff:x0&0xFF, sX0<0?'-':' ', sX0<0?-sX0&0xFF:sX0&0xFF);
  fprintf(stderr, "sx [%c%02x][y][z] = %c%02x *\n", x <0?'-':' ',  x <0?-x &0xff:x &0xFF, sX <0?'-':' ', sX <0?-sX &0xFF:sX &0xFF);
  fprintf(stderr, "sx1[%c%02x][y][z] = %c%02x\n\n", x1<0?'-':' ',  x1<0?-x1&0xff:x1&0xFF, sX1<0?'-':' ', sX1<0?-sX1&0xFF:sX1&0xFF);
#endif  
  return sX;
}

static inline SCREEN lookupy(XYCOORD x, XYCOORD y, ZCOORD z) {
#ifdef NEVER
  int N;
  XYCOORD y0 =  (y>>4)   <<4;
  XYCOORD y1 = ((y>>4)+1)<<4; // BEWARE END CASE WHERE +1 WRAPS IN A BYTE.
  int frac = y&15;
  SCREEN *Y0 = lookupxmap(x,y0,z,&N);
  SCREEN sY0 = *Y0*N;
  if (y == y0) {
#ifdef DEBUG_INTERPOLATION
    fprintf(stderr, "sy [x][%c%02x][z] = %c%02x *\n\n", y <0?'-':' ',  y <0?-y &0xff:y &0xFF, sY0<0?'-':' ', sY0<0?-sY0&0xFF:sY0 &0xFF);
#endif
    return sY0;
  }
  SCREEN *Y1 = lookupxmap(x,y1,z,&N);
  SCREEN sY1 = *Y1*N;
  if (sY0 == sY1) {
#ifdef DEBUG_INTERPOLATION
    fprintf(stderr, "sy [x][%c%02x][z] = %c%02x *\n\n", y <0?'-':' ',  y <0?-y &0xff:y &0xFF, sY0<0?'-':' ', sY0<0?-sY0&0xFF:sY0 &0xFF);
#endif
    return sY0;
  }
  SCREEN sY = sY0 + (((sY1-sY0)*frac)>>4); // BEWARE INTERMEDIATE VALUES OUTSIDE OF BYTE RANGE.
#ifdef DEBUG_INTERPOLATION
  fprintf(stderr, "sy0[x][%c%02x][z] = %c%02x\n",   y0<0?'-':' ',  y0<0?-y0&0xff:y0&0xFF, sY0<0?'-':' ', sY0<0?-sY0&0xFF:sY0&0xFF);
  fprintf(stderr, "sx [x][%c%02x][z] = %c%02x *\n", y <0?'-':' ',  y <0?-y &0xff:y &0xFF, sY <0?'-':' ', sY <0?-sY &0xFF:sY &0xFF);
  fprintf(stderr, "sy1[x][%c%02x][z] = %c%02x\n\n", y1<0?'-':' ',  y1<0?-y1&0xff:y1&0xFF, sY1<0?'-':' ', sY1<0?-sY1&0xFF:sY1&0xFF);
#endif  
  return sY;
#else
  // sy[x][y][z] == sx[y][x][z]  so parameters swapped
  return lookupx(y, x, z);
#endif
}

void moveto(int x, int y) {
  fprintf(stdout, "moveto(%d,%d);\n", x, y);
  //fprintf(stdout, "moveto(%3.1f,%3.1f);\n", x, y);
}

void lineto(int x, int y) {
  fprintf(stdout, "lineto(%d,%d);\n", x, y);
  //fprintf(stdout, "lineto(%3.1f,%3.1f);\n", x, y);
}

void mv(XYCOORD x, XYCOORD y, ZCOORD z) {
  SCREEN X, Y;
  perspective(x, y, z, &X, &Y);
  moveto(X, Y);
}

void dw(XYCOORD x, XYCOORD y, ZCOORD z) {
  SCREEN X, Y;
  perspective(x, y, z, &X, &Y);
  lineto(X, Y);
}

int main(int argc, char **argv) {
  //int N;
  
  SCREEN X, Y;
  int x, y, z;

  int bytes = 0;
  
  screen_dist = 24.0;

  // -128:127 coordinate range used for x,y  0:255 used for z.  0 is closest to screen.
  
  sx = ckmalloc(sizeof(char **)*9); // 0:8
#ifdef NEVER
  sy = ckmalloc(sizeof(char **)*9);
#endif
  for (x = 0; x <= 128; x+=16) {
    sx[x>>4] =  ckmalloc(sizeof(char *)*9); // 0:8
#ifdef NEVER
    sy[x>>4] =  ckmalloc(sizeof(char *)*9);
#endif
    for (y = 0; y <= 128; y+=16) {
      sx[x>>4][y>>4] =  ckmalloc(sizeof(char)*256); // 0:15
#ifdef NEVER
      sy[x>>4][y>>4] =  ckmalloc(sizeof(char)*256); // no symmetry in z
#endif
    }
  }

  for (x = -128; x <=  0; x+=16) {
    for (y = -128; y <=  0; y+=16) {
      for (z =     0; z < 256; z+=4) {
        int a,b,c,d; // , p,q,r,s;
        perspective(x,y,z, &X, &Y); // recenter on X,Y=0,0
        //*lookupxmap(x,y,z, &N) = X; *lookupymap(x,y,z, &N) = Y;
        sx[a=(x+128)>>4][b=(y+128)>>4][c=z>>2] = d=X;
#ifdef NEVER
        sy[p=(x+128)>>4][q=(y+128)>>4][r=z>>2] = s=Y;
#endif
        bytes++;
        //fprintf(stderr, "SX[%d][%d][%d] = %d  SY[%d][%d][%d] = %d\n", a,b,c,d, p,q,r,s);
      }
    }
  }

  for (z = 0; z < 64; z+=1) {
    // Map a 255-unit wide line to a ???-wide line:
    scale[z] = -lookupx(-128,0,z*4)*2-1; // just look at x axis.  y will be the same.
    bytes++;
  }
  // 8 x 8 x 8 world coordinates.

#ifdef TEST_SCALE
  for (z = 0; z < 256; z += 16) {
    fprintf(stdout, "z=%d: scale = %d\n", z, scale[z]);
  }
#endif

  // A naive table-driven perspective would take too much rom space.  We need to optimise the views
  // available so that we take advantage of the Vectrex hardware scaling in preference to taking up
  // extra table space.

#ifdef TEST_PERSP
  for (z = 0; z < 256; z += 16) {
    fprintf(stdout, "z %02x:\n", z);
    for (y = 0; y < 256; y += 16) {
      fprintf(stdout, "y %02x: ", (y-128)&255);
      for (x = 0; x < 256; x += 16) {
        SCREEN xx, yy;
        //fprintf(stdout, "[%d,%d,%d] -> [%d,%d]\n",x-128,y-128,z, sx[x][y][z], sy[x][y][z]);
        xx = lookupx(x,y,z);
        yy = lookupy(x,y,z);
        fprintf(stdout, "x:%02x %02x %02x ", x, xx&0xFF, yy&0xFF);
      }
      fprintf(stdout, "\n");
    }
    fprintf(stdout, "\n\n\n");
  }
#endif

#ifdef DUMP_TABLES
  fprintf(stdout, "#include <stdio.h>\n");
  fprintf(stdout, "typedef unsigned char u_int8_t;\n");
  fprintf(stdout, "typedef   signed char   int8_t;\n");
  fprintf(stdout, "const u_int8_t scale[64] = {\n");
  for (N = 0; N < 64; N += 16) {
    fprintf(stdout, "  %d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d,\n",
            scale[N+0], scale[N+1], scale[N+2], scale[N+3], scale[N+4], scale[N+5], scale[N+6], scale[N+7], 
            scale[N+8], scale[N+9], scale[N+10], scale[N+11], scale[N+12], scale[N+13], scale[N+14], scale[N+15]);
  }
  fprintf(stdout, "};\n");

  fprintf(stdout, "const int8_t sx[9][9][64] = {\n");
  for (x = -128; x <= 0; x += 16) {
    fprintf(stdout, "  {\n");
    for (y = -128; y <= 0; y += 16) { // To do: check whether modifying for y makes enough difference to a projected x value.
      fprintf(stdout, "    { /* [x=%d][y=%d][z=0:63] */\n", x, y);
      for (z = 0; z < 64; z += 1) {
        if ((z&15) == 0) fprintf(stdout, "       ");
        fprintf(stdout, "%d, ", sx[(x+128)>>4][(y+128)>>4][z]);
        if ((z&15) == 15) fprintf(stdout, "\n");
      }
      fprintf(stdout, "    },\n");
    }
    fprintf(stdout, "  },\n");
  }
  fprintf(stdout, "};\n");

  // sy[x][y][z] == sx[y][x][z]
#ifdef NEVER
  fprintf(stdout, "const int8_t sy[9][9][64] = {\n");
  for (x = -128; x <= 0; x += 16) {
    fprintf(stdout, "  {\n");
    for (y = -128; y <= 0; y += 16) {
      fprintf(stdout, "    { /* [x=%d][y=%d][z=0:63] */\n", x, y);
      for (z = 0; z < 64; z += 1) {
        if ((z&15) == 0) fprintf(stdout, "       ");
        fprintf(stdout, "%d, ", sy[(x+128)>>4][(y+128)>>4][z]);
        if ((z&15) == 15) fprintf(stdout, "\n");
      }
      fprintf(stdout, "    },\n");
    }
    fprintf(stdout, "  },\n");
  }
  fprintf(stdout, "};\n");
#endif
  
  fprintf(stdout, "// rom space used: %d bytes\n", bytes);
#endif // DUMP_TABLES
  
#ifdef TEST_PROGRAM
  int h = 91;

  // So at this point we have the perspective projection working well, but we still need
  // to do rotational transformations on the objects themselves...  This *might* be time
  // to look at using polar coordinates for the models?  Or can we use lookup tables for
  // the object rotations as well?  Shouldn't really be that hard, given that the object
  // is defined relative to the center point around which it rotates.
  mv(h, -h, -h); dw(h, h, -h);
  dw( -h, h, -h);
  dw( -h, h, h);
  dw( -h, -h, h);
  dw(h, -h, h);
  dw(h, -h, -h);
  mv(h, h, -h); dw(h, h, h);
  dw( -h, h, h);
  mv(h, h, h); dw(h, -h, h);
  mv(h, -h, -h); dw(-h, -h, -h);
  dw( -h, h, -h);
  mv(-h, -h, -h); dw(-h, -h, h);
#endif

  exit(EXIT_SUCCESS);
  return EXIT_FAILURE;
}