draw.c

   1 #include "image.h"
   2 #include "draw.h"
   3 #include "log.h"
   4
   5 #include <limits.h>
   6
   7 void
   8 i_mmarray_cr(i_mmarray *ar,int l) {
   9   int i;
  10
  11   ar->lines=l;
  12   ar->data=mymalloc(sizeof(minmax)*l);
  13   for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
  14 }
  15
  16 void
  17 i_mmarray_dst(i_mmarray *ar) {
  18   ar->lines=0;
  19   if (ar->data != NULL) { myfree(ar->data); ar->data=NULL; }
  20 }
  21
  22 void
  23 i_mmarray_add(i_mmarray *ar,int x,int y) {
  24   if (y>-1 && y<ar->lines)
  25     {
  26       if (x<ar->data[y].min) ar->data[y].min=x;
  27       if (x>ar->data[y].max) ar->data[y].max=x;
  28     }
  29 }
  30
  31 int
  32 i_mmarray_gmin(i_mmarray *ar,int y) {
  33   if (y>-1 && y<ar->lines) return ar->data[y].min;
  34   else return -1;
  35 }
  36
  37 int
  38 i_mmarray_getm(i_mmarray *ar,int y) {
  39   if (y>-1 && y<ar->lines) return ar->data[y].max;
  40   else return MAXINT;
  41 }
  42
  43 void
  44 i_mmarray_render(i_img *im,i_mmarray *ar,i_color *val) {
  45   int i,x;
  46   for(i=0;i<ar->lines;i++) if (ar->data[i].max!=-1) for(x=ar->data[i].min;x<ar->data[i].max;x++) i_ppix(im,x,i,val);
  47 }
  48
  49 void
  50 i_mmarray_render_fill(i_img *im,i_mmarray *ar,i_fill_t *fill) {
  51   int x, w, y;
  52   if (im->bits == i_8_bits && fill->fill_with_color) {
  53     i_color *line = mymalloc(sizeof(i_color) * im->xsize);
  54     for(y=0;y<ar->lines;y++) {
  55       if (ar->data[y].max!=-1) {
  56         x = ar->data[y].min;
  57         w = ar->data[y].max-ar->data[y].min;
  58
  59         if (fill->combines)
  60           i_glin(im, x, x+w, y, line);
  61
  62         (fill->fill_with_color)(fill, x, y, w, im->channels, line);
  63         i_plin(im, x, x+w, y, line);
  64       }
  65     }
  66
  67     myfree(line);
  68   }
  69   else {
  70     i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
  71     for(y=0;y<ar->lines;y++) {
  72       if (ar->data[y].max!=-1) {
  73         x = ar->data[y].min;
  74         w = ar->data[y].max-ar->data[y].min;
  75
  76         if (fill->combines)
  77           i_glinf(im, x, x+w, y, line);
  78
  79         (fill->fill_with_fcolor)(fill, x, y, w, im->channels, line);
  80         i_plinf(im, x, x+w, y, line);
  81       }
  82     }
  83
  84     myfree(line);
  85   }
  86 }
  87
  88
  89 static
  90 void
  91 i_arcdraw(int x1, int y1, int x2, int y2, i_mmarray *ar) {
  92   double alpha;
  93   double dsec;
  94   int temp;
  95   alpha=(double)(y2-y1)/(double)(x2-x1);
  96   if (fabs(alpha)<1)
  97     {
  98       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
  99       dsec=y1;
 100       while(x1<x2)
 101         {
 102           dsec+=alpha;
 103           i_mmarray_add(ar,x1,(int)(dsec+0.5));
 104           x1++;
 105         }
 106     }
 107   else
 108     {
 109       alpha=1/alpha;
 110       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 111       dsec=x1;
 112       while(y1<y2)
 113         {
 114           dsec+=alpha;
 115           i_mmarray_add(ar,(int)(dsec+0.5),y1);
 116           y1++;
 117         }
 118     }
 119 }
 120
 121 void
 122 i_mmarray_info(i_mmarray *ar) {
 123   int i;
 124   for(i=0;i<ar->lines;i++)
 125   if (ar->data[i].max!=-1) printf("line %d: min=%d, max=%d.\n",i,ar->data[i].min,ar->data[i].max);
 126 }
 127
 128
 129 void
 130 i_arc(i_img *im,int x,int y,float rad,float d1,float d2,i_color *val) {
 131   i_mmarray dot;
 132   float f,fx,fy;
 133   int x1,y1;
 134
 135   mm_log((1,"i_arc(im* 0x%x,x %d,y %d,rad %.2f,d1 %.2f,d2 %.2f,val 0x%x)\n",im,x,y,rad,d1,d2,val));
 136
 137   i_mmarray_cr(&dot,im->ysize);
 138
 139   x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
 140   y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
 141   fx=(float)x1; fy=(float)y1;
 142
 143   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 144   i_arcdraw(x, y, x1, y1, &dot);
 145
 146   x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
 147   y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
 148
 149   for(f=d1;f<=d2;f+=0.01) i_mmarray_add(&dot,(int)(x+0.5+rad*cos(f*PI/180.0)),(int)(y+0.5+rad*sin(f*PI/180.0)));
 150
 151   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 152   i_arcdraw(x, y, x1, y1, &dot);
 153
 154   /*  dot.info(); */
 155   i_mmarray_render(im,&dot,val);
 156 }
 157
 158 void
 159 i_arc_cfill(i_img *im,int x,int y,float rad,float d1,float d2,i_fill_t *fill) {
 160   i_mmarray dot;
 161   float f,fx,fy;
 162   int x1,y1;
 163
 164   mm_log((1,"i_arc_cfill(im* 0x%x,x %d,y %d,rad %.2f,d1 %.2f,d2 %.2f,fill 0x%x)\n",im,x,y,rad,d1,d2,fill));
 165
 166   i_mmarray_cr(&dot,im->ysize);
 167
 168   x1=(int)(x+0.5+rad*cos(d1*PI/180.0));
 169   y1=(int)(y+0.5+rad*sin(d1*PI/180.0));
 170   fx=(float)x1; fy=(float)y1;
 171
 172   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 173   i_arcdraw(x, y, x1, y1, &dot);
 174
 175   x1=(int)(x+0.5+rad*cos(d2*PI/180.0));
 176   y1=(int)(y+0.5+rad*sin(d2*PI/180.0));
 177
 178   for(f=d1;f<=d2;f+=0.01) i_mmarray_add(&dot,(int)(x+0.5+rad*cos(f*PI/180.0)),(int)(y+0.5+rad*sin(f*PI/180.0)));
 179
 180   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
 181   i_arcdraw(x, y, x1, y1, &dot);
 182
 183   /*  dot.info(); */
 184   i_mmarray_render_fill(im,&dot,fill);
 185 }
 186
 187
 188
 189 /* Temporary AA HACK */
 190
 191
 192 typedef int frac;
 193 static  frac float_to_frac(float x) { return (frac)(0.5+x*16.0); }
 194 static   int frac_sub     (frac x)  { return (x%16); }
 195 static   int frac_int     (frac x)  { return (x/16); }
 196 static float frac_to_float(float x) { return (float)x/16.0; }
 197
 198 static
 199 void
 200 polar_to_plane(float cx, float cy, float angle, float radius, frac *x, frac *y) {
 201   *x = float_to_frac(cx+radius*cos(angle));
 202   *y = float_to_frac(cy+radius*sin(angle));
 203 }
 204
 205 static
 206 void
 207 order_pair(frac *x, frac *y) {
 208   frac t = *x;
 209   if (t>*y) {
 210     *x = *y;
 211     *y = t;
 212   }
 213 }
 214
 215
 216
 217
 218 static
 219 void
 220 make_minmax_list(i_mmarray *dot, float x, float y, float radius) {
 221   float angle = 0.0;
 222   float astep = radius>0.1 ? .5/radius : 10;
 223   frac cx, cy, lx, ly, sx, sy;
 224
 225   mm_log((1, "make_minmax_list(dot %p, x %.2f, y %.2f, radius %.2f)\n", dot, x, y, radius));
 226
 227   polar_to_plane(x, y, angle, radius, &sx, &sy);
 228
 229   for(angle = 0.0; angle<361; angle +=astep) {
 230     float alpha;
 231     lx = sx; ly = sy;
 232     polar_to_plane(x, y, angle, radius, &cx, &cy);
 233     sx = cx; sy = cy;
 234
 235     if (fabs(cx-lx) > fabs(cy-ly)) {
 236       int ccx, ccy;
 237       if (lx>cx) {
 238         ccx = lx; lx = cx; cx = ccx;
 239         ccy = ly; ly = cy; cy = ccy;
 240       }
 241
 242       for(ccx=lx; ccx<=cx; ccx++) {
 243         ccy = ly + ((cy-ly)*(ccx-lx))/(cx-lx);
 244         i_mmarray_add(dot, ccx, ccy);
 245       }
 246     } else {
 247       int ccx, ccy;
 248
 249       if (ly>cy) {
 250         ccy = ly; ly = cy; cy = ccy;
 251         ccx = lx; lx = cx; cx = ccx;
 252       }
 253
 254       for(ccy=ly; ccy<=cy; ccy++) {
 255         if (cy-ly) ccx = lx + ((cx-lx)*(ccy-ly))/(cy-ly); else ccx = lx;
 256         i_mmarray_add(dot, ccx, ccy);
 257       }
 258     }
 259   }
 260 }
 261
 262 /* Get the number of subpixels covered */
 263
 264 static
 265 int
 266 i_pixel_coverage(i_mmarray *dot, int x, int y) {
 267   frac minx = x*16;
 268   frac maxx = minx+15;
 269   frac cy;
 270   int cnt = 0;
 271
 272   for(cy=y*16; cy<(y+1)*16; cy++) {
 273     frac tmin = dot->data[cy].min;
 274     frac tmax = dot->data[cy].max;
 275
 276     if (tmax == -1 || tmin > maxx || tmax < minx) continue;
 277
 278     if (tmin < minx) tmin = minx;
 279     if (tmax > maxx) tmax = maxx;
 280
 281     cnt+=1+tmax-tmin;
 282   }
 283   return cnt;
 284 }
 285
 286 void
 287 i_circle_aa(i_img *im, float x, float y, float rad, i_color *val) {
 288   i_mmarray dot;
 289   i_color temp;
 290   int ly;
 291
 292   mm_log((1, "i_circle_aa(im %p, x %d, y %d, rad %.2f, val %p)\n", im, x, y, rad, val));
 293
 294   i_mmarray_cr(&dot,16*im->ysize);
 295   make_minmax_list(&dot, x, y, rad);
 296
 297   for(ly = 0; ly<im->ysize; ly++) {
 298     int ix, cy, cnt = 0, minx = INT_MAX, maxx = INT_MIN;
 299
 300     /* Find the left/rightmost set subpixels */
 301     for(cy = 0; cy<16; cy++) {
 302       frac tmin = dot.data[ly*16+cy].min;
 303       frac tmax = dot.data[ly*16+cy].max;
 304       if (tmax == -1) continue;
 305
 306       if (minx > tmin) minx = tmin;
 307       if (maxx < tmax) maxx = tmax;
 308     }
 309
 310     if (maxx == INT_MIN) continue; /* no work to be done for this row of pixels */
 311
 312     minx /= 16;
 313     maxx /= 16;
 314     for(ix=minx; ix<=maxx; ix++) {
 315       int cnt = i_pixel_coverage(&dot, ix, ly);
 316       if (cnt>255) cnt = 255;
 317       if (cnt) { /* should never be true */
 318         int ch;
 319         float ratio = (float)cnt/255.0;
 320         i_gpix(im, ix, ly, &temp);
 321         for(ch=0;ch<im->channels; ch++) temp.channel[ch] = (unsigned char)((float)val->channel[ch]*ratio + (float)temp.channel[ch]*(1.0-ratio));
 322         i_ppix(im, ix, ly, &temp);
 323       }
 324     }
 325   }
 326 }
 327
 328
 329
 330
 331
 332
 333 void
 334 i_box(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 335   int x,y;
 336   mm_log((1,"i_box(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
 337   for(x=x1;x<x2+1;x++) {
 338     i_ppix(im,x,y1,val);
 339     i_ppix(im,x,y2,val);
 340   }
 341   for(y=y1;y<y2+1;y++) {
 342     i_ppix(im,x1,y,val);
 343     i_ppix(im,x2,y,val);
 344   }
 345 }
 346
 347 void
 348 i_box_filled(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 349   int x,y;
 350   mm_log((1,"i_box_filled(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
 351   for(x=x1;x<x2+1;x++) for (y=y1;y<y2+1;y++) i_ppix(im,x,y,val);
 352 }
 353
 354 void
 355 i_box_cfill(i_img *im,int x1,int y1,int x2,int y2,i_fill_t *fill) {
 356   mm_log((1,"i_box_cfill(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,fill 0x%x)\n",im,x1,y1,x2,y2,fill));
 357
 358   ++x2;
 359   if (im->bits == i_8_bits && fill->fill_with_color) {
 360     i_color *line = mymalloc(sizeof(i_color) * (x2 - x1));
 361     while (y1 <= y2) {
 362       if (fill->combines)
 363         i_glin(im, x1, x2, y1, line);
 364
 365       (fill->fill_with_color)(fill, x1, y1, x2-x1, im->channels, line);
 366       i_plin(im, x1, x2, y1, line);
 367       ++y1;
 368     }
 369     myfree(line);
 370   }
 371   else {
 372     i_fcolor *line = mymalloc(sizeof(i_fcolor) * (x2 - x1));
 373     while (y1 <= y2) {
 374       if (fill->combines)
 375         i_glinf(im, x1, x2, y1, line);
 376
 377       (fill->fill_with_fcolor)(fill, x1, y1, x2-x1, im->channels, line);
 378       i_plinf(im, x1, x2, y1, line);
 379       ++y1;
 380     }
 381     myfree(line);
 382   }
 383 }
 384
 385 void
 386 i_draw(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 387   double alpha;
 388   double dsec;
 389   int temp;
 390
 391   mm_log((1,"i_draw(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
 392
 393   alpha=(double)(y2-y1)/(double)(x2-x1);
 394   if (fabs(alpha)<1)
 395     {
 396       if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 397       dsec=y1;
 398       while(x1<x2)
 399         {
 400           dsec+=alpha;
 401           i_ppix(im,x1,(int)(dsec+0.5),val);
 402           x1++;
 403         }
 404     }
 405   else
 406     {
 407       alpha=1/alpha;
 408       if (y2<y1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 409       dsec=x1;
 410       while(y1<y2)
 411         {
 412           dsec+=alpha;
 413           i_ppix(im,(int)(dsec+0.5),y1,val);
 414           y1++;
 415         }
 416     }
 417   mm_log((1,"i_draw: alpha=%f.\n",alpha));
 418 }
 419
 420 void
 421 i_line_aa(i_img *im,int x1,int y1,int x2,int y2,i_color *val) {
 422   i_color tval;
 423   float alpha;
 424   float dsec,dfrac;
 425   int temp,dx,dy,isec,ch;
 426
 427   mm_log((1,"i_draw(im* 0x%x,x1 %d,y1 %d,x2 %d,y2 %d,val 0x%x)\n",im,x1,y1,x2,y2,val));
 428
 429   dy=y2-y1;
 430   dx=x2-x1;
 431
 432   if (abs(dx)>abs(dy)) { /* alpha < 1 */
 433     if (x2<x1) { temp=x1; x1=x2; x2=temp; temp=y1; y1=y2; y2=temp; }
 434     alpha=(float)(y2-y1)/(float)(x2-x1);
 435
 436     dsec=y1;
 437     while(x1<=x2) {
 438       isec=(int)dsec;
 439       dfrac=dsec-isec;
 440       /*      dfrac=1-(1-dfrac)*(1-dfrac); */
 441       /* This is something we can play with to try to get better looking lines */
 442
 443       i_gpix(im,x1,isec,&tval);
 444       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
 445       i_ppix(im,x1,isec,&tval);
 446
 447       i_gpix(im,x1,isec+1,&tval);
 448       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
 449       i_ppix(im,x1,isec+1,&tval);
 450
 451       dsec+=alpha;
 452       x1++;
 453     }
 454   } else {
 455     if (y2<y1) { temp=y1; y1=y2; y2=temp; temp=x1; x1=x2; x2=temp; }
 456     alpha=(float)(x2-x1)/(float)(y2-y1);
 457     dsec=x1;
 458     while(y1<=y2) {
 459       isec=(int)dsec;
 460       dfrac=dsec-isec;
 461       /*      dfrac=sqrt(dfrac); */
 462       /* This is something we can play with */
 463       i_gpix(im,isec,y1,&tval);
 464       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)(dfrac*(float)tval.channel[ch]+(1-dfrac)*(float)val->channel[ch]);
 465       i_ppix(im,isec,y1,&tval);
 466
 467       i_gpix(im,isec+1,y1,&tval);
 468       for(ch=0;ch<im->channels;ch++) tval.channel[ch]=(unsigned char)((1-dfrac)*(float)tval.channel[ch]+dfrac*(float)val->channel[ch]);
 469       i_ppix(im,isec+1,y1,&tval);
 470
 471       dsec+=alpha;
 472       y1++;
 473     }
 474   }
 475 }
 476
 477 double
 478 perm(int n,int k) {
 479   double r;
 480   int i;
 481   r=1;
 482   for(i=k+1;i<=n;i++) r*=i;
 483   for(i=1;i<=(n-k);i++) r/=i;
 484   return r;
 485 }
 486
 487
 488 /* Note in calculating t^k*(1-t)^(n-k)
 489    we can start by using t^0=1 so this simplifies to
 490    t^0*(1-t)^n - we want to multiply that with t/(1-t) each iteration
 491    to get a new level - this may lead to errors who knows lets test it */
 492
 493 void
 494 i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
 495   double *bzcoef;
 496   double t,cx,cy;
 497   int k,i;
 498   int lx = 0,ly = 0;
 499   int n=l-1;
 500   double itr,ccoef;
 501
 502
 503   bzcoef=mymalloc(sizeof(double)*l);
 504   for(k=0;k<l;k++) bzcoef[k]=perm(n,k);
 505   ICL_info(val);
 506
 507
 508   /*  for(k=0;k<l;k++) printf("bzcoef: %d -> %f\n",k,bzcoef[k]); */
 509   i=0;
 510   for(t=0;t<=1;t+=0.005) {
 511     cx=cy=0;
 512     itr=t/(1-t);
 513     ccoef=pow(1-t,n);
 514     for(k=0;k<l;k++) {
 515       /*      cx+=bzcoef[k]*x[k]*pow(t,k)*pow(1-t,n-k);
 516               cy+=bzcoef[k]*y[k]*pow(t,k)*pow(1-t,n-k);*/
 517
 518       cx+=bzcoef[k]*x[k]*ccoef;
 519       cy+=bzcoef[k]*y[k]*ccoef;
 520       ccoef*=itr;
 521     }
 522     /*    printf("%f -> (%d,%d)\n",t,(int)(0.5+cx),(int)(0.5+cy)); */
 523     if (i++) {
 524       i_line_aa(im,lx,ly,(int)(0.5+cx),(int)(0.5+cy),val);
 525     }
 526       /*     i_ppix(im,(int)(0.5+cx),(int)(0.5+cy),val); */
 527     lx=(int)(0.5+cx);
 528     ly=(int)(0.5+cy);
 529   }
 530   ICL_info(val);
 531   myfree(bzcoef);
 532 }
 533
 534
 535
 536 /* Flood fill
 537
 538    REF: Graphics Gems I. page 282+
 539
 540 */
 541
 542 /* This should be moved into a seperate file? */
 543
 544 /* This is the truncation used:
 545
 546    a double is multiplied by 16 and then truncated.
 547    This means that 0 -> 0
 548    So a triangle of (0,0) (10,10) (10,0) Will look like it's
 549    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
 550
 551 */
 552
 553
 554
 555
 556 #define IMTRUNC(x) ((int)(x*16))
 557
 558
 559 /*
 560 typedef struct {
 561   short ms,ls;
 562 } pcord;
 563 */
 564
 565 typedef int pcord;
 566
 567 struct p_point {
 568   int n;
 569   pcord x,y;
 570 };
 571
 572 struct p_line  {
 573   int n;
 574   pcord x1,y1;
 575   pcord x2,y2;
 576   pcord miny,maxy;
 577 };
 578
 579 struct p_slice {
 580   int n;
 581   double x;
 582 };
 583
 584 int
 585 p_compy(const struct p_point *p1, const struct p_point *p2) {
 586   if (p1->y > p2->y) return 1;
 587   if (p1->y < p2->y) return -1;
 588   return 0;
 589 }
 590
 591 int
 592 p_compx(const struct p_slice *p1, const struct p_slice *p2) {
 593   if (p1->x > p2->x) return 1;
 594   if (p1->x < p2->x) return -1;
 595   return 0;
 596 }
 597
 598 /* Change this to int? and round right goddamn it! */
 599
 600 double
 601 p_eval_aty(struct p_line *l,pcord y) {
 602   int t;
 603   t=l->y2-l->y1;
 604   if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
 605   return (l->x1+l->x2)/2.0;
 606 }
 607
 608 double
 609 p_eval_atx(struct p_line *l,pcord x) {
 610   int t;
 611   t=l->x2-l->x1;
 612   if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
 613   return (l->y1+l->y2)/2.0;
 614 }
 615
 616
 617 /* Algorithm to count the pixels covered by line going through pixel (x,y)
 618    in coarse coords.
 619 */
 620
 621 /*
 622 static int
 623 p_eval_coverage(struct p_line *l, int lc, int x, pcord y1, pcord y2) {
 624
 625   return 0;
 626 }
 627 */
 628
 629
 630 /* Antialiasing polygon algorithm
 631    specs:
 632      1. only nice polygons - no crossovers
 633      2. 1/16 pixel resolution # previously - floating point co-ordinates
 634      3. full antialiasing ( complete spectrum of blends )
 635      4. uses hardly any memory
 636      5. no subsampling phase
 637
 638    For each interval we must:
 639      1. find which lines are in it
 640      2. order the lines from in increasing x order.
 641         since we are assuming no crossovers it is sufficent
 642         to check a single point on each line.
 643 */
 644
 645 /*
 646   Terms:
 647
 648     1. Interval:  A vertical segment in which no lines cross nor end.
 649     2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
 650     3. Slice:     A start stop line pair.
 651
 652  */
 653
 654 /* Templine logic:
 655
 656    The variable tempflush describes if there is anything in the templine array or not.
 657
 658    if tempflush is 0 then the array is clean.
 659    if tempflush is 1 then the array contains a partial filled scanline
 660
 661  */
 662
 663 /* Rendering of a single start stop pair:
 664
 665 ?? REWRITE
 666
 667    The rendering is split in three parts
 668    1. From the first start pixel to the first stop pixel
 669    2. Area from the first end pixel to the last start pixel
 670    3. Area from the first end pixel to the last start pixel
 671
 672  */
 673
 674
 675 void
 676 i_poly_aa(i_img *im,int l,double *x,double *y,i_color *val) {
 677   int i,k;                      /* Index variables */
 678   int clc;                      /* Index of next item on interval linelist */
 679   int tx;                       /* Coarse x coord within a scanline */
 680   pcord miny,maxy;              /* Min and max values of the current slice in the subcord system */
 681   pcord minacy,maxacy;          /* Min and max values of the current scanline bounded by the slice
 682                                    in the subcord system */
 683   int cscl;                     /* Current scanline */
 684   pcord cc;                     /* Current vertical centerpoint of interval */
 685   int mt1,mt2;
 686   int minsx,minex,maxsx,maxex;  /* The horizontal stretches of the lines beloning to the current slice within a scanline */
 687   int *templine;                /* Line accumulator */
 688
 689   struct p_point *pset;         /* List of points in polygon */
 690   struct p_line *lset;          /* List of lines in polygon */
 691   struct p_slice *tllist;       /* List of slices */
 692
 693   i_color red,blue,yellow;
 694   red.rgb.r=255;
 695   red.rgb.g=0;
 696   red.rgb.b=0;
 697
 698   blue.rgb.r=0;
 699   blue.rgb.g=0;
 700   blue.rgb.b=255;
 701
 702   yellow.rgb.r=255;
 703   yellow.rgb.g=255;
 704   yellow.rgb.b=255;
 705
 706   if ( (pset=mymalloc(sizeof(struct p_point)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 707   if ( (lset=mymalloc(sizeof(struct p_line)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 708   if ( (tllist=mymalloc(sizeof(struct p_slice)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 709   if ( (templine=mymalloc(sizeof(int)*im->xsize)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 710
 711   /* insert the lines into the line list */
 712
 713   for(i=0;i<l;i++) {
 714     pset[i].n=i;
 715     pset[i].x=IMTRUNC(x[i]);
 716     pset[i].y=IMTRUNC(y[i]);
 717     lset[i].n=i;
 718     lset[i].x1=IMTRUNC(x[i]);
 719     lset[i].y1=IMTRUNC(y[i]);
 720     lset[i].x2=IMTRUNC(x[(i+1)%l]);
 721     lset[i].y2=IMTRUNC(y[(i+1)%l]);
 722     lset[i].miny=min(lset[i].y1,lset[i].y2);
 723     lset[i].maxy=max(lset[i].y1,lset[i].y2);
 724   }
 725
 726   qsort(pset,l,sizeof(struct p_point),(int(*)(const void *,const void *))p_compy);
 727
 728   printf("post point list (sorted in ascending y order)\n");
 729   for(i=0;i<l;i++) {
 730     printf("%d [ %d ] %d %d\n",i,pset[i].n,pset[i].x,pset[i].y);
 731   }
 732
 733   printf("line list\n");
 734   for(i=0;i<l;i++) {
 735     printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",i,lset[i].n,lset[i].x1,lset[i].y1,lset[i].x2,lset[i].y2,lset[i].miny,lset[i].maxy);
 736   }
 737
 738   printf("MAIN LOOP\n\n");
 739
 740   /* Zero templine buffer */
 741   /* Templine buffer flushed everytime a scan line ends */
 742   for(i=0;i<im->xsize;i++) templine[i]=0;
 743
 744
 745   /* loop on intervals */
 746   for(i=0;i<l-1;i++) {
 747     cc=(pset[i].y+pset[i+1].y)/2;
 748     printf("current slice is: %d to %d ( cpoint %d )\n",pset[i].y,pset[i+1].y,cc);
 749     clc=0;
 750
 751     /* stuff this in a function ?? */
 752
 753     /* Check what lines belong to interval */
 754     for(k=0;k<l;k++) {
 755       printf("checking line: %d [ %d ] (%d , %d) -> (%d, %d) yspan ( %d , %d )",
 756              k,lset[k].n,lset[k].x1,lset[k].y1,lset[k].x2,lset[k].y2,lset[k].miny,lset[k].maxy);
 757       if (cc >= lset[k].miny && cc <=  lset[k].maxy) {
 758         if (lset[k].miny == lset[k].maxy) printf(" HORIZONTAL - skipped\n");
 759         else {
 760           printf(" INSIDE\n");
 761           tllist[clc].x=p_eval_aty(&lset[k],cc);
 762           tllist[clc++].n=k;
 763         }
 764       } else printf(" OUTSIDE\n");
 765     }
 766
 767     /*
 768        at this point a table of pixels that need special care should
 769        be generated from the line list - it should be ordered so that only
 770        one needs to be checked - options: rendering to a list then order - or
 771        rendering in the right order might be possible to do nicely with the
 772        following heuristic:
 773
 774        1. Draw leftmost pixel for this line
 775        2. If preceeding pixel was occupied check next one else go to 1 again.
 776     */
 777
 778     printf("lines in current interval:");
 779     for(k=0;k<clc;k++) printf("  %d (%.2f)",tllist[k].n,tllist[k].x);
 780     printf("\n");
 781
 782     /* evaluate the lines in the middle of the slice */
 783
 784     printf("Sort lines left to right within interval\n");
 785     qsort(tllist,clc,sizeof(struct p_slice),(int(*)(const void *,const void *))p_compx);
 786
 787     printf("sorted lines in interval - output:");
 788     for(k=0;k<clc;k++) printf(" %d",tllist[k].n);
 789     printf("\n");
 790
 791     miny=pset[i].y;
 792     maxy=pset[i+1].y;
 793
 794     /* iterate over scanlines */
 795     for(cscl=(miny)/16;cscl<=maxy/16;cscl++) {
 796       minacy=max(miny,cscl*16);
 797       maxacy=min(maxy,cscl*16+15);
 798
 799       printf("Scanline bound %d - %d\n",minacy, maxacy);
 800
 801       /* iterate over line pairs (slices) within interval */
 802       for(k=0;k<clc-1;k+=2) {
 803
 804         mt1=p_eval_aty(&lset[tllist[k].n],minacy);      /* upper corner */
 805         mt2=p_eval_aty(&lset[tllist[k].n],maxacy);      /* lower corner */
 806         minsx=min(mt1,mt2);
 807         minex=max(mt1,mt2);
 808         mt1=p_eval_aty(&lset[tllist[k+1].n],minacy);    /* upper corner */
 809         mt2=p_eval_aty(&lset[tllist[k+1].n],maxacy);    /* lower corner */
 810         maxsx=min(mt1,mt2);
 811         maxex=max(mt1,mt2);
 812
 813         printf("minsx: %d minex: %d\n",minsx,minex);
 814         printf("maxsx: %d maxex: %d\n",maxsx,maxex);
 815
 816         if (minex/16<maxsx/16) printf("Scan slice is simple!\n");
 817         else printf("Scan slice is complicated!\n");
 818
 819         if (minsx/16 == minex/16) { /* The line starts and ends in the same pixel */
 820           printf("Low slant start pixel\n");
 821           templine[minsx/16]=(maxacy-minacy+1)*(minex-minsx+1)/2+((minex | 0xF)-minex)*(maxacy-minacy+1);
 822         } else {
 823           for(tx=minsx/16;tx<minex/16+1;tx++) {
 824             int minx,maxx,minxy,maxxy;
 825             minx=max(minsx,  tx*16   );
 826             maxx=min(minex,  tx*16+15);
 827
 828             if (minx == maxx) {
 829               templine[tx]=(maxacy-minacy+1);
 830             } else {
 831
 832               minxy=p_eval_atx(&lset[tllist[k].n], minx);
 833               maxxy=p_eval_atx(&lset[tllist[k].n], maxx);
 834
 835               templine[tx]+=(abs(minxy-maxxy)+1)*(minex-minsx+1)/2; /* The triangle between the points */
 836               if (mt1 < mt2) { /* \ slant */
 837                 /* ((minex | 0xF)-minex)*(maxacy-minacy+1); FIXME: unfinished */
 838
 839
 840
 841               } else {
 842                 templine[tx]+=((minex | 0xF)-minex)*(maxacy-minacy+1);
 843               }
 844
 845             }
 846           }
 847         }
 848
 849         for(tx=maxsx/16;tx<maxex/16+1;tx++) templine[tx]+=16*(maxacy-minacy+1);
 850
 851         /*      for(tx=minex/16+1;tx<maxsx/16;tx++) 0; */
 852
 853
 854         printf("line %d: painting  %d - %d\n",cscl,minex/16+1,maxsx/16);
 855         if ( (minacy != cscl*16) || (maxacy != cscl*16+15) ) {
 856           for(tx=minsx/16;tx<maxex/16+1;tx++) {
 857             i_ppix(im,tx,cscl,&yellow);
 858           }
 859         }
 860         else {
 861           for(tx=minsx/16;tx<minex/16+1;tx++) i_ppix(im,tx,cscl,&red);
 862           for(tx=maxsx/16;tx<maxex/16+1;tx++) i_ppix(im,tx,cscl,&blue);
 863           for(tx=minex/16+1;tx<maxsx/16;tx++) i_ppix(im,tx,cscl,val);
 864         }
 865
 866       } /* Slices */
 867     } /* Scanlines */
 868   } /* Intervals */
 869 } /* Function */
 870
 871
 872
 873
 874
 875
 876
 877 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
 878    graphics gems I */
 879
 880 /*
 881 struct stc {
 882   int mylx,myrx;
 883   int dadlx,dadrx;
 884   int myy;
 885   int mydirection;
 886 };
 887
 888 Not used code???
 889 */
 890
 891
 892 struct stack_element {
 893   int myLx,myRx;
 894   int dadLx,dadRx;
 895   int myY;
 896   int myDirection;
 897 };
 898
 899
 900 /* create the link data to put push onto the stack */
 901
 902 static
 903 struct stack_element*
 904 crdata(int left,int right,int dadl,int dadr,int y, int dir) {
 905   struct stack_element *ste;
 906   ste=(struct stack_element*)mymalloc(sizeof(struct stack_element));
 907   ste->myLx=left;
 908   ste->myRx=right;
 909   ste->dadLx=dadl;
 910   ste->dadRx=dadr;
 911   ste->myY=y;
 912   ste->myDirection=dir;
 913   return ste;
 914 }
 915
 916 /* i_ccomp compares two colors and gives true if they are the same */
 917
 918 static int
 919 i_ccomp(i_color *val1,i_color *val2,int ch) {
 920   int i;
 921   for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
 922   return 1;
 923 }
 924
 925
 926 static int
 927 i_lspan(i_img *im,int seedx,int seedy,i_color *val) {
 928   i_color cval;
 929   while(1) {
 930     if (seedx-1 < 0) break;
 931     i_gpix(im,seedx-1,seedy,&cval);
 932     if (!i_ccomp(val,&cval,im->channels)) break;
 933     seedx--;
 934   }
 935   return seedx;
 936 }
 937
 938 static int
 939 i_rspan(i_img *im,int seedx,int seedy,i_color *val) {
 940   i_color cval;
 941   while(1) {
 942     if (seedx+1 > im->xsize-1) break;
 943     i_gpix(im,seedx+1,seedy,&cval);
 944     if (!i_ccomp(val,&cval,im->channels)) break;
 945     seedx++;
 946   }
 947   return seedx;
 948 }
 949
 950 /* Macro to create a link and push on to the list */
 951
 952 #define ST_PUSH(left,right,dadl,dadr,y,dir) { struct stack_element *s=crdata(left,right,dadl,dadr,y,dir); llist_push(st,&s);}
 953
 954 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
 955 /* No overflow check! */
 956
 957 #define ST_POP() { struct stack_element *s; llist_pop(st,&s); lx=s->myLx; rx=s->myRx; dadLx=s->dadLx; dadRx=s->dadRx; y=s->myY; direction=s->myDirection; myfree(s); }
 958
 959 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) { int pushrx=rx+1; int pushlx=lx-1; ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir); if (rx > dadRx) ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir); if (lx < dadLx) ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir); }
 960
 961 #define SET(x,y) btm_set(btm,x,y);
 962
 963 #define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels)  ) ))
 964
 965 void
 966 i_flood_fill(i_img *im,int seedx,int seedy,i_color *dcol) {
 967
 968   int lx,rx;
 969   int y;
 970   int direction;
 971   int dadLx,dadRx;
 972
 973   int wasIn=0;
 974   int x=0;
 975
 976   /*  int tx,ty; */
 977
 978   int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
 979
 980   struct llist *st;
 981   struct i_bitmap *btm;
 982
 983   int channels,xsize,ysize;
 984   i_color cval,val;
 985
 986   channels=im->channels;
 987   xsize=im->xsize;
 988   ysize=im->ysize;
 989
 990   btm=btm_new(xsize,ysize);
 991   st=llist_new(100,sizeof(struct stack_element*));
 992
 993   /* Get the reference color */
 994   i_gpix(im,seedx,seedy,&val);
 995
 996   /* Find the starting span and fill it */
 997   lx=i_lspan(im,seedx,seedy,&val);
 998   rx=i_rspan(im,seedx,seedy,&val);
 999
1000   /* printf("span: %d %d \n",lx,rx); */
1001
1002   for(x=lx;x<=rx;x++) SET(x,seedy);
1003
1004   ST_PUSH(lx,rx,lx,rx,seedy+1,1);
1005   ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
1006
1007   while(st->count) {
1008     ST_POP();
1009
1010     if (y<0 || y>ysize-1) continue;
1011
1012     if (bymin > y) bymin=y; /* in the worst case an extra line */
1013     if (bymax < y) bymax=y;
1014
1015     /*     printf("start of scan - on stack : %d \n",st->count); */
1016
1017
1018     /*     printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
1019
1020     /*
1021     printf(" ");
1022     for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
1023     printf("\n");
1024     for(ty=0;ty<ysize;ty++) {
1025       printf("%d",ty%10);
1026       for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
1027       printf("\n");
1028     }
1029
1030     printf("y=%d\n",y);
1031     */
1032
1033
1034     x=lx+1;
1035     if ( (wasIn = INSIDE(lx,y)) ) {
1036       SET(lx,y);
1037       lx--;
1038       while(INSIDE(lx,y) && lx > 0) {
1039         SET(lx,y);
1040         lx--;
1041       }
1042     }
1043
1044     if (bxmin > lx) bxmin=lx;
1045
1046     while(x <= xsize-1) {
1047       /*  printf("x=%d\n",x); */
1048       if (wasIn) {
1049
1050         if (INSIDE(x,y)) {
1051           /* case 1: was inside, am still inside */
1052           SET(x,y);
1053         } else {
1054           /* case 2: was inside, am no longer inside: just found the
1055              right edge of a span */
1056           ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1057
1058           if (bxmax < x) bxmax=x;
1059
1060           wasIn=0;
1061         }
1062       } else {
1063         if (x>rx) goto EXT;
1064         if (INSIDE(x,y)) {
1065           SET(x,y);
1066           /* case 3: Wasn't inside, am now: just found the start of a new run */
1067           wasIn=1;
1068             lx=x;
1069         } else {
1070           /* case 4: Wasn't inside, still isn't */
1071         }
1072       }
1073       x++;
1074     }
1075   EXT: /* out of loop */
1076     if (wasIn) {
1077       /* hit an edge of the frame buffer while inside a run */
1078       ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1079       if (bxmax < x) bxmax=x;
1080     }
1081   }
1082
1083   /*   printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
1084        printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
1085
1086   for(y=bymin;y<=bymax;y++) for(x=bxmin;x<=bxmax;x++) if (btm_test(btm,x,y)) i_ppix(im,x,y,dcol);
1087
1088   btm_destroy(btm);
1089   llist_destroy(st);
1090 }
1091
1092 static struct i_bitmap *
1093 i_flood_fill_low(i_img *im,int seedx,int seedy,
1094                  int *bxminp, int *bxmaxp, int *byminp, int *bymaxp) {
1095   int lx,rx;
1096   int y;
1097   int direction;
1098   int dadLx,dadRx;
1099
1100   int wasIn=0;
1101   int x=0;
1102
1103   /*  int tx,ty; */
1104
1105   int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
1106
1107   struct llist *st;
1108   struct i_bitmap *btm;
1109
1110   int channels,xsize,ysize;
1111   i_color cval,val;
1112
1113   channels=im->channels;
1114   xsize=im->xsize;
1115   ysize=im->ysize;
1116
1117   btm=btm_new(xsize,ysize);
1118   st=llist_new(100,sizeof(struct stack_element*));
1119
1120   /* Get the reference color */
1121   i_gpix(im,seedx,seedy,&val);
1122
1123   /* Find the starting span and fill it */
1124   lx=i_lspan(im,seedx,seedy,&val);
1125   rx=i_rspan(im,seedx,seedy,&val);
1126
1127   /* printf("span: %d %d \n",lx,rx); */
1128
1129   for(x=lx;x<=rx;x++) SET(x,seedy);
1130
1131   ST_PUSH(lx,rx,lx,rx,seedy+1,1);
1132   ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
1133
1134   while(st->count) {
1135     ST_POP();
1136
1137     if (y<0 || y>ysize-1) continue;
1138
1139     if (bymin > y) bymin=y; /* in the worst case an extra line */
1140     if (bymax < y) bymax=y;
1141
1142     /*     printf("start of scan - on stack : %d \n",st->count); */
1143
1144
1145     /*     printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
1146
1147     /*
1148     printf(" ");
1149     for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
1150     printf("\n");
1151     for(ty=0;ty<ysize;ty++) {
1152       printf("%d",ty%10);
1153       for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
1154       printf("\n");
1155     }
1156
1157     printf("y=%d\n",y);
1158     */
1159
1160
1161     x=lx+1;
1162     if ( (wasIn = INSIDE(lx,y)) ) {
1163       SET(lx,y);
1164       lx--;
1165       while(INSIDE(lx,y) && lx > 0) {
1166         SET(lx,y);
1167         lx--;
1168       }
1169     }
1170
1171     if (bxmin > lx) bxmin=lx;
1172
1173     while(x <= xsize-1) {
1174       /*  printf("x=%d\n",x); */
1175       if (wasIn) {
1176
1177         if (INSIDE(x,y)) {
1178           /* case 1: was inside, am still inside */
1179           SET(x,y);
1180         } else {
1181           /* case 2: was inside, am no longer inside: just found the
1182              right edge of a span */
1183           ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1184
1185           if (bxmax < x) bxmax=x;
1186
1187           wasIn=0;
1188         }
1189       } else {
1190         if (x>rx) goto EXT;
1191         if (INSIDE(x,y)) {
1192           SET(x,y);
1193           /* case 3: Wasn't inside, am now: just found the start of a new run */
1194           wasIn=1;
1195             lx=x;
1196         } else {
1197           /* case 4: Wasn't inside, still isn't */
1198         }
1199       }
1200       x++;
1201     }
1202   EXT: /* out of loop */
1203     if (wasIn) {
1204       /* hit an edge of the frame buffer while inside a run */
1205       ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1206       if (bxmax < x) bxmax=x;
1207     }
1208   }
1209
1210   /*   printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
1211        printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
1212
1213   llist_destroy(st);
1214
1215   *bxminp = bxmin;
1216   *bxmaxp = bxmax;
1217   *byminp = bymin;
1218   *bymaxp = bymax;
1219
1220   return btm;
1221 }
1222
1223 void
1224 i_flood_cfill(i_img *im, int seedx, int seedy, i_fill_t *fill) {
1225   int bxmin, bxmax, bymin, bymax;
1226   struct i_bitmap *btm;
1227   int x, y;
1228   int start;
1229
1230   btm = i_flood_fill_low(im, seedx, seedy, &bxmin, &bxmax, &bymin, &bymax);
1231
1232   if (im->bits == i_8_bits && fill->fill_with_color) {
1233     i_color *line = mymalloc(sizeof(i_color) * (bxmax - bxmin));
1234
1235     for(y=bymin;y<=bymax;y++) {
1236       x = bxmin;
1237       while (x < bxmax) {
1238         while (x < bxmax && !btm_test(btm, x, y)) {
1239           ++x;
1240         }
1241         if (btm_test(btm, x, y)) {
1242           start = x;
1243           while (x < bxmax && btm_test(btm, x, y)) {
1244             ++x;
1245           }
1246           if (fill->combines)
1247             i_glin(im, start, x, y, line);
1248           (fill->fill_with_color)(fill, start, y, x-start, im->channels, line);
1249           i_plin(im, start, x, y, line);
1250         }
1251       }
1252     }
1253     myfree(line);
1254   }
1255   else {
1256     i_fcolor *line = mymalloc(sizeof(i_fcolor) * (bxmax - bxmin));
1257
1258     for(y=bymin;y<=bymax;y++) {
1259       x = bxmin;
1260       while (x < bxmax) {
1261         while (x < bxmax && !btm_test(btm, x, y)) {
1262           ++x;
1263         }
1264         if (btm_test(btm, x, y)) {
1265           start = x;
1266           while (x < bxmax && btm_test(btm, x, y)) {
1267             ++x;
1268           }
1269           if (fill->combines)
1270             i_glinf(im, start, x, y, line);
1271           (fill->fill_with_fcolor)(fill, start, y, x-start, im->channels, line);
1272           i_plinf(im, start, x, y, line);
1273         }
1274       }
1275     }
1276     myfree(line);
1277   }
1278
1279   btm_destroy(btm);
1280 }