From 002f2ed7c404339e11d669aa86ec998d8dd473a5 Mon Sep 17 00:00:00 2001 From: Matthias Kramm Date: Fri, 1 May 2009 03:07:47 +0200 Subject: [PATCH] more improvements to, and bugfixes in, the new polygon intersector --- lib/gfxpoly/Makefile | 2 +- lib/gfxpoly/convert.c | 29 +++++--- lib/gfxpoly/convert.h | 2 +- lib/gfxpoly/poly.c | 121 ++++++++++++++++++++------------- lib/gfxpoly/poly.h | 39 ++++++++--- lib/gfxpoly/renderpoly.c | 168 ++++++++++++++++++++++++++++++++-------------- lib/gfxpoly/renderpoly.h | 3 + lib/gfxpoly/test.c | 81 ++++++++++++++-------- lib/gfxpoly/wind.c | 144 +++++++++++++++++++++++++++++++++++++++ lib/gfxpoly/wind.h | 17 ++--- 10 files changed, 442 insertions(+), 164 deletions(-) create mode 100644 lib/gfxpoly/wind.c diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile index 8ee22ed..35e2039 100644 --- a/lib/gfxpoly/Makefile +++ b/lib/gfxpoly/Makefile @@ -25,7 +25,7 @@ poly.o: poly.c poly.h active.h ../q.h wind.o: wind.c wind.h poly.h $(CC) -c wind.c -o wind.o -renderpoly.o: renderpoly.c wind.h poly.h +renderpoly.o: renderpoly.c wind.h poly.h renderpoly.h $(CC) -c renderpoly.c -o renderpoly.o xrow.o: xrow.c xrow.h ../q.h ../mem.h diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index 39d1164..50282b9 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -28,19 +28,23 @@ static inline void gfxpoly_add_edge(edge_t**list, double _x1, double _y1, double } } -gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line) +gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line, double gridsize) { edge_t*s = 0; /* factor that determines into how many line fragments a spline is converted */ double subfraction = 2.4;//0.3 + double z = 1.0 / gridsize; + double lastx=0, lasty=0; assert(!line || line[0].type == gfx_moveTo); while(line) { + double x = line->x*z; + double y = line->y*z; if(line->type == gfx_moveTo) { } else if(line->type == gfx_lineTo) { - gfxpoly_add_edge(&s, lastx, lasty, line->x, line->y); + gfxpoly_add_edge(&s, lastx, lasty, x, 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); @@ -49,20 +53,23 @@ gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line) int i; for(i=0;ix*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_edge(&s, lastx, lasty, x, y); - lastx = x; - lasty = y; + double sx = (line->x*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(&s, lastx, lasty, sx, sy); + lastx = sx; + lasty = sy; } - gfxpoly_add_edge(&s, lastx, lasty, line->x, line->y); + gfxpoly_add_edge(&s, lastx, lasty, x, y); } - lastx = line->x; - lasty = line->y; + lastx = x; + lasty = y; line = line->next; } gfxline_free(line); - return s; + + gfxpoly_t*p = gfxpoly_new(gridsize); + p->edges = s; + return p; } diff --git a/lib/gfxpoly/convert.h b/lib/gfxpoly/convert.h index 688f016..b54b65d 100644 --- a/lib/gfxpoly/convert.h +++ b/lib/gfxpoly/convert.h @@ -3,6 +3,6 @@ #include "poly.h" -gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line); +gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line, double gridsize); #endif //__poly_convert_h__ diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 2303944..38ec637 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -7,6 +7,7 @@ #include "poly.h" #include "active.h" #include "xrow.h" +#include "wind.h" //#define DEBUG //#undef assert @@ -47,10 +48,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 @@ -81,18 +84,21 @@ int compare_events(const void*_a,const void*_b) return 0; } -gfxpoly_t* gfxpoly_new() +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); } void gfxpoly_dump(gfxpoly_t*poly) @@ -129,7 +135,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; @@ -157,7 +163,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; @@ -183,10 +189,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,7 +201,7 @@ 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) { @@ -204,7 +210,7 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue) 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, @@ -402,33 +408,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: @@ -446,7 +455,7 @@ void mark_point_in_segment(status_t*status, segment_t*s, point_t p) 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 +471,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 +488,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 +503,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,19 +513,28 @@ 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 + } void intersect_with_horizontal(status_t*status, segment_t*h) @@ -595,12 +613,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); @@ -639,17 +659,20 @@ void check_status(status_t*status) } #endif -edge_t* gfxpoly_process(edge_t*poly) +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(); @@ -674,9 +697,9 @@ edge_t* gfxpoly_process(edge_t*poly) } 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 +713,7 @@ 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; + return p; } diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index 6314935..e678b00 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -24,6 +24,20 @@ typedef struct _edge { struct _edge *next; } edge_t; +typedef struct _windstate +{ + char is_filled; + int wind_nr; + int num_polygons; +} windstate_t; + +typedef struct _windrule +{ + windstate_t (*start)(int num_polygons); + windstate_t (*add)(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int polygon_nr); + fillstyle_t* (*diff)(windstate_t*left, windstate_t*right); +} windrule_t; + typedef struct _segment { point_t a; point_t b; @@ -31,15 +45,18 @@ typedef struct _segment { double k; //k = a.x*b.y-a.y*b.x = delta.y*a.x - delta.x*a.y (=0 for points on the segment) segment_dir_t dir; - fillstyle_t*style; - + fillstyle_t*fs; + fillstyle_t*fs_out; + char fs_out_ok; + + int polygon_nr; + windstate_t wind; int nr; + struct _segment*left; struct _segment*right; point_t pos; - point_t new_point; - point_t new_pos; dict_t scheduled_crossings; } segment_t; @@ -47,10 +64,14 @@ typedef struct _segment { #define LINE_EQ(p,s) ((double)(s)->delta.y*(p).x - (double)(s)->delta.x*(p).y - (s)->k) #define XPOS(s,ypos) ((s)->a.x + ceil(((s)->delta.x * (double)((ypos) - (s)->a.y)) / (s)->delta.y)) -typedef edge_t gfxpoly_t; -gfxpoly_t* gfxpoly_new(); +typedef struct _gfxpoly { + double gridsize; + edge_t*edges; +} gfxpoly_t; + +gfxpoly_t* gfxpoly_new(double gridsize); void gfxpoly_dump(gfxpoly_t*poly); -gfxpoly_t* gfxpoly_process(gfxpoly_t*poly); +gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule); typedef struct _event { eventtype_t type; @@ -59,8 +80,4 @@ typedef struct _event { segment_t*s2; } event_t; -void segment_init(segment_t*s, 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); -void segment_insert_before(segment_t**list, segment_t*add); - #endif diff --git a/lib/gfxpoly/renderpoly.c b/lib/gfxpoly/renderpoly.c index de7dc0a..9ec6abf 100644 --- a/lib/gfxpoly/renderpoly.c +++ b/lib/gfxpoly/renderpoly.c @@ -8,6 +8,7 @@ typedef struct _renderpoint double x; segment_dir_t dir; fillstyle_t*fs; + int polygon_nr; } renderpoint_t; typedef struct _renderline @@ -26,12 +27,13 @@ typedef struct _renderbuf renderline_t*lines; } renderbuf_t; -static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir, fillstyle_t*fs) +static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir, fillstyle_t*fs, int polygon_nr) { renderpoint_t p; p.x = x; p.dir = dir; p.fs = fs; + p.polygon_nr = polygon_nr; if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin) return; @@ -46,7 +48,7 @@ static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir } #define CUT 0.5 #define INT(x) ((int)((x)+16)-16) -static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, fillstyle_t*fs) +static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2, fillstyle_t*fs, int polygon_nr) { x1 *= buf->zoom; y1 *= buf->zoom; @@ -86,7 +88,7 @@ static void add_line(renderbuf_t*buf, double x1, double y1, double x2, double y2 while(posy<=endy) { double xx = startx + posx; - add_pixel(buf, xx, posy, dir, fs); + add_pixel(buf, xx, posy, dir, fs, polygon_nr); posx+=stepx; posy++; } @@ -122,7 +124,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi buf->width = (bbox->xmax - bbox->xmin); buf->height = (bbox->ymax - bbox->ymin); buf->bbox = *bbox; - buf->zoom = zoom; + buf->zoom = zoom * polygon->gridsize; int width8 = (buf->width+7) >> 3; unsigned char* image = (unsigned char*)malloc(width8*buf->height); memset(image, 0, width8*buf->height); @@ -136,8 +138,9 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi } edge_t*e; - for(e=polygon;e;e=e->next) { - add_line(buf, e->a.x, e->a.y, e->b.x, e->b.y, e->style); + int polygon_nr = 0; + for(e=polygon->edges;e;e=e->next) { + add_line(buf, e->a.x, e->a.y, e->b.x, e->b.y, e->style, polygon_nr); } for(y=0;yheight;y++) { @@ -148,7 +151,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi qsort(points, num, sizeof(renderpoint_t), compare_renderpoints); int lastx = 0; - windstate_t*fill = 0; + windstate_t fill = rule->start(1); for(n=0;nx - bbox->xmin); @@ -158,14 +161,18 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi if(x > buf->width) { break; } - if(fill->is_filled && x!=lastx) { + if(fill.is_filled && x!=lastx) { fill_bitwise(line, lastx, x); } - fill = rule->add(fill, p->fs, p->dir, polygon); + fill = rule->add(fill, p->fs, p->dir, p->polygon_nr); lastx = x; } - if(fill->is_filled && lastx!=buf->width) + if(fill.is_filled && lastx!=buf->width) { + + return 0;// return an error, we're bleeding + fill_bitwise(line, lastx, buf->width); + } } for(y=0;yheight;y++) { @@ -184,19 +191,33 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi static inline max(double a, double b) {return a>b?a:b;} static inline min(double a, double b) {return aedges; + + zoom *= polygon->gridsize; if(e) { - b.xmin = e->a.x; - b.ymin = e->a.y; - b.xmax = e->a.x; - b.ymax = e->a.y; + b.xmin = e->a.x*zoom; + b.ymin = e->a.y*zoom; + b.xmax = e->a.x*zoom; + b.ymax = e->a.y*zoom; } - for(e=polygon;e;e=e->next) { + for(e=polygon->edges;e;e=e->next) { double x_min = min(e->a.x,e->b.x)*zoom; double y_min = min(e->a.y,e->b.y)*zoom; double x_max = max(e->a.x,e->b.x)*zoom; @@ -229,6 +250,10 @@ intbbox_t get_polygon_bbox(gfxpoly_t*polygon, double zoom) return b; } +#define B11111000 0xf8 +#define B01111100 0x7c +#define B00111110 0x3e +#define B00011111 0x1f #define B11100000 0xe0 #define B01110000 0x70 #define B00111000 0x38 @@ -246,47 +271,90 @@ intbbox_t get_polygon_bbox(gfxpoly_t*polygon, double zoom) int compare_bitmaps(intbbox_t*bbox, unsigned char*data1, unsigned char*data2) { - int similar = 0; int x,y; int height = bbox->height; int width = bbox->width; int width8 = (width+7) >> 3; - unsigned char*l1 = &data1[width8]; - unsigned char*l2 = &data2[width8]; - int fail = 0; - for(y=1;ywidth+7) >> 3; + unsigned char*data = malloc(b->width*b->height*4*4); + unsigned char*p = data; + int x,y; + unsigned char*b1 = data1; + unsigned char*b2 = data2; + compare_bitmaps(b, data1, data2); +//# define MARK ((abs(x-badx)<3 && abs(y-bady)<3)*255) +#define MARK 0 + for(y=0;yheight;y++) { + for(x=0;xwidth;x++) { + unsigned char c1 = (b1[x>>3]&(0x80>>(x&7)))?255:0; + unsigned char c2 = (b2[x>>3]&(0x80>>(x&7)))?255:0; + *p++ = 255; + *p++ = c1^c2; + *p++ = c1^c2; + *p++ = MARK; + } + for(x=0;xwidth;x++) { + unsigned char c = (b2[x>>3]&(0x80>>(x&7)))?255:0; + *p++ = 255; + *p++ = c; + *p++ = c; + *p++ = MARK; + } + b1 += width8; + b2 += width8; + } + b1 = data1; + for(y=0;yheight;y++) { + for(x=0;xwidth;x++) { + unsigned char c = (b1[x>>3]&(0x80>>(x&7)))?255:0; + *p++ = 255; + *p++ = c; + *p++ = c; + *p++ = MARK; + } + for(x=0;xwidth;x++) { + *p++ = 255; + *p++ = 0; + *p++ = 0; + *p++ = 0; + } + b1 += width8; + } + writePNG(filename, data, b->width*2, b->height*2); + free(data); } diff --git a/lib/gfxpoly/renderpoly.h b/lib/gfxpoly/renderpoly.h index 9172787..050c781 100644 --- a/lib/gfxpoly/renderpoly.h +++ b/lib/gfxpoly/renderpoly.h @@ -15,4 +15,7 @@ typedef struct { unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, windrule_t*rule); +intbbox_t intbbox_new(int x1, int y1, int x2, int y2); +intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom); + #endif diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c index 766b1a7..b9062f5 100644 --- a/lib/gfxpoly/test.c +++ b/lib/gfxpoly/test.c @@ -1,10 +1,12 @@ #include #include +#include #include #include #include "../gfxtools.h" #include "poly.h" #include "convert.h" +#include "renderpoly.h" gfxline_t*mkstar(int x1, int y1, int x2, int y2) { @@ -44,44 +46,61 @@ int test1() matrix.m01=-sin(ua);matrix.m11=cos(ua); gfxline_transform(b, &matrix); - gfxpoly_t*poly = gfxpoly_fillToPoly(b); + gfxpoly_t*poly = gfxpoly_fillToPoly(b, 0.05); gfxline_free(box1); gfxline_free(box2); gfxline_free(box3); gfxline_free(star); gfxpoly_dump(poly); - gfxpoly_process(poly); + gfxpoly_process(poly, &windrule_evenodd); } -int test_square(int width, int height, int num) +int test_square(int width, int height, int num, double gridsize, char bitmaptest) { int t; gfxline_t* line = malloc(sizeof(gfxline_t)*num); for(t=0;tedges; while(e) { - swf_ShapeSetMove(tag, s, e->a.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); + swf_ShapeSetMove(tag, s, e->a.x, e->a.y); + swf_ShapeSetLine(tag, s, e->b.x - e->a.x, e->b.y - e->a.y); e = e->next; } #else swf_ShapeSetAll(tag,s,0,0,ls,0,0); - edge_t*e = poly2; + edge_t*e = poly2->edges; while(e) { - swf_ShapeSetMove(tag, s, e->a.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); + swf_ShapeSetMove(tag, s, e->a.x, e->a.y); + swf_ShapeSetLine(tag, s, e->b.x - e->a.x, e->b.y - e->a.y); - swf_ShapeSetCircle(tag, s, e->a.x*20, e->a.y*20, 5*20, 5*20); - swf_ShapeSetCircle(tag, s, e->b.x*20, e->b.y*20, 5*20, 5*20); + swf_ShapeSetCircle(tag, s, e->a.x, e->a.y, 5*20, 5*20); + swf_ShapeSetCircle(tag, s, e->b.x, e->b.y, 5*20, 5*20); e = e->next; } #endif @@ -192,5 +215,5 @@ void test3() int main() { - test2(); + test3(); } diff --git a/lib/gfxpoly/wind.c b/lib/gfxpoly/wind.c new file mode 100644 index 0000000..fa6d724 --- /dev/null +++ b/lib/gfxpoly/wind.c @@ -0,0 +1,144 @@ +#include +#include "wind.h" + +fillstyle_t fillstyle_default; + +windstate_t windstate_nonfilled = { + is_filled: 0, + wind_nr: 0, + + /* TODO: move num_polygons into windstate_t.internal */ + num_polygons: 1, +}; + +// -------------------- even/odd ---------------------- + +windstate_t evenodd_start(int num_polygons) +{ + return windstate_nonfilled; +} +windstate_t evenodd_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master) +{ + left.is_filled ^= 1; + return left; +} +fillstyle_t* evenodd_diff(windstate_t*left, windstate_t*right) +{ + if(left->is_filled==right->is_filled) + return 0; + else + return &fillstyle_default; +} + +windrule_t windrule_evenodd = { + start: evenodd_start, + add: evenodd_add, + diff: evenodd_diff, +}; + +// -------------------- circular ---------------------- + +windstate_t circular_start(int num_polygons) +{ + return windstate_nonfilled; +} + +windstate_t circular_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master) +{ + /* which one is + and which one - doesn't actually make any difference */ + if(dir == DIR_DOWN) + left.wind_nr++; + else + left.wind_nr--; + + left.is_filled = left.wind_nr != 0; + return left; +} + +fillstyle_t* circular_diff(windstate_t*left, windstate_t*right) +{ + if(left->is_filled==right->is_filled) + return 0; + else + return &fillstyle_default; +} + +windrule_t windrule_circular = { + start: circular_start, + add: circular_add, + diff: circular_diff, +}; + +// -------------------- intersect ---------------------- + +windstate_t intersect_start(int num_polygons) +{ + windstate_t w; + w.num_polygons = num_polygons; + return w; +} + +windstate_t intersect_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master) +{ + assert(master < left.num_polygons); + + left.wind_nr ^= 1<is_filled==right->is_filled) + return 0; + else + return &fillstyle_default; +} + +windrule_t windrule_intersect = { + start: intersect_start, + add: intersect_add, + diff: intersect_diff, +}; + +// -------------------- union ---------------------- + +windstate_t union_start(int num_polygons) +{ + return windstate_nonfilled; +} + +windstate_t union_add(windstate_t left, fillstyle_t*edge, segment_dir_t dir, int master) +{ + assert(masteris_filled==right->is_filled) + return 0; + else + return &fillstyle_default; +} + +windrule_t windrule_union = { + start: union_start, + add: union_add, + diff: union_diff, +}; + + +/* + } else if (rule == WIND_NONZERO) { + fill = wind!=0; + } else if (rule == WIND_ODDEVEN) { + fill = wind&1; + } else { // rule == WIND_POSITIVE + fill = wind>=1; + } + */ diff --git a/lib/gfxpoly/wind.h b/lib/gfxpoly/wind.h index e057544..1dae74e 100644 --- a/lib/gfxpoly/wind.h +++ b/lib/gfxpoly/wind.h @@ -3,18 +3,9 @@ #include "poly.h" -typedef struct _windstate -{ - char is_filled; -} windstate_t; - -typedef struct _windrule -{ - windstate_t* (*add)(windstate_t*left, fillstyle_t*edge, segment_dir_t dir, gfxpoly_t*master); - fillstyle_t* (*diff)(windstate_t*left, windstate_t*right); -} windrule_t; - -windrule_t* windrule_new_evenodd(); -windrule_t* windrule_new_circular(); +extern windrule_t windrule_evenodd; +extern windrule_t windrule_circular; +extern windrule_t windrule_intersect; +extern windrule_t windrule_union; #endif -- 1.7.10.4