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