Finished antialiased polygon drawing routines.
authorArnar Mar Hrafnkelsson <addi@cpan.org>
Mon, 12 Nov 2001 07:11:58 +0000 (07:11 +0000)
committerArnar Mar Hrafnkelsson <addi@cpan.org>
Mon, 12 Nov 2001 07:11:58 +0000 (07:11 +0000)
Imager.pm
MANIFEST
Makefile.PL
draw.c
image.c
polygon.c [new file with mode: 0644]
t/t75polyaa.t

index cf80d8b..2bbc800 100644 (file)
--- a/Imager.pm
+++ b/Imager.pm
@@ -117,7 +117,7 @@ use Imager::Font;
                NF
 );
 
-@EXPORT=qw( 
+@EXPORT=qw(
           init_log
           i_list_formats
           i_has_format
@@ -1547,7 +1547,7 @@ sub transform2 {
     $Imager::ERRSTR = Imager::Expr::error();
     return;
   }
-  
+
   my $img = Imager->new();
   $img->{IMG} = i_transform2($opts->{width}, $opts->{height}, $code->code(),
                              $code->nregs(), $code->cregs(),
@@ -1556,7 +1556,7 @@ sub transform2 {
     $Imager::ERRSTR = Imager->_error_as_msg();
     return;
   }
-  
+
   return $img;
 }
 
@@ -2922,7 +2922,7 @@ This creates a green circle with its center at (200, 100) and has a
 radius of 20.
 
 Line:
-  $img->line(color=>$green, x1=10, x2=>100, 
+  $img->line(color=>$green, x1=>10, x2=>100,
                             y1=>20, y2=>50, antialias=>1 );
 
 That draws an antialiased line from (10,100) to (20,50).
index ab247b1..3173b16 100644 (file)
--- a/MANIFEST
+++ b/MANIFEST
@@ -10,6 +10,7 @@ color.c         Color translation and handling
 conv.c
 convert.c
 draw.c
+polygon.c
 draw.h
 fills.c         Generic fills
 map.c
index 01c8b30..cce7b9c 100644 (file)
@@ -59,8 +59,8 @@ $OSDEF  = "-DOS_$^O";
 if ($^O eq 'hpux')                { $OSLIBS .= ' -ldld'; }
 if (defined $Config{'d_dlsymun'}) { $OSDEF  .= ' -DDLSYMUN'; }
 
-@objs = qw(Imager.o draw.o image.o io.o iolayer.o log.o
-          gaussian.o conv.o pnm.o raw.o feat.o font.o
+@objs = qw(Imager.o draw.o polygon.o image.o io.o iolayer.o
+           log.o gaussian.o conv.o pnm.o raw.o feat.o font.o
           filters.o dynaload.o stackmach.o datatypes.o
           regmach.o trans2.o quant.o error.o convert.o
           map.o tags.o palimg.o maskimg.o img16.o rotate.o
diff --git a/draw.c b/draw.c
index 5ad73f1..0340c75 100644 (file)
--- a/draw.c
+++ b/draw.c
@@ -556,6 +556,14 @@ i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
 
 
 
+
+
+
+
+
+
+
+
 /* Flood fill 
 
    REF: Graphics Gems I. page 282+
@@ -574,329 +582,6 @@ i_bezier_multi(i_img *im,int l,double *x,double *y,i_color *val) {
 */
 
 
-
-
-#define IMTRUNC(x) ((int)(x*16))
-
-
-/*
-typedef struct {
-  short ms,ls;
-} pcord;
-*/
-
-typedef int pcord;
-
-struct p_point {
-  int n;
-  pcord x,y;
-};
-
-struct p_line  {
-  int n;
-  pcord x1,y1;
-  pcord x2,y2;
-  pcord miny,maxy;
-};
-
-struct p_slice {
-  int n;
-  double x;
-};
-
-int
-p_compy(const struct p_point *p1, const struct p_point *p2) {
-  if (p1->y > p2->y) return 1;
-  if (p1->y < p2->y) return -1;
-  return 0;
-}
-
-int
-p_compx(const struct p_slice *p1, const struct p_slice *p2) {
-  if (p1->x > p2->x) return 1;
-  if (p1->x < p2->x) return -1;
-  return 0;
-}
-
-/* Change this to int? and round right goddamn it! */
-
-double
-p_eval_aty(struct p_line *l,pcord y) {
-  int t;
-  t=l->y2-l->y1;
-  if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
-  return (l->x1+l->x2)/2.0;
-}
-
-double
-p_eval_atx(struct p_line *l,pcord x) {
-  int t;
-  t=l->x2-l->x1;
-  if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
-  return (l->y1+l->y2)/2.0;
-}
-
-
-/* Algorithm to count the pixels covered by line going through pixel (x,y)
-   in coarse coords.
-*/
-
-/*
-static int
-p_eval_coverage(struct p_line *l, int lc, int x, pcord y1, pcord y2) {
-
-  return 0;
-}
-*/
-
-
-/* Antialiasing polygon algorithm 
-   specs:
-     1. only nice polygons - no crossovers
-     2. 1/16 pixel resolution # previously - floating point co-ordinates
-     3. full antialiasing ( complete spectrum of blends )
-     4. uses hardly any memory
-     5. no subsampling phase
-
-   For each interval we must: 
-     1. find which lines are in it
-     2. order the lines from in increasing x order.
-        since we are assuming no crossovers it is sufficent
-        to check a single point on each line.
-*/
-
-/*
-  Terms:
-  
-    1. Interval:  A vertical segment in which no lines cross nor end.
-    2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
-    3. Slice:     A start stop line pair.
-  
- */
-
-/* Templine logic: 
-   
-   The variable tempflush describes if there is anything in the templine array or not.
-   
-   if tempflush is 0 then the array is clean.
-   if tempflush is 1 then the array contains a partial filled scanline
-   
- */
-
-/* Rendering of a single start stop pair:
-
-?? REWRITE
-   
-   The rendering is split in three parts
-   1. From the first start pixel to the first stop pixel
-   2. Area from the first end pixel to the last start pixel
-   3. Area from the first end pixel to the last start pixel
-
- */
-
-
-void
-i_poly_aa(i_img *im,int l,double *x,double *y,i_color *val) {
-  int i,k;                     /* Index variables */
-  int clc;                     /* Index of next item on interval linelist */
-  int tx;                      /* Coarse x coord within a scanline */
-  pcord miny,maxy;             /* Min and max values of the current slice in the subcord system */
-  pcord minacy,maxacy;         /* Min and max values of the current scanline bounded by the slice
-                                  in the subcord system */
-  int cscl;                    /* Current scanline */
-  pcord cc;                    /* Current vertical centerpoint of interval */
-  int mt1,mt2;
-  int minsx,minex,maxsx,maxex; /* The horizontal stretches of the lines beloning to the current slice within a scanline */
-  int *templine;               /* Line accumulator */
-
-  struct p_point *pset;                /* List of points in polygon */
-  struct p_line *lset;         /* List of lines in polygon */
-  struct p_slice *tllist;      /* List of slices */
-
-  i_color red,blue,yellow;
-  red.rgb.r=255;
-  red.rgb.g=0;
-  red.rgb.b=0;
-
-  blue.rgb.r=0;
-  blue.rgb.g=0;
-  blue.rgb.b=255;
-
-  yellow.rgb.r=255;
-  yellow.rgb.g=255;
-  yellow.rgb.b=255;
-  
-  if ( (pset=mymalloc(sizeof(struct p_point)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
-  if ( (lset=mymalloc(sizeof(struct p_line)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
-  if ( (tllist=mymalloc(sizeof(struct p_slice)*l)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
-  if ( (templine=mymalloc(sizeof(int)*im->xsize)) == NULL) { m_fatal(2,"malloc failed\n"); return; }
-
-  /* insert the lines into the line list */
-  
-  for(i=0;i<l;i++) {
-    pset[i].n=i;
-    pset[i].x=IMTRUNC(x[i]);
-    pset[i].y=IMTRUNC(y[i]);
-    lset[i].n=i;
-    lset[i].x1=IMTRUNC(x[i]);
-    lset[i].y1=IMTRUNC(y[i]);
-    lset[i].x2=IMTRUNC(x[(i+1)%l]);
-    lset[i].y2=IMTRUNC(y[(i+1)%l]);
-    lset[i].miny=min(lset[i].y1,lset[i].y2);
-    lset[i].maxy=max(lset[i].y1,lset[i].y2);
-  }
-  
-  qsort(pset,l,sizeof(struct p_point),(int(*)(const void *,const void *))p_compy);
-  
-  printf("post point list (sorted in ascending y order)\n");
-  for(i=0;i<l;i++) {
-    printf("%d [ %d ] %d %d\n",i,pset[i].n,pset[i].x,pset[i].y);
-  }
-  
-  printf("line list\n");
-  for(i=0;i<l;i++) {
-    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);
-  }
-
-  printf("MAIN LOOP\n\n");
-
-  /* Zero templine buffer */
-  /* Templine buffer flushed everytime a scan line ends */
-  for(i=0;i<im->xsize;i++) templine[i]=0;
-  
-
-  /* loop on intervals */
-  for(i=0;i<l-1;i++) {
-    cc=(pset[i].y+pset[i+1].y)/2;
-    printf("current slice is: %d to %d ( cpoint %d )\n",pset[i].y,pset[i+1].y,cc);
-    clc=0;
-
-    /* stuff this in a function ?? */
-
-    /* Check what lines belong to interval */
-    for(k=0;k<l;k++) {
-      printf("checking line: %d [ %d ] (%d , %d) -> (%d, %d) yspan ( %d , %d )",
-            k,lset[k].n,lset[k].x1,lset[k].y1,lset[k].x2,lset[k].y2,lset[k].miny,lset[k].maxy);
-      if (cc >= lset[k].miny && cc <=  lset[k].maxy) {
-       if (lset[k].miny == lset[k].maxy) printf(" HORIZONTAL - skipped\n");
-       else {
-         printf(" INSIDE\n"); 
-         tllist[clc].x=p_eval_aty(&lset[k],cc);
-         tllist[clc++].n=k;
-       }
-      } else printf(" OUTSIDE\n");
-    }
-    
-    /* 
-       at this point a table of pixels that need special care should
-       be generated from the line list - it should be ordered so that only
-       one needs to be checked - options: rendering to a list then order - or
-       rendering in the right order might be possible to do nicely with the
-       following heuristic:
-       
-       1. Draw leftmost pixel for this line
-       2. If preceeding pixel was occupied check next one else go to 1 again.
-    */
-    
-    printf("lines in current interval:");
-    for(k=0;k<clc;k++) printf("  %d (%.2f)",tllist[k].n,tllist[k].x);
-    printf("\n");
-    
-    /* evaluate the lines in the middle of the slice */
-    
-    printf("Sort lines left to right within interval\n");
-    qsort(tllist,clc,sizeof(struct p_slice),(int(*)(const void *,const void *))p_compx);
-    
-    printf("sorted lines in interval - output:");
-    for(k=0;k<clc;k++) printf(" %d",tllist[k].n);
-    printf("\n");
-    
-    miny=pset[i].y;
-    maxy=pset[i+1].y;
-
-    /* iterate over scanlines */
-    for(cscl=(miny)/16;cscl<=maxy/16;cscl++) {
-      minacy=max(miny,cscl*16);
-      maxacy=min(maxy,cscl*16+15);
-      
-      printf("Scanline bound %d - %d\n",minacy, maxacy);
-
-      /* iterate over line pairs (slices) within interval */
-      for(k=0;k<clc-1;k+=2) {
-
-       mt1=p_eval_aty(&lset[tllist[k].n],minacy);      /* upper corner */
-       mt2=p_eval_aty(&lset[tllist[k].n],maxacy);      /* lower corner */
-       minsx=min(mt1,mt2);
-       minex=max(mt1,mt2);
-       mt1=p_eval_aty(&lset[tllist[k+1].n],minacy);    /* upper corner */
-       mt2=p_eval_aty(&lset[tllist[k+1].n],maxacy);    /* lower corner */
-       maxsx=min(mt1,mt2);
-       maxex=max(mt1,mt2);
-
-       printf("minsx: %d minex: %d\n",minsx,minex);
-       printf("maxsx: %d maxex: %d\n",maxsx,maxex);
-       
-       if (minex/16<maxsx/16) printf("Scan slice is simple!\n");
-       else printf("Scan slice is complicated!\n");
-       
-       if (minsx/16 == minex/16) { /* The line starts and ends in the same pixel */
-         printf("Low slant start pixel\n");
-         templine[minsx/16]=(maxacy-minacy+1)*(minex-minsx+1)/2+((minex | 0xF)-minex)*(maxacy-minacy+1);
-       } else {
-         for(tx=minsx/16;tx<minex/16+1;tx++) {
-           int minx,maxx,minxy,maxxy;
-           minx=max(minsx,  tx*16   );
-           maxx=min(minex,  tx*16+15);
-
-           if (minx == maxx) {
-             templine[tx]=(maxacy-minacy+1);
-           } else {
-           
-             minxy=p_eval_atx(&lset[tllist[k].n], minx);
-             maxxy=p_eval_atx(&lset[tllist[k].n], maxx);
-             
-             templine[tx]+=(abs(minxy-maxxy)+1)*(minex-minsx+1)/2; /* The triangle between the points */
-             if (mt1 < mt2) { /* \ slant */
-               /* ((minex | 0xF)-minex)*(maxacy-minacy+1); FIXME: unfinished */
-               
-
-
-             } else {
-               templine[tx]+=((minex | 0xF)-minex)*(maxacy-minacy+1);
-             }
-             
-           }
-         }
-       }
-
-       for(tx=maxsx/16;tx<maxex/16+1;tx++) templine[tx]+=16*(maxacy-minacy+1);
-       
-       /*      for(tx=minex/16+1;tx<maxsx/16;tx++) 0; */
-       
-       
-       printf("line %d: painting  %d - %d\n",cscl,minex/16+1,maxsx/16);
-       if ( (minacy != cscl*16) || (maxacy != cscl*16+15) ) {
-         for(tx=minsx/16;tx<maxex/16+1;tx++) {
-           i_ppix(im,tx,cscl,&yellow);
-         }
-       }
-       else {
-         for(tx=minsx/16;tx<minex/16+1;tx++) i_ppix(im,tx,cscl,&red);
-         for(tx=maxsx/16;tx<maxex/16+1;tx++) i_ppix(im,tx,cscl,&blue);
-         for(tx=minex/16+1;tx<maxsx/16;tx++) i_ppix(im,tx,cscl,val);
-       }
-
-      } /* Slices */
-    } /* Scanlines */
-  } /* Intervals */
-} /* Function */
-
-
-
-
-
-
-
 /* Flood fill algorithm - based on the Ken Fishkins (pixar) gem in 
    graphics gems I */
 
diff --git a/image.c b/image.c
index 0478b98..8bad545 100644 (file)
--- a/image.c
+++ b/image.c
@@ -1342,7 +1342,7 @@ i_gpix_d(i_img *im, int x, int y, i_color *val) {
   int ch;
   if (x>-1 && x<im->xsize && y>-1 && y<im->ysize) {
     for(ch=0;ch<im->channels;ch++) 
-       val->channel[ch]=im->idata[(x+y*im->xsize)*im->channels+ch];
+      val->channel[ch]=im->idata[(x+y*im->xsize)*im->channels+ch];
     return 0;
   }
   for(ch=0;ch<im->channels;ch++) val->channel[ch] = 0;
diff --git a/polygon.c b/polygon.c
new file mode 100644 (file)
index 0000000..27d2980
--- /dev/null
+++ b/polygon.c
@@ -0,0 +1,594 @@
+#include "image.h"
+#include "draw.h"
+#include "log.h"
+
+
+#define IMTRUNC(x) ((int)((x)*16))
+
+#define coarse(x) ((x)/16)
+#define fine(x)   ((x)%16)
+
+#define POLY_DEB(x)
+
+
+
+typedef int pcord;
+
+typedef struct {
+  int n;
+  pcord x,y;
+} p_point;
+
+typedef struct {
+  int n;
+  pcord x1,y1;
+  pcord x2,y2;
+  pcord miny,maxy;
+  pcord minx,maxx;
+  int updown; /* -1 means down, 0 vertical, 1 up */
+} p_line;
+
+typedef struct {
+  int n;
+  double x;
+} p_slice;
+
+typedef struct {
+  int start;
+  int stop;
+} ss_pair;
+
+typedef struct {
+  int *line;           /* temporary buffer for scanline */
+  int linelen;         /* length of scanline */
+  ss_pair *ss_list;    /* list of start stop linepairs */
+  int ssnext;          /* index of the next pair to use */
+  int sslen;           /* maximum number of start stop pairs */
+} ss_scanline;
+
+
+
+
+
+
+
+
+static
+int
+p_compy(const p_point *p1, const p_point *p2) {
+  if (p1->y > p2->y) return 1;
+  if (p1->y < p2->y) return -1;
+  return 0;
+}
+
+static
+int
+p_compx(const p_slice *p1, const p_slice *p2) {
+  if (p1->x > p2->x) return 1;
+  if (p1->x < p2->x) return -1;
+  return 0;
+}
+
+/* Change this to int? and round right goddamn it! */
+
+static
+double
+p_eval_aty(p_line *l, pcord y) {
+  int t;
+  t=l->y2-l->y1;
+  if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
+  return (l->x1+l->x2)/2.0;
+}
+
+static
+double
+p_eval_atx(p_line *l, pcord x) {
+  int t;
+  t = l->x2-l->x1;
+  if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
+  return (l->y1+l->y2)/2.0;
+}
+
+static
+p_line *
+line_set_new(double *x, double *y, int l) {
+  int i;
+  p_line *lset = mymalloc(sizeof(p_line) * l);
+
+  for(i=0; i<l; i++) {
+    lset[i].n=i;
+    lset[i].x1 = IMTRUNC(x[i]);
+    lset[i].y1 = IMTRUNC(y[i]);
+    lset[i].x2 = IMTRUNC(x[(i+1)%l]);
+    lset[i].y2 = IMTRUNC(y[(i+1)%l]);
+    lset[i].miny=min(lset[i].y1,lset[i].y2);
+    lset[i].maxy=max(lset[i].y1,lset[i].y2);
+    lset[i].minx=min(lset[i].x1,lset[i].x2);
+    lset[i].maxx=max(lset[i].x1,lset[i].x2);
+  }
+  return lset;
+}
+
+static
+p_point *
+point_set_new(double *x, double *y, int l) {
+  int i;
+  p_point *pset = mymalloc(sizeof(p_point) * l);
+  
+  for(i=0; i<l; i++) {
+    pset[i].n=i;
+    pset[i].x=IMTRUNC(x[i]);
+    pset[i].y=IMTRUNC(y[i]);
+  }
+  return pset;
+}
+
+static
+void
+p_line_dump(p_line *l) {
+  printf("%d (%d,%d)->(%d,%d) [%d-%d,%d-%d]\n", l->n, l->x1, l->y1, l->x2, l->y2, 
+        l->minx, l->maxx, l->miny, l->maxy);
+}
+
+
+static
+void
+ss_scanline_reset(ss_scanline *ss) {
+  ss->ssnext = 0;
+  memset(ss->line, 0, sizeof(int) * ss->linelen);
+}
+
+static
+void
+ss_scanline_init(ss_scanline *ss, int linelen, int linepairs) {
+  ss->line    = mymalloc( sizeof(int) * linelen );
+  ss->linelen = linelen;
+  ss->ss_list = mymalloc( sizeof(ss_pair) * linepairs );
+  ss->sslen   = linepairs;
+  ss_scanline_reset(ss);
+}
+
+
+/* returns the number of matches */
+
+static
+int
+lines_in_interval(p_line *lset, int l, p_slice *tllist, pcord cc) {
+  int k;
+  int count = 0;
+  for(k=0; k<l; k++) {
+    if (cc >= lset[k].miny && cc <=  lset[k].maxy) {
+      if (lset[k].miny == lset[k].maxy) {
+       POLY_DEB( printf(" HORIZONTAL - skipped\n") );
+      }
+      else {
+       tllist[count].x=p_eval_aty(&lset[k],cc);
+       tllist[count].n=k;
+       count++;
+      }
+    }
+  }
+  return count;
+}
+
+/* marks the up variable for all lines in a slice */
+
+static
+void
+mark_updown_slices(p_line *lset, p_slice *tllist, int count) {
+  p_line *l, *r;
+  int k;
+  for(k=0; k<count; k+=2) {
+    l = lset + tllist[k].n;
+    r = lset + tllist[k+1].n;
+
+    if (l->y1 == l->y2) {
+      mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
+      exit(3);
+    }
+
+    if (r->y1 == r->y2) {
+      mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
+      exit(3);
+    }
+
+    l->updown = (l->x1 == l->x2) ?
+      0 :
+      (l->x1 > l->x2)
+      ? 
+      (l->y1 > l->y2) ? -1 : 1
+      : 
+      (l->y1 > l->y2) ? 1 : -1;
+
+    r->updown = (r->x1 == r->x2) ?
+      0 :
+      (r->x1 > r->x2)
+      ? 
+      (r->y1 > r->y2) ? -1 : 1
+      : 
+      (r->y1 > r->y2) ? 1 : -1;
+    
+    POLY_DEB( printf("marking left line %d as %s(%d)\n", l->n,
+                    l->updown ?  l->updown == 1 ? "up" : "down" : "vert", l->updown, l->updown);
+             printf("marking right line %d as %s(%d)\n", r->n,
+                    r->updown ?  r->updown == 1 ? "up" : "down" : "vert", r->updown, r->updown);
+             );
+  }
+}
+
+
+
+static
+unsigned char
+saturate(int in) {
+  if (in>255) { return 255; }
+  else if (in>0) return in;
+  return 0;
+}
+
+
+/* This function must be modified later to do proper blending */
+
+void
+scanline_flush(i_img *im, ss_scanline *ss, int y, i_color *val) {
+  int x, ch, tv;
+  i_color t;
+  for(x=0; x<im->xsize; x++) {
+    tv = saturate(ss->line[x]);
+    i_gpix(im, x, y, &t);
+    for(ch=0; ch<im->channels; ch++) 
+      t.channel[ch] = tv/255.0 * val->channel[ch] + (1.0-tv/255.0) * t.channel[ch];
+    i_ppix(im, x, y, &t);
+  }
+}
+
+
+
+static
+int
+trap_square(pcord xlen, pcord ylen, double xl, double yl) {
+  POLY_DEB( printf("trap_square: %d %d %.2f %.2f\n", xlen, ylen, xl, yl) );
+  return xlen*ylen-(xl*yl)/2.0;
+}
+
+
+/* 
+   pixel_coverage calculates the 'left side' pixel coverage of a pixel that is
+   within the min/max ranges.  The shape always corresponds to a square with some
+   sort of a triangle cut from it (which can also yield a triangle).
+*/
+
+
+static
+int 
+pixel_coverage(p_line *line, pcord minx, pcord maxx, pcord  miny, pcord maxy) {
+  double lycross, rycross;
+  int l, r;
+
+  double xs, ys;
+  
+  if (!line->updown) {
+    l = r = 0;
+  } else {
+    lycross = p_eval_atx(line, minx);
+    rycross = p_eval_atx(line, maxx);
+    l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */
+    r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */
+  }
+  POLY_DEB(
+          printf("%4s(%+d): ", line->updown ?  line->updown == 1 ? "up" : "down" : "vert", line->updown);
+          printf("(%2d,%2d) [%3d-%3d, %3d-%3d] lycross=%.2f rycross=%.2f", coarse(minx), coarse(miny), minx, maxx, miny, maxy, lycross, rycross);
+          printf("    l=%d r=%d\n", l, r)
+          );
+  
+  if (l && r) 
+    return line->updown == 1 ? 
+      (double)(maxx-minx) * (2.0*maxy-lycross-rycross)/2.0  /* up case */
+      :
+      (double)(maxx-minx) * (lycross+rycross-2*miny)/2.0;  /* down case */
+  
+  if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0;
+
+  if (l && !r)
+    return line->updown == 1 ?
+      trap_square(maxx-minx, maxy-miny, p_eval_aty(line, miny)-minx, p_eval_atx(line, minx)-miny) : 
+      trap_square(maxx-minx, maxy-miny, p_eval_aty(line, maxy)-minx, maxy-p_eval_atx(line, minx));
+  
+
+  if (!l && r) {
+    int r = line->updown == 1 ?
+      (maxx-p_eval_aty(line, maxy))*(maxy-p_eval_atx(line, maxx))/2.0 : 
+      (maxx-p_eval_aty(line, miny))*(p_eval_atx(line, maxx)-miny)/2.0;
+    return r;
+  }
+}
+
+
+
+
+
+/* 
+   handle the scanline slice in three steps 
+   
+   1.  Where only the left edge is inside a pixel
+   2a. Where both left and right edge are inside a pixel
+   2b. Where neither left or right edge are inside a pixel
+   3.  Where only the right edge is inside a pixel
+*/
+
+static
+void
+render_slice_scanline(ss_scanline *ss, int y, p_line *l, p_line *r) {
+  
+  pcord miny, maxy;    /* y bounds in fine coordinates */
+  pcord lminx, lmaxx;  /* left line min/max within y bounds in fine coords */
+  pcord rminx, rmaxx;  /* right line min/max within y bounds in fine coords */
+  int cpix;            /* x-coordinate of current pixel */
+  int thin;            /* boolean for thin/thick segment */
+  int startpix;                /* temporary variable for "start of this interval" */
+  int stoppix;         /* temporary variable for "end of this interval" */
+  int step2end;                /* temporary variable to mark where step2 ends */
+
+  /* Find the y bounds of scanline_slice */
+
+  maxy = min( l->maxy, r->maxy );
+  miny = max( l->miny, r->miny );
+
+  maxy = min( maxy, (y+1)*16 );
+  miny = max( miny,  y*16 );
+
+  lminx = min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
+  lmaxx = max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
+
+  rminx = min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
+  rmaxx = max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
+
+  thin = coarse(lmaxx) >= coarse(rminx);
+
+  startpix = max( coarse(lminx), 0 );
+  stoppix  = min( coarse(rmaxx-1), ss->linelen-1 );
+  
+  for(cpix=startpix; cpix<=stoppix; cpix++) {
+    int lt = coarse(lmaxx-1) >= cpix;
+    int rt = coarse(rminx) <= cpix;
+    
+    int A, B, C;
+    
+    POLY_DEB( printf("(%d,%d) lt=%d rt=%d\n", cpix, y, lt, rt) );
+
+    A = lt ? pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy) : 0;
+    B = lt ? 0 : 16*(maxy-miny);
+    C = rt ? pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy) : 0;
+
+    POLY_DEB( printf("A=%d B=%d C=%d\n", A, B, C) );
+
+    ss->line[cpix] += A+B-C;
+
+  }
+  
+}
+
+
+
+static
+void
+render_slice_scanline_old(ss_scanline *ss, int y, p_line *l, p_line *r) {
+  
+  pcord miny, maxy;    /* y bounds in fine coordinates */
+  pcord lminx, lmaxx;  /* left line min/max within y bounds in fine coords */
+  pcord rminx, rmaxx;  /* right line min/max within y bounds in fine coords */
+  int cpix;            /* x-coordinate of current pixel */
+  int thin;            /* boolean for thin/thick segment */
+  int startpix;                /* temporary variable for "start of this interval" */
+  int stoppix;         /* temporary variable for "end of this interval" */
+  int step2end;                /* temporary variable to mark where step2 ends */
+
+  /* Find the y bounds of scanline_slice */
+
+  maxy = min( l->maxy, r->maxy );
+  miny = max( l->miny, r->miny );
+
+  maxy = min( maxy, (y+1)*16 );
+  miny = max( miny,  y*16 );
+
+  lminx = min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
+  lmaxx = max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
+
+  rminx = min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
+  rmaxx = max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
+
+  thin = coarse(lmaxx) >= coarse(rminx);
+
+
+  /* First step */
+  startpix = coarse(lminx);                            /* includes tricky starting pixel */
+  stoppix  = min(coarse(lmaxx), coarse(rminx) );       /* last pixel is tricky */
+  
+  /* handle start pixel */
+
+  cpix = startpix;
+  if (cpix < stoppix) {
+    ss->line[cpix] += pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy);
+    printf("%2d: step1 - start pixel\n", cpix);
+  }
+  
+  for(cpix=startpix+1; cpix<stoppix; cpix++) {
+    printf("%2d: step1 pixel\n", cpix);
+    ss->line[cpix] += l->updown == 1 ? 
+      8.0 * (2*maxy-p_eval_atx(l, 16*cpix)-p_eval_atx(l, 16*cpix+16))  /* up case */
+      :
+      8.0 * (p_eval_atx(l, 16*cpix)+p_eval_atx(l, 16*cpix+16)-2*miny); /* down case */
+  }
+  
+  
+  /* handle stop pixel */
+
+  if (thin) { /* step 2a */
+    startpix = coarse(rminx);
+    stoppix = coarse(lmaxx+15); /* one more than needed */
+    
+    for(cpix=startpix; cpix<stoppix; cpix++) {
+      printf("%2d: step2a pixel\n", cpix);
+      ss->line[cpix] += 
+       pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy)
+       +(cpix*16+16-min(cpix*16+16, l->maxx))*(maxy-miny)
+       -pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy);
+    }
+  } else { /* step 2b */
+    stoppix = coarse(rminx);
+    for(/* cpix already correct */; cpix<stoppix; cpix++) {
+      printf("%2d: step2b pixel\n", cpix);
+      ss->line[cpix] += 16.0*(maxy-miny);
+    }
+  }
+  
+  /* step 3 */
+
+  cpix = max(coarse(rminx), coarse(lmaxx+15));
+  stoppix = coarse(rmaxx-15);
+  
+  printf("step3 from %d to %d\n", cpix, stoppix);
+
+  for(; cpix<stoppix; cpix++) {
+    printf("%2d: step3 pixel\n", cpix);
+    ss->line[cpix] += 0+ 
+      (l->updown == 1 ?
+       8.0 * (2*maxy-p_eval_atx(r, 16*cpix)-p_eval_atx(r, 16*cpix+16))  /* up case */
+       :
+       8.0 * (p_eval_atx(r, 16*cpix)+p_eval_atx(r, 16*cpix+16)-2*miny));  /* down case */
+  }
+  
+  ss->line[cpix] += (16.0)*(maxy-miny) - pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy);
+}
+
+
+
+
+
+
+/* Antialiasing polygon algorithm 
+   specs:
+   1. only nice polygons - no crossovers
+   2. 1/16 pixel resolution
+   3. full antialiasing ( complete spectrum of blends )
+   4. uses hardly any memory
+   5. no subsampling phase
+   
+
+   Algorithm outline:
+   1. Split into vertical intervals.
+   2. handle each interval 
+
+   For each interval we must: 
+   1. find which lines are in it
+   2. order the lines from in increasing x order.
+      since we are assuming no crossovers it is sufficent
+      to check a single point on each line.
+*/
+
+/*
+  Definitions:
+  
+  1. Interval:  A vertical segment in which no lines cross nor end.
+  2. Scanline:  A physical line, contains 16 subpixels in the horizontal direction
+  3. Slice:     A start stop line pair.
+  
+ */
+
+
+void
+i_poly_aa(i_img *im, int l, double *x, double *y, i_color *val) {
+  int i ,k;                    /* Index variables */
+  int clc;                     /* Lines inside current interval */
+  pcord miny ,maxy;            /* Min and max values of the current slice in the subcord system */
+  pcord tempy;
+  int cscl;                    /* Current scanline */
+
+  ss_scanline templine;                /* scanline accumulator */
+  p_point *pset;               /* List of points in polygon */
+  p_line  *lset;               /* List of lines in polygon */
+  p_slice *tllist;             /* List of slices */
+
+  fflush(stdout);
+  setbuf(stdout, NULL);
+   
+
+  tllist   = mymalloc(sizeof(p_slice)*l);
+  
+  ss_scanline_init(&templine, im->xsize, l);
+
+  pset     = point_set_new(x, y, l);
+  lset     = line_set_new(x, y, l);
+
+
+  qsort(pset, l, sizeof(p_point), (int(*)(const void *,const void *))p_compy);
+  
+  POLY_DEB(
+          for(i=0;i<l;i++) {
+            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);
+          }
+          printf("MAIN LOOP\n\n");
+          );
+  
+
+  /* loop on intervals */
+  for(i=0; i<l-1; i++) {
+    int startscan = max( coarse(pset[i].y), 0);
+    int stopscan = min( coarse(pset[i+1].y+15), im->ysize-1);
+    pcord cc = (pset[i].y + pset[i+1].y)/2;
+
+    POLY_DEB(
+            printf("current slice is %d: %d to %d ( cpoint %d ) scanlines %d to %d\n", 
+                   i, pset[i].y, pset[i+1].y, cc, startscan, stopscan)
+            );
+    
+    if (pset[i].y == pset[i+1].y) {
+      POLY_DEB( printf("current slice thickness = 0 => skipping\n") );
+      continue;
+    }
+    
+    clc = lines_in_interval(lset, l, tllist, cc);
+    qsort(tllist, clc, sizeof(p_slice), (int(*)(const void *,const void *))p_compx);
+
+    mark_updown_slices(lset, tllist, clc);
+
+    POLY_DEB( printf("Interval contains %d lines\n", clc) );
+
+    for(k=0; k<clc; k++) {
+      int lno = tllist[k].n;
+      p_line *ln = lset+lno;
+      POLY_DEB(
+              printf("%d:  line #%2d: (%2d, %2d)->(%2d, %2d) (%2d/%2d, %2d/%2d) -> (%2d/%2d, %2d/%2d) alignment=%s\n",
+                     k, lno, ln->x1, ln->y1, ln->x2, ln->y2, 
+                     coarse(ln->x1), fine(ln->x1), 
+                     coarse(ln->y1), fine(ln->y1), 
+                     coarse(ln->x2), fine(ln->x2), 
+                     coarse(ln->y2), fine(ln->y2),
+                     ln->updown == 0 ? "vert" : ln->updown == 1 ? "up" : "down")
+              );
+    }
+    for(cscl=startscan; cscl<stopscan; cscl++) {
+      tempy = min(cscl*16+16, pset[i+1].y);
+      POLY_DEB( printf("evaluating scan line %d \n", cscl) );
+      for(k=0; k<clc-1; k+=2) {
+       render_slice_scanline(&templine, cscl, lset+tllist[k].n, lset+tllist[k+1].n);
+      }
+      if (16*coarse(tempy) == tempy) {
+       POLY_DEB( printf("flushing scan line %d\n", cscl) );
+       scanline_flush(im, &templine, cscl, val);
+       ss_scanline_reset(&templine);
+      }
+      /*
+       else {
+       scanline_flush(im, &templine, cscl, val);
+       ss_scanline_reset(&templine);
+       return 0;
+       }
+      */
+    }
+  } /* Intervals */
+  if (16*coarse(tempy) != tempy) 
+    scanline_flush(im, &templine, cscl-1, val);
+} /* Function */
+
index c088867..c9444bf 100644 (file)
 # Change 1..1 below to 1..last_test_to_print .
 # (It may become useful if the test is moved to ./t subdirectory.)
 
-BEGIN { $| = 1; print "1..3\n"; }
+BEGIN { $| = 1; print "1..5\n"; }
 END {print "not ok 1\n" unless $loaded;}
 use Imager qw(:all);
 
+sub PI () { 3.14159265358979323846 }
 
-$Imager::DEBUG=1;
 $loaded = 1;
 print "ok 1\n";
 
 init_log("testout/t75aapolyaa.log",1);
 
-$green=i_color_new(0,255,0,0);
+$red   = Imager::Color->new(255,0,0);
+$green = Imager::Color->new(0,255,0);
+$blue  = Imager::Color->new(0,0,255);
+$white = Imager::Color->new(255,255,255);
 
 
-$img=Imager->new(xsize=>10,ysize=>10);
+$img = Imager->new(xsize=>20, ysize=>10);
+@data = translate(5.5,5,
+                 rotate(0,
+                        scale(5, 5,
+                              get_polygon(n_gon => 5)
+                             )
+                       )
+                );
 
-#$nums=10;
-#$rn=10;
 
-#@rand=map { rand($rn) } 0..$nums-1;
-#@angle=sort { $a<=>$b } map { rand(360) } 0..$nums-1;
+my ($x, $y) = array_to_refpair(@data);
+i_poly_aa($img->{IMG}, $x, $y, $white);
 
-#@x=map { 25+(10+$rand[$_])*cos($angle[$_]/180*3.1415) } 0..$nums-1;
-#@y=map { 25+(10+$rand[$_])*sin($angle[$_]/180*3.1415) } 0..$nums-1;
 
-#i_poly_aa($img,[50,300,290,200],[50,60,190,220],$green);
 
-$x1=16;
-$y1=10;
 
-@x=(1, $x1, $x1);
-@y=(1,  1, $y1);
+print "ok 2\n";
 
-@x=map { $_+0.5 } (0, 8, 8);
-@y=map { $_+0.5 } (0, 4, 0);
+$img->write(file=>"testout/t75.ppm") or die $img->errstr;
+print "ok 3\n";
 
-i_poly_aa($img->{IMG},\@x,\@y,$green);
 
-push(@x,$x[0]);
-push(@y,$y[0]);
+$zoom = make_zoom($img, 8, \@data, $red);
+$zoom->write(file=>"testout/t75zoom.ppm") or die $zoom->errstr;
 
-#$red=i_color_new(255,0,0,0);
-#$img->polyline(color=>$red,'x'=>\@x,'y'=>\@y,antialias=>0);
-print "ok 2\n";
+print "ok 4\n";
 
-open(FH,">testout/t75.ppm") || die "Cannot open testout/t75.ppm\n";
-binmode(FH);
-$IO = Imager::io_new_fd( fileno(FH) );
-i_writeppm_wiol($img->{IMG}, $IO) || die "Cannot write testout/t75.ppm\n";
-close(FH);
+$img = Imager->new(xsize=>300, ysize=>100);
 
-print "ok 3\n";
+for $n (0..55) {
+  @data = translate(20+20*($n%14),18+20*int($n/14),
+                   rotate(15*$n/PI,
+                          scale(15, 15,
+                                get_polygon('box')
+                               )
+                         )
+                  );
+  my ($x, $y) = array_to_refpair(@data);
+  i_poly_aa($img->{IMG}, $x, $y, NC(rand(255), rand(255), rand(255)));
+}
+
+$img->write(file=>"testout/t75big.png") or die $img->errstr;
+
+print "ok 5\n";
+
+malloc_state();
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+sub get_polygon {
+  my $name = shift;
+  if (exists $primitives{$name}) {
+    return @{$primitives{$name}};
+  }
+
+  if (exists $polygens{$name}) {
+    return $polygens{$name}->(@_);
+  }
+
+  die "polygon spec: $name unknown\n";
+}
+
+
+sub make_zoom {
+  my ($img, $sc, $polydata, $linecolor) = @_;
+
+  # scale with nearest neighboor sampling
+  my $timg = $img->scale(scalefactor=>$sc, qtype=>'preview');
+
+  # draw the grid
+  for($lx=0; $lx<$timg->getwidth(); $lx+=$sc) {
+    $timg->line(color=>$green, x1=>$lx, x2=>$lx, y1=>0, y2=>$timg->getheight(), antialias=>0);
+  }
+
+  for($ly=0; $ly<$timg->getheight(); $ly+=$sc) {
+    $timg->line(color=>$green, y1=>$ly, y2=>$ly, x1=>0, x2=>$timg->getwidth(), antialias=>0);
+  }
+  my @data = scale($sc, $sc, @$polydata);
+  push(@data, $data[0]);
+  my ($x, $y) = array_to_refpair(@data);
+
+  $timg->polyline(color=>$linecolor, 'x'=>$x, 'y'=>$y, antialias=>0);
+  return $timg;
+}
+
+# utility functions to manipulate point data
+
+sub scale {
+  my ($x, $y, @data) = @_;
+  return map { [ $_->[0]*$x , $_->[1]*$y ] } @data;
+}
+
+sub translate {
+  my ($x, $y, @data) = @_;
+  map { [ $_->[0]+$x , $_->[1]+$y ] } @data;
+}
+
+sub rotate {
+  my ($rad, @data) = @_;
+  map { [ $_->[0]*cos($rad)+$_->[1]*sin($rad) , $_->[1]*cos($rad)-$_->[0]*sin($rad) ] } @data;
+}
+
+sub array_to_refpair {
+  my (@x, @y);
+  for (@_) {
+    push(@x, $_->[0]);
+    push(@y, $_->[1]);
+  }
+  return \@x, \@y;
+}
+
+
+
+BEGIN {
+%primitives = (
+              box => [ [-0.5,-0.5], [0.5,-0.5], [0.5,0.5], [-0.5,0.5] ],
+              triangle => [ [0,0], [1,0], [1,1] ],
+             );
 
-#malloc_state();
+%polygens = (
+            wavycircle => sub {
+              my $numv = shift;
+              my $radfunc = shift;
+              my @radians = map { $_*2*PI/$numv } 0..$numv-1;
+              my @radius  = map { $radfunc->($_) } @radians;
+              map {
+                [ $radius[$_] * cos($_), $radius[$_] * sin($_) ]
+              } 0..$#radians;
+            },
+            n_gon => sub {
+              my $N = shift;
+              map {
+                [ cos($_*2*PI/$N), sin($_*2*PI/$N) ]
+              } 0..$N-1;
+            },
+);
+}