From 64cbdc0d10e611af20d4d375ff6319793da8e6f5 Mon Sep 17 00:00:00 2001 From: Matthias Kramm Date: Sun, 3 May 2009 20:57:00 +0200 Subject: [PATCH] new polygon renderer: fixed numerical issues --- lib/gfxpoly/Makefile | 2 +- lib/gfxpoly/active.c | 15 ++++++++++----- lib/gfxpoly/convert.c | 9 ++++++++- lib/gfxpoly/poly.c | 45 ++++++++++++++++++++++----------------------- lib/gfxpoly/poly.h | 7 ++----- lib/gfxpoly/renderpoly.c | 24 ++++++++++++------------ lib/gfxpoly/test.c | 44 +++++++++++++++++++++++++++++++------------- 7 files changed, 86 insertions(+), 60 deletions(-) diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile index 068901a..8469965 100644 --- a/lib/gfxpoly/Makefile +++ b/lib/gfxpoly/Makefile @@ -1,6 +1,6 @@ all: testheap test -CC = gcc -g -pg +CC = gcc -g -O2 ../libbase.a: ../q.c ../q.h ../mem.c ../mem.h cd ..; make libbase.a diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c index 02638f5..aece368 100644 --- a/lib/gfxpoly/active.c +++ b/lib/gfxpoly/active.c @@ -35,14 +35,19 @@ void actlist_verify(actlist_t*a, int32_t y) { segment_t*s = a->list; assert(!s || !s->left); - double lastx; + segment_t*l = 0; while(s) { if(y) { - double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x; - if(s!=a->list) { - assert(lastx<=x); + if(l) { + /* we need to re-evaluate the x of the previous segment. if we + try to store it, it might end up being converted to a double, + which will make it non-equal to (and possibly larger than) the + "long double" the FPU has in it's register. This only happens + when compiler optimizations are turned on. */ + assert((XPOS(s, y) - XPOS(l, y)) >= 0); + assert(XDIFF(s,l,y) >= 0); } - lastx = x; + l = s; } assert(!s->left || s->left->right == s); assert(!s->right || s->right->left == s); diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index f293d16..aea0a17 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -104,6 +104,7 @@ gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize) return 0; } int count = 0; + double g = 0; double lastx=0,lasty=0; while(1) { char*line = readline(fi); @@ -124,10 +125,16 @@ gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize) } lastx = x; lasty = y; + } else if(sscanf(line, "%% gridsize %lf", &g) == 1) { + p->gridsize = g; } free(line); } fclose(fi); - printf("loaded %d points from %s\n", count, filename); + if(g) { + printf("loaded %d points from %s (gridsize %f)\n", count, filename, g); + } else { + printf("loaded %d points from %s\n", count, filename); + } return p; } diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index b143328..4d641a1 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -175,6 +175,7 @@ void gfxpoly_dump(gfxpoly_t*poly) gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename) { FILE*fi = fopen(filename, "wb"); + fprintf(fi, "%% gridsize %f\n", poly->gridsize); fprintf(fi, "%% begin\n"); edge_t* s = poly->edges; while(s) { @@ -216,7 +217,7 @@ static inline min32(int32_t v1, int32_t v2) {return v1(%d,%d) ", s->a.x, s->a.y, s->b.x, s->b.y); - fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k, + fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k, (double)s->delta.x / s->delta.y); } @@ -521,7 +522,7 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p) if(s->fs_out) { #ifdef DEBUG - fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr, + fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr, s->pos.x, s->pos.y, p.x, p.y); #endif // omit horizontal lines @@ -552,16 +553,9 @@ typedef struct _segrange { segment_t*segmax; } segrange_t; -static inline char xpos_eq(segment_t*s1, segment_t*s2, int y) -{ - if(XPOS_EQ(s1, s2, y)) { - return 1; - } - return 0; -} - void segrange_adjust_endpoints(segrange_t*range, int y) { +#define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos))) #ifdef CHECK /* this would mean that the segment left/right of the minimum/maximum intersects the current segment exactly at the scanline, but somehow @@ -570,12 +564,13 @@ void segrange_adjust_endpoints(segrange_t*range, int y) assert(!max || !max->right || !XPOS_EQ(max, max->right, y)); #endif + /* this doesn't actually ever happen anymore (see checks above) */ segment_t*min = range->segmin; segment_t*max = range->segmax; - if(min) while(min->left && xpos_eq(min, min->left, y)) { + if(min) while(min->left && XPOS_EQ(min, min->left, y)) { min = min->left; } - if(max) while(max->right && xpos_eq(max, max->right, y)) { + if(max) while(max->right && XPOS_EQ(max, max->right, y)) { max = max->right; } range->segmin = min; @@ -621,9 +616,8 @@ static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, for(t=0;txrow->num;t++) { box_t box = box_new(status->xrow->x[t], y); segment_t*seg = actlist_find(status->actlist, box.left2, box.left2); - - seg = actlist_right(status->actlist, seg); + seg = actlist_right(status->actlist, seg); while(seg) { if(seg->a.y == y) { // this segment started in this scanline, ignore it @@ -665,7 +659,7 @@ static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, for(t=status->xrow->num-1;t>=0;t--) { box_t box = box_new(status->xrow->x[t], y); segment_t*seg = actlist_find(status->actlist, box.right2, box.right2); - + while(seg) { if(seg->a.y == y) { // this segment started in this scanline, ignore it @@ -710,7 +704,7 @@ void add_points_to_ending_segments(status_t*status, int32_t y) segment_t*next = seg->right;seg->right=0; assert(seg->b.y == status->y); - + if(status->xrow->num == 1) { // shortcut point_t p = {status->xrow->x[0], y}; @@ -773,12 +767,12 @@ static void recalculate_windings(status_t*status, segrange_t*range) s = actlist_leftmost(status->actlist); while(s && s!=range->segmin) { assert(!s->changed); - s = actlist_right(status->actlist, s); + s = s->right; } s = actlist_rightmost(status->actlist); while(s && s!=range->segmax) { assert(!s->changed); - s = actlist_left(status->actlist, s); + s = s->left; } /* in check mode, go through the whole interval so we can test that all polygons where the fillstyle changed also have seg->changed=1 */ @@ -790,7 +784,7 @@ static void recalculate_windings(status_t*status, segrange_t*range) end = actlist_right(status->actlist, end); while(s!=end) { #ifndef CHECK - if(s->changed) + if(s->changed) #endif { segment_t* left = actlist_left(status->actlist, s); @@ -807,7 +801,7 @@ static void recalculate_windings(status_t*status, segrange_t*range) fprintf(stderr, "[%d] %s/%d/%s/%s ", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit"); #endif } - s = actlist_right(status->actlist, s); + s = s->right; } #ifdef DEBUG fprintf(stderr, "\n"); @@ -825,8 +819,13 @@ void intersect_with_horizontal(status_t*status, segment_t*h) xrow_add(status->xrow, h->a.x); point_t o = h->a; - left = actlist_right(status->actlist, left); - right = actlist_right(status->actlist, right); + if(!right) { + assert(!left); + return; + } + + left = actlist_right(status->actlist, left); //first seg to the right of h->a + right = right->right; //first seg to the right of h->b segment_t* s = left; while(s!=right) { @@ -845,7 +844,7 @@ void intersect_with_horizontal(status_t*status, segment_t*h) assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x); xrow_add(status->xrow, x); - s = actlist_right(status->actlist, s); + s = s->right; } } diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index 6e4c7e4..b967567 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -5,7 +5,7 @@ #include "../q.h" //#define DEBUG -//#define CHECKS +#define CHECKS typedef enum {DIR_UP, DIR_DOWN} segment_dir_t; typedef enum {EVENT_CROSS, EVENT_END, EVENT_CORNER, EVENT_START, EVENT_HORIZONTAL} eventtype_t; @@ -81,10 +81,7 @@ typedef struct _segment { #define XPOS_INT(s,ypos) ((int)ceil(XPOS((s),ypos))) #define XDIFF(s1,s2,ypos) (((s1)->k + (double)(s1)->delta.x*ypos)*(s2)->delta.y - \ - ((s2)->k + (double)(s1)->delta.x*ypos)*(s1)->delta.y) - -// rewrite as XDIFF==0? -#define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos))) + ((s2)->k + (double)(s2)->delta.x*ypos)*(s1)->delta.y) typedef struct _gfxpoly { double gridsize; diff --git a/lib/gfxpoly/renderpoly.c b/lib/gfxpoly/renderpoly.c index 06440fa..9e3c593 100644 --- a/lib/gfxpoly/renderpoly.c +++ b/lib/gfxpoly/renderpoly.c @@ -36,10 +36,10 @@ static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t 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; + if(y >= buf->bbox.ymax || y < buf->bbox.ymin) + return; + renderline_t*l = &buf->lines[y-buf->bbox.ymin]; if(l->num == l->size) { @@ -130,7 +130,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi int width8 = (buf->width+7) >> 3; unsigned char* image = (unsigned char*)malloc(width8*buf->height); memset(image, 0, width8*buf->height); - + buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t)); int y; for(y=0;yheight;y++) { @@ -152,18 +152,18 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi int num = buf->lines[y].num; qsort(points, num, sizeof(renderpoint_t), compare_renderpoints); int lastx = 0; - + windstate_t fill = rule->start(1); for(n=0;nx - bbox->xmin); - + if(x < lastx) - x = lastx; - if(x > buf->width) { - break; - } - if(fill.is_filled && x!=lastx) { + x = lastx; + if(x > buf->width) + x = buf->width; + + if(fill.is_filled && lastxadd(fill, p->fs, p->dir, p->polygon_nr); @@ -232,7 +232,7 @@ intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom) if(x2 > b.xmax) b.xmax = x2; 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)) diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c index 4ab1004..888e4d6 100644 --- a/lib/gfxpoly/test.c +++ b/lib/gfxpoly/test.c @@ -137,7 +137,7 @@ int test0() gfxpoly_destroy(poly); } -int test1() +int test1(int argn, char*argv[]) { gfxline_t*box1 = gfxline_makerectangle(50,50,150,150); // put box2 and box3 on top of each other *snicker* @@ -202,7 +202,7 @@ int test_square(int width, int height, int num, double gridsize, char bitmaptest gfxpoly_destroy(poly); } -int test2() +int test2(int argn, char*argv[]) { test_square(400,400, 3, 0.05, 1); @@ -216,7 +216,7 @@ int test2() } #include "../rfxswf.h" -void test3() +void test3(int argn, char*argv[]) { #undef N #undef RANGE @@ -320,7 +320,7 @@ void test3() } #include -void test4() +void test4(int argn, char*argv[]) { char*dir = "ps"; DIR*_dir = opendir(dir); @@ -333,10 +333,18 @@ void test4() if(!strstr(file->d_name, ".ps")) continue; - char* filename = allocprintf("%s/%s", dir, file->d_name); + char* filename; + + if(argn<2) + filename = allocprintf("%s/%s", dir, file->d_name); + else + filename = argv[1]; + windrule_t*rule = &windrule_evenodd; gfxpoly_t*poly = gfxpoly_from_file(filename, 1.0);//0.01); - free(filename); + + if(argn!=2) + free(filename); double zoom = 1.0; intbbox_t bbox = intbbox_from_polygon(poly, zoom); @@ -357,8 +365,14 @@ void test4() save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png"); assert(!"bitmaps don't match"); } + free(bitmap1); + free(bitmap2); + gfxpoly_destroy(poly); gfxpoly_destroy(poly2); + if(argn==2) + break; } + closedir(_dir); } #include "../gfxdevice.h" @@ -376,16 +390,16 @@ void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color) } windrule_t*rule = &windrule_evenodd; - gfxpoly_t*poly2 = gfxpoly_process(poly, rule); double zoom = 1.0; intbbox_t bbox = intbbox_from_polygon(poly, zoom); unsigned char*bitmap1 = render_polygon(poly, &bbox, zoom, rule); - unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd); if(!bitmap_ok(&bbox, bitmap1)) { printf("bad polygon or error in renderer\n"); return; } + gfxpoly_t*poly2 = gfxpoly_process(poly, rule); + unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd); if(!bitmap_ok(&bbox, bitmap2)) { save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png"); assert(!"error in bitmap"); @@ -394,6 +408,8 @@ void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color) save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png"); assert(!"bitmaps don't match"); } + free(bitmap1); + free(bitmap2); gfxpoly_destroy(poly); gfxpoly_destroy(poly2); @@ -454,8 +470,9 @@ finish: 0, internal: 0 }; -void test5() +void test5(int argn, char*argv[]) { + gfxsource_t*driver = gfxsource_pdf_create(); char*dir = "pdfs"; DIR*_dir = opendir(dir); if(!_dir) return; @@ -468,7 +485,6 @@ void test5() continue; char* filename = allocprintf("%s/%s", dir, file->d_name); - gfxsource_t*driver = gfxsource_pdf_create(); gfxdocument_t*doc = driver->open(driver, filename); gfxdevice_t*out = &extract_polygons; int t; @@ -477,13 +493,15 @@ void test5() gfxpage_t* page = doc->getpage(doc, t); page->render(page, out); page->destroy(page); - break; } + doc->destroy(doc); free(filename); } + closedir(_dir); + driver->destroy(driver); } -int main() +int main(int argn, char*argv[]) { - test3(); + test5(argn, argv); } -- 1.7.10.4