From: Matthias Kramm Date: Fri, 1 May 2009 12:13:35 +0000 (+0200) Subject: polygon intersector: improved test routines X-Git-Tag: polyok~14 X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=commitdiff_plain;h=c41f4433d3e721073c60d55cd923a087761e45f7;hp=002f2ed7c404339e11d669aa86ec998d8dd473a5 polygon intersector: improved test routines --- diff --git a/lib/gfxpoly.c b/lib/gfxpoly.c index a08899d..76352af 100644 --- a/lib/gfxpoly.c +++ b/lib/gfxpoly.c @@ -265,7 +265,7 @@ intbbox_t get_svp_bbox(ArtSVP*svp, double zoom) if(x1 < b.xmin) b.xmin = x1; if(y1 < b.ymin) b.ymin = y1; if(x2 > b.xmax) b.xmax = x2; - if(y2 > b.xmax) b.ymax = y2; + if(y2 > b.ymax) b.ymax = y2; } } if(b.xmax > (int)(MAX_WIDTH*zoom)) @@ -304,49 +304,37 @@ intbbox_t get_svp_bbox(ArtSVP*svp, double zoom) int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2) { - int similar = 0; + if(!data1 || !data2) + return 0; int x,y; int height = bbox->height; int width = bbox->width; int width8 = (width+7) >> 3; unsigned char*l1 = &data1[width8]; unsigned char*l2 = &data2[width8]; - int fail = 0; for(y=1;y Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line)); ArtSVP* svp = gfxfillToSVP(line, 1); - /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if - positive and negative line segments add up to something positive. - I *think* that clockwise fill in PDF is defined in a way, however, - that the *last* shape's direction will determine whether something - is filled */ ArtSVP* svp_rewinded; - svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE); + svp_rewinded = run_intersector(svp, ART_WIND_RULE_NONZERO); if(!svp_rewinded) { art_svp_free(svp); return 0; diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index 50282b9..5615612 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -1,6 +1,7 @@ #include #include #include +#include #include "../gfxdevice.h" #include "poly.h" @@ -15,7 +16,7 @@ static edge_t*edge_new(int x1, int y1, int x2, int y2) return s; } -static inline void gfxpoly_add_edge(edge_t**list, double _x1, double _y1, double _x2, double _y2) +static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, double _x2, double _y2) { int x1 = ceil(_x1); int y1 = ceil(_y1); @@ -23,14 +24,14 @@ static inline void gfxpoly_add_edge(edge_t**list, double _x1, double _y1, double int y2 = ceil(_y2); if(x1!=x2 || y1!=y2) { edge_t*s = edge_new(x1, y1, x2, y2); - s->next = *list; - *list = s; + s->next = poly->edges; + poly->edges = s; } } gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line, double gridsize) { - edge_t*s = 0; + gfxpoly_t*p = gfxpoly_new(gridsize); /* factor that determines into how many line fragments a spline is converted */ double subfraction = 2.4;//0.3 @@ -44,7 +45,7 @@ gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line, double gridsize) double y = line->y*z; if(line->type == gfx_moveTo) { } else if(line->type == gfx_lineTo) { - gfxpoly_add_edge(&s, lastx, lasty, x, y); + gfxpoly_add_edge(p, lastx, lasty, x, y); } else if(line->type == gfx_splineTo) { int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) + fabs(line->y-2*line->sy+lasty))*subfraction); @@ -55,11 +56,11 @@ gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line, double gridsize) double t = (double)i*stepsize; double sx = (line->x*t*t + 2*line->sx*t*(1-t) + x*(1-t)*(1-t))*z; double sy = (line->y*t*t + 2*line->sy*t*(1-t) + y*(1-t)*(1-t))*z; - gfxpoly_add_edge(&s, lastx, lasty, sx, sy); + gfxpoly_add_edge(p, lastx, lasty, sx, sy); lastx = sx; lasty = sy; } - gfxpoly_add_edge(&s, lastx, lasty, x, y); + gfxpoly_add_edge(p, lastx, lasty, x, y); } lastx = x; lasty = y; @@ -67,9 +68,67 @@ gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line, double gridsize) } gfxline_free(line); + return p; +} + +static char* readline(FILE*fi) +{ + char c; + while(1) { + int l = fread(&c, 1, 1, fi); + if(!l) + return 0; + if(c!=10 || c!=13) + break; + } + char line[256]; + int pos = 0; + while(1) { + line[pos++] = c; + line[pos] = 0; + int l = fread(&c, 1, 1, fi); + if(!l || c==10 || c==13) { + return strdup(line); + } + } +} +gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize) +{ gfxpoly_t*p = gfxpoly_new(gridsize); - p->edges = s; + + double z = 1.0 / gridsize; + + FILE*fi = fopen(filename, "rb"); + if(!fi) { + perror(filename); + return 0; + } + int count = 0; + double lastx=0,lasty=0; + while(1) { + char*line = readline(fi); + if(!line) + break; + double x,y; + char s[256]; + if(sscanf(line, "%lf %lf %s", &x, &y, &s) == 3) { + x*=z; + y*=z; + if(s && !strcmp(s,"moveto")) { + count++; + } else if(s && !strcmp(s,"lineto")) { + gfxpoly_add_edge(p, lastx, lasty, x, y); + count++; + } else { + printf("invalid command: %s\n", s); + } + lastx = x; + lasty = y; + } + free(line); + } + fclose(fi); + printf("loaded %d points from %s\n", count, filename); return p; } - diff --git a/lib/gfxpoly/convert.h b/lib/gfxpoly/convert.h index b54b65d..d1d5344 100644 --- a/lib/gfxpoly/convert.h +++ b/lib/gfxpoly/convert.h @@ -4,5 +4,6 @@ #include "poly.h" gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line, double gridsize); +gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize); #endif //__poly_convert_h__ diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 38ec637..72e72aa 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -3,6 +3,7 @@ #include #include #include "../mem.h" +#include "../types.h" #include "../q.h" #include "poly.h" #include "active.h" @@ -100,12 +101,45 @@ void gfxpoly_destroy(gfxpoly_t*poly) } free(poly); } +char gfxpoly_check(gfxpoly_t*poly) +{ + edge_t* s = poly->edges; + dict_t*d = dict_new2(&point_type); + while(s) { + if(!dict_contains(d, &s->a)) { + dict_put(d, &s->a, (void*)(ptroff_t)1); + } else { + int count = (ptroff_t)dict_lookup(d, &s->a); + dict_del(d, &s->a); + count++; + dict_put(d, &s->a, (void*)(ptroff_t)count); + } + if(!dict_contains(d, &s->b)) { + dict_put(d, &s->b, (void*)(ptroff_t)1); + } else { + int count = (ptroff_t)dict_lookup(d, &s->b); + dict_del(d, &s->b); + count++; + dict_put(d, &s->b, (void*)(ptroff_t)count); + } + s = s->next; + } + DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) { + int count = (ptroff_t)c; + if(count&1) { + fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count); + return 0; + } + } + return 1; +} void gfxpoly_dump(gfxpoly_t*poly) { - edge_t* s = (edge_t*)poly; + edge_t* s = poly->edges; + double g = poly->gridsize; while(s) { - fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y); + fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g); s = s->next; } } diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index e678b00..fede823 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -70,6 +70,7 @@ typedef struct _gfxpoly { } gfxpoly_t; gfxpoly_t* gfxpoly_new(double gridsize); +char gfxpoly_check(gfxpoly_t*poly); void gfxpoly_dump(gfxpoly_t*poly); gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule); diff --git a/lib/gfxpoly/renderpoly.c b/lib/gfxpoly/renderpoly.c index 9ec6abf..2373a64 100644 --- a/lib/gfxpoly/renderpoly.c +++ b/lib/gfxpoly/renderpoly.c @@ -8,6 +8,7 @@ typedef struct _renderpoint double x; segment_dir_t dir; fillstyle_t*fs; + edge_t*e; //only for debugging int polygon_nr; } renderpoint_t; @@ -27,16 +28,18 @@ typedef struct _renderbuf renderline_t*lines; } renderbuf_t; -static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir, fillstyle_t*fs, int polygon_nr) +static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir, fillstyle_t*fs, int polygon_nr, edge_t*e) { renderpoint_t p; p.x = x; p.dir = dir; p.fs = fs; + p.e = e; p.polygon_nr = polygon_nr; if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin) return; + renderline_t*l = &buf->lines[y-buf->bbox.ymin]; if(l->num == l->size) { @@ -47,8 +50,7 @@ static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir l->num++; } #define CUT 0.5 -#define INT(x) ((int)((x)+16)-16) -static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, fillstyle_t*fs, int polygon_nr) +static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, fillstyle_t*fs, int polygon_nr, edge_t*e) { x1 *= buf->zoom; y1 *= buf->zoom; @@ -65,14 +67,14 @@ static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2 } diffx = x2 - x1; diffy = y2 - y1; - ny1 = INT(y1)+CUT; - ny2 = INT(y2)+CUT; + ny1 = floor(y1)+CUT; + ny2 = floor(y2)+CUT; if(ny1 < y1) { - ny1 = INT(y1) + 1.0 + CUT; + ny1 = floor(y1) + 1.0 + CUT; } if(ny2 >= y2) { - ny2 = INT(y2) - 1.0 + CUT; + ny2 = floor(y2) - 1.0 + CUT; } if(ny1 > ny2) return; @@ -81,14 +83,14 @@ static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2 x1 = x1 + (ny1-y1)*stepx; x2 = x2 + (ny2-y2)*stepx; - int posy=INT(ny1); - int endy=INT(ny2); + int posy=floor(ny1); + int endy=floor(ny2); double posx=0; double startx = x1; while(posy<=endy) { double xx = startx + posx; - add_pixel(buf, xx, posy, dir, fs, polygon_nr); + add_pixel(buf, xx, posy, dir, fs, polygon_nr, e); posx+=stepx; posy++; } @@ -140,7 +142,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi edge_t*e; int polygon_nr = 0; for(e=polygon->edges;e;e=e->next) { - add_line(buf, e->a.x, e->a.y, e->b.x, e->b.y, e->style, polygon_nr); + add_line(buf, e->a.x, e->a.y, e->b.x, e->b.y, e->style, polygon_nr, e); } for(y=0;yheight;y++) { @@ -168,10 +170,9 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi lastx = x; } if(fill.is_filled && lastx!=buf->width) { - - return 0;// return an error, we're bleeding - - fill_bitwise(line, lastx, buf->width); + /* we're bleeding, fill over padding, too. */ + fprintf(stderr, "Polygon %08x is bleeding in line %d\n", polygon, y); + fill_bitwise(line, lastx, width8*8); } } @@ -209,19 +210,19 @@ intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom) intbbox_t b = {0,0,0,0}; edge_t*e = polygon->edges; - zoom *= polygon->gridsize; + double g = zoom*polygon->gridsize; if(e) { - b.xmin = e->a.x*zoom; - b.ymin = e->a.y*zoom; - b.xmax = e->a.x*zoom; - b.ymax = e->a.y*zoom; + b.xmin = e->a.x*g; + b.ymin = e->a.y*g; + b.xmax = e->a.x*g; + b.ymax = e->a.y*g; } for(e=polygon->edges;e;e=e->next) { - double x_min = min(e->a.x,e->b.x)*zoom; - double y_min = min(e->a.y,e->b.y)*zoom; - double x_max = max(e->a.x,e->b.x)*zoom; - double y_max = max(e->a.y,e->b.y)*zoom; + double x_min = min(e->a.x,e->b.x)*g; + double y_min = min(e->a.y,e->b.y)*g; + double x_max = max(e->a.x,e->b.x)*g; + double y_max = max(e->a.y,e->b.y)*g; int x1 = floor(x_min); int y1 = floor(y_min); int x2 = ceil(x_max); @@ -229,8 +230,9 @@ intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom) if(x1 < b.xmin) b.xmin = x1; if(y1 < b.ymin) b.ymin = y1; if(x2 > b.xmax) b.xmax = x2; - if(y2 > b.xmax) b.ymax = y2; + if(y2 > b.ymax) b.ymax = y2; } + if(b.xmax > (int)(MAX_WIDTH*zoom)) b.xmax = (int)(MAX_WIDTH*zoom); if(b.ymax > (int)(MAX_HEIGHT*zoom)) @@ -244,9 +246,15 @@ intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom) b.xmin = b.xmax; if(b.ymin > b.ymax) b.ymin = b.ymax; + + b.xmax += 8; + while(((b.xmax - b.xmin)&0x07) != 0x04) + b.xmax++; b.width = b.xmax - b.xmin; b.height = b.ymax - b.ymin; + printf("%dx%d\n", b.width, b.height); + return b; } @@ -269,8 +277,24 @@ intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom) #define B00000010 0x02 #define B00000001 0x01 +int bitmap_ok(intbbox_t*bbox, unsigned char*data) +{ + int y; + int width8 = (bbox->width+7) >> 3; + if((bbox->width&7) == 0) + return 1; + for(y=0;yheight;y++) { + if(data[width8-1]&0x01) + return 0; //bleeding + data += width8; + } + return 1; +} + int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2) { + if(!data1 || !data2) + return 0; int x,y; int height = bbox->height; int width = bbox->width; diff --git a/lib/gfxpoly/renderpoly.h b/lib/gfxpoly/renderpoly.h index 050c781..7d0afb4 100644 --- a/lib/gfxpoly/renderpoly.h +++ b/lib/gfxpoly/renderpoly.h @@ -18,4 +18,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi intbbox_t intbbox_new(int x1, int y1, int x2, int y2); intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom); +int bitmap_ok(intbbox_t*bbox, unsigned char*data); +int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2); + #endif diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c index b9062f5..74c6497 100644 --- a/lib/gfxpoly/test.c +++ b/lib/gfxpoly/test.c @@ -70,12 +70,11 @@ int test_square(int width, int height, int num, double gridsize, char bitmaptest line[num-1].y = line[0].y; line[num-1].next = 0; - windrule_t*rule = &windrule_circular; - gfxpoly_t*poly = gfxpoly_fillToPoly(line, gridsize); - gfxpoly_t*poly2 = gfxpoly_process(poly, rule); gfxline_free(line); + windrule_t*rule = &windrule_circular; + gfxpoly_t*poly2 = gfxpoly_process(poly, rule); if(bitmaptest) { intbbox_t bbox = intbbox_new(0, 0, width, height); unsigned char*bitmap1 = render_polygon(poly, &bbox, 1.0, rule); @@ -85,9 +84,8 @@ int test_square(int width, int height, int num, double gridsize, char bitmaptest assert(!"bitmaps don't match"); } } - - gfxpoly_destroy(poly); gfxpoly_destroy(poly2); + gfxpoly_destroy(poly); } int test2() @@ -213,7 +211,49 @@ void test3() swf_SaveSWF(&swf, "test.swf"); } +#include +void test4() +{ + char*dir = "ps"; + DIR*_dir = opendir(dir); + if(!_dir) return; + struct dirent*file; + while(1) { + file = readdir(_dir); + if (!file) + break; + if(!strstr(file->d_name, ".ps")) + continue; + + char* filename = allocprintf("%s/%s", dir, file->d_name); + windrule_t*rule = &windrule_evenodd; + gfxpoly_t*poly = gfxpoly_from_file(filename, 0.01); + free(filename); + + double zoom = 1.0; + intbbox_t bbox = intbbox_from_polygon(poly, zoom); + + if(!gfxpoly_check(poly)) { + printf("bad polygon\n"); + continue; + } + + gfxpoly_t*poly2 = gfxpoly_process(poly, rule); + unsigned char*bitmap1 = render_polygon(poly, &bbox, zoom, rule); + unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd); + if(!bitmap_ok(&bbox, bitmap1) || !bitmap_ok(&bbox, bitmap2)) { + save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png"); + assert(!"error in bitmaps"); + } + if(!compare_bitmaps(&bbox, bitmap1, bitmap2)) { + save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png"); + assert(!"bitmaps don't match"); + } + gfxpoly_destroy(poly2); + } +} + int main() { - test3(); + test4(); }