src/polymod.c

   1 /*
   2  * This program is free software: you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License as published by
   4  * the Free Software Foundation, either version 3 of the License, or
   5  * (at your option) any later version.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  14  */
  15 #include "polymod.h"
  16
  17 #include <stdint.h>
  18
  19 #ifdef TEST
  20 # include <stdio.h>
  21 # include <stdlib.h>
  22 # include <string.h>
  23 #else
  24 # include "video.h"
  25 # include "gameglobals.h"
  26 #endif
  27
  28 #include "sincostab.c"
  29
  30
  31 #ifdef TEST
  32 static void fatal (const char *msg) {
  33   printf("FATAL: %s\n", msg);
  34   abort();
  35 }
  36 #endif
  37
  38
  39 typedef struct PolyPoint {
  40   int next; // -1: none
  41   int x;
  42 } PolyPoint;
  43
  44
  45 static int polyPointPoolSize = 0;
  46 static int polyPointPoolPos = 0;
  47 static PolyPoint *polyPointPool = NULL;
  48 static int polyScans[200]; // index of the first point of each scan; -1: none
  49 static int firstX, firstY;
  50 static int lastX, lastY;
  51 static int firstPoint;
  52 static int lastDY;
  53 static int minY, maxY;
  54 static int pofsx, pofsy;
  55 static int pscale;
  56 static int pangle;
  57
  58
  59 void polymodInitialize (void) {
  60   for (int f = 0; f < 200; ++f) polyScans[f] = -1;
  61   polyPointPool = NULL;
  62   polyPointPoolSize = 0;
  63   polyPointPoolPos = 0;
  64   firstPoint = 1;
  65 }
  66
  67
  68 void polymodDeinitialize (void) {
  69   if (polyPointPool != NULL) free(polyPointPool);
  70   polyPointPool = NULL;
  71   polyPointPoolSize = 0;
  72   polyPointPoolPos = 0;
  73   firstPoint = 1;
  74 }
  75
  76
  77 static inline int allocPolyPoint (int x, int next) {
  78   if (polyPointPoolPos+1 > polyPointPoolSize) {
  79     int newsz = polyPointPoolSize+8192;
  80     PolyPoint *nn = realloc(polyPointPool, sizeof(PolyPoint)*newsz);
  81     //
  82     if (nn == NULL) fatal("out of memory in polymod");
  83     polyPointPool = nn;
  84     polyPointPoolSize = newsz;
  85   }
  86   polyPointPool[polyPointPoolPos].x = x;
  87   polyPointPool[polyPointPoolPos].next = next;
  88   return polyPointPoolPos++;
  89 }
  90
  91
  92 static inline void insertPoint (int x, int y) {
  93   if (y >= 0 && y < 200) {
  94     int n;
  95     //
  96     if ((n = polyScans[y]) != -1) {
  97       int p;
  98       //
  99       for (p = -1; n != -1 && x > polyPointPool[n].x; p = n, n = polyPointPool[n].next) ;
 100       if (p == -1) {
 101         // this is new first point
 102         polyScans[y] = allocPolyPoint(x, n);
 103       } else {
 104         // insert new point after p; n is the next point
 105         polyPointPool[p].next = allocPolyPoint(x, n);
 106       }
 107     } else {
 108       // first
 109       polyScans[y] = allocPolyPoint(x, -1);
 110     }
 111   }
 112 }
 113
 114
 115 static inline void rotate (int *x, int *y) {
 116   int64_t tx = (int64_t)(*x)*pscale/POLYFIX_BASE;
 117   int64_t ty = (int64_t)(*y)*pscale/POLYFIX_BASE;
 118   *x = (tx*costab[pangle]-ty*sintab[pangle])/POLYFIX_BASE+pofsx;
 119   *y = (tx*sintab[pangle]+ty*costab[pangle])/POLYFIX_BASE+pofsy;
 120 }
 121
 122
 123 static void lineDDA (int x0, int y0, int x1, int y1) {
 124   int dy;
 125   double x, dx;
 126   //
 127   if (y0 == y1) {
 128     // horizontal line
 129     if (y0 >= 0 && y0 <= 199 && lastDY != 0) insertPoint(x0, y0);
 130     lastDY = 0;
 131     return;
 132   }
 133   //
 134   rotate(&x0, &y0);
 135   rotate(&x1, &y1);
 136   //
 137   //fprintf(stderr, "*(%d,%d)-(%d,%d)\n", x0, y0, x1, y1);
 138   if ((y0 < 0 && y1 < 0) || (y0 > 199 && y1 > 199)) return; // out-of-screen lines aren't interesting
 139   //
 140   if (x0 == x1) {
 141     // straight vertical line
 142     if (y0 < y1) {
 143       if (y0 < 0) y0 = 0;
 144       if (y1 > 199) y1 = 199;
 145       if (y0 < minY) minY = y0;
 146       if (y1 > maxY) maxY = y1;
 147       if (lastDY == -11) insertPoint(x0, y0);
 148       lastDY = 1;
 149       for (; y0 < y1; ++y0) insertPoint(x0, y0);
 150     } else {
 151       if (y1 < 0) y1 = 0;
 152       if (y0 > 199) y0 = 199;
 153       if (y1 < minY) minY = y1;
 154       if (y0 > maxY) maxY = y0;
 155       if (lastDY == 1) insertPoint(x0, y0);
 156       lastDY = -1;
 157       for (; y0 > y1; --y0) insertPoint(x0, y0);
 158     }
 159   } else {
 160     // draw sloped
 161     x = x0;
 162     if (y0 < y1) {
 163       dx = (double)(x1-x0)/(double)(y1-y0);
 164       dy = 1;
 165       if (y0 < 0) { x += dx*(0-y0); y0 = 0; }
 166       if (y1 > 199) y1 = 199;
 167       if (y0 < minY) minY = y0;
 168       if (y1 > maxY) maxY = y1;
 169     } else {
 170       dx = (double)(x1-x0)/(double)(y0-y1);
 171       dy = -1;
 172       if (y1 < 0) y1 = 0;
 173       if (y0 > 199) { x += dy*(y0-199); y0 = 199; }
 174       if (y1 < minY) minY = y1;
 175       if (y0 > maxY) maxY = y0;
 176     }
 177     if (lastDY == -dy) insertPoint(x0, y0);
 178     lastDY = dy;
 179     for (; y0 != y1; y0 += dy) { insertPoint(x+0.5, y0); x += dx; }
 180   }
 181 }
 182
 183
 184 void polymodStart (int ofsx, int ofsy, int scale, int angle) {
 185   for (int f = 0; f < 200; ++f) polyScans[f] = -1;
 186   polyPointPoolPos = 0;
 187   lastDY = 0;
 188   firstPoint = 1;
 189   minY = 200;
 190   maxY = -1;
 191   pofsx = ofsx;
 192   pofsy = ofsy;
 193   pscale = scale;
 194   while (angle < 0) angle += 360; // hehe
 195   pangle = angle%360;
 196 }
 197
 198
 199 void polymodAddPoint (int x, int y) {
 200   if (!firstPoint) {
 201     lineDDA(lastX, lastY, x, y);
 202   } else {
 203     firstPoint = 0;
 204     firstX = x;
 205     firstY = y;
 206   }
 207   lastX = x;
 208   lastY = y;
 209 }
 210
 211
 212 void polymodEnd (void) {
 213   if (!firstPoint) {
 214     lineDDA(lastX, lastY, firstX, firstY);
 215     insertPoint(firstX, firstY);
 216   }
 217 }
 218
 219
 220 void polymodFill (SDL_Surface *frame, Uint8 color, Uint8 alpha) {
 221   for (int y = minY; y <= maxY; ++y) {
 222     int p = polyScans[y];
 223     //
 224     if (p >= 0) {
 225 #ifdef TEST
 226       printf("y: %d\n", y);
 227       while (p >= 0) {
 228         printf(" x: %d\n", polyPointPool[p].x);
 229         p = polyPointPool[p].next;
 230       }
 231 #else
 232       for (;;) {
 233         int n = polyPointPool[p].next;
 234         //
 235         if (n < 0) break;
 236         //fprintf(stderr, "y: %d; x0: %d; x1: %d\n", y, polyPointPool[p].x, polyPointPool[n].x);
 237         //ex = polyPointPool[n].x;
 238         //for (int x = polyPointPool[p].x; x <= ex; ++x) putPixelA2x(frame, x, y, color, alpha);
 239         hline2x(frame, polyPointPool[p].x, y, polyPointPool[n].x-polyPointPool[p].x+1, color);
 240         p = polyPointPool[n].next;
 241         if (p < 0) break;
 242       }
 243 #endif
 244     }
 245   }
 246 }
 247
 248
 249 #ifdef TEST
 250 int main () {
 251   polymodStart();
 252   //
 253   /*
 254   polymodAddPoint(50, 50);
 255   polymodAddPoint(90, 50);
 256   polymodAddPoint(90, 90);
 257   polymodAddPoint(50, 90);
 258   */
 259   /*
 260   polymodAddPoint(10, 200-10);
 261   polymodAddPoint(320-10, 200-10);
 262   polymodAddPoint(10, 10);
 263   polymodAddPoint(320-10, 10);
 264   */
 265   /*
 266   polymodAddPoint(202, 100);
 267   polymodAddPoint(200, 110);
 268   polymodAddPoint(196, 120);
 269   polymodAddPoint(189, 129);
 270   polymodAddPoint(181, 136);
 271   polymodAddPoint(170, 140);
 272   polymodAddPoint(160, 142);
 273   polymodAddPoint(150, 140);
 274   polymodAddPoint(140, 136);
 275   polymodAddPoint(131, 129);
 276   polymodAddPoint(124, 120);
 277   polymodAddPoint(120, 110);
 278   polymodAddPoint(118, 100);
 279   polymodAddPoint(120, 90);
 280   polymodAddPoint(124, 79);
 281   polymodAddPoint(131, 71);
 282   polymodAddPoint(139, 64);
 283   polymodAddPoint(150, 60);
 284   polymodAddPoint(160, 58);
 285   polymodAddPoint(170, 60);
 286   polymodAddPoint(181, 64);
 287   polymodAddPoint(189, 71);
 288   polymodAddPoint(196, 79);
 289   polymodAddPoint(200, 90);
 290   */
 291   polymodAddPoint(196, 100);
 292   polymodAddPoint(206, 112);
 293   polymodAddPoint(191, 117);
 294   polymodAddPoint(193, 133);
 295   polymodAddPoint(178, 131);
 296   polymodAddPoint(172, 146);
 297   polymodAddPoint(160, 136);
 298   polymodAddPoint(148, 146);
 299   polymodAddPoint(143, 131);
 300   polymodAddPoint(127, 133);
 301   polymodAddPoint(129, 117);
 302   polymodAddPoint(114, 112);
 303   polymodAddPoint(124, 100);
 304   polymodAddPoint(114, 88);
 305   polymodAddPoint(129, 82);
 306   polymodAddPoint(127, 67);
 307   polymodAddPoint(142, 69);
 308   polymodAddPoint(148, 54);
 309   polymodAddPoint(160, 64);
 310   polymodAddPoint(172, 54);
 311   polymodAddPoint(178, 69);
 312   polymodAddPoint(193, 67);
 313   polymodAddPoint(191, 82);
 314   polymodAddPoint(206, 88);
 315   //
 316   polymodEnd();
 317   polymodFill(NULL, 3, 50);
 318   return 0;
 319 }
 320 #endif