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