From 95071265866ba487f424b1c66db70de905601ad8 Mon Sep 17 00:00:00 2001 From: kramm Date: Sat, 24 May 2008 11:15:07 +0000 Subject: [PATCH] added bitmap-based polygon check --- lib/gfxpoly.c | 317 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 313 insertions(+), 4 deletions(-) diff --git a/lib/gfxpoly.c b/lib/gfxpoly.c index 8b914a8..acf2de3 100644 --- a/lib/gfxpoly.c +++ b/lib/gfxpoly.c @@ -37,6 +37,298 @@ //#define SHEAR //#define DEBUG +//----------------------------------------- svp renderer ---------------------------------------- + +typedef struct { + int xmin; + int ymin; + int xmax; + int ymax; + int width; + int height; +} intbbox_t; + +typedef struct _renderpoint +{ + double x; + signed char direction; +} renderpoint_t; + +typedef struct _renderline +{ + renderpoint_t*points; + int size; + int num; +} renderline_t; + +typedef struct _renderbuf +{ + intbbox_t bbox; + int width; + int height; + double zoom; + renderline_t*lines; +} renderbuf_t; + +static inline void add_pixel(renderbuf_t*buf, double x, int y, signed char direction) +{ + renderpoint_t p; + p.x = x; + p.direction = direction; + + if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin) + return; + renderline_t*l = &buf->lines[y-buf->bbox.ymin]; + + if(l->num == l->size) { + l->size += 32; + l->points = (renderpoint_t*)rfx_realloc(l->points, l->size * sizeof(renderpoint_t)); + } + l->points[l->num] = p; + l->num++; +} +#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, signed char direction) +{ + x1 *= buf->zoom; + y1 *= buf->zoom; + x2 *= buf->zoom; + y2 *= buf->zoom; + double diffx, diffy; + double ny1, ny2, stepx; + if(y2 < y1) { + double x,y; + x = x1;x1 = x2;x2=x; + y = y1;y1 = y2;y2=y; + } + diffx = x2 - x1; + diffy = y2 - y1; + ny1 = INT(y1)+CUT; + ny2 = INT(y2)+CUT; + + if(ny1 < y1) { + ny1 = INT(y1) + 1.0 + CUT; + } + if(ny2 >= y2) { + ny2 = INT(y2) - 1.0 + CUT; + } + if(ny1 > ny2) + return; + + stepx = diffx/diffy; + x1 = x1 + (ny1-y1)*stepx; + x2 = x2 + (ny2-y2)*stepx; + + int posy=INT(ny1); + int endy=INT(ny2); + double posx=0; + double startx = x1; + + while(posy<=endy) { + double xx = startx + posx; + add_pixel(buf, xx, posy, direction); + posx+=stepx; + posy++; + } +} + +static int compare_renderpoints(const void * _a, const void * _b) +{ + renderpoint_t*a = (renderpoint_t*)_a; + renderpoint_t*b = (renderpoint_t*)_b; + if(a->x < b->x) return -1; + if(a->x > b->x) return 1; + return 0; +} + +static void fill_bitwise(unsigned char*line, int x1, int x2) +{ + int p1 = x1>>3; + int p2 = x2>>3; + int b1 = 0xff >> (x1&7); + int b2 = 0xff << (1+7-(x2&7)); + if(p1==p2) { + line[p1] |= b1&b2; + } else { + line[p1] |= b1; + memset(&line[p1+1], 255, p2-(p1+1)); + line[p2] = b2; + } +} + +unsigned char* render_svp(ArtSVP*svp, intbbox_t*bbox, double zoom, ArtWindRule rule) +{ + renderbuf_t _buf, *buf=&_buf; + buf->width = (bbox->xmax - bbox->xmin); + buf->height = (bbox->ymax - bbox->ymin); + buf->bbox = *bbox; + buf->zoom = zoom; + int width8 = (buf->width+7) >> 3; + unsigned char* image = (unsigned char*)malloc(width8*buf->height); + memset(image, 0, width8*buf->height); + + buf->lines = (renderline_t*)rfx_alloc(buf->height*sizeof(renderline_t)); + int y; + for(y=0;yheight;y++) { + memset(&buf->lines[y], 0, sizeof(renderline_t)); + buf->lines[y].points = 0; + buf->lines[y].num = 0; + } + + int t; + for(t=0;tn_segs;t++) { + ArtSVPSeg* seg = &svp->segs[t]; + int s; + for(s=0;sn_points-1;s++) { + int dir = seg->dir? 1 : -1; + add_line(buf, seg->points[s].x, seg->points[s].y, seg->points[s+1].x, seg->points[s+1].y, dir); + } + } + for(y=0;yheight;y++) { + renderpoint_t*points = buf->lines[y].points; + unsigned char*line = &image[width8*y]; + int n; + int num = buf->lines[y].num; + int wind = 0; + qsort(points, num, sizeof(renderpoint_t), compare_renderpoints); + int lastx = 0; + int fill = 0; + + for(n=0;nx - bbox->xmin); + + if(x < lastx) + x = lastx; + if(x > buf->width) { + break; + } + if(fill && x!=lastx) { + fill_bitwise(line, lastx, x); + } + wind += p->direction; + if(rule == ART_WIND_RULE_INTERSECT) { + fill = wind>=2; + } else if (rule == ART_WIND_RULE_NONZERO) { + fill = wind!=0; + } else if (rule == ART_WIND_RULE_ODDEVEN) { + fill = wind&1; + } else { // rule == ART_WIND_RULE_POSITIVE + fill = wind>=1; + } + lastx = x; + } + if(fill && lastx!=buf->width) + fill_bitwise(line, lastx, buf->width); + } + + for(y=0;yheight;y++) { + if(buf->lines[y].points) { + free(buf->lines[y].points); + } + memset(&buf->lines[y], 0, sizeof(renderline_t)); + } + free(buf->lines);buf->lines=0; + return image; +} + +intbbox_t get_svp_bbox(ArtSVP*svp, double zoom) +{ + int t; + intbbox_t b = {0,0,0,0}; + if(svp->n_segs && svp->segs[0].n_points) { + b.xmin = svp->segs[0].points[0].x; + b.ymin = svp->segs[0].points[0].y; + b.xmax = svp->segs[0].points[0].x; + b.ymax = svp->segs[0].points[0].y; + } + for(t=0;tn_segs;t++) { + ArtSVPSeg* seg = &svp->segs[t]; + int s; + for(s=0;sn_points;s++) { + double x = seg->points[s].x*zoom; + double y = seg->points[s].y*zoom; + int x1 = floor(x); + int x2 = ceil(x); + int y1 = floor(y); + int y2 = ceil(y); + if(x1 < b.xmin) b.xmin = x1; + if(y1 < b.ymin) b.ymin = y1; + if(x2 > b.xmax) b.xmax = x2; + if(y2 > b.xmax) b.ymax = y2; + } + } + b.width = b.xmax - b.xmin; + b.height = b.ymax - b.ymin; + return b; +} + +#define B11100000 0xe0 +#define B01110000 0x70 +#define B00111000 0x38 +#define B00011100 0x1c +#define B00001110 0x0e +#define B00000111 0x07 +#define B10000000 0x80 +#define B01000000 0x40 +#define B00100000 0x20 +#define B00010000 0x10 +#define B00001000 0x08 +#define B00000100 0x04 +#define B00000010 0x02 +#define B00000001 0x01 + +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;ypoints[p+1]; if(p1->y >= p2->y) { - msg(" bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y); + if(p1->y > p2->y) { + msg(" bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y); + } } else { segs[num_segs].y1 = p1->y; segs[num_segs].y2 = p2->y; @@ -393,7 +687,7 @@ int check_svp(ArtSVP*svp) lasty = y[t]; } if(bleed) { - msg(" svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n", + msg(" svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n", bleedy1, bleedy2, bleed, num_segs); free(y);free(segs);free(seg_start);free(seg_end); @@ -621,15 +915,30 @@ ArtSVP* run_intersector(ArtSVP*svp, ArtWindRule rule) { ArtSvpWriter * swr = art_svp_writer_rewind_new(rule); + double zoom = 1.0; + intbbox_t bbox = get_svp_bbox(svp, zoom); + art_svp_intersector(svp, swr); ArtSVP*result = art_svp_writer_rewind_reap(swr); clean_svp(result); if(!check_svp(result)) { - msg(" Error in polygon processing"); current_svp = result; art_report_error(); // might set art_error_in_intersector + } else { + unsigned char*data1 = render_svp(svp, &bbox, zoom, rule); + unsigned char*data2 = render_svp(result, &bbox, zoom, ART_WIND_RULE_ODDEVEN); + msg(" Comparing polygon renderings of size %dx%d and %dx%d", bbox.width, bbox.height, bbox.width, bbox.height); + if(!compare_bitmaps(&bbox, data1, data2)) { + msg(" Bad SVP rewinding result- polygons don't match"); + current_svp = result; + art_report_error(); // might set art_error_in_intersector + } + free(data1); + free(data2); } + if(art_error_in_intersector) { + msg(" Error in polygon processing"); art_svp_free(result); art_error_in_intersector=0; return 0; -- 1.7.10.4