+ /*
+ |..| |...........| | |
+ |..| |...........| | |
+ |..+ + +..| +--+ +--+
+ |...........| |..| | |
+ |...........| |..| | |
+ */
+
+#ifdef DEBUG
+ fprintf(stderr, "========================================================================\n");
+#endif
+ heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
+ gfxpoly_enqueue(poly->edges, queue, windrule->start(1), 0);
+
+ actlist_t* actlist = actlist_new();
+
+ event_t*e = heap_chopmax(queue);
+ while(e) {
+ int y = e->p.y;
+ int x = 0;
+ char fill = 0;
+#ifdef DEBUG
+ fprintf(stderr, "----------------------------------- %d\n", y);
+ actlist_dump(actlist, y-1);
+#endif
+#ifdef CHECKS
+ actlist_verify(actlist, y-1);
+#endif
+ do {
+ if(fill && x != e->p.x) {
+#ifdef DEBUG
+ fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
+#endif
+ edge_t*l= malloc(sizeof(edge_t));
+ l->a.y = l->b.y = y;
+ l->a.x = x;
+ l->b.x = e->p.x;
+ l->next = poly->edges;
+ poly->edges = l;
+ }
+ 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);
+ actlist_insert(actlist, s->a, s->b, s);
+ event_t e;
+ e.type = EVENT_END;
+ e.p = s->b;
+ e.s1 = s;
+ e.s2 = 0;
+ heap_put(queue, &e);
+ left = actlist_left(actlist, s);
+
+ before = left?left->wind:windrule->start(1);
+ after = s->wind = windrule->add(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(1);
+ break;
+ }
+ default: assert(0);
+ }
+
+ 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",
+ y, e->type==EVENT_START?"start":"end",
+ s->nr,
+ left?left->nr:-1,
+ x,
+ before.is_filled, after.is_filled);
+#endif
+
+ if(e->type == EVENT_END)
+ segment_destroy(s);
+
+ free(e);
+ e = heap_chopmax(queue);
+ } while(e && y == e->p.y);
+
+ assert(!fill); // check that polygon is not bleeding
+ }
+ actlist_destroy(actlist);
+ heap_destroy(queue);
+}
+
+gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule)
+{
+ current_polygon = poly;