add new comparison method rgb_difference that resembles arithmetical difference per...
[imager.git] / draw.c
diff --git a/draw.c b/draw.c
index b74fe2e..647c9d2 100644 (file)
--- a/draw.c
+++ b/draw.c
@@ -5,6 +5,8 @@
 #include "imageri.h"
 #include "imrender.h"
 #include <limits.h>
 #include "imageri.h"
 #include "imrender.h"
 #include <limits.h>
+#define NDEBUG
+#include <assert.h>
 
 int
 i_ppix_norm(i_img *im, i_img_dim x, i_img_dim y, i_color const *col) {
 
 int
 i_ppix_norm(i_img *im, i_img_dim x, i_img_dim y, i_color const *col) {
@@ -93,7 +95,10 @@ i_mmarray_cr(i_mmarray *ar,i_img_dim l) {
     exit(3);
   }
   ar->data=mymalloc(alloc_size); /* checked 5jul05 tonyc */
     exit(3);
   }
   ar->data=mymalloc(alloc_size); /* checked 5jul05 tonyc */
-  for(i=0;i<l;i++) { ar->data[i].max=-1; ar->data[i].min=MAXINT; }
+  for(i=0;i<l;i++) {
+    ar->data[i].max = -1;
+    ar->data[i].min = i_img_dim_MAX;
+  }
 }
 
 void
 }
 
 void
@@ -111,16 +116,18 @@ i_mmarray_add(i_mmarray *ar,i_img_dim x,i_img_dim y) {
     }
 }
 
     }
 }
 
-int
+i_img_dim
 i_mmarray_gmin(i_mmarray *ar,i_img_dim y) {
   if (y>-1 && y<ar->lines) return ar->data[y].min;
   else return -1;
 }
 
 i_mmarray_gmin(i_mmarray *ar,i_img_dim y) {
   if (y>-1 && y<ar->lines) return ar->data[y].min;
   else return -1;
 }
 
-int
+i_img_dim
 i_mmarray_getm(i_mmarray *ar,i_img_dim y) {
 i_mmarray_getm(i_mmarray *ar,i_img_dim y) {
-  if (y>-1 && y<ar->lines) return ar->data[y].max;
-  else return MAXINT;
+  if (y>-1 && y<ar->lines)
+    return ar->data[y].max;
+  else
+    return i_img_dim_MAX;
 }
 
 #if 0
 }
 
 #if 0
