started rewriting polygon conversion functions

6 files changed, 236 insertions, 88 deletions

diff --git a/lib/gfxpoly/Makefile b/lib/gfxpoly/Makefile
index 326c8c6d..3af0dda7 100644
--- a/lib/gfxpoly/Makefile
+++ b/lib/gfxpoly/Makefile
@@ -1,6 +1,8 @@
 all: test
+include ../../Makefile.common
 
 CC = gcc -g -O2
+#CC = gcc -O3
 
 ../libbase.a: ../q.c ../q.h ../mem.c ../mem.h
 	cd ..; make libbase.a
@@ -31,9 +33,9 @@ renderpoly.o: renderpoly.c wind.h poly.h renderpoly.h
 xrow.o: xrow.c xrow.h ../q.h ../mem.h
 	$(CC) -c xrow.c -o xrow.o
 
-SWF = ../librfxswf.a ../libpdf.a ../libgfx.a -lstdc++ -lfontconfig
+SWF = ../librfxswf.a ../libpdf.a ../libgfx.a -lstdc++
 test: ../libbase.a ../libgfx.a test.c $(OBJS) poly.h convert.h
-	$(CC) test.c $(OBJS) $(SWF) ../libbase.a ../libgfx.a -o test -lm -lz -ljpeg -lfreetype
+	$(CC) test.c $(OBJS) $(SWF) ../libbase.a ../libgfx.a -o test $(LIBS)
 
 clean: 
 	rm -f *.o test
diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c
index 0e458be3..5619f790 100644
--- a/lib/gfxpoly/convert.c
+++ b/lib/gfxpoly/convert.c
@@ -18,24 +18,22 @@ static edge_t*edge_new(int x1, int y1, int x2, int y2)
     return s;
 }
 
-static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, double _x2, double _y2)
+static inline int32_t convert_coord(double x)
 {
     /* we clamp to 31 bit instead of 32 bit because we use
        a (x1-x2) shortcut when comparing coordinates
     */
-    if(_x1 < -0x40000000) _x1 = -0x40000000;
-    if(_x1 >  0x3fffffff) _x1 =  0x3fffffff;
-    if(_y1 < -0x40000000) _y1 = -0x40000000;
-    if(_y1 >  0x3fffffff) _y1 =  0x3fffffff;
-    if(_x2 < -0x40000000) _x2 = -0x40000000;
-    if(_x2 >  0x3fffffff) _x2 =  0x3fffffff;
-    if(_y2 < -0x40000000) _y2 = -0x40000000;
-    if(_y2 >  0x3fffffff) _y2 =  0x3fffffff;
+    if(x < -0x40000000) x = -0x40000000;
+    if(x >  0x3fffffff) x =  0x3fffffff;
+    return ceil(x);
+}
 
-    int x1 = ceil(_x1);
-    int y1 = ceil(_y1);
-    int x2 = ceil(_x2);
-    int y2 = ceil(_y2);
+static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, double _x2, double _y2)
+{
+    int x1 = convert_coord(_x1);
+    int y1 = convert_coord(_y1);
+    int x2 = convert_coord(_x2);
+    int y2 = convert_coord(_y2);
 
     if(x1!=x2 || y1!=y2) {
         edge_t*s = edge_new(x1, y1, x2, y2);
@@ -44,20 +42,17 @@ static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, doub
     }
 }
 
-gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize)
+static void convert_gfxline(gfxline_t*line, void*data, void(*moveto)(void*data, double x, double y), void(*lineto)(void*data, double x, double y), void(*setgridsize)(void*data, double g))
 {
-    gfxpoly_t*p = gfxpoly_new(gridsize);
-
-    double z = 1.0 / gridsize;
-
-    double lastx=0, lasty=0;
     assert(!line || line[0].type == gfx_moveTo);
+    double lastx=0,lasty=0;
     while(line) {
-        double x = line->x*z;
-        double y = line->y*z;
         if(line->type == gfx_moveTo) {
+	    if(line->next && line->next->type != gfx_moveTo && (line->x!=lastx || line->y!=lasty)) {
+		moveto(data, line->x, line->y);
+	    }
         } else if(line->type == gfx_lineTo) {
-            gfxpoly_add_edge(p, lastx, lasty, x, y);
+            lineto(data, 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);
@@ -66,35 +61,18 @@ gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize)
             int i;
 	    for(i=0;i<parts;i++) {
 		double t = (double)i*stepsize;
-		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(p, lastx, lasty, sx, sy);
-                lastx = sx;
-                lasty = sy;
+		double sx = (line->x*t*t + 2*line->sx*t*(1-t) + lastx*(1-t)*(1-t));
+		double sy = (line->y*t*t + 2*line->sy*t*(1-t) + lasty*(1-t)*(1-t));
+		lineto(data, sx, sy);
 	    }
-            gfxpoly_add_edge(p, lastx, lasty, x, y);
+	    lineto(data, line->x, line->y);
         }
-        lastx = x;
-        lasty = y;
+	lastx = line->x;
+	lasty = line->y;
         line = line->next;
     }
