added bitmap-based polygon check

diff --git a/lib/gfxpoly.c b/lib/gfxpoly.c
index 8b914a8..acf2de3 100644 (file)
--- a/lib/gfxpoly.c
+++ b/lib/gfxpoly.c
@@ -37,6 +37,298 @@
 //#define SHEAR
 //#define DEBUG
 
 //#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;y<buf->height;y++) {
+       memset(&buf->lines[y], 0, sizeof(renderline_t));
+        buf->lines[y].points = 0;
+        buf->lines[y].num = 0;
+    }
+
+    int t;
+    for(t=0;t<svp->n_segs;t++) {
+        ArtSVPSeg* seg = &svp->segs[t];
+        int s;
+        for(s=0;s<seg->n_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;y<buf->height;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;n<num;n++) {
+            renderpoint_t*p = &points[n];
+            int x = (int)(p->x - 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;y<buf->height;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;t<svp->n_segs;t++) {
+        ArtSVPSeg* seg = &svp->segs[t];
+        int s;
+        for(s=0;s<seg->n_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;y<height-1;y++) {
+        for(x=0;x<width8;x++) {
+            unsigned a = l1[x-width8] & l1[x] & l1[x+width8];
+            unsigned b = l2[x-width8] & l2[x] & l2[x+width8];
+
+            if((a&B11100000) && !(l2[x]&B01000000))
+                fail == 1;
+            if((a&B01110000) && !(l2[x]&B00100000))
+                fail == 1;
+            if((a&B00111000) && !(l2[x]&B00010000))
+                fail == 1;
+            if((a&B00011100) && !(l2[x]&B00001000))
+                fail == 1;
+            if((a&B00001110) && !(l2[x]&B00000100))
+                fail == 1;
+            if((a&B00000111) && !(l2[x]&B00000010))
+                fail == 1;
+
+            if((b&B11100000) && !(l1[x]&B01000000))
+                fail == 1;
+            if((b&B01110000) && !(l1[x]&B00100000))
+                fail == 1;
+            if((b&B00111000) && !(l1[x]&B00010000))
+                fail == 1;
+            if((b&B00011100) && !(l1[x]&B00001000))
+                fail == 1;
+            if((b&B00001110) && !(l1[x]&B00000100))
+                fail == 1;
+            if((b&B00000111) && !(l1[x]&B00000010))
+                fail == 1;
+        }
+        l1 += width8;
+        l2 += width8;
+    }
+    return !fail;
+}
+
+
+//-----------------------------------------------------------------------------------------------
+

 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
 {
     ArtVpath *vec = NULL;
 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
 {
     ArtVpath *vec = NULL;

@@ -165,7 +457,7 @@ static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
 
 static void shear_svp(ArtSVP*svp, double v)
 {
 
 static void shear_svp(ArtSVP*svp, double v)
 {

-    /* do a "shearing on the polygon. We do this to eliminate all
+    /* do a "shearing" on the polygon. We do this to eliminate all

        horizontal lines (which libart can't handle properly, even though
        it tries). */
 
        horizontal lines (which libart can't handle properly, even though
        it tries). */
 

@@ -347,7 +639,9 @@ int check_svp(ArtSVP*svp)
            ArtPoint* p2 = &seg->points[p+1];
             
            if(p1->y >= p2->y) {
            ArtPoint* p2 = &seg->points[p+1];
             
            if(p1->y >= p2->y) {

-                msg("<error> bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y);
+                if(p1->y > p2->y) {
+                    msg("<error> 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;
             } 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) {
        lasty = y[t];
     }
     if(bleed) {

-       msg("<warning> svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n", 
+       msg("<verbose> 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);
                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);
 
 {
     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)) {
     art_svp_intersector(svp, swr);
     ArtSVP*result = art_svp_writer_rewind_reap(swr);
     clean_svp(result);
     if(!check_svp(result)) {

-       msg("<warning> Error in polygon processing");

        current_svp = result;
        art_report_error(); // might set art_error_in_intersector
        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("<verbose> 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("<verbose> 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) {
     if(art_error_in_intersector) {

+       msg("<verbose> Error in polygon processing");

        art_svp_free(result);
        art_error_in_intersector=0;
        return 0;
        art_svp_free(result);
        art_error_in_intersector=0;
        return 0;