X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fgfxpoly%2Fpoly.c;h=97289892b1b3359a69707bdd01f961c3f4afa12c;hp=23039445a5f6b01d14cbe7eff554fa25a4d961ac;hb=bf04757cd94e94c1f67fa3d2a4e3e59fa5bce0c0;hpb=e5ec9f136f070b7e824e223c0b67e28efd8c70f0 diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 2303944..9728989 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -3,27 +3,29 @@ #include #include #include "../mem.h" +#include "../types.h" #include "../q.h" #include "poly.h" #include "active.h" #include "xrow.h" +#include "wind.h" //#define DEBUG //#undef assert -//#define assert(x) +//#define assert(x) -char point_equals(const void*o1, const void*o2) +char point_equals(const void*o1, const void*o2) { const point_t*p1 = o1; const point_t*p2 = o2; return p1->x == p2->x && p1->y == p2->y; } -unsigned int point_hash(const void*o) +unsigned int point_hash(const void*o) { const point_t*p = o; return p->x^p->y; } -void* point_dup(const void*o) +void* point_dup(const void*o) { const point_t*p = o; point_t*n = malloc(sizeof(point_t)); @@ -31,7 +33,7 @@ void* point_dup(const void*o) n->y = p->y; return n; } -void point_free(void*o) +void point_free(void*o) { point_t*p = o; p->x = 0; @@ -47,10 +49,12 @@ type_t point_type = { typedef struct _status { int y; + int num_polygons; actlist_t*actlist; heap_t*queue; edge_t*output; xrow_t*xrow; + windrule_t*windrule; #ifdef DEBUG dict_t*seen_crossings; //list of crossing we saw so far dict_t*intersecting_segs; //list of segments intersecting in this scanline @@ -58,21 +62,14 @@ typedef struct _status { #endif } status_t; -int compare_events(const void*_a,const void*_b) +int compare_events_simple(const void*_a,const void*_b) { event_t* a = (event_t*)_a; - event_t* b = (event_t*)_b; + event_t* b = (event_t*)_b; if(a->p.y < b->p.y) { return 1; } else if(a->p.y > b->p.y) { return -1; - /* we should schedule start events after end/intersect. - The order of end/intersect doesn't actually matter, however, - so this might be doing too much */ - } else if(a->type < b->type) { - return 1; - } else if(a->type > b->type) { - return -1; } else if(a->p.x < b->p.x) { return 1; } else if(a->p.x > b->p.x) { @@ -81,25 +78,76 @@ int compare_events(const void*_a,const void*_b) return 0; } -gfxpoly_t* gfxpoly_new() +int compare_events(const void*_a,const void*_b) +{ + event_t* a = (event_t*)_a; + event_t* b = (event_t*)_b; + int d = b->p.y - a->p.y; + if(d) return d; + /* we should schedule start events after end/intersect. + The order of end/intersect doesn't actually matter, however, + so this might be doing too much */ + d = b->type - a->type; + if(d) return d; + d = b->p.x - a->p.x; + return d; +} + +gfxpoly_t* gfxpoly_new(double gridsize) { - return 0; + gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t)); + p->gridsize = gridsize; + return p; } void gfxpoly_destroy(gfxpoly_t*poly) { - edge_t* s = poly; + edge_t* s = poly->edges; while(s) { edge_t*next = s->next; free(s); s = next; } + 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; } } @@ -129,7 +177,7 @@ void event_dump(event_t*e) static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;} static inline min32(int32_t v1, int32_t v2) {return v1dir = DIR_DOWN; @@ -139,7 +187,7 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2) s->dir = DIR_UP; } else { /* up/down for horizontal segments is handled by "rotating" - them 90° anticlockwise in screen coordinates (tilt your head to + them 90° anticlockwise in screen coordinates (tilt your head to the right) */ s->dir = DIR_UP; if(x1>x2) { @@ -157,7 +205,7 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2) s->delta.x = x2-x1; s->delta.y = y2-y1; s->pos = s->a; - s->new_point.y = y1-1; + s->polygon_nr = polygon_nr; #define XDEBUG #ifdef XDEBUG static int segment_count=0; @@ -166,7 +214,7 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2) assert(LINE_EQ(s->a, s) == 0); assert(LINE_EQ(s->b, s) == 0); - + /* check that all signs are in order: a a |\ /| @@ -183,10 +231,10 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2) dict_init2(&s->scheduled_crossings, &ptr_type, 0); } -segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2) +segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr) { segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t)); - segment_init(s, x1, y1, x2, y2); + segment_init(s, x1, y1, x2, y2, initial, polygon_nr); return s; } void segment_destroy(segment_t*s) @@ -195,16 +243,16 @@ void segment_destroy(segment_t*s) free(s); } -void gfxpoly_enqueue(edge_t*list, heap_t*queue) +void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr) { edge_t*l; for(l=list;l;l=l->next) { - if(l->a.x == l->b.x && + if(l->a.x == l->b.x && l->a.y == l->b.y) { fprintf(stderr, "Warning: intersector input contains zero-length segments\n"); continue; } - segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y); + segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr); #ifdef DEBUG fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n", s->nr, s->a.x, s->a.y, s->b.x, s->b.y, @@ -247,7 +295,7 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2) int32_t miny2 = min32(s2->a.y,s2->b.y); int32_t maxx2 = max32(s2->a.x,s2->b.x); int32_t maxy2 = max32(s2->a.y,s2->b.y); - + /* both segments are active, so this can't happen */ assert(!(maxy1 <= miny2 || maxy2 <= miny1)); @@ -257,7 +305,7 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2) /* bounding boxes don't intersect */ return; } - + if(dict_contains(&s1->scheduled_crossings, s2)) { /* FIXME: this whole segment hashing thing is really slow */ //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr); @@ -402,33 +450,36 @@ static inline box_t box_new(int x, int y) return box; } -void insert_point_into_segment(status_t*status, segment_t*s, point_t p) -{ - edge_t*e = malloc(sizeof(edge_t)); - e->a = s->pos; - e->b = p; - assert(e->a.y != e->b.y); - e->next = status->output; - status->output = e; -} -void mark_point_in_segment(status_t*status, segment_t*s, point_t p) +static void insert_point_into_segment(status_t*status, segment_t*s, point_t p) { -#ifdef DEBUG - if(s->pos.x == p.x && s->pos.y == p.y) { - fprintf(stderr, "Error: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr); - } -#endif assert(s->pos.x != p.x || s->pos.y != p.y); + #ifdef DEBUG - fprintf(stderr, "[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y); if(!dict_contains(status->segs_with_point, s)) dict_put(status->segs_with_point, s, 0); #endif - if(s->new_point.y != p.y) { - s->new_point = p; + + assert(s->fs_out_ok); + if(s->fs_out) { +#ifdef DEBUG + fprintf(stderr, "[%d] receives next point (%d,%d) (drawing)\n", s->nr, p.x, p.y); +#endif + // omit horizontal lines + if(s->pos.y != p.y) { + edge_t*e = malloc(sizeof(edge_t)); + e->a = s->pos; + e->b = p; + assert(e->a.y != e->b.y); + e->next = status->output; + status->output = e; + } + } else { +#ifdef DEBUG + fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y); +#endif } - s->new_pos = p; + s->pos = p; } /* possible optimizations: @@ -439,14 +490,14 @@ void mark_point_in_segment(status_t*status, segment_t*s, point_t p) */ /* SLOPE_POSITIVE: - \+ \ + ------- I \I - -I\---- I + \+ \ + +------ I \I + -I\---- I I \ --I\--- I \ I \ ------- + \ + \ */ -static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y) +static void add_points_to_positively_sloped_segments(status_t*status, int32_t y) { int t; for(t=0;txrow->num;t++) { @@ -462,7 +513,7 @@ static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y double d1 = LINE_EQ(box.right1, seg); double d2 = LINE_EQ(box.right2, seg); if(d1>=0 || d2>=0) { - mark_point_in_segment(status, seg, box.right2); + insert_point_into_segment(status, seg, box.right2); } else { break; } @@ -479,7 +530,7 @@ static void mark_points_in_positively_sloped_segments(status_t*status, int32_t y | I | /I / | /+ |/ + / */ -static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y) +static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y) { int t; for(t=status->xrow->num-1;t>=0;t--) { @@ -494,7 +545,7 @@ static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y double d1 = LINE_EQ(box.left1, seg); double d2 = LINE_EQ(box.left2, seg); if(d1<0 || d2<0) { - mark_point_in_segment(status, seg, box.right2); + insert_point_into_segment(status, seg, box.right2); } else { break; } @@ -504,39 +555,56 @@ static void mark_points_in_negatively_sloped_segments(status_t*status, int32_t y } } -static void add_points(status_t*status) +static void recalculate_windings(status_t*status) { /* TODO: we could use some clever second linked list structure so that we - only need to process points which we know we marked */ - int t; + only need to process points we know we marked */ + segment_t*s = actlist_leftmost(status->actlist); + segment_t*last = 0; while(s) { - if(s->new_point.y == status->y) { - insert_point_into_segment(status, s, s->new_point); - s->pos = s->new_pos; - } + windstate_t wind = last?last->wind:status->windrule->start(status->num_polygons); + s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr); + s->fs_out = status->windrule->diff(&wind, &s->wind); + s->fs_out_ok = 1; +#ifdef DEBUG + 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 + last = s; s = actlist_right(status->actlist, s); } +#ifdef DEBUG + fprintf(stderr, "\n"); +#endif + } +/* we need to handle horizontal lines in order to add points to segments + we otherwise would miss during the windrule re-evaluation */ void intersect_with_horizontal(status_t*status, segment_t*h) { segment_t* left = actlist_find(status->actlist, h->a, h->a); segment_t* right = actlist_find(status->actlist, h->b, h->b); - segment_t* s = right; + /* not strictly necessary, also done by the event */ + xrow_add(status->xrow, h->a.x); + point_t o = h->a; + + left = actlist_right(status->actlist, left); + right = actlist_right(status->actlist, right); + segment_t* s = left; - while(s!=left) { + while(s!=right) { assert(s); /* - x1 + ((x2-x1)*(y-y1)) / dy = + x1 + ((x2-x1)*(y-y1)) / dy = (x1*(y2-y) + x2*(y-y1)) / dy */ point_t p; p.y = status->y; p.x = XPOS(s, p.y); #ifdef DEBUG - fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr, + fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr, s->a.x, s->a.y, s->b.x, s->b.y, p.x, p.y @@ -548,9 +616,8 @@ void intersect_with_horizontal(status_t*status, segment_t*h) assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x); xrow_add(status->xrow, p.x); - s = actlist_left(status->actlist, s); + s = actlist_right(status->actlist, s); } - xrow_add(status->xrow, h->a.x); } void event_apply(status_t*status, event_t*e) @@ -595,12 +662,14 @@ void event_apply(status_t*status, event_t*e) schedule_crossing(status, left, s); if(right) schedule_crossing(status, s, right); - schedule_endpoint(status, e->s1); break; } case EVENT_CROSS: { - // exchange two (or more) segments + // exchange two segments +#ifdef DEBUG + event_dump(e); +#endif if(actlist_right(status->actlist, e->s1) == e->s2 && actlist_left(status->actlist, e->s2) == e->s1) { exchange_two(status, e); @@ -627,10 +696,10 @@ void check_status(status_t*status) { DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) { if((s->pos.x != s->b.x || - s->pos.y != s->b.y) && + 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, + fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n", + s->nr, s->delta.x<0?"-":"+", status->y); assert(0); @@ -639,19 +708,114 @@ void check_status(status_t*status) } #endif -edge_t* gfxpoly_process(edge_t*poly) +static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule) +{ + /* + |..| |...........| | | + |..| |...........| | | + |..+ + +..| +--+ +--+ + |...........| |..| | | + |...........| |..| | | + */ + +#ifdef DEBUG + fprintf(stderr, "========================================================================\n"); +#endif + heap_t* queue = heap_new(sizeof(event_t), compare_events_simple); + gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0); + + actlist_t* actlist = actlist_new(); + + event_t*e = heap_chopmax(queue); + while(e) { + int y = e->p.y; + int x = 0; + char fill = 0; +#ifdef DEBUG + actlist_verify_and_dump(actlist, y-1); +#endif + do { + if(fill && x != e->p.x) { +#ifdef DEBUG + fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x); +#endif + edge_t*l= malloc(sizeof(edge_t)); + l->a.y = l->b.y = y; + l->a.x = x; + l->b.x = e->p.x; + l->next = poly->edges; + poly->edges = l; + } + segment_t*left = 0; + segment_t*s = e->s1; + + windstate_t before,after; + switch(e->type) { + case EVENT_START: { + actlist_insert(actlist, e->p, s); + event_t e; + e.type = EVENT_END; + e.p = s->b; + e.s1 = s; + e.s2 = 0; + heap_put(queue, &e); + left = actlist_left(actlist, s); + + before = left?left->wind:windrule->start(1); + after = s->wind = windrule->add(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(1); + break; + } + default: assert(0); + } + + x = e->p.x; + fill ^= 1;//(before.is_filled != after.is_filled); +#ifdef DEBUG + fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n", + y, e->type==EVENT_START?"start":"end", + s->nr, + left?left->nr:-1, + x, + before.is_filled, after.is_filled); +#endif + + if(e->type == EVENT_END) + segment_destroy(s); + + e = heap_chopmax(queue); + } while(e && y == e->p.y); + + if(fill) { + fprintf(stderr, "Error: polygon is bleeding\n"); + exit(0); + } + } +} + +gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule) { heap_t* queue = heap_new(sizeof(event_t), compare_events); - gfxpoly_enqueue(poly, queue); + + gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0); + status_t status; memset(&status, 0, sizeof(status_t)); + status.num_polygons = 1; status.queue = queue; + status.windrule = windrule; status.actlist = actlist_new(); #ifdef DEBUG status.seen_crossings = dict_new2(&point_type); - gfxpoly_dump(poly); #endif - + status.xrow = xrow_new(); event_t*e = heap_chopmax(queue); @@ -665,18 +829,16 @@ edge_t* gfxpoly_process(edge_t*poly) #endif xrow_reset(status.xrow); do { - if(e->type != EVENT_HORIZONTAL) { - xrow_add(status.xrow, e->p.x); - } + xrow_add(status.xrow, e->p.x); event_apply(&status, e); free(e); e = heap_chopmax(queue); } while(e && status.y == e->p.y); xrow_sort(status.xrow); - mark_points_in_positively_sloped_segments(&status, status.y); - mark_points_in_negatively_sloped_segments(&status, status.y); - add_points(&status); + add_points_to_positively_sloped_segments(&status, status.y); + add_points_to_negatively_sloped_segments(&status, status.y); + recalculate_windings(&status); #ifdef DEBUG check_status(&status); dict_destroy(status.intersecting_segs); @@ -690,5 +852,9 @@ edge_t* gfxpoly_process(edge_t*poly) heap_destroy(queue); xrow_destroy(status.xrow); - return status.output; + gfxpoly_t*p = gfxpoly_new(poly->gridsize); + p->edges = status.output; + + add_horizontals(p, &windrule_evenodd); // output is always even/odd + return p; }