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);
 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 = stroke->fs;
 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         segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
 670
 671         // omit horizontal lines
 672         if(s->pos.y != p.y) {
 673             point_t a = s->pos;
 674             point_t b = p;
 675             assert(a.y != b.y);
 676
 677             gfxpolystroke_t*stroke = status->strokes;
 678             /* find a stoke to attach this segment to. It has to have an endpoint
 679                matching our start point, and a matching edgestyle */
 680             while(stroke) {
 681                 point_t p = stroke->points[stroke->num_points-1];
 682                 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
 683                     break;
 684                 stroke = stroke->next;
 685             }
 686             if(!stroke) {
 687                 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
 688                 stroke->dir = dir;
 689                 stroke->fs = fs;
 690                 stroke->next = status->strokes;
 691                 status->strokes = stroke;
 692                 stroke->points_size = 2;
 693                 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
 694                 stroke->points[0] = a;
 695                 stroke->num_points = 1;
 696             } else if(stroke->num_points == stroke->points_size) {
 697                 assert(stroke->fs);
 698                 stroke->points_size *= 2;
 699                 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
 700             }
 701             stroke->points[stroke->num_points++] = b;
 702         }
 703     } else {
 704 #ifdef DEBUG
 705         fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
 706 #endif
 707     }
 708     s->pos = p;
 709 }
 710
 711 typedef struct _segrange {
 712     double xmin;
 713     segment_t*segmin;
 714     double xmax;
 715     segment_t*segmax;
 716 } segrange_t;
 717
 718 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
 719 {
 720 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
 721     segment_t*min = range->segmin;
 722     segment_t*max = range->segmax;
 723
 724     /* we need this because if two segments intersect exactly on
 725        the scanline, segrange_test_segment_{min,max} can't tell which
 726        one is smaller/larger */
 727     if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
 728         min = min->left;
 729     }
 730     if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
 731         max = max->right;
 732     }
 733     range->segmin = min;
 734     range->segmax = max;
 735 }
 736 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
 737 {
 738     if(!seg) return;
 739     /* we need to calculate the xpos anew (and can't use start coordinate or
 740        intersection coordinate), because we need the xpos exactly at the end of
 741        this scanline.
 742      */
 743     double x = XPOS(seg, y);
 744     if(!range->segmin || x<range->xmin) {
 745         range->segmin = seg;
 746         range->xmin = x;
 747     }
 748 }
 749 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
 750 {
 751     if(!seg) return;
 752     double x = XPOS(seg, y);
 753     if(!range->segmax || x>range->xmax) {
 754         range->segmax = seg;
 755         range->xmax = x;
 756     }
 757 }
 758
 759 /*
 760    SLOPE_POSITIVE:
 761       \+     \ +
 762 ------ I      \I
 763       -I\----  I
 764        I \   --I\---
 765        I  \    I \  -------
 766        +   \   +  \
 767 */
 768 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 769 {
 770     segment_t*first=0, *last = 0;
 771     int t;
 772     for(t=0;t<status->xrow->num;t++) {
 773         box_t box = box_new(status->xrow->x[t], y);
 774         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 775
 776         seg = actlist_right(status->actlist, seg);
 777         while(seg) {
 778             if(seg->a.y == y) {
 779                 // this segment started in this scanline, ignore it
 780                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 781             } else if(seg->delta.x <= 0) {
 782                 // ignore segment w/ negative slope
 783             } else {
 784                 last = seg;if(!first) {first=seg;}
 785                 double d1 = LINE_EQ(box.right1, seg);
 786                 double d2 = LINE_EQ(box.right2, seg);
 787                 if(d1>0 || d2>=0) {
 788                     seg->changed = 1;
 789                     insert_point_into_segment(status, seg, box.right2);
 790                 } else {
 791                     /* we unfortunately can't break here- the active list is sorted according
 792                        to the *bottom* of the scanline. hence pretty much everything that's still
 793                        coming might reach into our box */
 794                     //break;
 795                 }
 796             }
 797             seg = seg->right;
 798         }
 799     }
 800     segrange_test_segment_min(range, first, y);
 801     segrange_test_segment_max(range, last, y);
 802 }
 803 /* SLOPE_NEGATIVE:
 804    |   +   /|  +  /    /
 805    |   I  / |  I /    /
 806    |   I /  |  I/    /
 807    |   I/   |  I    /
 808    |   I    | /I   /
 809    |  /+    |/ +  /
 810 */
 811 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
 812 {
 813     segment_t*first=0, *last = 0;
 814     int t;
 815     for(t=status->xrow->num-1;t>=0;t--) {
 816         box_t box = box_new(status->xrow->x[t], y);
 817         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 818
 819         while(seg) {
 820             if(seg->a.y == y) {
 821                 // this segment started in this scanline, ignore it
 822                 seg->changed = 1;last = seg;if(!first) {first=seg;}
 823             } else if(seg->delta.x > 0) {
 824                 // ignore segment w/ positive slope
 825             } else {
 826                 last = seg;if(!first) {first=seg;}
 827                 double d1 = LINE_EQ(box.left1, seg);
 828                 double d2 = LINE_EQ(box.left2, seg);
 829                 if(d1<0 || d2<0) {
 830                     seg->changed = 1;
 831                     insert_point_into_segment(status, seg, box.right2);
 832                 } else {
 833                     //break;
 834                 }
 835             }
 836             seg = seg->left;
 837         }
 838     }
 839     segrange_test_segment_min(range, last, y);
 840     segrange_test_segment_max(range, first, y);
 841 }
 842
 843 /* segments ending in the current scanline need xrow treatment like everything else.
 844    (consider an intersection taking place just above a nearly horizontal segment
 845    ending on the current scanline- the intersection would snap down *below* the
 846    ending segment if we don't add the intersection point to the latter right away)
 847    we need to treat ending segments seperately, however. we have to delete them from
 848    the active list right away to make room for intersect operations (which might
 849    still be in the current scanline- consider two 45° polygons and a vertical polygon
 850    intersecting on an integer coordinate). but once they're no longer in the active list,
 851    we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
 852    them to the active list just for point snapping would be overkill.
 853    (One other option to consider, however, would be to create a new active list only
 854     for ending segments)
 855 */
 856 static void add_points_to_ending_segments(status_t*status, int32_t y)
 857 {
 858     segment_t*seg = status->ending_segments;
 859     while(seg) {
 860         segment_t*next = seg->right;seg->right=0;
 861
 862         assert(seg->b.y == status->y);
 863
 864         if(status->xrow->num == 1) {
 865             // shortcut
 866             assert(seg->b.x == status->xrow->x[0]);
 867             point_t p = {status->xrow->x[0], y};
 868             insert_point_into_segment(status, seg, p);
 869         } else {
 870             int t;
 871             int start=0,end=status->xrow->num,dir=1;
 872             if(seg->delta.x < 0) {
 873                 start = status->xrow->num-1;
 874                 end = dir = -1;
 875             }
 876             for(t=start;t!=end;t+=dir) {
 877                 box_t box = box_new(status->xrow->x[t], y);
 878                 double d0 = LINE_EQ(box.left1, seg);
 879                 double d1 = LINE_EQ(box.left2, seg);
 880                 double d2 = LINE_EQ(box.right1, seg);
 881                 double d3 = LINE_EQ(box.right2, seg);
 882                 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
 883                      d0<=0 && d1<=0 && d2<=0 && d3<0)) {
 884                     insert_point_into_segment(status, seg, box.right2);
 885                     break;
 886                 }
 887             }
 888
 889 #ifdef CHECKS
 890             /* we *need* to find a point to insert. the segment's own end point
 891                is in that list, for Pete's sake. */
 892             assert(t!=end);
 893 #endif
 894         }
 895         // now that this is done, too, we can also finally free this segment
 896         segment_destroy(seg);
 897         seg = next;
 898     }
 899     status->ending_segments = 0;
 900 }
 901
 902 static void recalculate_windings(status_t*status, segrange_t*range)
 903 {
 904 #ifdef DEBUG
 905     fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
 906 #endif
 907     segrange_adjust_endpoints(range, status->y);
 908
 909     segment_t*s = range->segmin;
 910     segment_t*end = range->segmax;
 911     segment_t*last = 0;
 912
 913 #ifdef DEBUG
 914     s = actlist_leftmost(status->actlist);
 915     while(s) {
 916         fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
 917             s == range->segmin?"S":(
 918             s == range->segmax?"E":""));
 919         s = s->right;
 920     }
 921     fprintf(stderr, "\n");
 922     s = range->segmin;
 923 #endif
 924 #ifdef CHECKS
 925     /* test sanity: verify that we don't have changed segments
 926        outside of the given range */
 927     s = actlist_leftmost(status->actlist);
 928     while(s && s!=range->segmin) {
 929         assert(!s->changed);
 930         s = s->right;
 931     }
 932     s = actlist_rightmost(status->actlist);
 933     while(s && s!=range->segmax) {
 934         assert(!s->changed);
 935         s = s->left;
 936     }
 937     /* in check mode, go through the whole interval so we can test
 938        that all polygons where the edgestyle changed also have seg->changed=1 */
 939     s = actlist_leftmost(status->actlist);
 940     end = 0;
 941 #endif
 942
 943     if(end)
 944         end = end->right;
 945     while(s!=end) {
 946 #ifndef CHECKS
 947         if(s->changed)
 948 #endif
 949         {
 950             segment_t* left = actlist_left(status->actlist, s);
 951             windstate_t wind = left?left->wind:status->windrule->start(status->context);
 952             s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
 953             edgestyle_t*fs_old = s->fs_out;
 954             s->fs_out = status->windrule->diff(&wind, &s->wind);
 955
 956 #ifdef DEBUG
 957             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",
 958                     fs_old?"draw":"omit", s->fs_out?"draw":"omit",
 959                     fs_old!=s->fs_out?"CHANGED":"");
 960 #endif
 961             assert(!(!s->changed && fs_old!=s->fs_out));
 962             s->changed = 0;
 963
 964 #ifdef CHECKS
 965             s->fs_out_ok = 1;
 966 #endif
 967         }
 968         s = s->right;
 969     }
 970 }
 971
 972 /* we need to handle horizontal lines in order to add points to segments
 973    we otherwise would miss during the windrule re-evaluation */
 974 static void intersect_with_horizontal(status_t*status, segment_t*h)
 975 {
 976     segment_t* left = actlist_find(status->actlist, h->a, h->a);
 977     segment_t* right = actlist_find(status->actlist, h->b, h->b);
 978
 979     /* not strictly necessary, also done by the event */
 980     xrow_add(status->xrow, h->a.x);
 981     point_t o = h->a;
 982
 983     if(!right) {
 984         assert(!left);
 985         return;
 986     }
 987
 988     left = actlist_right(status->actlist, left); //first seg to the right of h->a
 989     right = right->right; //first seg to the right of h->b
 990     segment_t* s = left;
 991
 992     while(s!=right) {
 993         assert(s);
 994         int32_t x = XPOS_INT(s, status->y);
 995 #ifdef DEBUG
 996         fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
 997                 s->a.x, s->a.y,
 998                 s->b.x, s->b.y,
 999                 x, status->y
1000                 );
1001 #endif
1002         assert(x >= h->a.x);
1003         assert(x <= h->b.x);
1004         assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1005         assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1006         xrow_add(status->xrow, x);
1007
1008         s = s->right;
1009     }
1010 }
1011
1012 static void event_apply(status_t*status, event_t*e)
1013 {
1014     switch(e->type) {
1015         case EVENT_HORIZONTAL: {
1016             segment_t*s = e->s1;
1017 #ifdef DEBUG
1018             event_dump(e);
1019 #endif
1020             intersect_with_horizontal(status, s);
1021             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1022             segment_destroy(s);e->s1=0;
1023             break;
1024         }
1025         case EVENT_END: {
1026             //delete segment from list
1027             segment_t*s = e->s1;
1028 #ifdef DEBUG
1029             event_dump(e);
1030 #endif
1031 #ifdef CHECKS
1032             dict_del(status->intersecting_segs, s);
1033             dict_del(status->segs_with_point, s);
1034             assert(!dict_contains(status->intersecting_segs, s));
1035             assert(!dict_contains(status->segs_with_point, s));
1036 #endif
1037             segment_t*left = s->left;
1038             segment_t*right = s->right;
1039             actlist_delete(status->actlist, s);
1040             if(left && right)
1041                 schedule_crossing(status, left, right);
1042
1043             /* schedule segment for xrow handling */
1044             s->left = 0; s->right = status->ending_segments;
1045             status->ending_segments = s;
1046             advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1047             break;
1048         }
1049         case EVENT_START: {
1050             //insert segment into list
1051 #ifdef DEBUG
1052             event_dump(e);
1053 #endif
1054             segment_t*s = e->s1;
1055             assert(e->p.x == s->a.x && e->p.y == s->a.y);
1056             actlist_insert(status->actlist, s->a, s->b, s);
1057             segment_t*left = s->left;
1058             segment_t*right = s->right;
1059             if(left)
1060                 schedule_crossing(status, left, s);
1061             if(right)
1062                 schedule_crossing(status, s, right);
1063             schedule_endpoint(status, s);
1064             break;
1065         }
1066         case EVENT_CROSS: {
1067             // exchange two segments
1068 #ifdef DEBUG
1069             event_dump(e);
1070 #endif
1071             if(e->s1->right == e->s2) {
1072                 assert(e->s2->left == e->s1);
1073                 exchange_two(status, e);
1074             } else {
1075                 assert(e->s2->left != e->s1);
1076 #ifdef DEBUG
1077                 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1078 #endif
1079 #ifndef DONT_REMEMBER_CROSSINGS
1080                 /* ignore this crossing for now (there are some line segments in between).
1081                    it'll get rescheduled as soon as the "obstacles" are gone */
1082                 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1083                 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1084                 assert(del1 && del2);
1085 #endif
1086 #ifdef CHECKS
1087                 point_t pair;
1088                 pair.x = e->s1->nr;
1089                 pair.y = e->s2->nr;
1090 #ifndef DONT_REMEMBER_CROSSINGS
1091                 assert(dict_contains(status->seen_crossings, &pair));
1092                 dict_del(status->seen_crossings, &pair);
1093 #endif
1094 #endif
1095             }
1096         }
1097     }
1098 }
1099
1100 #ifdef CHECKS
1101 static void check_status(status_t*status)
1102 {
1103     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1104         if((s->pos.x != s->b.x ||
1105             s->pos.y != s->b.y) &&
1106            !dict_contains(status->segs_with_point, s)) {
1107             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1108                     SEGNR(s),
1109                     s->delta.x<0?"-":"+",
1110                     status->y);
1111             assert(0);
1112         }
1113     }
1114 }
1115 #endif
1116
1117 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1118 {
1119     /*
1120           |..|        |...........|                 |           |
1121           |..|        |...........|                 |           |
1122           |..+        +        +..|                 +--+     +--+
1123           |...........|        |..|                    |     |
1124           |...........|        |..|                    |     |
1125      */
1126
1127 #ifdef DEBUG
1128     fprintf(stderr, "========================================================================\n");
1129 #endif
1130     hqueue_t hqueue;
1131     hqueue_init(&hqueue);
1132     gfxpoly_enqueue(poly, 0, &hqueue, 0);
1133
1134     actlist_t* actlist = actlist_new();
1135
1136     event_t*e = hqueue_get(&hqueue);
1137     while(e) {
1138         int32_t y = e->p.y;
1139         int32_t x = 0;
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         char dir_up = 0;
1149         char dir_down = 0;
1150
1151         do {
1152             assert(e->s1->fs);
1153             if(fill && x != e->p.x) {
1154                 assert(!dir_up || !dir_down);
1155                 assert(dir_up || dir_down);
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?DIR_UP:DIR_DOWN;
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             segment_t*s = e->s1;
1191
1192             segment_t*left = 0;
1193             switch(e->type) {
1194                 case EVENT_START: {
1195                     assert(e->p.x == s->a.x && e->p.y == s->a.y);
1196                     actlist_insert(actlist, s->a, s->b, s);
1197                     event_t* e = event_new();
1198                     e->type = EVENT_END;
1199                     e->p = s->b;
1200                     e->s1 = s;
1201                     e->s2 = 0;
1202                     hqueue_put(&hqueue, e);
1203                     left = actlist_left(actlist, s);
1204                     dir_down^=1;
1205                     break;
1206                 }
1207                 case EVENT_END: {
1208                     left = actlist_left(actlist, s);
1209                     actlist_delete(actlist, s);
1210                     advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1211                     dir_up^=1;
1212                     break;
1213                 }
1214                 default: assert(0);
1215             }
1216
1217             x = e->p.x;
1218
1219             fill = fill?0:&edgestyle_default;
1220 #if 0
1221             if(windrule==&windrule_evenodd) {
1222                 if(!!fill != !!fill2) {
1223                     segment_dump(s);
1224                     event_dump(e);
1225                     printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill);
1226                     if(e->type==EVENT_END) {
1227                         printf("            %9p\n", s->fs);
1228                         printf("               |\n");
1229                     }
1230                     printf("              %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled);
1231                     printf("%12p -----+----- %p\n", old_fill, fill2);
1232                     printf("              %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled);
1233                     if(e->type==EVENT_START) {
1234                         printf("                  |\n");
1235                         printf("             %9p\n", s->fs);
1236                     }
1237                 }
1238                 assert(!!fill == !!fill2);
1239             }
1240 #endif
1241
1242 #ifdef DEBUG
1243             fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1244                     y, e->type==EVENT_START?"start":"end",
1245                     s->nr,
1246                     left?left->nr:-1,
1247                     x);
1248 #endif
1249
1250             if(e->type == EVENT_END)
1251                 segment_destroy(s);
1252
1253             event_free(e);
1254             e = hqueue_get(&hqueue);
1255         } while(e && y == e->p.y);
1256
1257 #ifdef CHECKS
1258         edgestyle_t*bleeding = fill;
1259         assert(!bleeding);
1260 #endif
1261     }
1262
1263     actlist_destroy(actlist);
1264     hqueue_destroy(&hqueue);
1265 }
1266
1267 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1268 {
1269     current_polygon = poly1;
1270
1271     status_t status;
1272     memset(&status, 0, sizeof(status_t));
1273     queue_init(&status.queue);
1274     gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1275     if(poly2) {
1276         assert(poly1->gridsize == poly2->gridsize);
1277         gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1278     }
1279
1280     status.windrule = windrule;
1281     status.context = context;
1282     status.actlist = actlist_new();
1283
1284 #ifdef CHECKS
1285     status.seen_crossings = dict_new2(&point_type);
1286     int32_t lasty=-0x80000000;
1287 #endif
1288
1289     status.xrow = xrow_new();
1290
1291     event_t*e = queue_get(&status.queue);
1292     while(e) {
1293         assert(e->s1->fs);
1294         status.y = e->p.y;
1295 #ifdef CHECKS
1296         assert(status.y>=lasty);
1297         lasty = status.y;
1298         status.intersecting_segs = dict_new2(&ptr_type);
1299         status.segs_with_point = dict_new2(&ptr_type);
1300 #endif
1301
1302 #ifdef DEBUG
1303         fprintf(stderr, "----------------------------------- %d\n", status.y);
1304         actlist_dump(status.actlist, status.y-1);
1305 #endif
1306 #ifdef CHECKS
1307         actlist_verify(status.actlist, status.y-1);
1308 #endif
1309         xrow_reset(status.xrow);
1310         do {
1311             xrow_add(status.xrow, e->p.x);
1312             event_apply(&status, e);
1313             event_free(e);
1314             e = queue_get(&status.queue);
1315         } while(e && status.y == e->p.y);
1316
1317         xrow_sort(status.xrow);
1318         segrange_t range;
1319         memset(&range, 0, sizeof(range));
1320 #ifdef DEBUG
1321         actlist_dump(status.actlist, status.y);
1322 #endif
1323         add_points_to_positively_sloped_segments(&status, status.y, &range);
1324         add_points_to_negatively_sloped_segments(&status, status.y, &range);
1325         add_points_to_ending_segments(&status, status.y);
1326
1327         recalculate_windings(&status, &range);
1328 #ifdef CHECKS
1329         check_status(&status);
1330         dict_destroy(status.intersecting_segs);
1331         dict_destroy(status.segs_with_point);
1332 #endif
1333     }
1334 #ifdef CHECKS
1335     dict_destroy(status.seen_crossings);
1336 #endif
1337     actlist_destroy(status.actlist);
1338     queue_destroy(&status.queue);
1339     xrow_destroy(status.xrow);
1340
1341     gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1342     p->gridsize = poly1->gridsize;
1343     p->strokes = status.strokes;
1344
1345 #ifdef CHECKS
1346     /* we only add segments with non-empty edgestyles to strokes in
1347        recalculate_windings, but better safe than sorry */
1348     gfxpolystroke_t*stroke = p->strokes;
1349     while(stroke) {
1350         assert(stroke->fs);
1351         stroke = stroke->next;
1352     }
1353 #endif
1354
1355     add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1356     //add_horizontals(p, windrule, context);
1357     return p;
1358 }
1359
1360 static windcontext_t twopolygons = {2};
1361 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1362 {
1363     return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1364 }
1365 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1366 {
1367     return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);
1368 }