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     if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
 489         /* FIXME: this whole segment hashing thing is really slow */
 490 #ifdef DEBUG
 491         fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
 492 //      DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
 493 //          fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
 494 //      }
 495 #endif
 496         return; // we already know about this one
 497     }
 498
 499     double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
 500     if(!det) {
 501         if(s1->k == s2->k) {
 502             // lines are exactly on top of each other (ignored)
 503 #ifdef DEBUG
 504             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
 505 #endif
 506             return;
 507         } else {
 508 #ifdef DEBUG
 509             fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
 510 #endif
 511             /* lines are parallel */
 512             return;
 513         }
 514     }
 515     double asign2 = LINE_EQ(s1->a, s2);
 516     double bsign2 = LINE_EQ(s1->b, s2);
 517     if(asign2<0 && bsign2<0) {
 518         // segment1 is completely to the left of segment2
 519 #ifdef DEBUG
 520             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);
 521 #endif
 522         return;
 523     }
 524     if(asign2>0 && bsign2>0)  {
 525         // TODO: can this ever happen?
 526 #ifdef DEBUG
 527             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);
 528 #endif
 529         // segment2 is completely to the left of segment1
 530         return;
 531     }
 532     if(asign2==0) {
 533         // segment1 touches segment2 in a single point (ignored)
 534 #ifdef DEBUG
 535         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
 536 #endif
 537         return;
 538     }
 539     if(bsign2==0) {
 540         // segment1 touches segment2 in a single point (ignored)
 541 #ifdef DEBUG
 542         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
 543 #endif
 544         return;
 545     }
 546     double asign1 = LINE_EQ(s2->a, s1);
 547     double bsign1 = LINE_EQ(s2->b, s1);
 548     if(asign1<0 && bsign1<0) {
 549         // segment1 is completely to the left of segment2
 550 #ifdef DEBUG
 551             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);
 552 #endif
 553         return;
 554     }
 555     if(asign1>0 && bsign1>0)  {
 556         // segment2 is completely to the left of segment1
 557 #ifdef DEBUG
 558             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);
 559 #endif
 560         return;
 561     }
 562     if(asign1==0) {
 563         // segment2 touches segment1 in a single point (ignored)
 564 #ifdef DEBUG
 565         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
 566 #endif
 567         return;
 568     }
 569     if(asign2==0) {
 570         // segment2 touches segment1 in a single point (ignored)
 571 #ifdef DEBUG
 572         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
 573 #endif
 574         return;
 575     }
 576
 577     /* TODO: should we precompute these? */
 578     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
 579     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 580
 581     point_t p;
 582     p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
 583     p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
 584
 585     assert(p.y >= status->y);
 586 #ifdef CHECKS
 587     assert(p.x >= s1->minx && p.x <= s1->maxx);
 588     assert(p.x >= s2->minx && p.x <= s2->maxx);
 589
 590     point_t pair;
 591     pair.x = s1->nr;
 592     pair.y = s2->nr;
 593     assert(!dict_contains(status->seen_crossings, &pair));
 594     dict_put(status->seen_crossings, &pair, 0);
 595 #endif
 596 #ifdef DEBUG
 597     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 598 #endif
 599
 600     /* we insert into each other's intersection history because these segments might switch
 601        places and we still want to look them up quickly after they did */
 602     dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
 603     dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
 604
 605     event_t e = event_new();
 606     e.type = EVENT_CROSS;
 607     e.p = p;
 608     e.s1 = s1;
 609     e.s2 = s2;
 610     heap_put(status->queue, &e);
 611     return;
 612 }
 613
 614 static void exchange_two(status_t*status, event_t*e)
 615 {
 616     //exchange two segments in list
 617     segment_t*s1 = e->s1;
 618     segment_t*s2 = e->s2;
 619 #ifdef CHECKS
 620     if(!dict_contains(status->intersecting_segs, s1))
 621         dict_put(status->intersecting_segs, s1, 0);
 622     if(!dict_contains(status->intersecting_segs, s2))
 623         dict_put(status->intersecting_segs, s2, 0);
 624 #endif
 625     assert(s2->left == s1);
 626     assert(s1->right == s2);
 627     actlist_swap(status->actlist, s1, s2);
 628     assert(s2->right  == s1);
 629     assert(s1->left == s2);
 630     segment_t*left = s2->left;
 631     segment_t*right = s1->right;
 632     if(left)
 633         schedule_crossing(status, left, s2);
 634     if(right)
 635         schedule_crossing(status, s1, right);
 636 }
 637
 638 typedef struct _box {
 639     point_t left1, left2, right1, right2;
 640 } box_t;
 641 static inline box_t box_new(int32_t x, int32_t y)
 642 {
 643     box_t box;
 644     box.right1.x = box.right2.x = x;
 645     box.left1.x = box.left2.x = x-1;
 646     box.left1.y = box.right1.y = y-1;
 647     box.left2.y = box.right2.y = y;
 648     return box;
 649 }
 650
 651
 652 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 653 {
 654     assert(s->pos.x != p.x || s->pos.y != p.y);
 655
 656 #ifdef CHECKS
 657     if(!dict_contains(status->segs_with_point, s))
 658         dict_put(status->segs_with_point, s, 0);
 659     assert(s->fs_out_ok);
 660 #endif
 661
 662     if(s->fs_out) {
 663 #ifdef DEBUG
 664         fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
 665                 s->pos.x, s->pos.y, p.x, p.y);
 666 #endif
 667         // omit horizontal lines
 668         if(s->pos.y != p.y) {
 669             point_t a = s->pos;
 670             point_t b = p;
 671             assert(a.y != b.y);
 672             status->writer.moveto(&status->writer, a.x, a.y);
 673             status->writer.lineto(&status->writer, b.x, b.y);
 674         }
 675     } else {
 676 #ifdef DEBUG
 677         fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
 678 #endif
 679     }
 680     s->pos = p;
 681 }
 682
 683 typedef struct _segrange {
 684     double xmin;
 685     segment_t*segmin;
 686     double xmax;
 687     segment_t*segmax;
 688 } segrange_t;
 689
 690 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
 691 {
 692 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
 693     segment_t*min = range->segmin;
 694     segment_t*max = range->segmax;
 695
 696     /* we need this because if two segments intersect exactly on
 697        the scanline, segrange_test_segment_{min,max} can't tell which
 698        one is smaller/larger */
 699     if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
 700         min = min->left;
 701     }
 702     if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
 703         max = max->right;
 704     }
 705     range->segmin = min;
 706     range->segmax = max;
 707 }
 708 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
 709 {
 710     if(!seg) return;
 711     /* we need to calculate the xpos anew (and can't use start coordinate or
 712        intersection coordinate), because we need the xpos exactly at the end of
 713        this scanline.
 714      */
 715     double x = XPOS(seg, y);
 716     if(!range->segmin || x<range->xmin) {
 717         range->segmin = seg;
 718         range->xmin = x;
 719     }
 720 }
 721 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
 722 {
 723     if(!seg) return;
 724     double x = XPOS(seg, y);
 725     if(!range->segmax || x>range->xmax) {
 726         range->segmax = seg;
 727         range->xmax = x;
 728     }
 729 }
 730
 731 /*
 732    SLOPE_POSITIVE:
 733       \+     \ +
 734 ------ I      \I
 735       -I\----  I
 736        I \   --I\---
 737        I  \    I \  -------
 738        +   \   +  \
 739 */
 740 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 741 {
 742     segment_t*first=0, *last = 0;
 743     int t;
 744     for(t=0;t<status->xrow->num;t++) {
 745         box_t box = box_new(status->xrow->x[t], y);
 746         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 747
 748         seg = actlist_right(status->actlist, seg);
 749         while(seg) {
 750             if(seg->a.y == y) {
 751                 // this segment started in this scanline, ignore it
 752                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 753             } else if(seg->delta.x <= 0) {
 754                 // ignore segment w/ negative slope
 755             } else {
 756                 last = seg;if(!first) {first=seg;}
 757                 double d1 = LINE_EQ(box.right1, seg);
 758                 double d2 = LINE_EQ(box.right2, seg);
 759                 if(d1>0 || d2>=0) {
 760                     seg->changed = 1;
 761                     insert_point_into_segment(status, seg, box.right2);
 762                 } else {
 763                     /* we unfortunately can't break here- the active list is sorted according
 764                        to the *bottom* of the scanline. hence pretty much everything that's still
 765                        coming might reach into our box */
 766                     //break;
 767                 }
 768             }
 769             seg = seg->right;
 770         }
 771     }
 772     segrange_test_segment_min(range, first, y);
 773     segrange_test_segment_max(range, last, y);
 774 }
 775 /* SLOPE_NEGATIVE:
 776    |   +   /|  +  /    /
 777    |   I  / |  I /    /
 778    |   I /  |  I/    /
 779    |   I/   |  I    /
 780    |   I    | /I   /
 781    |  /+    |/ +  /
 782 */
 783 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 784 {
 785     segment_t*first=0, *last = 0;
 786     int t;
 787     for(t=status->xrow->num-1;t>=0;t--) {
 788         box_t box = box_new(status->xrow->x[t], y);
 789         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 790
 791         while(seg) {
 792             if(seg->a.y == y) {
 793                 // this segment started in this scanline, ignore it
 794                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 795             } else if(seg->delta.x > 0) {
 796                 // ignore segment w/ positive slope
 797             } else {
 798                 last = seg;if(!first) {first=seg;}
 799                 double d1 = LINE_EQ(box.left1, seg);
 800                 double d2 = LINE_EQ(box.left2, seg);
 801                 if(d1<0 || d2<0) {
 802                     seg->changed = 1;
 803                     insert_point_into_segment(status, seg, box.right2);
 804                 } else {
 805                     //break;
 806                 }
 807             }
 808             seg = seg->left;
 809         }
 810     }
 811     segrange_test_segment_min(range, last, y);
 812     segrange_test_segment_max(range, first, y);
 813 }
 814
 815 /* segments ending in the current scanline need xrow treatment like everything else.
 816    (consider an intersection taking place just above a nearly horizontal segment
 817    ending on the current scanline- the intersection would snap down *below* the
 818    ending segment if we don't add the intersection point to the latter right away)
 819    we need to treat ending segments seperately, however. we have to delete them from
 820    the active list right away to make room for intersect operations (which might
 821    still be in the current scanline- consider two 45° polygons and a vertical polygon
 822    intersecting on an integer coordinate). but once they're no longer in the active list,
 823    we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
 824    them to the active list just for point snapping would be overkill.
 825    (One other option to consider, however, would be to create a new active list only
 826     for ending segments)
 827 */
 828 static void add_points_to_ending_segments(status_t*status, int32_t y)
 829 {
 830     segment_t*seg = status->ending_segments;
 831     while(seg) {
 832         segment_t*next = seg->right;seg->right=0;
 833
 834         assert(seg->b.y == status->y);
 835
 836         if(status->xrow->num == 1) {
 837             // shortcut
 838             assert(seg->b.x == status->xrow->x[0]);
 839             point_t p = {status->xrow->x[0], y};
 840             insert_point_into_segment(status, seg, p);
 841         } else {
 842             int t;
 843             int start=0,end=status->xrow->num,dir=1;
 844             if(seg->delta.x < 0) {
 845                 start = status->xrow->num-1;
 846                 end = dir = -1;
 847             }
 848             for(t=start;t!=end;t+=dir) {
 849                 box_t box = box_new(status->xrow->x[t], y);
 850                 double d0 = LINE_EQ(box.left1, seg);
 851                 double d1 = LINE_EQ(box.left2, seg);
 852                 double d2 = LINE_EQ(box.right1, seg);
 853                 double d3 = LINE_EQ(box.right2, seg);
 854                 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
 855                      d0<=0 && d1<=0 && d2<=0 && d3<0)) {
 856                     insert_point_into_segment(status, seg, box.right2);
 857                     break;
 858                 }
 859             }
 860
 861 #ifdef CHECKS
 862             /* we *need* to find a point to insert. the segment's own end point
 863                is in that list, for Pete's sake. */
 864             assert(t!=end);
 865 #endif
 866         }
 867         // now that this is done, too, we can also finally free this segment
 868         segment_destroy(seg);
 869         seg = next;
 870     }
 871     status->ending_segments = 0;
 872 }
 873
 874 static void recalculate_windings(status_t*status, segrange_t*range)
 875 {
 876 #ifdef DEBUG
 877     fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
 878 #endif
 879     segrange_adjust_endpoints(range, status->y);
 880
 881     segment_t*s = range->segmin;
 882     segment_t*end = range->segmax;
 883     segment_t*last = 0;
 884
 885 #ifdef DEBUG
 886     s = actlist_leftmost(status->actlist);
 887     while(s) {
 888         fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
 889             s == range->segmin?"S":(
 890             s == range->segmax?"E":""));
 891         s = s->right;
 892     }
 893     fprintf(stderr, "\n");
 894     s = range->segmin;
 895 #endif
 896 #ifdef CHECKS
 897     /* test sanity: check that we don't have changed segments
 898        outside of the given range */
 899     s = actlist_leftmost(status->actlist);
 900     while(s && s!=range->segmin) {
 901         assert(!s->changed);
 902         s = s->right;
 903     }
 904     s = actlist_rightmost(status->actlist);
 905     while(s && s!=range->segmax) {
 906         assert(!s->changed);
 907         s = s->left;
 908     }
 909     /* in check mode, go through the whole interval so we can test
 910        that all polygons where the fillstyle changed also have seg->changed=1 */
 911     s = actlist_leftmost(status->actlist);
 912     end = 0;
 913 #endif
 914
 915     if(end)
 916         end = end->right;
 917     while(s!=end) {
 918 #ifndef CHECKS
 919         if(s->changed)
 920 #endif
 921         {
 922             segment_t* left = actlist_left(status->actlist, s);
 923             windstate_t wind = left?left->wind:status->windrule->start(status->context);
 924             s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
 925             fillstyle_t*fs_old = s->fs_out;
 926             s->fs_out = status->windrule->diff(&wind, &s->wind);
 927
 928 #ifdef DEBUG
 929             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",
 930                     fs_old!=s->fs_out?"CHANGED":"");
 931 #endif
 932             assert(!(!s->changed && fs_old!=s->fs_out));
 933             s->changed = 0;
 934
 935 #ifdef CHECKS
 936             s->fs_out_ok = 1;
 937 #endif
 938         }
 939         s = s->right;
 940     }
 941 }
 942
 943 /* we need to handle horizontal lines in order to add points to segments
 944    we otherwise would miss during the windrule re-evaluation */
 945 static void intersect_with_horizontal(status_t*status, segment_t*h)
 946 {
 947     segment_t* left = actlist_find(status->actlist, h->a, h->a);
 948     segment_t* right = actlist_find(status->actlist, h->b, h->b);
 949
 950     /* not strictly necessary, also done by the event */
 951     xrow_add(status->xrow, h->a.x);
 952     point_t o = h->a;
 953
 954     if(!right) {
 955         assert(!left);
 956         return;
 957     }
 958
 959     left = actlist_right(status->actlist, left); //first seg to the right of h->a
 960     right = right->right; //first seg to the right of h->b
 961     segment_t* s = left;
 962
 963     while(s!=right) {
 964         assert(s);
 965         int32_t x = XPOS_INT(s, status->y);
 966 #ifdef DEBUG
 967         fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
 968                 s->a.x, s->a.y,
 969                 s->b.x, s->b.y,
 970                 x, status->y
 971                 );
 972 #endif
 973         assert(x >= h->a.x);
 974         assert(x <= h->b.x);
 975         assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
 976         assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
 977         xrow_add(status->xrow, x);
 978
 979         s = s->right;
 980     }
 981 }
 982
 983 static void event_apply(status_t*status, event_t*e)
 984 {
 985     switch(e->type) {
 986         case EVENT_HORIZONTAL: {
 987             segment_t*s = e->s1;
 988 #ifdef DEBUG
 989             event_dump(e);
 990 #endif
 991             intersect_with_horizontal(status, s);
 992             advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
 993             segment_destroy(s);e->s1=0;
 994             break;
 995         }
 996         case EVENT_END: {
 997             //delete segment from list
 998             segment_t*s = e->s1;
 999 #ifdef DEBUG
1000             event_dump(e);
1001 #endif
1002 #ifdef CHECKS
1003             dict_del(status->intersecting_segs, s);
1004             dict_del(status->segs_with_point, s);
1005             assert(!dict_contains(status->intersecting_segs, s));
1006             assert(!dict_contains(status->segs_with_point, s));
1007 #endif
1008             segment_t*left = s->left;
1009             segment_t*right = s->right;
1010             actlist_delete(status->actlist, s);
1011             if(left && right)
1012                 schedule_crossing(status, left, right);
1013
1014             /* schedule segment for xrow handling */
1015             s->left = 0; s->right = status->ending_segments;
1016             status->ending_segments = s;
1017             advance_stroke(status->queue, s->stroke, s->polygon_nr, s->stroke_pos);
1018             break;
1019         }
1020         case EVENT_START: {
1021             //insert segment into list
1022 #ifdef DEBUG
1023             event_dump(e);
1024 #endif
1025             segment_t*s = e->s1;
1026             assert(e->p.x == s->a.x && e->p.y == s->a.y);
1027             actlist_insert(status->actlist, s->a, s->b, s);
1028             segment_t*left = s->left;
1029             segment_t*right = s->right;
1030             if(left)
1031                 schedule_crossing(status, left, s);
1032             if(right)
1033                 schedule_crossing(status, s, right);
1034             schedule_endpoint(status, s);
1035             break;
1036         }
1037         case EVENT_CROSS: {
1038             // exchange two segments
1039 #ifdef DEBUG
1040             event_dump(e);
1041 #endif
1042             if(e->s1->right == e->s2) {
1043                 assert(e->s2->left == e->s1);
1044                 exchange_two(status, e);
1045             } else {
1046                 assert(e->s2->left != e->s1);
1047 #ifdef DEBUG
1048                 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1049 #endif
1050                 /* ignore this crossing for now (there are some line segments in between).
1051                    it'll get rescheduled as soon as the "obstacles" are gone */
1052                 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1053                 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1054                 assert(del1 && del2);
1055 #ifdef CHECKS
1056                 point_t pair;
1057                 pair.x = e->s1->nr;
1058                 pair.y = e->s2->nr;
1059                 assert(dict_contains(status->seen_crossings, &pair));
1060                 dict_del(status->seen_crossings, &pair);
1061 #endif
1062             }
1063         }
1064     }
1065 }
1066
1067 #ifdef CHECKS
1068 static void check_status(status_t*status)
1069 {
1070     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1071         if((s->pos.x != s->b.x ||
1072             s->pos.y != s->b.y) &&
1073            !dict_contains(status->segs_with_point, s)) {
1074             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1075                     s->nr,
1076                     s->delta.x<0?"-":"+",
1077                     status->y);
1078             assert(0);
1079         }
1080     }
1081 }
1082 #endif
1083
1084 static void add_horizontals(gfxcompactpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1085 {
1086     /*
1087           |..|        |...........|                 |           |
1088           |..|        |...........|                 |           |
1089           |..+        +        +..|                 +--+     +--+
1090           |...........|        |..|                    |     |
1091           |...........|        |..|                    |     |
1092      */
1093
1094 #ifdef DEBUG
1095     fprintf(stderr, "========================================================================\n");
1096 #endif
1097     heap_t* queue = heap_new(sizeof(event_t), compare_events_simple);
1098     gfxpoly_enqueue(poly, queue, 0);
1099
1100     actlist_t* actlist = actlist_new();
1101
1102     event_t*e = heap_chopmax(queue);
1103     int newstrokes_size = 4;
1104     int num_newstrokes = 0;
1105     gfxpolystroke_t*newstrokes = malloc(sizeof(gfxpolystroke_t)*newstrokes_size);
1106     while(e) {
1107         int32_t y = e->p.y;
1108         int32_t x = 0;
1109         char fill = 0;
1110 #ifdef DEBUG
1111         fprintf(stderr, "----------------------------------- %d\n", y);
1112         actlist_dump(actlist, y-1);
1113 #endif
1114 #ifdef CHECKS
1115         actlist_verify(actlist, y-1);
1116 #endif
1117         do {
1118             if(fill && x != e->p.x) {
1119 #ifdef DEBUG
1120                 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1121 #endif
1122                 assert(x<e->p.x);
1123
1124                 if(num_newstrokes == newstrokes_size) {
1125                     newstrokes_size = (newstrokes_size)<<1;
1126                     newstrokes = rfx_realloc(newstrokes, sizeof(gfxpolystroke_t)*newstrokes_size);
1127                 }
1128                 gfxpolystroke_t*stroke = &newstrokes[num_newstrokes++];
1129                 stroke->num_points = 2;
1130                 stroke->points = malloc(sizeof(point_t)*2);
1131                 stroke->dir = DIR_UP; // FIXME
1132                 stroke->fs = 0;
1133                 point_t a,b;
1134                 a.y = b.y = y;
1135                 /* we draw from low x to high x so that left/right fillstyles add up
1136                    (because the horizontal line's fill style controls the area *below* the line)
1137                  */
1138                 a.x = e->p.x;
1139                 b.x = x;
1140                 stroke->points[0] = a;
1141                 stroke->points[1] = b;
1142 #ifdef CHECKS
1143                 /* the output should always be intersection free polygons, so check this horizontal
1144                    line isn't hacking through any segments in the active list */
1145                 segment_t* start = actlist_find(actlist, b, b);
1146                 segment_t* s = actlist_find(actlist, a, a);
1147                 while(s!=start) {
1148                     assert(s->a.y == y || s->b.y == y);
1149                     s = s->left;
1150                 }
1151 #endif
1152             }
1153             segment_t*left = 0;
1154             segment_t*s = e->s1;
1155
1156             switch(e->type) {
1157                 case EVENT_START: {
1158                     assert(e->p.x == s->a.x && e->p.y == s->a.y);
1159                     actlist_insert(actlist, s->a, s->b, s);
1160                     event_t e;
1161                     e.type = EVENT_END;
1162                     e.p = s->b;
1163                     e.s1 = s;
1164                     e.s2 = 0;
1165                     heap_put(queue, &e);
1166                     left = actlist_left(actlist, s);
1167                     break;
1168                 }
1169                 case EVENT_END: {
1170                     left = actlist_left(actlist, s);
1171                     actlist_delete(actlist, s);
1172                     advance_stroke(queue, s->stroke, s->polygon_nr, s->stroke_pos);
1173                     break;
1174                 }
1175                 default: assert(0);
1176             }
1177
1178             x = e->p.x;
1179             fill ^= 1;//(before.is_filled != after.is_filled);
1180 #ifdef DEBUG
1181             fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1182                     y, e->type==EVENT_START?"start":"end",
1183                     s->nr,
1184                     left?left->nr:-1,
1185                     x);
1186 #endif
1187
1188             if(e->type == EVENT_END)
1189                 segment_destroy(s);
1190
1191             free(e);
1192             e = heap_chopmax(queue);
1193         } while(e && y == e->p.y);
1194
1195         assert(!fill); // check that polygon is not bleeding
1196     }
1197
1198     poly->strokes = rfx_realloc(poly->strokes, sizeof(gfxpolystroke_t)*(num_newstrokes+poly->num_strokes));
1199     memcpy(&poly->strokes[poly->num_strokes], newstrokes, sizeof(gfxpolystroke_t)*num_newstrokes);
1200     poly->num_strokes += num_newstrokes;
1201     free(newstrokes);
1202
1203     actlist_destroy(actlist);
1204     heap_destroy(queue);
1205 }
1206
1207 gfxpoly_t* gfxpoly_process(gfxcompactpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1208 {
1209     current_polygon = poly;
1210     heap_t* queue = heap_new(sizeof(event_t), compare_events);
1211
1212     gfxpoly_enqueue(poly, queue, /*polygon nr*/0);
1213
1214     status_t status;
1215     memset(&status, 0, sizeof(status_t));
1216     status.queue = queue;
1217     status.windrule = windrule;
1218     status.context = context;
1219     status.actlist = actlist_new();
1220     gfxcompactpolywriter_init(&status.writer);
1221     status.writer.setgridsize(&status.writer, poly->gridsize);
1222
1223 #ifdef CHECKS
1224     status.seen_crossings = dict_new2(&point_type);
1225     int lasty=heap_peek(queue)?((event_t*)heap_peek(queue))->p.y-1:0;
1226 #endif
1227
1228     status.xrow = xrow_new();
1229
1230     event_t*e = heap_chopmax(queue);
1231     while(e) {
1232         status.y = e->p.y;
1233         assert(status.y>=lasty);
1234 #ifdef CHECKS
1235         status.intersecting_segs = dict_new2(&ptr_type);
1236         status.segs_with_point = dict_new2(&ptr_type);
1237 #endif
1238
1239 #ifdef DEBUG
1240         fprintf(stderr, "----------------------------------- %d\n", status.y);
1241         actlist_dump(status.actlist, status.y-1);
1242 #endif
1243 #ifdef CHECKS
1244         actlist_verify(status.actlist, status.y-1);
1245 #endif
1246         xrow_reset(status.xrow);
1247         do {
1248             xrow_add(status.xrow, e->p.x);
1249             event_apply(&status, e);
1250             free(e);
1251             e = heap_chopmax(queue);
1252         } while(e && status.y == e->p.y);
1253
1254         xrow_sort(status.xrow);
1255         segrange_t range;
1256         memset(&range, 0, sizeof(range));
1257 #ifdef DEBUG
1258         actlist_dump(status.actlist, status.y);
1259 #endif
1260         add_points_to_positively_sloped_segments(&status, status.y, &range);
1261         add_points_to_negatively_sloped_segments(&status, status.y, &range);
1262         add_points_to_ending_segments(&status, status.y);
1263
1264         recalculate_windings(&status, &range);
1265 #ifdef CHECKS
1266         check_status(&status);
1267         dict_destroy(status.intersecting_segs);
1268         dict_destroy(status.segs_with_point);
1269 #endif
1270     }
1271 #ifdef CHECKS
1272     dict_destroy(status.seen_crossings);
1273 #endif
1274     actlist_destroy(status.actlist);
1275     heap_destroy(queue);
1276     xrow_destroy(status.xrow);
1277
1278     gfxcompactpoly_t*p = (gfxcompactpoly_t*)status.writer.finish(&status.writer);
1279     add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1280     return gfxpoly_from_gfxcompactpoly(p);
1281 }