X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fgfxpoly%2Fpoly.c;h=d2c52953b1d471289aaee304db3915170a5581e9;hp=7036a61b59ad0dd5192d1f81c88dc48ae7979232;hb=fec1ab31707e68c2396b186e0e4928632402d649;hpb=f7e9e8a9616f1ecb26776369fda6807cf8821a68

diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
index 7036a61..d2c5295 100644
--- a/lib/gfxpoly/poly.c
+++ b/lib/gfxpoly/poly.c
@@ -9,21 +9,25 @@
 #include "active.h"
 #include "xrow.h"
 #include "wind.h"
+#include "convert.h"
 
 static gfxpoly_t*current_polygon = 0;
 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
 {
-    if(!current_polygon) {fprintf(stderr, "error outside polygon\n");exit(1);}
+    if(!current_polygon) {
+	fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
+	exit(1);
+    }
 
     void*md5 = init_md5();
-    
-    edge_t* s = current_polygon->edges;
-    while(s) {
-	update_md5(md5, (unsigned char*)&s->a.x, sizeof(s->a.x));
-	update_md5(md5, (unsigned char*)&s->a.y, sizeof(s->a.y));
-	update_md5(md5, (unsigned char*)&s->b.x, sizeof(s->b.x));
-	update_md5(md5, (unsigned char*)&s->b.y, sizeof(s->b.y));
-	s = s->next;
+   
+    int s,t;
+    gfxpolystroke_t*stroke = current_polygon->strokes;
+    for(;stroke;stroke=stroke->next) {
+	for(t=0;t<stroke->num_points;t++) {
+	    update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
+	    update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
+	}
     }
     unsigned char h[16];
     char filename[32+4+1];
@@ -75,11 +79,11 @@ typedef struct _status {
     int32_t y;
     actlist_t*actlist;
     heap_t*queue;
-    edge_t*output;
     xrow_t*xrow;
     windrule_t*windrule;
     windcontext_t*context;
     segment_t*ending_segments;
+    polywriter_t writer;
 #ifdef CHECKS
     dict_t*seen_crossings; //list of crossing we saw so far
     dict_t*intersecting_segs; //list of segments intersecting in this scanline
@@ -87,6 +91,13 @@ typedef struct _status {
 #endif
 } status_t;
 
+typedef struct _event {
+    eventtype_t type;
+    point_t p;
+    segment_t*s1;
+    segment_t*s2;
+} event_t;
+
 /* compare_events_simple differs from compare_events in that it schedules
    events from left to right regardless of type. It's only used in horizontal
    processing, in order to get an x-wise sorting of the current scanline */
@@ -110,65 +121,52 @@ static int compare_events(const void*_a,const void*_b)
     /* we need to schedule end after intersect (so that a segment about
        to end has a chance to tear up a few other segs first) and start
        events after end (in order not to confuse the intersection check, which
-       assumes there's an actual y overlap between active segments)). 
+       assumes there's an actual y overlap between active segments, and 
+       because ending segments in the active list make it difficult to insert
+       starting segments at the right position)). 
        Horizontal lines come last, because the only purpose
        they have is to create snapping coordinates for the segments (still)
        existing in this scanline.
     */
     d = b->type - a->type;
     if(d) return d;
-    d = b->p.x - a->p.x;
-    return d;
-}
+    return 0;
 
-gfxpoly_t* gfxpoly_new(double gridsize)
-{
-    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->edges;
-    while(s) {
-        edge_t*next  = s->next;
-        free(s);
-        s = next;
-    }
-    free(poly);
+    /* I don't see any reason why we would need to order by x- at least as long
+       as we do horizontal lines in a seperate pass */
+    //d = b->p.x - a->p.x;
+    //return d;
 }
+
 int gfxpoly_size(gfxpoly_t*poly)
 {
-    edge_t* s = poly->edges;
-    int t=0;
-    while(s) {
-        s = s->next;t++;
+    int s,t;
+    int edges = 0;
+    gfxpolystroke_t*stroke = poly->strokes;
+    for(;stroke;stroke=stroke->next) {
+	edges += stroke->num_points-1;
     }
-    return t;
+    return edges;
 }
 
 char gfxpoly_check(gfxpoly_t*poly)
 {
-    edge_t* s = poly->edges;
     dict_t*d = dict_new2(&point_type);
-    while(s) {
-        if(!dict_contains(d, &s->a)) {
-            dict_put(d, &s->a, (void*)(ptroff_t)1);
-        } else {
-            int count = (ptroff_t)dict_lookup(d, &s->a);
-            dict_del(d, &s->a);
-            count++;
-            dict_put(d, &s->a, (void*)(ptroff_t)count);
-        }
-        if(!dict_contains(d, &s->b)) {
-            dict_put(d, &s->b, (void*)(ptroff_t)1);
-        } else {
-            int count = (ptroff_t)dict_lookup(d, &s->b);
-            dict_del(d, &s->b);
-            count++;
-            dict_put(d, &s->b, (void*)(ptroff_t)count);
-        }
-        s = s->next;
+    int s,t;
+    gfxpolystroke_t*stroke = poly->strokes;
+    for(;stroke;stroke=stroke->next) {
+	for(s=0;s<stroke->num_points;s++) {
+	    point_t p = stroke->points[s];
+	    int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
+	    if(!dict_contains(d, &p)) {
+		dict_put(d, &p, (void*)(ptroff_t)num);
+	    } else {
+		int count = (ptroff_t)dict_lookup(d, &p);
+		dict_del(d, &p);
+		count+=num;
+		dict_put(d, &p, (void*)(ptroff_t)count);
+	    }
+	}
     }
     DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
         int count = (ptroff_t)c;
@@ -184,26 +182,36 @@ char gfxpoly_check(gfxpoly_t*poly)
 
 void gfxpoly_dump(gfxpoly_t*poly)
 {
-    edge_t* s = poly->edges;
+    int s,t;
     double g = poly->gridsize;
-    while(s) {
-        fprintf(stderr, "(%f,%f) -> (%f,%f)\n", s->a.x*g, s->a.y*g, s->b.x*g, s->b.y*g);
-        s = s->next;
+    fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
+    gfxpolystroke_t*stroke = poly->strokes;
+    for(;stroke;stroke=stroke->next) {
+	for(s=0;s<stroke->num_points-1;s++) {
+	    point_t a = stroke->points[s];
+	    point_t b = stroke->points[s+1];
+	    fprintf(stderr, "%s(%f,%f) -> (%f,%f)%s\n", s?" ":"[", a.x*g, a.y*g, b.x*g, b.y*g,
+		                                        s==stroke->num_points-2?"]":"");
+	}
     }
 }
 
-gfxpoly_t* gfxpoly_save(gfxpoly_t*poly, const char*filename)
+void 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) {
-        fprintf(fi, "%g setgray\n", s->b.y < s->a.y ? 0.7 : 0);
-        fprintf(fi, "%d %d moveto\n", s->a.x, s->a.y);
-        fprintf(fi, "%d %d lineto\n", s->b.x, s->b.y);
-        fprintf(fi, "stroke\n");
-        s = s->next;
+    int s,t;
+    gfxpolystroke_t*stroke = poly->strokes;
+    for(;stroke;stroke=stroke->next) {
+	for(s=0;s<stroke->num_points-1;s++) {
+	    point_t a = stroke->points[s];
+	    point_t b = stroke->points[s+1];
+	    fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
+	    fprintf(fi, "%d %d moveto\n", a.x, a.y);
+	    fprintf(fi, "%d %d lineto\n", b.x, b.y);
+	    fprintf(fi, "stroke\n");
+	}
     }
     fprintf(fi, "showpage\n");
     fclose(fi);
@@ -226,8 +234,6 @@ static void event_dump(event_t*e)
         fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
     } else if(e->type == EVENT_CROSS) {
         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
-    } else if(e->type == EVENT_CORNER) {
-        fprintf(stderr, "event: segment [%d] ends, segment [%d] starts, at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
     } else {
         assert(0);
     }
@@ -243,18 +249,17 @@ static void segment_dump(segment_t*s)
             (double)s->delta.x / s->delta.y);
 }
 
-static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr)
+static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr, segment_dir_t dir)
 {
-    if(y1<y2) {
-        s->dir = DIR_DOWN;
-    } else if(y1>y2) {
-        int32_t x = x1;x1=x2;x2=x;
-        int32_t y = y1;y1=y2;y2=y;
-        s->dir = DIR_UP;
+    s->dir = dir;
+    if(y1!=y2) {
+	assert(y1<y2);
     } else {
         /* up/down for horizontal segments is handled by "rotating"
            them 90° anticlockwise in screen coordinates (tilt your head to
-           the right) */
+           the right) 
+           TODO: is this still needed?
+	 */
         s->dir = DIR_UP;
         if(x1>x2) {
             s->dir = DIR_DOWN;
@@ -275,11 +280,8 @@ static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_
 
     s->pos = s->a;
     s->polygon_nr = polygon_nr;
-#define XDEBUG
-#ifdef XDEBUG
     static int segment_count=0;
     s->nr = segment_count++;
-#endif
 
 #ifdef CHECKS
     assert(LINE_EQ(s->a, s) == 0);
@@ -299,45 +301,67 @@ static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_
     assert(LINE_EQ(p, s) >= 0);
 #endif
 
+    /* TODO: make this int_type */
     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 }
 
-static segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr)
+static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
 {
     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
-    segment_init(s, x1, y1, x2, y2, polygon_nr);
+    segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
     return s;
 }
 
-static void segment_destroy(segment_t*s)
+static void segment_clear(segment_t*s)
 {
     dict_clear(&s->scheduled_crossings);
+}
+static void segment_destroy(segment_t*s)
+{
+    segment_clear(s);
     free(s);
 }
 
-static void gfxpoly_enqueue(edge_t*list, heap_t*queue, int polygon_nr)
+static void advance_stroke(heap_t*queue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
 {
-    edge_t*l;
-    for(l=list;l;l=l->next) {
-        if(l->a.x == l->b.x &&
-           l->a.y == l->b.y) {
-            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, polygon_nr);
+    while(pos < stroke->num_points-1) {
+	assert(stroke->points[pos].y <= stroke->points[pos+1].y);
+	segment_t*s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
+	s->stroke = stroke;
+	s->stroke_pos = ++pos;
 #ifdef DEBUG
-        if(l->tmp)
-            s->nr = l->tmp;
-        fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
-                s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
-                s->dir==DIR_UP?"up":"down");
+	/*if(l->tmp)
+	    s->nr = l->tmp;*/
+	fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (%d more to come)\n",
+		s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
+		s->dir==DIR_UP?"up":"down", stroke->num_points - 1 - pos);
 #endif
-        event_t e = event_new();
-        e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
-        e.p = s->a;
-        e.s1 = s;
-        e.s2 = 0;
-        heap_put(queue, &e);
+	event_t e = event_new();
+	e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
+	e.p = s->a;
+	e.s1 = s;
+	e.s2 = 0;
+	heap_put(queue, &e);
+	if(e.type != EVENT_HORIZONTAL) {
+	    break;
+	}
+    }
+}
+
+static void gfxpoly_enqueue(gfxpoly_t*p, heap_t*queue, int polygon_nr)
+{
+    int t;
+    gfxpolystroke_t*stroke = p->strokes;
+    for(;stroke;stroke=stroke->next) {
+	assert(stroke->num_points > 1);
+
+#ifdef CHECKS
+	int s;
+	for(s=0;s<stroke->num_points-1;s++) {
+	    assert(stroke->points[s].y <= stroke->points[s+1].y);
+	}
+#endif
+	advance_stroke(queue, stroke, polygon_nr, 0);
     }
 }
 
@@ -358,7 +382,6 @@ static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
     /* the code that's required (and the checks you can perform) before
        it can be said with 100% certainty that we indeed have a valid crossing
        amazes me every time. -mk */
-
 #ifdef CHECKS
     assert(s1!=s2);
     assert(s1->right == s2);
@@ -383,15 +406,26 @@ static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 #endif
 
     if(s1->maxx <= s2->minx) {
+#ifdef DEBUG
+            fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
+#endif
         /* bounding boxes don't intersect */
         return;
     }
 
-    if(dict_contains(&s1->scheduled_crossings, s2)) {
+#define REMEMBER_CROSSINGS
+#ifdef REMEMBER_CROSSINGS
+    if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
         /* FIXME: this whole segment hashing thing is really slow */
-        //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
+#ifdef DEBUG
+        fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
+//	DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
+//	    fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
+//	}
+#endif
         return; // we already know about this one
     }
+#endif
 
     double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
     if(!det) {
@@ -402,6 +436,9 @@ static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 #endif
             return;
         } else {
+#ifdef DEBUG
+            fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
+#endif
             /* lines are parallel */
             return;
         }
@@ -410,9 +447,16 @@ static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
     double bsign2 = LINE_EQ(s1->b, s2);
     if(asign2<0 && bsign2<0) {
         // segment1 is completely to the left of segment2
+#ifdef DEBUG
+            fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
+#endif
         return;
     }
     if(asign2>0 && bsign2>0)  {
+	// TODO: can this ever happen?
+#ifdef DEBUG
+            fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
+#endif
         // segment2 is completely to the left of segment1
         return;
     }
@@ -434,10 +478,16 @@ static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
     double bsign1 = LINE_EQ(s2->b, s1);
     if(asign1<0 && bsign1<0) {
         // segment1 is completely to the left of segment2
+#ifdef DEBUG
+            fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
+#endif
         return;
     }
     if(asign1>0 && bsign1>0)  {
         // segment2 is completely to the left of segment1
+#ifdef DEBUG
+            fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
+#endif
         return;
     }
     if(asign1==0) {
@@ -463,6 +513,10 @@ static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
     p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
     p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
 
+#ifndef REMEMBER_CROSSINGS
+    if(p.y < status->y) return;
+#endif
+
     assert(p.y >= status->y);
 #ifdef CHECKS
     assert(p.x >= s1->minx && p.x <= s1->maxx);
@@ -471,17 +525,21 @@ static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
     point_t pair;
     pair.x = s1->nr;
     pair.y = s2->nr;
+#ifdef REMEMBER_CROSSINGS
     assert(!dict_contains(status->seen_crossings, &pair));
     dict_put(status->seen_crossings, &pair, 0);
 #endif
+#endif
 #ifdef DEBUG
     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 #endif
 
+#ifdef REMEMBER_CROSSINGS
     /* we insert into each other's intersection history because these segments might switch
        places and we still want to look them up quickly after they did */
-    dict_put(&s1->scheduled_crossings, s2, 0);
-    dict_put(&s2->scheduled_crossings, s1, 0);
+    dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
+    dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
+#endif
 
     event_t e = event_new();
     e.type = EVENT_CROSS;
@@ -529,7 +587,6 @@ static inline box_t box_new(int32_t x, int32_t y)
     return box;
 }
 
-
 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 {
     assert(s->pos.x != p.x || s->pos.y != p.y);
@@ -547,15 +604,11 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 #endif
         // omit horizontal lines
         if(s->pos.y != p.y) {
-            edge_t*e = rfx_calloc(sizeof(edge_t));
-#ifdef DEBUG
-            e->tmp = s->nr;
-#endif
-            e->a = s->pos;
-            e->b = p;
-            assert(e->a.y != e->b.y);
-            e->next = status->output;
-            status->output = e;
+            point_t a = s->pos;
+            point_t b = p;
+            assert(a.y != b.y);
+	    status->writer.moveto(&status->writer, a.x, a.y);
+	    status->writer.lineto(&status->writer, b.x, b.y);
         }
     } else {
 #ifdef DEBUG
@@ -596,7 +649,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 +704,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 +743,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 +773,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 +851,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)
@@ -810,16 +863,16 @@ static void recalculate_windings(status_t*status, segrange_t*range)
             fillstyle_t*fs_old = s->fs_out;
             s->fs_out = status->windrule->diff(&wind, &s->wind);
 
+#ifdef DEBUG
+            fprintf(stderr, "[%d] %s/%d/%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit",
+		    fs_old!=s->fs_out?"CHANGED":"");
+#endif
             assert(!(!s->changed && fs_old!=s->fs_out));
             s->changed = 0;
 
 #ifdef CHECKS
             s->fs_out_ok = 1;
 #endif
-#ifdef DEBUG
-            fprintf(stderr, "[%d] %s/%d/%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill", s->fs_out?"draw":"omit",
-		    fs_old!=s->fs_out?"CHANGED":"");
-#endif
         }
         s = s->right;
     }
@@ -869,11 +922,13 @@ static void event_apply(status_t*status, event_t*e)
 {
     switch(e->type) {
         case EVENT_HORIZONTAL: {
+            segment_t*s = e->s1;
 #ifdef DEBUG
             event_dump(e);
 #endif
-            intersect_with_horizontal(status, e->s1);
-            segment_destroy(e->s1);e->s1=0;
+            intersect_with_horizontal(status, s);
+	    advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
+            segment_destroy(s);e->s1=0;
             break;
         }
         case EVENT_END: {
@@ -888,14 +943,16 @@ 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;
+	    advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
             break;
         }
         case EVENT_START: {
@@ -906,13 +963,13 @@ 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)
                 schedule_crossing(status, s, right);
-            schedule_endpoint(status, e->s1);
+            schedule_endpoint(status, s);
             break;
         }
         case EVENT_CROSS: {
@@ -920,25 +977,30 @@ 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
+#ifdef REMEMBER_CROSSINGS
                 /* ignore this crossing for now (there are some line segments in between).
                    it'll get rescheduled as soon as the "obstacles" are gone */
-                char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
-                char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
+                char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
+                char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
                 assert(del1 && del2);
+#endif
 #ifdef CHECKS
                 point_t pair;
                 pair.x = e->s1->nr;
                 pair.y = e->s2->nr;
+#ifdef REMEMBER_CROSSINGS
                 assert(dict_contains(status->seen_crossings, &pair));
                 dict_del(status->seen_crossings, &pair);
 #endif
+#endif
             }
         }
     }
