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