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
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557 /* This should be moved into a seperate file? */
 558
 559 /* This is the truncation used:
 560
 561    a double is multiplied by 16 and then truncated.
 562    This means that 0 -> 0
 563    So a triangle of (0,0) (10,10) (10,0) Will look like it's
 564    not filling the (10,10) point nor the (10,0)-(10,10)  line segment
 565
 566 */
 567
 568
 569
 570
 571 #define IMTRUNC(x) ((int)(x*16))
 572
 573
 574 /*
 575 typedef struct {
 576   short ms,ls;
 577 } pcord;
 578 */
 579
 580 typedef int pcord;
 581
 582 struct p_point {
 583   int n;
 584   pcord x,y;
 585 };
 586
 587 struct p_line  {
 588   int n;
 589   pcord x1,y1;
 590   pcord x2,y2;
 591   pcord miny,maxy;
 592 };
 593
 594 struct p_slice {
 595   int n;
 596   double x;
 597 };
 598
 599 int
 600 p_compy(const struct p_point *p1, const struct p_point *p2) {
 601   if (p1->y > p2->y) return 1;
 602   if (p1->y < p2->y) return -1;
 603   return 0;
 604 }
 605
 606 int
 607 p_compx(const struct p_slice *p1, const struct p_slice *p2) {
 608   if (p1->x > p2->x) return 1;
 609   if (p1->x < p2->x) return -1;
 610   return 0;
 611 }
 612
 613 /* Change this to int? and round right goddamn it! */
 614
 615 double
 616 p_eval_aty(struct p_line *l,pcord y) {
 617   int t;
 618   t=l->y2-l->y1;
 619   if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
 620   return (l->x1+l->x2)/2.0;
 621 }
 622
 623 double
 624 p_eval_atx(struct p_line *l,pcord x) {
 625   int t;
 626   t=l->x2-l->x1;
 627   if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
 628   return (l->y1+l->y2)/2.0;
 629 }
 630
 631
 632 /* Algorithm to count the pixels covered by line going through pixel (x,y)
 633    in coarse coords.
 634 */
 635
 636 /*
 637 static int
 638 p_eval_coverage(struct p_line *l, int lc, int x, pcord y1, pcord y2) {
 639
 640   return 0;
 641 }
 642 */
 643
 644
 645 /* Antialiasing polygon algorithm
 646    specs:
 647      1. only nice polygons - no crossovers
 648      2. 1/16 pixel resolution # previously - floating point co-ordinates
 649      3. full antialiasing ( complete spectrum of blends )
 650      4. uses hardly any memory
 651      5. no subsampling phase
 652
 653    For each interval we must:
 654      1. find which lines are in it
 655      2. order the lines from in increasing x order.
 656         since we are assuming no crossovers it is sufficent
 657         to check a single point on each line.
 658 */
 659
 660 /*
 661   Terms:
 662
 663     1. Interval:  A vertical segment in which no lines cross nor end.
 664     2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
 665     3. Slice:     A start stop line pair.
 666
 667  */
 668
 669 /* Templine logic:
 670
 671    The variable tempflush describes if there is anything in the templine array or not.
 672
 673    if tempflush is 0 then the array is clean.
 674    if tempflush is 1 then the array contains a partial filled scanline
 675
 676  */
 677
 678 /* Rendering of a single start stop pair:
 679
 680 ?? REWRITE
 681
 682    The rendering is split in three parts
 683    1. From the first start pixel to the first stop pixel
 684    2. Area from the first end pixel to the last start pixel
 685    3. Area from the first end pixel to the last start pixel
 686
 687  */
 688
 689
 690 void
 691 i_poly_aa(i_img *im,int l,double *x,double *y,i_color *val) {
 692   int i,k;                      /* Index variables */
 693   int clc;                      /* Index of next item on interval linelist */
 694   int tx;                       /* Coarse x coord within a scanline */
 695   pcord miny,maxy;              /* Min and max values of the current slice in the subcord system */
 696   pcord minacy,maxacy;          /* Min and max values of the current scanline bounded by the slice
 697                                    in the subcord system */
 698   int cscl;                     /* Current scanline */
 699   pcord cc;                     /* Current vertical centerpoint of interval */
 700   int mt1,mt2;
 701   int minsx,minex,maxsx,maxex;  /* The horizontal stretches of the lines beloning to the current slice within a scanline */
 702   int *templine;                /* Line accumulator */
 703
 704   struct p_point *pset;         /* List of points in polygon */
 705   struct p_line *lset;          /* List of lines in polygon */
 706   struct p_slice *tllist;       /* List of slices */
 707
 708   i_color red,blue,yellow;
 709   red.rgb.r=255;
 710   red.rgb.g=0;
 711   red.rgb.b=0;
 712
 713   blue.rgb.r=0;
 714   blue.rgb.g=0;
 715   blue.rgb.b=255;
 716
 717   yellow.rgb.r=255;
 718   yellow.rgb.g=255;
 719   yellow.rgb.b=255;
 720
 721   if ( (pset=mymalloc(sizeof(struct p_point)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 722   if ( (lset=mymalloc(sizeof(struct p_line)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 723   if ( (tllist=mymalloc(sizeof(struct p_slice)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 724   if ( (templine=mymalloc(sizeof(int)*im->xsize)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
 725
 726   /* insert the lines into the line list */
 727
 728   for(i=0;i<l;i++) {
 729     pset[i].n=i;
 730     pset[i].x=IMTRUNC(x[i]);
 731     pset[i].y=IMTRUNC(y[i]);
 732     lset[i].n=i;
 733     lset[i].x1=IMTRUNC(x[i]);
 734     lset[i].y1=IMTRUNC(y[i]);
 735     lset[i].x2=IMTRUNC(x[(i+1)%l]);
 736     lset[i].y2=IMTRUNC(y[(i+1)%l]);
 737     lset[i].miny=min(lset[i].y1,lset[i].y2);
 738     lset[i].maxy=max(lset[i].y1,lset[i].y2);
 739   }
 740
 741   qsort(pset,l,sizeof(struct p_point),(int(*)(const void *,const void *))p_compy);
 742
 743   printf("post point list (sorted in ascending y order)\n");
 744   for(i=0;i<l;i++) {
 745     printf("%d [ %d ] %d %d\n",i,pset[i].n,pset[i].x,pset[i].y);
 746   }
 747
 748   printf("line list\n");
 749   for(i=0;i<l;i++) {
 750     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);
 751   }
 752
 753   printf("MAIN LOOP\n\n");
 754
 755   /* Zero templine buffer */
 756   /* Templine buffer flushed everytime a scan line ends */
 757   for(i=0;i<im->xsize;i++) templine[i]=0;
 758
 759
 760   /* loop on intervals */
 761   for(i=0;i<l-1;i++) {
 762     cc=(pset[i].y+pset[i+1].y)/2;
 763     printf("current slice is: %d to %d ( cpoint %d )\n",pset[i].y,pset[i+1].y,cc);
 764     clc=0;
 765
 766     /* stuff this in a function ?? */
 767
 768     /* Check what lines belong to interval */
 769     for(k=0;k<l;k++) {
 770       printf("checking line: %d [ %d ] (%d , %d) -> (%d, %d) yspan ( %d , %d )",
 771              k,lset[k].n,lset[k].x1,lset[k].y1,lset[k].x2,lset[k].y2,lset[k].miny,lset[k].maxy);
 772       if (cc >= lset[k].miny && cc <=  lset[k].maxy) {
 773         if (lset[k].miny == lset[k].maxy) printf(" HORIZONTAL - skipped\n");
 774         else {
 775           printf(" INSIDE\n");
 776           tllist[clc].x=p_eval_aty(&lset[k],cc);
 777           tllist[clc++].n=k;
 778         }
 779       } else printf(" OUTSIDE\n");
 780     }
 781
 782     /*
 783        at this point a table of pixels that need special care should
 784        be generated from the line list - it should be ordered so that only
 785        one needs to be checked - options: rendering to a list then order - or
 786        rendering in the right order might be possible to do nicely with the
 787        following heuristic:
 788
 789        1. Draw leftmost pixel for this line
 790        2. If preceeding pixel was occupied check next one else go to 1 again.
 791     */
 792
 793     printf("lines in current interval:");
 794     for(k=0;k<clc;k++) printf("  %d (%.2f)",tllist[k].n,tllist[k].x);
 795     printf("\n");
 796
 797     /* evaluate the lines in the middle of the slice */
 798
 799     printf("Sort lines left to right within interval\n");
 800     qsort(tllist,clc,sizeof(struct p_slice),(int(*)(const void *,const void *))p_compx);
 801
 802     printf("sorted lines in interval - output:");
 803     for(k=0;k<clc;k++) printf(" %d",tllist[k].n);
 804     printf("\n");
 805
 806     miny=pset[i].y;
 807     maxy=pset[i+1].y;
 808
 809     /* iterate over scanlines */
 810     for(cscl=(miny)/16;cscl<=maxy/16;cscl++) {
 811       minacy=max(miny,cscl*16);
 812       maxacy=min(maxy,cscl*16+15);
 813
 814       printf("Scanline bound %d - %d\n",minacy, maxacy);
 815
 816       /* iterate over line pairs (slices) within interval */
 817       for(k=0;k<clc-1;k+=2) {
 818
 819         mt1=p_eval_aty(&lset[tllist[k].n],minacy);      /* upper corner */
 820         mt2=p_eval_aty(&lset[tllist[k].n],maxacy);      /* lower corner */
 821         minsx=min(mt1,mt2);
 822         minex=max(mt1,mt2);
 823         mt1=p_eval_aty(&lset[tllist[k+1].n],minacy);    /* upper corner */
 824         mt2=p_eval_aty(&lset[tllist[k+1].n],maxacy);    /* lower corner */
 825         maxsx=min(mt1,mt2);
 826         maxex=max(mt1,mt2);
 827
 828         printf("minsx: %d minex: %d\n",minsx,minex);
 829         printf("maxsx: %d maxex: %d\n",maxsx,maxex);
 830
 831         if (minex/16<maxsx/16) printf("Scan slice is simple!\n");
 832         else printf("Scan slice is complicated!\n");
 833
 834         if (minsx/16 == minex/16) { /* The line starts and ends in the same pixel */
 835           printf("Low slant start pixel\n");
 836           templine[minsx/16]=(maxacy-minacy+1)*(minex-minsx+1)/2+((minex | 0xF)-minex)*(maxacy-minacy+1);
 837         } else {
 838           for(tx=minsx/16;tx<minex/16+1;tx++) {
 839             int minx,maxx,minxy,maxxy;
 840             minx=max(minsx,  tx*16   );
 841             maxx=min(minex,  tx*16+15);
 842
 843             if (minx == maxx) {
 844               templine[tx]=(maxacy-minacy+1);
 845             } else {
 846
 847               minxy=p_eval_atx(&lset[tllist[k].n], minx);
 848               maxxy=p_eval_atx(&lset[tllist[k].n], maxx);
 849
 850               templine[tx]+=(abs(minxy-maxxy)+1)*(minex-minsx+1)/2; /* The triangle between the points */
 851               if (mt1 < mt2) { /* \ slant */
 852                 /* ((minex | 0xF)-minex)*(maxacy-minacy+1); FIXME: unfinished */
 853
 854
 855
 856               } else {
 857                 templine[tx]+=((minex | 0xF)-minex)*(maxacy-minacy+1);
 858               }
 859
 860             }
 861           }
 862         }
 863
 864         for(tx=maxsx/16;tx<maxex/16+1;tx++) templine[tx]+=16*(maxacy-minacy+1);
 865
 866         /*      for(tx=minex/16+1;tx<maxsx/16;tx++) 0; */
 867
 868
 869         printf("line %d: painting  %d - %d\n",cscl,minex/16+1,maxsx/16);
 870         if ( (minacy != cscl*16) || (maxacy != cscl*16+15) ) {
 871           for(tx=minsx/16;tx<maxex/16+1;tx++) {
 872             i_ppix(im,tx,cscl,&yellow);
 873           }
 874         }
 875         else {
 876           for(tx=minsx/16;tx<minex/16+1;tx++) i_ppix(im,tx,cscl,&red);
 877           for(tx=maxsx/16;tx<maxex/16+1;tx++) i_ppix(im,tx,cscl,&blue);
 878           for(tx=minex/16+1;tx<maxsx/16;tx++) i_ppix(im,tx,cscl,val);
 879         }
 880
 881       } /* Slices */
 882     } /* Scanlines */
 883   } /* Intervals */
 884 } /* Function */
 885
 886
 887
 888
 889
 890
 891
 892 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in
 893    graphics gems I */
 894
 895 /*
 896 struct stc {
 897   int mylx,myrx;
 898   int dadlx,dadrx;
 899   int myy;
 900   int mydirection;
 901 };
 902
 903 Not used code???
 904 */
 905
 906
 907 struct stack_element {
 908   int myLx,myRx;
 909   int dadLx,dadRx;
 910   int myY;
 911   int myDirection;
 912 };
 913
 914
 915 /* create the link data to put push onto the stack */
 916
 917 static
 918 struct stack_element*
 919 crdata(int left,int right,int dadl,int dadr,int y, int dir) {
 920   struct stack_element *ste;
 921   ste=(struct stack_element*)mymalloc(sizeof(struct stack_element));
 922   ste->myLx=left;
 923   ste->myRx=right;
 924   ste->dadLx=dadl;
 925   ste->dadRx=dadr;
 926   ste->myY=y;
 927   ste->myDirection=dir;
 928   return ste;
 929 }
 930
 931 /* i_ccomp compares two colors and gives true if they are the same */
 932
 933 static int
 934 i_ccomp(i_color *val1,i_color *val2,int ch) {
 935   int i;
 936   for(i=0;i<ch;i++) if (val1->channel[i] !=val2->channel[i]) return 0;
 937   return 1;
 938 }
 939
 940
 941 static int
 942 i_lspan(i_img *im,int seedx,int seedy,i_color *val) {
 943   i_color cval;
 944   while(1) {
 945     if (seedx-1 < 0) break;
 946     i_gpix(im,seedx-1,seedy,&cval);
 947     if (!i_ccomp(val,&cval,im->channels)) break;
 948     seedx--;
 949   }
 950   return seedx;
 951 }
 952
 953 static int
 954 i_rspan(i_img *im,int seedx,int seedy,i_color *val) {
 955   i_color cval;
 956   while(1) {
 957     if (seedx+1 > im->xsize-1) break;
 958     i_gpix(im,seedx+1,seedy,&cval);
 959     if (!i_ccomp(val,&cval,im->channels)) break;
 960     seedx++;
 961   }
 962   return seedx;
 963 }
 964
 965 /* Macro to create a link and push on to the list */
 966
 967 #define ST_PUSH(left,right,dadl,dadr,y,dir) { struct stack_element *s=crdata(left,right,dadl,dadr,y,dir); llist_push(st,&s);}
 968
 969 /* pops the shadow on TOS into local variables lx,rx,y,direction,dadLx and dadRx */
 970 /* No overflow check! */
 971
 972 #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); }
 973
 974 #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); }
 975
 976 #define SET(x,y) btm_set(btm,x,y);
 977
 978 #define INSIDE(x,y) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),i_ccomp(&val,&cval,channels)  ) ))
 979
 980 void
 981 i_flood_fill(i_img *im,int seedx,int seedy,i_color *dcol) {
 982
 983   int lx,rx;
 984   int y;
 985   int direction;
 986   int dadLx,dadRx;
 987
 988   int wasIn=0;
 989   int x=0;
 990
 991   /*  int tx,ty; */
 992
 993   int bxmin=seedx,bxmax=seedx,bymin=seedy,bymax=seedy;
 994
 995   struct llist *st;
 996   struct i_bitmap *btm;
 997
 998   int channels,xsize,ysize;
 999   i_color cval,val;
1000
1001   channels=im->channels;
1002   xsize=im->xsize;
1003   ysize=im->ysize;
1004
1005   btm=btm_new(xsize,ysize);
1006   st=llist_new(100,sizeof(struct stack_element*));
1007
1008   /* Get the reference color */
1009   i_gpix(im,seedx,seedy,&val);
1010
1011   /* Find the starting span and fill it */
1012   lx=i_lspan(im,seedx,seedy,&val);
1013   rx=i_rspan(im,seedx,seedy,&val);
1014
1015   /* printf("span: %d %d \n",lx,rx); */
1016
1017   for(x=lx;x<=rx;x++) SET(x,seedy);
1018
1019   ST_PUSH(lx,rx,lx,rx,seedy+1,1);
1020   ST_PUSH(lx,rx,lx,rx,seedy-1,-1);
1021
1022   while(st->count) {
1023     ST_POP();
1024
1025     if (y<0 || y>ysize-1) continue;
1026
1027     if (bymin > y) bymin=y; /* in the worst case an extra line */
1028     if (bymax < y) bymax=y;
1029
1030     /*     printf("start of scan - on stack : %d \n",st->count); */
1031
1032
1033     /*     printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction); */
1034
1035     /*
1036     printf(" ");
1037     for(tx=0;tx<xsize;tx++) printf("%d",tx%10);
1038     printf("\n");
1039     for(ty=0;ty<ysize;ty++) {
1040       printf("%d",ty%10);
1041       for(tx=0;tx<xsize;tx++) printf("%d",!!btm_test(btm,tx,ty));
1042       printf("\n");
1043     }
1044
1045     printf("y=%d\n",y);
1046     */
1047
1048
1049     x=lx+1;
1050     if ( (wasIn = INSIDE(lx,y)) ) {
1051       SET(lx,y);
1052       lx--;
1053       while(INSIDE(lx,y) && lx > 0) {
1054         SET(lx,y);
1055         lx--;
1056       }
1057     }
1058
1059     if (bxmin > lx) bxmin=lx;
1060
1061     while(x <= xsize-1) {
1062       /*  printf("x=%d\n",x); */
1063       if (wasIn) {
1064
1065         if (INSIDE(x,y)) {
1066           /* case 1: was inside, am still inside */
1067           SET(x,y);
1068         } else {
1069           /* case 2: was inside, am no longer inside: just found the
1070              right edge of a span */
1071           ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1072
1073           if (bxmax < x) bxmax=x;
1074
1075           wasIn=0;
1076         }
1077       } else {
1078         if (x>rx) goto EXT;
1079         if (INSIDE(x,y)) {
1080           SET(x,y);
1081           /* case 3: Wasn't inside, am now: just found the start of a new run */
1082           wasIn=1;
1083             lx=x;
1084         } else {
1085           /* case 4: Wasn't inside, still isn't */
1086         }
1087       }
1088       x++;
1089     }
1090   EXT: /* out of loop */
1091     if (wasIn) {
1092       /* hit an edge of the frame buffer while inside a run */
1093       ST_STACK(direction,dadLx,dadRx,lx,(x-1),y);
1094       if (bxmax < x) bxmax=x;
1095     }
1096   }
1097
1098   /*   printf("lx=%d rx=%d dadLx=%d dadRx=%d y=%d direction=%d\n",lx,rx,dadLx,dadRx,y,direction);
1099        printf("bounding box: [%d,%d] - [%d,%d]\n",bxmin,bymin,bxmax,bymax); */
1100
1101   for(y=bymin;y<=bymax;y++) for(x=bxmin;x<=bxmax;x++) if (btm_test(btm,x,y)) i_ppix(im,x,y,dcol);
1102
1103   btm_destroy(btm);
1104   llist_destroy(st);
1105 }