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