+
+
+
+
+
+
+
+
/* Flood fill
REF: Graphics Gems I. page 282+
*/
-
-
-#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 */
--- /dev/null
+#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 */
+
# 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;
+ },
+);
+}
projects / imager.git / commitdiff