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