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