-    
-    gfxline_free(line);
-    return p;
 }
 
-typedef struct _gfxstroke {
-    segment_dir_t dir;
-    point_t*stroke;
-    fillstyle_t*fs;
-    int num_points;
-} gfxstroke_t;
-typedef struct _gfxcompactpoly {
-    double gridsize;
-    int num_strokes;
-    gfxstroke_t strokes[0];
-} gfxcompactpoly_t;
-
 static char* readline(FILE*fi)
 {
     char c;
@@ -117,16 +95,11 @@ static char* readline(FILE*fi)
     }
 }
 
-gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize)
+static void convert_file(const char*filename, void*data, void(*moveto)(void*data, double x, double y), void(*lineto)(void*data, double x, double y),void(*setgridsize)(void*data, double gridsize))
 {
-    gfxpoly_t*p = gfxpoly_new(gridsize);
-
-    double z = 1.0 / gridsize;
-
     FILE*fi = fopen(filename, "rb");
     if(!fi) {
         perror(filename);
-        return 0;
     }
     int count = 0;
     double g = 0;
@@ -138,28 +111,187 @@ gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize)
         double x,y;
         char s[256];
         if(sscanf(line, "%lf %lf %s", &x, &y, &s) == 3) {
-            x*=z;
-            y*=z;
             if(s && !strcmp(s,"moveto")) {
+		moveto(data, x, y);
                 count++;
             } else if(s && !strcmp(s,"lineto")) {
-                gfxpoly_add_edge(p, lastx, lasty, x, y);
+		lineto(data, x, y);
                 count++;
             } else {
-                printf("invalid command: %s\n", s);
+                fprintf(stderr, "invalid command: %s\n", s);
             }
-            lastx = x;
-            lasty = y;
         } else if(sscanf(line, "%% gridsize %lf", &g) == 1) {
-            p->gridsize = g;
+	    setgridsize(data, g);
         }
         free(line);
     }
     fclose(fi);
     if(g) {
-        printf("loaded %d points from %s (gridsize %f)\n", count, filename, g);
+        fprintf(stderr, "loaded %d points from %s (gridsize %f)\n", count, filename, g);
     } else {
-        printf("loaded %d points from %s\n", count, filename);
+        fprintf(stderr, "loaded %d points from %s\n", count, filename);
     }
-    return p;
 }
