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