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