From: Matthias Kramm Date: Thu, 21 May 2009 01:55:36 +0000 (-0700) Subject: started rewriting polygon conversion functions X-Git-Tag: polyok~1 X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=commitdiff_plain;h=3513ae007a04da02f11cdca9f0d08ddda9eac245 started rewriting polygon conversion functions --- diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile index 326c8c6..3af0dda 100644 --- a/lib/gfxpoly/Makefile +++ b/lib/gfxpoly/Makefile @@ -1,6 +1,8 @@ all: test +include ../../Makefile.common CC = gcc -g -O2 +#CC = gcc -O3 ../libbase.a: ../q.c ../q.h ../mem.c ../mem.h cd ..; make libbase.a @@ -31,9 +33,9 @@ renderpoly.o: renderpoly.c wind.h poly.h renderpoly.h xrow.o: xrow.c xrow.h ../q.h ../mem.h $(CC) -c xrow.c -o xrow.o -SWF = ../librfxswf.a ../libpdf.a ../libgfx.a -lstdc++ -lfontconfig +SWF = ../librfxswf.a ../libpdf.a ../libgfx.a -lstdc++ test: ../libbase.a ../libgfx.a test.c $(OBJS) poly.h convert.h - $(CC) test.c $(OBJS) $(SWF) ../libbase.a ../libgfx.a -o test -lm -lz -ljpeg -lfreetype + $(CC) test.c $(OBJS) $(SWF) ../libbase.a ../libgfx.a -o test $(LIBS) clean: rm -f *.o test diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index 0e458be..5619f79 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -18,24 +18,22 @@ static edge_t*edge_new(int x1, int y1, int x2, int y2) return s; } -static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, double _x2, double _y2) +static inline int32_t convert_coord(double x) { /* we clamp to 31 bit instead of 32 bit because we use a (x1-x2) shortcut when comparing coordinates */ - if(_x1 < -0x40000000) _x1 = -0x40000000; - if(_x1 > 0x3fffffff) _x1 = 0x3fffffff; - if(_y1 < -0x40000000) _y1 = -0x40000000; - if(_y1 > 0x3fffffff) _y1 = 0x3fffffff; - if(_x2 < -0x40000000) _x2 = -0x40000000; - if(_x2 > 0x3fffffff) _x2 = 0x3fffffff; - if(_y2 < -0x40000000) _y2 = -0x40000000; - if(_y2 > 0x3fffffff) _y2 = 0x3fffffff; + if(x < -0x40000000) x = -0x40000000; + if(x > 0x3fffffff) x = 0x3fffffff; + return ceil(x); +} - int x1 = ceil(_x1); - int y1 = ceil(_y1); - int x2 = ceil(_x2); - int y2 = ceil(_y2); +static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, double _x2, double _y2) +{ + int x1 = convert_coord(_x1); + int y1 = convert_coord(_y1); + int x2 = convert_coord(_x2); + int y2 = convert_coord(_y2); if(x1!=x2 || y1!=y2) { edge_t*s = edge_new(x1, y1, x2, y2); @@ -44,20 +42,17 @@ static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, doub } } -gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize) +static void convert_gfxline(gfxline_t*line, void*data, void(*moveto)(void*data, double x, double y), void(*lineto)(void*data, double x, double y), void(*setgridsize)(void*data, double g)) { - gfxpoly_t*p = gfxpoly_new(gridsize); - - double z = 1.0 / gridsize; - - double lastx=0, lasty=0; assert(!line || line[0].type == gfx_moveTo); + double lastx=0,lasty=0; while(line) { - double x = line->x*z; - double y = line->y*z; if(line->type == gfx_moveTo) { + if(line->next && line->next->type != gfx_moveTo && (line->x!=lastx || line->y!=lasty)) { + moveto(data, line->x, line->y); + } } else if(line->type == gfx_lineTo) { - gfxpoly_add_edge(p, lastx, lasty, x, y); + lineto(data, line->x, line->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); @@ -66,35 +61,18 @@ gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize) int i; for(i=0;ix*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(p, lastx, lasty, sx, sy); - lastx = sx; - lasty = sy; + double sx = (line->x*t*t + 2*line->sx*t*(1-t) + lastx*(1-t)*(1-t)); + double sy = (line->y*t*t + 2*line->sy*t*(1-t) + lasty*(1-t)*(1-t)); + lineto(data, sx, sy); } - gfxpoly_add_edge(p, lastx, lasty, x, y); + lineto(data, line->x, line->y); } - lastx = x; - lasty = y; + lastx = line->x; + lasty = line->y; line = line->next; } - - gfxline_free(line); - return p; } -typedef struct _gfxstroke { - segment_dir_t dir; - point_t*stroke; - fillstyle_t*fs; - int num_points; -} gfxstroke_t; -typedef struct _gfxcompactpoly { - double gridsize; - int num_strokes; - gfxstroke_t strokes[0]; -} gfxcompactpoly_t; - static char* readline(FILE*fi) { char c; @@ -117,16 +95,11 @@ static char* readline(FILE*fi) } } -gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize) +static void convert_file(const char*filename, void*data, void(*moveto)(void*data, double x, double y), void(*lineto)(void*data, double x, double y),void(*setgridsize)(void*data, double gridsize)) { - gfxpoly_t*p = gfxpoly_new(gridsize); - - double z = 1.0 / gridsize; - FILE*fi = fopen(filename, "rb"); if(!fi) { perror(filename); - return 0; } int count = 0; double g = 0; @@ -138,28 +111,187 @@ gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize) 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")) { + moveto(data, x, y); count++; } else if(s && !strcmp(s,"lineto")) { - gfxpoly_add_edge(p, lastx, lasty, x, y); + lineto(data, x, y); count++; } else { - printf("invalid command: %s\n", s); + fprintf(stderr, "invalid command: %s\n", s); } - lastx = x; - lasty = y; } else if(sscanf(line, "%% gridsize %lf", &g) == 1) { - p->gridsize = g; + setgridsize(data, g); } free(line); } fclose(fi); if(g) { - printf("loaded %d points from %s (gridsize %f)\n", count, filename, g); + fprintf(stderr, "loaded %d points from %s (gridsize %f)\n", count, filename, g); } else { - printf("loaded %d points from %s\n", count, filename); + fprintf(stderr, "loaded %d points from %s\n", count, filename); } - return p; } + +typedef struct _stdpoly { + gfxpoly_t*poly; + double lastx,lasty; + double z; +} stdpoly_t; +static void stdmoveto(void*data, double x, double y) +{ + stdpoly_t*d = (stdpoly_t*)data; + x *= d->z; + y *= d->z; + d->lastx = x;d->lasty = y; +} +static void stdlineto(void*data, double x, double y) +{ + stdpoly_t*d = (stdpoly_t*)data; + x *= d->z; + y *= d->z; + gfxpoly_add_edge(d->poly, d->lastx, d->lasty, x, y); + d->lastx = x;d->lasty = y; +} +static void stdsetgridsize(void*data, double gridsize) +{ + stdpoly_t*d = (stdpoly_t*)data; + d->poly->gridsize = gridsize; +} +gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize) +{ + stdpoly_t data; + data.poly = gfxpoly_new(gridsize); + data.z = 1.0 / gridsize; + data.lastx = data.lasty = 0; + convert_gfxline(line, &data, stdmoveto, stdlineto, stdsetgridsize); + return data.poly; +} +gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize) +{ + stdpoly_t data; + data.poly = gfxpoly_new(gridsize); + data.z = 1.0 / gridsize; + data.lastx = data.lasty = 0; + convert_file(filename, &data, stdmoveto, stdlineto, stdsetgridsize); + return data.poly; +} + +typedef struct _compactpoly { + gfxcompactpoly_t*poly; + point_t last; + double z; + int strokes_size; + point_t*points; + int num_points; + int points_size; + segment_dir_t dir; +} compactpoly_t; + +void add_segment(compactpoly_t*data, point_t start, segment_dir_t dir) +{ + if(data->poly->num_strokes == data->strokes_size) { + data->strokes_size <<= 1; + assert(data->strokes_size > data->poly->num_strokes); + data->poly->strokes = rfx_realloc(data->poly->strokes, data->strokes_size); + } + data->poly->strokes[data->poly->num_strokes].dir = dir; + data->points[0] = start; + data->num_points = 1; + data->dir = dir; +} +void finish_segment(compactpoly_t*data) +{ + if(data->num_points <= 1) + return; + point_t*p = malloc(sizeof(point_t)*data->num_points); + data->poly->strokes[data->poly->num_strokes-1].points = p; + if(data->dir == DIR_UP) { + int t; + int s = data->num_points; + for(t=0;tnum_points;t++) { + p[--s] = data->points[t]; + } + } else { + memcpy(p, data->points, sizeof(point_t)*data->num_points); + } + data->poly->num_strokes++; +} +static void compactmoveto(void*_data, double _x, double _y) +{ + compactpoly_t*data = (compactpoly_t*)_data; + data->dir = DIR_UNKNOWN; + point_t p; + p.x = convert_coord(_x); + p.y = convert_coord(_y); + data->last = p; +} +static void compactlineto(void*_data, double _x, double _y) +{ + compactpoly_t*data = (compactpoly_t*)_data; + point_t p; + p.x = convert_coord(_x); + p.y = convert_coord(_y); + if(p.y < data->last.y && data->dir != DIR_UP || + p.y > data->last.y && data->dir != DIR_DOWN) { + data->dir = p.y > data->last.y ? DIR_DOWN : DIR_UP; + finish_segment(data); + add_segment(data, data->last, data->dir); + } + if(data->points_size == data->num_points) { + data->points_size <<= 1; + assert(data->points_size > data->num_points); + data->points = rfx_realloc(data->points, data->points_size); + } + data->points[data->num_points++] = p; +} +static void compactsetgridsize(void*data, double gridsize) +{ + compactpoly_t*d = (compactpoly_t*)data; + d->poly->gridsize = gridsize; +} +static void compactinit(compactpoly_t*data, double gridsize) +{ + data->poly = rfx_calloc(sizeof(gfxcompactpoly_t)); + data->poly->gridsize = gridsize; + data->z = 1.0 / gridsize; + data->last.x = data->last.y = 0; + data->strokes_size = 16; + data->num_points = 0; + data->points_size = 16; + data->points = (point_t*)rfx_alloc(sizeof(point_t)*data->points_size); + data->poly->strokes = (gfxstroke_t*)rfx_alloc(sizeof(gfxstroke_t)*data->strokes_size); +} +static gfxcompactpoly_t*compactfinish(compactpoly_t*data) +{ + finish_segment(data); + data->poly->strokes = rfx_realloc(data->poly->strokes, sizeof(gfxstroke_t)*data->poly->num_strokes); + free(data->points); + return data->poly; +} +gfxcompactpoly_t* gfxcompactpoly_from_gfxline(gfxline_t*line, double gridsize) +{ + compactpoly_t data; + compactinit(&data, gridsize); + data.poly->gridsize = gridsize; + convert_gfxline(line, &data, compactmoveto, compactlineto, compactsetgridsize); + return compactfinish(&data); +} +gfxcompactpoly_t* gfxcompactpoly_from_file(const char*filename, double gridsize) +{ + compactpoly_t data; + compactinit(&data, gridsize); + data.poly->gridsize = gridsize; + convert_file(filename, &data, compactmoveto, compactlineto, compactsetgridsize); + return compactfinish(&data); +} +void gfxcompactpoly_free(gfxcompactpoly_t*poly) +{ + int t; + for(t=0;tnum_strokes;t++) { + free(poly->strokes[t].points); + } + free(poly->strokes); + free(poly); +} + diff --git a/lib/gfxpoly/convert.h b/lib/gfxpoly/convert.h index 93bf980..8ac8a86 100644 --- a/lib/gfxpoly/convert.h +++ b/lib/gfxpoly/convert.h @@ -5,5 +5,9 @@ gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize); gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize); +gfxcompactpoly_t* gfxcompactpoly_from_gfxline(gfxline_t*line, double gridsize); +gfxcompactpoly_t* gfxcompactpoly_from_file(const char*filename, double gridsize); + +void gfxcompactpoly_free(gfxcompactpoly_t*poly); #endif //__poly_convert_h__ diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 7036a61..4bbd776 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -596,7 +596,6 @@ static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y /* we need to calculate the xpos anew (and can't use start coordinate or intersection coordinate), because we need the xpos exactly at the end of this scanline. - TODO: might be faster to use XPOS_COMPARE here (see also _max) */ double x = XPOS(seg, y); if(!range->segmin || xxmin) { @@ -652,7 +651,7 @@ static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, //break; } } - seg = actlist_right(status->actlist, seg); + seg = seg->right; } } segrange_test_segment_min(range, first, y); @@ -691,7 +690,7 @@ static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, //break; } } - seg = actlist_left(status->actlist, seg); + seg = seg->left; } } segrange_test_segment_min(range, last, y); @@ -721,6 +720,7 @@ static void add_points_to_ending_segments(status_t*status, int32_t y) if(status->xrow->num == 1) { // shortcut + assert(seg->b.x == status->xrow->x[0]); point_t p = {status->xrow->x[0], y}; insert_point_into_segment(status, seg, p); } else { @@ -798,7 +798,7 @@ static void recalculate_windings(status_t*status, segrange_t*range) #endif if(end) - end = actlist_right(status->actlist, end); + end = end->right; while(s!=end) { #ifndef CHECKS if(s->changed) @@ -888,12 +888,13 @@ static void event_apply(status_t*status, event_t*e) assert(!dict_contains(status->intersecting_segs, s)); assert(!dict_contains(status->segs_with_point, s)); #endif - segment_t*left = actlist_left(status->actlist, s); - segment_t*right = actlist_right(status->actlist, s); + segment_t*left = s->left; + segment_t*right = s->right; actlist_delete(status->actlist, s); if(left && right) schedule_crossing(status, left, right); + /* schedule segment for xrow handling */ s->left = 0; s->right = status->ending_segments; status->ending_segments = s; break; @@ -906,8 +907,8 @@ static void event_apply(status_t*status, event_t*e) segment_t*s = e->s1; assert(e->p.x == s->a.x && e->p.y == s->a.y); actlist_insert(status->actlist, s->a, s->b, s); - segment_t*left = actlist_left(status->actlist, s); - segment_t*right = actlist_right(status->actlist, s); + segment_t*left = s->left; + segment_t*right = s->right; if(left) schedule_crossing(status, left, s); if(right) @@ -920,10 +921,11 @@ static void event_apply(status_t*status, event_t*e) #ifdef DEBUG event_dump(e); #endif - if(actlist_right(status->actlist, e->s1) == e->s2 && - actlist_left(status->actlist, e->s2) == e->s1) { + if(e->s1->right == e->s2) { + assert(e->s2->left == e->s1); exchange_two(status, e); } else { + assert(e->s2->left != e->s1); #ifdef DEBUG fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr); #endif @@ -999,18 +1001,18 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c assert(xp.x); edge_t*l= malloc(sizeof(edge_t)); l->a.y = l->b.y = y; - /* TODO: strictly speaking we need to draw from low x to high x so that left/right fillstyles add up - (because the horizontal line's fill style controls the area *below* the line) + /* we draw from low x to high x so that left/right fillstyles add up + (because the horizontal line's fill style controls the area *below* the line) */ - l->a.x = x; - l->b.x = e->p.x; + l->a.x = e->p.x; + l->b.x = x; l->next = poly->edges; poly->edges = l; #ifdef CHECKS /* the output should always be intersection free polygons, so check this horizontal line isn't hacking through any segments in the active list */ - segment_t* start = actlist_find(actlist, l->a, l->a); - segment_t* s = actlist_find(actlist, l->b, l->b); + segment_t* start = actlist_find(actlist, l->b, l->b); + segment_t* s = actlist_find(actlist, l->a, l->a); while(s!=start) { assert(s->a.y == y || s->b.y == y); s = s->left; @@ -1020,7 +1022,6 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c segment_t*left = 0; segment_t*s = e->s1; - windstate_t before,after; switch(e->type) { case EVENT_START: { assert(e->p.x == s->a.x && e->p.y == s->a.y); @@ -1032,17 +1033,11 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c e.s2 = 0; heap_put(queue, &e); left = actlist_left(actlist, s); - - before = left?left->wind:windrule->start(context); - after = s->wind = windrule->add(context, before, s->fs, s->dir, s->polygon_nr); break; } case EVENT_END: { left = actlist_left(actlist, s); actlist_delete(actlist, s); - - before = s->wind; - after = left?left->wind:windrule->start(context); break; } default: assert(0); diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index 2ea3ff4..ff623d3 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -8,7 +8,7 @@ #define CHECKS #define SPLAY -typedef enum {DIR_UP, DIR_DOWN} segment_dir_t; +typedef enum {DIR_UP, DIR_DOWN, DIR_UNKNOWN} segment_dir_t; typedef enum {EVENT_CROSS, EVENT_END, EVENT_CORNER, EVENT_START, EVENT_HORIZONTAL} eventtype_t; typedef enum {SLOPE_POSITIVE, SLOPE_NEGATIVE} slope_t; @@ -105,6 +105,18 @@ typedef struct _gfxpoly { edge_t*edges; } gfxpoly_t; +typedef struct _gfxstroke { + segment_dir_t dir; + int num_points; + point_t*points; + fillstyle_t*fs; +} gfxstroke_t; +typedef struct _gfxcompactpoly { + double gridsize; + int num_strokes; + gfxstroke_t*strokes; +} gfxcompactpoly_t; + void gfxpoly_fail(char*expr, char*file, int line, const char*function); gfxpoly_t* gfxpoly_new(double gridsize); diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c index 892798a..6a41566 100644 --- a/lib/gfxpoly/test.c +++ b/lib/gfxpoly/test.c @@ -135,6 +135,7 @@ int test0() gfxline_transform(b, &m); gfxpoly_t*poly = gfxpoly_from_gfxline(b, 0.05); + gfxline_free(b); gfxpoly_t*poly2 = gfxpoly_process(poly, &windrule_evenodd, &onepolygon); gfxpoly_destroy(poly2); gfxpoly_destroy(poly); @@ -408,6 +409,8 @@ void test4(int argn, char*argv[]) void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color) { + gfxcompactpoly_t*c = gfxcompactpoly_from_gfxline(line, 0.05); + gfxcompactpoly_free(c); gfxpoly_t*poly = gfxpoly_from_gfxline(line, 0.05); if(gfxpoly_size(poly)>100000) { printf("%d segments (skipping)\n", gfxpoly_size(poly)); @@ -536,5 +539,5 @@ void test5(int argn, char*argv[]) int main(int argn, char*argv[]) { - test3(argn, argv); + test5(argn, argv); }