X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fgfxpoly%2Fpoly.c;h=72e72aaa1454ba5f9b4d333231e351cbda404b10;hp=9dc42b003d5c895ec2abf5c5996451e907c72aaa;hb=c41f4433d3e721073c60d55cd923a087761e45f7;hpb=66a03382aab040571f94b0861719753bda3ff8f1

diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c
index 9dc42b0..72e72aa 100644
--- a/lib/gfxpoly/poly.c
+++ b/lib/gfxpoly/poly.c
@@ -2,12 +2,17 @@
 #include <assert.h>
 #include <memory.h>
 #include <math.h>
+#include "../mem.h"
+#include "../types.h"
 #include "../q.h"
 #include "poly.h"
 #include "active.h"
 #include "xrow.h"
+#include "wind.h"
 
-#define DEBUG
+//#define DEBUG
+//#undef assert
+//#define assert(x) 
 
 char point_equals(const void*o1, const void*o2) 
 {
@@ -44,8 +49,12 @@ type_t point_type = {
 
 typedef struct _status {
     int y;
+    int num_polygons;
     actlist_t*actlist;
     heap_t*queue;
+    edge_t*output;
+    xrow_t*xrow;
+    windrule_t*windrule;
 #ifdef DEBUG
     dict_t*seen_crossings; //list of crossing we saw so far
     dict_t*intersecting_segs; //list of segments intersecting in this scanline
@@ -61,6 +70,9 @@ int compare_events(const void*_a,const void*_b)
         return 1;
     } else if(a->p.y > b->p.y) {
         return -1;
+    /* we should schedule start events after end/intersect.
+       The order of end/intersect doesn't actually matter, however,
+       so this might be doing too much */
     } else if(a->type < b->type) {
         return 1;
     } else if(a->type > b->type) {
@@ -73,32 +85,62 @@ int compare_events(const void*_a,const void*_b)
         return 0;
 }
 
-gfxpoly_t* gfxpoly_new()
+gfxpoly_t* gfxpoly_new(double gridsize)
 {
-    return 0;
+    gfxpoly_t*p = (gfxpoly_t*)rfx_calloc(sizeof(gfxpoly_t));
+    p->gridsize = gridsize;
+    return p;
 }
 void gfxpoly_destroy(gfxpoly_t*poly)
 {
-    segment_t* s = poly;
+    edge_t* s = poly->edges;
     while(s) {
-        segment_t*right = s->right;
+        edge_t*next  = s->next;
         free(s);
-        s = right;
-        if(s==poly)
-            break;
+        s = next;
     }
+    free(poly);
+}
+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;
+    }
+    DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
+        int count = (ptroff_t)c;
+        if(count&1) {
+            fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
+            return 0;
+        }
+    }
+    return 1;
 }
 
 void gfxpoly_dump(gfxpoly_t*poly)
 {
-    segment_t* s = (segment_t*)poly;
+    edge_t* s = poly->edges;
+    double g = poly->gridsize;
     while(s) {
-        printf("[%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");
-        s = s->right;
-        if(s==poly)
-            break;
+        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;
     }
 }
 
