polygon.c

   1 #include "imager.h"
   2 #include "draw.h"
   3 #include "log.h"
   4 #include "imrender.h"
   5
   6 #define IMTRUNC(x) ((int)((x)*16))
   7
   8 #define coarse(x) ((x)/16)
   9 #define fine(x)   ((x)%16)
  10
  11 /*#define DEBUG_POLY*/
  12 #ifdef DEBUG_POLY
  13 #define POLY_DEB(x) x
  14 #else
  15 #define POLY_DEB(x)
  16 #endif
  17
  18
  19 typedef int pcord;
  20
  21 typedef struct {
  22   int n;
  23   pcord x,y;
  24 } p_point;
  25
  26 typedef struct {
  27   int n;
  28   pcord x1,y1;
  29   pcord x2,y2;
  30   pcord miny,maxy;
  31   pcord minx,maxx;
  32   int updown; /* -1 means down, 0 vertical, 1 up */
  33 } p_line;
  34
  35 typedef struct {
  36   int n;
  37   double x;
  38 } p_slice;
  39
  40 typedef struct {
  41   int start;
  42   int stop;
  43 } ss_pair;
  44
  45 typedef struct {
  46   int *line;            /* temporary buffer for scanline */
  47   int linelen;          /* length of scanline */
  48 } ss_scanline;
  49
  50 static
  51 int
  52 p_compy(const p_point *p1, const p_point *p2) {
  53   if (p1->y > p2->y) return 1;
  54   if (p1->y < p2->y) return -1;
  55   return 0;
  56 }
  57
  58 static
  59 int
  60 p_compx(const p_slice *p1, const p_slice *p2) {
  61   if (p1->x > p2->x) return 1;
  62   if (p1->x < p2->x) return -1;
  63   return 0;
  64 }
  65
  66 /* Change this to int? and round right goddamn it! */
  67
  68 static
  69 double
  70 p_eval_aty(p_line *l, pcord y) {
  71   int t;
  72   t=l->y2-l->y1;
  73   if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
  74   return (l->x1+l->x2)/2.0;
  75 }
  76
  77 static
  78 double
  79 p_eval_atx(p_line *l, pcord x) {
  80   int t;
  81   t = l->x2-l->x1;
  82   if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
  83   return (l->y1+l->y2)/2.0;
  84 }
  85
  86 static
  87 p_line *
  88 line_set_new(const double *x, const double *y, int l) {
  89   int i;
  90   p_line *lset = mymalloc(sizeof(p_line) * l);
  91
  92   for(i=0; i<l; i++) {
  93     lset[i].n=i;
  94     lset[i].x1 = IMTRUNC(x[i]);
  95     lset[i].y1 = IMTRUNC(y[i]);
  96     lset[i].x2 = IMTRUNC(x[(i+1)%l]);
  97     lset[i].y2 = IMTRUNC(y[(i+1)%l]);
  98     lset[i].miny=i_min(lset[i].y1,lset[i].y2);
  99     lset[i].maxy=i_max(lset[i].y1,lset[i].y2);
 100     lset[i].minx=i_min(lset[i].x1,lset[i].x2);
 101     lset[i].maxx=i_max(lset[i].x1,lset[i].x2);
 102   }
 103   return lset;
 104 }
 105
 106 static
 107 p_point *
 108 point_set_new(const double *x, const double *y, int l) {
 109   int i;
 110   p_point *pset = mymalloc(sizeof(p_point) * l);
 111
 112   for(i=0; i<l; i++) {
 113     pset[i].n=i;
 114     pset[i].x=IMTRUNC(x[i]);
 115     pset[i].y=IMTRUNC(y[i]);
 116   }
 117   return pset;
 118 }
 119
 120 static
 121 void
 122 ss_scanline_reset(ss_scanline *ss) {
 123   memset(ss->line, 0, sizeof(int) * ss->linelen);
 124 }
 125
 126 static
 127 void
 128 ss_scanline_init(ss_scanline *ss, int linelen, int linepairs) {
 129   ss->line    = mymalloc( sizeof(int) * linelen );
 130   ss->linelen = linelen;
 131   ss_scanline_reset(ss);
 132 }
 133
 134 static
 135 void
 136 ss_scanline_exorcise(ss_scanline *ss) {
 137   myfree(ss->line);
 138 }
 139
 140
 141
 142
 143 /* returns the number of matches */
 144
 145 static
 146 int
 147 lines_in_interval(p_line *lset, int l, p_slice *tllist, pcord minc, pcord maxc) {
 148   int k;
 149   int count = 0;
 150   for(k=0; k<l; k++) {
 151     if (lset[k].maxy > minc && lset[k].miny < maxc) {
 152       if (lset[k].miny == lset[k].maxy) {
 153         POLY_DEB( printf(" HORIZONTAL - skipped\n") );
 154       } else {
 155         tllist[count].x=p_eval_aty(&lset[k],(minc+maxc)/2.0 );
 156         tllist[count].n=k;
 157         count++;
 158       }
 159     }
 160   }
 161   return count;
 162 }
 163
 164 /* marks the up variable for all lines in a slice */
 165
 166 static
 167 void
 168 mark_updown_slices(p_line *lset, p_slice *tllist, int count) {
 169   p_line *l, *r;
 170   int k;
 171   for(k=0; k<count; k+=2) {
 172     l = lset + tllist[k].n;
 173
 174     if (l->y1 == l->y2) {
 175       mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
 176       exit(3);
 177     }
 178
 179     l->updown = (l->x1 == l->x2) ?
 180       0 :
 181       (l->x1 > l->x2)
 182       ?
 183       (l->y1 > l->y2) ? -1 : 1
 184       :
 185       (l->y1 > l->y2) ? 1 : -1;
 186
 187     POLY_DEB( printf("marking left line %d as %s(%d)\n", l->n,
 188                      l->updown ?  l->updown == 1 ? "up" : "down" : "vert", l->updown, l->updown)
 189               );
 190
 191     if (k+1 >= count) {
 192       mm_log((1, "Invalid polygon spec, odd number of line crossings.\n"));
 193       return;
 194     }
 195
 196     r = lset + tllist[k+1].n;
 197     if (r->y1 == r->y2) {
 198       mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
 199       exit(3);
 200     }
 201
 202     r->updown = (r->x1 == r->x2) ?
 203       0 :
 204       (r->x1 > r->x2)
 205       ?
 206       (r->y1 > r->y2) ? -1 : 1
 207       :
 208       (r->y1 > r->y2) ? 1 : -1;
 209
 210     POLY_DEB( printf("marking right line %d as %s(%d)\n", r->n,
 211                      r->updown ?  r->updown == 1 ? "up" : "down" : "vert", r->updown, r->updown)
 212               );
 213   }
 214 }
 215
 216
 217
 218 static
 219 unsigned char
 220 saturate(int in) {
 221   if (in>255) { return 255; }
 222   else if (in>0) return in;
 223   return 0;
 224 }
 225
 226 typedef void (*scanline_flusher)(i_img *im, ss_scanline *ss, int y, void *ctx);
 227
 228 /* This function must be modified later to do proper blending */
 229
 230 static void
 231 scanline_flush(i_img *im, ss_scanline *ss, int y, void *ctx) {
 232   int x, ch, tv;
 233   i_color t;
 234   i_color *val = (i_color *)ctx;
 235   POLY_DEB( printf("Flushing line %d\n", y) );
 236   for(x=0; x<im->xsize; x++) {
 237     tv = saturate(ss->line[x]);
 238     i_gpix(im, x, y, &t);
 239     for(ch=0; ch<im->channels; ch++)
 240       t.channel[ch] = tv/255.0 * val->channel[ch] + (1.0-tv/255.0) * t.channel[ch];
 241     i_ppix(im, x, y, &t);
 242   }
 243 }
 244
 245
 246
 247 static
 248 int
 249 trap_square(pcord xlen, pcord ylen, double xl, double yl) {
 250   POLY_DEB( printf("trap_square: %d %d %.2f %.2f\n", xlen, ylen, xl, yl) );
 251   return xlen*ylen-(xl*yl)/2.0;
 252 }
 253
 254
 255 /*
 256    pixel_coverage calculates the 'left side' pixel coverage of a pixel that is
 257    within the min/max ranges.  The shape always corresponds to a square with some
 258    sort of a triangle cut from it (which can also yield a triangle).
 259 */
 260
 261
 262 static
 263 int
 264 pixel_coverage(p_line *line, pcord minx, pcord maxx, pcord  miny, pcord maxy) {
 265   double lycross, rycross;
 266   int l, r;
 267
 268   POLY_DEB
 269     (
 270      printf("    pixel_coverage(..., minx %g, maxx%g, miny %g, maxy %g)\n",
 271             minx/16.0, maxx/16.0, miny/16.0, maxy/16.0)
 272      );
 273
 274   if (!line->updown) {
 275     l = r = 0;
 276   } else {
 277     lycross = p_eval_atx(line, minx);
 278     rycross = p_eval_atx(line, maxx);
 279     l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */
 280     r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */
 281   }
 282   POLY_DEB(
 283            printf("    %4s(%+d): ", line->updown ?  line->updown == 1 ? "up" : "down" : "vert", line->updown);
 284            printf(" (%2d,%2d) [%3d-%3d, %3d-%3d] lycross=%.2f rycross=%.2f", coarse(minx), coarse(miny), minx, maxx, miny, maxy, lycross, rycross);
 285            printf(" l=%d r=%d\n", l, r)
 286            );
 287
 288   if (l && r)
 289     return line->updown == 1 ?
 290       (double)(maxx-minx) * (2.0*maxy-lycross-rycross)/2.0  /* up case */
 291       :
 292       (double)(maxx-minx) * (lycross+rycross-2*miny)/2.0;  /* down case */
 293
 294   if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0;
 295
 296   if (l && !r)
 297     return line->updown == 1 ?
 298       trap_square(maxx-minx, maxy-miny, p_eval_aty(line, miny)-minx, p_eval_atx(line, minx)-miny) :
 299       trap_square(maxx-minx, maxy-miny, p_eval_aty(line, maxy)-minx, maxy-p_eval_atx(line, minx));
 300
 301
 302   if (!l && r) {
 303     int r = line->updown == 1 ?
 304       (maxx-p_eval_aty(line, maxy))*(maxy-p_eval_atx(line, maxx))/2.0 :
 305       (maxx-p_eval_aty(line, miny))*(p_eval_atx(line, maxx)-miny)/2.0;
 306     return r;
 307   }
 308
 309   return 0; /* silence compiler warning */
 310 }
 311
 312
 313
 314
 315
 316 /*
 317    handle the scanline slice in three steps
 318
 319    1.  Where only the left edge is inside a pixel
 320    2a. Where both left and right edge are inside a pixel
 321    2b. Where neither left or right edge are inside a pixel
 322    3.  Where only the right edge is inside a pixel
 323 */
 324
 325 static
 326 void
 327 render_slice_scanline(ss_scanline *ss, int y, p_line *l, p_line *r, pcord miny, pcord maxy) {
 328
 329   pcord lminx, lmaxx;   /* left line min/max within y bounds in fine coords */
 330   pcord rminx, rmaxx;   /* right line min/max within y bounds in fine coords */
 331   int cpix;             /* x-coordinate of current pixel */
 332   int thin;             /* boolean for thin/thick segment */
 333   int startpix;         /* temporary variable for "start of this interval" */
 334   int stoppix;          /* temporary variable for "end of this interval" */
 335
 336   /* Find the y bounds of scanline_slice */
 337
 338   POLY_DEB
 339     (
 340      printf("render_slice_scanline(..., y=%d)\n");
 341      printf("  left  n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
 342             l->n, l->x1/16.0, l->y1/16.0, l->x2/16.0, l->y2/16.0,
 343             l->minx/16.0, l->miny/16.0, l->maxx/16.0, l->maxy/16.0,
 344             l->updown);
 345      printf("  right n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
 346             r->n, r->x1/16.0, r->y1/16.0, r->x2/16.0, r->y2/16.0,
 347             r->minx/16.0, r->miny/16.0, r->maxx/16.0, r->maxy/16.0,
 348             r->updown);
 349      );
 350
 351   lminx = i_min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
 352   lmaxx = i_max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
 353
 354   rminx = i_min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
 355   rmaxx = i_max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
 356
 357   thin = coarse(lmaxx) >= coarse(rminx);
 358
 359   startpix = i_max( coarse(lminx), 0 );
 360   stoppix  = i_min( coarse(rmaxx-1), ss->linelen-1 );
 361
 362   POLY_DEB(  printf("  miny=%g maxy=%g\n", miny/16.0, maxy/16.0)  );
 363
 364   for(cpix=startpix; cpix<=stoppix; cpix++) {
 365     int lt = coarse(lmaxx-1) >= cpix;
 366     int rt = coarse(rminx) <= cpix;
 367
 368     int A, B, C;
 369
 370     POLY_DEB( printf("  (%d,%d) lt=%d rt=%d\n", cpix, y, lt, rt) );
 371
 372     A = lt ? pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy) : 0;
 373     B = lt ? 0 : 16*(maxy-miny);
 374     C = rt ? pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy) : 0;
 375
 376     POLY_DEB( printf("  A=%d B=%d C=%d\n", A, B, C) );
 377
 378     ss->line[cpix] += A+B-C;
 379
 380   }
 381   POLY_DEB( printf("end render_slice_scanline()\n") );
 382 }
 383
 384 /* Antialiasing polygon algorithm
 385    specs:
 386    1. only nice polygons - no crossovers
 387    2. 1/16 pixel resolution
 388    3. full antialiasing ( complete spectrum of blends )
 389    4. uses hardly any memory
 390    5. no subsampling phase
 391
 392
 393    Algorithm outline:
 394    1. Split into vertical intervals.
 395    2. handle each interval
 396
 397    For each interval we must:
 398    1. find which lines are in it
 399    2. order the lines from in increasing x order.
 400       since we are assuming no crossovers it is sufficent
 401       to check a single point on each line.
 402 */
 403
 404 /*
 405   Definitions:
 406
 407   1. Interval:  A vertical segment in which no lines cross nor end.
 408   2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
 409   3. Slice:     A start stop line pair.
 410
 411  */
 412
 413
 414 static void
 415 i_poly_aa_low(i_img *im, int l, const double *x, const double *y, void *ctx, scanline_flusher flusher) {
 416   int i ,k;                     /* Index variables */
 417   int clc;                      /* Lines inside current interval */
 418   /* initialize to avoid compiler warnings */
 419   pcord tempy = 0;
 420   int cscl = 0;                 /* Current scanline */
 421
 422   ss_scanline templine;         /* scanline accumulator */
 423   p_point *pset;                /* List of points in polygon */
 424   p_line  *lset;                /* List of lines in polygon */
 425   p_slice *tllist;              /* List of slices */
 426
 427   mm_log((1, "i_poly_aa(im %p, l %d, x %p, y %p, ctx %p, flusher %p)\n", im, l, x, y, ctx, flusher));
 428
 429   for(i=0; i<l; i++) {
 430     mm_log((2, "(%.2f, %.2f)\n", x[i], y[i]));
 431   }
 432
 433
 434   POLY_DEB(
 435            fflush(stdout);
 436            setbuf(stdout, NULL);
 437            );
 438
 439   tllist   = mymalloc(sizeof(p_slice)*l);
 440
 441   ss_scanline_init(&templine, im->xsize, l);
 442
 443   pset     = point_set_new(x, y, l);
 444   lset     = line_set_new(x, y, l);
 445
 446
 447   qsort(pset, l, sizeof(p_point), (int(*)(const void *,const void *))p_compy);
 448
 449   POLY_DEB(
 450            for(i=0;i<l;i++) {
 451              printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",
 452                     i, lset[i].n, lset[i].x1, lset[i].y1, lset[i].x2, lset[i].y2, lset[i].miny, lset[i].maxy);
 453            }
 454            printf("MAIN LOOP\n\n");
 455            );
 456
 457
 458   /* loop on intervals */
 459   for(i=0; i<l-1; i++) {
 460     int startscan = i_max( coarse(pset[i].y), 0);
 461     int stopscan = i_min( coarse(pset[i+1].y+15), im->ysize);
 462     pcord miny, maxy;   /* y bounds in fine coordinates */
 463
 464     POLY_DEB( pcord cc = (pset[i].y + pset[i+1].y)/2 );
 465
 466     POLY_DEB(
 467              printf("current slice is %d: %d to %d ( cpoint %d ) scanlines %d to %d\n",
 468                     i, pset[i].y, pset[i+1].y, cc, startscan, stopscan)
 469              );
 470
 471     if (pset[i].y == pset[i+1].y) {
 472       POLY_DEB( printf("current slice thickness = 0 => skipping\n") );
 473       continue;
 474     }
 475
 476     clc = lines_in_interval(lset, l, tllist, pset[i].y, pset[i+1].y);
 477     qsort(tllist, clc, sizeof(p_slice), (int(*)(const void *,const void *))p_compx);
 478
 479     mark_updown_slices(lset, tllist, clc);
 480
 481     POLY_DEB
 482       (
 483        printf("Interval contains %d lines\n", clc);
 484        for(k=0; k<clc; k++) {
 485          int lno = tllist[k].n;
 486          p_line *ln = lset+lno;
 487          printf("%d:  line #%2d: (%2d, %2d)->(%2d, %2d) (%2d/%2d, %2d/%2d) -> (%2d/%2d, %2d/%2d) alignment=%s\n",
 488                 k, lno, ln->x1, ln->y1, ln->x2, ln->y2,
 489                 coarse(ln->x1), fine(ln->x1),
 490                 coarse(ln->y1), fine(ln->y1),
 491                 coarse(ln->x2), fine(ln->x2),
 492                 coarse(ln->y2), fine(ln->y2),
 493                 ln->updown == 0 ? "vert" : ln->updown == 1 ? "up" : "down");
 494
 495        }
 496        );
 497     maxy = im->ysize * 16;
 498     miny = 0;
 499     for (k = 0; k < clc; ++k) {
 500       p_line const * line = lset + tllist[k].n;
 501       if (line->miny > miny)
 502         miny = line->miny;
 503       if (line->maxy < maxy)
 504         maxy = line->maxy;
 505       POLY_DEB( printf(" line miny %g maxy %g\n", line->miny/16.0, line->maxy/16.0) );
 506     }
 507     POLY_DEB( printf("miny %g maxy %g\n", miny/16.0, maxy/16.0) );
 508
 509     for(cscl=startscan; cscl<stopscan; cscl++) {
 510       pcord scan_miny = i_max(miny, cscl * 16);
 511       pcord scan_maxy = i_min(maxy, (cscl + 1 ) * 16);
 512
 513       tempy = i_min(cscl*16+16, pset[i+1].y);
 514       POLY_DEB( printf("evaluating scan line %d \n", cscl) );
 515       for(k=0; k<clc-1; k+=2) {
 516         POLY_DEB( printf("evaluating slice %d\n", k) );
 517         render_slice_scanline(&templine, cscl, lset+tllist[k].n, lset+tllist[k+1].n, scan_miny, scan_maxy);
 518       }
 519       if (16*coarse(tempy) == tempy) {
 520         POLY_DEB( printf("flushing scan line %d\n", cscl) );
 521         flusher(im, &templine, cscl, ctx);
 522         ss_scanline_reset(&templine);
 523       }
 524       /*
 525         else {
 526         scanline_flush(im, &templine, cscl, val);
 527         ss_scanline_reset(&templine);
 528         return 0;
 529         }
 530       */
 531     }
 532   } /* Intervals */
 533   if (16*coarse(tempy) != tempy)
 534     flusher(im, &templine, cscl-1, ctx);
 535
 536   ss_scanline_exorcise(&templine);
 537   myfree(pset);
 538   myfree(lset);
 539   myfree(tllist);
 540
 541 } /* Function */
 542
 543 int
 544 i_poly_aa(i_img *im, int l, const double *x, const double *y, const i_color *val) {
 545   i_color c = *val;
 546   i_poly_aa_low(im, l, x, y, &c, scanline_flush);
 547   return 1;
 548 }
 549
 550 struct poly_render_state {
 551   i_render render;
 552   i_fill_t *fill;
 553   unsigned char *cover;
 554 };
 555
 556 static void
 557 scanline_flush_render(i_img *im, ss_scanline *ss, int y, void *ctx) {
 558   int x;
 559   int left, right;
 560   struct poly_render_state *state = (struct poly_render_state *)ctx;
 561
 562   left = 0;
 563   while (left < im->xsize && ss->line[left] <= 0)
 564     ++left;
 565   if (left < im->xsize) {
 566     right = im->xsize;
 567     /* since going from the left found something, moving from the
 568        right should */
 569     while (/* right > left && */ ss->line[right-1] <= 0)
 570       --right;
 571
 572     /* convert to the format the render interface wants */
 573     for (x = left; x < right; ++x) {
 574       state->cover[x-left] = saturate(ss->line[x]);
 575     }
 576     i_render_fill(&state->render, left, y, right-left, state->cover,
 577                   state->fill);
 578   }
 579 }
 580
 581 int
 582 i_poly_aa_cfill(i_img *im, int l, const double *x, const double *y,
 583                 i_fill_t *fill) {
 584   struct poly_render_state ctx;
 585
 586   i_render_init(&ctx.render, im, im->xsize);
 587   ctx.fill = fill;
 588   ctx.cover = mymalloc(im->xsize);
 589   i_poly_aa_low(im, l, x, y, &ctx, scanline_flush_render);
 590   myfree(ctx.cover);
 591   i_render_done(&ctx.render);
 592   return 1;
 593 }