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