lib/gfxpoly/poly.c

   1 #include <stdlib.h>
   2 #include <memory.h>
   3 #include <math.h>
   4 #include "../mem.h"
   5 #include "../types.h"
   6 #include "../q.h"
   7 #include "../MD5.h"
   8 #include "poly.h"
   9 #include "active.h"
  10 #include "xrow.h"
  11 #include "wind.h"
  12 #include "convert.h"
  13 #include "heap.h"
  14
  15 static gfxpoly_t*current_polygon = 0;
  16 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
  17 {
  18     if(!current_polygon) {
  19         fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
  20         exit(1);
  21     }
  22
  23     void*md5 = init_md5();
  24
  25     int s,t;
  26     gfxpolystroke_t*stroke = current_polygon->strokes;
  27     for(;stroke;stroke=stroke->next) {
  28         for(t=0;t<stroke->num_points;t++) {
  29             update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
  30             update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
  31         }
  32     }
  33     unsigned char h[16];
  34     char filename[32+4+1];
  35     finish_md5(md5, h);
  36     sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
  37             h[0],h[1],h[2],h[3],h[4],h[5],h[6],h[7],h[8],h[9],h[10],h[11],h[12],h[13],h[14],h[15]);
  38
  39     fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
  40     fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
  41
  42     gfxpoly_save(current_polygon, filename);
  43     exit(1);
  44 }
  45
  46 static char point_equals(const void*o1, const void*o2)
  47 {
  48     const point_t*p1 = o1;
  49     const point_t*p2 = o2;
  50     return p1->x == p2->x && p1->y == p2->y;
  51 }
  52 static unsigned int point_hash(const void*o)
  53 {
  54     const point_t*p = o;
  55     return p->x^p->y;
  56 }
  57 static void* point_dup(const void*o)
  58 {
  59     const point_t*p = o;
  60     point_t*n = malloc(sizeof(point_t));
  61     n->x = p->x;
  62     n->y = p->y;
  63     return n;
  64 }
  65 static void point_free(void*o)
  66 {
  67     point_t*p = o;
  68     p->x = 0;
  69     p->y = 0;
  70     free(p);
  71 }
  72 static type_t point_type = {
  73     equals: point_equals,
  74     hash: point_hash,
  75     dup: point_dup,
  76     free: point_free,
  77 };
  78
  79 typedef struct _event {
  80     eventtype_t type;
  81     point_t p;
  82     segment_t*s1;
  83     segment_t*s2;
  84 } event_t;
  85
  86 /* compare_events_simple differs from compare_events in that it schedules
  87    events from left to right regardless of type. It's only used in horizontal
  88    processing, in order to get an x-wise sorting of the current scanline */
  89 static inline int compare_events_simple(const void*_a,const void*_b)
  90 {
  91     event_t* a = (event_t*)_a;
  92     event_t* b = (event_t*)_b;
  93     int d = b->p.y - a->p.y;
  94     if(d) return d;
  95     d = b->p.x - a->p.x;
  96     if(d) return d;
  97     return 0;
  98 }
  99
 100 static inline int compare_events(const void*_a,const void*_b)
 101 {
 102     event_t* a = (event_t*)_a;
 103     event_t* b = (event_t*)_b;
 104     int d = b->p.y - a->p.y;
 105     if(d) return d;
 106     /* we need to schedule end after intersect (so that a segment about
 107        to end has a chance to tear up a few other segs first) and start
 108        events after end (in order not to confuse the intersection check, which
 109        assumes there's an actual y overlap between active segments, and
 110        because ending segments in the active list make it difficult to insert
 111        starting segments at the right position)).
 112        Horizontal lines come last, because the only purpose
 113        they have is to create snapping coordinates for the segments (still)
 114        existing in this scanline.
 115     */
 116     d = b->type - a->type;
 117     if(d) return d;
 118     return 0;
 119
 120     /* I don't see any reason why we would need to order by x- at least as long
 121        as we do horizontal lines in a seperate pass */
 122     //d = b->p.x - a->p.x;
 123     //return d;
 124 }
 125
 126 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
 127 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
 128 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
 129 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
 130
 131 typedef struct _status {
 132     int32_t y;
 133     actlist_t*actlist;
 134     queue_t queue;
 135     xrow_t*xrow;
 136     windrule_t*windrule;
 137     windcontext_t*context;
 138     segment_t*ending_segments;
 139
 140     gfxpolystroke_t*strokes;
 141 #ifdef CHECKS
 142     dict_t*seen_crossings; //list of crossing we saw so far
 143     dict_t*intersecting_segs; //list of segments intersecting in this scanline
 144     dict_t*segs_with_point; //lists of segments that received a point in this scanline
 145 #endif
 146 } status_t;
 147
 148
 149 int gfxpoly_size(gfxpoly_t*poly)
 150 {
 151     int s,t;
 152     int edges = 0;
 153     gfxpolystroke_t*stroke = poly->strokes;
 154     for(;stroke;stroke=stroke->next) {
 155         edges += stroke->num_points-1;
 156     }
 157     return edges;
 158 }
 159
 160 char gfxpoly_check(gfxpoly_t*poly)
 161 {
 162     dict_t*d = dict_new2(&point_type);
 163     int s,t;
 164     gfxpolystroke_t*stroke = poly->strokes;
 165     for(;stroke;stroke=stroke->next) {
 166         for(s=0;s<stroke->num_points;s++) {
 167             point_t p = stroke->points[s];
 168             int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
 169             if(!dict_contains(d, &p)) {
 170                 dict_put(d, &p, (void*)(ptroff_t)num);
 171             } else {
 172                 int count = (ptroff_t)dict_lookup(d, &p);
 173                 dict_del(d, &p);
 174                 count+=num;
 175                 dict_put(d, &p, (void*)(ptroff_t)count);
 176             }
 177         }
 178     }
 179     DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
 180         int count = (ptroff_t)c;
 181         if(count&1) {
 182             fprintf(stderr, "Point (%f,%f) occurs %d times\n", p->x*poly->gridsize, p->y*poly->gridsize, count);
 183             dict_destroy(d);
 184             return 0;
 185         }
 186     }
 187     dict_destroy(d);
 188     return 1;
 189 }
 190
 191 void gfxpoly_dump(gfxpoly_t*poly)
 192 {
 193     int s,t;
 194     double g = poly->gridsize;
 195     fprintf(stderr, "polyon %08x (gridsize: %f)\n", poly, poly->gridsize);
 196     gfxpolystroke_t*stroke = poly->strokes;
 197     for(;stroke;stroke=stroke->next) {
 198         fprintf(stderr, "%08x", stroke);
 199         for(s=0;s<stroke->num_points-1;s++) {
 200             point_t a = stroke->points[s];
 201             point_t b = stroke->points[s+1];
 202             fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s\n", s?"        ":"", a.x*g, a.y*g, b.x*g, b.y*g,
 203                                                         s==stroke->num_points-2?"]":"");
 204         }
 205     }
 206 }
 207
 208 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
 209 {
 210     FILE*fi = fopen(filename, "wb");
 211     fprintf(fi, "%% gridsize %f\n", poly->gridsize);
 212     fprintf(fi, "%% begin\n");
 213     int s,t;
 214     gfxpolystroke_t*stroke = poly->strokes;
 215     for(;stroke;stroke=stroke->next) {
 216             fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
 217         point_t p = stroke->points[0];
 218         fprintf(fi, "%d %d moveto\n", p.x, p.y);
 219         for(s=1;s<stroke->num_points;s++) {
 220             p = stroke->points[s];
 221             fprintf(fi, "%d %d lineto\n", p.x, p.y);
 222         }
 223         fprintf(fi, "stroke\n");
 224     }
 225     fprintf(fi, "showpage\n");
 226     fclose(fi);
 227 }
 228
 229 inline static event_t* event_new()
 230 {
 231     event_t*e = rfx_calloc(sizeof(event_t));
 232     return e;
 233 }
 234 inline static void event_free(event_t*e)
 235 {
 236     free(e);
 237 }
 238
 239 static void event_dump(event_t*e)
 240 {
 241     if(e->type == EVENT_HORIZONTAL) {
 242         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);
 243     } else if(e->type == EVENT_START) {
 244         fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 245     } else if(e->type == EVENT_END) {
 246         fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 247     } else if(e->type == EVENT_CROSS) {
 248         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
 249     } else {
 250         assert(0);
 251     }
 252 }
 253
 254 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 255 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 256
 257 static void segment_dump(segment_t*s)
 258 {
 259     fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
 260     fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f\n", s->delta.x, s->delta.y, s->k,
 261             (double)s->delta.x / s->delta.y);
 262 }
 263
 264 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)
 265 {
 266     s->dir = dir;
 267     if(y1!=y2) {
 268         assert(y1<y2);
 269     } else {
 270         /* We need to make sure horizontal segments always go from left to right.
 271            "up/down" for horizontal segments is handled by "rotating"
 272            them 90° anticlockwise in screen coordinates (tilt your head to
 273            the right).
 274          */
 275         s->dir = DIR_UP;
 276         if(x1>x2) {
 277             s->dir = DIR_DOWN;
 278             int32_t x = x1;x1=x2;x2=x;
 279             int32_t y = y1;y1=y2;y2=y;
 280         }
 281     }
 282     s->a.x = x1;
 283     s->a.y = y1;
 284     s->b.x = x2;
 285     s->b.y = y2;
 286     s->k = (double)x1*y2-(double)x2*y1;
 287     s->left = s->right = 0;
 288     s->delta.x = x2-x1;
 289     s->delta.y = y2-y1;
 290     s->minx = min32(x1,x2);
 291     s->maxx = max32(x1,x2);
 292
 293     s->pos = s->a;
 294     s->polygon_nr = polygon_nr;
 295     static int segment_count=0;
 296     s->nr = segment_count++;
 297
 298 #ifdef CHECKS
 299     assert(LINE_EQ(s->a, s) == 0);
 300     assert(LINE_EQ(s->b, s) == 0);
 301
 302     /* check that all signs are in order:
 303        a        a
 304        |\      /|
 305        | \    / |
 306      minx-b  b--maxx
 307      < 0        > 0
 308     */
 309     point_t p = s->b;
 310     p.x = min32(s->a.x, s->b.x);
 311     assert(LINE_EQ(p, s) <= 0);
 312     p.x = max32(s->a.x, s->b.x);
 313     assert(LINE_EQ(p, s) >= 0);
 314 #endif
 315
 316 #ifndef DONT_REMEMBER_CROSSINGS
 317     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 318 #endif
 319 }
 320
 321 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
 322 {
 323     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
 324     segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
 325     return s;
 326 }
 327
 328 static void segment_clear(segment_t*s)
 329 {
 330 #ifndef DONT_REMEMBER_CROSSINGS
 331     dict_clear(&s->scheduled_crossings);
 332 #endif
 333 }
 334 static void segment_destroy(segment_t*s)
 335 {
 336     segment_clear(s);
 337     free(s);
 338 }
 339
 340 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
 341 {
 342     if(!stroke)
 343         return;
 344     segment_t*s = 0;
 345     /* we need to queue multiple segments at once because we need to process start events
 346        before horizontal events */
 347     while(pos < stroke->num_points-1) {
 348         assert(stroke->points[pos].y <= stroke->points[pos+1].y);
 349         s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
 350         pos++;
 351         s->stroke = 0;
 352         s->stroke_pos = 0;
 353 #ifdef DEBUG
 354         /*if(l->tmp)
 355             s->nr = l->tmp;*/
 356         fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %08x, %d more to come)\n",
 357                 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
 358                 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
 359 #endif
 360         event_t* e = event_new();
 361         e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
 362         e->p = s->a;
 363         e->s1 = s;
 364         e->s2 = 0;
 365
 366         if(queue) queue_put(queue, e);
 367         else hqueue_put(hqueue, e);
 368
 369         if(e->type != EVENT_HORIZONTAL) {
 370             break;
 371         }
 372     }
 373     if(s) {
 374 #ifdef DEBUG
 375         fprintf(stderr, "attaching contingency of stroke %08x to segment [%d] %s\n",
 376                 stroke, s, s->delta.y?"":"(horizontal)");
 377 #endif
 378         s->stroke = stroke;
 379         s->stroke_pos = pos;
 380     }
 381 }
 382
 383 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
 384 {
 385     int t;
 386     gfxpolystroke_t*stroke = p->strokes;
 387     for(;stroke;stroke=stroke->next) {
 388         assert(stroke->num_points > 1);
 389
 390 #ifdef CHECKS
 391         int s;
 392         for(s=0;s<stroke->num_points-1;s++) {
 393             assert(stroke->points[s].y <= stroke->points[s+1].y);
 394         }
 395 #endif
 396         advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
 397     }
 398 }
 399
 400 static void schedule_endpoint(status_t*status, segment_t*s)
 401 {
 402     // schedule end point of segment
 403     assert(s->b.y > status->y);
 404     event_t*e = event_new();
 405     e->type = EVENT_END;
 406     e->p = s->b;
 407     e->s1 = s;
 408     e->s2 = 0;
 409     queue_put(&status->queue, e);
 410 }
 411
 412 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 413 {
 414     /* the code that's required (and the checks you can perform) before
 415        it can be said with 100% certainty that we indeed have a valid crossing
 416        amazes me every time. -mk */
 417 #ifdef CHECKS
 418     assert(s1!=s2);
 419     assert(s1->right == s2);
 420     assert(s2->left == s1);
 421     int32_t miny1 = min32(s1->a.y,s1->b.y);
 422     int32_t maxy1 = max32(s1->a.y,s1->b.y);
 423     int32_t miny2 = min32(s2->a.y,s2->b.y);
 424     int32_t maxy2 = max32(s2->a.y,s2->b.y);
 425     int32_t minx1 = min32(s1->a.x,s1->b.x);
 426     int32_t minx2 = min32(s2->a.x,s2->b.x);
 427     int32_t maxx1 = max32(s1->a.x,s1->b.x);
 428     int32_t maxx2 = max32(s2->a.x,s2->b.x);
 429     /* check that precomputation is sane */
 430     assert(minx1 == s1->minx && minx2 == s2->minx);
 431     assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
 432     /* both segments are active, so this can't happen */
 433     assert(!(maxy1 <= miny2 || maxy2 <= miny1));
 434     /* we know that right now, s2 is to the right of s1, so there's
 435        no way the complete bounding box of s1 is to the right of s1 */
 436     assert(!(s1->minx > s2->maxx));
 437     assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
 438 #endif
 439
 440     if(s1->maxx <= s2->minx) {
 441 #ifdef DEBUG
 442             fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
 443 #endif
 444         /* bounding boxes don't intersect */
 445         return;
 446     }
 447
 448 #ifndef DONT_REMEMBER_CROSSINGS
 449     if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
 450         /* FIXME: this whole segment hashing thing is really slow */
 451 #ifdef DEBUG
 452         fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
 453 //      DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
 454 //          fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
 455 //      }
 456 #endif
 457         return; // we already know about this one
 458     }
 459 #endif
 460
 461     double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
 462     if(!det) {
 463         if(s1->k == s2->k) {
 464             // lines are exactly on top of each other (ignored)
 465 #ifdef DEBUG
 466             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
 467 #endif
 468             return;
 469         } else {
 470 #ifdef DEBUG
 471             fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
 472 #endif
 473             /* lines are parallel */
 474             return;
 475         }
 476     }
 477
 478     double asign2 = LINE_EQ(s1->a, s2);
 479     if(asign2==0) {
 480         // segment1 touches segment2 in a single point (ignored)
 481 #ifdef DEBUG
 482         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
 483 #endif
 484         return;
 485     }
 486     double bsign2 = LINE_EQ(s1->b, s2);
 487     if(bsign2==0) {
 488         // segment1 touches segment2 in a single point (ignored)
 489 #ifdef DEBUG
 490         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
 491 #endif
 492         return;
 493     }
 494
 495     if(asign2<0 && bsign2<0) {
 496         // segment1 is completely to the left of segment2
 497 #ifdef DEBUG
 498             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);
 499 #endif
 500         return;
 501     }
 502     if(asign2>0 && bsign2>0)  {
 503         // segment1 is completely to the right of segment2
 504 #ifndef DONT_REMEMBER_CROSSINGS
 505         assert(0);
 506 #endif
 507 #ifdef DEBUG
 508             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);
 509 #endif
 510         return;
 511     }
 512
 513     double asign1 = LINE_EQ(s2->a, s1);
 514     if(asign1==0) {
 515         // segment2 touches segment1 in a single point (ignored)
 516 #ifdef DEBUG
 517         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
 518 #endif
 519         return;
 520     }
 521     double bsign1 = LINE_EQ(s2->b, s1);
 522     if(asign2==0) {
 523         // segment2 touches segment1 in a single point (ignored)
 524 #ifdef DEBUG
 525         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
 526 #endif
 527         return;
 528     }
 529
 530     if(asign1<0 && bsign1<0) {
 531         // segment2 is completely to the left of segment1
 532 #ifndef DONT_REMEMBER_CROSSINGS
 533         assert(0);
 534 #endif
 535 #ifdef DEBUG
 536             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);
 537 #endif
 538         return;
 539     }
 540     if(asign1>0 && bsign1>0)  {
 541         // segment2 is completely to the right of segment1
 542 #ifdef DEBUG
 543             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);
 544 #endif
 545         return;
 546     }
 547
 548 #ifdef DONT_REMEMBER_CROSSINGS
 549     /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
 550        there's not way s2 would be to the left of s1 otherwise */
 551     if(asign1<0 && bsign1>0) return;
 552     if(asign2>0 && bsign2<0) return;
 553 #endif
 554
 555     assert(!(asign1<0 && bsign1>0));
 556     assert(!(asign2>0 && bsign2<0));
 557
 558     /* TODO: should we precompute these? */
 559     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
 560     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 561
 562     point_t p;
 563     p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
 564     p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
 565
 566     assert(p.y >= status->y);
 567 #ifdef CHECKS
 568     assert(p.x >= s1->minx && p.x <= s1->maxx);
 569     assert(p.x >= s2->minx && p.x <= s2->maxx);
 570
 571     point_t pair;
 572     pair.x = s1->nr;
 573     pair.y = s2->nr;
 574 #ifndef DONT_REMEMBER_CROSSINGS
 575     assert(!dict_contains(status->seen_crossings, &pair));
 576     dict_put(status->seen_crossings, &pair, 0);
 577 #endif
 578 #endif
 579 #ifdef DEBUG
 580     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 581 #endif
 582
 583 #ifndef DONT_REMEMBER_CROSSINGS
 584     /* we insert into each other's intersection history because these segments might switch
 585        places and we still want to look them up quickly after they did */
 586     dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
 587     dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
 588 #endif
 589
 590     event_t* e = event_new();
 591     e->type = EVENT_CROSS;
 592     e->p = p;
 593     e->s1 = s1;
 594     e->s2 = s2;
 595     queue_put(&status->queue, e);
 596     return;
 597 }
 598
 599 static void exchange_two(status_t*status, event_t*e)
 600 {
 601     //exchange two segments in list
 602     segment_t*s1 = e->s1;
 603     segment_t*s2 = e->s2;
 604 #ifdef CHECKS
 605     if(!dict_contains(status->intersecting_segs, s1))
 606         dict_put(status->intersecting_segs, s1, 0);
 607     if(!dict_contains(status->intersecting_segs, s2))
 608         dict_put(status->intersecting_segs, s2, 0);
 609 #endif
 610     assert(s2->left == s1);
 611     assert(s1->right == s2);
 612     actlist_swap(status->actlist, s1, s2);
 613     assert(s2->right  == s1);
 614     assert(s1->left == s2);
 615     segment_t*left = s2->left;
 616     segment_t*right = s1->right;
 617     if(left)
 618         schedule_crossing(status, left, s2);
 619     if(right)
 620         schedule_crossing(status, s1, right);
 621 }
 622
 623 typedef struct _box {
 624     point_t left1, left2, right1, right2;
 625 } box_t;
 626 static inline box_t box_new(int32_t x, int32_t y)
 627 {
 628     box_t box;
 629     box.right1.x = box.right2.x = x;
 630     box.left1.x = box.left2.x = x-1;
 631     box.left1.y = box.right1.y = y-1;
 632     box.left2.y = box.right2.y = y;
 633     return box;
 634 }
 635
 636 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 637 {
 638     assert(s->pos.x != p.x || s->pos.y != p.y);
 639
 640 #ifdef CHECKS
 641     if(!dict_contains(status->segs_with_point, s))
 642         dict_put(status->segs_with_point, s, 0);
 643     assert(s->fs_out_ok);
 644 #endif
 645
 646     if(s->fs_out) {
 647 #ifdef DEBUG
 648         fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
 649                 s->pos.x, s->pos.y, p.x, p.y);
 650 #endif
 651         /* XXX we probably will never output circular/anticircular polygons, but if
 652            we do, we would need to set the segment direction here */
 653         fillstyle_t*fs = s->fs_out;
 654
 655         // omit horizontal lines
 656         if(s->pos.y != p.y) {
 657             point_t a = s->pos;
 658             point_t b = p;
 659             assert(a.y != b.y);
 660
 661             gfxpolystroke_t*stroke = status->strokes;
 662             while(stroke) {
 663                 point_t p = stroke->points[stroke->num_points-1];
 664                 if(p.x == a.x && p.y == a.y && stroke->fs == fs)
 665                     break;
 666                 stroke = stroke->next;
 667             }
 668             if(!stroke) {
 669                 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
 670                 stroke->dir = DIR_DOWN;
 671                 stroke->fs = fs;
 672                 stroke->next = status->strokes;
 673                 status->strokes = stroke;
 674                 stroke->points_size = 2;
 675                 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
 676                 stroke->points[0] = a;
 677                 stroke->num_points = 1;
 678             } else if(stroke->num_points == stroke->points_size) {
 679                 stroke->points_size *= 2;
 680                 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
 681             }
 682             stroke->points[stroke->num_points++] = b;
 683         }
 684     } else {
 685 #ifdef DEBUG
 686         fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
 687 #endif
 688     }
 689     s->pos = p;
 690 }
 691
 692 typedef struct _segrange {
 693     double xmin;
 694     segment_t*segmin;
 695     double xmax;
 696     segment_t*segmax;
 697 } segrange_t;
 698
 699 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
 700 {
 701 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
 702     segment_t*min = range->segmin;
 703     segment_t*max = range->segmax;
 704
 705     /* we need this because if two segments intersect exactly on
 706        the scanline, segrange_test_segment_{min,max} can't tell which
 707        one is smaller/larger */
 708     if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
 709         min = min->left;
 710     }
 711     if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
 712         max = max->right;
 713     }
 714     range->segmin = min;
 715     range->segmax = max;
 716 }
 717 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
 718 {
 719     if(!seg) return;
 720     /* we need to calculate the xpos anew (and can't use start coordinate or
 721        intersection coordinate), because we need the xpos exactly at the end of
 722        this scanline.
 723      */
 724     double x = XPOS(seg, y);
 725     if(!range->segmin || x<range->xmin) {
 726         range->segmin = seg;
 727         range->xmin = x;
 728     }
 729 }
 730 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
 731 {
 732     if(!seg) return;
 733     double x = XPOS(seg, y);
 734     if(!range->segmax || x>range->xmax) {
 735         range->segmax = seg;
 736         range->xmax = x;
 737     }
 738 }
 739
 740 /*
 741    SLOPE_POSITIVE:
 742       \+     \ +
 743 ------ I      \I
 744       -I\----  I
 745        I \   --I\---
 746        I  \    I \  -------
 747        +   \   +  \
 748 */
 749 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 750 {
 751     segment_t*first=0, *last = 0;
 752     int t;
 753     for(t=0;t<status->xrow->num;t++) {
 754         box_t box = box_new(status->xrow->x[t], y);
 755         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 756
 757         seg = actlist_right(status->actlist, seg);
 758         while(seg) {
 759             if(seg->a.y == y) {
 760                 // this segment started in this scanline, ignore it
 761                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 762             } else if(seg->delta.x <= 0) {
 763                 // ignore segment w/ negative slope
 764             } else {
 765                 last = seg;if(!first) {first=seg;}
 766                 double d1 = LINE_EQ(box.right1, seg);
 767                 double d2 = LINE_EQ(box.right2, seg);
 768                 if(d1>0 || d2>=0) {
 769                     seg->changed = 1;
 770                     insert_point_into_segment(status, seg, box.right2);
 771                 } else {
 772                     /* we unfortunately can't break here- the active list is sorted according
 773                        to the *bottom* of the scanline. hence pretty much everything that's still
 774                        coming might reach into our box */
 775                     //break;
 776                 }
 777             }
 778             seg = seg->right;
 779         }
 780     }
 781     segrange_test_segment_min(range, first, y);
 782     segrange_test_segment_max(range, last, y);
 783 }
 784 /* SLOPE_NEGATIVE:
 785    |   +   /|  +  /    /
 786    |   I  / |  I /    /
 787    |   I /  |  I/    /
 788    |   I/   |  I    /
 789    |   I    | /I   /
 790    |  /+    |/ +  /
 791 */
 792 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 793 {
 794     segment_t*first=0, *last = 0;
 795     int t;
 796     for(t=status->xrow->num-1;t>=0;t--) {
 797         box_t box = box_new(status->xrow->x[t], y);
 798         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 799
 800         while(seg) {
 801             if(seg->a.y == y) {
 802                 // this segment started in this scanline, ignore it
 803                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 804             } else if(seg->delta.x > 0) {
 805                 // ignore segment w/ positive slope
 806             } else {
 807                 last = seg;if(!first) {first=seg;}
 808                 double d1 = LINE_EQ(box.left1, seg);
 809                 double d2 = LINE_EQ(box.left2, seg);
 810                 if(d1<0 || d2<0) {
 811                     seg->changed = 1;
 812                     insert_point_into_segment(status, seg, box.right2);
 813                 } else {
 814                     //break;
 815                 }
 816             }
 817             seg = seg->left;
 818         }
 819     }
 820     segrange_test_segment_min(range, last, y);
 821     segrange_test_segment_max(range, first, y);
 822 }
 823
 824 /* segments ending in the current scanline need xrow treatment like everything else.
 825    (consider an intersection taking place just above a nearly horizontal segment
 826    ending on the current scanline- the intersection would snap down *below* the
 827    ending segment if we don't add the intersection point to the latter right away)
 828    we need to treat ending segments seperately, however. we have to delete them from
 829    the active list right away to make room for intersect operations (which might
 830    still be in the current scanline- consider two 45° polygons and a vertical polygon
 831    intersecting on an integer coordinate). but once they're no longer in the active list,
 832    we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
 833    them to the active list just for point snapping would be overkill.
 834    (One other option to consider, however, would be to create a new active list only
 835     for ending segments)
 836 */
 837 static void add_points_to_ending_segments(status_t*status, int32_t y)
 838 {
 839     segment_t*seg = status->ending_segments;
 840     while(seg) {
 841         segment_t*next = seg->right;seg->right=0;
 842
 843         assert(seg->b.y == status->y);
 844
 845         if(status->xrow->num == 1) {
 846             // shortcut
 847             assert(seg->b.x == status->xrow->x[0]);
 848             point_t p = {status->xrow->x[0], y};
 849             insert_point_into_segment(status, seg, p);
 850         } else {
 851             int t;
 852             int start=0,end=status->xrow->num,dir=1;
 853             if(seg->delta.x < 0) {
 854                 start = status->xrow->num-1;
 855                 end = dir = -1;
 856             }
 857             for(t=start;t!=end;t+=dir) {
 858                 box_t box = box_new(status->xrow->x[t], y);
 859                 double d0 = LINE_EQ(box.left1, seg);
 860                 double d1 = LINE_EQ(box.left2, seg);
 861                 double d2 = LINE_EQ(box.right1, seg);
 862                 double d3 = LINE_EQ(box.right2, seg);
 863                 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
 864                      d0<=0 && d1<=0 && d2<=0 && d3<0)) {
 865                     insert_point_into_segment(status, seg, box.right2);
 866                     break;
 867                 }
 868             }
 869
 870 #ifdef CHECKS
 871             /* we *need* to find a point to insert. the segment's own end point
 872                is in that list, for Pete's sake. */
 873             assert(t!=end);
 874 #endif
 875         }
 876         // now that this is done, too, we can also finally free this segment
 877         segment_destroy(seg);
 878         seg = next;
 879     }
 880     status->ending_segments = 0;
 881 }
 882
 883 static void recalculate_windings(status_t*status, segrange_t*range)
 884 {
 885 #ifdef DEBUG
 886     fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
 887 #endif
 888     segrange_adjust_endpoints(range, status->y);
 889
 890     segment_t*s = range->segmin;
 891     segment_t*end = range->segmax;
 892     segment_t*last = 0;
 893
 894 #ifdef DEBUG
 895     s = actlist_leftmost(status->actlist);
 896     while(s) {
 897         fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
 898             s == range->segmin?"S":(
 899             s == range->segmax?"E":""));
 900         s = s->right;
 901     }
 902     fprintf(stderr, "\n");
 903     s = range->segmin;
 904 #endif
 905 #ifdef CHECKS
 906     /* test sanity: check that we don't have changed segments
 907        outside of the given range */
 908     s = actlist_leftmost(status->actlist);
 909     while(s && s!=range->segmin) {
 910         assert(!s->changed);
 911         s = s->right;
 912     }
 913     s = actlist_rightmost(status->actlist);
 914     while(s && s!=range->segmax) {
 915         assert(!s->changed);
 916         s = s->left;
 917     }
 918     /* in check mode, go through the whole interval so we can test
 919        that all polygons where the fillstyle changed also have seg->changed=1 */
 920     s = actlist_leftmost(status->actlist);
 921     end = 0;
 922 #endif
 923
 924     if(end)
 925         end = end->right;
 926     while(s!=end) {
 927 #ifndef CHECKS
 928         if(s->changed)
 929 #endif
 930         {
 931             segment_t* left = actlist_left(status->actlist, s);
 932             windstate_t wind = left?left->wind:status->windrule->start(status->context);
 933             s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
 934             fillstyle_t*fs_old = s->fs_out;
 935             s->fs_out = status->windrule->diff(&wind, &s->wind);
 936
 937 #ifdef DEBUG
 938             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",
 939                     fs_old!=s->fs_out?"CHANGED":"");
 940 #endif
 941             assert(!(!s->changed && fs_old!=s->fs_out));
 942             s->changed = 0;
 943
 944 #ifdef CHECKS
 945             s->fs_out_ok = 1;
 946 #endif
 947         }
 948         s = s->right;
 949     }
 950 }
 951
 952 /* we need to handle horizontal lines in order to add points to segments
 953    we otherwise would miss during the windrule re-evaluation */
 954 static void intersect_with_horizontal(status_t*status, segment_t*h)
 955 {
 956     segment_t* left = actlist_find(status->actlist, h->a, h->a);
 957     segment_t* right = actlist_find(status->actlist, h->b, h->b);
 958
 959     /* not strictly necessary, also done by the event */
 960     xrow_add(status->xrow, h->a.x);
 961     point_t o = h->a;
 962
 963     if(!right) {
 964         assert(!left);
 965         return;
 966     }
 967
 968     left = actlist_right(status->actlist, left); //first seg to the right of h->a
 969     right = right->right; //first seg to the right of h->b
 970     segment_t* s = left;
 971
 972     while(s!=right) {
 973         assert(s);
 974         int32_t x = XPOS_INT(s, status->y);
 975 #ifdef DEBUG
 976         fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
 977                 s->a.x, s->a.y,
 978                 s->b.x, s->b.y,
 979                 x, status->y
 980                 );
 981 #endif
 982         assert(x >= h->a.x);
 983         assert(x <= h->b.x);
 984         assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
 985         assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
 986         xrow_add(status->xrow, x);
 987
 988         s = s->right;
 989     }
 990 }
 991
 992 static void event_apply(status_t*status, event_t*e)
 993 {
 994     switch(e->type) {
 995         case EVENT_HORIZONTAL: {
 996             segment_t*s = e->s1;
 997 #ifdef DEBUG
 998             event_dump(e);
 999 #endif
1000             intersect_with_horizontal(status, s);
1001             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1002             segment_destroy(s);e->s1=0;
1003             break;
1004         }
1005         case EVENT_END: {
1006             //delete segment from list
1007             segment_t*s = e->s1;
1008 #ifdef DEBUG
1009             event_dump(e);
1010 #endif
1011 #ifdef CHECKS
1012             dict_del(status->intersecting_segs, s);
1013             dict_del(status->segs_with_point, s);
1014             assert(!dict_contains(status->intersecting_segs, s));
1015             assert(!dict_contains(status->segs_with_point, s));
1016 #endif
1017             segment_t*left = s->left;
1018             segment_t*right = s->right;
1019             actlist_delete(status->actlist, s);
1020             if(left && right)
1021                 schedule_crossing(status, left, right);
1022
1023             /* schedule segment for xrow handling */
1024             s->left = 0; s->right = status->ending_segments;
1025             status->ending_segments = s;
1026             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1027             break;
1028         }
1029         case EVENT_START: {
1030             //insert segment into list
1031 #ifdef DEBUG
1032             event_dump(e);
1033 #endif
1034             segment_t*s = e->s1;
1035             assert(e->p.x == s->a.x && e->p.y == s->a.y);
1036             actlist_insert(status->actlist, s->a, s->b, s);
1037             segment_t*left = s->left;
1038             segment_t*right = s->right;
1039             if(left)
1040                 schedule_crossing(status, left, s);
1041             if(right)
1042                 schedule_crossing(status, s, right);
1043             schedule_endpoint(status, s);
1044             break;
1045         }
1046         case EVENT_CROSS: {
1047             // exchange two segments
1048 #ifdef DEBUG
1049             event_dump(e);
1050 #endif
1051             if(e->s1->right == e->s2) {
1052                 assert(e->s2->left == e->s1);
1053                 exchange_two(status, e);
1054             } else {
1055                 assert(e->s2->left != e->s1);
1056 #ifdef DEBUG
1057                 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1058 #endif
1059 #ifndef DONT_REMEMBER_CROSSINGS
1060                 /* ignore this crossing for now (there are some line segments in between).
1061                    it'll get rescheduled as soon as the "obstacles" are gone */
1062                 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1063                 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1064                 assert(del1 && del2);
1065 #endif
1066 #ifdef CHECKS
1067                 point_t pair;
1068                 pair.x = e->s1->nr;
1069                 pair.y = e->s2->nr;
1070 #ifndef DONT_REMEMBER_CROSSINGS
1071                 assert(dict_contains(status->seen_crossings, &pair));
1072                 dict_del(status->seen_crossings, &pair);
1073 #endif
1074 #endif
1075             }
1076         }
1077     }
1078 }
1079
1080 #ifdef CHECKS
1081 static void check_status(status_t*status)
1082 {
1083     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1084         if((s->pos.x != s->b.x ||
1085             s->pos.y != s->b.y) &&
1086            !dict_contains(status->segs_with_point, s)) {
1087             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1088                     s->nr,
1089                     s->delta.x<0?"-":"+",
1090                     status->y);
1091             assert(0);
1092         }
1093     }
1094 }
1095 #endif
1096
1097 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1098 {
1099     /*
1100           |..|        |...........|                 |           |
1101           |..|        |...........|                 |           |
1102           |..+        +        +..|                 +--+     +--+
1103           |...........|        |..|                    |     |
1104           |...........|        |..|                    |     |
1105      */
1106
1107 #ifdef DEBUG
1108     fprintf(stderr, "========================================================================\n");
1109 #endif
1110     hqueue_t hqueue;
1111     hqueue_init(&hqueue);
1112     gfxpoly_enqueue(poly, 0, &hqueue, 0);
1113
1114     actlist_t* actlist = actlist_new();
1115
1116     event_t*e = hqueue_get(&hqueue);
1117     while(e) {
1118         int32_t y = e->p.y;
1119         int32_t x = 0;
1120         char fill = 0;
1121 #ifdef DEBUG
1122         fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1123         actlist_dump(actlist, y-1);
1124 #endif
1125 #ifdef CHECKS
1126         actlist_verify(actlist, y-1);
1127 #endif
1128         do {
1129             if(fill && x != e->p.x) {
1130 #ifdef DEBUG
1131                 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1132 #endif
1133                 assert(x<e->p.x);
1134
1135                 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1136                 stroke->next = poly->strokes;
1137                 poly->strokes = stroke;
1138
1139                 stroke->num_points = 2;
1140                 stroke->points = malloc(sizeof(point_t)*2);
1141                 stroke->dir = DIR_UP; // FIXME
1142                 stroke->fs = 0;
1143                 point_t a,b;
1144                 a.y = b.y = y;
1145                 /* we draw from low x to high x so that left/right fillstyles add up
1146                    (because the horizontal line's fill style controls the area *below* the line)
1147                  */
1148                 a.x = e->p.x;
1149                 b.x = x;
1150                 stroke->points[0] = a;
1151                 stroke->points[1] = b;
1152 #ifdef CHECKS
1153                 /* the output should always be intersection free polygons, so check this horizontal
1154                    line isn't hacking through any segments in the active list */
1155                 segment_t* start = actlist_find(actlist, b, b);
1156                 segment_t* s = actlist_find(actlist, a, a);
1157                 while(s!=start) {
1158                     assert(s->a.y == y || s->b.y == y);
1159                     s = s->left;
1160                 }
1161 #endif
1162             }
1163             segment_t*left = 0;
1164             segment_t*s = e->s1;
1165
1166             switch(e->type) {
1167                 case EVENT_START: {
1168                     assert(e->p.x == s->a.x && e->p.y == s->a.y);
1169                     actlist_insert(actlist, s->a, s->b, s);
1170                     event_t* e = event_new();
1171                     e->type = EVENT_END;
1172                     e->p = s->b;
1173                     e->s1 = s;
1174                     e->s2 = 0;
1175                     hqueue_put(&hqueue, e);
1176                     left = actlist_left(actlist, s);
1177                     break;
1178                 }
1179                 case EVENT_END: {
1180                     left = actlist_left(actlist, s);
1181                     actlist_delete(actlist, s);
1182                     advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1183                     break;
1184                 }
1185                 default: assert(0);
1186             }
1187
1188             x = e->p.x;
1189             fill ^= 1;//(before.is_filled != after.is_filled);
1190 #ifdef DEBUG
1191             fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1192                     y, e->type==EVENT_START?"start":"end",
1193                     s->nr,
1194                     left?left->nr:-1,
1195                     x);
1196 #endif
1197
1198             if(e->type == EVENT_END)
1199                 segment_destroy(s);
1200
1201             event_free(e);
1202             e = hqueue_get(&hqueue);
1203         } while(e && y == e->p.y);
1204
1205         assert(!fill); // check that polygon is not bleeding
1206     }
1207
1208     actlist_destroy(actlist);
1209     hqueue_destroy(&hqueue);
1210 }
1211
1212 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1213 {
1214     current_polygon = poly;
1215
1216     status_t status;
1217     memset(&status, 0, sizeof(status_t));
1218     queue_init(&status.queue);
1219     gfxpoly_enqueue(poly, &status.queue, 0, /*polygon nr*/0);
1220
1221     status.windrule = windrule;
1222     status.context = context;
1223     status.actlist = actlist_new();
1224
1225 #ifdef CHECKS
1226     status.seen_crossings = dict_new2(&point_type);
1227     int32_t lasty=-0x80000000;
1228 #endif
1229
1230     status.xrow = xrow_new();
1231
1232     event_t*e = queue_get(&status.queue);
1233     while(e) {
1234         status.y = e->p.y;
1235 #ifdef CHECKS
1236         assert(status.y>=lasty);
1237         lasty = status.y;
1238         status.intersecting_segs = dict_new2(&ptr_type);
1239         status.segs_with_point = dict_new2(&ptr_type);
1240 #endif
1241
1242 #ifdef DEBUG
1243         fprintf(stderr, "----------------------------------- %d\n", status.y);
1244         actlist_dump(status.actlist, status.y-1);
1245 #endif
1246 #ifdef CHECKS
1247         actlist_verify(status.actlist, status.y-1);
1248 #endif
1249         xrow_reset(status.xrow);
1250         do {
1251             xrow_add(status.xrow, e->p.x);
1252             event_apply(&status, e);
1253             event_free(e);
1254             e = queue_get(&status.queue);
1255         } while(e && status.y == e->p.y);
1256
1257         xrow_sort(status.xrow);
1258         segrange_t range;
1259         memset(&range, 0, sizeof(range));
1260 #ifdef DEBUG
1261         actlist_dump(status.actlist, status.y);
1262 #endif
1263         add_points_to_positively_sloped_segments(&status, status.y, &range);
1264         add_points_to_negatively_sloped_segments(&status, status.y, &range);
1265         add_points_to_ending_segments(&status, status.y);
1266
1267         recalculate_windings(&status, &range);
1268 #ifdef CHECKS
1269         check_status(&status);
1270         dict_destroy(status.intersecting_segs);
1271         dict_destroy(status.segs_with_point);
1272 #endif
1273     }
1274 #ifdef CHECKS
1275     dict_destroy(status.seen_crossings);
1276 #endif
1277     actlist_destroy(status.actlist);
1278     queue_destroy(&status.queue);
1279     xrow_destroy(status.xrow);
1280
1281     gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1282     p->gridsize = poly->gridsize;
1283     p->strokes = status.strokes;
1284
1285     gfxpoly_dump(p);
1286     add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1287     return p;
1288 }