lib/gfxpoly/poly.c

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