@@ -111,27 +153,40 @@ inline static event_t event_new()
 
 void event_dump(event_t*e)
 {
-    if(e->type == EVENT_START) {
-        printf("event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
+    if(e->type == EVENT_HORIZONTAL) {
+        fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
+    } else if(e->type == EVENT_START) {
+        fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
     } else if(e->type == EVENT_END) {
-        printf("event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
+        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) {
-        printf("event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
-    } else assert(0);
+        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 {
+        assert(0);
+    }
 }
 
 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 
-void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
+void segment_init(segment_t*s, int x1, int y1, int x2, int y2, windstate_t windstate, int polygon_nr)
 {
-    assert(y1!=y2);
     if(y1<y2) {
         s->dir = DIR_DOWN;
-    } else {
+    } else if(y1>y2) {
         int x = x1;x1=x2;x2=x;
         int y = y1;y1=y2;y2=y;
         s->dir = DIR_UP;
+    } else {
+        /* up/down for horizontal segments is handled by "rotating"
+           them 90° anticlockwise in screen coordinates (tilt your head to 
+           the right) */
+        s->dir = DIR_UP;
+        if(x1>x2) {
+            s->dir = DIR_DOWN;
+            int x = x1;x1=x2;x2=x;
+            int y = y1;y1=y2;y2=y;
+        }
     }
     s->a.x = x1;
     s->a.y = y1;
@@ -142,9 +197,10 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
     s->delta.x = x2-x1;
     s->delta.y = y2-y1;
     s->pos = s->a;
-    s->tmp = -1;
-#ifdef DEBUG
-    static int segment_count=0; //for debugging
+    s->polygon_nr = polygon_nr;
+#define XDEBUG
+#ifdef XDEBUG
+    static int segment_count=0;
     s->nr = segment_count++;
 #endif
 
@@ -167,56 +223,61 @@ void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 }
 
-segment_t*segment_new(int x1, int y1, int x2, int y2)
+segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2, windstate_t initial, int polygon_nr)
 {
-    segment_t*s = malloc(sizeof(segment_t));
-    segment_init(s, x1, y1, x2, y2);
+    segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
+    segment_init(s, x1, y1, x2, y2, initial, polygon_nr);
     return s;
 }
-
-void segment_insert_before(segment_t**list, segment_t*add)
+void segment_destroy(segment_t*s)
 {
-    if(!*list) {
-        *list = add;
-        add->left = add->right = add;
-    } else {
-        add->left = (*list)->left;
-        add->right = (*list);
-        add->right->left = add;
-        add->left->right = add;
-    }
+    dict_clear(&s->scheduled_crossings);
+    free(s);
 }
 
-void segments_enqueue(segment_t*list, heap_t*queue)
+void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon_nr)
 {
-    segment_t*l = list;
-    while(l) {
-        segment_t*right = l->right;
-        l->left = l->right = 0;
+    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, initial, polygon_nr);
+#ifdef DEBUG
+        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");
+#endif
         event_t e = event_new();
-        e.type = EVENT_START;
-        e.p = l->a;e.s1 = l;e.s2 = 0;
-        heap_put(queue, &e);
-        e.type = EVENT_END;
-        e.p = l->b;e.s1 = l;e.s2 = 0;
+        e.type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
+        e.p = s->a;
+        e.s1 = s;
+        e.s2 = 0;
         heap_put(queue, &e);
-        l = right;
-        if(l==list) break;
     }
 }
 
-void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny)
+void schedule_endpoint(status_t*status, segment_t*s)
+{
+    // schedule end point of segment
+    assert(s->b.y > status->y);
+    event_t e;
+    e.type = EVENT_END;
+    e.p = s->b;
+    e.s1 = s;
+    e.s2 = 0;
+    heap_put(status->queue, &e);
+}
+
+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 */
     assert(s1!=s2);
 
-    if(dict_contains(&s1->scheduled_crossings, s2)) {
-        // we already know about this one
-        return;
-    }
-
     /* we probably could precompute these */
     int32_t minx1 = min32(s1->a.x,s1->b.x);
     int32_t miny1 = min32(s1->a.y,s1->b.y);
@@ -226,12 +287,25 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny)
     int32_t miny2 = min32(s2->a.y,s2->b.y);
     int32_t maxx2 = max32(s2->a.x,s2->b.x);
     int32_t maxy2 = max32(s2->a.y,s2->b.y);
-    
+      
+    /* both segments are active, so this can't happen */
+    assert(!(maxy1 <= miny2 || maxy2 <= miny1));
+
+    /* TODO: optimize this. remove y, precompute the two x values */
     if(maxx1 <= minx2 || maxx2 <= minx1 ||
        maxy1 <= miny2 || maxy2 <= miny1) {
         /* bounding boxes don't intersect */
         return;
     }
+    
+    if(dict_contains(&s1->scheduled_crossings, s2)) {
+        /* FIXME: this whole segment hashing thing is really slow */
+        //fprintf(stderr, "Encountered crossing between [%d] and [%d] twice\n", s1->nr, s2->nr);
+
+        // we already know about this one
+        return;
+    }
+
     double adx = s1->delta.x;
     double ady = s1->delta.y;
     double bdx = s2->delta.x;