+
+typedef struct _stdpoly {
+    gfxpoly_t*poly;
+    double lastx,lasty;
+    double z;
+} stdpoly_t;
+static void stdmoveto(void*data, double x, double y)
+{
+    stdpoly_t*d = (stdpoly_t*)data;
+    x *= d->z;
+    y *= d->z;
+    d->lastx = x;d->lasty = y;
+}
+static void stdlineto(void*data, double x, double y)
+{
+    stdpoly_t*d = (stdpoly_t*)data;
+    x *= d->z;
+    y *= d->z;
+    gfxpoly_add_edge(d->poly, d->lastx, d->lasty, x, y);
+    d->lastx = x;d->lasty = y;
+}
+static void stdsetgridsize(void*data, double gridsize)
+{
+    stdpoly_t*d = (stdpoly_t*)data;
+    d->poly->gridsize = gridsize;
+}
+gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize)
+{
+    stdpoly_t data;
+    data.poly = gfxpoly_new(gridsize);
+    data.z = 1.0 / gridsize;
+    data.lastx = data.lasty = 0;
+    convert_gfxline(line, &data, stdmoveto, stdlineto, stdsetgridsize);
+    return data.poly;
+}
+gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize)
+{
+    stdpoly_t data;
+    data.poly = gfxpoly_new(gridsize);
+    data.z = 1.0 / gridsize;
+    data.lastx = data.lasty = 0;
+    convert_file(filename, &data, stdmoveto, stdlineto, stdsetgridsize);
+    return data.poly;
+}
+
+typedef struct _compactpoly {
+    gfxcompactpoly_t*poly;
+    point_t last;
+    double z;
+    int strokes_size;
+    point_t*points;
+    int num_points;
+    int points_size;
+    segment_dir_t dir;
+} compactpoly_t;
+
+void add_segment(compactpoly_t*data, point_t start, segment_dir_t dir)
+{
+    if(data->poly->num_strokes == data->strokes_size) {
+	data->strokes_size <<= 1;
+	assert(data->strokes_size > data->poly->num_strokes);
+	data->poly->strokes = rfx_realloc(data->poly->strokes, data->strokes_size);
+    }
+    data->poly->strokes[data->poly->num_strokes].dir = dir;
+    data->points[0] = start;
+    data->num_points = 1;
+    data->dir = dir;
+}
+void finish_segment(compactpoly_t*data)
+{
+    if(data->num_points <= 1)
+	return;
+    point_t*p = malloc(sizeof(point_t)*data->num_points);
+    data->poly->strokes[data->poly->num_strokes-1].points = p;
+    if(data->dir == DIR_UP) {
+	int t;
+	int s = data->num_points;
+	for(t=0;t<data->num_points;t++) {
+	    p[--s] = data->points[t];
+	}
+    } else {
+	memcpy(p, data->points, sizeof(point_t)*data->num_points);
+    }
+    data->poly->num_strokes++;
+}
+static void compactmoveto(void*_data, double _x, double _y)
+{
+    compactpoly_t*data = (compactpoly_t*)_data;
+    data->dir = DIR_UNKNOWN;
+    point_t p;
+    p.x = convert_coord(_x);
+    p.y = convert_coord(_y);
+    data->last = p;
+}
+static void compactlineto(void*_data, double _x, double _y)
+{
+    compactpoly_t*data = (compactpoly_t*)_data;
+    point_t p;
+    p.x = convert_coord(_x);
+    p.y = convert_coord(_y);
+    if(p.y < data->last.y && data->dir != DIR_UP ||
+       p.y > data->last.y && data->dir != DIR_DOWN) {
+	data->dir = p.y > data->last.y ? DIR_DOWN : DIR_UP;
+	finish_segment(data);
+	add_segment(data, data->last, data->dir);
+    }
+    if(data->points_size == data->num_points) {
+	data->points_size <<= 1;
+	assert(data->points_size > data->num_points);
+	data->points = rfx_realloc(data->points, data->points_size);
+    }
+    data->points[data->num_points++] = p;
+}
+static void compactsetgridsize(void*data, double gridsize)
+{
+    compactpoly_t*d = (compactpoly_t*)data;
+    d->poly->gridsize = gridsize;
+}
+static void compactinit(compactpoly_t*data, double gridsize)
+{
+    data->poly = rfx_calloc(sizeof(gfxcompactpoly_t));
+    data->poly->gridsize = gridsize;
+    data->z = 1.0 / gridsize;
+    data->last.x = data->last.y = 0;
+    data->strokes_size = 16;
+    data->num_points = 0;
+    data->points_size = 16;
+    data->points = (point_t*)rfx_alloc(sizeof(point_t)*data->points_size);
+    data->poly->strokes = (gfxstroke_t*)rfx_alloc(sizeof(gfxstroke_t)*data->strokes_size);
+}
+static gfxcompactpoly_t*compactfinish(compactpoly_t*data)
+{
+    finish_segment(data);
+    data->poly->strokes = rfx_realloc(data->poly->strokes, sizeof(gfxstroke_t)*data->poly->num_strokes);
+    free(data->points);
+    return data->poly;
+}
+gfxcompactpoly_t* gfxcompactpoly_from_gfxline(gfxline_t*line, double gridsize)
+{
+    compactpoly_t data;
+    compactinit(&data, gridsize);
+    data.poly->gridsize = gridsize;
+    convert_gfxline(line, &data, compactmoveto, compactlineto, compactsetgridsize);
+    return compactfinish(&data);
+}
+gfxcompactpoly_t* gfxcompactpoly_from_file(const char*filename, double gridsize)
+{
+    compactpoly_t data;
+    compactinit(&data, gridsize);
+    data.poly->gridsize = gridsize;
+    convert_file(filename, &data, compactmoveto, compactlineto, compactsetgridsize);
+    return compactfinish(&data);
+}
+void gfxcompactpoly_free(gfxcompactpoly_t*poly)
+{
+    int t;
+    for(t=0;t<poly->num_strokes;t++) {
+	free(poly->strokes[t].points);
+    }
+    free(poly->strokes);
+    free(poly);
+}
+
diff --git a/lib/gfxpoly/convert.h b/lib/gfxpoly/convert.h
index 93bf980f..8ac8a86e 100644
--- a/lib/gfxpoly/convert.h
+++ b/lib/gfxpoly/convert.h
@@ -5,5 +5,9 @@
 
 gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize);
 gfxpoly_t* gfxpoly_from_file(const char*filename, double gridsize);