@@ -176,14 +183,13 @@ i_mmarray_info(i_mmarray *ar) {
 static void
 i_arc_minmax(i_int_hlines *hlines,i_img_dim x,i_img_dim y, double rad,float d1,float d2) {
   i_mmarray dot;
 static void
 i_arc_minmax(i_int_hlines *hlines,i_img_dim x,i_img_dim y, double rad,float d1,float d2) {
   i_mmarray dot;
-  double f,fx,fy;
+  double f;
   i_img_dim x1,y1;
 
   i_mmarray_cr(&dot, hlines->limit_y);
 
   x1=(i_img_dim)(x+0.5+rad*cos(d1*PI/180.0));
   y1=(i_img_dim)(y+0.5+rad*sin(d1*PI/180.0));
   i_img_dim x1,y1;
 
   i_mmarray_cr(&dot, hlines->limit_y);
 
   x1=(i_img_dim)(x+0.5+rad*cos(d1*PI/180.0));
   y1=(i_img_dim)(y+0.5+rad*sin(d1*PI/180.0));
-  fx=(float)x1; fy=(float)y1;
 
   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
   i_arcdraw(x, y, x1, y1, &dot);
 
   /*  printf("x1: %d.\ny1: %d.\n",x1,y1); */
   i_arcdraw(x, y, x1, y1, &dot);
@@ -415,85 +421,30 @@ i_arc_aa_cfill(i_img *im, double x, double y, double rad, double d1, double d2,
   myfree(yvals);
 }
 
   myfree(yvals);
 }
 
-/* Temporary AA HACK */
-
-
 typedef i_img_dim frac;
 static  frac float_to_frac(double x) { return (frac)(0.5+x*16.0); }
 
 typedef i_img_dim frac;
 static  frac float_to_frac(double x) { return (frac)(0.5+x*16.0); }
 
-static 
-void
-polar_to_plane(double cx, double cy, float angle, double radius, frac *x, frac *y) {
-  *x = float_to_frac(cx+radius*cos(angle));
-  *y = float_to_frac(cy+radius*sin(angle));
-}
-
-static
-void
-make_minmax_list(pIMCTX, i_mmarray *dot, double x, double y, double radius) {
-  float angle = 0.0;
-  float astep = radius>0.1 ? .5/radius : 10;
-  frac cx, cy, lx, ly, sx, sy;
-
-  im_log((aIMCTX, 1, "make_minmax_list(dot %p, x %.2f, y %.2f, radius %.2f)\n", dot, x, y, radius));
+typedef void
+(*flush_render_t)(i_img *im, i_img_dim l, i_img_dim r, i_img_dim y, const i_sample_t *cover, void *ctx);
 
 
-  polar_to_plane(x, y, angle, radius, &sx, &sy);
-  
-  for(angle = 0.0; angle<361; angle +=astep) {
-    lx = sx; ly = sy;
-    polar_to_plane(x, y, angle, radius, &cx, &cy);
-    sx = cx; sy = cy;
-
-    if (fabs(cx-lx) > fabs(cy-ly)) {
-      int ccx, ccy;
-      if (lx>cx) { 
-       ccx = lx; lx = cx; cx = ccx; 
-       ccy = ly; ly = cy; cy = ccy; 
-      }
-
-      for(ccx=lx; ccx<=cx; ccx++) {
-       ccy = ly + ((cy-ly)*(ccx-lx))/(cx-lx);
-       i_mmarray_add(dot, ccx, ccy);
-      }
-    } else {
-      int ccx, ccy;
+static void
+i_circle_aa_low(i_img *im, double x, double y, double rad, flush_render_t r, void *ctx);
 
 
-      if (ly>cy) { 
-       ccy = ly; ly = cy; cy = ccy; 
-       ccx = lx; lx = cx; cx = ccx; 
-      }
-      
-      for(ccy=ly; ccy<=cy; ccy++) {
-       if (cy-ly) ccx = lx + ((cx-lx)*(ccy-ly))/(cy-ly); else ccx = lx;
-       i_mmarray_add(dot, ccx, ccy);
-      }
-    }
-  }
-}
+static void
+scanline_flush_color(i_img *im, i_img_dim l, i_img_dim y, i_img_dim width, const i_sample_t *cover, void *ctx);
 
 
-/* Get the number of subpixels covered */
+static void
+scanline_flush_fill(i_img *im, i_img_dim l, i_img_dim y, i_img_dim width, const i_sample_t *cover, void *ctx);
 
 
-static
-int
-i_pixel_coverage(i_mmarray *dot, i_img_dim x, i_img_dim y) {
-  frac minx = x*16;
-  frac maxx = minx+15;
-  frac cy;
-  int cnt = 0;
-  
-  for(cy=y*16; cy<(y+1)*16; cy++) {
-    frac tmin = dot->data[cy].min;
-    frac tmax = dot->data[cy].max;
+typedef struct {
+  i_render r;
+  i_color c;
+} flush_color_t;
 
 
-    if (tmax == -1 || tmin > maxx || tmax < minx) continue;
-    
-    if (tmin < minx) tmin = minx;
-    if (tmax > maxx) tmax = maxx;
-    
-    cnt+=1+tmax-tmin;
-  }
-  return cnt;
-}
+typedef struct {
+  i_render r;
+  i_fill_t *fill;
+} flush_fill_t;
 
 /*
 =item i_circle_aa(im, x, y, rad, color)
 
 /*
 =item i_circle_aa(im, x, y, rad, color)
@@ -506,51 +457,183 @@ color.
 
 =cut
 */
 
 =cut
 */
+
 void
 i_circle_aa(i_img *im, double x, double y, double rad, const i_color *val) {
 void
 i_circle_aa(i_img *im, double x, double y, double rad, const i_color *val) {
-  i_mmarray dot;
-  i_color temp;
-  i_img_dim ly;
-  dIMCTXim(im);
+  flush_color_t fc;
+
+  fc.c = *val;
+  i_render_init(&fc.r, im, rad * 2 + 1);
+
+  i_circle_aa_low(im, x, y, rad, scanline_flush_color, &fc);
+
+  i_render_done(&fc.r);
+}
 
 
-  im_log((aIMCTX, 1, "i_circle_aa(im %p, centre(" i_DFp "), rad %.2f, val %p)\n",
-         im, i_DFcp(x, y), rad, val));
+/*
+=item i_circle_aa_fill(im, x, y, rad, fill)
 
 
-  i_mmarray_cr(&dot,16*im->ysize);
-  make_minmax_list(aIMCTX, &dot, x, y, rad);
+=category Drawing
+=synopsis i_circle_aa_fill(im, 50, 50, 45, fill);
 
 
-  for(ly = 0; ly<im->ysize; ly++) {
-    int ix, cy, minx = INT_MAX, maxx = INT_MIN;
+Anti-alias fills a circle centered at (x,y) for radius I<rad> with
+fill.
 
 
-    /* Find the left/rightmost set subpixels */
-    for(cy = 0; cy<16; cy++) {
-      frac tmin = dot.data[ly*16+cy].min;
-      frac tmax = dot.data[ly*16+cy].max;
-      if (tmax == -1) continue;
+=cut
+*/
 
 
-      if (minx > tmin) minx = tmin;
-      if (maxx < tmax) maxx = tmax;
+void
+i_circle_aa_fill(i_img *im, double x, double y, double rad, i_fill_t *fill) {
+  flush_fill_t ff;
+
+  ff.fill = fill;
+  i_render_init(&ff.r, im, rad * 2 + 1);
+
+  i_circle_aa_low(im, x, y, rad, scanline_flush_fill, &ff);
+
+  i_render_done(&ff.r);
+}
+
+static void
+i_circle_aa_low(i_img *im, double x, double y, double rad, flush_render_t r,
+               void *ctx) {
+  i_color temp;
+  i_img_dim ly;
+  dIMCTXim(im);
+  double ceil_rad = ceil(rad);
+  i_img_dim first_row = floor(y) - ceil_rad;
+  i_img_dim last_row = ceil(y) + ceil_rad;
+  i_img_dim first_col = floor(x) - ceil_rad;
+  i_img_dim last_col = ceil(x) + ceil_rad;
+  double r_sqr = rad * rad;
+  i_img_dim max_width = 2 * ceil(rad) + 1;
+  unsigned char *coverage = NULL;
+  size_t coverage_size;
+  int sub;
+
+  im_log((aIMCTX, 1, "i_circle_aa_low(im %p, centre(" i_DFp "), rad %.2f, r %p, ctx %p)\n",
+         im, i_DFcp(x, y), rad, r, ctx));
+
+  if (first_row < 0)
+    first_row = 0;
+  if (last_row > im->ysize-1)
+    last_row = im->ysize - 1;
+  if (first_col < 0)
+    first_col = 0;
+  if (last_col > im->xsize-1)
+    last_col = im->xsize - 1;
+
+  if (rad <= 0 || last_row < first_row || last_col < first_col) {
+    /* outside the image */
+    return;
+  }
+
+  coverage_size = max_width;
+  coverage = mymalloc(coverage_size);
+
+  for(ly = first_row; ly < last_row; ly++) {
+    frac min_frac_x[16];
+    frac max_frac_x[16];
+    i_img_dim min_frac_left_x = 16 *(ceil(x) + ceil(rad));
+    i_img_dim max_frac_left_x = -1;
+    i_img_dim min_frac_right_x = 16 * (floor(x) - ceil(rad));
+    i_img_dim max_frac_right_x = -1;
+    /* reset work_y each row so the error doesn't build up */
+    double work_y = ly;
+    double dy, dy_sqr;
+      
+    for (sub = 0; sub < 16; ++sub) {
+      work_y += 1.0 / 16.0;
+      dy = work_y - y;
+      dy_sqr = dy * dy;
+
+      if (dy_sqr < r_sqr) {
+       double dx = sqrt(r_sqr - dy_sqr);
+       double left_x = x - dx;
+       double right_x = x + dx;
+       frac frac_left_x = float_to_frac(left_x);
+       frac frac_right_x = float_to_frac(right_x);
+
+       if (frac_left_x < min_frac_left_x)
+         min_frac_left_x = frac_left_x;
+       if (frac_left_x > max_frac_left_x)
+         max_frac_left_x = frac_left_x;
+       if (frac_right_x < min_frac_right_x)
+         min_frac_right_x = frac_right_x;
+       if (frac_right_x > max_frac_right_x)
+         max_frac_right_x = frac_right_x;
+       min_frac_x[sub] = frac_left_x;
+       max_frac_x[sub] = frac_right_x;
+      }
+      else {
+       min_frac_x[sub] = max_frac_x[sub] = 0;
+       max_frac_left_x = im->xsize * 16;
+       min_frac_right_x = -1;
+      }
     }
 
     }
 
-    if (maxx == INT_MIN) continue; /* no work to be done for this row of pixels */
-
-    minx /= 16;
-    maxx /= 16;
-    for(ix=minx; ix<=maxx; ix++) {
-      int cnt = i_pixel_coverage(&dot, ix, ly);
-      if (cnt>255) cnt = 255;
-      if (cnt) { /* should never be true */
-       int ch;
-       float ratio = (float)cnt/255.0;
-       i_gpix(im, ix, ly, &temp);
-       for(ch=0;ch<im->channels; ch++) temp.channel[ch] = (unsigned char)((float)val->channel[ch]*ratio + (float)temp.channel[ch]*(1.0-ratio));
-       i_ppix(im, ix, ly, &temp);
+    if (min_frac_left_x != -1) {
+      /* something to draw on this line */
+      i_img_dim min_x = (min_frac_left_x / 16);
+      i_img_dim max_x = (max_frac_right_x + 15) / 16;
+      i_img_dim left_solid = (max_frac_left_x + 15) / 16;
+      i_img_dim right_solid = min_frac_right_x / 16;
+      i_img_dim work_x;
+      i_img_dim frac_work_x;
+      i_sample_t *cout = coverage;
+
+      for (work_x = min_x, frac_work_x = min_x * 16;
+          work_x <= max_x;
+          ++work_x, frac_work_x += 16) {
+       if (work_x <= left_solid || work_x >= right_solid) {
+         int pix_coverage = 0;
+         int ch;
+         double ratio;
+         i_img_dim frac_work_right = frac_work_x + 16;
+         for (sub = 0; sub < 16; ++sub) {
+           frac pix_left = min_frac_x[sub];
+           frac pix_right = max_frac_x[sub];
+           if (pix_left < pix_right
+               && pix_left < frac_work_right
+               && pix_right >= frac_work_x) {
+             if (pix_left < frac_work_x)
+               pix_left = frac_work_x;
+             if (pix_right > frac_work_right)
+               pix_right = frac_work_right;
+             pix_coverage += pix_right - pix_left;
+           }
+         }
+
+         assert(pix_coverage <= 256);
+         *cout++ = pix_coverage * 255 / 256;
+       }
+       else {
+         /* full coverage */
+         *cout++ = 255;
+       }
       }
       }
+      r(im, min_x, ly, max_x - min_x + 1, coverage, ctx);
     }
   }
     }
   }
-  i_mmarray_dst(&dot);
+
+  myfree(coverage);
+}
+
+static void
+scanline_flush_color(i_img *im, i_img_dim x, i_img_dim y, i_img_dim width, const unsigned char *cover, void *ctx) {
+  flush_color_t *fc = ctx;
+
+  i_render_color(&fc->r, x, y, width, cover, &fc->c);
+}
+
+static void
+scanline_flush_fill(i_img *im, i_img_dim x, i_img_dim y, i_img_dim width, const unsigned char *cover, void *ctx) {
+  flush_fill_t *ff = ctx;
+
+  i_render_fill(&ff->r, x, y, width, cover, ff->fill);
 }
 
 }
 
+
 /*
 =item i_circle_out(im, x, y, r, col)
 
 /*
 =item i_circle_out(im, x, y, r, col)
 
@@ -640,7 +723,7 @@ i_circle_out(i_img *im, i_img_dim xc, i_img_dim yc, i_img_dim r,
 Convert an angle in degrees into an angle measure we can generate
 simply from the numbers we have when drawing the circle.
 
 Convert an angle in degrees into an angle measure we can generate
 simply from the numbers we have when drawing the circle.
 
-=back
+=cut
 */
 
 static i_img_dim
 */
 
 static i_img_dim
@@ -1684,10 +1767,36 @@ i_rspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpf
   return seedx;
 }
 
   return seedx;
 }
 
