X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fgfxpoly%2Fpoly.c;h=7eb6509c62c745f1a9a09db2b8aeeda2342d91d7;hp=226584ad199921d1f79abd7d82ad1201ebeb4203;hb=83aa304f14f03d1a214817fa3af43dda74436415;hpb=34ea6c36c2a3377546d0e8038f0d4f43b5e3cb6f diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 226584a..7eb6509 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -3,7 +3,6 @@ #include #include "../mem.h" #include "../types.h" -#include "../q.h" #include "../MD5.h" #include "poly.h" #include "active.h" @@ -20,7 +19,7 @@ void gfxpoly_fail(char*expr, char*file, int line, const char*function) exit(1); } - void*md5 = init_md5(); + void*md5 = initialize_md5(); int s,t; gfxpolystroke_t*stroke = current_polygon->strokes; @@ -69,7 +68,7 @@ static void point_free(void*o) p->y = 0; free(p); } -static type_t point_type = { +type_t point_type = { equals: point_equals, hash: point_hash, dup: point_dup, @@ -146,6 +145,15 @@ typedef struct _status { } status_t; +int gfxpoly_num_segments(gfxpoly_t*poly) +{ + gfxpolystroke_t*stroke = poly->strokes; + int count = 0; + for(;stroke;stroke=stroke->next) { + count++; + } + return count; +} int gfxpoly_size(gfxpoly_t*poly) { int s,t; @@ -159,10 +167,17 @@ int gfxpoly_size(gfxpoly_t*poly) char gfxpoly_check(gfxpoly_t*poly) { + current_polygon = poly; dict_t*d = dict_new2(&point_type); int s,t; gfxpolystroke_t*stroke = poly->strokes; for(;stroke;stroke=stroke->next) { + /* In order to not confuse the fill/wind logic, existing segments must have + a non-zero edge style */ + assert(stroke->fs); + + /* put all the segments into dictionaries so that we can check + that the endpoint multiplicity is two */ for(s=0;snum_points;s++) { point_t p = stroke->points[s]; int num = (s>=1 && snum_points-1)?2:1; // mid points are two points (start+end) @@ -179,9 +194,9 @@ char gfxpoly_check(gfxpoly_t*poly) 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); + fprintf(stderr, "Point (%d,%d) occurs %d times\n", p->x, p->y, count); dict_destroy(d); - return 0; + assert(count%2 == 0); } } dict_destroy(d); @@ -192,15 +207,24 @@ void gfxpoly_dump(gfxpoly_t*poly) { int s,t; double g = poly->gridsize; - fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize); + fprintf(stderr, "polyon %p (gridsize: %f)\n", poly, poly->gridsize); gfxpolystroke_t*stroke = poly->strokes; for(;stroke;stroke=stroke->next) { - fprintf(stderr, "%08x", stroke); - for(s=0;snum_points-1;s++) { - point_t a = stroke->points[s]; - point_t b = stroke->points[s+1]; - fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g, - s==stroke->num_points-2?"]":""); + fprintf(stderr, "%11p", stroke); + if(stroke->dir==DIR_UP) { + for(s=stroke->num_points-1;s>=1;s--) { + point_t a = stroke->points[s]; + point_t b = stroke->points[s-1]; + fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s%s\n", s!=stroke->num_points-1?" ":"", a.x*g, a.y*g, b.x*g, b.y*g, + s==1?"]":"", a.y==b.y?"H":""); + } + } else { + for(s=0;snum_points-1;s++) { + point_t a = stroke->points[s]; + point_t b = stroke->points[s+1]; + fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g, + s==stroke->num_points-2?"]":"", a.y==b.y?"H":""); + } } } } @@ -239,26 +263,26 @@ inline static void event_free(event_t*e) static void event_dump(event_t*e) { if(e->type == EVENT_HORIZONTAL) { - fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y); + fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", (int)e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y); } else if(e->type == EVENT_START) { - fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y); + fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y); } else if(e->type == EVENT_END) { - fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y); + fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y); } else if(e->type == EVENT_CROSS) { - fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y); + fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", (int)e->s1->nr, (int)e->s2->nr, e->p.x, e->p.y); } else { assert(0); } } -static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;} -static inline min32(int32_t v1, int32_t v2) {return v1v2?v1:v2;} +static inline int32_t min32(int32_t v1, int32_t v2) {return v1(%d,%d) ", s->nr, 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, - (double)s->delta.x / s->delta.y); + fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y); + fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k, + (double)s->delta.x / s->delta.y, s->fs); } static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr, segment_dir_t dir) @@ -296,6 +320,11 @@ static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_ s->nr = segment_count++; #ifdef CHECKS + /* notice: on some systems (with some compilers), for the line + (1073741823,-1073741824)->(1073741823,1073741823) + we get LINE_EQ(s->a, s) == 1. + That's why we now clamp to 26 bit. + */ assert(LINE_EQ(s->a, s) == 0); assert(LINE_EQ(s->b, s) == 0); @@ -347,13 +376,14 @@ static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*strok while(pos < stroke->num_points-1) { assert(stroke->points[pos].y <= stroke->points[pos+1].y); s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir); + s->fs = stroke->fs; pos++; s->stroke = 0; s->stroke_pos = 0; #ifdef DEBUG /*if(l->tmp) s->nr = l->tmp;*/ - fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %08x, %d more to come)\n", + fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %p, %d more to come)\n", s->nr, s->a.x, s->a.y, s->b.x, s->b.y, s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos); #endif @@ -371,10 +401,6 @@ static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*strok } } if(s) { -#ifdef DEBUG - fprintf(stderr, "attaching contingency of stroke %08x to segment [%d] %s\n", - stroke, s, s->delta.y?"":"(horizontal)"); -#endif s->stroke = stroke; s->stroke_pos = pos; } @@ -648,9 +674,8 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p) 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 - /* XXX we probably will never output circular/anticircular polygons, but if - we do, we would need to set the segment direction here */ - fillstyle_t*fs = s->fs_out; + edgestyle_t*fs = s->fs_out; + segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP; // omit horizontal lines if(s->pos.y != p.y) { @@ -659,15 +684,17 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p) assert(a.y != b.y); gfxpolystroke_t*stroke = status->strokes; + /* find a stoke to attach this segment to. It has to have an endpoint + matching our start point, and a matching edgestyle */ while(stroke) { point_t p = stroke->points[stroke->num_points-1]; - if(p.x == a.x && p.y == a.y && stroke->fs == fs) + if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir) break; stroke = stroke->next; } if(!stroke) { stroke = rfx_calloc(sizeof(gfxpolystroke_t)); - stroke->dir = DIR_DOWN; + stroke->dir = dir; stroke->fs = fs; stroke->next = status->strokes; status->strokes = stroke; @@ -676,6 +703,7 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p) stroke->points[0] = a; stroke->num_points = 1; } else if(stroke->num_points == stroke->points_size) { + assert(stroke->fs); stroke->points_size *= 2; stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size); } @@ -903,7 +931,7 @@ static void recalculate_windings(status_t*status, segrange_t*range) s = range->segmin; #endif #ifdef CHECKS - /* test sanity: check that we don't have changed segments + /* test sanity: verify that we don't have changed segments outside of the given range */ s = actlist_leftmost(status->actlist); while(s && s!=range->segmin) { @@ -916,7 +944,7 @@ static void recalculate_windings(status_t*status, segrange_t*range) 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 */ + that all polygons where the edgestyle changed also have seg->changed=1 */ s = actlist_leftmost(status->actlist); end = 0; #endif @@ -931,11 +959,12 @@ static void recalculate_windings(status_t*status, segrange_t*range) segment_t* left = actlist_left(status->actlist, s); windstate_t wind = left?left->wind:status->windrule->start(status->context); s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr); - fillstyle_t*fs_old = s->fs_out; + edgestyle_t*fs_old = s->fs_out; s->fs_out = status->windrule->diff(&wind, &s->wind); #ifdef DEBUG - fprintf(stderr, "[%d] %s/%d/%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit", + fprintf(stderr, "[%d] dir=%s wind=%d wind.filled=%s fs_old/new=%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", + fs_old?"draw":"omit", s->fs_out?"draw":"omit", fs_old!=s->fs_out?"CHANGED":""); #endif assert(!(!s->changed && fs_old!=s->fs_out)); @@ -1085,7 +1114,7 @@ static void check_status(status_t*status) s->pos.y != s->b.y) && !dict_contains(status->segs_with_point, s)) { fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n", - s->nr, + SEGNR(s), s->delta.x<0?"-":"+", status->y); assert(0); @@ -1117,7 +1146,6 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c while(e) { int32_t y = e->p.y; int32_t x = 0; - char fill = 0; #ifdef DEBUG fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y); actlist_dump(actlist, y-1); @@ -1125,8 +1153,15 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c #ifdef CHECKS actlist_verify(actlist, y-1); #endif + edgestyle_t*fill = 0; + char dir_up = 0; + char dir_down = 0; + do { + assert(e->s1->fs); if(fill && x != e->p.x) { + assert(!dir_up || !dir_down); + assert(dir_up || dir_down); #ifdef DEBUG fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x); #endif @@ -1138,8 +1173,8 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c stroke->num_points = 2; stroke->points = malloc(sizeof(point_t)*2); - stroke->dir = DIR_UP; // FIXME - stroke->fs = 0; + stroke->dir = dir_up?DIR_UP:DIR_DOWN; + stroke->fs = fill; point_t a,b; a.y = b.y = y; /* we draw from low x to high x so that left/right fillstyles add up @@ -1151,7 +1186,7 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c stroke->points[1] = b; #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 */ + line isn't puncturing any segments in the active list */ segment_t* start = actlist_find(actlist, b, b); segment_t* s = actlist_find(actlist, a, a); while(s!=start) { @@ -1160,9 +1195,10 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c } #endif } + + segment_t*s = e->s1; + segment_t*left = 0; - segment_t*s = e->s1; - switch(e->type) { case EVENT_START: { assert(e->p.x == s->a.x && e->p.y == s->a.y); @@ -1174,19 +1210,50 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c e->s2 = 0; hqueue_put(&hqueue, e); left = actlist_left(actlist, s); + if(e->s1->dir==DIR_UP) + dir_up^=1; + else + dir_down^=1; break; } case EVENT_END: { left = actlist_left(actlist, s); actlist_delete(actlist, s); advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos); + if(e->s1->dir==DIR_DOWN) + dir_up^=1; + else + dir_down^=1; break; } default: assert(0); } x = e->p.x; - fill ^= 1;//(before.is_filled != after.is_filled); + + fill = fill?0:&edgestyle_default; +#if 0 + if(windrule==&windrule_evenodd) { + if(!!fill != !!fill2) { + segment_dump(s); + event_dump(e); + printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill); + if(e->type==EVENT_END) { + printf(" %9p\n", s->fs); + printf(" |\n"); + } + printf(" %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled); + printf("%12p -----+----- %p\n", old_fill, fill2); + printf(" %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled); + if(e->type==EVENT_START) { + printf(" |\n"); + printf(" %9p\n", s->fs); + } + } + assert(!!fill == !!fill2); + } +#endif + #ifdef DEBUG fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n", y, e->type==EVENT_START?"start":"end", @@ -1202,21 +1269,28 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c e = hqueue_get(&hqueue); } while(e && y == e->p.y); - assert(!fill); // check that polygon is not bleeding +#ifdef CHECKS + edgestyle_t*bleeding = fill; + assert(!bleeding); +#endif } actlist_destroy(actlist); hqueue_destroy(&hqueue); } -gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context) +gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context) { - current_polygon = poly; + current_polygon = poly1; status_t status; memset(&status, 0, sizeof(status_t)); queue_init(&status.queue); - gfxpoly_enqueue(poly, &status.queue, 0, /*polygon nr*/0); + gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0); + if(poly2) { + assert(poly1->gridsize == poly2->gridsize); + gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1); + } status.windrule = windrule; status.context = context; @@ -1231,6 +1305,7 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*co event_t*e = queue_get(&status.queue); while(e) { + assert(e->s1->fs); status.y = e->p.y; #ifdef CHECKS assert(status.y>=lasty); @@ -1279,10 +1354,30 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*co xrow_destroy(status.xrow); gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t)); - p->gridsize = poly->gridsize; + p->gridsize = poly1->gridsize; p->strokes = status.strokes; - gfxpoly_dump(p); +#ifdef CHECKS + /* we only add segments with non-empty edgestyles to strokes in + recalculate_windings, but better safe than sorry */ + gfxpolystroke_t*stroke = p->strokes; + while(stroke) { + assert(stroke->fs); + stroke = stroke->next; + } +#endif + add_horizontals(p, &windrule_evenodd, context); // output is always even/odd + //add_horizontals(p, windrule, context); return p; } + +static windcontext_t twopolygons = {2}; +gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2) +{ + return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons); +} +gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2) +{ + return gfxpoly_process(p1, p2, &windrule_union, &twopolygons); +}