+gfxcompactpoly_t* gfxcompactpoly_from_gfxline(gfxline_t*line, double gridsize);
+gfxcompactpoly_t* gfxcompactpoly_from_file(const char*filename, double gridsize);
+
+void gfxcompactpoly_free(gfxcompactpoly_t*poly);
 
 #endif //__poly_convert_h__
diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
index 7036a61b..4bbd7765 100644
--- a/lib/gfxpoly/poly.c
+++ b/lib/gfxpoly/poly.c
@@ -596,7 +596,6 @@ static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y
     /* we need to calculate the xpos anew (and can't use start coordinate or
        intersection coordinate), because we need the xpos exactly at the end of
        this scanline.
-       TODO: might be faster to use XPOS_COMPARE here (see also _max)
      */
     double x = XPOS(seg, y);
     if(!range->segmin || x<range->xmin) {
@@ -652,7 +651,7 @@ static void add_points_to_positively_sloped_segments(status_t*status, int32_t y,
                     //break;
                 }
             }
-            seg = actlist_right(status->actlist, seg);
+            seg = seg->right;
         }
     }
     segrange_test_segment_min(range, first, y);
@@ -691,7 +690,7 @@ static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y,
                     //break;
                 }
             }
-            seg = actlist_left(status->actlist, seg);
+            seg = seg->left;
         }
     }
     segrange_test_segment_min(range, last, y);
