lib/gfxpoly/poly.c

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