From f5626be739a1e1b61f89d7a389be3c4b5d4d9128 Mon Sep 17 00:00:00 2001 From: Matthias Kramm Date: Thu, 23 Apr 2009 20:06:00 +0200 Subject: [PATCH 1/1] many optimizations and bugfixes in the new intersector code --- lib/gfxpoly/Makefile | 18 ++- lib/gfxpoly/active.c | 46 ++----- lib/gfxpoly/active.h | 4 +- lib/gfxpoly/convert.c | 26 ++-- lib/gfxpoly/poly.c | 317 ++++++++++++++++++++++--------------------------- lib/gfxpoly/poly.h | 9 +- lib/gfxpoly/test.c | 107 +++++++++++++++-- lib/gfxpoly/xrow.c | 19 ++- lib/gfxpoly/xrow.h | 2 + lib/q.c | 2 +- lib/rfxswf.c | 19 ++- lib/rfxswf.h | 1 + 12 files changed, 334 insertions(+), 236 deletions(-) diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile index 04d227b..036c5d1 100644 --- a/lib/gfxpoly/Makefile +++ b/lib/gfxpoly/Makefile @@ -1,5 +1,7 @@ all: testheap test +CC = gcc -g -pg + ../libbase.a: ../q.c ../q.h ../mem.c ../mem.h cd ..; make libbase.a @@ -7,19 +9,23 @@ all: testheap test cd ..; make libgfx.a testheap: ../libbase.a testheap.c - gcc -g testheap.c ../libbase.a -o testheap -lm -lz -ljpeg + $(CC) testheap.c ../libbase.a -o testheap -lm -lz -ljpeg active.o: active.c active.h poly.h - gcc -g -c active.c -o active.o + $(CC) -c active.c -o active.o convert.o: convert.c convert.h poly.h - gcc -g -c convert.c -o convert.o + $(CC) -c convert.c -o convert.o poly.o: poly.c poly.h active.h ../q.h - gcc -g -c poly.c -o poly.o + $(CC) -c poly.c -o poly.o xrow.o: xrow.c xrow.h ../q.h ../mem.h - gcc -g -c xrow.c -o xrow.o + $(CC) -c xrow.c -o xrow.o +SWF = ../librfxswf.a test: ../libbase.a ../libgfx.a test.c poly.o convert.o active.o xrow.o poly.h convert.h - gcc -g test.c poly.o convert.o active.o xrow.o ../libbase.a ../libgfx.a -o test -lm -lz -ljpeg -lfreetype + $(CC) test.c poly.o convert.o active.o xrow.o $(SWF) ../libbase.a ../libgfx.a -o test -lm -lz -ljpeg -lfreetype + +clean: + rm -f *.o test diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c index d726a01..56c7b90 100644 --- a/lib/gfxpoly/active.c +++ b/lib/gfxpoly/active.c @@ -7,6 +7,10 @@ actlist_t* actlist_new() NEW(actlist_t, a); return a; } +void actlist_destroy(actlist_t*a) +{ + free(a); +} void actlist_verify_and_dump(actlist_t*a, int32_t y) { @@ -17,23 +21,26 @@ void actlist_verify_and_dump(actlist_t*a, int32_t y) if(y) { double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x; if(s!=a->list) { - if(lastx>x) printf("?%f<->%f? ", lastx, x); + if(lastx>x) fprintf(stderr, "?%f<->%f? ", lastx, x); } lastx = x; } assert(!s->left || s->left->right == s); assert(!s->right || s->right->left == s); - printf("[%d]", s->nr); + fprintf(stderr, "[%d]", s->nr); s = s->right; - if(s) printf(" "); - else printf("\n"); + if(s) fprintf(stderr, " "); + else fprintf(stderr, "\n"); } } segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) { /* this runs in O(n) right now, and should be optimized using a splay - tree to run in ammortized O(log(n)) */ + tree to run in ammortized O(log(n)) + (update: currently only 2.5% of the algorithm's running time is spent here, + so maybe we don't need to bother) + */ segment_t*last=0, *s = a->list; if(!s) return last; while(s) { @@ -110,32 +117,3 @@ void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2) actlist_delete(a, s1); actlist_insert_after(a, s2, s1); } - -void actlist_invert_fromto(actlist_t*a, segment_t*s1, segment_t*s2) -{ - segment_t*left = s1->left; - segment_t*right = s2->right; - segment_t*s = s1; - assert(s!=s2); - while(1) { - assert(s); - segment_t*l = s->left; - segment_t*r = s->right; - s->left = r; - s->right = l; - if(s==s2) - break; - s = r; - } - s2->left = left; - s1->right = right; - if(left) { - left->right = s2; - } else { - assert(a->list == s1); - a->list = s2; - } - if(right) { - right->left = s1; - } -} diff --git a/lib/gfxpoly/active.h b/lib/gfxpoly/active.h index f257f96..911ed63 100644 --- a/lib/gfxpoly/active.h +++ b/lib/gfxpoly/active.h @@ -2,7 +2,7 @@ #define __active_h__ #include "poly.h" -#include "splay.h" +//#include "splay.h" typedef struct _actlist { @@ -11,12 +11,12 @@ typedef struct _actlist } actlist_t; actlist_t* actlist_new(); +void actlist_destroy(actlist_t*a); void actlist_verify_and_dump(actlist_t*a, int32_t y); segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2); // finds segment immediately to the left of p1 (breaking ties w/ p2) void actlist_insert(actlist_t*a, point_t p, segment_t*s); void actlist_delete(actlist_t*a, segment_t*s); void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2); -void actlist_invert_fromto(actlist_t*a, segment_t*s1, segment_t*s2); segment_t* actlist_left(actlist_t*a, segment_t*s); segment_t* actlist_leftmost(actlist_t*a); segment_t* actlist_right(actlist_t*a, segment_t*s); diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index 10171f2..f71a096 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -4,21 +4,33 @@ #include "../gfxdevice.h" #include "poly.h" -static inline void gfxpoly_add_segment(segment_t**list, double _x1, double _y1, double _x2, double _y2) +static edge_t*edge_new(int x1, int y1, int x2, int y2) +{ + edge_t*s = malloc(sizeof(edge_t)); + s->a.x = x1; + s->a.y = y1; + s->b.x = x2; + s->b.y = y2; + s->next = 0; + return s; +} + +static inline void gfxpoly_add_edge(edge_t**list, double _x1, double _y1, double _x2, double _y2) { int x1 = ceil(_x1); int y1 = ceil(_y1); int x2 = ceil(_x2); int y2 = ceil(_y2); if(y1!=y2) { - segment_t*s = segment_new(x1, y1, x2, y2); - segment_insert_before(list, s); + edge_t*s = edge_new(x1, y1, x2, y2); + s->next = *list; + *list = s; } } gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line) { - segment_t*s = 0; + edge_t*s = 0; /* factor that determines into how many line fragments a spline is converted */ double subfraction = 2.4;//0.3 @@ -28,7 +40,7 @@ gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line) while(line) { if(line->type == gfx_moveTo) { } else if(line->type == gfx_lineTo) { - gfxpoly_add_segment(&s, lastx, lasty, line->x, line->y); + gfxpoly_add_edge(&s, lastx, lasty, 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); @@ -39,11 +51,11 @@ gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line) double t = (double)i*stepsize; double x = line->x*t*t + 2*line->sx*t*(1-t) + x*(1-t)*(1-t); double y = line->y*t*t + 2*line->sy*t*(1-t) + y*(1-t)*(1-t); - gfxpoly_add_segment(&s, lastx, lasty, x, y); + gfxpoly_add_edge(&s, lastx, lasty, x, y); lastx = x; lasty = y; } - gfxpoly_add_segment(&s, lastx, lasty, line->x, line->y); + gfxpoly_add_edge(&s, lastx, lasty, line->x, line->y); } lastx = line->x; lasty = line->y; diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 9dc42b0..48e92f9 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -2,12 +2,15 @@ #include #include #include +#include "../mem.h" #include "../q.h" #include "poly.h" #include "active.h" #include "xrow.h" -#define DEBUG +//#define DEBUG +//#undef assert +//#define assert(x) char point_equals(const void*o1, const void*o2) { @@ -46,6 +49,7 @@ typedef struct _status { int y; actlist_t*actlist; heap_t*queue; + edge_t*output; #ifdef DEBUG dict_t*seen_crossings; //list of crossing we saw so far dict_t*intersecting_segs; //list of segments intersecting in this scanline @@ -61,6 +65,9 @@ int compare_events(const void*_a,const void*_b) 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) { @@ -79,26 +86,20 @@ gfxpoly_t* gfxpoly_new() } void gfxpoly_destroy(gfxpoly_t*poly) { - segment_t* s = poly; + edge_t* s = poly; while(s) { - segment_t*right = s->right; + edge_t*next = s->next; free(s); - s = right; - if(s==poly) - break; + s = next; } } void gfxpoly_dump(gfxpoly_t*poly) { - segment_t* s = (segment_t*)poly; + edge_t* s = (edge_t*)poly; while(s) { - printf("[%d] (%d,%d) -> (%d,%d) %s\n", - s->nr, s->a.x, s->a.y, s->b.x, s->b.y, - s->dir==DIR_UP?"up":"down"); - s = s->right; - if(s==poly) - break; + fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y); + s = s->next; } } @@ -112,12 +113,14 @@ inline static event_t event_new() void event_dump(event_t*e) { if(e->type == EVENT_START) { - printf("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", e->s1->nr, e->p.x, e->p.y); } else if(e->type == EVENT_END) { - printf("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", e->s1->nr, e->p.x, e->p.y); } else if(e->type == EVENT_CROSS) { - printf("event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y); - } else assert(0); + fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, 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;} @@ -167,56 +170,57 @@ 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(int x1, int y1, int x2, int y2) +segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2) { - segment_t*s = malloc(sizeof(segment_t)); + segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t)); segment_init(s, x1, y1, x2, y2); return s; } - -void segment_insert_before(segment_t**list, segment_t*add) +void segment_destroy(segment_t*s) { - if(!*list) { - *list = add; - add->left = add->right = add; - } else { - add->left = (*list)->left; - add->right = (*list); - add->right->left = add; - add->left->right = add; - } + dict_clear(&s->scheduled_crossings); + free(s); } -void segments_enqueue(segment_t*list, heap_t*queue) +void gfxpoly_enqueue(edge_t*list, heap_t*queue) { - segment_t*l = list; + edge_t*l = list; while(l) { - segment_t*right = l->right; - l->left = l->right = 0; + segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y); +#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, + s->dir==DIR_UP?"up":"down"); +#endif event_t e = event_new(); e.type = EVENT_START; - e.p = l->a;e.s1 = l;e.s2 = 0; + e.p = s->a; + e.s1 = s; + e.s2 = 0; heap_put(queue, &e); - e.type = EVENT_END; - e.p = l->b;e.s1 = l;e.s2 = 0; - heap_put(queue, &e); - l = right; - if(l==list) break; + l = l->next; } } -void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny) +void schedule_endpoint(status_t*status, segment_t*s) +{ + // schedule end point of segment + assert(s->b.y > status->y); + event_t e; + e.type = EVENT_END; + e.p = s->b; + e.s1 = s; + e.s2 = 0; + heap_put(status->queue, &e); +} + +void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2) { /* the code that's required (and the checks you can perform) before it can be said with 100% certainty that we indeed have a valid crossing amazes me every time. -mk */ assert(s1!=s2); - if(dict_contains(&s1->scheduled_crossings, s2)) { - // we already know about this one - return; - } - /* we probably could precompute these */ int32_t minx1 = min32(s1->a.x,s1->b.x); int32_t miny1 = min32(s1->a.y,s1->b.y); @@ -226,12 +230,22 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny) 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)); + + /* TODO: optimize this. remove y, precompute the two x values */ if(maxx1 <= minx2 || maxx2 <= minx1 || maxy1 <= miny2 || maxy2 <= miny1) { /* bounding boxes don't intersect */ return; } + + if(dict_contains(&s1->scheduled_crossings, s2)) { + // we already know about this one + return; + } + double adx = s1->delta.x; double ady = s1->delta.y; double bdx = s2->delta.x; @@ -240,7 +254,9 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny) if(!det) { if(s1->k == s2->k) { // lines are exactly on top of each other (ignored) +#ifdef DEBUG fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr); +#endif return; } else { /* lines are parallel */ @@ -302,108 +318,29 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny) point_t p; p.x = (int32_t)ceil((-la*bdx +lb*adx) / det); p.y = (int32_t)ceil((+lb*ady -la*bdy) / det); - /* we only schedule crossings if they are *after* the current y. That way, we don't - schedule the same crossing twice */ - if(p.y >= miny) { -#ifdef DEBUG - point_t pair; - pair.x = s1->nr; - pair.y = s2->nr; - assert(!dict_contains(status->seen_crossings, &pair)); - dict_put(status->seen_crossings, &pair, 0); -#endif - event_t e = event_new(); - e.type = EVENT_CROSS; - e.p = p; - e.s1 = s1; - e.s2 = s2; + + assert(p.y >= status->y); #ifdef DEBUG - printf("schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, e.p.x, e.p.y); + point_t pair; + pair.x = s1->nr; + pair.y = s2->nr; + assert(!dict_contains(status->seen_crossings, &pair)); + dict_put(status->seen_crossings, &pair, 0); + fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y); #endif - /* we insert into each other's intersection history because these segments might switch - places */ - dict_put(&s1->scheduled_crossings, s2, 0); - dict_put(&s2->scheduled_crossings, s1, 0); - heap_put(status->queue, &e); - } - return; -} + /* we insert into each other's intersection history because these segments might switch + places and we still want to look them up quickly after they did */ + dict_put(&s1->scheduled_crossings, s2, 0); + dict_put(&s2->scheduled_crossings, s1, 0); -/* routine dealing with the special case of a number of line segments intersecting in exactly one - point */ -void exchange_many(status_t*status, event_t*e) -{ - int size = 16; - int n = 0; - segment_t**segs = (segment_t**)malloc(sizeof(segment_t*)*size); - segs[n] = e->s1;e->s1->tmp = n;n++; - segs[n] = e->s2;e->s2->tmp = n;n++; -#ifdef DEBUG - dict_put(status->intersecting_segs, e->s1, 0); - dict_put(status->intersecting_segs, e->s2, 0); -#endif - while(1) { - event_t*ee = heap_peek(status->queue); - if(ee->p.x != e->p.x || - ee->p.y != e->p.y || - ee->type != e->type) { - break; - } - if(n>=size-1) { - size *= 2; - segs = realloc(segs, sizeof(segment_t*)*size); - } - ee = heap_chopmax(status->queue); - if(ee->s1->tmp<0) { - segs[n] = ee->s1;ee->s1->tmp = n;n++; - } - if(ee->s2->tmp<0) { - segs[n] = ee->s2;ee->s2->tmp = n;n++; - } -#ifdef DEBUG - dict_put(status->intersecting_segs, ee->s1, 0); - dict_put(status->intersecting_segs, ee->s2, 0); -#endif - } - int t; -#ifdef DEBUG - printf("event: multi-intersect: "); - for(t=0;tnr); - } - printf("\n"); -#endif - segment_t*left = 0; - segment_t*right = 0; - char warn = 0; - for(t=0;tleft || segs[t]->left->tmp<0) { - assert(!left); - left = segs[t]; - } - if(!segs[t]->right || segs[t]->right->tmp<0) { - assert(!right); - right = segs[t]; - } - if(segs[t]->tmp<0) - warn = 1; - } - if(warn) - fprintf(stderr, "Warning: multi-cross section contains rogue segments\n"); - - assert(left); - assert(right); - assert(left!=right); - actlist_invert_fromto(status->actlist, left, right); - for(t=0;ttmp = -1; - } - free(segs); - if(right->left) - schedule_crossing(status, right->left, right, status->y); - if(left->right) - schedule_crossing(status, left, left->right, status->y); + event_t e = event_new(); + e.type = EVENT_CROSS; + e.p = p; + e.s1 = s1; + e.s2 = s2; + heap_put(status->queue, &e); + return; } void exchange_two(status_t*status, event_t*e) @@ -412,8 +349,10 @@ void exchange_two(status_t*status, event_t*e) segment_t*s1 = e->s1; segment_t*s2 = e->s2; #ifdef DEBUG - dict_put(status->intersecting_segs, s1, 0); - dict_put(status->intersecting_segs, s2, 0); + if(!dict_contains(status->intersecting_segs, s1)) + dict_put(status->intersecting_segs, s1, 0); + if(!dict_contains(status->intersecting_segs, s2)) + dict_put(status->intersecting_segs, s2, 0); #endif segment_t*left = actlist_left(status->actlist, s2); segment_t*right = actlist_right(status->actlist, s1); @@ -425,22 +364,29 @@ void exchange_two(status_t*status, event_t*e) left = actlist_left(status->actlist, s2); right = actlist_right(status->actlist, s1); if(left) - schedule_crossing(status, left, s2, status->y); + schedule_crossing(status, left, s2); if(right) - schedule_crossing(status, s1, right, status->y); + schedule_crossing(status, s1, right); } -void insert_point_into_segment(segment_t*s, point_t p) +void insert_point_into_segment(status_t*status, segment_t*s, point_t p) { - if(s->pos.x == p.x && s->pos.y == p.y) { #ifdef DEBUG - fprintf(stderr, "Notice: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr); -#endif - return; + 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 - printf("[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y); + fprintf(stderr, "[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y); #endif + + edge_t*e = malloc(sizeof(edge_t)); + e->a = s->pos; + e->b = p; + e->next = status->output; + status->output = e; + s->pos = p; } @@ -494,7 +440,7 @@ void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int3 #ifdef DEBUG dict_put(status->segs_with_point, seg, 0); #endif - insert_point_into_segment(seg, box.right2); + insert_point_into_segment(status, seg, box.right2); } else { break; } @@ -529,7 +475,7 @@ void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int3 #ifdef DEBUG dict_put(status->segs_with_point, seg, 0); #endif - insert_point_into_segment(seg, box.right2); + insert_point_into_segment(status, seg, box.right2); } else { break; } @@ -544,40 +490,58 @@ void event_apply(status_t*status, event_t*e) switch(e->type) { case EVENT_END: { //delete segment from list - event_dump(e); segment_t*s = e->s1; - insert_point_into_segment(s, s->b); +#ifdef DEBUG + event_dump(e); + dict_del(status->intersecting_segs, s); + dict_del(status->segs_with_point, s); + assert(!dict_contains(status->intersecting_segs, s)); + assert(!dict_contains(status->segs_with_point, s)); +#endif + insert_point_into_segment(status, s, s->b); segment_t*left = actlist_left(status->actlist, s); segment_t*right = actlist_right(status->actlist, s); actlist_delete(status->actlist, s); - dict_clear(&s->scheduled_crossings); if(left && right) - schedule_crossing(status, left, right, status->y+1); + schedule_crossing(status, left, right); + segment_destroy(s);e->s1=0; break; } case EVENT_START: { //insert segment into list +#ifdef DEBUG event_dump(e); +#endif segment_t*s = e->s1; actlist_insert(status->actlist, e->p, s); segment_t*left = actlist_left(status->actlist, s); segment_t*right = actlist_right(status->actlist, s); if(left) - schedule_crossing(status, left, s, status->y+1); + schedule_crossing(status, left, s); if(right) - schedule_crossing(status, s, right, status->y+1); + schedule_crossing(status, s, right); + + schedule_endpoint(status, e->s1); break; } case EVENT_CROSS: { // exchange two (or more) segments - event_t*ee = heap_peek(status->queue); - if(ee->p.x != e->p.x || - ee->p.y != e->p.y || - ee->type != e->type) { - event_dump(e); + if(actlist_right(status->actlist, e->s1) == e->s2 && + actlist_left(status->actlist, e->s2) == e->s1) { exchange_two(status, e); } else { - exchange_many(status, e); + /* ignore this crossing for now (there are some line segments in between). + it'll get rescheduled as soon as the "obstacles" are gone */ + char del1 = dict_del(&e->s1->scheduled_crossings, e->s2); + char del2 = dict_del(&e->s2->scheduled_crossings, e->s1); + assert(del1 && del2); +#ifdef DEBUG + point_t pair; + pair.x = e->s1->nr; + pair.y = e->s2->nr; + assert(dict_contains(status->seen_crossings, &pair)); + dict_del(status->seen_crossings, &pair); +#endif } } } @@ -587,7 +551,9 @@ void event_apply(status_t*status, event_t*e) void check_status(status_t*status) { DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) { - if(!dict_contains(status->segs_with_point, s)) { + if((s->pos.x != s->b.x || + 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, s->delta.x<0?"-":"+", @@ -598,16 +564,17 @@ void check_status(status_t*status) } #endif -void gfxpoly_process(segment_t*poly) +edge_t* gfxpoly_process(edge_t*poly) { heap_t* queue = heap_new(sizeof(event_t), compare_events); - segments_enqueue(poly, queue); + gfxpoly_enqueue(poly, queue); status_t status; memset(&status, 0, sizeof(status_t)); status.queue = queue; status.actlist = actlist_new(); #ifdef DEBUG status.seen_crossings = dict_new2(&point_type); + gfxpoly_dump(poly); #endif xrow_t*xrow = xrow_new(); @@ -618,7 +585,7 @@ void gfxpoly_process(segment_t*poly) #ifdef DEBUG status.intersecting_segs = dict_new2(&ptr_type); status.segs_with_point = dict_new2(&ptr_type); - printf("----------------------------------- %d\n", status.y); + fprintf(stderr, "----------------------------------- %d\n", status.y); actlist_verify_and_dump(status.actlist, status.y-1); #endif xrow_reset(xrow); @@ -641,7 +608,9 @@ void gfxpoly_process(segment_t*poly) #ifdef DEBUG dict_destroy(status.seen_crossings); #endif + actlist_destroy(status.actlist); heap_destroy(queue); - gfxpoly_destroy(poly); xrow_destroy(xrow); + + return status.output; } diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index e9da73c..972d471 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -13,6 +13,12 @@ typedef struct _point { int32_t y; } point_t; +typedef struct _edge { + point_t a; + point_t b; + struct _edge *next; +} edge_t; + typedef struct _segment { point_t a; point_t b; @@ -30,9 +36,10 @@ typedef struct _segment { #define LINE_EQ(p,s) ((double)(s)->delta.y*(p).x - (double)(s)->delta.x*(p).y - (s)->k) -typedef segment_t gfxpoly_t; +typedef edge_t gfxpoly_t; gfxpoly_t* gfxpoly_new(); void gfxpoly_dump(gfxpoly_t*poly); +gfxpoly_t* gfxpoly_process(gfxpoly_t*poly); typedef struct _event { eventtype_t type; diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c index e4e8455..e8c140c 100644 --- a/lib/gfxpoly/test.c +++ b/lib/gfxpoly/test.c @@ -11,12 +11,12 @@ gfxline_t*mkstar(int x1, int y1, int x2, int y2) gfxline_t*l=0,*line = 0; int x; for(x=x1;x<=x2;x+=50) { - l = malloc(sizeof(gfxline_t)); + l = rfx_calloc(sizeof(gfxline_t)); l->type = gfx_moveTo; l->x = x;l->y = y1; line = gfxline_append(line, l); - l = malloc(sizeof(gfxline_t)); + l = rfx_calloc(sizeof(gfxline_t)); l->type = gfx_lineTo; l->x = x2-x;l->y = y2; line = gfxline_append(line, l); @@ -27,7 +27,6 @@ gfxline_t*mkstar(int x1, int y1, int x2, int y2) int test1() { gfxline_t*box1 = gfxline_makerectangle(50,50,150,150); - // put box2 and box3 on top of each other *snicker* gfxline_t*box2 = gfxline_makerectangle(100,100,200,200); gfxline_t*box3 = gfxline_makerectangle(100,100,200,200); @@ -49,6 +48,7 @@ int test1() gfxline_free(box1); gfxline_free(box2); gfxline_free(box3); + gfxline_free(star); gfxpoly_dump(poly); gfxpoly_process(poly); @@ -56,13 +56,14 @@ int test1() int test2() { -#define N 1000 +#define N 50 +#define RANGE 150 int t; gfxline_t* line = malloc(sizeof(gfxline_t)*N); for(t=0;ta.x*20, e->a.y*20); + swf_ShapeSetLine(tag, s, e->b.x*20 - e->a.x*20, e->b.y*20 - e->a.y*20); + e = e->next; + } + swf_ShapeSetEnd(tag); + swf_ShapeFree(s); + + gfxpoly_destroy(poly); + gfxpoly_destroy(poly2); + + gfxline_free(l); + + if(t) { + tag = swf_InsertTag(tag,ST_REMOVEOBJECT2); + swf_SetU16(tag, t); + } + tag = swf_InsertTag(tag,ST_PLACEOBJECT2); + swf_ObjectPlace(tag,t+1,t+1,NULL,NULL,NULL); + + tag = swf_InsertTag(tag, ST_SHOWFRAME); + } + tag = swf_InsertTag(tag, ST_END); + + swf_SaveSWF(&swf, "test.swf"); } int main() { - test2(); + test3(); } diff --git a/lib/gfxpoly/xrow.c b/lib/gfxpoly/xrow.c index 123e00c..48fe7ad 100644 --- a/lib/gfxpoly/xrow.c +++ b/lib/gfxpoly/xrow.c @@ -1,3 +1,5 @@ +#include +#include #include "../mem.h" #include "xrow.h" @@ -11,6 +13,9 @@ xrow_t* xrow_new() void xrow_add(xrow_t*r, int32_t x) { + if(r->num && r->lastx==x) + return; + r->lastx = x; if(r->num >= r->size) { r->size *= 2; r->x = rfx_realloc(r->x, sizeof(r->x[0])*r->size); @@ -22,7 +27,7 @@ int compare_int32(const void*_i1,const void*_i2) { int32_t*i1 = (int32_t*)_i1; int32_t*i2 = (int32_t*)_i2; - return i1-i2; + return *i1-*i2; } void xrow_sort(xrow_t*r) @@ -46,6 +51,18 @@ void xrow_reset(xrow_t*r) r->num = 0; } +void xrow_dump(xrow_t*xrow) +{ + fprintf(stderr, "x: "); + int t; + for(t=0;tnum;t++) { + if(t) + fprintf(stderr, ", "); + fprintf(stderr, "%d", xrow->x[t]); + } + fprintf(stderr, "\n"); +} + void xrow_destroy(xrow_t*r) { if(r->x) { diff --git a/lib/gfxpoly/xrow.h b/lib/gfxpoly/xrow.h index cc32436..51300a3 100644 --- a/lib/gfxpoly/xrow.h +++ b/lib/gfxpoly/xrow.h @@ -7,11 +7,13 @@ typedef struct _xrow { int32_t*x; int num; int size; + int32_t lastx; } xrow_t; xrow_t* xrow_new(); void xrow_add(xrow_t*xrow, int32_t x); void xrow_sort(xrow_t*xrow); +void xrow_dump(xrow_t*xrow); void xrow_reset(xrow_t*xrow); void xrow_destroy(xrow_t*xrow); diff --git a/lib/q.c b/lib/q.c index 3416a0f..64934a6 100644 --- a/lib/q.c +++ b/lib/q.c @@ -1144,7 +1144,7 @@ char dict_del(dict_t*h, const void*key) while(e) { if(h->key_type->equals(e->key, key)) { dictentry_t*next = e->next; - rfx_free((void*)e->key); + h->key_type->free(e->key); memset(e, 0, sizeof(dictentry_t)); rfx_free(e); if(e == head) { diff --git a/lib/rfxswf.c b/lib/rfxswf.c index b063cc0..bd8cd17 100644 --- a/lib/rfxswf.c +++ b/lib/rfxswf.c @@ -1470,6 +1470,7 @@ int swf_ReadSWF2(reader_t*reader, SWF * swf) // Reads SWF to memory (malloc'ed swf->frameCount = SWAP16(swf->frameCount); /* read tags and connect to list */ + t1.next = 0; t = &t1; while (t) { t = swf_ReadTag(reader,t); @@ -1479,7 +1480,8 @@ int swf_ReadSWF2(reader_t*reader, SWF * swf) // Reads SWF to memory (malloc'ed } } swf->firstTag = t1.next; - t1.next->prev = NULL; + if(t1.next) + t1.next->prev = NULL; } return reader->pos; @@ -1709,6 +1711,21 @@ int swf_WriteSWF2(writer_t*writer, SWF * swf) // Writes SWF to file, return } } +int swf_SaveSWF(SWF * swf, char*filename) +{ + int fi = open(filename, O_BINARY|O_RDWR|O_TRUNC|O_CREAT, 0777); + if(fi<0) { + perror(filename); + return 0; + } + if(swf_WriteSWF(fi, swf)<0) { + fprintf(stderr, "Unable to write output file: %s\n", filename); + return 0; + } + close(fi); + return 1; +} + int swf_WriteSWF(int handle, SWF * swf) // Writes SWF to file, returns length or <0 if fails { writer_t writer; diff --git a/lib/rfxswf.h b/lib/rfxswf.h index d4b0424..3c5e244 100644 --- a/lib/rfxswf.h +++ b/lib/rfxswf.h @@ -169,6 +169,7 @@ int swf_ReadSWF2(reader_t*reader, SWF * swf); // Reads SWF via callback int swf_ReadSWF(int handle,SWF * swf); // Reads SWF to memory (malloc'ed), returns length or <0 if fails int swf_WriteSWF2(writer_t*writer, SWF * swf); // Writes SWF via callback, returns length or <0 if fails int swf_WriteSWF(int handle,SWF * swf); // Writes SWF to file, returns length or <0 if fails +int swf_SaveSWF(SWF * swf, char*filename); int swf_WriteCGI(SWF * swf); // Outputs SWF with valid CGI header to stdout void swf_FreeTags(SWF * swf); // Frees all malloc'ed memory for swf SWF* swf_CopySWF(SWF*swf); -- 1.7.10.4