@@ -721,6 +720,7 @@ static void add_points_to_ending_segments(status_t*status, int32_t y)
 
         if(status->xrow->num == 1) {
             // shortcut
+	    assert(seg->b.x == status->xrow->x[0]);
             point_t p = {status->xrow->x[0], y};
             insert_point_into_segment(status, seg, p);
         } else {
@@ -798,7 +798,7 @@ static void recalculate_windings(status_t*status, segrange_t*range)
 #endif
 
     if(end)
-        end = actlist_right(status->actlist, end);
+        end = end->right;
     while(s!=end) {
 #ifndef CHECKS
         if(s->changed)
@@ -888,12 +888,13 @@ static void event_apply(status_t*status, event_t*e)
             assert(!dict_contains(status->intersecting_segs, s));
             assert(!dict_contains(status->segs_with_point, s));
 #endif
-            segment_t*left = actlist_left(status->actlist, s);
-            segment_t*right = actlist_right(status->actlist, s);
+            segment_t*left = s->left;
+            segment_t*right = s->right;
             actlist_delete(status->actlist, s);
             if(left && right)
                 schedule_crossing(status, left, right);
 
+	    /* schedule segment for xrow handling */
             s->left = 0; s->right = status->ending_segments;
             status->ending_segments = s;
             break;
@@ -906,8 +907,8 @@ static void event_apply(status_t*status, event_t*e)
             segment_t*s = e->s1;
 	    assert(e->p.x == s->a.x && e->p.y == s->a.y);
             actlist_insert(status->actlist, s->a, s->b, s);
-            segment_t*left = actlist_left(status->actlist, s);
-            segment_t*right = actlist_right(status->actlist, s);
+            segment_t*left = s->left;
+            segment_t*right = s->right;
             if(left)
                 schedule_crossing(status, left, s);
             if(right)
@@ -920,10 +921,11 @@ static void event_apply(status_t*status, event_t*e)
 #ifdef DEBUG
             event_dump(e);
 #endif
-            if(actlist_right(status->actlist, e->s1) == e->s2 &&
-               actlist_left(status->actlist, e->s2) == e->s1) {
+            if(e->s1->right == e->s2) {
+		assert(e->s2->left == e->s1);
                 exchange_two(status, e);
             } else {
+		assert(e->s2->left != e->s1);
 #ifdef DEBUG
 		fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
 #endif
@@ -999,18 +1001,18 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c
 		assert(x<e->p.x);
                 edge_t*l= malloc(sizeof(edge_t));
                 l->a.y = l->b.y = y;
-		/* TODO: strictly speaking we need to draw from low x to high x so that left/right fillstyles add up
-		         (because the horizontal line's fill style controls the area *below* the line)
+		/* we draw from low x to high x so that left/right fillstyles add up
+                   (because the horizontal line's fill style controls the area *below* the line)
 		 */
-                l->a.x = x;
-                l->b.x = e->p.x;
+                l->a.x = e->p.x;
+                l->b.x = x;
                 l->next = poly->edges;
                 poly->edges = l;
 #ifdef CHECKS
 		/* the output should always be intersection free polygons, so check this horizontal
 		   line isn't hacking through any segments in the active list */
-		segment_t* start = actlist_find(actlist, l->a, l->a);
-		segment_t* s = actlist_find(actlist, l->b, l->b);
+		segment_t* start = actlist_find(actlist, l->b, l->b);
+		segment_t* s = actlist_find(actlist, l->a, l->a);
 		while(s!=start) {
 		    assert(s->a.y == y || s->b.y == y);
 		    s = s->left;
@@ -1020,7 +1022,6 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c
             segment_t*left = 0;
             segment_t*s = e->s1;
 
-            windstate_t before,after;
             switch(e->type) {
                 case EVENT_START: {
 		    assert(e->p.x == s->a.x && e->p.y == s->a.y);
@@ -1032,17 +1033,11 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c
                     e.s2 = 0;
                     heap_put(queue, &e);
                     left = actlist_left(actlist, s);
-
-                    before = left?left->wind:windrule->start(context);
-                    after = s->wind = windrule->add(context, before, s->fs, s->dir, s->polygon_nr);
                     break;
                 }
                 case EVENT_END: {
                     left = actlist_left(actlist, s);
                     actlist_delete(actlist, s);
-
-                    before = s->wind;
-                    after = left?left->wind:windrule->start(context);
                     break;
                 }
                 default: assert(0);
diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h
index 2ea3ff4b..ff623d36 100644
--- a/lib/gfxpoly/poly.h
+++ b/lib/gfxpoly/poly.h
@@ -8,7 +8,7 @@
 #define CHECKS
 #define SPLAY
 
-typedef enum {DIR_UP, DIR_DOWN} segment_dir_t;
+typedef enum {DIR_UP, DIR_DOWN, DIR_UNKNOWN} segment_dir_t;
 typedef enum {EVENT_CROSS, EVENT_END, EVENT_CORNER, EVENT_START, EVENT_HORIZONTAL} eventtype_t;
 typedef enum {SLOPE_POSITIVE, SLOPE_NEGATIVE} slope_t;
 
@@ -105,6 +105,18 @@ typedef struct _gfxpoly {
     edge_t*edges;
 } gfxpoly_t;
 
+typedef struct _gfxstroke {
+    segment_dir_t dir;
+    int num_points;
+    point_t*points;
+    fillstyle_t*fs;
+} gfxstroke_t;
+typedef struct _gfxcompactpoly {
+    double gridsize;
+    int num_strokes;
+    gfxstroke_t*strokes;
+} gfxcompactpoly_t;
+
 void gfxpoly_fail(char*expr, char*file, int line, const char*function);
 
 gfxpoly_t* gfxpoly_new(double gridsize);
diff --git a/lib/gfxpoly/test.c b/lib/gfxpoly/test.c
index 892798aa..6a41566e 100644
--- a/lib/gfxpoly/test.c
+++ b/lib/gfxpoly/test.c
@@ -135,6 +135,7 @@ int test0()
     gfxline_transform(b, &m);
 
     gfxpoly_t*poly = gfxpoly_from_gfxline(b, 0.05);
+    gfxline_free(b);
     gfxpoly_t*poly2 = gfxpoly_process(poly, &windrule_evenodd, &onepolygon);
     gfxpoly_destroy(poly2);
     gfxpoly_destroy(poly);
@@ -408,6 +409,8 @@ void test4(int argn, char*argv[])
 
 void extract_polygons_fill(gfxdevice_t*dev, gfxline_t*line, gfxcolor_t*color) 
 {
+    gfxcompactpoly_t*c = gfxcompactpoly_from_gfxline(line, 0.05);
+    gfxcompactpoly_free(c);
     gfxpoly_t*poly = gfxpoly_from_gfxline(line, 0.05);
     if(gfxpoly_size(poly)>100000) {
 	printf("%d segments (skipping)\n", gfxpoly_size(poly));
@@ -536,5 +539,5 @@ void test5(int argn, char*argv[])
 
 int main(int argn, char*argv[])
 {
-    test3(argn, argv);
+    test5(argn, argv);
 }