@@ -975,7 +1037,7 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c
     fprintf(stderr, "========================================================================\n");
 #endif
     heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
-    gfxpoly_enqueue(poly->edges, queue, 0);
+    gfxpoly_enqueue(poly, queue, 0);
 
     actlist_t* actlist = actlist_new();
 
@@ -997,20 +1059,29 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c
                 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
 #endif
 		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)
+
+                gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
+		stroke->next = poly->strokes;
+		poly->strokes = stroke;
+
+		stroke->num_points = 2;
+		stroke->points = malloc(sizeof(point_t)*2);
+		stroke->dir = DIR_UP; // FIXME
+		stroke->fs = 0;
+		point_t a,b;
+                a.y = b.y = y;
+		/* 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->next = poly->edges;
-                poly->edges = l;
+                a.x = e->p.x;
+                b.x = x;
+		stroke->points[0] = a;
+		stroke->points[1] = b;
 #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, b, b);
+		segment_t* s = actlist_find(actlist, a, a);
 		while(s!=start) {
 		    assert(s->a.y == y || s->b.y == y);
 		    s = s->left;
@@ -1020,7 +1091,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 +1102,12 @@ 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);
+		    advance_stroke(queue, s->stroke, s->polygon_nr, s->stroke_pos);
                     break;
                 }
                 default: assert(0);
@@ -1051,12 +1116,11 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c
             x = e->p.x;
             fill ^= 1;//(before.is_filled != after.is_filled);
 #ifdef DEBUG
-            fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d before:%d after:%d\n",
+            fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
                     y, e->type==EVENT_START?"start":"end",
                     s->nr,
                     left?left->nr:-1,
-                    x,
-                    before.is_filled, after.is_filled);
+                    x);
 #endif
 
             if(e->type == EVENT_END)
@@ -1068,6 +1132,7 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*c
 
         assert(!fill); // check that polygon is not bleeding
     }
+
     actlist_destroy(actlist);
     heap_destroy(queue);
 }
@@ -1077,7 +1142,7 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*co
     current_polygon = poly;
     heap_t* queue = heap_new(sizeof(event_t), compare_events);
 
-    gfxpoly_enqueue(poly->edges, queue, /*polygon nr*/0);
+    gfxpoly_enqueue(poly, queue, /*polygon nr*/0);
 
     status_t status;
     memset(&status, 0, sizeof(status_t));
@@ -1085,8 +1150,12 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*co
     status.windrule = windrule;
     status.context = context;
     status.actlist = actlist_new();
+    gfxpolywriter_init(&status.writer);
+    status.writer.setgridsize(&status.writer, poly->gridsize);
+
 #ifdef CHECKS
     status.seen_crossings = dict_new2(&point_type);
+    int lasty=heap_peek(queue)?((event_t*)heap_peek(queue))->p.y-1:0;
 #endif
 
     status.xrow = xrow_new();
@@ -1094,6 +1163,7 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*co
     event_t*e = heap_chopmax(queue);
     while(e) {
         status.y = e->p.y;
+	assert(status.y>=lasty);
 #ifdef CHECKS
         status.intersecting_segs = dict_new2(&ptr_type);
         status.segs_with_point = dict_new2(&ptr_type);
@@ -1138,8 +1208,7 @@ gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*co
     heap_destroy(queue);
     xrow_destroy(status.xrow);
 
-    gfxpoly_t*p = gfxpoly_new(poly->gridsize);
-    p->edges = status.output;
+    gfxpoly_t*p = (gfxpoly_t*)status.writer.finish(&status.writer);
 
     add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
     return p;