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