+#ifdef DEBUG_FLOOD_FILL
+
+#define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir) \
+  fprintf(stderr, "push(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
+         i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
+
+#define ST_POP_NOTE(left, right, dadl, dadr, y, dir) \
+  fprintf(stderr, "popped(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
+         i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
+
+#define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)                 \
+  fprintf(stderr, "stack(left %" i_DF ", right %" i_DF ", dadleft %" i_DF  ", dadright %" i_DF ", y %" i_DF ", dir %d, line %d)\n", \
+         i_DFc(left), i_DFc(right), i_DFc(dadl), i_DFc(dadr), i_DFc(y), (dir), __LINE__)
+
+#else
+
+#define ST_PUSH_NOTE(left, right, dadl, dadr, y, dir)
+
+#define ST_POP_NOTE(left, right, dadl, dadr, y, dir)
+
+#define ST_STACK_NOTE(dadl, dadr, left, right, y, dir)
+
+#endif
+
+
 /* Macro to create a link and push on to the list */
 
 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
 /* Macro to create a link and push on to the list */
 
 #define ST_PUSH(left,right,dadl,dadr,y,dir) do {                 \
   struct stack_element *s = crdata(left,right,dadl,dadr,y,dir);  \
+  ST_PUSH_NOTE(left, right, dadl, dadr, y, dir);                \
   llist_push(st,&s);                                             \
 } while (0)
 
   llist_push(st,&s);                                             \
 } while (0)
 
