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