@@ -240,7 +314,9 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny)
     if(!det) {
         if(s1->k == s2->k) {
             // lines are exactly on top of each other (ignored)
+#ifdef DEBUG
             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
+#endif
             return;
         } else {
             /* lines are parallel */
@@ -302,108 +378,29 @@ void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2, int miny)
     point_t p;
     p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
     p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
-    /* we only schedule crossings if they are *after* the current y. That way, we don't
-       schedule the same crossing twice */
-    if(p.y >= miny) {
-#ifdef DEBUG
-        point_t pair;
-        pair.x = s1->nr;
-        pair.y = s2->nr;
-        assert(!dict_contains(status->seen_crossings, &pair));
-        dict_put(status->seen_crossings, &pair, 0);
-#endif
-        event_t e = event_new();
-        e.type = EVENT_CROSS;
-        e.p = p;
-        e.s1 = s1;
-        e.s2 = s2;
+
+    assert(p.y >= status->y);
 #ifdef DEBUG
-        printf("schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, e.p.x, e.p.y);
+    point_t pair;
+    pair.x = s1->nr;
+    pair.y = s2->nr;
+    assert(!dict_contains(status->seen_crossings, &pair));
+    dict_put(status->seen_crossings, &pair, 0);
+    fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 #endif
-        /* we insert into each other's intersection history because these segments might switch
-           places */
-        dict_put(&s1->scheduled_crossings, s2, 0);
-        dict_put(&s2->scheduled_crossings, s1, 0);
 
-        heap_put(status->queue, &e);
-    }
-    return;
-}
+    /* 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);
 
-/* routine dealing with the special case of a number of line segments intersecting in exactly one
-   point */
-void exchange_many(status_t*status, event_t*e)
-{
-    int size = 16;
-    int n = 0;
-    segment_t**segs = (segment_t**)malloc(sizeof(segment_t*)*size);
-    segs[n] = e->s1;e->s1->tmp = n;n++;
-    segs[n] = e->s2;e->s2->tmp = n;n++;
-#ifdef DEBUG
-    dict_put(status->intersecting_segs, e->s1, 0);
-    dict_put(status->intersecting_segs, e->s2, 0);
-#endif
-    while(1) {
-        event_t*ee = heap_peek(status->queue);
-        if(ee->p.x != e->p.x ||
-           ee->p.y != e->p.y ||
-           ee->type != e->type) {
-            break;
-        }
-        if(n>=size-1) {
-            size *= 2;
-            segs = realloc(segs, sizeof(segment_t*)*size);
-        }
-        ee = heap_chopmax(status->queue);
-        if(ee->s1->tmp<0) {
-            segs[n] = ee->s1;ee->s1->tmp = n;n++;
-        }
-        if(ee->s2->tmp<0) {
-            segs[n] = ee->s2;ee->s2->tmp = n;n++;
-        }
-#ifdef DEBUG
-        dict_put(status->intersecting_segs, ee->s1, 0);
-        dict_put(status->intersecting_segs, ee->s2, 0);
-#endif
-    }
-    int t;
-#ifdef DEBUG
-    printf("event: multi-intersect: ");
-    for(t=0;t<n;t++) {
-        printf("[%d] ", segs[t]->nr);
-    }
-    printf("\n");
-#endif
-    segment_t*left = 0;
-    segment_t*right = 0;
-    char warn = 0;
-    for(t=0;t<n;t++) {
-        if(!segs[t]->left || segs[t]->left->tmp<0) {
-            assert(!left);
-            left = segs[t];
-        }
-        if(!segs[t]->right || segs[t]->right->tmp<0) {
-            assert(!right);
-            right = segs[t];
-        }
-        if(segs[t]->tmp<0)
-            warn = 1;
-    }
-    if(warn)
-        fprintf(stderr, "Warning: multi-cross section contains rogue segments\n");
-
-    assert(left);
-    assert(right);
-    assert(left!=right);
-    actlist_invert_fromto(status->actlist, left, right);
-    for(t=0;t<n;t++) {
-        segs[t]->tmp = -1;
-    }
-    free(segs);
-    if(right->left)
-        schedule_crossing(status, right->left, right, status->y);
-    if(left->right)
-        schedule_crossing(status, left, left->right, status->y);
+    event_t e = event_new();
+    e.type = EVENT_CROSS;
+    e.p = p;
+    e.s1 = s1;
+    e.s2 = s2;
+    heap_put(status->queue, &e);
+    return;
 }
 
 void exchange_two(status_t*status, event_t*e)
@@ -412,8 +409,10 @@ void exchange_two(status_t*status, event_t*e)
     segment_t*s1 = e->s1;
     segment_t*s2 = e->s2;
 #ifdef DEBUG
-    dict_put(status->intersecting_segs, s1, 0);
-    dict_put(status->intersecting_segs, s2, 0);
+    if(!dict_contains(status->intersecting_segs, s1))
+        dict_put(status->intersecting_segs, s1, 0);
+    if(!dict_contains(status->intersecting_segs, s2))
+        dict_put(status->intersecting_segs, s2, 0);
 #endif
     segment_t*left = actlist_left(status->actlist, s2);
     segment_t*right = actlist_right(status->actlist, s1);
@@ -425,23 +424,9 @@ void exchange_two(status_t*status, event_t*e)
     left = actlist_left(status->actlist, s2);
     right = actlist_right(status->actlist, s1);
     if(left)
-        schedule_crossing(status, left, s2, status->y);
+        schedule_crossing(status, left, s2);
     if(right)
-        schedule_crossing(status, s1, right, status->y);
-}
-
-void insert_point_into_segment(segment_t*s, point_t p)
-{
-    if(s->pos.x == p.x && s->pos.y == p.y) {
-#ifdef DEBUG
-        fprintf(stderr, "Notice: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr);
-#endif
-        return;
-    }
-#ifdef DEBUG
-    printf("[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y);
-#endif
-    s->pos = p;
+        schedule_crossing(status, s1, right);
 }
 
 typedef struct _box {
@@ -456,7 +441,39 @@ static inline box_t box_new(int x, int y)
     box.left2.y = box.right2.y = 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);
+
+#ifdef DEBUG
+    if(!dict_contains(status->segs_with_point, s))
+        dict_put(status->segs_with_point, s, 0);
+#endif
+
+    assert(s->fs_out_ok);
+    if(s->fs_out) {
+#ifdef DEBUG
+        fprintf(stderr, "[%d] receives next point (%d,%d) (drawing)\n", s->nr, p.x, p.y);
+#endif
+        // omit horizontal lines
+        if(s->pos.y != p.y) {
+            edge_t*e = malloc(sizeof(edge_t));
+            e->a = s->pos;
+            e->b = p;
+            assert(e->a.y != e->b.y);
+            e->next = status->output;
+            status->output = e;
+        }
+    } else {
+#ifdef DEBUG
+        fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
+#endif
+    }
+    s->pos = p;
+}
+
 /* possible optimizations:
    1.) keep two different active lists around, one for negative and one for
        positive slopes
@@ -465,23 +482,20 @@ static inline box_t box_new(int x, int y)
 */
 /*
    SLOPE_POSITIVE:
-       +     \ +        
+      \+     \ +        
 ------ I      \I       
       -I\----  I      
        I \   --I\---
        I  \    I \  -------
        +   \   +  \
 */
-void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
+static void add_points_to_positively_sloped_segments(status_t*status, int32_t y)
 {
     int t;
-    for(t=0;t<xrow->num;t++) {
-        box_t box = box_new(xrow->x[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);
-        if(seg) 
-            seg = seg->right;
-        else    
-            seg = actlist_leftmost(status->actlist);
+        seg = actlist_right(status->actlist, seg);
         while(seg) {
             if(seg->a.y == y) {
                 // this segment just started, ignore it
@@ -491,15 +505,12 @@ void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int3
                 double d1 = LINE_EQ(box.right1, seg);
                 double d2 = LINE_EQ(box.right2, seg);
                 if(d1>=0 || d2>=0) {
-#ifdef DEBUG
-                    dict_put(status->segs_with_point, seg, 0);
-#endif
-                    insert_point_into_segment(seg, box.right2);
+                    insert_point_into_segment(status, seg, box.right2);
                 } else {
                     break;
                 }
             }
-            seg = seg->right;
+            seg = actlist_right(status->actlist, seg);
         }
     }
 }
@@ -511,11 +522,11 @@ void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int3
    |   I    | /I   /
    |  /+    |/ +  /
 */
-void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
+static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y)
 {
     int t;
-    for(t=xrow->num-1;t>=0;t--) {
-        box_t box = box_new(xrow->x[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) {
@@ -526,58 +537,140 @@ void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int3
                 double d1 = LINE_EQ(box.left1, seg);
                 double d2 = LINE_EQ(box.left2, seg);
                 if(d1<0 || d2<0) {
-#ifdef DEBUG
-                    dict_put(status->segs_with_point, seg, 0);
-#endif
-                    insert_point_into_segment(seg, box.right2);
+                    insert_point_into_segment(status, seg, box.right2);
                 } else {
                     break;
                 }
             }
-            seg = seg->left;
+            seg = actlist_left(status->actlist, seg);
         }
     }
 }
 
+static void recalculate_windings(status_t*status)
+{
+    /* TODO: we could use some clever second linked list structure so that we
+             only need to process points we know we marked */
+    
+    segment_t*s = actlist_leftmost(status->actlist);
+    segment_t*last = 0;
+    while(s) {
+        windstate_t wind = last?last->wind:status->windrule->start(status->num_polygons);
+        s->wind = status->windrule->add(wind, s->fs, s->dir, s->polygon_nr);
+        s->fs_out = status->windrule->diff(&wind, &s->wind);
+        s->fs_out_ok = 1;
+#ifdef DEBUG
+        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
+        last = s;
+        s = actlist_right(status->actlist, s);
+    }
+#ifdef DEBUG
+    fprintf(stderr, "\n");
+#endif
+
+}
+
+void intersect_with_horizontal(status_t*status, segment_t*h)
+{
+    segment_t* left = actlist_find(status->actlist, h->a, h->a);
+    segment_t* right = actlist_find(status->actlist, h->b, h->b);
+
+    segment_t* s = right;
+
+    while(s!=left) {
+        assert(s);
+        /*
+           x1 + ((x2-x1)*(y-y1)) / dy = 
+           (x1*(y2-y) + x2*(y-y1)) / dy
+        */
+        point_t p;
+        p.y = status->y;
+        p.x = XPOS(s, p.y);
+#ifdef DEBUG
+        fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr, 
+                s->a.x, s->a.y,
+                s->b.x, s->b.y,
+                p.x, p.y
+                );
+#endif
+        assert(p.x >= h->a.x);
+        assert(p.x <= h->b.x);
+        assert(s->delta.x > 0 && p.x >= s->a.x || s->delta.x <= 0 && p.x <= s->a.x);
+        assert(s->delta.x > 0 && p.x <= s->b.x || s->delta.x <= 0 && p.x >= s->b.x);
+        xrow_add(status->xrow, p.x);
+
+        s = actlist_left(status->actlist, s);
+    }
+    xrow_add(status->xrow, h->a.x);
+}
+
 void event_apply(status_t*status, event_t*e)
 {
     switch(e->type) {
+        case EVENT_HORIZONTAL: {
+#ifdef DEBUG
+            event_dump(e);
+#endif
+            intersect_with_horizontal(status, e->s1);
+            break;
+        }
         case EVENT_END: {
             //delete segment from list
-            event_dump(e);
             segment_t*s = e->s1;
-            insert_point_into_segment(s, s->b);
+#ifdef DEBUG
+            event_dump(e);
+            dict_del(status->intersecting_segs, s);
+            dict_del(status->segs_with_point, s);
+            assert(!dict_contains(status->intersecting_segs, s));
+            assert(!dict_contains(status->segs_with_point, s));
+#endif
+            insert_point_into_segment(status, s, s->b);
             segment_t*left = actlist_left(status->actlist, s);
             segment_t*right = actlist_right(status->actlist, s);
             actlist_delete(status->actlist, s);
-            dict_clear(&s->scheduled_crossings);
             if(left && right)
-                schedule_crossing(status, left, right, status->y+1);
+                schedule_crossing(status, left, right);
+            segment_destroy(s);e->s1=0;
             break;
         }
         case EVENT_START: {
             //insert segment into list
+#ifdef DEBUG
             event_dump(e);
+#endif
             segment_t*s = e->s1;
             actlist_insert(status->actlist, e->p, s);
             segment_t*left = actlist_left(status->actlist, s);
             segment_t*right = actlist_right(status->actlist, s);
             if(left)
-                schedule_crossing(status, left, s, status->y+1);
+                schedule_crossing(status, left, s);
             if(right)
-                schedule_crossing(status, s, right, status->y+1);
+                schedule_crossing(status, s, right);
+            schedule_endpoint(status, e->s1);
             break;
         }
         case EVENT_CROSS: {
-            // exchange two (or more) segments
-            event_t*ee = heap_peek(status->queue);
-            if(ee->p.x != e->p.x ||
-               ee->p.y != e->p.y ||
-               ee->type != e->type) {
-                event_dump(e);
+            // exchange two segments
+#ifdef DEBUG
+            event_dump(e);
+#endif
+            if(actlist_right(status->actlist, e->s1) == e->s2 &&
+               actlist_left(status->actlist, e->s2) == e->s1) {
                 exchange_two(status, e);
             } else {
-                exchange_many(status, e);
+                /* 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);
+                assert(del1 && del2);
+#ifdef DEBUG
+                point_t pair;
+                pair.x = e->s1->nr;
+                pair.y = e->s2->nr;
+                assert(dict_contains(status->seen_crossings, &pair));
+                dict_del(status->seen_crossings, &pair);
+#endif
             }
         }
     }
@@ -587,7 +680,9 @@ void event_apply(status_t*status, event_t*e)
 void check_status(status_t*status)
 {
     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
-        if(!dict_contains(status->segs_with_point, s)) {
+        if((s->pos.x != s->b.x ||
+            s->pos.y != s->b.y) && 
+           !dict_contains(status->segs_with_point, s)) {
             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n", 
                     s->nr, 
                     s->delta.x<0?"-":"+",
@@ -598,19 +693,23 @@ void check_status(status_t*status)
 }
 #endif
 
-void gfxpoly_process(segment_t*poly)
+gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
 {
     heap_t* queue = heap_new(sizeof(event_t), compare_events);
-    segments_enqueue(poly, queue);
+    
+    gfxpoly_enqueue(poly->edges, queue, windrule->start(1), /*polygon nr*/0);
+
     status_t status;
     memset(&status, 0, sizeof(status_t));
+    status.num_polygons = 1;
     status.queue = queue;
+    status.windrule = windrule;
     status.actlist = actlist_new();
 #ifdef DEBUG
     status.seen_crossings = dict_new2(&point_type);
 #endif
     
-    xrow_t*xrow = xrow_new();
+    status.xrow = xrow_new();
 
     event_t*e = heap_chopmax(queue);
     while(e) {
@@ -618,20 +717,23 @@ void gfxpoly_process(segment_t*poly)
 #ifdef DEBUG
         status.intersecting_segs = dict_new2(&ptr_type);
         status.segs_with_point = dict_new2(&ptr_type);
-        printf("----------------------------------- %d\n", status.y);
+        fprintf(stderr, "----------------------------------- %d\n", status.y);
         actlist_verify_and_dump(status.actlist, status.y-1);
 #endif
-        xrow_reset(xrow);
+        xrow_reset(status.xrow);
         do {
-            xrow_add(xrow, e->p.x);
+            if(e->type != EVENT_HORIZONTAL) {
+                xrow_add(status.xrow, e->p.x);
+            }
             event_apply(&status, e);
             free(e);
             e = heap_chopmax(queue);
         } while(e && status.y == e->p.y);
 
-        xrow_sort(xrow);
-        add_points_to_positively_sloped_segments(&status, xrow, status.y);
-        add_points_to_negatively_sloped_segments(&status, xrow, status.y);
+        xrow_sort(status.xrow);
+        add_points_to_positively_sloped_segments(&status, status.y);
+        add_points_to_negatively_sloped_segments(&status, status.y);
+        recalculate_windings(&status);
 #ifdef DEBUG
         check_status(&status);
         dict_destroy(status.intersecting_segs);
@@ -641,7 +743,11 @@ void gfxpoly_process(segment_t*poly)
 #ifdef DEBUG
     dict_destroy(status.seen_crossings);
 #endif
+    actlist_destroy(status.actlist);
     heap_destroy(queue);
-    gfxpoly_destroy(poly);
-    xrow_destroy(xrow);
+    xrow_destroy(status.xrow);
+
+    gfxpoly_t*p = gfxpoly_new(poly->gridsize);
+    p->edges = status.output;
+    return p;
 }