git.mutantstargoat.com Git - gbajam22/blob - src/polyfill.c

   1 /*
   2 gbajam22 entry for the Gameboy Advance
   3 Copyright (C) 2022  John Tsiombikas <nuclear@mutantstargoat.com>
   4
   5 This program is free software: you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation, either version 3 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17 */
  18 #include <string.h>
  19 #include "polyfill.h"
  20 #include "debug.h"
  21
  22 static unsigned char *fb;
  23 static int fbwidth, fbheight;
  24 static short scantab[2][160] __attribute__((section(".iwram")));
  25
  26 void polyfill_framebuffer(unsigned char *ptr, int w, int h)
  27 {
  28         fb = ptr;
  29         fbwidth = w;
  30         fbheight = h;
  31 }
  32
  33 #define VNEXT(p)        (((p) == vlast) ? varr : (p) + 1)
  34 #define VPREV(p)        ((p) == varr ? vlast : (p) - 1)
  35 #define VSUCC(p, side)  ((side) == 0 ? VNEXT(p) : VPREV(p))
  36
  37 void polyfill_flat(struct pvertex *varr, int vnum, unsigned char col)
  38 {
  39         int i, line, top, bot;
  40         struct pvertex *vlast, *v, *vn;
  41         int32_t x, y0, y1, dx, dy, slope, fx, fy;
  42         short *tab, start, len;
  43         unsigned char *fbptr;
  44         uint16_t *pptr, pcol = ((uint16_t)col << 8) | (uint16_t)col;
  45
  46         vlast = varr + vnum - 1;
  47         top = fbheight;
  48         bot = 0;
  49
  50         for(i=0; i<vnum; i++) {
  51                 v = varr + i;
  52                 vn = VNEXT(v);
  53
  54                 if(vn->y == v->y) continue;
  55
  56                 if(vn->y > v->y) {
  57                         tab = scantab[0];
  58                 } else {
  59                         tab = scantab[1];
  60                         v = vn;
  61                         vn = varr + i;
  62                 }
  63
  64                 dx = vn->x - v->x;
  65                 dy = vn->y - v->y;
  66                 slope = (dx << 8) / dy;
  67
  68                 y0 = (v->y + 0x100) & 0xffffff00;       /* start from the next scanline */
  69                 fy = y0 - v->y;                                         /* fractional part before the next scanline */
  70                 fx = (fy * slope) >> 8;                         /* X adjust for the step to the next scanline */
  71                 x = v->x + fx;                                          /* adjust X */
  72                 y1 = vn->y & 0xffffff00;                        /* last scanline of the edge <= vn->y */
  73
  74                 line = y0 >> 8;
  75                 if(line < top) top = line;
  76                 if((y1 >> 8) > bot) bot = y1 >> 8;
  77
  78                 if(line > 0) tab += line;
  79
  80                 while(line <= (y1 >> 8) && line < fbheight) {
  81                         if(line >= 0) {
  82                                 int val = x < 0 ? 0 : x >> 8;
  83                                 *tab++ = val < fbwidth ? val : fbwidth - 1;
  84                         }
  85                         x += slope;
  86                         line++;
  87                 }
  88         }
  89
  90         if(top < 0) top = 0;
  91         if(bot >= fbheight) bot = fbheight - 1;
  92
  93         fbptr = fb + top * fbwidth;
  94         for(i=top; i<=bot; i++) {
  95                 start = scantab[0][i];
  96                 len = scantab[1][i] - start;
  97
  98                 if(len > 0) {
  99                         if(start & 1) {
 100                                 pptr = (uint16_t*)(fbptr + (start & 0xfffe));
 101                                 *pptr = (*pptr & 0xff) | ((uint16_t)col << 8);
 102                                 len--;
 103                                 start++;
 104                         }
 105                         pptr = (uint16_t*)(fbptr + start);
 106                         while(len > 1) {
 107                                 *pptr++ = pcol;
 108                                 len -= 2;
 109                         }
 110                         if(len) {
 111                                 *pptr = (*pptr & 0xff00) | col;
 112                         }
 113                 }
 114                 fbptr += fbwidth;
 115         }
 116 }
 117
 118
 119 /* ----- line drawing and clipping ------ */
 120 enum {
 121         IN              = 0,
 122         LEFT    = 1,
 123         RIGHT   = 2,
 124         TOP             = 4,
 125         BOTTOM  = 8
 126 };
 127
 128 static int outcode(int x, int y, int xmin, int ymin, int xmax, int ymax)
 129 {
 130         int code = 0;
 131
 132         if(x < xmin) {
 133                 code |= LEFT;
 134         } else if(x > xmax) {
 135                 code |= RIGHT;
 136         }
 137         if(y < ymin) {
 138                 code |= TOP;
 139         } else if(y > ymax) {
 140                 code |= BOTTOM;
 141         }
 142         return code;
 143 }
 144
 145 #define FIXMUL(a, b)    (((a) * (b)) >> 8)
 146 #define FIXDIV(a, b)    (((a) << 8) / (b))
 147
 148 #define LERP(a, b, t)   ((a) + FIXMUL((b) - (a), (t)))
 149
 150 int clip_line(int *x0, int *y0, int *x1, int *y1, int xmin, int ymin, int xmax, int ymax)
 151 {
 152         int oc_out;
 153
 154         int oc0 = outcode(*x0, *y0, xmin, ymin, xmax, ymax);
 155         int oc1 = outcode(*x1, *y1, xmin, ymin, xmax, ymax);
 156
 157         long fx0, fy0, fx1, fy1, fxmin, fymin, fxmax, fymax;
 158
 159         if(!(oc0 | oc1)) return 1;      /* both points are inside */
 160
 161         fx0 = *x0 << 8;
 162         fy0 = *y0 << 8;
 163         fx1 = *x1 << 8;
 164         fy1 = *y1 << 8;
 165         fxmin = xmin << 8;
 166         fymin = ymin << 8;
 167         fxmax = xmax << 8;
 168         fymax = ymax << 8;
 169
 170         for(;;) {
 171                 long x, y, t;
 172
 173                 if(oc0 & oc1) return 0;         /* both have points with the same outbit, not visible */
 174                 if(!(oc0 | oc1)) break;         /* both points are inside */
 175
 176                 oc_out = oc0 ? oc0 : oc1;
 177
 178                 if(oc_out & TOP) {
 179                         t = FIXDIV(fymin - fy0, fy1 - fy0);
 180                         x = LERP(fx0, fx1, t);
 181                         y = fymin;
 182                 } else if(oc_out & BOTTOM) {
 183                         t = FIXDIV(fymax - fy0, fy1 - fy0);
 184                         x = LERP(fx0, fx1, t);
 185                         y = fymax;
 186                 } else if(oc_out & LEFT) {
 187                         t = FIXDIV(fxmin - fx0, fx1 - fx0);
 188                         x = fxmin;
 189                         y = LERP(fy0, fy1, t);
 190                 } else {/*if(oc_out & RIGHT) {*/
 191                         t = FIXDIV(fxmax - fx0, fx1 - fx0);
 192                         x = fxmax;
 193                         y = LERP(fy0, fy1, t);
 194                 }
 195
 196                 if(oc_out == oc0) {
 197                         fx0 = x;
 198                         fy0 = y;
 199                         oc0 = outcode(fx0 >> 8, fy0 >> 8, xmin, ymin, xmax, ymax);
 200                 } else {
 201                         fx1 = x;
 202                         fy1 = y;
 203                         oc1 = outcode(fx1 >> 8, fy1 >> 8, xmin, ymin, xmax, ymax);
 204                 }
 205         }
 206
 207         *x0 = fx0 >> 8;
 208         *y0 = fy0 >> 8;
 209         *x1 = fx1 >> 8;
 210         *y1 = fy1 >> 8;
 211         return 1;
 212 }
 213
 214 #ifdef ALT_LCLIP
 215 #define PUTPIXEL(ptr) \
 216         do { \
 217                 if(x0 >= 0 && x0 < fbwidth && y0 >= 0 && y0 < fbheight) { \
 218                         uint16_t *pptr = (uint16_t*)((uint32_t)ptr & 0xfffffffe); \
 219                         if((uint32_t)ptr & 1) { \
 220                                 *pptr = (*pptr & 0xff) | (color << 8); \
 221                         } else { \
 222                                 *pptr = (*pptr & 0xff00) | color; \
 223                         } \
 224                 } \
 225         } while(0)
 226 #else   /* !ALT_LCLIP */
 227 #define PUTPIXEL(ptr) \
 228         do { \
 229                 uint16_t *pptr = (uint16_t*)((uint32_t)ptr & 0xfffffffe); \
 230                 if((uint32_t)ptr & 1) { \
 231                         *pptr = (*pptr & 0xff) | (color << 8); \
 232                 } else { \
 233                         *pptr = (*pptr & 0xff00) | color; \
 234                 } \
 235         } while(0)
 236 #endif
 237
 238 void draw_line(int x0, int y0, int x1, int y1, unsigned short color)
 239 {
 240         int i, dx, dy, x_inc, y_inc, error;
 241 #ifdef ALT_LCLIP
 242         int y0inc;
 243 #endif
 244         unsigned char *fbptr = fb;
 245
 246         fbptr += y0 * fbwidth + x0;
 247
 248         dx = x1 - x0;
 249         dy = y1 - y0;
 250
 251         if(dx >= 0) {
 252                 x_inc = 1;
 253         } else {
 254                 x_inc = -1;
 255                 dx = -dx;
 256         }
 257         if(dy >= 0) {
 258                 y_inc = fbwidth;
 259 #ifdef ALT_LCLIP
 260                 y0inc = 1;
 261 #endif
 262         } else {
 263                 y_inc = -fbwidth;
 264 #ifdef ALT_LCLIP
 265                 y0inc = -1;
 266 #endif
 267                 dy = -dy;
 268         }
 269
 270         if(dx > dy) {
 271                 error = dy * 2 - dx;
 272                 for(i=0; i<=dx; i++) {
 273                         PUTPIXEL(fbptr);
 274                         if(error >= 0) {
 275                                 error -= dx * 2;
 276                                 fbptr += y_inc;
 277 #ifdef ALT_LCLIP
 278                                 y0 += y0inc;
 279 #endif
 280                         }
 281                         error += dy * 2;
 282                         fbptr += x_inc;
 283 #ifdef ALT_LCLIP
 284                         x0 += x_inc;
 285 #endif
 286                 }
 287         } else {
 288                 error = dx * 2 - dy;
 289                 for(i=0; i<=dy; i++) {
 290                         PUTPIXEL(fbptr);
 291                         if(error >= 0) {
 292                                 error -= dy * 2;
 293                                 fbptr += x_inc;
 294 #ifdef ALT_LCLIP
 295                                 x0 += x_inc;
 296 #endif
 297                         }
 298                         error += dx * 2;
 299                         fbptr += y_inc;
 300 #ifdef ALT_LCLIP
 301                         y0 += y0inc;
 302 #endif
 303                 }
 304         }
 305 }
 306