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