@@ -1703,24 +1812,28 @@ i_rspan(i_img *im, i_img_dim seedx, i_img_dim seedy, i_color const *val, ff_cmpf
   dadRx     = s->dadRx;       \
   y         = s->myY;         \
   direction = s->myDirection; \
   dadRx     = s->dadRx;       \
   y         = s->myY;         \
   direction = s->myDirection; \
+  ST_POP_NOTE(lx, rx, dadLx, dadRx, y, direction);     \
   myfree(s);                  \
 } while (0)
 
 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
   i_img_dim pushrx = rx+1;                                              \
   i_img_dim pushlx = lx-1;                                              \
   myfree(s);                  \
 } while (0)
 
 #define ST_STACK(dir,dadLx,dadRx,lx,rx,y) do {                    \
   i_img_dim pushrx = rx+1;                                              \
   i_img_dim pushlx = lx-1;                                              \
+  ST_STACK_NOTE(lx, rx, dadLx, dadRx, y, dir);          \
   ST_PUSH(lx,rx,pushlx,pushrx,y+dir,dir);                         \
   if (rx > dadRx)                                                 \
     ST_PUSH(dadRx+1,rx,pushlx,pushrx,y-dir,-dir);                 \
   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);   \
+  if (lx < dadLx)                                              \
+    ST_PUSH(lx,dadLx-1,pushlx,pushrx,y-dir,-dir);   \
 } while (0)
 
 #define SET(x,y) btm_set(btm,x,y)
 
 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
 } while (0)
 
 #define SET(x,y) btm_set(btm,x,y)
 
 /* INSIDE returns true if pixel is correct color and we haven't set it before. */
