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