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