-#define INSIDE(x,y, seed) ((!btm_test(btm,x,y) && ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
-
-
+#define INSIDE(x,y, seed) \
+  (assert((x) >= 0 && (x) < (im)->xsize && (y) >= 0 && (y) < (im)->ysize), \
+   (!btm_test(btm,x,y) && \
+     ( i_gpix(im,x,y,&cval),cmpfunc(seed,&cval,channels)  ) ))
 
 /* The function that does all the real work */
 
 
 /* The function that does all the real work */
 
@@ -1741,7 +1854,7 @@ i_flood_fill_low(i_img *im,i_img_dim seedx,i_img_dim seedy,
 
   int channels;
   i_img_dim xsize,ysize;
 
   int channels;
   i_img_dim xsize,ysize;
-  i_color cval;
+  i_color cval; /* used by the INSIDE() macro */
 
   channels = im->channels;
   xsize    = im->xsize;
 
   channels = im->channels;
   xsize    = im->xsize;
@@ -1786,6 +1899,8 @@ i_flood_fill_low(i_img *im,i_img_dim seedx,i_img_dim seedy,
        SET(lx,y);
        lx--;
       }
        SET(lx,y);
        lx--;
       }
+      /* lx should point at the left-most INSIDE() pixel */
+      ++lx;
     }
 
     if (bxmin > lx) bxmin = lx;
     }
 
     if (bxmin > lx) bxmin = lx;
@@ -2039,3 +2154,9 @@ cfill_from_btm(i_img *im, i_fill_t *fill, struct i_bitmap *btm,
   }
   i_render_done(&r);
 }
   }
   i_render_done(&r);
 }
+
+/*
+=back
+
+=cut
+*/