new polygon renderer: fixed numerical issues

diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile
index 068901a..8469965 100644 (file)
--- a/lib/gfxpoly/Makefile
+++ b/lib/gfxpoly/Makefile
@@ -1,6 +1,6 @@
 all: testheap test
 
-CC = gcc -g -pg
+CC = gcc -g -O2
 
 ../libbase.a: ../q.c ../q.h ../mem.c ../mem.h
        cd ..; make libbase.a

diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c
index 02638f5..aece368 100644 (file)
--- a/lib/gfxpoly/active.c
+++ b/lib/gfxpoly/active.c
@@ -35,14 +35,19 @@ void actlist_verify(actlist_t*a, int32_t y)
 {
     segment_t*s = a->list;
     assert(!s || !s->left);
-    double lastx;
+    segment_t*l = 0;
     while(s) {
         if(y) {
-            double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
-            if(s!=a->list) {
-                assert(lastx<=x);
+            if(l) {
+                /* we need to re-evaluate the x of the previous segment. if we
+                   try to store it, it might end up being converted to a double,
+                   which will make it non-equal to (and possibly larger than) the
+                   "long double" the FPU has in it's register. This only happens
+                   when compiler optimizations are turned on. */
+                assert((XPOS(s, y) - XPOS(l, y)) >= 0);
+                assert(XDIFF(s,l,y) >= 0);
             }
-            lastx = x;
+            l = s;
         }
         assert(!s->left || s->left->right == s);
         assert(!s->right || s->right->left == s);

diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c
index f293d16..aea0a17 100644 (file)
--- a/lib/gfxpoly/convert.c
+++ b/lib/gfxpoly/convert.c
@@ -104,6 +104,7 @@ gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize)
         return 0;
     }
     int count = 0;
+    double g = 0;
     double lastx=0,lasty=0;
     while(1) {
         char*line = readline(fi);
@@ -124,10 +125,16 @@ gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize)
             }
             lastx = x;
             lasty = y;
+        } else if(sscanf(line, "%% gridsize %lf", &g) == 1) {
+            p->gridsize = g;
         }
         free(line);
     }
     fclose(fi);
-    printf("loaded %d points from %s\n", count, filename);
+    if(g) {
+        printf("loaded %d points from %s (gridsize %f)\n", count, filename, g);
+    } else {
+        printf("loaded %d points from %s\n", count, filename);
+    }
     return p;
 }

diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
index b143328..4d641a1 100644 (file)
--- a/lib/gfxpoly/poly.c
+++ b/lib/gfxpoly/poly.c
@@ -175,6 +175,7 @@ void gfxpoly_dump(gfxpoly_t*poly)
 gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename)
 {
     FILE*fi = fopen(filename, "wb");
+    fprintf(fi, "%% gridsize %f\n", poly->gridsize);
     fprintf(fi, "%% begin\n");
     edge_t* s = poly->edges;
     while(s) {
@@ -216,7 +217,7 @@ static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 void segment_dump(segment_t*s)
 {
     fprintf(stderr, "(%d,%d)->(%d,%d) ", s->a.x, s->a.y, s->b.x, s->b.y);
-    fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k, 
+    fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
             (double)s->delta.x / s->delta.y);
 }
 
@@ -521,7 +522,7 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 
     if(s->fs_out) {
 #ifdef DEBUG
-        fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr, 
+        fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
                 s->pos.x, s->pos.y, p.x, p.y);
 #endif
         // omit horizontal lines
@@ -552,16 +553,9 @@ typedef struct _segrange {
     segment_t*segmax;
 } segrange_t;
 
-static inline char xpos_eq(segment_t*s1, segment_t*s2, int y)
-{
-    if(XPOS_EQ(s1, s2, y)) {
-        return 1;
-    }
-    return 0;
-}
-
 void segrange_adjust_endpoints(segrange_t*range, int y)
 {
+#define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
 #ifdef CHECK
     /* this would mean that the segment left/right of the minimum/maximum
        intersects the current segment exactly at the scanline, but somehow
@@ -570,12 +564,13 @@ void segrange_adjust_endpoints(segrange_t*range, int y)
     assert(!max || !max->right || !XPOS_EQ(max, max->right, y));
 #endif
 
+    /* this doesn't actually ever happen anymore (see checks above) */
     segment_t*min = range->segmin;
     segment_t*max = range->segmax;
-    if(min) while(min->left && xpos_eq(min, min->left, y)) {
+    if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
         min = min->left;
     }
-    if(max) while(max->right && xpos_eq(max, max->right, y)) {
+    if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
         max = max->right;
     }
     range->segmin = min;
@@ -621,9 +616,8 @@ static void add_points_to_positively_sloped_segments(status_t*status, int32_t y,
     for(t=0;t<status->xrow->num;t++) {
         box_t box = box_new(status->xrow->x[t], y);
         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
-       
-        seg = actlist_right(status->actlist, seg);
 
+        seg = actlist_right(status->actlist, seg);
         while(seg) {
             if(seg->a.y == y) {
                 // this segment started in this scanline, ignore it
@@ -665,7 +659,7 @@ static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y,
     for(t=status->xrow->num-1;t>=0;t--) {
         box_t box = box_new(status->xrow->x[t], y);
         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
-        
+
         while(seg) {
             if(seg->a.y == y) {
                 // this segment started in this scanline, ignore it
@@ -710,7 +704,7 @@ void add_points_to_ending_segments(status_t*status, int32_t y)
         segment_t*next = seg->right;seg->right=0;
 
         assert(seg->b.y == status->y);
-  
+
         if(status->xrow->num == 1) {
             // shortcut
             point_t p = {status->xrow->x[0], y};
@@ -773,12 +767,12 @@ static void recalculate_windings(status_t*status, segrange_t*range)
     s = actlist_leftmost(status->actlist);
     while(s && s!=range->segmin) {
         assert(!s->changed);
-        s = actlist_right(status->actlist, s);
+        s = s->right;
     }
     s = actlist_rightmost(status->actlist);
     while(s && s!=range->segmax) {
         assert(!s->changed);
-        s = actlist_left(status->actlist, s);
+        s = s->left;
     }
     /* in check mode, go through the whole interval so we can test
        that all polygons where the fillstyle changed also have seg->changed=1 */
@@ -790,7 +784,7 @@ static void recalculate_windings(status_t*status, segrange_t*range)
         end = actlist_right(status->actlist, end);
     while(s!=end) {
 #ifndef CHECK
-        if(s->changed) 
+        if(s->changed)
 #endif
         {
             segment_t* left = actlist_left(status->actlist, s);
@@ -807,7 +801,7 @@ static void recalculate_windings(status_t*status, segrange_t*range)
             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
         }
-        s = actlist_right(status->actlist, s);
+        s = s->right;
     }
 #ifdef DEBUG
     fprintf(stderr, "\n");
@@ -825,8 +819,13 @@ void intersect_with_horizontal(status_t*status, segment_t*h)
     xrow_add(status->xrow, h->a.x);
     point_t o = h->a;
 
-    left = actlist_right(status->actlist, left);
-    right = actlist_right(status->actlist, right);
+    if(!right) {
+        assert(!left);
+        return;
+    }
+
+    left = actlist_right(status->actlist, left); //first seg to the right of h->a
+    right = right->right; //first seg to the right of h->b
     segment_t* s = left;
 
     while(s!=right) {
@@ -845,7 +844,7 @@ void intersect_with_horizontal(status_t*status, segment_t*h)
         assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
         xrow_add(status->xrow, x);
 
-        s = actlist_right(status->actlist, s);
+        s = s->right;
     }
 }
 

diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h
index 6e4c7e4..b967567 100644 (file)
--- a/lib/gfxpoly/poly.h
+++ b/lib/gfxpoly/poly.h
@@ -5,7 +5,7 @@
 #include "../q.h"
 
 //#define DEBUG
-//#define CHECKS
+#define CHECKS
 
 typedef enum {DIR_UP, DIR_DOWN} segment_dir_t;
 typedef enum {EVENT_CROSS, EVENT_END, EVENT_CORNER, EVENT_START, EVENT_HORIZONTAL} eventtype_t;
@@ -81,10 +81,7 @@ typedef struct _segment {
 
 #define XPOS_INT(s,ypos) ((int)ceil(XPOS((s),ypos)))
 #define XDIFF(s1,s2,ypos) (((s1)->k + (double)(s1)->delta.x*ypos)*(s2)->delta.y - \
-                           ((s2)->k + (double)(s1)->delta.x*ypos)*(s1)->delta.y)
-
-// rewrite as XDIFF==0?
-#define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
+                           ((s2)->k + (double)(s2)->delta.x*ypos)*(s1)->delta.y)
 
 typedef struct _gfxpoly {
     double gridsize;

diff --git a/lib/gfxpoly/renderpoly.c b/lib/gfxpoly/renderpoly.c
index 06440fa..9e3c593 100644 (file)
--- a/lib/gfxpoly/renderpoly.c
+++ b/lib/gfxpoly/renderpoly.c
@@ -36,10 +36,10 @@ static inline void add_pixel(renderbuf_t*buf, double x, int y, segment_dir_t dir
     p.fs = fs;
     p.e = e;
     p.polygon_nr = polygon_nr;
-
-    if(x >= buf->bbox.xmax || y >= buf->bbox.ymax || y < buf->bbox.ymin) 
-        return;
     
+    if(y >= buf->bbox.ymax || y < buf->bbox.ymin) 
+        return;
+
     renderline_t*l = &buf->lines[y-buf->bbox.ymin];
 
     if(l->num == l->size) {
@@ -130,7 +130,7 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi
     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++) {
@@ -152,18 +152,18 @@ unsigned char* render_polygon(gfxpoly_t*polygon, intbbox_t*bbox, double zoom, wi
        int num = buf->lines[y].num;
         qsort(points, num, sizeof(renderpoint_t), compare_renderpoints);
         int lastx = 0;
-
+        
         windstate_t fill = rule->start(1);
         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.is_filled && x!=lastx) {
+                x = lastx; 
+            if(x > buf->width)
+                x = buf->width;
+
+            if(fill.is_filled && lastx<x) {
                 fill_bitwise(line, lastx, x);
             }
             fill = rule->add(fill, p->fs, p->dir, p->polygon_nr);
@@ -232,7 +232,7 @@ intbbox_t intbbox_from_polygon(gfxpoly_t*polygon, double zoom)
         if(x2 > b.xmax) b.xmax = x2;
         if(y2 > b.ymax) b.ymax = y2;
     }
-
+    
     if(b.xmax > (int)(MAX_WIDTH*zoom))
        b.xmax = (int)(MAX_WIDTH*zoom);
     if(b.ymax > (int)(MAX_HEIGHT*zoom))

diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c
index 4ab1004..888e4d6 100644 (file)
--- a/lib/gfxpoly/test.c
+++ b/lib/gfxpoly/test.c
@@ -137,7 +137,7 @@ int test0()
     gfxpoly_destroy(poly);
 }
 
-int test1()
+int test1(int argn, char*argv[])
 {
     gfxline_t*box1 = gfxline_makerectangle(50,50,150,150);
     // put box2 and box3 on top of each other *snicker*
@@ -202,7 +202,7 @@ int test_square(int width, int height, int num, double gridsize, char bitmaptest
     gfxpoly_destroy(poly);
 }
 
-int test2()
+int test2(int argn, char*argv[])
 {
     test_square(400,400, 3, 0.05, 1);
 
@@ -216,7 +216,7 @@ int test2()
 }
 
 #include "../rfxswf.h"
-void test3()
+void test3(int argn, char*argv[])
 {
 #undef N
 #undef RANGE
@@ -320,7 +320,7 @@ void test3()
 }
 
 #include <dirent.h>
-void test4()
+void test4(int argn, char*argv[])
 {
     char*dir = "ps";
     DIR*_dir = opendir(dir);
@@ -333,10 +333,18 @@ void test4()
         if(!strstr(file->d_name, ".ps")) 
             continue;
 
-        char* filename = allocprintf("%s/%s", dir, file->d_name);
+        char* filename;
+
+        if(argn<2)
+            filename = allocprintf("%s/%s", dir, file->d_name);
+        else
+            filename = argv[1];
+
         windrule_t*rule = &windrule_evenodd;
         gfxpoly_t*poly = gfxpoly_from_file(filename, 1.0);//0.01);
-        free(filename);
+
+        if(argn!=2)
+            free(filename);
 
         double zoom = 1.0;
         intbbox_t bbox = intbbox_from_polygon(poly, zoom);
@@ -357,8 +365,14 @@ void test4()
             save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
             assert(!"bitmaps don't match");
         }
+        free(bitmap1);
+        free(bitmap2);
+        gfxpoly_destroy(poly);
         gfxpoly_destroy(poly2);
+        if(argn==2) 
+            break;
     }
+    closedir(_dir);
 }
 
 #include "../gfxdevice.h"
@@ -376,16 +390,16 @@ void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color)
     }
 
     windrule_t*rule = &windrule_evenodd;
-    gfxpoly_t*poly2 = gfxpoly_process(poly, rule);
         
     double zoom = 1.0;
     intbbox_t bbox = intbbox_from_polygon(poly, zoom);
     unsigned char*bitmap1 = render_polygon(poly, &bbox, zoom, rule);
-    unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd);
     if(!bitmap_ok(&bbox, bitmap1)) {
         printf("bad polygon or error in renderer\n");
         return;
     }
+    gfxpoly_t*poly2 = gfxpoly_process(poly, rule);
+    unsigned char*bitmap2 = render_polygon(poly2, &bbox, zoom, &windrule_evenodd);
     if(!bitmap_ok(&bbox, bitmap2)) {
         save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
         assert(!"error in bitmap");
@@ -394,6 +408,8 @@ void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color)
         save_two_bitmaps(&bbox, bitmap1, bitmap2, "error.png");
         assert(!"bitmaps don't match");
     }
+    free(bitmap1);
+    free(bitmap2);
 
     gfxpoly_destroy(poly);
     gfxpoly_destroy(poly2);
@@ -454,8 +470,9 @@ finish: 0,
 internal: 0
 };
 
-void test5()
+void test5(int argn, char*argv[])
 {
+    gfxsource_t*driver = gfxsource_pdf_create();
     char*dir = "pdfs";
     DIR*_dir = opendir(dir);
     if(!_dir) return;
@@ -468,7 +485,6 @@ void test5()
             continue;
         char* filename = allocprintf("%s/%s", dir, file->d_name);
 
-        gfxsource_t*driver = gfxsource_pdf_create();
         gfxdocument_t*doc = driver->open(driver, filename);
         gfxdevice_t*out = &extract_polygons;
         int t;
@@ -477,13 +493,15 @@ void test5()
             gfxpage_t* page = doc->getpage(doc, t);
             page->render(page, out);
             page->destroy(page);
-            break;
         }
+        doc->destroy(doc);
         free(filename);
     }
+    closedir(_dir);
+    driver->destroy(driver);
 }
 
-int main()
+int main(int argn, char*argv[])
 {
-    test3();
+    test5(argn, argv);
 }